Finitary relation

The non-negative integer n that gives 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.

Definitions

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

— Augustus De Morgan

Definition— An n-ary relation R on sets X₁, ..., X_n is a subset of the Cartesian product X₁ × ... × X_n.

Since the definition is predicated on the underlying sets X₁, ..., X_n, R may be more formally defined as the (n + 1)-tuple (X₁, ..., X_n, G), where G, called the graph of R, is a subset of the Cartesian product X₁ × ... × X_n.

As is often done in mathematics, the same symbol is used to refer to the mathematical object and an underlying set, so the statement (x₁, ..., x_n) ∈ R is often used to mean (x₁, ..., x_n) ∈ G, is read "x₁, ..., x_n are R-related", and is denoted using prefix notation by Rx₁⋯x_n and using postfix notation by x₁⋯x_nR. In the case where R is a binary relation, those statements are also denoted using infix notation by x₁Rx₂.

The following considerations apply:

• The set X_i is called the ith domain of R. In the case where R is a binary relation, X₁ is also called simply the domain or set of departure of R, and X₂ is also called the codomain or set of destination of R.
• When the elements of X_i are relations, X_i is called a nonsimple domain of R.
• The set of ∀x_i ∈ X_i such that Rx₁⋯x_i−1x_ix_i+1⋯x_n for at least one (x₁, ..., x_n) 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 X_i, R is said to be total on its ith domain (or on X_i, when this is not ambiguous). In the case where R is a binary relation, when R is total on X₁, it is also said to be left-total (or serial, in the special case where X₁ = X₂), and when R is total on X₂, it is also said to be right-total or surjective.
• When ∀x ∀y ∈ X_i. ∀z ∈ X_j. xR_ijz ∧ yR_ijz ⇒ x = y, where i ∈ I, j ∈ J, R_ij = π_ij R, and {I, J} is a partition of {1, ..., n}, R is said to be unique on {X_i}_i∈I, and {X_i}_i∈J is called a primary key of R. In the case where R is a binary relation, when R is unique on {X₁}, it is also said to be left-unique or injective, and when R is unique on {X₂}, it is also said to be univalent or right-unique.
• When all X_i are the same set X, it is simpler to refer to R as an n-ary relation over X, called a homogeneous relation. Without this restriction, R is called a heterogeneous relation.
• When any of X_i is empty, the defining Cartesian product is empty, and the only relation over such a sequence of domains is the empty relation R = ∅.

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: X₁ × ... × X_n → B, defined by χ_R((x₁, ..., x_n)) = 1 if Rx₁⋯x_n and χ_R((x₁, ..., x_n)) = 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).