Equivalence relations & classes

Equivalence relation in V

relation R of type V × V that satisfies:

• reflexivity: x R x
• transitivity: x R y ∧ y R z ➝ x R z
• symmetry: x R y ➝ y R x

Equivalence classes

an equivalence relation ≡ in a set V partitions the set into equivalence classes

equivalence class of p: [p] = { x ∈ V: p ≡ x },    p ∈ V

all elements of equivalence class relate to each other

elements of different equivalence classes are unrelated

equivalence classes lead to a partition: { [p] : p ∈ V }

Complete system of representatives

for ≡ in V is a set S ⊆ V that contains *exactly one *element from each equivalence class

in other words:

1. every v ∈ V is equivalent to some s ∈ S
2. two different elements of S are not equivalent