Relation (mathematics)

From Ref
Jump to: navigation, search

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.

  • The basic idea is to generalize the concept of a two-place relation, such as the relation of equality denoted by the sign “” in a statement like Failed to parse (Missing texvc executable; please see math/README to configure.):
or the relation of order denoted by the sign “Failed to parse (Missing texvc executable; please see math/README to configure.): 

” in a statement like Failed to parse (Missing texvc executable; please see math/README to configure.):   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 concept of a two-place relation is generalized by considering relations with increasing but still finite numbers of places or roles.  These are called finite-place or finitary relations.  A finitary relation involving places is variously called a -ary, -adic, or -dimensional relation.  The number 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 Failed to parse (Missing texvc executable; please see math/README to configure.):   The facts of a concrete situation could be organized in the form of a Table like the one below:


Failed to parse (Missing texvc executable; please see math/README to configure.):
Failed to parse (Missing texvc executable; please see math/README to configure.): Failed to parse (Missing texvc executable; please see math/README to configure.): Failed to parse (Missing texvc executable; please see math/README to configure.):
Failed to parse (Missing texvc executable; please see math/README to configure.): Failed to parse (Missing texvc executable; please see math/README to configure.): Failed to parse (Missing texvc executable; please see math/README to configure.):
Failed to parse (Missing texvc executable; please see math/README to configure.): Failed to parse (Missing texvc executable; please see math/README to configure.): Failed to parse (Missing texvc executable; please see math/README to configure.):
Failed to parse (Missing texvc executable; please see math/README to configure.): Failed to parse (Missing texvc executable; please see math/README to configure.): Failed to parse (Missing texvc executable; please see math/README to configure.):
Failed to parse (Missing texvc executable; please see math/README to configure.): Failed to parse (Missing texvc executable; please see math/README to configure.): Failed to parse (Missing texvc executable; please see math/README to configure.):


Each row of the Table records a fact or makes an assertion of the form Failed to parse (Missing texvc executable; please see math/README to configure.):   For instance, the first row says, in effect, Failed to parse (Missing texvc executable; please see math/README to configure.):   The Table represents a relation over the set Failed to parse (Missing texvc executable; please see math/README to configure.):

of people under discussion:
Failed to parse (Missing texvc executable; please see math/README to configure.):

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

Failed to parse (Missing texvc executable; please see math/README to configure.):

By a slight overuse of notation, it is usual to write Failed to parse (Missing texvc executable; please see math/README to configure.):

to say the same thing as the first row of the Table.  The relation  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 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 Failed to parse (Missing texvc executable; please see math/README to configure.):

and Failed to parse (Missing texvc executable; please see math/README to configure.): 
that is expressed in statements like Failed to parse (Missing texvc executable; please see math/README to configure.): 
or Failed to parse (Missing texvc executable; please see math/README to configure.): 

  This is a relation that comes up so often that a special symbol Failed to parse (Missing texvc executable; please see math/README to configure.):

is reserved to express it, allowing one to write Failed to parse (Missing texvc executable; please see math/README to configure.): 
for Failed to parse (Missing texvc executable; please see math/README to configure.): 


To express the binary relation of divisibility in terms of sets, we have the set Failed to parse (Missing texvc executable; please see math/README to configure.):

of positive integers, Failed to parse (Missing texvc executable; please see math/README to configure.): 
and we have the binary relation Failed to parse (Missing texvc executable; please see math/README to configure.): 
on Failed to parse (Missing texvc executable; please see math/README to configure.): 
such that the ordered pair Failed to parse (Missing texvc executable; please see math/README to configure.): 
is in the relation Failed to parse (Missing texvc executable; please see math/README to configure.): 
just in case Failed to parse (Missing texvc executable; please see math/README to configure.): 

  In other turns of phrase that are frequently used, one says that the number Failed to parse (Missing texvc executable; please see math/README to configure.):

is related by Failed to parse (Missing texvc executable; please see math/README to configure.): 
to the number Failed to parse (Missing texvc executable; please see math/README to configure.): 
just in case Failed to parse (Missing texvc executable; please see math/README to configure.): 
is a factor of Failed to parse (Missing texvc executable; please see math/README to configure.): 
that is, just in case Failed to parse (Missing texvc executable; please see math/README to configure.): 
divides Failed to parse (Missing texvc executable; please see math/README to configure.): 
with no remainder.  The relation Failed to parse (Missing texvc executable; please see math/README to configure.): 
regarded as a set of ordered pairs, consists of all pairs of numbers Failed to parse (Missing texvc executable; please see math/README to configure.): 
such that Failed to parse (Missing texvc executable; please see math/README to configure.): 
divides Failed to parse (Missing texvc executable; please see math/README to configure.): 


For example, Failed to parse (Missing texvc executable; please see math/README to configure.):

