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