Trying to understand ω-inconsistency

[andrewkirk]

I am trying to understand ω-inconsistency in order to appreciate some of the subtleties of Godel's incompleteness theorems. It seems to be such a weird and anti-intuitive concept.

Q1. Based on my reading, this is what I think it means, in the context of a theory T (in a language L) that includes the axioms of Robinson Arithmetic (I know the concept is probably more general than that, but that seems to be all that needs to be considered to understand the relevance of ω-inconsistency to Godel's two incompleteness theorems and the Godel-Rosser Theorem):

T is ω-inconsistent if there exists at least one well-formed L-formula φ, with one free variable, such that:
1. T⊢∃x:¬φ(x)
and
2. for every natural number n: T⊢φ(n)
where the underlining denotes the representation of the number n in L (eg as 0 preceded by n S's in Peano arithmetic.
Importantly,
3. T⊬∀x:φ(x),
otherwise 1 above would not be true. 2 above sounds a lot like T⊢∀x:φ(x), but isn't, because the 'for every' is not part of a formula in L. This is the bit that was tripping me up for a while.

Is that correct?

Q2. Is including the axiom schema of induction sufficient to make a consistent theory T ω-consistent?
By the axiom schema of induction I mean the set of formulas:
(\phi^x_0 \wedge (\phi\to\phi_{Sx}^{\ x}))\to\phi
for every well-formed L-formula \phi

It seems to me that it probably is, but I'm not certain.

If it is a sufficient condition, does that mean that any consistent theory that includes full Peano Arithmetic (by which I mean Robinson Arithmetic plus the axiom schema of induction) will be ω-consistent?

If not, is there an easily understandable counter-example? I am trying to imagine such a counter-example. It would have to be a theory in which there is a formula φ with one free variable, such that for every number n we can prove φ(n) within T, but for which there is no induction (or other) proof of ∀x:φ(x) as a theorem within T. If we have such a theory, we can then just add 1 above as an axiom and it is ω-inconsistent.

Q3. If the axiom schema is sufficient, is its inclusion also a necessary condition to make a consistent theory T ω-consistent?

I have a feeling that it's not, but it's no more than a feeling.

Thank you.

 

[Preno]

T is ω-inconsistent if there exists at least one well-formed L-formula φ, with one free variable, such that:
1. T⊢∃x:¬φ(x)
and
2. for every natural number n: T⊢φ(n)
where the underlining denotes the representation of the number n in L (eg as 0 preceded by n S's in Peano arithmetic.
Importantly,
3. T⊬∀x:φ(x),
otherwise 1 above would not be true. 2 above sounds a lot like T⊢∀x:φ(x), but isn't, because the 'for every' is not part of a formula in L. This is the bit that was tripping me up for a while.

Is that correct?

(3) is not part of the definition of ω-inconsistency - every inconsistent theory is trivially ω-inconsistent. Other than that, yes.

Q2. Is including the axiom schema of induction sufficient to make a consistent theory T ω-consistent?

No. If a formula of the form \exists x \varphi(x) is independent on T, i.e. if T \nvdash \exists x \varphi(x) and T \nvdash \neg \exists x \varphi(x), then adding it to T yields a consistent theory which is ω-inconsistent. In particular, PA + ~Con(PA) is consistent (assuming the consistency of PA) but ω-inconsistent.

 

[andrewkirk]

Thank you Preno. You have come to the rescue yet again!