is a factor of Failed to parse (Missing texvc executable; please see math/README to configure.): 
and Failed to parse (Missing texvc executable; please see math/README to configure.): 
is a factor of Failed to parse (Missing texvc executable; please see math/README to configure.): 
which two facts can be written either as Failed to parse (Missing texvc executable; please see math/README to configure.): 
and Failed to parse (Missing texvc executable; please see math/README to configure.): 
or as Failed to parse (Missing texvc executable; please see math/README to configure.): 
and Failed to parse (Missing texvc executable; please see math/README to configure.): 


Formal definitions

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

Definition 1.   A relation over the sets is a subset of their cartesian product, written   Under this definition, then, a -ary relation is simply a set of -tuples.

The second definition makes use of an idiom that is common in mathematics, saying that “such and such is an Failed to parse (Missing texvc executable; please see math/README to configure.): -tuple” to mean that the mathematical object being defined is determined by the specification of Failed to parse (Missing texvc executable; please see math/README to configure.):

component mathematical objects.  In the case of a relation  over  sets, there are Failed to parse (Missing texvc executable; please see math/README to configure.): 
things to specify, namely, the  sets plus a subset of their cartesian product.  In the idiom, this is expressed by saying that  is a -tuple.

Definition 2.   A relation over the sets is a -tuple Failed to parse (Missing texvc executable; please see math/README to configure.):

where  is a subset of the cartesian product Failed to parse (Missing texvc executable; please see math/README to configure.): 
called the graph of 

Elements of a relation are sometimes denoted by using boldface characters, for example, the constant element Failed to parse (Missing texvc executable; please see math/README to configure.):

or the variable element Failed to parse (Missing texvc executable; please see math/README to configure.): 


A statement of the form “Failed to parse (Missing texvc executable; please see math/README to configure.):

is in the relation ” is taken to mean that Failed to parse (Missing texvc executable; please see math/README to configure.): 
is in  under the first definition and that Failed to parse (Missing texvc executable; please see math/README to configure.): 
is in  under the second definition.

The following considerations apply under either definition:

  • The sets Failed to parse (Missing texvc executable; please see math/README to configure.):
for Failed to parse (Missing texvc executable; please see math/README to configure.): 
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 Failed to parse (Missing texvc executable; please see math/README to configure.):
are the same set  then  is more simply referred to as  a -ary relation over 
  • If any domain Failed to parse (Missing texvc executable; please see math/README to configure.):
is empty then the cartesian product is empty and the only relation over such a sequence of domains is the empty relation Failed to parse (Missing texvc executable; please see math/README to configure.): 

  Most applications of the relation concept will set aside this trivial case and assume that all domains are nonempty.

If is a relation over the domains it is conventional to consider a sequence of terms called variables, Failed to parse (Missing texvc executable; please see math/README to configure.):

that are said to range over the respective domains.

A boolean domain is a generic 2-element set, say, Failed to parse (Missing texvc executable; please see math/README to configure.):

whose elements are interpreted as logical values, typically Failed to parse (Missing texvc executable; please see math/README to configure.): 
and Failed to parse (Missing texvc executable; please see math/README to configure.): 


The characteristic function of the relation written Failed to parse (Missing texvc executable; please see math/README to configure.):

or Failed to parse (Missing texvc executable; please see math/README to configure.): 
is the boolean-valued function Failed to parse (Missing texvc executable; please see math/README to configure.): 
defined in such a way that Failed to parse (Missing texvc executable; please see math/README to configure.): 
just in case the -tuple Failed to parse (Missing texvc executable; please see math/README to configure.): 
is in the relation   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 Failed to parse (Missing texvc executable; please see math/README to configure.):

as a -place predicate.  From the more abstract viewpoints of formal logic and model theory, the relation  is seen as constituting a logical model or a relational structure that serves as one of many possible interpretations of a corresponding -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 Failed to parse (Missing texvc executable; please see math/README to configure.):

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 Failed to parse (Missing texvc executable; please see math/README to configure.):

when the lines Failed to parse (Missing texvc executable; please see math/README to configure.): 
lie in a plane, and Failed to parse (Missing texvc executable; please see math/README to configure.): 
for the binary relation, it is not true that Failed to parse (Missing texvc executable; please see math/README to configure.): 
Failed to parse (Missing texvc executable; please see math/README to configure.): 
and Failed to parse (Missing texvc executable; please see math/README to configure.): 
together imply Failed to parse (Missing texvc executable; please see math/README to configure.): 
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 -axis, -axis, and -axis, the three lines are concurrent, that is, they intersect at a single point.  In another case, Failed to parse (Missing texvc executable; please see math/README to configure.):

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:

Failed to parse (Missing texvc executable; please see math/README to configure.): Monadic or unary relation, in other words, a property or set
Failed to parse (Missing texvc executable; please see math/README to configure.): Dyadic or binary relation
Failed to parse (Missing texvc executable; please see math/README to configure.): Triadic or ternary relation
Failed to parse (Missing texvc executable; please see math/README to configure.): Tetradic or quaternary relation
Failed to parse (Missing texvc executable; please see math/README to configure.): Pentadic or quinary relation

Relations with more than five terms are usually referred to as -adic or -ary, for example, a 6-adic, 6-ary, or hexadic 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.

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.