Which of the following relations on ℤ is NOT an equivalence relation?
Aa R b if and only if a − b is even
Ba R b if and only if a² = b²
Ca R b if and only if a ≤ b
Da R b if and only if a and b have the same remainder when divided by 5
An equivalence relation must be reflexive, symmetric, and transitive. The relation a ≤ b fails symmetry: 2 ≤ 3 but it is not the case that 3 ≤ 2. It is reflexive (a ≤ a) and transitive, but symmetry is missing. The other three are genuine equivalence relations: even differences partition ℤ into two classes (even and odd integers), a² = b² partitions by absolute value, and congruence mod 5 produces five classes.
Question 2 Multiple Choice
The rational numbers ℚ are constructed as equivalence classes of integer pairs (a,b) with b ≠ 0 under the relation (a,b) ~ (c,d) iff ad = bc. What is the equivalence class [(1,2)]?
AThe single ordered pair (1, 2)
BThe unique fraction 1/2, with no other representations
CThe set of all integer pairs equal to 1/2: {(1,2), (2,4), (3,6), (−1,−2), …}
DAll fractions with numerator 1
The equivalence class [(1,2)] is not just the pair (1,2) — it is the entire collection of all pairs (a,b) where a/b = 1/2, i.e., (1,2), (2,4), (3,6), (−1,−2), and so on. The rational number 1/2 *is* this equivalence class: all its representations simultaneously, treated as a single object. This is the quotient construction — we build ℚ from ℤ by declaring pairs equivalent when they represent the same ratio, then working with the classes as mathematical objects.
Question 3 True / False
If a relation on a set S is both symmetric and transitive, it should also be reflexive — and is therefore automatically an equivalence relation.
TTrue
FFalse
Answer: False
This seems logically compelling but is false. Consider the empty relation on any nonempty set: it is vacuously symmetric and transitive (no counterexamples exist to violate these properties), but not reflexive — no element is related to itself. Reflexivity must be verified independently. A relation satisfying only symmetry and transitivity may hold only for some elements, leaving others unrelated to anything. All three properties must be checked separately.
Question 4 True / False
There is a bijection between equivalence relations on a set S and partitions of S — every equivalence relation produces a partition, and every partition determines an equivalence relation.
TTrue
FFalse
Answer: True
This is the fundamental theorem connecting the two concepts. Given an equivalence relation R, the equivalence classes form a partition: they are nonempty, pairwise disjoint, and cover all of S. Conversely, any partition of S defines an equivalence relation: declare a R b iff a and b lie in the same block. These two constructions are inverses of each other, establishing a one-to-one correspondence. The relational language (for logic and algebra) and the partition language (for combinatorics) are interchangeable.
Question 5 Short Answer
What does it mean to form a 'quotient set' S/R, and why is this construction useful in mathematics? Give an example.
Think about your answer, then reveal below.
Model answer: The quotient set S/R is the set of all equivalence classes under R — it collapses S by treating equivalent elements as a single object. For example, ℤ/3ℤ partitions ℤ into three classes: {…,−3,0,3,…}, {…,−2,1,4,…}, and {…,−1,2,5,…}. Arithmetic on these three classes is well-defined, giving a new algebraic structure with only 3 elements. Quotient construction is how mathematics builds ℤ/nℤ, ℚ (equivalence classes of integer pairs), and cardinal numbers (equivalence classes of sets under bijection).
The power of quotient sets is that they let you build new mathematical objects by declaring 'these things count as the same.' This is the foundational technique of abstract algebra: group quotients, ring quotients, and module quotients all rely on this construction. Understanding equivalence relations and quotients is prerequisite to virtually all of modern algebra and to the set-theoretic foundations of mathematics.