© . Three Profound Theorems about Gödel's Completeness Theorem : & rules, to prove all validities. *Theoretically only: having more Copyright ©Albert R. Meyer, 2005.lec 2F.1 September 16, 2005 Copyright Albert R. Meyer, 2005Power & Limits of Logic Mathematical Logic lec 2F.2 September 16, 2005 Thm 1, good newsonly need to know* a few axioms rules is convenient. © . Axioms & Inference Rules propositional & simple predicate validities, every valid assertion can be proved just UG and modus ponens repeatedly! Bad News: there is no procedure that determines when assertions are valid (in contrast to propositional Copyright ©Albert R. Meyer, 2005.lec 2F.3 September 16, 2005 Copyright Albert R. Meyer, 2005Namely, starting from a few using lec 2F.4 September 16, 2005 Cannot Determine Validity Thm 2, quantified formulas). © . Gödel's Incompleteness Theorem for Arithmetic Worse News: N, with predicates x + y = z, x · y = z, then no proof system can prove all the assertions! Three Profound Theorems We won't prove these Theorems. Copyright ©Albert R. Meyer, 2005.lec 2F.5 September 16, 2005 Copyright Albert R. Meyer, 2005Thm 3, if we stick to domain, true lec 2F.6 September 16, 2005 Their proofs usually require half a term in an intro logic course after 6.042. 1© . Sets & Functions Sets collection? Copyright ©Albert R. Meyer, 2005.lec 2F.7 September 16, 2005 Copyright Albert R. Meyer, 2005Mathematics for Computer Science MIT 6.042J/18.062J lec 2F.8 September 16, 2005 Informally, a set is a collection of mathematical objects with the collection treated as a single mathematical object. This is circular of course: what’s a © . Some sets Real numbers, R complex numbers, C Z ∅ , pow(Z) Some sets {7, “Albert R.”, π/2, Τ} A set with 4 : two numbers, a string, and a Boolean value. {“Albert R.”,7,Τ, π/2} Copyright ©Albert R. Meyer, 2005.lec 2F.9 September 16, 2005 Copyright Albert R. Meyer, 2005integers, the emptyset, the set of all sets of integers the set power lec 2F.10 September 16, 2005 elementsSame as -- order doesn’t matter © . Membership x A∈ x is an of A π/2 ∈ {7, “Albert R.”,π/2, Τ} π/3 ∉ {7, “Albert R.”,π/2, Τ} 14/2 ∈ {7, “Albert R.”,π/2, Τ} © . Membership x A∈ x is a member of A shorter: “x is in A” 7∈Z 2/3 ∉ Z Z ∈pow(R) lec 2F.11 September 16, 2005 Copyright Albert R. Meyer, 2005element lec 2F.12 September 16, 2005 Copyright Albert R. Meyer, 20052© . In or Not In {7, π π/2} in a set, or not in more than once) © . A B⊆ A is a subset of B A is contained in B A is also an element of B. Z⊆R, R⊆C, {3}⊆{5,7,3} ∅⊆ every set lec 2F.13 September 16, 2005 Copyright Albert R. Meyer, 2005/2, 7} is same as {7, An element, like 7, is the set. (No notion of being in the set lec 2F.14 September 16, 2005 Copyright Albert R. Meyer, 2005Containment Every element of © . Team Problem Problem 1 © . Defining Sets ){ }(|∈ The , x, in A such that P(x) is true. lec 2F.15 September 16, 2005 Copyright Albert R. Meyer, 2005 lec 2F.16 September 16, 2005 Copyright Albert R. Meyer, 2005xA Px set of elements© . Defining Sets { }| . 2n m n m∈ ∃ ∈ = Z Z The set of even integers: { }|n n∈ Z © . A and B A B lec 2F.17 September 16, 2005 Copyright Albert R. Meyer, 2005 is even lec 2F.19 September 16, 2005 Copyright Albert R. Meyer, 2005Venn Diagram for New sets from old 34lec 2F.20September 16, 2005Copyright © Albert R. Meyer, 2005.unionAB:: {|()()}xxA xA BB ∨=∈ ∈∪lec 2F.21September 16, 2005Copyright © Albert R. Meyer, 2005. intersectionAB:: { | }A xx x BB A= ∈∈∩ ∧lec 2F.22September 16, 2005Copyright © Albert R. Meyer, 2005. BAset difference:: { | ( ) ( )}xxA xABB ∧=∈−∉lec 2F.23September 16, 2005Copyright © Albert R. Meyer, 2005. complement:: { | }xD AA xA D∉= ∈=−AD−AA =knowndomain Dlec 2F.24September 16, 2005Copyright © Albert R. Meyer, 2005. ()::{|o }pwA SS A= ⊆{} {}{}{}{}pow( , ) , , , ,ab ab a b=∅power setlec 2F.25September 16, 2005Copyright © Albert R. Meyer, 2005. QuickieWhat is Pow(∅)?Ans: {∅}What is Pow(Pow(∅))?Ans: {{∅}, ∅}© . Russell’s Paradox { }|W S= ∈ ∉ so SW∈ ∉↔ Let S be W and reach a contradiction: WW WW∈ ↔ ∉ © . Russell’s Paradox So the collection, , of all sets, cannot set! lec 2F.26 September 16, 2005 Copyright Albert R. Meyer, 2005Let :: Sets S S S S lec 2F.27 September 16, 2005 Copyright Albert R. Meyer, 2005Setsbe considered a © . Functions © . f A to set B with an element Example: f is the string-length function: f(“aabd”)=4 : B→ () B∈ .aA∈ lec 2F.31 September 16, 2005 Copyright Albert R. Meyer, 2005Mathematics for Computer Science MIT 6.042J/18.062J lec 2F.32 September 16, 2005 Copyright Albert R. Meyer, 2005function, , from set associates an element, f A f a © . f is the string-length function. A, the domain of f, B, the codomain of f, is : B→ N © . domain(g) = all pairs of reals codomain(g)=But g is partial: not defined on all pairs of reals 2:g →1(, )gxy x y = − lec 2F.33 September 16, 2005 Copyright Albert R. Meyer, 2005is the set of strings. f A lec 2F.34 September 16, 2005 Copyright Albert R. Meyer, 2005all reals R R 5© . where Then g´ is total: D. :gD′ →R 1(, )′ = − { }2 (, ) |D = − =R © . Total functions is total A is assigned a B-value by f :fA B→ .( ) b= lec 2F.35 September 16, 2005 Copyright Albert R. Meyer, 2005defined on all pairs in domain gxy x y xy y x lec 2F.36 September 16, 2005 Copyright Albert R. Meyer, 2005iff every element of aA b Bfa ∀ ∈∃∈ © . is onto B is f :fA B→ .( ) b= a surjection © . is 1-1 B is f of at most:fA B→ , .( ( ) ( ')) ( ')aa′∀ ∈ = → = an injection lec 2F.37 September 16, 2005 Copyright Albert R. Meyer, 2005Onto functions iff every element of of something bB a Afa ∀∈ ∃∈ lec 2F.38 September 16, 2005 Copyright Albert R. Meyer, 20051-1 functions iff every element of 1 thing A f a f a a a © . is a bijection iff it is all those good things: total, onto, and 1-1 Bijections : B→ © . is a bijection an exact correspondence: Bijections : B→ A B f( )= lec 2F.39 September 16, 2005 Copyright Albert R. Meyer, 2005f A lec 2F.40 September 16, 2005 Copyright Albert R. Meyer, 2005iff it is f A 6© . Bijections A B f( )= exactly one arrow in © . Team Problem Problem 2 lec 2F.41
View Full Document
Unlocking...