Prove that ever $\Sigma_0$ sentence is provable from PA (Peano Arithmetic, with exponentiation)

Question

I am trying to study the intuition and steps leading up to proving Godel's Incompleteness theorems. In a text I am studying it asserts that every true $\Sigma_0$ sentence is provable from PAE (where this system is the peano axioms with exponentiation). I am confused about how I get this fact; I don't know if it follows from constructing proof predicates or using Godel numbering in a similar way. Any help and guidance would be really appreciated. Thank you.

Answer 1

We want to prove that for all sentences $\psi \in \Sigma_0$, $\mathbb{N} \models \psi \implies PAE \vdash \psi$.

By completeness, it suffices to prove the following:

For all models $M$ of $PAE$ and for all sentences $\psi \in \Sigma_0$, $\mathbb{N} \models \psi \iff M \models \psi$.

Fix a model $M$ of $PAE$ and proceed by induction on the structure of $\psi$:

• $\psi$ atomic: $\mathbb{N}$ is a term (minimal) model of PAE, so there is an embedding $\mathbb{N} \to M$ given by $n \mapsto \bar n^M$. Embeddings preserve atomic formulas, and so $\mathbb{N} \models \psi \iff M \models \psi$.
• $\psi \equiv \chi \land \phi$: Since $\psi \in \Sigma_0$, $\chi ,\phi \in \Sigma_0$ and so this follows easily by the induction hypothesis.
• $\psi \equiv \lnot \chi$: Same idea
• $\psi \equiv \exists v \leq \bar n \chi(v)$: We have that $\mathbb{N} \models \psi \iff \mathbb{N} \models \lor_{m=0}^n \chi(\bar m) \iff M \models \lor_{m=0}^n \chi(\bar m)$ by the induction hypothesis as $\chi(\bar m)$ is a $\Sigma_0$ sentence. Finally, $M \models \lor_{m=0}^n \chi(\bar m) \implies M \models \psi$ trivially. For the other direction we have that since $M \models PAE$, $\{ m \in M : m\leq_M \bar n^M\}=\{\bar 0, \bar 1, ..., \bar n\}$ (Can you see why?). Therefore $M \models \psi \implies M\models \lor_{m=0}^n \chi(\bar m)$.

Hence if $\mathbb{N} \models \psi$, $M \models \psi$ for all models of $PAE$, so $PAE \models \psi$ and by completeness $PAE \vdash \psi$.