machine learning, ai, cs · slides

Intuitive Intro to Gödel's Incompleteness Theorem

Slide 1 of 56: this slide intentionally left blankSlide 2 of 56: Intuition The Book of All True Sentences http://fouryears.eu/2013/01/27/on-godels-theorems-and-the-universe/Slide 3 of 56: Intuition “This sentence is not in The Book” http://fouryears.eu/2013/01/27/on-godels-theorems-and-the-universe/Slide 4 of 56: Intuition “This sentence is not in The Book” incomplete http://fouryears.eu/2013/01/27/on-godels-theorems-and-the-universe/Slide 5 of 56: Intuition “This sentence is not in The Book” incomplete “This sentence is not in The Book” http://fouryears.eu/2013/01/27/on-godels-theorems-and-the-universe/Slide 6 of 56: Intuition “This sentence is not in The Book” incomplete “This sentence is not in The Book” inconsistent http://fouryears.eu/2013/01/27/on-godels-theorems-and-the-universe/Slide 7 of 56: Language http://fouryears.eu/2013/01/27/on-godels-theorems-and-the-universe/Slide 8 of 56: Language Because it would be infinitely large The Book of All True Sentences http://fouryears.eu/2013/01/27/on-godels-theorems-and-the-universe/Slide 9 of 56: Language http://fouryears.eu/2013/01/27/on-godels-theorems-and-the-universe/Slide 10 of 56: Language http://fouryears.eu/2013/01/27/on-godels-theorems-and-the-universe/Slide 11 of 56: Language The Book of All True Sentences http://fouryears.eu/2013/01/27/on-godels-theorems-and-the-universe/Slide 12 of 56: Language “This sentence will not be included in the book generated by our language." http://fouryears.eu/2013/01/27/on-godels-theorems-and-the-universe/Slide 13 of 56: Language “This sentence will not be included in the book generated by our language." http://fouryears.eu/2013/01/27/on-godels-theorems-and-the-universe/Slide 14 of 56: Puzzle Raymond M. Smullyan - Godel's Incompleteness TheoremsSlide 15 of 56: Puzzle Raymond M. Smullyan - Godel's Incompleteness Theorems a lphabet: ~ P N ( )Slide 16 of 56: Puzzle Raymond M. Smullyan - Godel's Incompleteness Theorems a lphabet: ~ P N ( ) expression: finite non-empty string of these symbolsSlide 17 of 56: Puzzle Raymond M. Smullyan - Godel's Incompleteness Theorems a lphabet: ~ P N ( ) expression: finite non-empty string of these symbols printable: machine can and will print itSlide 18 of 56: Puzzle Raymond M. Smullyan - Godel's Incompleteness Theorems a lphabet: ~ P N ( ) expression: finite non-empty string of these symbols printable: machine can and will print it norm of X : expression in form X(X) , for example P(P)Slide 19 of 56: Puzzle Raymond M. Smullyan - Godel's Incompleteness Theorems a lphabet: ~ P N ( ) expression: finite non-empty string of these symbols printable: machine can and will print it norm of X : expression in form X(X) , for example P(P) sentence: (1) P(X) true iff X is printable (2)…Slide 20 of 56: Puzzle Raymond M. Smullyan - Godel's Incompleteness Theorems a lphabet: ~ P N ( ) expression: finite non-empty string of these symbols printable: machine can and will print it norm of X : expression in form X(X) , for example P(P) sentence: (1) P(X) true iff X is printable (2)…Slide 21 of 56: Puzzle Raymond M. Smullyan - Godel's Incompleteness Theorems a lphabet: ~ P N ( ) expression: finite non-empty string of these symbols printable: machine can and will print it norm of X : expression in form X(X) , for example P(P) sentence: (1) P(X) true iff X is printable (2)…Slide 22 of 56: Raymond M. Smullyan - Godel's Incompleteness Theorems PuzzleSlide 23 of 56: Raymond M. Smullyan - Godel's Incompleteness Theorems Puzzle ~PN(~PN)Slide 24 of 56: Raymond M. Smullyan - Godel's Incompleteness Theorems Puzzle ~PN(~PN) ~PN(~PN) is true iff norm of ~PN is not printable.Slide 25 of 56: Raymond M. Smullyan - Godel's Incompleteness Theorems Puzzle ~PN(~PN) ~PN(~PN) is true iff norm of ~PN is not printable. ~PN(~PN) is true iff ~PN(~PN) is not printable.Slide 26 of 56: Raymond M. Smullyan - Godel's Incompleteness Theorems Puzzle ~PN(~PN) ~PN(~PN) is true iff norm of ~PN is not printable. ~PN(~PN) is true iff ~PN(~PN) is not printable. If machine prints ~PN(~PN) then is has printed false sentence.Slide 27 of 56: Raymond M. Smullyan - Godel's Incompleteness Theorems Puzzle ~PN(~PN) ~PN(~PN) is true iff norm of ~PN is not printable. ~PN(~PN) is true iff ~PN(~PN) is not printable. If machine prints ~PN(~PN) then is has printed false sentence. If machine never prints ~PN(~PN) then is has…Slide 28 of 56: Raymond M. Smullyan - Godel's Incompleteness Theorems Puzzle ~PN(~PN) ~PN(~PN) is true iff norm of ~PN is not printable. ~PN(~PN) is true iff ~PN(~PN) is not printable. If machine prints ~PN(~PN) then is has printed false sentence. If machine never prints ~PN(~PN) then is has…Slide 29 of 56: Raymond M. Smullyan - Godel's Incompleteness Theorems Provable “Printable” “Provable”Slide 30 of 56: Raymond M. Smullyan - Godel's Incompleteness Theorems Provable “Printable” “Provable” ~PN(~PN) The norm of ~PN is not provable within the formal systemSlide 31 of 56: Raymond M. Smullyan - Godel's Incompleteness Theorems Provable “Printable” “Provable” ~PN(~PN) The norm of ~PN is not provable within the formal system If you can prove ~PN(~PN) within the system (using system’s rules) then you have proven false claim and your system is…Slide 32 of 56: Raymond M. Smullyan - Godel's Incompleteness Theorems Provable “Printable” “Provable” ~PN(~PN) The norm of ~PN is not provable within the formal system If you can prove ~PN(~PN) within the system (using system’s rules) then you have proven false claim and your system is…Slide 33 of 56: Theorem Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete . In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement…Slide 34 of 56: Theorem Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete . In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement…Slide 35 of 56: Theorem Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete . In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement…Slide 36 of 56: Theorem Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete . In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement…Slide 37 of 56: this slide intentionally left blankSlide 38 of 56: “Book” intuition ✓Slide 39 of 56: “Book” intuition ~ P N ( ) system ✓ ✓Slide 40 of 56: “Book” intuition ~ P N ( ) system Gödel’s theorem with shades of Tarski ✓ ✓ ✓Slide 41 of 56: “Book” intuition ~ P N ( ) system Gödel’s theorem with shades of Tarski Assuming Peano Arithmetic is correct ✓ ✓ ✓ ✓Slide 42 of 56: “Book” intuition ~ P N ( ) system Gödel’s theorem with shades of Tarski Assuming Peano Arithmetic is correct Assuming Peano Arithmetic is ω -consistent ✓ ✓ ✓ ✓ ?Slide 43 of 56: ω -consistency Consistency: There is no formula F such that both F and ¬F are provableSlide 44 of 56: ω -consistency Consistency: There is no formula F such that both F and ¬F are provable ω -inconsistency If for some formula A(x), each formula of the infinite sequence A(0), …, A(n) is provable and also the formula ¬ ∀ xA(x) is provableSlide 45 of 56: ω -consistency Consistency: There is no formula F such that both F and ¬F are provable ω -inconsistency If for some formula A(x), each formula of the infinite sequence A(0), …, A(n) is provable and also the formula ¬ ∀ xA(x) is provable This may not lead directly to an outright…Slide 46 of 56: ω -consistency Consistency: There is no formula F such that both F and ¬F are provable ω -inconsistency If for some formula A(x), each formula of the infinite sequence A(0), …, A(n) is provable and also the formula ¬ ∀ xA(x) is provable This may not lead directly to an outright…Slide 47 of 56: If a formal system which contains elementary arithmetic (like Peano Arithmetic) is consistent , then it cannot prove its own consistency . 2ndSlide 48 of 56: Consistent formal system is incompleteSlide 49 of 56: Consistent formal system is incomplete Some stuff is not provableSlide 50 of 56: Consistent formal system is incomplete Some stuff is not provable For example claim of its own consistency is one such stuffSlide 51 of 56Slide 52 of 56Slide 53 of 56Slide 54 of 56Slide 55 of 56Slide 56 of 56: Q: An advanced reasoner visits the Island of Knights and Knaves and meets a native who tells him, "You can not prove I'm a knight." Prove that if the reasoner should assume that he is consistent, then he will be come inconsistent. Stated otherwise, if the reasoner is (and…
1 / 56

An informal walk towards Gödel’s incompleteness theorems, built on intuition and puzzles rather than formal logic. It starts with The Book of All True Sentences and the sentence “This sentence is not in The Book”: either the book leaves out a true sentence and is incomplete, or it includes a false one and is inconsistent. The same trick is then played on a language that generates such a book, and on Raymond Smullyan’s printing machine with the alphabet ~ P N ( ), where the sentence ~PN(~PN) says of itself that the machine will never print it. The first part follows the blog post On Gödel’s theorems and the universe.

Reading “printable” as “provable” turns the puzzle into the theorem: any consistent, effectively generated formal system that can express elementary arithmetic contains true statements it cannot prove. The slides then cover ω-consistency and the second incompleteness theorem: such a system cannot prove its own consistency.

Download PDF