Our review of ordered pairs leads us to relations. Informally, a relation is a property that a pair of elements may or may not have. Think of equality, which holds for the pair ; or, for something more interesting, of the set of all such that is a man, is an enby (slay), and is married to (many such cases). Formally, we identify a relation with the set of pairs for which it holds.
Definition 1.2.1 (Relations). A relation between sets and is a subset ; we write for . A relation on a set is a relation between and , that is, a subset . The domain and range of are
Consider the following examples:
- , so that means : the relation less than;
- , so that means : the relation of belonging (being an element of);
- .
Naturally, there are infinitely many possible relations, but one class of them concerns us for now: the relations that declare elements equivalent to one another, in a sense that the next definition makes precise.
Definition 1.2.2 (Equivalence relations). Let be a relation on a set . We say that is
- reflexive if for every ;
- symmetric if implies ;
- transitive if and imply .
An equivalence relation on is a relation on that is reflexive, symmetric, and transitive. Equivalence relations are usually denoted .
Question 1.2.3. The three properties in the definition are independent of one another. For each of them, find an explicit relation that has that property and lacks the other two.
Show solution
For reflexivity, let Since , the relation is reflexive on . However, but , so is not symmetric. For transitivity, we have and in , so we can set up the first step, but ; thus transitivity fails. This example is a reminder that we need not think of concrete properties that can be seen in front of our eyes (shapes, dogs, even equality!) in order to have a mathematical relation: any set of pairs will do.
For symmetry, let be a set with at least two elements and consider . No element satisfies , so is not reflexive. It is symmetric, since implies . Transitivity may seem plausible at first, but for we have and , and transitivity would then demand , which is false.
For transitivity, consider on . It is not reflexive, since is never greater than itself, and it is not symmetric, since never implies . It is transitive: and imply .
1.2.1 Equivalence Classes and Partitions
An equivalence relation on declares certain elements of equivalent to one another. Gathering mutually equivalent elements together produces a smaller set, whose elements are the resulting classes.
Definition 1.2.4 (Equivalence classes). Let be an equivalence relation on a set . The equivalence class of is Any element of is called a representative of the class.
By reflexivity, .
Lemma 1.2.5 (Equal classes). Let be an equivalence relation on , and let .
- if and only if .
- If , then .
Proof. (a) Suppose . If , then , and transitivity gives ; so . By symmetry , and the same argument gives . Conversely, if , then , that is, .
(b) If , then and ; by symmetry , and by transitivity . Now apply (a). ∎
Definition 1.2.6 (Partitions). A partition of a set is a collection of nonempty subsets of such that every element of belongs to exactly one member of ; equivalently, the members of are nonempty and pairwise disjoint, and their union is . The relation induced by is the relation on given by
Definition 1.2.7 (Quotient sets). Let be an equivalence relation on . The quotient set of by is the set of its equivalence classes,
Equivalence relations and partitions turn out to be two descriptions of the same thing.
Proposition 1.2.8 (Equivalence relations and partitions). Let be a set.
- If is an equivalence relation on , then is a partition of , and the relation it induces is .
- If is a partition of , then is an equivalence relation on , and its set of equivalence classes is exactly : .
Proof. (a) Each class is nonempty, since it contains , and each lies in the class . If lies in two classes and , they intersect, so by Lemma 1.2.5. Hence is a partition, and the only class containing is . Consequently some class contains both and if and only if , which by Lemma 1.2.5 happens if and only if .
(b) For , let be the unique member of containing . If for some , then by uniqueness; so if and only if . Now is reflexive, since ; it is symmetric, since its definition is symmetric in and ; and it is transitive, since and give , hence , and . The class of is , so . Every member of is nonempty, and for any ; hence . ∎
Example 1.2.9 (Congruence mod ). Fix an integer , and for set if divides . This is an equivalence relation, called congruence mod and also written : divides ; if divides , it divides ; and if divides and , it divides their sum . The class of is . By division with remainder, every integer can be written as with and , so is congruent to its remainder . No two of are congruent, since their differences have absolute value less than . So every integer is congruent to exactly one of , and the quotient set has exactly elements: