Finitary Relation

Finitary Relation

In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple. For a given set of k-tuples, a truth value is assigned to each k-tuple according to whether the property does or does not hold.

An example of a ternary relation (i.e., between three individuals) is: "X was-introduced-to Y by Z", where (X,Y,Z) is a 3-tuple of persons; for example, "Beatrice Wood was introduced to Henri-Pierre Roché by Marcel Duchamp" is true, while "Karl Marx was introduced to Friedrich Engels by Queen Victoria" is false.

The variable k giving the number of "places" in the relation, 3 for the above example, is a non-negative integer, called the relation's arity, adicity, or dimension. A relation with k places is variously called a k-ary, a k-adic, or a k-dimensional relation. Relations with a finite number of places are called finite-place or finitary relations. It is possible to generalize the concept to include infinitary relations between infinitudes of individuals, for example infinite sequences; however, in this article only finitary relations are discussed, which will from now on simply be called relations.

Since there is only one 0-tuple, the so-called empty tuple ( ), there are only two zero-place relations: the one that always holds, and the one that never holds. They are sometimes useful for constructing the base case of an induction argument. One-place relations are called unary relations. For instance, any set (such as the collection of Nobel laureates) can be viewed as a collection of individuals having some property (such as that of having been awarded the Nobel prize). Two-place relations are called binary relations or dyadic relations. The latter term has historic priority. Binary relations are very common, given the ubiquity of relations such as:

• Equality and inequality, denoted by signs such as "=" and "<" in statements like "5 < 12";
• Being a divisor of, denoted by the sign "|" in statements like "13 | 143";
• Set membership, denoted by the sign "∈" in statements like "1 ∈ N".

A k-ary relation, k ≠ 2, is a straightforward generalization of a binary relation.