Main Index
Foundation of mathematics
Relations
Subject Index
comment on the page
The calculus of binary relations was created by A. De Morgan [1]. It was subsequently developed by Ch.S. Peirce [2] and E.Schröder [3]. A.Tarski [4] axiomatized and revived the subject at the end of the first half of 20th century [5].
Let be a set. A binary relation on the set is a subset of the Cartesian product . If , , then we say that the elements and of the set are in relation ( or that is in relation to ) and write
Since a relation is a set we can apply the set-theoretical operations to them. If and are two relations on the set then
Note that the is equivalent with the fact .
Under a composition (or product) of two relations and on the set it is meant the relation defined by
Composition of relations is associative but not commutative.
If , , and are relations on a set then
In the last relation the operation union cannot be replaced by the intersection.
To every relation on a set there exists the inverse relation which is defined as
If , , , are relations on the set , then
Some other relations are of special interest. For instance,
Clearly, , and for every relation on the set .
Among the various properties of the relation on the set the following are of particular interest:
Reflexivity: for every , i.e. ,
Transitivity: if and , then , i.e. ,
Symmetry: if then , i.e. ,
Antisymmetry: if and then , i.e. .
Note that if the relation possesses one of these properties then also does.
Given a relation on the set and a subset , then we can define the contraction of to as .
It can be easily seen that
A natural generalization of the binary relation is the -ary relation on the set , where is a non-negative integer. It is defined as a subset of the set of all ordered tuples of elements of .
Another generalization we get if we take two (generally distinct) sets and . A relation, , from to is a subset of the Cartesian product . The domain of , denoted by , is the set of elements in the first component of every ordered pair in . The range of , denoted by , is the set of elements in the second component of every ordered pair in .
The inverse of , denoted by , is a relation from to such that means that , , .
A relation is called single-valued when and , , , together imply . Relations that are not single-valued are sometimes called multivalued.
A relation is called total if foe each there exists a such that .
In this general case one can also form the composites of relations. If is the relation from to and from to then the product of and is the relation from to defined for and as follows: if and only if there exists a such that and . (Note that often it is preferred to write the product as , instead of .)
Many properties of the properties of products and inverses mentioned above remain valid also in this case. One of these is that products do not, in general, commute. However, is valid. Note that this property is sometimes called the commutativity rule for products and inverses. The product of relations is also associative.
[1] | De Morgan, A. (1860). On the syllogism, no. IV, and on the logic of relations. Transactions of the Cambridge Philosophical Society, 10, 331-358. |
[2] | Peirce, C. S. (1933). Description of a notation for the logic of relatives, resulting from an amplification of the conceptions of Boole’s calculus of logic. In: Collected Papers of Charles Sanders Peirce. III. Exact Logic, Harward University Press. |
[3] | Schröder, E. (1895). Vorlesungen über die Algebra der Logik (Exakte Logik), Band III: Algebra und Logik der Relative. Leipzig: B.G.Teubner. |
[4] | Tarski, A. (1941). On the calculus of relations. Journal of the Symbolic Logic, 6, 73-89. |
[5] | Pratt, V. R. (1992). Origins of the calculus of binary relations. In : Proc. 7th Annual IEEE Symp. on Logic in Computer Science (pp. 248-254). Santa Cruz, CA. |
Cite this web-page as:
Štefan Porubský: Binary Relation.