next up previous
Up: Factasia Logic

On Complete $\omega$-Consistent Theories of Arithmetic

R.D. Arthan
rda@lemma-one.com

Abstract:

In connection with some philosophical concerns, Roger Bishop Jones has conjectured, in effect, that the set of theorems of every complete $\omega$-consistent first-order theory in the language of Peano Arithmetic is the set of all formulae that are true in the standard model of arithmetic. This note provides a proof of this conjecture. The proof turns out to be quite straightforward and so the result is doubtless well-known to experts in the field.

1. Notation and Terminology

We assume known the basic concepts of first-order logic as described in introductory text books on the subject such as Elliot Mendelson's ``Introduction to Mathematical Logic''. We use the following notation:

$\mbox{{\sf L}}= \mbox{{\sf L}}_{\mbox{{\sf PA}}}$ is the language of first-order Peano arithmetic ( $\mbox{{\sf PA}}$).
$\mathbb{N} $ is the set of natural numbers of day-to-day thought. Augmented with the usual operations of addition, multiplication and so on, $\mathbb{N} $ provides the standard model of theories such as $\mbox{{\sf PA}}$.
$K$ is some theory (set of axioms) in the language $\mbox{{\sf L}}$
$\vdash_K S$ means that the theory $K$ entails the formula $S$ of $L$ by the usual rules of first-order logic.
$\vDash_{\mathbb{N} } S$ means that the formula $S$ of $\mbox{{\sf L}}$ is true in the standard model of $\mbox{{\sf PA}}$.
$\overline{i}$ where $i$ is a natural number denotes the representation in $\mbox{{\sf L}}$ of $i$ ( $0^{' \ldots'}$ with $i$ dashes).
$S[t_1/x_1, ..., t_n/x_n]$ where $S$ is any formula of $\mbox{{\sf L}}$, where the $t_i$ are terms of $\mbox{{\sf L}}$, and where the $x_i$ are variables, denotes the result of simultaneously substituting $t_i$ for $x_i$ in $S$, taking care to avoid variable capture.

We say $K$ is ground-complete1 iff. $K$ proves every ground formula that is true in the standard model. Here by ``ground formula'' we mean a formula containing no variables (and so, in particular, no quantifiers). Intuitively, a ground-complete theory is one that ``knows its tables'': it can derive any formula of $L$ whose truth follows purely by dint of arithmetic calculation on particular natural numbers. A ground-complete theory need not be consistent, but a ground-complete theory that is consistent cannot prove a false ground formula (this is a special case of lemma 1 below). Ground-completeness is enjoyed by $\mbox{{\sf PA}}$ and by many weaker theories such as Robinson's system $\mbox{{\sf Q}}$.

As usual, $K$ is consistent iff. there is a formula $S$ such that $\not\vdash_K S$, or, equivalently, iff. there is no formula $S$ for which both $\vdash_K S$ and $\vdash_K \neg S$; $K$ is $\omega$-consistent iff. whenever $\vdash_K \exists x \bullet S$ for some formula $S$, there is at least one natural number, $i$, for which $\not\vdash_K \neg S[\overline{i}/x]$. $K$ is complete if for every formula $S$, either $\vdash_K S$ or $\vdash_K \neg S$.

An $\omega$-consistent theory is certainly consistent: if $K$ is $\omega$-consistent and $S$ is any formula, then either $\not\vdash_K \exists x \bullet S$ or for some natural number, $i$, $\not\vdash_K \neg S[\overline{i}/x]$, so there is at least one formula that $K$ does not prove.

2. The Proof

Lemma 1   If $K$ is consistent and ground-complete, then every quantifier-free formula that $K$ proves is true in the standard model. I.e., If $S$ in $L$ is quantifier-free and $\vdash_K S$, then $\vDash_{\mathbb{N} } S$.

Proof: Let $S$ be a quantifier-free formula such that $\vdash_K S$ and let $x_1, \ldots, x_n$ be the variables that appear free in $S$ (possibly $n = 0$, in which case $S$ is a ground formula). By first-order logic, $\vdash_K \forall x_1 \bullet \ldots \forall x_n \bullet S$. Now $S$ is true in a model iff. its universal closure is. So assume for a contradiction that $\not\vDash_{\mathbb{N} } \forall x_1 \bullet \ldots \forall x_n \bullet S$. Then for some natural numbers, $i_1, \ldots, i_n$, we must have $\vDash_{\mathbb{N} } \neg S[\overline{i_1}/x_1, \ldots, \overline{i_n}/x_n]$. But $\neg S[\overline{i_1}/x_1, \ldots, \overline{i_n}/x_n]$ is a ground formula, and so by ground-completeness, $K$ proves it. Thus $\vdash_K \forall x_1 \bullet \ldots \forall x_n \bullet S$and $\vdash_K \neg S[\overline{i_1}/x_1, \ldots, \overline{i_n}/x_n]$contradicting the assumed consistency of $K$.

