After wikipedia:

Theory is $\omega$-inconsistent if, for some property P of natural numbers, T proves P(0), P(1), P(2), and so on (that is, for every standard natural number n, T proves that P(n) holds), but T also proves that there is some (necessarily nonstandard) natural number n such that P(n) fails. http://en.wikipedia.org/wiki/Omega-consistent

How I understand this is that those two sentences:
(1): $\forall_n P(n)$
(2): $\exists_n (not P(n)$
may be true at the same time and that does not lead to condtradiction. How is it possible?

Isn't proving second sentence not enought to prove that first one is false? In other words what is wrong with this proof:
$\exists_n P(n) \iff not~\forall_n(not~P(n))$ -- This is De Morgan's law
so $\exists_n (not P(n)) \iff not~\forall_nP(n)$ so last term is contradiction of (1).

  • 2
    $\begingroup$ All of $P(0)$, $P(1)$, $P(2)$ and so forth indefinitely together do not imply $\forall n P(n)$. A first order theory cannot express the fact that every $n$ is a natural number (i.e., given by some numeral), even if it is intended to be a theory of natural numbers. Also if one wanted to prove $\forall n P(n)$ based on the hypotheses $P(0)$, $P(1)$, $P(2)\ldots$, then one could use only finitely many of them (proofs are finite!), and those alone obviously do not suffice for the conclusion. $\endgroup$ – Marc van Leeuwen Feb 18 '12 at 21:59
  • $\begingroup$ Wow. Reading GEB and had this question, and Immediately was able to find your question. Thank you :) $\endgroup$ – Chandler Watson Sep 13 '16 at 15:52

Pay attention your mixing syntax with semantic.

A theory $T$ is $\omega$-inconsistent if exists a formula $P$ in the language of $T$ such that for every standard natural number $n \in \mathbb N$ the $T$ proves the formula $P(n)$ but it also prove the formula $\exists x \neg P(x)$.

The point is the you aren't quantifying over the whole universe of natural numbers of your theory but just on the standard ones: from the fact that for every standard natural number $n$ you can prove $T \vdash P(n)$ doesn't follow that you can also prove $T \vdash \forall n \ P(n)$, that's because it possibile that your theory $T$ include in its interpretation of arithmetic some non standard natural numbers.

Hope this help.

| cite | improve this answer | |
  • $\begingroup$ I much appreciate your answer it is very clear. Could you breifly explain what is the standard natural number or indicate some source -- I found one on wikipedia bu it presumes some knowledge about category theory? $\endgroup$ – Trismegistos Feb 18 '12 at 14:09
  • $\begingroup$ I don't find a reference right now, but standard natural numbers are what all mathematicians call the natural numbers, they are the element of the canonical model of Peano Arithmetic. If you're looking for a more formal and combinatorial description of such objects you can think of them as the closed terms of PA-language (or their interpretation in the language of $T$, if you are working in a interpretation of PA) build up from the constant $0$ via consecutive application of the 1-ary operation $s$ (successor). $\endgroup$ – Giorgio Mossa Feb 18 '12 at 14:29
  • $\begingroup$ Thanks. So not standard numbers will be some objects that theory T consider natural number but in fact it is not natural number of Peano Arithmetic? $\endgroup$ – Trismegistos Feb 18 '12 at 17:14
  • $\begingroup$ Not exactly. the point is that there are many different possible models of Peano Arithmetic (for Lowenheim-Skolem theorem), between this models there is a special model, which can be embedded in a necessarily unique way, this is the standard model of Peano, it is the model build up of natural numbers. Because this model can be embedded in every other model this means that every model of Peano Arithmetic has its version of standard natural numbers, all the others elements of the model are said non standard numbers. $\endgroup$ – Giorgio Mossa Feb 19 '12 at 17:43
  • $\begingroup$ @Trismegistos Consider PA added infinite axioms such that not x=0,not x=2......every finite sunset of it could be satisfied,so by the Compactness theorem there is a model of this theory which contains a number that will make for every standard natural number the T proves the formula P(n) but it also prove the formula ∃x¬P(x). $\endgroup$ – AnduinWilde Jul 9 at 5:59

In first order logic the theory $T$ proving $P(0)$, $P(1)$, etc. is not the same as $T$ proving $\forall n P(n)$. You might wish to read about nonstandard models of arithmetic.

Consider the theory $T^{*}$ which consists of $T$ together with the infinite collection of statements $0 < c$, $1 < c$, $2 < c$, etc. for every numeral $n$ you can write in the language of $T$. This set of axioms is just as consistent as $T$ because given a finite collection of these axioms there is a model of the axioms. The standard model is such a model. Interpret $c$ as as a number larger than any number that appears in the finite collection. But then, by the compactness theorem there is a model of the entire collection. It might be that $P(c)$ does not hold.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.