Gödel’s TheoremOverviewLifeHistoryThe theoremGödel’s MethodPredicate CalculusStandard ArithmeticThe axiomsGödel NumberingComputing a Gödel NumberProof (x,y,z)Proof(x,y,z)Slide 14Slide 15The ProofSlide 17ImplicationsSourcesHomeworkGGöödel’s Theoremdel’s TheoremCarmen SerranoCarmen SerranoOverviewOverviewKurt GödelKurt Gödel2020thth century mathematical logician century mathematical logicianIncompleteness TheoremIncompleteness TheoremProve incompleteness of formal systemsProve incompleteness of formal systemsLifeLifeBorn in 1906 in Austria-HungaryBorn in 1906 in Austria-HungaryEarly interest in mathematicsEarly interest in mathematicsStudies in University of ViennaStudies in University of ViennaPublishes famous theorems at 25Publishes famous theorems at 25Nazi Germany annexation of AustriaNazi Germany annexation of AustriaInstitute for Advanced Study, PrincetonInstitute for Advanced Study, PrincetonHistoryHistoryFormalized system for mathematicsFormalized system for mathematicsBased on axiomsBased on axiomsWorks by Russell, Whitehead, HilbertWorks by Russell, Whitehead, HilbertWidely believed to be possibleWidely believed to be possibleThe theoremThe theorem““In any sound, consistent, formal system In any sound, consistent, formal system containing arithmetic there are true containing arithmetic there are true statements that cannot be proved…”statements that cannot be proved…”……solely with axioms from that systemsolely with axioms from that systemGödel’s MethodGödel’s MethodThree steps:Three steps:1. Set up axioms and rule of inference for 1. Set up axioms and rule of inference for predicate calculuspredicate calculus2. Set up axioms for arithmetic in predicate 2. Set up axioms for arithmetic in predicate calculuscalculus3. Establish numbering system for formulas3. Establish numbering system for formulasPredicate CalculusPredicate CalculusAx - “For all values of x…”Ax - “For all values of x…”Ex – “There exists an x…”Ex – “There exists an x…”P, Q, … – formulasP, Q, … – formulasx – variablex – variable - implication; “if… then…”- implication; “if… then…”┐ ┐ - “not” operator- “not” operator& - “and” operator& - “and” operatorStandard ArithmeticStandard ArithmeticNatural numbers: 0, 1, 2, 3, …Natural numbers: 0, 1, 2, 3, …Addition and multiplicationAddition and multiplicationSuccessor function, Successor function, ss::sx = x+1sx = x+1The axiomsThe axiomsSix axioms and a rule of inference for Six axioms and a rule of inference for predicate calculuspredicate calculusIf F and F If F and F G, then G. G, then G.Nine axioms and rule of induction for Nine axioms and rule of induction for arithmeticarithmetic(P(0) & Ax(P(x)(P(0) & Ax(P(x)P(sx))) P(sx))) AxP(x) AxP(x)Gödel NumberingGödel NumberingSymbolSymbol00++==xxCode NumberCode Number11335599Computing a Gödel NumberComputing a Gödel Numberx + 0 = xx + 0 = x2^9 * 3^3 * 5^1 * 7^5 * 11^92^9 * 3^3 * 5^1 * 7^5 * 11^9Gödel number: Gödel number: 512*27*5*16807*2357947691512*27*5*16807*2357947691A very large number! A very large number! Expression can be extracted from numberExpression can be extracted from numberProof (x,y,z)Proof (x,y,z)Representation from textbookRepresentation from textbookProof X: Proof(x,y,z)Proof X: Proof(x,y,z)x – Gödel number of proof Xx – Gödel number of proof Xy – Gödel number of formula Yy – Gödel number of formula YY – formula being provenY – formula being provenz – integer substituted in formula Yz – integer substituted in formula YProof(x,y,z)Proof(x,y,z)Actual expression is more complicatedActual expression is more complicatedTextbook version is concise:Textbook version is concise:““x is the Gödel number of a proof X of a x is the Gödel number of a proof X of a formula Y (with one free variable and Gödel formula Y (with one free variable and Gödel number y) which has the integer z substituted number y) which has the integer z substituted into it.”into it.”Making sense?Making sense?Proof (x,y,z)Proof (x,y,z)Review:Review:Proof X: Proof(x,y,z)Proof X: Proof(x,y,z)x – Gödel number of proof Xx – Gödel number of proof Xy – Gödel number of formula Yy – Gödel number of formula YY – formula being provenY – formula being provenz – integer substituted in formula Yz – integer substituted in formula YGödel’s TheoremGödel’s TheoremGödel’s Theorem:Gödel’s Theorem:┐┐ExProof(x,g,g) is true but not provable in the ExProof(x,g,g) is true but not provable in the formal arithmetic system.formal arithmetic system.Proof(x,g,g): “x is the Gödel number of a proof Proof(x,g,g): “x is the Gödel number of a proof of the formula obtained by substituting its own of the formula obtained by substituting its own Gödel number g for its one free variable”Gödel number g for its one free variable”The ProofThe ProofSuppose Suppose ┐ExProof(x,g,g) can be proven┐ExProof(x,g,g) can be provenUsing axioms and rules of systemUsing axioms and rules of systemCall proof P, with Gödel number pCall proof P, with Gödel number pProof P: Proof(p,g,g)Proof P: Proof(p,g,g)P is true since we supposed it was provableP is true since we supposed it was provableBut Proof(p,g,g) contradicts But Proof(p,g,g) contradicts ┐ExProof(x,g,g)┐ExProof(x,g,g)Therefore P can’t existTherefore P can’t existOriginal claim is true – doesn’t have a proofOriginal claim is true – doesn’t have a proofProof with Universal Truth MachineProof with Universal Truth MachineGödel’s TheoremGödel’s TheoremConsistent – true statements are not Consistent – true statements are not contradictedcontradictedComplete – true statements can be provenComplete – true statements can be proven““Within any sound, consistent, formal Within any sound, consistent, formal system containing arithmetic there are true system containing arithmetic there are true statements that cannot be proved [within statements that cannot be proved [within that system].”that system].”Consistent vs. CompleteConsistent vs. CompleteImplicationsImplicationsMajor discovery in mathematical theoryMajor discovery in
View Full Document
Unlocking...