Understanding ω-consistent and ω-incomplete theory

Question

A theory $K$ is said to be $ω$-consistent if, for every formula $B(x)$ of $K$, if $﹁ B(n)$ is a theorem in $K$ for every natural number $n$, then it is not the case that $(∃x)B(x)$ is a theorem in $K$.
A theory $K$ is said to be $ω$-incomplete if there is a formula $E(x)$ such that $E(n)$ is a theorem in K for every natural number $n$, but is not the case that $(∀x)E(x)$ is a theorem in $K$. These definition are not intuitive and concrete for me. Please help me.

Answer 1

This usually comes in to play for what are known as non-standard models of arithmetic.

For example, when we say let $n$ be a natural number, (informally) we mean that $n$ can be obtained by using the successor function on $0$ finitely many times. However by using compactness we can come with a model of arithmetic for which there is some $k$ s.t. $k>n$ for any "standard" (in the sense above) natural number $n$. In these models things do not work the way you would expect them to work.

If you know about Godel numbering and the incompleteness theorems, here is an example: Let $\sigma(n)$ be a formula that states $n$ witnesses the inconsistency of PA. Now since we believe in the consistency of PA, we have that for each standard natural number $n$. $\text{PA}\vdash\neg{\sigma(n)}$. But this is not enough to conclude that $\forall{n}\neg{\sigma(n)}$ is a consequence of PA. Thus PA is not $\omega$-complete.

Note that this isn't such a bad thing though. If PA was $\omega$-complete, then PA proves its own consistency and by the second incompleteness theorem, is actually inconsistent.

Answer 2

Here is an example. Suppose you are working in some system $M$, and you can prove all of these theorems:

$$\begin{align} 0 &\le 0 \\ 1 &\le 1 \\ 2 &\le 2 \\ &\vdots\end{align}$$

You might think that $M$ would also be able to prove $$(\forall n) n\le n\tag{1}$$ but depending on the axioms, maybe it can and maybe it can't. If it can't prove $(1)$, we say that $M$ is $\omega$-incomplete.

In fact, $M$ might even be able to prove the opposite of $(1)$, that $$\lnot(\forall n) n\le n.\tag{2}$$

If $M$ proves all of $0≤0, 1≤1, 2≤2,\ldots,$ and also $\lnot(\forall n) n \le n$, we say that $M$ is $\omega$-inconsistent. It's not actually inconsistent, but it is somewhat puzzling, because it asserts that there is some $n$ for which $\lnot (n\le n)$, but it also asserts that $n$ is not $0, 1, 2, $ or any other number.

Answer 3

It might be useful to observe that a model of an $\omega$-inconsistent theory cannot have just the standard natural numbers. The reason is that (in the notation of the question) the provability of $\exists x\, B(x)$ requires the model to have an element $a$ satisfying the predicate $B$, while the provability of $\neg B(n)$ for each standard natural number $n$ means that $a$ cannot be any such number.

On the other hand, $\omega$-incompleteness is not so damaging. Common axiomatic theories like Peano arithmetic and Zermelo-Fraenkel set theory are $\omega$-incomplete. For example, PA proves, for each natural number $n$, the statement that formalizes (in a natural way) "$n$ is not the Gödel number of a proof of a contradiction in PA". But, by Gödel's second incompleteness theorem, PA cannot prove the corresponding universally quantified sentence, as that sentence would say "PA is consistent."

Answer 4

It depends how much detail you want: but for a "concrete" explanation of why PA is $\omega$-consistent and $\omega$-incomplete, you could try Episode 9 of the (freely available) notes "Gödel Without Tears" available at http://www.logicmatters.net/igt/godel-without-tears/ .

Answer 5

Here is another answer. There and many propositions in number theory for example, where we can prove the theorem for specific values of $n$, but a general proof eludes us. Fermat's last theorem would have been an example 20 years ago, but for example the Goldbach conjecture, we can begin to prove it for all even numbers, $4=2+2, 6=3+3, 8=3+5, 10=3+7$ etc. But to prove $\forall n (2n =\text{prime}+ \text{prime})$ is unknown. Assume now for the sake of discussion that we somehow magically knew that every attempt to verify the statement for a specific $n$ would be successful. Does this imply we supply a proof of the general Goldbach conjecture, this is a question about the nature of our mathematical system. $\omega$-completeness says that we would have a general proof. Consider further the possibility that we could again verify Goldbach for every $n$ but we had a proof that Golbach was false. This would be a strange situation indeed. We have a system that is $\omega $-inconsistent. Not able to produce an actual contradiction (if we are consistent) but with a proof that there is a counterexample and unable to produce such a counterexample.

In logic we get an $\omega$-inconsistent theory by taking $T\cup \{\neg \text{con}(T)\}$ (assume $T$ consistent). This is a theory that thinks that it is inconsistent, as that is one of its axioms, but it is not it cannot actually produce a contradiction, it is $\omega$-inconsistent and in desperate need of psychotherapy.

Godel initially introduced $\omega$ consistence because his sentence "I cannot be proven" indeed cannot be proven, for if there were a proof that proof would itself be a counterexample. Say it was proof number $35$ the we have $$35 \text{is a proof}$$ but the Godel sentence is $$\forall n(n \text{is not a proof})$$ and this implies $$ 35 \text{is not a proof}$$ a direct contradiction.

On the other hand how do you know you cannot prove the negative of the Godel sentence ? That would be $$\exists n(n \text{is a proof})$$ now you cannot get a direct contradiction because you cannot find a proof. So again a strange situation which you can get out of by assuming $\omega$- consistency. Rosser later found a way to avoid the $\omega$-consistence assumption.