6
$\begingroup$

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

  • 0
    Wow. Reading GEB and had this question, and Immediately was able to find your question. Thank you :)2016-09-13

2 Answers 2

8

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.

  • 0
    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.2012-02-19
5

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.