Main Index Foundation of mathematics Relations
 Subject Index
comment on the page

Binary relations

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

Binary relation between elements of a set

Let typeset structure be a set. A binary relation typeset structure on the set typeset structure is a subset of the Cartesian product typeset structure. If typeset structure, typeset structure, then we say that the elements typeset structure and typeset structure of the set typeset structure are in relation typeset structure ( or that typeset structure is in relation typeset structure to typeset structure) and write

a ρ b               or             (a, b) ϵ ρ .

Since a relation is a set we can apply the set-theoretical operations to them. If typeset structure and typeset structure are two relations on the set typeset structure then

Note that the typeset structure is equivalent with the fact typeset structure.

Under a composition (or product) of two relations typeset structure and typeset structure on the set typeset structure it is meant the relation typeset structure defined by

(a, b) ϵ αβ      if    there exists    ...  that      a α c     and     c β b .

Composition of relations is associative but not commutative.

If typeset structure, typeset structure, and typeset structure are relations on a set typeset structure then

(Underscript[∪, ι ϵ I] ρ _ ι) π = Underscript[∪, ι &# ... ] ρ _ ι)    = Underscript[∪, ι ϵ I] (π ρ _ ι) .

In the last relation the operation union cannot be replaced by the intersection.

To every relation typeset structure on a set typeset structure there exists the inverse relation typeset structure which is defined as

a α^(-1) b      if and only if    b α a .

If typeset structure, typeset structure, typeset structure, typeset structure are relations on the set typeset structure, then  

Some other relations are of special interest. For instance,

Clearly, typeset structure, and typeset structure for every relation typeset structure on the set typeset structure.

Among the various properties of the relation typeset structure on the set  the following are of particular interest:

Reflexivity: typeset structure for every typeset structure, i.e. typeset structure,

Transitivity:  if typeset structure and typeset structure, then typeset structure, i.e. typeset structure,

Symmetry: if typeset structure then typeset structure, i.e. typeset structure,

Antisymmetry: if typeset structure and typeset structure then typeset structure, i.e. typeset structure.

Note that if the relation typeset structure possesses one of these properties then also typeset structure does.

Given a relation typeset structure on the set typeset structure and a subset typeset structure, then we can define the contraction typeset structure of typeset structure to typeset structure as typeset structure.  

It can be easily seen that

FormBox[RowBox[{(ρ | _ N)^(-1) = ρ^(-1) | _ N,  , ,,    , Cell[TextDa ...                                     ι ϵ I       ι   N   ι ϵ I         N

A natural generalization of the binary relation is the typeset structure-ary relation on the set typeset structure, where typeset structure is a non-negative integer. It is defined as a subset of the set typeset structure of all ordered typeset structure tuples of elements of typeset structure.

Binary relation between elements of two distinct sets

Another  generalization we get  if we take two (generally distinct) sets typeset structure and typeset structure.  A relation, typeset structure, from typeset structure to typeset structure is a subset of the Cartesian product typeset structure. The domain of typeset structure, denoted by typeset structure, is the set of elements in the first component of every ordered pair in typeset structure. The range of typeset structure, denoted by typeset structure, is the set of elements in the second component of every ordered pair in typeset structure.

The inverse of typeset structure, denoted by typeset structure, is a relation from typeset structure to typeset structure such that typeset structure means that typeset structure, typeset structure, typeset structure.  

A relation typeset structure is called single-valued when typeset structure and typeset structure, typeset structure, typeset structure, together imply typeset structure.  Relations that are not single-valued are sometimes called multivalued.

A relation typeset structure is called total if  foe each typeset structure there exists a typeset structure such that typeset structure.

In this general case one can also form the composites of relations. If typeset structure is the relation from typeset structure to typeset structure and typeset structure from typeset structure to typeset structure then the product typeset structure of typeset structure and typeset structure is the relation from typeset structure to typeset structure defined for typeset structure and typeset structure as follows: typeset structure if and only if there exists a typeset structure such that typeset structure and typeset structure. (Note that often it is preferred to write the product as typeset structure, instead of typeset structure.)

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, typeset structureis valid.  Note that this property is sometimes called the commutativity rule for products and inverses. The product of relations is also associative.

References

[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.
Page created .