Prove that, for any $\Delta_0$ sentence $\sigma$, QE$\models \sigma \leftrightarrow \sigma$ is true in $\eta$

Question

A formula $\varphi$ of $L^A$ is $\Delta _0$ if $\varphi$ belongs to the smallest set containing the atomic formulas and closed under negation, forming conditionals, and bounded quantification. Closure of $\Delta _0$ under forming conditionals means that if $\varphi$ and $\psi$ are $\Delta _0$ then so is $(\varphi \to \psi)$. Closure of $\Delta _0$ under bounded quantification means that if $\psi$ is $\Delta _0$ then both $\forall x(x<t \to \psi )$ and $\forall x(x\leq t \to \psi )$ are $\Delta_0$ for any term t not containing x.

Prove that, for any $\Delta_0$ sentence $\sigma$, QE$\models \sigma \leftrightarrow \sigma$ is true in $\eta$

For the material I learned, $L^A$ is the language of arithmetic: {$0,S,<,+,\cdot$}.
$\eta$ is the standard model of arithmetic: {$N,0,S,<,+,\cdot$}.
QE consists of 8 axioms:
1) $0\neq Sv_0$ 2) $Sv_0=Sv_1 \to v_0=v_1$ 3) $v_0 \nless 0$ 4) $v_0<Sv_1 \to v_0 \leq v_1$
5) $v_0+0=v_0$ 6) $v_0+Sv_1=S(v_0+v_1)$ 7) $v_0 \cdot 0=0$ 8) $v_0\cdot Sv_1=v_0\cdot v_1+v_0$

For this question I used induction on length, so I suppose any $\Delta_0$ sentences shorter than $\sigma$ has this property and tries to prove that $\sigma$ also has this property for every form. I have already done the atomic cases and the negation case. But for the other cases I don't know how to deal with them. For example is $\sigma$ is $\varphi \to \psi$ for some term $\varphi$ and $\psi$, I'm not sure if $\varphi$ and $\psi$ have to be $\Delta_0$ and get stucked.

I think I don't understand this part well. Very appreciated for any help.

Answer 1

You have to prove that for every $\Delta_0$ sentence $\sigma$ :

$QE \vDash \sigma$ iff $\sigma$ is true in $\mathcal N$,

where $\mathcal N$ is the standard model of arithmetic.

Due to the Completeness Theorem for first-order logic, $QE \vDash \sigma$ is equivalent to : $QE \vdash \sigma$.

I'll refer to George Boolos & John Burgess & Richard Jeffrey, Computability and Logic (5th ed - 2007).

The $QE$ axiom system is a subset of BBJ's minimal arithmetic $Q$ [see page 208].

The $\Delta_0$ sentences are called by BBJ rudimentary [see page 204] :

By a rudimentary formula of the language of arithmetic we mean a formula built up from atomic formulas using only negation, conjunction, disjunction, and bounded quantifications $∀x < t$ and $∃x < t$, where $t$ may be any term of the language (not involving $x$). (Conditionals and biconditionals are allowed, too, since these officially are just abbreviations for certain constructions involving negation, conjunction, and disjunction. So are the bounded quantifiers $∀x ≤ t$ and $∃x ≤ t$, since these are equivalent to $∀x < St$ and $∃x < St$).

Your result is :

16.13 Theorem. An $∃$-rudimentary sentence [see page 204 : by an $∃$-rudimentary formula we mean a formula of form $∃xF$ where $F$ is rudimentary] is correct [see page 199 : we now abbreviate ‘true in the standard interpretation’ to correct] if and only if it is a theorem of $Q$ [page 208].

Thus, we have to adapt the proof of the above theorem to the system $QE$ (subsystem of $Q$) and to the class $\Delta_0$ (i.e.we have to exclude the existentially quantifier case).

Proof : Since every axiom of $QE$ is correct, so is every theorem of $QE$, and hence any $\Delta_0$ sentence provable from the axioms of $Q$ is correct.

All the work will go into proving the converse. To begin with zero and sucessor, for any natural number $m$, of course $\overline m = \overline m$ (where $\overline m$ is as always the numeral for $m$, that is, is the term $0...$ preceded by $m$ $S$) is provable even without any axioms, by pure logic.

All of $0 \ne 1, 0 \ne 2, 0 \ne 3,...$ are provable by 1) (since the numerals 1, 2, 3, . . . all begin with $S$). Then $1=2 → 0=1, 1=3 → 0=2, . . .$ are provable using 2), and since $0 \ne 1, 0 \ne 2, . . .$ are provable, it follows by pure logic that $1 \ne 2, 1 \ne 3, . . .$ , are provable.

Then $2=3 → 1=2, 2=4 → 1=3, . . .$ are provable, again using 2), and since $1 \ne 2, 1 \ne 3, . . .$ , are provable, it follows by pure logic that $2 \ne 3, 2 \ne 4, . . .$ are provable. Continuing in the same way, if $m < n$, then $\overline m \ne \overline n$ is provable.

It follows by pure logic (the symmetry of identity) that if $m < n$, then $\overline n \ne \overline m$ is provable also. Since in general if $m \ne n$ we have either $m < n$ or $n < m$, it follows that if $m \ne n$ then both $\overline m \ne \overline n$ and $\overline n \ne \overline m$ are provable.

The poof goes on for a full page considering more complex cases and concluding with :

Thus all correct closed atomic and negated atomic sentences are provable. Now we move beyond atomic and negation-atomic sentences. [...] Since all correct atomic and negated atomic closed sentences are provable, so are all correct sentences of types $\lnot \sigma, \lnot \lnot \sigma, \sigma_1 \land \sigma_2, \lnot (\sigma_1 \land \sigma_2), \sigma_1 \lor \sigma_2, \lnot(\sigma_1 \lor \sigma_2)$, where $\sigma, \sigma_1, \sigma_2$ are atomic or negated atomic sentences. Continuing in this way, all correct closed formulas built up from atomic formulas by negation, conjunction, and disjunction are provable: All correct closed formulas without quantifiers are provable.

Then the bounded quantifiers are considered :

Thus any bounded universal or existential quantification of formulas without quantifiers can be proved equivalent to a conjunction or disjunction of sentences without quantifiers, which is of course itself then a sentence without quantifiers, so that we already know it can be proved if it is correct. Thus any correct sentence obtained by applying bounded universal or existential quantification to formulas without quantifiers is provable, and repeating the argument, so is any correct sentence built up from atomic formulas using negation, conjunction, disjunction, and bounded universal and bounded existential quantification: Any correct $\Delta_0$ [i.e.rudimentary] sentence is provable.

Finally, the proof consider the case of a correct $∃$-rudimentary sentence $∃xA(x)$, which is not in the scope of your theorem.