Binary Relations

A binary relation is a special type of relation with arity two. Typical binary relations include less than, equality, divisibility, greater than, etc.

Examples

A binary relation is a typical and commonly encountered type of relation. It also has some interesting properties, which we will describe here.

An example of a binary relation could be: the "father-son" relationship, the pair "vehicle - number of wheels," or the more general "object - property of object." The object could be an animal, and the property could be the number of legs, life expectancy, number of hairs on the head, and so on.

The binary relation R between the sets M₁ and M₂ can be defined as follows: R ⊆ M₁ × M₂. A binary relation is thus a set of pairs, where this set is a subset of the Cartesian product of the two sets between which we establish the relation. So, a father-son relation can be a relation between sets of all people, between sets of all people in Europe, or in Prague. We can restrict the set in another way; we can say that we define the relation between the sets of all men, not men in general.

We usually use special notation for binary relations. Instead of writing [a, b] ∈ R, we can write aRb. For example, instead of [3, 1] ∈ >, we might write 1 > 3. Similarly for other relations. So writing aSb is equivalent to writing [a, b] ∈ S.

Inverse relations

An inverse relation is a relation opposite to the current relation. (Note, not to be confused with a complement relation.) What is the inverse of a relation labeled "less than"? It's "greater than". If the less-than relation includes the element [4, 7], i.e. 4 < 7, then the inverse element will be its opposite: 7 > 4, thus creating [7, 4] in the inverse relation.

If we have a relation R ⊆ M₁ × M₂, then we construct the inverse relation R⁻¹ by taking all the elements of [a, b] ∈ R and inserting their inverses into R⁻¹. Thus, if the relation R contains the element [a, b], then the relation R⁻¹ must contain the element [b, a]. The reverse is also true: if R⁻¹ contains the element [b, a], then the relation R must contain the element [a, b].

If we were to define this, then the relation R⁻¹ is the inverse of R if and only if it applies:

$$\forall a\in M_1,\forall b\in M_2:\quad [a, b]\in R \Leftrightarrow [b, a]\in R^{-1}$$

6 < 8 holds precisely when 8 > 6. This is similar for other pairs.

Composition of relations

We can compose binary relations with each other. Let's consider two relations: the first, R, is "being a father to a son," and the second, S, is "being a sister's brother" Thus, the relation R contains the pairs [father, son], and the second relation contains the pairs [brother, sister].

At this point, let's try to combine the relations. We will derive a new relation, labeled as $R \circ S$, which contains the element [a, c]. This element exists because [a, b] ∈ R and simultaneously, [b, c] ∈ S. Note that both elements include b, first in the second position and then in the first position of the pair, serving as a crucial linking element in the combination.

Example: R = {[Tonda, Marek], [Petr, Jakub]} and S = {[Marek, Jana], [Marek, Lenka], [Jakub, Lucie]}. Tonda is the father of Marek, Petr is the father of Jakub. Marek has sisters named Jana and Lenka, and Jakub has a sister named Lucie.

Now we will compose the relation: $R \circ S$. We are looking for such a pair from R, where someone in the position of a son is listed as a brother in the relation S. For example, consider these two pairs: [Tonda, Marek] and [Marek, Jana]. Marek is the linking element; we can disregard him and create a new pair from the remaining names: [Tonda, Jana]. The relation $R \circ S$ thus contains the pair [Tonda, Jana]. Marek has another sister, Lenka, and we add her to the composite relation: [Tonda, Lenka]. Finally, we consider the son Jakub, who has a sister named Lucia. This leads to two pairs: [Petr, Jakub] and [Jakub, Lucie]. This creates another element: [Petr, Lucie].

The result of the relation is: $R \circ S = {[Tonda, Jana], [Tonda, Lenka], [Petr, Lucie]}$. What could we name this relation? Perhaps "being a father to his daughter".

Once again, here is the entire definition:

$$[a, c] \in (R \circ S) \Leftrightarrow \exists b\quad [a, b] \in R \wedge [b, c] \in S$$

Note: sometimes the reverse notation is used; that is, for the same definition one would use $S \circ R$ instead of $R \circ S$.