Binary relations on a set

A binary relation on a set is a rule that associates pairs of elements from the set, indicating some kind of relationship between them.

Definition and Examples

Therefore, a binary relation on a set is represented by R such that R ⊆ S × S.

A "greater than" relation is a binary relation on a set, as it involves numbers on both sides. Thus, "greater than" ⊆ ℝ × ℝ. The relation "Music band and its most famous song," such as the pair "Linkin Park" and "In the End," is not a binary relation on a set because it represents a relation between the set of all bands and the set of all songs.

Properties

The binary relation R on the set S may have some interesting properties. We say that the relation R is...

• Reflexive if for all a ∈ S, it holds that [a, a] ∈ R.
• Symmetric if, for all a, b ∈ S, it holds that if [a, b] ∈ R, then [b, a] ∈ R must also be true.
• antisymmetric if for all a, b ∈ S, it holds that if [a, b] ∈ R and [b, a] ∈ R, then a = b.
• Transitive: For all a, b, c ∈ S, it holds that if [a, b] ∈ R and [b, c] ∈ R, then [a, c] ∈ R as well.

Examples of reflexivity

Reflexivity means that an element is related to itself. A typical example is equality. If we define equality on natural numbers, it certainly holds for any element a: a = a. Another example might be divisibility. Here again, the number a is divisible by itself, so the pair [a, a] is in a divisibility relation (seven divides seven).

However, a relation such as "less than" is no longer reflexive because it is not true that a < a. This is not possible; seven cannot be less than seven. Similarly, the relation of "being a sibling" is not reflexive since one cannot be its own sibling.

The crucial point is that reflexivity must hold for all elements; it is not sufficient to find just a few instances. Consider the relation "to like someone." I may like someone else, say a Jennifer Lawrence, but I might also like myself. Certainly, there exists someone who likes themselves. However, there also exists someone who doesn't like themselves. Therefore, such a relation is not reflexive - all individuals must like themselves for it to be reflexive.

Examples of symmetry

In a symmetrical relation, if there is a pair in the relation, then there is an inverse pair in the relation. For example, the relation of being a sibling. If John is a sibling of Jennifer, then Jennifer is also a sibling of John. From numerical relations, it could be the relation "to be the opposite number." By this, I mean the pair 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 doesn't matter: [2, −2] and [−2, 2] are still opposite numbers to each other and add up to zero.

A relation that is not symmetric is "less than" (over the real numbers). It lacks symmetry because a < b and b < a can never both be valid. If 5 < 15, then 15 < 5 cannot be valid either. Furthermore, the relation "being a father of a son" is not symmetric. You can be the father of your son, but your son cannot be your father.

Again, this property must hold in all cases. If the relation "liking someone" (within the set of all people) is to be symmetric, then if I like Jennifer Lawrence, Jennifer Lawrence would also need to like me. Since she doesn't even know me, I can't claim that she likes me. This lack of reciprocity means the relation is not symmetric, which is unfortunate.

Examples of antisymmetry

The classic example of an antisymmetric relation is the less-than-or-equal relation. Antisymmetry dictates that if the elements [a, b] and [b, a] are in a relation, then they can only be equal if a = b. The less-than-or-equal relation satisfies this condition. When do a ≤ b and b ≤ a simultaneously apply? Only if a = b. Consider the examples: does 3 ≤ 5 and at the same time 5 ≤ 3 hold? No. But 4 ≤ 4 and 4 ≤ 4 do apply simultaneously.

An example of a relation that is not antisymmetric might be pairs of words that have the same length, for example [orange, banana]. Such a relation is not antisymmetric because if we find a pair of words that are in the relation, their inverse element is also in the relation, and yet the two words are different. So, the aforementioned element [orange, banana] and its inverse: [banana, orange]. Both are obviously in our relation, but at the same time orange ≠ banana, so the relation is not antisymmetric.

Example of transitivity

The classic example of a transitive relation is the "less-than" relation. It implies that if 3 < 4 and 4 < 5, then 3 < 5 must surely also hold. This is a rather natural property for many relations. The same logic applies with words of the same length. If [banana, orange] and [orange, tomato] are in a relation, then the words [banana, tomato] must also be in a relation.

The term "transitive" does not apply to "being a father of a son". If John is the father of Patrick, and Patrick is the father of Thomas, then John is not the father of Thomas; he is his grandfather. Similarly, liking someone is not a transitive relation. If I like Jennifer Lawrence and Jennifer Lawrence likes her husband, it doesn't mean I like Jennifer's husband. Although, he must be lovely.

Transitivity is also addressed in the classic dice game. Suppose a die A is better than die B if die A is more likely to roll a higher number than die B. Is such an assumption transitive? This question is addressed in the article non-transitive cubes.

Equivalence and ordering

Some special types of binary sequences have names:

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