So, recently I was reading Godel, Escher and Bach and came across these terms and I am not quite sure of the difference between them and it is my humble request if someone can explain these terms not in the Hofstadterian sense.
Asked
Active
Viewed 961 times
1 Answers
4
A theory $T$ with "enough experssive capabilities" such that is able to prove the basic axioms of the natural numbers is ω-inconsistent if, for some formula $P(x)$ in the language of $T$, $T$ proves $P(0), P(1), P(2), \ldots$ (i.e. for every natural number $n$ : $T \vdash P(n)$), but $T$ also proves that there is some natural number $k$ (necessarily non-standard) such that $P(k)$ does not hold.
A theory $T$ (as above) is ω-incomplete if, for some formula $P(x)$ in the language of $T$, $T$ proves $P(n)$, for every natural number $n$, but $T$ does not prove $∀x P(x)$ (i.e. $T \nvdash ∀x P(x)$).
Mauro ALLEGRANZA
- 94,169
-
3+1. A concrete example for the op: assuming PA is actually true, it is $\omega $-incomplete. Why? Well, for each new PA can prove that there is no contradiction in PA using at most n symbols, just by looking at each proof in PA using at most n symbols. But pa can't prove that this is true for all n, since then it would prove it's own consistency. Meanwhile, PA + "PA is inconsistent" is consistent but $\omega $-inconsistent. – Noah Schweber Nov 06 '16 at 16:54