Equivalence classes.md (1105B)
1 +++ 2 title = 'Equivalence classes' 3 template = 'page-math.html' 4 +++ 5 # Equivalence classes 6 a *binary* relation R is an equivalence relation if for all elements x, y, z in its domain, R satisfies: 7 8 - reflexivity: x R x 9 - symmetry: x R y ➝ y R x 10 - transitivity: x R y ∧ y R z ➝ x R z 11 12 an equivalence class consists of all elements x,y for which x R y 13 14 within an equivalence class, all formulas are semantically equivalent 15 16 each equivalence class contains infinitely many formulas 17 18 one class contains all tautologies, another all contradictions (all semantically equivalent) 19 20 for two vars p,q there are as many ≡-equivalence classes as truth tables for p,q — i.e. 16 21 22 ## How many equivalence classes? 23 24 for one variable p, there are two valuations (T or F) 25 - each valuation has two possible outcomes (T or F) 26 - therefore, 22 = 4 equivalence classes 27 28 for two variables p,q there are four valuations (T or F for each var) 29 - each valuation has two possible outcomes (T or F) 30 - therefore, 24 = 16 equivalence classes 31 32 etc. for n variables, there are $2^n$ valuations and $2^{2^n}$ equivalence classes.