# Difference between revisions of "Relation (mathematics)"

Jon Awbrey (talk | contribs) (add ref) |
Jon Awbrey (talk | contribs) (→Bibliography: trim annotation) |
||

Line 118: | Line 118: | ||

* Maddux, R.D. (2006), ''Relation Algebras'', vol. 150 in 'Studies in Logic and the Foundations of Mathematics', Elsevier Science. | * Maddux, R.D. (2006), ''Relation Algebras'', vol. 150 in 'Studies in Logic and the Foundations of Mathematics', Elsevier Science. | ||

− | * Mili, A., Desharnais, J., Mili, F., with Frappier, M. (1994), ''Computer Program Construction'', Oxford University Press, New York, NY | + | * Mili, A., Desharnais, J., Mili, F., with Frappier, M. (1994), ''Computer Program Construction'', Oxford University Press, New York, NY. |

* [[Marvin L. Minsky|Minsky, M.L.]], and [[Seymour A. Papert|Papert, S.A.]] (1969/1988), ''[[Perceptron]]s, An Introduction to Computational Geometry'', MIT Press, Cambridge, MA, 1969. Expanded edition, 1988. | * [[Marvin L. Minsky|Minsky, M.L.]], and [[Seymour A. Papert|Papert, S.A.]] (1969/1988), ''[[Perceptron]]s, An Introduction to Computational Geometry'', MIT Press, Cambridge, MA, 1969. Expanded edition, 1988. |

## Revision as of 18:05, 5 September 2007

*This article presents the generalized concept of a relation. For more basic presentations see the articles on binary relations and triadic relations.*

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

- The basic idea is to generalize the concept of a
*2-place relation*, such as the relation of*equality*denoted by the sign "=" in a statement like "5 + 7 = 12" or the relation of*order*denoted by the sign "<" in a statement like "5 < 12". Relations that involve two 'places' or 'roles' are called*binary relations*by some and*dyadic relations*by others, the latter being historically prior but also useful when necessary to avoid confusion with binary (base 2) numerals.

- The next step up is to consider relations that involve increasing but still finite numbers of places or roles. These are called
*finite place*or*finitary*relations. A finitary relation that involves*k*places is variously called a*k-ary*, a*k-adic*, or a*k-dimensional*relation. The number*k*is then called the*arity*, the*adicity*, or the*dimension*of the relation, respectively.

## 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* suspects that *Y* likes *Z* ". The facts of a concrete situation could be organized in a Table like the following:

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* suspects that *Y* likes *Z* ". For instance, the first row says, in effect, "Alice suspects 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 overuse 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, that carries all of 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: 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 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}, …, *X*_{k} is a subset of their cartesian product, written *L* ⊆ *X*_{1} × … × *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, 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*_{1}, …, *X*_{k} is a (*k*+1)-tuple *L* = (*X*_{1}, …, *X*_{k}, *G*(*L*)), where *G*(*L*) is a subset of the cartesian product *X*_{1} × … × *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 \(\mathbf{a}\) = (a_{1}, …, a_{k}) or the variable element \(\mathbf{x}\) = (*x*_{1}, …, *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 *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. In the case of the first definition, the relation itself does not uniquely determine a given sequence of domains.

- The sets

- If all of the domains
*X*_{j}are the same set*X*, then*L*is more simply referred to as a*k*-ary relation over*X*.

- If all of the domains

- If any of the domains
*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\). As a result, naturally occurring applications of the relation concept typically involve a stipulation that all of the domains be nonempty.

- If any of the domains

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 alternatives, the latter type of object can be referred to as an *embedded* or *included* relation.

If *L* is a relation over the domains *X*_{1}, …, *X*_{k}, it is conventional to consider a sequence of terms called *variables*, *x*_{1}, …, *x*_{k}, that are said to *range over* the respective domains.

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

The *characteristic function* of the relation *L*, written *f*_{L} or χ(*L*), is the boolean-valued function *f*_{L} : *X*_{1} × … × *X*_{k} → **B**, defined in such a way that *f*_{L}(\(\mathbf{x}\)) = 1 just in case the *k*-tuple \(\mathbf{x}\) is in the relation *L*. The characteristic function of a relation may also be called its *indicator function*, especially in probability and statistics.

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 different styles of study on the same areas of interest, the reader will find much variation in usage here. The variation presented in this article treats a relation as the set-theoretic *extension* of a relational concept or term. Another variation 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, but hardly finally, 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.

## Example: 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 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 according to the number of sets in the cartesian product, in other words the number of terms in the expression:

- Unary relation or property:
*L*(*u*) - Binary relation:
*L*(*u*,*v*) or*u**L**v* - Ternary relation:
*L*(*u*,*v*,*w*) - Quaternary relation:
*L*(*u*,*v*,*w*,*x*)

- Unary relation or property:

Relations with more than four terms are usually referred to as *k*-ary, for example, "a 5-ary relation".

## References

- Peirce, C.S. (1870), "Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic",
*Memoirs of the American Academy of Arts and Sciences*9, 317–378, 1870. Reprinted,*Collected Papers*CP 3.45–149,*Chronological Edition*CE 2, 359–429.

- Ulam, S.M. and Bednarek, A.R. (1990), "On the Theory of Relational Structures and Schemata for Parallel Computation", pp. 477–508 in A.R. Bednarek and Françoise Ulam (eds.),
*Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators*, University of California Press, Berkeley, CA.

## Bibliography

- Bourbaki, N. (1994),
*Elements of the History of Mathematics*, John Meldrum (trans.), Springer-Verlag, Berlin, Germany.

- Halmos, P.R. (1960),
*Naive Set Theory*, D. Van Nostrand Company, Princeton, NJ.

- Lawvere, F.W., and Rosebrugh, R. (2003),
*Sets for Mathematics*, Cambridge University Press, Cambridge, UK.

- Maddux, R.D. (2006),
*Relation Algebras*, vol. 150 in 'Studies in Logic and the Foundations of Mathematics', Elsevier Science.

- Mili, A., Desharnais, J., Mili, F., with Frappier, M. (1994),
*Computer Program Construction*, Oxford University Press, New York, NY.

- Minsky, M.L., and Papert, S.A. (1969/1988),
*Perceptrons, An Introduction to Computational Geometry*, MIT Press, Cambridge, MA, 1969. Expanded edition, 1988.

- Peirce, C.S. (1984),
*Writings of Charles S. Peirce : A Chronological Edition, Volume 2, 1867-1871*, Peirce Edition Project (eds.), Indiana University Press, Bloomington, IN.

- Royce, J. (1961),
*The Principles of Logic*, Philosophical Library, New York, NY.

- Tarski, A. (1956/1983),
*Logic, Semantics, Metamathematics, Papers from 1923 to 1938*, J.H. Woodger (trans.), 1st edition, Oxford University Press, 1956. 2nd edition, J. Corcoran (ed.), Hackett Publishing, Indianapolis, IN, 1983.

- Ulam, S.M. (1990),
*Analogies Between Analogies : The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators*, A.R. Bednarek and Françoise Ulam (eds.), University of California Press, Berkeley, CA.

- Venetus, P. (1984),
*Logica Parva, Translation of the 1472 Edition with Introduction and Notes*, Alan R. Perreiah (trans.), Philosophia Verlag, Munich, Germany.

## See also

Template:Col-breakTemplate:Col-break- Direct relationship
- Inverse relationship
- Logic of relatives
- Logical matrix
- Projection
- Sign relation
- Tacit extension
- Theory of relations
- Triadic relation

## 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.