Relation (mathematics)

This article sets out the set-theoretic notion of relation. For a more elementary point of view, see binary relations and triadic relations.
For a more combinatorial viewpoint, see theory of relations.

In mathematics, especially set theory, and logic, a relation is a property that assigns truth values to combinations (k-tuples) of k 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 or triadic 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 (zero, one, two, ...), 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, one for the property "is a 0-tuple", and one for its negation ("is not a 0-tuple"). 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:

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

Contents

Informal introduction

Relation is formally defined in the next section. In this section we introduce the concept of a relation with a familiar everyday example. Consider the relation involving three roles that people might play, expressed in a statement of the form "X thinks that Y likes Z ". The facts of a concrete situation could be organized in a Table like the following:

Relation S : X thinks that Y likes Z
Person X Person Y Person Z
Alice Bob Denise
Charles Alice Bob
Charles Charles Alice
Denise Denise Denise

Each row of the Table records a fact or makes an assertion of the form "X thinks that Y likes Z ". For instance, the first row says, in effect, "Alice thinks that Bob likes Denise". The Table represents a relation S over the set P of people under discussion:

P = {Alice, Bob, Charles, Denise}.

The data of the Table are equivalent to the following set of ordered triples:

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

By a slight abuse of notation, it is usual to write S(Alice, Bob, Denise) to say the same thing as the first row of the Table. The relation S is a ternary relation, since there are three items involved in each row. The relation itself is a mathematical object defined in terms of concepts from set theory (i.e., the relation is a subset of the Cartesian product on {Person X, Person Y, Person Z}), that carries all of the information from the Table in one neat package. Mathematically, then, a relation is simply a "set".

The Table for relation S is an extremely simple example of a relational database. The theoretical aspects of databases are the specialty of one branch of computer science, while their practical impacts have become all too familiar in our everyday lives. Computer scientists, logicians, and mathematicians, however, tend to see different things when they look at these concrete examples and samples of the more general concept of a relation.

For one thing, databases are designed to deal with empirical data, and experience is always finite, whereas mathematics at the very least concerns itself with potential infinity. This difference in perspective brings up a number of ideas that may be usefully introduced at this point, if by no means covered in depth.

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[1])

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

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

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 quarternary 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 X1, …, Xk is a (k+1)-tuple L = (X1, …, Xk, G(L)), where G(L) is a subset of the cartesian product X1 × … × Xk. 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 \mathbf{a} = (a1, …, ak) or the variable element \mathbf{x} = (x1, …, xk).

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

The following considerations apply under either definition:

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 X1, …, Xk, it is conventional to consider a sequence of terms called variables, x1, …, xk, that are said to range over the respective domains.

Let a Boolean domain B is a 2-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 fL or χ(L), is the boolean-valued function fL : X1 × … × Xk → B, defined in such a way that fL(\mathbf{x}) = 1 just in case the k-tuple \mathbf{x} is in the relation L. In probability and statistics, where characteristic function has another meaning, indicator function refers to what is here called a characteristic function.

It is conventional in applied mathematics, computer science, and statistics to refer to a Boolean-valued function like fL 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.

Ubiquity in mathematics

Many mathematical relations fall into two broad classes, equivalence relations and order relations. Equivalence relations are also symmetric, while order relations are antisymmetric or asymmetric. The algebraic structure of equivalence relations builds on transformation groups; that of order relations builds on lattice theory. For more on relations and mathematics, from a philosophical standpoint, see Lucas (1999: chpt. 9).

Analogy with functions

Relations generalize functions; just as there is composition of functions, there is composition of relations.

Every relation has an transpose relation, which is related to the inverse function.

Examples

This section discusses, by way of example, the arithmetical binary relation of divisibility and the geometric triadic relation of coplanarity.

Divisibility

A more typical example of a 2-place relation in mathematics is the relation of divisibility between two positive integers n and m that is expressed in statements like "n divides m" or "n goes into m." This is a relation that comes up so often that a special symbol "|" is reserved to express it, allowing one to write "n|m" for "n divides m."

To express the binary relation of divisibility in terms of sets, we have the set P of positive integers, P = {1, 2, 3, …}, and we have the binary relation D on P such that the ordered pair (n, m) is in the relation D just in case n|m. In other turns of phrase that are frequently used, one says that the number n is related by D to the number m just in case n is a factor of m, that is, just in case n divides m with no remainder. The relation D, regarded as a set of ordered pairs, consists of all pairs of numbers (n, m) such that n divides m.

For example, 2 is a factor of 4, and 6 is a factor of 72, which can be written either as 2|4 and 6|72 or as D(2, 4) and D(6, 72).

Coplanarity

For lines L in three-dimensional space, there is a ternary relation picking out the triples of lines that are coplanar. This does not reduce to the binary symmetric relation of coplanarity of pairs of lines.

In other words, writing P(L, M, N) when the lines L, M, and N lie in a plane, and Q(L, M) for the binary relation, it is not true that Q(L, M), Q(M, N) and Q(N, L) together imply P(L, M, N); although the converse is certainly true (any pair out of three coplanar lines is coplanar, a fortiori). There are two geometrical reasons for this.

In one case, for example taking the x-axis, y-axis and z-axis, the three lines are concurrent, i.e. intersect at a single point. In another case, L, M, and N can be the three parallel edges of an infinite triangular prism.

What is true is that if each pair of lines intersects, and the points of intersection are distinct, then pairwise coplanarity implies coplanarity of the triple.

Suggested reading

The logician Augustus De Morgan, in work published around 1860, was the first to articulate the notion of relation in anything like its present sense. He also stated the first formal results in the theory of relations (on De Morgan and relations, see Merrill 1990). Charles Peirce restated and extended De Morgan's results. Russell (1938; 1st ed. 1903) was historically important, in that it brought together in one place many 19th century results on relations, especially orders, by Peirce, Frege, Cantor, Dedekind, and others. Russell and A. N. Whitehead made free use of these results in their epochal Principia Mathematica.

Texts on set theory typically include a chapter on relations (e.g., chpt. 3 in Suppes 1972). But there is no systematic treatise on the theory of relations, even though relations can be found everywhere in mathematics, logic, and theoretical science, and are well-grounded in elementary set theory. Likewise, there is no comprehensive discussion of how algebraic structures emerge from the assumed properties of relations. These lacunae are all the more amazing given that functions are relations, and function is arguably the most ubiquitous concept in all of mathematics. Carnap (1958) is an introduction to mathematical logic that includes an unusual amount of relation theory, but employs an unconventional notation and terminology. In Lucas (1999), relations are an important part of the intersection of mathematics and philosophy. For an introduction to the closely related subject of relation algebra, see Maddux (2006).

Notes

  1. ↑ De Morgan, A. (1858) "On the syllogism, part 3" in Heath, P., ed. (1966) On the syllogism and other logical writings. Routledge. P. 119,

References

Bibliography

See also

External links