2
$\begingroup$

Is there any first order theory of arithmetic of the natural numbers that is known to be $\omega$-consistent if it is consistent?

If yes, then how?

$\endgroup$
  • 2
    $\begingroup$ $\omega$-consistency implies consistency. PA is $\omega$-consistent as is any theory that has the standard model $\Bbb{N}$ as a model. $\endgroup$ – Rob Arthan Sep 16 '17 at 23:10
  • $\begingroup$ I understand that. I'm asking if we can show that there exists a theory of arithmetic on $\mathbb{N}$ such that its consistency implies its $\omega$-consistency. Are you asserting that $\mathbb{N}$ exists and is consistent by fiat? If so, I'm asking basically is there any reason to believe arithmetic on $\mathbb{N}$ is indeed $\omega$-consistent. $\endgroup$ – oneq Sep 16 '17 at 23:13
  • 1
    $\begingroup$ The definition of $\omega$-consistency is contingent on the existence of $\Bbb{N}$. If you are trying to make some more subtle point in your question, please edit your question to clarify. $\endgroup$ – Rob Arthan Sep 16 '17 at 23:19
  • $\begingroup$ Ok, that answers my question. I was just wondering if there was any reason to believe any infinite theory is $\omega$-consistent, if one is not convinced of the existence of some true (intuitively $\omega$-consistent) arithmetic on $\mathbb{N}$. It appears then that the answer is no. Thanks for the help. $\endgroup$ – oneq Sep 16 '17 at 23:21
  • $\begingroup$ So basically one way the world could be is that all infinite theories are $\omega$-inconsistent, even if not all are inconsistent. That's what I was trying to figure out. $\endgroup$ – oneq Sep 16 '17 at 23:26
3
$\begingroup$

The empty theory over the language of arithmetic is certainly $\omega$-consistent.

This theory has the property that whenever it proves some formula $\phi$, you can replace every atomic formula $t_1=t_2$ by "true" and ignore all of the quantifiers, and the resulting Boolean expression will then evaluate to true. (Intuitively this is because the one-element universe is a model, but you can verify it purely syntactically one inference rule at a time).

Therefore it is impossible for the theory to prove both $\neg\phi(0)$ and $(\exists x)\,\phi(x)$, since the two Boolean expressions they translate to are each other's negations.


(This same argument also works for full Peano Arithmetic minus the axiom stating that $0$ is not a successor).

$\endgroup$
1
$\begingroup$

Let me add a fact that doesn't answer your question literally as stated, but may be interesting to you and other readers of this question: if you accept the axioms of ZFC, then pretty much any theory of arithmetic is $\omega$-consistent. Namely,

Theorem (ZFC). For any theory of arithmetic $\mathcal{T}$ such that $\mathbb{N} \vDash \mathcal{T}$, $\mathcal{T}$ is $\omega$-consistent.$^1$

Here "theory" means "set of axioms", and $\vDash$ is the satisfaction relation from model theory: $\mathcal{M} \vDash \mathcal{T}$ means that the structure $\mathcal{M}$ (in this case, natural numbers with addition, multiplication, etc.) satisfies all of the axioms $\mathcal{T}$.

Since pretty much any theory of $\mathbb{N}$ is supposed to start from true axioms, that is axioms we believe are actually true about $\mathbb{N}$, most such theories will be $\omega$-consistent. In particular:

Corollary. Assuming the axioms of ZFC, Peano Arithmetic (PA) and Robinson Arithmetic (RA) are $\omega$-consistent.

This may be a bit surprising! So what is the basis for these results? The theorem requires a strong meta-theory, in this case ZFC, in which we can develop all of model theory (in particular, in which we can define what a formula is, what a theory is, and what satisfaction $\vDash$ means). In such a meta-theory, there is also an object called $\mathbb{N}$, the natural numbers (in ZFC the existence of $\mathbb{N}$ is given as an axiom). Because such an object exists, we can then show that any correct theory (one that consists of axioms which are true about $\mathbb{N}$) is $\omega$-consistent.

If we do not get to assume strong meta-theory axioms like ZFC, but instead are wondering about the $\omega$-consistency of a theory like PA in a much weaker theory, then we may no longer be able to show that PA is $\omega$-consistent.


$^1$ Proof of the theorem: We proceed by contradiction: let $P(x)$ be a formula with one free variable, such that $\mathcal{T}$ proves (implies) $P(0)$, $P(1)$, and so on, but $\mathcal{T}$ also proves (implies) $\exists x. \lnot P(x)$.

Now since $\mathbb{N} \vDash \mathcal{T}$, $\mathbb{N} \vDash \varphi$ for any logical consequence (implication) $\varphi$ of the axioms $\mathcal{T}$. Therefore, $\mathbb{N} \vDash P(i)$ for all natural numbers $i \in \mathbb{N}$, and moreover, $\mathbb{N} \vDash \exists x. \lnot P(x)$. But these statements are in direct contradiction: by definition, the latter statement means that there exists some natural number $j$ such that $\mathbb{N} \vDash \lnot P(j)$, which is the exact opposite of the former statement. So we are done.

$\endgroup$

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.