Binary relation on a set

A binary relation on a set is a binary relation defined between two copies of the same set.

Examples

A binary relation on a set is a special type of binary relation in which both underlying sets are the same. A binary relation on a set is therefore a relation R such that R ⊆ M × M.

The relation “greater than” is a binary relation on a set, because on both sides we work with numbers. So > ⊆ ℝ × ℝ. The relation “father – number of children” is not a binary relation on a set, because we choose the father from the set of all people, whereas we choose the number of children from some set of numbers.

Properties

A binary relation R on a set M can have some interesting properties. We say that the relation R is…

• reflexive if (a, a) ∈ R for all a ∈ M.
• symmetric if for all a, b ∈ M, whenever (a, b) ∈ R, then also (b, a) ∈ R.
• antisymmetric if for all a, b ∈ M, whenever (a, b) ∈ R and at the same time (b, a) ∈ R, then a = b.
• transitive if for all a, b, c ∈ M, whenever (a, b) ∈ R and at the same time (b, c) ∈ R, then (a, c) is also in R.

Examples of reflexivity

Reflexivity means that an element is related to itself. A typical example is equality. If we define equality on the positive integers, then certainly for any element a we have a = a. Another example is divisibility. Again, the number a is divisible by itself, so the pair (a, a) is in the divisibility relation (seven divides seven).

The relation less than, however, is not reflexive, because a < a is not true. It cannot be: seven cannot be less than seven. Similarly for the relation “is the father of”: I cannot be my own father. Such relations are not reflexive.

It is important that reflexivity must hold for all elements; finding some is not enough. Take the relation “likes someone”. I might like someone, for example the ticket inspector, but I might also like myself. There is certainly a person who likes themselves. But there is equally a person who does not like themselves. Such a relation is then not reflexive – everyone would have to like themselves.

Examples of symmetry

In a symmetric relation, if a pair is in the relation, then the inverse pair is in the relation too. For example, the relation “is a sibling of”. If Oliver is a sibling of Amelia, then Amelia is a sibling of Oliver. Among numerical relations, an example is the relation “is the negative of”. By this I mean pairs such as 2 and −2 or −7 and 7. These are two numbers that add up to zero. Such a relation is symmetric, because the order simply does not matter: (2, −2) and (−2, 2) are still negatives of each other and add up to zero.

A relation that is not symmetric is less than (over the real numbers). It has no symmetric pair at all, because a < b and b < a can never both hold. If 5 < 15, then 15 < 5 cannot be true. The relation “is the father of his son” is not symmetric either. You can be the father of your son, but then the son cannot be the father of his father.

Again, this property must hold in all cases. If the relation “likes someone” (on the set of all people) is to be symmetric, then if I like the TV presenter Isla, Isla would also have to like me. And since she does not even know me, I cannot say that she likes me, which is a shame, and the relation is not symmetric. Which is also a shame.

Examples of antisymmetry

A classic example of an antisymmetric relation is less than or equal to. Antisymmetry tells us that if the pairs (a, b) and (b, a) are both in the relation, then this can happen only when the elements are equal, a = b. The relation less than or equal to satisfies this. When do a ≤ b and b ≤ a both hold? Only when a = b. Let’s substitute: do 3 ≤ 5 and 5 ≤ 3 both hold? No. But 4 ≤ 4 and 4 ≤ 4 do.

An example of a relation that is not antisymmetric is pairs of words that have the same length, for example (Sunday, hammer). Such a relation is not antisymmetric, because we can find a pair of words that are in the relation, whose inverse pair is also in the relation, and yet the two words are different. Take the pair (Sunday, hammer) and its inverse (hammer, Sunday). Both are clearly in our relation, but Sunday ≠ hammer, so the relation is not antisymmetric.

Example of transitivity

The relation less than is transitive. Transitivity tells us that if 3 < 4 and at the same time 4 < 5, then certainly 3 < 5 too. For many relations this is quite a natural property. The same goes for our example with words of the same length. If the pair (hammer, Sunday) is in the relation and the pair (Sunday, branch) is in the relation, then the pair (hammer, branch) is in the relation too.

The relation “is the father of” is not transitive. If Oliver is the father of Harry and Harry is the father of George, then Oliver is not the father of George; he is his grandfather. Similarly, the relation “likes someone” is not transitive. If I like Isla and Isla likes her husband, that does not mean I like Isla’s husband too.

Transitivity also comes up with ordinary dice. Suppose the relation is “dice A is better than dice B” if dice A more often (with a greater probability) shows a higher number than dice B. Is such a relation transitive? The article on non-transitive dice answers that.

Equivalence and order

Some special types of binary relations have names of their own:

• An equivalence relation is a relation that is reflexive, symmetric and transitive.
• An order relation is a relation that is reflexive, antisymmetric and transitive.