STEP-BY-STEP LESSON · §8.3
Equivalence Relations
Connect an equivalence relation with a partition into disjoint classes.
Before you begin
Reflexivity, Symmetry, and Transitivity
Reflexivity requires aRa for every a∈A, including elements with no other arrows.
∀a∈A: aRa
Symmetry requires that whenever aRb holds, bRa also holds.
aRb ⇒ bRa
If aRb and bRc hold, transitivity requires aRc. The elements a,b,c need not be distinct.
aRb ∧ bRc ⇒ aRc
Set Theory: Definitions and the Element Method of Proof
The statement x∈A concerns one object. A⊆B says that every element of A belongs to B.
A⊆B ⇔ ∀x(x∈A ⇒ x∈B)
X=Y means X⊆Y and Y⊆X. One inclusion still allows extra elements in the second set.
X=Y ⇔ (X⊆Y ∧ Y⊆X)
Symbols
- [a]
- equivalence class of a
- A
- the underlying set; all related objects lie in A
Definitions and notation for this topic
Equivalence relation
a∼b
A relation that is reflexive, symmetric, and transitive.
An equivalence relation partitions its underlying set into classes.
Separate glossary example
Having the same remainder modulo 3 is an equivalence relation on ℤ.
Equivalence class
[a]={x∈A:x∼a}For an equivalence relation ∼ on A, [a] is the set of all elements of A equivalent to a. The relation must be stated.
Any two classes are equal or disjoint; the union of all equivalence classes is A. The brackets here do not mean a real interval or rounding down.
Separate glossary example
On ℤ modulo 3, [1]={…,−5,−2,1,4,7,…} and [1]=[4].
Step by step
Step 1 / 6
Check the three properties
An equivalence relation must be reflexive, symmetric, and transitive. The idea “treated as equivalent” must satisfy all three.
a∼b
Groups that merely look similar do not guarantee equivalence.
Worked example
On ℤ let a∼b mean a−b is even. What are the classes?
- a−a=0 is even. If a−b=2k, then b−a=2(−k): reflexivity and symmetry hold.
- If a−b=2k and b−c=2m, then a−c=2(k+m), establishing transitivity.
- [0] is the even integers and [1] the odd integers. For example [2]=[0], not a third class.
Optional self-check
For this relation, does [3] equal [0] or [1]?
Show answer
[3]=[1], because 3−1=2 is even.