Relation (mathematics)

☞ This page belongs to resource collections on Logic and Inquiry.

In mathematics, a finitary relation is defined by one of the formal definitions given below.

Informal introduction

The definition of relation given in the next section formally captures a concept that is actually quite familiar from everyday life.  For example, consider the relationship, involving three roles that people might play, expressed in a statement of the form X ~\text{suspects that}~ Y ~\text{likes}~ Z.\!  The facts of a concrete situation could be organized in the form of a Table like the one below:


\text{Relation}~ S ~:~ X ~\text{suspects that}~ Y ~\text{likes}~ Z\!
\text{Person}~ X\! \text{Person}~ Y\! \text{Person}~ Z\!
\text{Alice}\! \text{Bob}\! \text{Denise}\!
\text{Charles}\! \text{Alice}\! \text{Bob}\!
\text{Charles}\! \text{Charles}\! \text{Alice}\!
\text{Denise}\! \text{Denise}\! \text{Denise}\!


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

P ~=~ \{ \text{Alice}, \text{Bob}, \text{Charles}, \text{Denise} \}\!

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

\begin{smallmatrix} S & = & \{ & \text{(Alice, Bob, Denise)}, & \text{(Charles, Alice, Bob)}, & \text{(Charles, Charles, Alice)}, & \text{(Denise, Denise, Denise)} & \} \end{smallmatrix}\!

By a slight overuse of notation, it is usual to write S (\text{Alice}, \text{Bob}, \text{Denise})\! to say the same thing as the first row of the Table.  The relation S\! is a triadic or 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, that carries all the information from the Table in one neat package.

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 is nothing if not concerned with infinity, at the very least, potential infinity. This difference in perspective brings up a number of ideas that are usefully introduced at this point, if by no means covered in depth.

Example 1. Divisibility

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

To express the binary relation of divisibility in terms of sets, we have the set P\! of positive integers, P = \{ 1, 2, 3, \ldots \},\! 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 two facts can be written either as 2|4\! and 6|72\! or as D(2, 4)\! and D(6, 72).\!

Formal definitions

There are two definitions of k\!-place relations that are commonly encountered in mathematics.  In order of simplicity, the first of these definitions is as follows:

Definition 1.   A relation L\! over the sets X_1, \ldots, X_k\! is a subset of their cartesian product, written L \subseteq X_1 \times \ldots \times X_k.\!  Under this definition, then, a k\!-ary relation is simply a set of k\!-tuples.

The second definition makes use of an idiom that is common in mathematics, saying that “such and such is an n\!-tuple” to mean that the mathematical object being defined 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_1, \ldots, X_k\! is a (k+1)\!-tuple L = (X_1, \ldots, X_k, \mathrm{graph}(L)),\! where \mathrm{graph}(L)\! is a subset of the cartesian product X_1 \times \ldots \times X_k~\! called the graph of L.\!

Elements of a relation are sometimes denoted by using boldface characters, for example, the constant element \mathbf{a} = (a_1, \ldots, a_k)\! or the variable element \mathbf{x} = (x_1, \ldots, x_k).\!

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 \mathrm{graph}(L)\! under the second definition.

The following considerations apply under either definition:

  • The sets X_j~\! for j = 1 ~\text{to}~ k\! are called the domains of the relation.  In the case of the first definition, the relation itself does not uniquely determine a given sequence of domains.
  • If all the domains X_j~\! are the same set X,\! then L\! is more simply referred to as a k\!-ary relation over X.\!
  • If any domain X_j~\! is empty then the cartesian product is empty and the only relation over such a sequence of domains is the empty relation L = \varnothing.\!  Most applications of the relation concept will set aside this trivial case and assume that all domains are nonempty.

If L\! is a relation over the domains X_1, \ldots, X_k,\! it is conventional to consider a sequence of terms called variables, x_1, \ldots, x_k,\! that are said to range over the respective domains.

A boolean domain \mathbb{B}\! is a generic 2-element set, say, \mathbb{B} = \{ 0, 1 \},\! whose elements are interpreted as logical values, typically 0 = \mathrm{false}\! and 1 = \mathrm{true}.\!

The characteristic function of the relation L,\! written f_L\! or \chi(L),\! is the boolean-valued function f_L : X_1 \times \ldots \times X_k \to \mathbb{B},\! defined in such a way that f_L (\mathbf{x}) = 1\! just in case the k\!-tuple \mathbf{x} = (x_1, \ldots, x_k)\! is in the relation L.\!  The characteristic function of a relation may also be called its indicator function, especially in probabilistic and statistical contexts.

It is conventional in applied mathematics, computer science, and statistics to refer to a boolean-valued function like f_L\! as a k\!-place predicate.  From the more abstract viewpoints of formal logic and model theory, the relation L\! is seen as constituting a logical model or a relational structure that serves as one of many possible interpretations of a corresponding k\!-place predicate symbol, as that term is used in predicate calculus.

Due to the convergence of many traditions of study, there are wide variations in the language used to describe relations.  The extensional approach presented in this article treats a relation as the set-theoretic extension of a relational concept or term.  An alternative, intensional approach reserves the term relation to the corresponding logical entity, either the logical comprehension, which is the totality of intensions or abstract properties that all the elements of the extensional relation have in common, or else the symbols that are taken to denote those elements and intensions.

Example 2. Coplanarity

For lines \ell\! in three-dimensional space, there is a triadic relation picking out the triples of lines that are coplanar.  This does not reduce to the dyadic relation of coplanarity between pairs of lines.

In other words, writing P(\ell, m, n)\! when the lines \ell, m, n\! lie in a plane, and Q(\ell, m)\! for the binary relation, it is not true that Q(\ell, m),\! Q(m, n),\! and Q(n, \ell)\! together imply P(\ell, m, n),\! although the converse is certainly true:  any two of three coplanar lines are necessarily coplanar.  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, that is, they intersect at a single point.  In another case, \ell, m, n\! can be three 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.

Remarks

Relations are classified by the number of sets in the cartesian product, in other words, the number of places or terms in the relational expression:

L(a)\! Monadic or unary relation, in other words, a property or set
L(a, b) ~\text{or}~ a L b\! Dyadic or binary relation
L(a, b, c)\! Triadic or ternary relation
L(a, b, c, d)\! Tetradic or quaternary relation
L(a, b, c, d, e)\! Pentadic or quinary relation

Relations with more than five terms are usually referred to as k\!-adic or k\!-ary, for example, a 6-adic, 6-ary, or hexadic relation.

References

Bibliography

Syllabus

Focal nodes

Peer nodes

Logical operators

Related topics

Relational concepts

Information, Inquiry

Related articles

Document history

Portions of the above article were adapted from the following sources under the GNU Free Documentation License, under other applicable licenses, or by permission of the copyright holders.

This article is issued from Wikiversity - version of the Saturday, November 14, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.