A relation R on a set S is reflexive and symmetric but NOT transitive. What does this mean for the equivalence classes?
AThe classes still form a valid partition, since reflexivity and symmetry are the important axioms
BElements can appear in more than one class, so R does not define a partition
CThe classes exist but may be empty for some elements
DThe classes form a partition as long as S is finite
All three axioms—reflexivity, symmetry, AND transitivity—are required for a valid partition. Transitivity is the closure property that forces any two elements that are both related to a common third element into the same class. Without it, a relation can create overlapping groups: a ~ b and b ~ c might hold without a ~ c, placing a and c in separate classes that share the element b. Reflexivity alone ensures everyone is in some class; symmetry ensures membership is mutual; but only transitivity prevents partial overlap.
Question 2 Multiple Choice
Suppose [a] and [b] are two equivalence classes under relation ~ on S, and there exists an element c such that c ∈ [a] and c ∈ [b]. What must be true?
A[a] and [b] overlap in exactly the element c, but may differ elsewhere
B[a] and [b] are identical — they are the same equivalence class
Ca and b are both equivalent to c, but a and b may not be equivalent to each other
DThe relation ~ is not a valid equivalence relation
If c ∈ [a], then a ~ c. If c ∈ [b], then b ~ c. By symmetry, c ~ b. By transitivity applied to a ~ c and c ~ b, we get a ~ b. Once a ~ b, every element equivalent to a is equivalent to b and vice versa, so [a] = [b]. This is the key theorem: two equivalence classes either are identical or completely disjoint — there is NO middle ground of partial overlap. The existence of a single shared element forces full identity.
Question 3 True / False
Two distinct equivalence classes under the same equivalence relation can share exactly one element.
TTrue
FFalse
Answer: False
If two classes share even one element, transitivity forces them to be the same class. If c ∈ [a] ∩ [b], then a ~ c and b ~ c, which by symmetry and transitivity gives a ~ b, hence [a] = [b]. Equivalence classes are either identical or disjoint — there is no possibility of partial overlap. This is precisely the content of the partition theorem.
Question 4 True / False
Reflexivity and transitivity together are sufficient to guarantee that a relation defines a valid partition of its domain.
TTrue
FFalse
Answer: False
Symmetry is also required. Without symmetry, a relation can be reflexive and transitive yet still fail to create mutually exclusive groups. For example, the relation '≤' on integers is reflexive and transitive, but 2 ≤ 3 does not imply 3 ≤ 2 — it is not symmetric, and it does not partition the integers into equivalence classes. All three axioms are jointly necessary: reflexivity ensures every element belongs to a class; symmetry ensures membership is mutual; transitivity closes the groups against partial overlap.
Question 5 Short Answer
Why is transitivity the 'load-bearing' axiom for the partition property — what breaks if you remove it while keeping reflexivity and symmetry?
Think about your answer, then reveal below.
Model answer: Without transitivity, two elements can each be related to a common third element without being related to each other. This allows equivalence classes to partially overlap — element c could belong to both [a] and [b] without a and b being related. The partition would break down because cells would no longer be disjoint.
Transitivity is what closes the groups. If a ~ c and b ~ c, transitivity (with symmetry) forces a ~ b, collapsing [a] and [b] into one class. Remove transitivity and you can have a ~ c and b ~ c without a ~ b, meaning c sits in two different groups simultaneously. The result is not a partition — it is an overlapping cover. Reflexivity and symmetry without transitivity describe 'local similarity' that doesn't propagate into well-defined global groups.