Binary relation

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

Examples

A binary relation is one of the most typical and common kinds of relation. It also has some interesting properties, which we describe here.

Examples of binary relations include “father – son”, the pairing “vehicle – number of wheels” or the more general “object – property of the object”. The object might be an animal and the property its number of legs, its average lifespan, the number of hairs on its head and so on.

We can define a binary relation R between sets M₁ and M₂ like this: R ⊆ M₁ × M₂. A binary relation is therefore a set of pairs, and this set is a subset of the Cartesian product of the two sets between which we define the relation. So the relation “father – son” could be a relation between the set of all people, between the set of all people in Europe or between the set of all people in London. We can also restrict the set in a different direction: we can say that we define the relation between the set of all men, not people in general.

For binary relations we usually use a special notation. Instead of writing (a, b) ∈ R, we can write aRb. For example, instead of (3, 1) ∈ > we can write 3 > 1. The same goes for other relations. So writing aSb is equivalent to writing (a, b) ∈ S.

Inverse relation

The inverse relation is the opposite of the relation we started with. (Careful, it is not the same as the complement of a relation.) What is the opposite of the relation less than? Greater than. If the relation less than contains the pair (4, 7), that is 4 < 7, then the inverse pair is the reverse: 7 > 4, so the inverse relation contains the inverse pair (7, 4).

Given a relation R ⊆ M₁ × M₂, we construct the inverse relation R⁻¹ by taking every pair (a, b) ∈ R and putting its inverse into R⁻¹. So if the relation R contains the pair (a, b), then the relation R⁻¹ must contain the pair (b, a). The converse holds too: if R⁻¹ contains the pair (b, a), then R must contain the pair (a, b).

As a formal definition, the relation R⁻¹ is the inverse of R if and only if:

$$\mathrm{\forall }a\in M_1\mathrm{\forall }b\in M_2:(a,b)\in R\iff (b,a)\in R^{-1}$$

So 6 < 8 if and only if 8 > 6. The same goes for other pairs.

Composition of relations

We can compose binary relations with each other. Take two relations: the first, R, is “is the father of his son” and the second, S, is “is the brother of his sister”. The relation R contains pairs (father, son) and the second relation contains pairs (brother, sister).

Now let’s try to compose them. We get a new relation, which we denote R ∘ S, and this relation contains the pair (a, c) if and only if (a, b) ∈ R and at the same time (b, c) ∈ S. Notice that b appears in both pairs, once in the second place and then in the first place. It is the linking element of the composition.

Example: R = {(Oliver, Harry), (Jack, George)} and S = {(Harry, Amelia), (Harry, Lily), (George, Isla)}. Oliver is Harry’s father and Jack is George’s father. Harry has sisters Amelia and Lily, and George has a sister Isla.

Now let’s compose the relations: R ∘ S. We look for a pair from R whose son is someone listed as a brother in S. For example, these two pairs: (Oliver, Harry) and (Harry, Amelia). Harry is the linking element, so we do not need him any more, and we form a new pair from the remaining names: (Oliver, Amelia). The relation R ∘ S therefore contains the pair (Oliver, Amelia). Harry has another sister, Lily, so we add her to the composite relation as well: (Oliver, Lily). Finally there is the son George. He has a sister, Isla. So we have two pairs, (Jack, George) and (George, Isla), and from them we create another element: (Jack, Isla).

The result is the relation R ∘ S = {(Oliver, Amelia), (Oliver, Lily), (Jack, Isla)}. What could we call this relation? Most likely “is the father of his daughter”.

Here is the whole definition once more:

$$(a,c)\in (R\circ S)\iff \mathrm{\exists }b(a,b)\in R\wedge (b,c)\in S$$

Note: sometimes the reverse notation is used, which means that for the same definition you would write S ∘ R instead of R ∘ S.