1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thannk you for your attention. Your explanation is so hard for me to understand. Please make it easier. $\endgroup$ – user87128 Jun 5 '14 at 15:42
  • 1
    $\begingroup$ I'm not really sure how to do that, short of doing an exposition as found in amazon.com/Computability-Logic-George-S-Boolos/dp/0521701465 . As far as I know these definitions are there to study the issues raised by the above facts. If you are not very familiar with these issues then the examples will not make any sense. $\endgroup$ – UserB1234 Jun 5 '14 at 16:06
  • $\begingroup$ Also how familiar are you with model theory / recursion theory and where did you run across these definitions? That might help me to better answer your question. $\endgroup$ – UserB1234 Jun 5 '14 at 16:08
  • $\begingroup$ Excuse me. At first I made a mistake, and I was careless. In fact your beautiful explanation resolve my problem. Thank you very much. $\endgroup$ – user87128 Jun 6 '14 at 14:17
4
$\begingroup$

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."

$\endgroup$
  • 1
    $\begingroup$ Thank you for your attention. But in the case of ω-incompleteness I still have problem. Your explanation is hard for me to understand. Please give a concrete example to show that PA is ω-incomplete. $\endgroup$ – user87128 Jun 5 '14 at 15:31
  • 2
    $\begingroup$ @aminliverpool I gave a concrete example. $E(x)$ is the formula expressing "$x$ is not the Gödel number of a proof of a contradiction in PA." $\endgroup$ – Andreas Blass Jun 5 '14 at 19:01
  • $\begingroup$ Ok. Excuse me for misunderstanding. Your example is concrete enough to understand. Thank you very much. $\endgroup$ – user87128 Jun 6 '14 at 14:11
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just one quick question: Wouldn't $\forall{n}, n=n$ follow as a result of the (sufficiently strong set of) logical axioms? $\endgroup$ – UserB1234 Jun 5 '14 at 15:04
  • $\begingroup$ How can you say that? I didn't say what the axioms are. Maybe $\lnot\forall n, n=n$ is itself an axiom. But to answer your question, no. It might follow, or it might not follow, or its negation might follow, depending on the axioms, so we have these terms “$\omega$-incomplete” and “$\omega$-inconsistent” to describe the situation when it doesn't follow, or when its negation follows. $\endgroup$ – MJD Jun 5 '14 at 15:07
  • $\begingroup$ @MJD I'm using the same line of reasoning as Mauro. $\endgroup$ – UserB1234 Jun 5 '14 at 15:11
  • $\begingroup$ Oh, I see. I intended $=$ here to represent a relation, not necessarily logical identity. Sorry for the confusion. I have changed the example. $\endgroup$ – MJD Jun 5 '14 at 15:12
  • 1
    $\begingroup$ @aminliverpool: The set of axioms that MJD is speaking about is not PA. Your original question doesn't mention PA, it mentions some set $K$ of axioms in some language. The only reason that PA came up so often in the other answers is because examples occur naturally there and has been well studied. In fact, with PA, using induction you can actually prove $\forall{n}, n\leq{n}$. $\endgroup$ – UserB1234 Jun 5 '14 at 16:13
1
$\begingroup$

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/ .

$\endgroup$
  • $\begingroup$ Thank you for your attention. Your notes are excellent. They are very useful for me to resolve my problem. Thank you very much. $\endgroup$ – user87128 Jun 6 '14 at 14:03
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your attention. Your example very good since it is intuitive and concrete for me. This help me to understand the concepts. Thank you very much. $\endgroup$ – user87128 Jun 6 '14 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy