Relation (mathematics)
Encyclopedia
In set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

 and logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

, a relation is a property that assigns truth values to k-tuples
Tuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...

 of 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 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
Beatrice Wood
Beatrice Wood was an American artist and studio potter, who late in life was dubbed the "Mama of Dada," and served as a partial inspiration for the character of Rose DeWitt Bukater in James Cameron's 1997 film, Titanic...

 was introduced to Henri-Pierre Roché
Henri-Pierre Roché
Henri-Pierre Roché was a French author who was deeply involved with the artistic avant-garde in Paris and the Dada movement.- Biography :Roché was born in Paris, France. In 1898, he was an art student at the Académie Julian....

 by Marcel Duchamp
Marcel Duchamp
Marcel Duchamp was a French artist whose work is most often associated with the Dadaist and Surrealist movements. Considered by some to be one of the most important artists of the 20th century, Duchamp's output influenced the development of post-World War I Western art...

" is true, while "Karl Marx
Karl Marx
Karl Heinrich Marx was a German philosopher, economist, sociologist, historian, journalist, and revolutionary socialist. His ideas played a significant role in the development of social science and the socialist political movement...

 was introduced to Friedrich Engels
Friedrich Engels
Friedrich Engels was a German industrialist, social scientist, author, political theorist, philosopher, and father of Marxist theory, alongside Karl Marx. In 1845 he published The Condition of the Working Class in England, based on personal observations and research...

 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
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

 (zero, one, two, ...), called the relation's arity
Arity
In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...

, adicity, or dimension
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...

. 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
Finitary
In mathematics or logic, a finitary operation is one, like those of arithmetic, that takes a finite number of input values to produce an output. An operation such as taking an integral of a function, in calculus, is defined in such a way as to depend on all the values of the function , and is so...

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: the one that always holds, and the one that never holds. They are sometimes useful for constructing the base case of an induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...

 argument. 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
Nobel Prize
The Nobel Prizes are annual international awards bestowed by Scandinavian committees in recognition of cultural and scientific advances. The will of the Swedish chemist Alfred Nobel, the inventor of dynamite, established the prizes in 1895...

). Two-place relations are called binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

s or dyadic relations. The latter term has historic priority. Binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

