sets.wiki (1739B)
1 %template math 2 == Sets == 3 Recap from logic and sets: 4 * empty set Ø = {x | false} 5 * universal set U = {x | true} 6 * union A ∪ B = {x | x ∈ A or x ∈ B} 7 * intersection A ∩ B = {x | x ∈ A and x ∈ B} 8 * complement Ā = {x | x ∉ A} 9 * difference A \ B = {x | x ∈ A and x ∉ B} 10 11 Theorems: 12 * A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 13 * (A \ B) \ C = A \ (B ∪ C) 14 15 === Relations === 16 definitions of properties: 17 * reflexive: ∀x R(x,x) 18 * symmetric: ∀x ∀y (R(x,y) → R(y,x)) 19 * transitive: ∀x ∀y ∀z ((R(x,y) ∧ R(y,z)) → R(x,z)) 20 * serial: ∀x ∃y R(x,y) 21 * functional: ∀x ∃y (R(x,y) ∧ ∀z (R(x,z) → z=y)) 22 23 ==== Order types ==== 24 partial order: 25 * reflexive 26 * transitive 27 * antisymmetric 28 29 total order: 30 * partial order 31 * ∀ a,b (R(a,b) ∨ R(b,a)) 32 33 strict partial order: partial order but irreflexive 34 35 strict total order: 36 * strict partial order 37 * ∀ a,b (R(a,b) ∨ (a=b) ∨ R(b,a)) 38 39 equivalence relation: 40 * reflexive (∀a, a ≡ A) 41 * symmetric 42 * transitive 43 44 === Natural numbers & induction === 45 Set of natural numbers is N ∈ (0,∞) 46 47 Principle of induction: let P be a property of natural numbers. Suppose P holds for zero, and whenever P holds for a natural number n, then it holds for its successor n+1. Then P holds for every natural number. 48 49 As a natural deduction rule: 50 51 {{local:../img/induction-natural-deduction-rule.png|Induction natural deduction rule}} 52 53 === Recursive definitions === 54 Let A be any set, suppose a is in A, and g: N × A → A. Then there is a unique function f satisfying: 55 * f(0) = a 56 * f(n+1) = g(n, f(n)) 57 58 Typically to prove something about a recursively defined function is to use induction. 59