Finitary Relation - Formal Definitions

Formal 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

The simpler of the two definitions of k-place relations encountered in mathematics is:

Definition 1. A relation L over the sets X₁, …, X_k is a subset of their Cartesian product, written L ⊆ X₁ × … × X_k.

Relations are classified according to the number of sets in the defining Cartesian product, in other words, according to the number of terms following L. Hence:

• Lu denotes a unary relation or property;
• Luv or uLv denote a binary relation;
• Luvw denotes a ternary relation;
• Luvwx denotes a quaternary relation.

Relations with more than four terms are usually referred to as k-ary or n-ary, for example, "a 5-ary relation". A k-ary relation is simply a set of k-tuples.

The second definition 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 n component mathematical objects. In the case of a relation L over k sets, there are k + 1 things to specify, namely, the k sets plus a subset of their Cartesian product. In the idiom, this is expressed by saying that L is a (k + 1)-tuple.

Definition 2. A relation L over the sets X₁, …, X_k is a (k + 1)-tuple L = (X₁, …, X_k, G(L)), where G(L) is a subset of the Cartesian product X₁ × … × X_k. G(L) is called the graph of L.

Elements of a relation are more briefly denoted by using boldface characters, for example, the constant element = (a₁, …, a_k) or the variable element = (x₁, …, x_k).

A statement of the form " is in the relation L " is taken to mean that is in L under the first definition and that is in G(L) under the second definition.

The following considerations apply under either definition:

• The sets X_j for j = 1 to k are called the domains of the relation. Under the first definition, the relation does not uniquely determine a given sequence of domains.
• If all of the domains X_j are the same set X, then it is simpler to refer to L as a k-ary relation over X.
• If any of the domains X_j is empty, then the defining Cartesian product is empty, and the only relation over such a sequence of domains is the empty relation L = . Hence it is commonly stipulated that all of the domains be nonempty.

As a rule, whatever definition best fits the application at hand will be chosen for that purpose, and anything that falls under it will be called a relation for the duration of that discussion. If it becomes necessary to distinguish the two definitions, an entity satisfying the second definition may be called an embedded or included relation.

If L is a relation over the domains X₁, …, X_k, it is conventional to consider a sequence of terms called variables, x₁, …, x_k, that are said to range over the respective domains.

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 the relation L, written ƒ_L or χ(L), is the Boolean-valued function ƒ_L : X₁ × … × X_k → B, defined in such a way that ƒ_L = 1 just in case the k-tuple is in the relation L. Such a function can also be called an indicator function, particularly in probability and statistics, to avoid confusion with the notion of a characteristic function in probability theory.

It is conventional in applied mathematics, computer science, and statistics to refer to a Boolean-valued function like ƒ_L as a k-place predicate. From the more abstract viewpoint of formal logic and model theory, the relation L constitutes a logical model or a relational structure that serves as one of many possible interpretations of some k-place 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. This article treats a relation as the set-theoretic extension of a relational concept or term. A variant usage reserves the term "relation" to the corresponding logical entity, either the logical comprehension, which is the totality of intensions or abstract properties that all of the elements of the relation in extension have in common, or else the symbols that are taken to denote these elements and intensions. Further, some writers of the latter persuasion introduce terms with more concrete connotations, like "relational structure", for the set-theoretic extension of a given relational concept.