6.042J/18.062J 7. Set Theory

1 lec 3F.1 Albert R Meyer, February 19, 2010 Mathematics for Computer Science MIT 6.042J/18.062J Set Theory lec 3F.2 Albert R Meyer, February 19, 2010 Axioms ∀x[x ∈ y↔ x ∈ z]→ y = z Equality Power set ∀x∃p∀s.s ⊆ x ↔ s ∈ p lec 3F.3 Albert R Meyer, February 19, 2010 Russell’s Paradox Now let s be W, and reach a contradiction: lec 3F.4 Albert R Meyer, February 19, 2010 Disaster: Math is broken! I am the Pope, Pigs fly, and verified programs crash... lec 3F.5 Albert R Meyer, February 19, 2010 for all sets s …can only substitute W for s if W is a set ...but paradox is buggy Assumes that W is a set! lec 3F.6 Albert R Meyer, February 19, 2010 We can avoid the paradox, if we deny that W is a set! …which raises the key question: just which well-defined collections are sets? ...but paradox is buggy Assumes that W is a set! 2 lec 3F.8 Albert R Meyer, February 19, 2010 Zermelo-Frankel Set Theory No simple answer, but the axioms of Zermelo-Frankel along with the Choice axiom (ZFC) do a pretty good job. lec 3F.9 Albert R Meyer, February 19, 2010 According to ZF, the elements of a set have to be “simpler” than the set itself. In particular, no set is a member of itself. Zermelo-Frankel Set Theory lec 3F.10 Albert R Meyer, February 19, 2010 This implies that (1) the collection of all sets is not a set, and (2) W equals the collection of all sets …which is why it’s not a set Zermelo-Frankel Set Theory lec 3F.11 Albert R Meyer, February 19, 2010 infinite sizes Are infinite sets the “same size”? NO, by Russell paradox variant: Theorem: No surjective function from A to pow(A), even for infinite A lec 3F.12 Albert R Meyer, February 19, 2010 no surjection from A to pow(A) W::= {a ∈A | a ∉ f(a)}, so a ∈W iff a ∉ f(a). f a surj, so W=f(a0), some a0 ∈A. So, a0 ∈f(a0) iff a0 ∉ f(a0). Pf by contradiction: suppose surj fcn f:A→pow(A). Let lec 3F.13 Albert R Meyer, February 19, 2010 {0,1}ω is uncountable A is countable iff can be listed a0,a1,a2,…. surj same as surj fcn: N→A So {0,1}ω is uncountable, because N → {0,1} ω surj      bij      → pow(N)3 lec 3F.16 Albert R Meyer, February 19, 2010 Team Problems Problems 1―3 MIT OpenCourseWare http://ocw.mit.edu 6.042J /18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.