2
$\begingroup$

(This question arose from a homework question which asked me to prove that (1st order) induction is independent from the other (1st order) Peano axioms)

Let $\mathcal{L}$ be the language of Peano arithmetic, i.e. with $0$ the only constant symbol, $+$, $\cdot$, and $S$ (the successor function) the only function symbols, and $=$ the only predicate symbol. Let $A$ be the theory in $\mathcal{L}$ whose axioms are the Peano axioms. Denote by $\overline{n}$ the term $S(S(\cdots S(0)\cdots))$, where $S$ is applied to $n$ times to $0$.

Next, extend $\mathcal{L}$ to a language $\mathcal{L}'$ with a single new constant symbol $\omega$. Let $A_1$ be $A$ extended to $\mathcal{L}'$, and set $$ A'=A_1\cup\{\overline{0}<\omega,\,\overline{1}<\omega,\,\overline{2}<\omega,\,\ldots\}.$$

$A'$ is consistent:

Let $T=A_1\cup\{\overline{i_1}<\omega,\,\overline{i_1}<\omega,\,\ldots,\overline{i_n}<\omega\}$, where $i_1,\ldots,i_n$ are natural numbers (if $n=0$, set $T=A_1$). Let $\mathbb{N}$ be the standard model of $A$. Then $\mathbb{N}$ may be interpreted as a model of $T$ by interpreting $\omega$ to be $\max\{i_0,\ldots,i_n\}+1$. Hence, $T$ is consistent. Thus, by the compactness theorem, $A'$ is consistent.

Question:

Let $M$ be a normal model of $A'$. Then $M$ is also an interpretation of $\mathcal{L}$, and all the axioms of $A$ are true in $M$ since they're also axioms of $A'$. So, $M$ is a model of $A$.

On the other hand, $\vdash_A x\neq0\Rightarrow (\exists y)(x=S(y))$. So, since $M$ is a model of $A$, it follows that $\models_M x\neq0\Rightarrow (\exists y)(x=S(y))$. So, $\omega\in M$ is the successor of some object in $M$. Repeating this, we get a sequence $$\omega>\omega-1>\omega-2>\cdots$$ in $M$ with no minimal element. But this contradicts the well ordering theorem, which is a theorem of $A$!

Where did I mess up?

$\endgroup$
  • $\begingroup$ You may want to be more precise: First order induction is part of the first order Peano axioms, so I doubt that you were asked to show independence (as it is false). Perhaps you mean that first order induction is independent from the other axioms? Even this is confusing, as first-order induction is an infinite list of statements. $\endgroup$ – Andrés E. Caicedo Oct 16 '13 at 23:12
  • $\begingroup$ Perhaps more relevant to the present question: What do you mean by a "normal" model? $\endgroup$ – Andrés E. Caicedo Oct 16 '13 at 23:13
  • $\begingroup$ Also, your title has issues: $\mathbb N$ is a structure, not a theory. How can you have models of a structure? What does it mean for a model to be inconsistent? For that matter, what does it mean for a model to be consistent? Consistency, after all, is a property of theories, not of structures. $\endgroup$ – Andrés E. Caicedo Oct 16 '13 at 23:15
  • 4
    $\begingroup$ The induction axiom scheme ensures that any non-empty definable subset of a model has a smallest element. A non-standard model is never well-ordered. $\endgroup$ – André Nicolas Oct 16 '13 at 23:16
  • $\begingroup$ The compactness argument you've given isn't quite right as it stands. You need to show that given any finite set of axioms $T \subseteq A'$, $\mathbb{N} \models T$. This is done pretty much in the way you suggest: clearly any $\varphi \in T \cap A_1$ is satisfied, so then let $\omega$ be the least natural number greater than those picked out by numerals in sentences of $T$. But you can't just pick some particular $T$ as it seems like you're doing currently: it must be an arbitrary finite subset of $A'$. $\endgroup$ – Benedict Eastaugh Oct 16 '13 at 23:18
4
$\begingroup$

Let $\varphi$ be a formula of our language, possibly extended to contain constant symbols for the elements of $M$. It is true in $M$ that if there is an $x$ such that $\varphi(x,m_1,m_2,\dots, m_k)$, then there is a smallest such $x$. However, the set that you described informally cannot be captured by any such $\varphi$: your argument is a proof of that.

$\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.