Some questions regarding some statements of Shoenfield.

134 Views Asked by At

Consider the system of arithmetic $\mathrm N$ found in Shoenfield's textbook Mathematical Logic:

N1. Sx$\neq$0,

N2. Sx=Sy$\rightarrow$x=y

N3. x+0=x

N4. x+Sy=S(x+y)

N5. x$\cdot$0=0

N6. x$\cdot$Sy=(x$\cdot$y)+x

N7. $\lnot$(x$\lt$0)

N8. x$\lt$Sy$\leftrightarrow$x$\lt$y $\lor$ x=y

N9. x$\lt$y $\lor$ x=y $\lor$ y$\lt$x

Now N1-N6 is just a subtheory of Robinson arithmetic and N7-N9 can be considered (?) inessential definitional axioms defining '$\lt$'. Note that the axiom $\forall$x(x$\ne$0$\rightarrow$$\exists$y(x=S(y))) of Robinson arithmetic was excluded from the list and for N1-N9 the universal quantifiers were (seemingly) excluded.

On page 51 of his book the following proof sketch of a finitary proof of the consistency of $\mathrm N$ can be found. It goes as follows:

"By combining the fact that $\mathfrak N$ [the standard model of $\mathrm N$ (see pg. 23 for the description)--my comment] is a model of $\mathrm N$ with the completeness theorem, we get a proof of the consistency of $\mathrm N$. We now indicate how we can convert this into a finitary proof of the consistency of $\mathrm N$. First we replace the individuals of $\mathfrak N$ by concrete objects. For this purpose, it suffices to replace the natural number $n$ by the expression containing $n$ strokes [and in so doing makes $\mathfrak N$ formulatable in the theory $TC$, making $TC$ the 'metatheory'--my comment]. Next we note that if we are given a variable-free term $\mathbf a$ or formula $\mathbf A$, we can actually compute $\mathfrak N$($\mathbf a$) or $\mathfrak N$($\mathbf A$). It follows that in certain cases, we can give a finitary proof that an open formula $\mathbf A$ of $\mathrm L$($\mathrm N$) is valid in $\mathfrak N$. In particular, we can prove that every instance of a non-logical axiom of $\mathrm N$ is valid in $\mathfrak N$. Now it is clearly impossible to have open formulas $\mathbf A_1$,...,$\mathbf A_n$ such that $\mathbf A_1$,...,$\mathbf A_n$, and $\lnot$$\mathbf A_1$ $\lor$$\cdot$$\cdot$$\cdot$$\lor$$\lnot$$\mathbf A_n$ are all valid in $\mathfrak N$; so by the consistency theorem, $\mathrm N$ is consistent."

Futhermore, on pp. 131-2, one has the following theorems:

$\mathbf Church's Theorem$: If $\mathrm T$ is a consistent extension of $\mathrm N$, then $\mathrm T$ is undecidable. (pg. 131)

$\mathbf Incompleteness$ $\mathrm Theorem$ ($\mathrm Goedel-Rosser$): If $\mathrm T$ is a consistent extension of $\mathrm N$, then $\mathrm T$ is not complete. (pg. 132)

Question: Is $\mathrm N$ just a version of Robinson arithmetic?

Question: Are all recursive functions representable in $\mathrm N$?

Question: If $\mathrm N$ is not equivalent to Robinson arithmetic, has it a name, and has it been studied (presumably it has)?

1

There are 1 best solutions below

9
On

You can find (quite) it into George Boolos & John Burgess & Richard Jeffrey, Computability and Logic (5th ed - 2007), Ch. 16.2 Minimal Arithmetic and Representability, page 207-on for details.

They use the subsystem of Robinson arithmetic called minimal arithmetic to prove that :

Every recursive function is representable in it.


Note

Instead of Shoenfield N9, they use :

(Q9) $ \ \ 0 < y ↔ y \ne 0$

(Q10) $ \ \ Sx < y ↔ (x < y \land y \ne Sx)$.