The Most Important Relation In Mathematics 1

Part 1: Basics

In this and few following posts I will argue that not only in mathematics, but in all human reasoning, the role of equivalence relations is crucial. The notion of an equivalence relation is the key to any abstractions; the only way to classify things in one’s mind; the ultimate way to simplify reasoning whenever it is natural and reasonable to do so.

On that basis I encourage to emphasize the notion of equivalence relation in the basic courses on mathematics and philosophy.

Because of the wideness described above, I will explain equivalence relations from scratch so that non-mathematicians can follow.

This first post in this series is devoted to just the mild basics of the subject, merely for those who are not familiar with equivalence relations.

The definition follows. If X is a set of objects, then [tex]x\in X[/tex] means that x is one of the objects in X (a member or an element of X). A relation R between the elements of a set X is called an equivalence relation if it is
(S) Symmetric: for all [tex]x, y \in X[/tex] the element x is related to y (denoted xRy) if and only if y is related to x (yRx).
(R) Reflexivity: Each element [tex]x\in X[/tex] is related to itself: xRx.
(T) Transitivity: For all [tex]x,y,z\in X[/tex], if xRy and yRz, then xRz.

Suppose we have a set X and an equivalence relation R on that set. Given an element [tex]x\in X[/tex], the equivalence class of x, denoted [x], is the set of all elements that are related to x. It follows easily from (S), (T) and (R) that for [tex]x,y\in X[/tex] either [tex][x]=[y][/tex] or there are no common elements in [x] and [y], i.e. [tex][x]\cap [y]=\varnothing[/tex].

Examples

1. X is the set of all people and xRy holds iff “x is born in the same year as y”. Clearly if xRy then yRx: if x is born in the same year as y, then y is born in the same year as x. Also everyone are born in the same year with themselves and transitivity also clearly holds. So this is an equivalence relation. Equivalence classes are sets of people that are born in the same year with each other. For instance I belong to the equivalence class formed by all who are born in 1986.

2. X is the set of spaghetti and xRy says “x is as long as y”. One easily checks that conditions (S), (R), (T) are satisfied. Equivalence classes are sets of spaghetti of fixed length.

3. X is the set of cats and xRy says “x is a parent of y”. In this case R is not an equivalence relation. In fact ALL the conditions (S), (R) and (T) fail.

4. X is the set of all collections and xRy says “x has as many members as y”. This is an equivalence relation (check for an exercise).

5. X is the set of trees and xRy says “x is taller than y”. This is not an equivalence relation. Only (T) is satisfied, but not (S) nor (R).

6. X is the animals and xRy says “x is the same species as y”. This is tricky. It is clearly supposed to be an equivalence relation but the first problem is that there is no satisfactory definition of this relation (according to Wikipedia “No one definition has satisfied all naturalists”) and the second problem is that none of the definitions is clearly giving a transitive relation. However, people do talk of certain species as being equivalence classes of this relation.

7. “x is the same race as y” is, as species, a hard-defined equivalence relation on animals which is a refinement of species (see below), that is, two animals maybe the same species (cats) but still represent different races ( say Nebelung and Havana), but if two animals are different species (a cat and a dog), they certainly belong to different races.

8. X is the set of real numbers and xRy says “the value |x-y| is a natural number divisible by 12”. This is also an equivalence relation (check!).

9. X is the set of three dimensional shapes and xRy says “x and y have the same volume”.