Equivalence relations & classes.md (846B)
1 +++ 2 title = 'Equivalence relations & classes' 3 +++ 4 # Equivalence relations & classes 5 ## Equivalence relation in V 6 relation R of type V × V that satisfies: 7 8 - reflexivity: x R x 9 - transitivity: x R y ∧ y R z ➝ x R z 10 - symmetry: x R y ➝ y R x 11 12 ## Equivalence classes 13 14 an equivalence relation ≡ in a set V partitions the set into equivalence classes 15 16 equivalence class of p: 17 [p] = { x ∈ V: p ≡ x }, p ∈ V 18 19 all elements of equivalence class relate to each other 20 21 elements of different equivalence classes are unrelated 22 23 equivalence classes lead to a partition: 24 { [p] : p ∈ V } 25 26 ## Complete system of representatives 27 28 for ≡ in V is a set S ⊆ V that contains *exactly one *element from each equivalence class 29 30 in other words: 31 1. every v ∈ V is equivalent to some s ∈ S 32 2. two different elements of S are not equivalent