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$ Feb 18, 2012 at 21:59
  • $\begingroup$ Wow. Reading GEB and had this question, and Immediately was able to find your question. Thank you :) $\endgroup$
    – user261214
    Sep 13, 2016 at 15:52

2 Answers 2


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.

  • $\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$ Feb 18, 2012 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$ Feb 18, 2012 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$ Feb 18, 2012 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$ Feb 19, 2012 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$
    – XXX
    Jul 9, 2020 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .