Report

Equivalence relations • Binary relations: – Let S1 and S2 be two sets, and R be a (binary relation) from S1 to S2 – Not every x in S1 and y in S2 have such relation – If R holds for a in S1 and b in S2, denote as aRb or R(a, b) Examples: Spouse relation from set Men to set Women – S1 and S2 can be the same set Examples: Parent relation on set Human > (greater than) relation on set Z (all integers) 1 Equivalence relations (cont) • Properties of binary relations: – Let R be a binary relation on set S – R is reflexive: if aRa for all a in S Ex: = relation, >= relation – R is symmetric: aRb iff bRa Ex: = relation, spouse relation – R is transitive: if aRb and bRc, then aRc Ex: = relation, >= relation, ancestor relation – R is an equivalence relation if it is reflexive, symmetric, and transitive. Ex. = relation, relative relation among humans Counter ex: >= relation, spouse relation – Use “~” to denote an abstract generic equivalence relation a~b 2 Equivalence relations (cont) • Equivalence classes – Let ~ be a equivalence relation defined on set S – S can be partitioned into disjoint subsets such that • If a ~ b, then a and b are in one subset • If a and b are in two different subsets, then a ~ b does not hold – Each of such subsets is called an equivalence class (with respect to relation ~), denoted C1, C2, ... • All elements in an equivalence class relate to each other by ~ • No elements in different equivalence classes relate to each other by ~ – Equivalence classes can be represented as disjoint sets 3