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