incompleteness-theorem.md (1221B)
1 +++ 2 template = 'page-math.html' 3 title = 'Incompleteness theorem' 4 +++ 5 # Incompleteness theorem 6 Consider sets of function and predicate symbols: 7 * F = {0, S, +, ·} 8 * P = {<} 9 10 with as intended model number theory N: 11 * domain of N is the natural numbers with 0 12 * $0^\mathbb{N} = 0$ 13 * $S^\mathbb{N} (n) = n + 1$ 14 * $+^\mathbb{N} (n,m) = n+m$ 15 * $\mathbb{N}(n,m) = n \cdot m$ 16 * $<^\mathbb{N} = \{ <n,m> | n,m \in \mathbb{N} \text{ such that }n < m \}$ 17 18 One would like to have complete theory (deduction system) ⊢ for N that allows to derive all formulas that are true in N. 19 20 First incompleteness theorem: 21 * every axiomatizable and sound theory ⊢ of first-order logic 22 * for number theory with language <F,P> 23 * is incomplete: 24 * it contains sentences Φ that are true in N, but unprovable in ⊢: N ⊨ Φ, yet ⊬ Φ. 25 26 27 Second incompleteness theorem: 28 * for every axiomatizable theory ⊢ of first-order logic 29 * for number theory with language <F,P> 30 * that is rich enough to express its own consistency by a sentence Φ⊢ 31 * it holds that either: 32 * ⊢ ⊥ (⊢ is inconsistent) 33 * ⊬ Φ⊢ (hence ⊢ is incomplete) 34 * so first-order theories (based on predicate logic) of number theory can't prove their own consistency