Godel's First Incompleteness Theorem Flashcards
What is representability?
What are the two key ideas of Godel’s proof?
- Godel Numbering: Allows formulas to refer to other formulas
- Self-focussing: String refer to itself
What are a proof pair?
Both must be the last line of a proof
1. Primitive recursive
2. Represented in TNT
Why isn’t the following primitive recursive?
Ex: proof-pair(x, y): provable(y)
Not primitive recursive since there is no upper bound - not false just not provable
Difference between finding and checking a proof
What is a MIU proof-pair?
Since property of MIU-proof pair is representability, let MIU-PROOF_PAIR{a, a’} be a formula that represents it
What is a TNT-proof pair?
Proof Representable
How does substitution of numerals in formulas work?
SUB{(from one free variable), (numeral to sub), (resulting formula)>
Task: Replace the free variable in a formula by a numeral
Representability in substitution
- Prim recursive
- Represented TNT fro 3 free variables
Therefore, TNT proves to true instance of it
What is arithmoquining?
a’ is the Godel number of the formula that results from substituting the numberal a’’ for the free variable in the formula with the Godel number a’’
What is the diagonal function for arithmiquinification?
Formulas expressing properties about formulas:
What is G’s aunt?
There is no proof in TNT of the arithmoquinification of a’’ so the arithmoquinification of a’’ is not provable in TNT
What is the formula for the Godel sentence G?
where F(a’’) = u, such that F(u) = G
What does it say?
(1) Literal Translation: “There is no number a, such taht there is a number a’ “
a) They form a TNT-proof pair (a codes a proof of the formula coded by a’), and
b) a’ is the arithmoquinification of u’’
(2) There is a number a’, the arithmoquinification of u, the problem must be with the other number, a.
Thus: There is no number a that makes a proof-pair with the arithmoquinification of u.
(3) So: G says “G is not a TNT Theorem
“I am not a TNT theorem”
What is the Godel’s First Incompleteness Theorem?
(a) Is G a TNT theorem?
* Assume that TNT ` G.
* If so, then it must be true (by soundness, TNT proves only arithmetical truths).
* But G asserts that it is not a TNT theorem. !Contradiction!
* So G cannot be a TNT theorem
b) Is ⇠ G a TNT theorem?
* Assume TNT ` ⇠ G.
* Then ⇠ G would be true.
* But ⇠ G asserts that: G is a TNT theorem.
So, both ⇠ G and G would be TNT theorems, i. e., TNT would be inconsistent.
* Thus, if TNT is consistent, ⇠ G cannot be a TNT theorem.
c) If TNT is consistent, then TNT is incomplete
Conditions: Every (1) consistent, (2) axiomatizable theory, (3) includes π1
is INCOMPLETE
Can we fix TNT?
Adding postulates to TNT to create stronger axiomatizable theories won’t solve the problem:
for each theory there will be a true formula, which is in OMEGA , but unprovable in the theory.
The Gödel-Rosser Theorem is a very strong result, for it tells us that any axiomatizable theory ⌃ which is consistent and extends ⇧1 is incomplete, and thus cannot come close to OMEGA
(the theory of all arithmetical truths, see Section 16.4, p. 60):
⇧1 ⇢ ⇧2 ⇢ ⇧ ⇢ …
