# Finitary relation

In mathematics, a finitary relation over sets X1, …, Xn is a subset of the Cartesian product X1 × … × Xn; that is, it is a set of n-tuples (x1, …, xn) consisting of elements xi in Xi. Typically, the relation describes a possible connection between the elements of an n-tuple. For example, the relation "x is divisible by y and z" consists of the set of 3-tuples such that when substituted to x, y and z, respectively, make the sentence true.

The non-negative integer n giving the number of "places" in the relation is called the arity, adicity or degree of the relation. A relation with n "places" is variously called an n-ary relation, an n-adic relation or a relation of degree n. Relations with a finite number of places are called finitary relations (or simply relations if the context is clear). It is also possible to generalize the concept to infinitary relations with infinite sequences.

An n-ary relation over sets X1, …, Xn is an element of the power set of X1 × … × Xn.

0-ary relations count only two members: the one that always holds, and the one that never holds. This is because there is only one 0-tuple, the empty tuple (). They are sometimes useful for constructing the base case of an induction argument.

Unary relations can be viewed as a collection of members (such as the collection of Nobel laureates) having some property (such as that of having been awarded the Nobel prize).

Binary relations are the most commonly studied form of finitary relations. When X1 = X2 it is called a homogeneous relation, for example:

• Equality and inequality, denoted by signs such as = and < in statements such as "5 < 12", or
• Divisibility, denoted by the sign | in statements such as "13|143".

Otherwise it is a heterogeneous relation, for example:

• Set membership, denoted by the sign ∈ in statements such as "1 ∈ N".

## Example

Consider the ternary relation R "x thinks that y likes z" over the set of people P = {Alice, Bob, Charles, Denise}, defined by:

R = {(Alice, Bob, Denise), (Charles, Alice, Bob), (Charles, Charles, Alice), (Denise, Denise, Denise)}.

R can be represented equivalently by the following table:

Relation R "x thinks that y likes z"
P P P
Alice Bob Denise
Charles Alice Bob
Charles Charles Alice
Denise Denise Denise

Here, each row represents a triple of R, that is it makes a statement of the form "x thinks that y likes z". For instance, the first row states that "Alice thinks that Bob likes Denise". All rows are distinct. The ordering of rows is insignificant but the ordering of columns is significant.

The above table is also a simple example of a relational database, a field with theory rooted in relational algebra and applications in data management. Computer scientists, logicians, and mathematicians, however, tend to have different conceptions what a general relation is, and what it is consisted of. For example, databases are designed to deal with empirical data, which is by definition finite, whereas in mathematics, relations with infinite arity (i.e., infinitary relation) are also considered.

## Definitions

When two objects, qualities, classes, or attributes, viewed together by the mind, are seen under some connexion, that connexion is called a relation.

The first definition of relations encountered in mathematics is:

Definition 1. — An n-ary relation R over sets X1, …, Xn is a subset of the Cartesian product X1 × … × Xn.

The second definition of relations makes use of an idiom that is common in mathematics, stipulating that "such and such is an n-tuple" in order to ensure that such and such a mathematical object is determined by the specification of mathematical objects with n elements. In the case of a relation R over n sets, there are n + 1 things to specify, namely, the n sets plus a subset of their Cartesian product. In the idiom, this is expressed by saying that R is a (n + 1)-tuple.

Definition 2. — An n-ary relation R over sets X1, …, Xn is an (n + 1)-tuple (X1, …, Xn, G) where G is a subset of the Cartesian product X1 × … × Xn called the graph of R.

As a rule, whatever definition best fits the application at hand will be chosen for that purpose, and if it ever becomes necessary to distinguish between the two definitions, then an entity satisfying the second definition may be called an embedded or included relation.

Both statements (x1, …, xn) in R (under the first definition) and (x1, …, xn) in G (under the second definition) read "x1, …, xn are R-related" and are denoted by the prefix notation Rx1xn or the postfix notation x1xnR. In the case where R is a binary relation, those statements are also denoted by the infix notation x1Rx2.

The following considerations apply under either definition:

• The set Xi is called the ith domain of R. Under the first definition, the relation does not uniquely determine a given sequence of domains. In the case where R is a binary relation, X1 is also called simply the domain or set of departure of R, and X2 is also called the codomain or set of destination of R.
• When the elements of Xi are relations, Xi is called a nonsimple domain of R.
• The set of all xi in Xi for which there exists (x1, …, xi − 1, xi + 1, …, xn) in X1 × … × Xi − 1 × Xi + 1 × … × Xn such that Rx1xi − 1xixi + 1xn is called the ith domain of definition or active domain of R. In the case where R is a binary relation, its first domain of definition is also called simply the domain of definition or active domain of R, and its second domain of definition is also called the codomain of definition or active codomain of R.
• When the ith domain of definition of R is equal to Xi, R is said to be total on Xi. In the case where R is a binary relation, when R is total on X1, it is also said to be left-total or serial, and when R is total on X2, it is also said to be right-total or surjective.
• When for all x and y in πiI Xi and for all z in πiJ Xi where {I, J} is a partition of {1, …, n}, if the components of x and z are R-related and the components of y and z are R-related then x = y, R is said to be unique on {Xi}iI, and {Xi}iJ is called a primary key of R. In the case where R is a binary relation, when R is unique on {X1}, it is also said to be left-unique or injective, and when R is unique on {X2}, it is also said to be right-unique or functional.
• When all Xi are the same set X, it is simpler to refer to R as an n-ary relation over X, called a homogeneous relation. Otherwise R is called a heterogeneous relation.
• When any of Xi is empty, the defining Cartesian product is empty, and the only relation over such a sequence of domains is the empty relation R = ∅. Hence it is commonly stipulated that all of the domains be nonempty.

Let a Boolean domain B be a two-element set, say, B = {0, 1}, whose elements can be interpreted as logical values, typically 0 = false and 1 = true. The characteristic function of R, denoted by χR, is the Boolean-valued function χR: X1 × … × XnB, defined by χR((x1, …, xn)) = 1 if Rx1xn and χR((x1, …, xn)) = 0 otherwise.

In applied mathematics, computer science and statistics, it is common to refer to a Boolean-valued function as an n-ary predicate. From the more abstract viewpoint of formal logic and model theory, the relation R constitutes a logical model or a relational structure, that serves as one of many possible interpretations of some n-ary predicate symbol.

Because relations arise in many scientific disciplines, as well as in many branches of mathematics and logic, there is considerable variation in terminology. Aside from the set-theoretic extension of a relational concept or term, the term "relation" can also be used to refer to the corresponding logical entity, either the logical comprehension, which is the totality of intensions or abstract properties shared by all elements in the relation, or else the symbols denoting these elements and intensions. Further, some writers of the latter persuasion introduce terms with more concrete connotations (such as "relational structure" for the set-theoretic extension of a given relational concept).