EQUIVALENCE RELATIONS

A motivating example for equivalence relations is the problem of constructing the rational numbers. A rational number is the same thing as a fraction a/b, a, b ∈ Z and b 6= 0, and hence specified by the pair (a, b) ∈ Z× (Z−{0}). But different ordered pairs (a, b) can define the same rational number a/b. In fact, a/b and c/d define the same rational number if and only if ad = bc. One way to solve this problem is to agree that we shall only look at those pairs (a, b) “in lowest terms,” in other words such that b > 0 is as small as possible, which happens exactly when a and b have no common factor. But this leads into complicated questions about factoring, and it is more convenient to let (a, b) be any element of Z× (Z− {0}) and then describe a very general mechanism for treating certain such pairs as equal. Let X be a set. A relation R is just a subset of X × X. Choose some symbol such as ∼ and denote by x ∼ y the statement that (x, y) ∈ R. There are three important types of relations in mathematics: functions f : X → X (we denote by y = f(x) the condition that (x, y) ∈ R), order (we use x ≤ y or x < y for (x, y) ∈ R), and equivalence relations for relations that are “like” equality. These are usually denoted by some special symbol such as ∼, ∼=, or ≡. Here is the formal definition: Definition 0.1. An equivalence relation on a set X is a subset R ⊆ X ×X with the following properties: denoting (x, y) ∈ R by x ∼ y, we have 1. For all x ∈ X, x ∼ x. (We say ∼ is reflexive.) 2. For all x, y ∈ X, if x ∼ y then y ∼ x. (We say ∼ is symmetric.) 3. For all x, y, z ∈ X, if x ∼ y and y ∼ z then x ∼ z. (We say ∼ is transitive.)