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.