Lemma 2   If $K$ is $\omega$-consistent, ground-complete, and complete, then every formula that $K$ proves is true in the standard model. I.e., for any formula $S$ in $L$, if $\vdash_K S$, then $\vDash_{\mathbb{N} } S$.

Proof: Assume $\vdash_K S$. We can assume without loss of generality that $S$ is in prenex normal form. Let us proceed by induction on the length of the prefix of $S$.

Since a prenex formula with a prefix of length $0$ is quantifier-free and, as remarked above, $\omega$-consistent theories are consistent, the base case is given by lemma 1.

There are two cases for the inductive step: (a), $S$ has the form $\forall x\bullet P$ or, (b), $S$ has the form $\exists x\bullet P$, where, in either case, $P$ has a shorter prefix than $S$, so that the inductive hypothesis applies to $P$. I.e., if $\vdash_K P$, then $\vDash_{\mathbb{N} } P$.

In case (a), from our assumptions, $\vdash_K S$, and so, by first-order logic, $\vdash_K P$, since $S$ is $\forall x\bullet P$. By the inductive hypothesis $\vDash_{\mathbb{N} } P$. But $P$ is true in a model iff. its universal closure is; so $\vDash_{\mathbb{N} } \forall x \bullet P$, i.e., $\vDash_{\mathbb{N} } S$ as required to complete the inductive step for case (a).

In case (b), $S$ has the form $\exists x\bullet P$ and, by assumption, $\vdash_K S$, i.e., $\vdash_K \exists x \bullet P$. By $\omega$-consistency, for some natural number $i$, $\not\vdash_K \neg P[\overline{i}/x]$. But then, by the completeness of $K$, $\vdash_K P[\overline{i}/x]$. By the inductive hypothesis, this implies that $\vDash_{\mathbb{N} } P[\overline{i}/x]$, whence $\vDash_{\mathbb{N} } \exists x\bullet P$, i.e. we may conclude that $\vDash_{\mathbb{N} } S$ as required to complete the inductive step for case (b) and hence the proof of the lemma.

Theorem 1   If $K$ is $\omega$-consistent, ground-complete, and complete, then $K$ decides truth in the standard model. I.e., for any formula $S$, $\vdash_K S$ iff. $\vDash_{\mathbb{N} } S$.

Proof: The left-to-right direction is lemma 2. As for the right-to-left direction, if $\vDash_{\mathbb{N} } S$, then by the completeness of $K$, either $\vdash_K S$ or $\vdash_K \neg S$, but the latter case would imply $\vDash_{\mathbb{N} } \neg S$ by lemma 2, leading to a contradiction, so $\vdash_K S$ as required.

Theorem 2   The deductive closure of any $\omega$-consistent and complete extension of $\mbox{{\sf PA}}$ is precisely the set of all formulae that are true in the standard model for $\mbox{{\sf PA}}$.

Proof: As we have already remarked, $\mbox{{\sf PA}}$, and so any extension of $\mbox{{\sf PA}}$, is ground-complete, so theorem 1 applies to complete the proof.

3. Conclusions

The philosophic interest stemmed inter alia from the observation that $\omega$-consistency denies the possibility of a theory of arithmetic making false claims about the consistency of $\mbox{{\sf PA}}$. We have shown that, a complete $\omega$-consistent theory extending $\mbox{{\sf PA}}$ must admit the standard model and so makes no false claims at all, as Roger Jones expected.

Our arguments have made unashamed use of the notion of the natural numbers as a given; however, our ontological demands are really very modest and our means are no more demanding than our ends: if first-order logic is to be admitted as a topic of philosophical study, then we must admit consideration of at least one countably infinite set, namely the language of the first-order theory in question. The only coherent way to reject theorem 2 is to deny the law of the excluded middle and so claim that both its statement and its proof are meaningless. If one admits classical first-order logic as offering a road to philosophical truth, then one must accept the theorem and read it as saying that there is exactly one $\omega$-consistent and complete extension of Peano arithmetic.


Subsections
next up previous
Up: Factasia Logic

1999-08-31