 # 5. Equivalence relations

### Definition

A relation on a set will be called an equivalence relation, it it has the following three properties:

• reflexive: for all , ,
• symmetric: for all , if , then ,
• transitive: for all , if and , then .

E.g., a relation on natural numbers such that if and only if is an equivalence relation. Indeed, for all , we get , so it is reflexive. It is also symmetric, because if , then . Finally, it is transitive, since if and , so and , then , so .

Meanwhile the relation on natural numbers is not an equivalence relation, because it is not symmetric, e.g. , but not .

Equivalence relations often appear in the real world. E.g. the following relation is an equivalence relation. Two cars are in the relation if and only if they are of the same colour. Another example is the relation of siblings.

### Fundamental theorem of equivalence relations

Given an equivalence relation on a set , the set of all elements which are in relation with a given is called the equivalence class of and denoted by . So . The family of all equivalence classes is denoted by and called the quotient set.

It is easy to notice that if , then (the key role in this fact is played by transitivity). On the other hand, if and are not in relation , then . This observation implies the fundamental theorem of equivalence relations, which states that an equivalence relation on a set is actually the same as a partition of this set.

A family will be called a partition of , if for any , , if only , and .

The fundamental theorem states that every equivalence relation on a set generates a partition of the set, precisely the partition into its equivalence classes. On the other hand every partition of a set generates an equivalence relation on this set. It is the relation such that two elements are in it, if they are in the same element of the partition.

E.g. the relation on the set of cars in which two cars are in the relation if and only if they are of the same colour, generates a partition of the set of cars into classes of equivalence related to each colour of cars.

E.g. relation on such that , if and only if generates the partition of into equivalence classes of this relation, e.g. , which are related to each number from the interval .

The partition of into generates the following equivalence relation: .

### Cardinality of equivalence classes and of quotient set

Often we have to calculate the cardinality of each of the equivalence class of a given relation and the cardinality of its quotient set. E.g, in the relation such that if and only if ), no two distinct numbers in are in relation, so function given as is one-to-one, and therefore . On the other hand, any partition of the reals is of cardinality , so . Finally, if , then , and therefore , for any .