s are very common, given the ubiquity of relations such as:
  • Equality and inequality, denoted by signs such as "=" and "<" in statements like "5 < 12";
  • Being a divisor
    Divisor
    In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...

     of, denoted by the sign "|" in statements like "13 | 1001";
  • Set membership, denoted by the sign "∈" in statements like "1 ∈ N".

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

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
Mathematical object
In mathematics and the philosophy of mathematics, a mathematical object is an abstract object arising in mathematics.Commonly encountered mathematical objects include numbers, permutations, partitions, matrices, sets, functions, and relations...

 defined in terms of concepts from set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

 (i.e., the relation is a subset of the Cartesian product
Cartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...

 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
Relational database
A relational database is a database that conforms to relational model theory. The software used in a relational database is called a relational database management system . Colloquial use of the term "relational database" may refer to the RDBMS software, or the relational database itself...

. The theoretical aspects of databases are the specialty of one branch of computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, 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

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
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

 of their Cartesian product
Cartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...

, written LX1 × … × 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
    Property (philosophy)
    In modern philosophy, logic, and mathematics a property is an attribute of an object; a red object is said to have the property of redness. The property may be considered a form of object in its own right, able to possess other properties. A property however differs from individual objects in that...

    ;
  • Luv or uLv denote a binary relation
    Binary relation
    In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

    ;
  • 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-tuple
Tuple
In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...

s.

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, …, XkG(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 = (a1, …, ak) or the variable element = (x1, …, xk).

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 Xj for j = 1 to k are called the domain
    Domain (mathematics)
    In mathematics, the domain of definition or simply the domain of a function is the set of "input" or argument values for which the function is defined...

    s of the relation. Under the first definition, the relation does not uniquely determine a given sequence of domains.
  • If all of the domains Xj 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 Xj 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 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
Boolean domain
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include false and true...

 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
Characteristic function
In mathematics, characteristic function can refer to any of several distinct concepts:* The most common and universal usage is as a synonym for indicator function, that is the function* In probability theory, the characteristic function of any probability distribution on the real line is given by...

 of the relation L, written ƒL or χ(L), is the Boolean-valued function
Boolean-valued function
A boolean-valued function, in some usages is a predicate or a proposition, is a function of the type f : X → B, where X is an arbitrary set and where B is a boolean domain....

 ƒL : X1 × … × Xk → B, defined in such a way that ƒL() = 1 just in case the k-tuple is in the relation L. In probability
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...

 and statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....

, 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
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, and statistics to refer to a Boolean-valued function like ƒL as a k-place predicate. From the more abstract viewpoint of formal logic
Formal logic
Classical or traditional system of determining the validity or invalidity of a conclusion deduced from two or more statements...

 and model theory
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

, the relation L constitutes a logical model or a relational structure that serves as one of many possible interpretation
Interpretation (logic)
An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...

s of some k-place predicate symbol.

Because relations arise in many scientific disciplines as well as in many branches of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 and logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

, there is considerable variation in terminology. This article treats a relation as the set-theoretic
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

 extension
Extension (semantics)
In any of several studies that treat the use of signs - for example, in linguistics, logic, mathematics, semantics, and semiotics - the extension of a concept, idea, or sign consists of the things to which it applies, in contrast with its comprehension or intension, which consists very roughly of...

 of a relational concept or term. A variant usage reserves the term "relation" to the corresponding logical entity, either the logical comprehension
Comprehension (logic)
In logic, the comprehension of an object is the totality of intensions, that is, attributes, characters, marks, properties, or qualities, that the object possesses, or else the totality of intensions that are pertinent to the context of a given discussion...

, which is the totality of intension
Intension
In linguistics, logic, philosophy, and other fields, an intension is any property or quality connoted by a word, phrase or other symbol. In the case of a word, it is often implied by the word's definition...

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

Transitive Relations

Transitive relations are binary relations R on a single set X where for all a, b, c in X, aRb and bRc implies aRc.  Transitive relations fall into two broad classes, equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...

s and order relations
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

.  Equivalence relations are also symmetric
Symmetric relation
In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...

 and reflexive
Reflexive relation
In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...

, while order relations are antisymmetric
Antisymmetric relation
In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:\forall a, b \in X,\ R \and R \; \Rightarrow \; a = bor, equivalently,...

 (complete order) or asymmetric
Asymmetric relation
Asymmetric often means, simply: not symmetric. In this sense an asymmetric relation is a binary relation which is not a symmetric relation.That is,\lnot....

 (partial order) and may be reflexive
Reflexive relation
In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...

 (inclusive order) or anti-reflexive (strict order).  The algebraic structure
Algebraic structure
In abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...

 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)
John Lucas (philosopher)
- Overview :John Lucas was educated at Winchester College and Balliol College, Oxford, where he studied first mathematics, then Greats , obtaining first class honors, and proceeding to an MA in Philosophy in 1954. He spent the 1957-58 academic year at Princeton University, deepening his...

.

Analogy with functions

A binary relation R on sets X and Y may be considered to associate, with each member of X, zero or more members of Y.  (In the case of a relation T on more than two sets, X or Y or both can be cross products of any of the sets on which T is defined.)  X is then referred to a the domain of RY is called the range or codomain of R.  The subset of Y associated with a member x of X, is called the image of x, written as R(x).  The subset of Y associated with a subset ξ of X is the union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...

 of the images of all the x in ξ and is called the image of ξ, written as R(ξ).

R is fully defined or total at X, if for every member x of X, there is at least one member y of Y where xRy.  R is uniquely defined or tubular at X, if for every member x of X, there is at most one member y of Y where xRy.  R is surjective or total at Y, if for every member y of Y, there is at least one member x of X where xRy.  R is injective or tubular at Y, if for every member y of Y, there is at most one member x of X where xRy.  If R is both fully defined and uniquely defined then R is well defined or 1-regular at X (for every member x of X, there is one and only one member y of Y where xRy).  If R is both surjective and injective then R is bijective or 1-regular at Y.  If R is both uniquely defined and injective then R is one-to-one.

A function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 is a well defined relation.  A uniquely defined relation is a partial function
Partial function
In mathematics, a partial function from X to Y is a function ƒ: X' → Y, where X' is a subset of X. It generalizes the concept of a function by not forcing f to map every element of X to an element of Y . If X' = X, then ƒ is called a total function and is equivalent to a function...

.  A surjective function is a surjection.  An injective function is an injection.  A bijective function is a bijection.

Relations generalize functions
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

.  Just as there is composition of functions, there is composition of relations
Composition of relations
In mathematics, the composition of binary relations is a concept of forming a new relation from two given relations R and S, having as its most well-known special case the composition of functions.- Definition :...

.

Every binary relation R has a transpose relation
Inverse relation
In mathematics, the inverse relation of a binary relation is the relation that occurs when you switch the order of the elements in the relation. For example, the inverse of the relation 'child of' is the relation 'parent of'...

 R-1, which is related to the inverse function
Inverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...

.  For a relation R that is both fully defined and injective, the transpose relation R-1 is a true inverse in that R-1 faithfully restores any element x or subset ξR-1(R(ξ)) = ξ.

Examples

This section discusses, by way of example, the arithmetic
Arithmetic
Arithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations. It involves the study of quantity, especially as the result of combining numbers...

al binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

 of divisibility.

Divisibility

A more typical example of a 2-place relation in mathematics is the relation of divisibility
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...

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

Suggested reading

The logician Augustus De Morgan
Augustus De Morgan
Augustus De Morgan was a British mathematician and logician. He formulated De Morgan's laws and introduced the term mathematical induction, making its idea rigorous. The crater De Morgan on the Moon is named after him....

, 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 Sanders Peirce restated and extended De Morgan's results. Bertrand Russell
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...

 (1938; 1st ed. 1903) was historically important, in that it brought together in one place many 19th century results on relations, especially orders
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

, by Peirce, Gottlob Frege
Gottlob Frege
Friedrich Ludwig Gottlob Frege was a German mathematician, logician and philosopher. He is considered to be one of the founders of modern logic, and made major contributions to the foundations of mathematics. He is generally considered to be the father of analytic philosophy, for his writings on...

, Georg Cantor
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...

, Richard Dedekind
Richard Dedekind
Julius Wilhelm Richard Dedekind was a German mathematician who did important work in abstract algebra , algebraic number theory and the foundations of the real numbers.-Life:...

, and others. Russell and A. N. Whitehead made free use of these results in their epochal Principia Mathematica
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913...

. For a systematic treatise on the theory of relations see R. Fraïssé, Theory of Relations (North Holland; 2000).

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK