$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.6: An Old Friend

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Back in Example 2.8.3 we introduced the collection of nonlogical axioms $$N$$. Just because they are so important, we'll reprint them here:

The Axioms of $$N$$

\begin{align} &1. \left( \forall x \right) \neg Sx = 0. \\ &2. \left( \forall x \right) \left( \forall y \right) \left[ Sx = Sy \rightarrow x = y \right]. \\ &3. \left( \forall x \right) x + 0 = x. \\ &4. \left( \forall x \right) \left( \forall y \right) x + Sy = S \left( x + y \right). \\ &5. \left( \forall x \right) x \cdot 0 = 0. \\ &6. \left( \forall x \right) \left( \forall y \right) x \cdot Sy = \left( x \cdot y \right) + x. \\ &7. \left( \forall x \right) xE0 = S0. \\ &8. \left( \forall x \right) \left( \forall y \right) xE \left( Sy \right) = \left( xEy \right) \cdot x. \\ &9. \left( \forall x \right) \neg x < 0. \\ &10. \left( \forall x \right) \left( \forall y \right) \left[ x < Sy \leftrightarrow \left( x < y \lor x = y \right) \right].\\ &11. \left( \forall x \right) \left( \forall y \right) \left[ \left( x < y \right) \lor \left( x = y \right) \lor \left( y < x \right) \right]. \end{align}

At that time (Lemma 2.8.4) we proved some things about the strength of this innocuous-looking set of axioms, for example, if the natural number $$a$$ is equal to the sum $$b + c$$, then $$N \vdash \bar{a} = \bar{b} + \bar{c}$$. We will need some further results about the strength of $$N$$ that will be proven in detail in Chapter 5. We state them here and give some examples.

Recall that we have defined the collections of $$\Delta$$-formulas as the formulas in the language of number theory that contain no unbounded quantifiers. For a specific example, consider $$\phi \left( x \right)$$, the formula with one free variable

$\phi \left( x \right) : \equiv \left( \exists y \leq x \right) \bar{2} y = x$

which states that $$x$$ is an even number. Suppose that we consider two different sentences associated with $$\phi : \phi \left( \bar{2} \right)$$ and $$\phi \left( \bar{3} \right)$$. We will all agree that $$\phi \left( \bar{2} \right)$$ is a true statement about $$\mathfrak{N}$$, while $$\phi \left( \bar{3} \right)$$ is false. What is so wonderful about our set of non-logical axioms $$N$$ is that $$N$$ is strong enough to prove the first statement and refute the second:

$N \vdash \phi \left( \bar{2} \right) \: \: \: \: \: \: \: \: \: \: N \vdash \neg \phi \left( \bar{3} \right)$

This is a general fact about the relation between $$\Delta$$-formulas and $$N$$, which we will state here and prove as Proposition 5.3.14:

Proposition 4.6.1.

If $$\phi \left( \underset{\sim}{x} \right)$$ is a $$\Delta$$-formula with free variables $$\underset{\sim}{x}$$, if $$\underset{\sim}{t}$$ are variable-free terms, and if $$\mathfrak{N} \models \phi \left( \underset{\sim}{t} \right)$$, then $$N \vdash \phi \left( \underset{\sim}{t} \right)$$. If, on the other hand, $$\mathfrak{N} \models \neg \phi \left( \underset{\sim}{t} \right)$$, then $$N \vdash \neg \phi \left( \underset{\sim}{t} \right)$$.

If we allow an unbounded existential quantifier, the situation changes slightly. Our set of axioms $$N$$ is strong enough to prove the true $$\Sigma$$-sentences, but it cannot refute the false $$\Sigma$$-sentences. This result, called $$\Sigma$$-completeness, will be proven as Proposition 5.3.13:

proposition 4.6.2.

If $$\phi \left( \underset{\sim}{x} \right)$$ is a $$\Sigma$$-formula with free variables $$\underset{\sim}{x}$$, if $$\underset{\sim}{t}$$ are variable-free terms, and if $$\mathfrak{N} \models \phi \left( \underset{\sim}{t} \right)$$, then $$N \vdash \phi \left( \underset{\sim}{t} \right)$$.

At one level, this should not be too surprising, given that $$N$$ is strong enough to prove or refute sentences that have no unbounded quantifiers. Suppose that $$\phi$$ is a true $$\Sigma$$-sentence. Then $$\phi$$ look (roughly) like $$\exists x \psi \left( x \right)$$, where $$\psi$$ has one free variable. Since $$\exists x \psi \left( x \right)$$ is true in $$\mathfrak{N}$$, then there is some natural number $$k$$ such that $$\psi \left( k \right)$$ is true. But then $$\psi \left( \bar{k} \right)$$ is a true-in-$$\mathfrak{N}$$ sentence with no unbounded quantifiers. By assumption, $$N$$ is strong enough to prove $$\psi \left( \bar{k} \right)$$, and so by the usual rules of logic, $$N$$ also proves $$\exists x \psi \left( x \right)$$; i.e., $$N$$ proves $$\phi$$.

On the other hand, if our $$\Sigma$$-sentence $$\phi$$ is false in $$\mathfrak{N}$$, that just means that there is no natural number $$k$$ such that $$\psi \left( k \right)$$ is true. Now, since $$\psi \left( \bar{k} \right)$$ has no unbounded quantifiers, by assumption that means that $$N \vdash \neg \psi \left( \bar{k} \right)$$ for every natural number $$k$$. But we have already seen that there are lots of structures of non-standard arithmetic where a property can be false of every natural number but still true of some other element of the universe. So just because $$N$$ can prove that $$\psi$$ is false of every natural number, there is no reason a priori to assume that $$N$$ can then prove that $$\psi$$ is false of everything. And in fact, it cannot.

So, the short version:

$$N$$ is strong enough to prove true $$\Sigma$$-sentences, but not strong enough to refute false $$\Sigma$$-sentences.

Equivalently, since the denial of a $$\Sigma$$-sentences is equivalent to a $$\Pi$$-sentence:

$$N$$ is strong enough to prove every true $$\Sigma$$-sentence, but not strong enough to prove every true $$\Pi$$-sentence.

For example, consider the Goldbach Conjecture, which states that every even number greater than two can be written as the sum of two primes. It is not difficult to see that the Goldbach Conjecture can be written formally as a $$\Pi$$-sentence, but unfortunately we currently do not know whether the Goldbach Conjecture is true or not. Suppose for a second that the conjecture was false. Then its denial, equivalent to a $$\Sigma$$-sentence, would be true, and therefore $$N$$ would be able to prove the denial. Not surprising, really. All we would have to do is find an even number that is a counterexample to the Goldbach Conjecture and check that it isn't the sum of two primes. (Warning: If you're going to start looking for the counterexample, go big or go home. The conjecture has been verified for all even numbers up to at least $$4 \times 10^{18}$$.)

On the other hand, if the Goldbach Conjecture is true, then there is no reason to believe that $$N$$ is strong enough to prove that fact. Which, by the way, means that if we could prove that $$N$$ is not strong enough to decide the Goldbach Conjecture, then the Goldbach Conjecture is true!