What do you get if you swap the second order induction axiom from full
second order arithmetic for the induction schema from Peano
Arithmetic? How much weaker is the resulting theory?

On May 11, 10:21 am, kleptomaniac6...@hotmail.com wrote:

If you have full comprehension but only first-order induction, the
resulting theory is conservative over Peano Arithmetic.

On 2008-05-11, in sci.logic, Rupert wrote:

That's true, but we can say something more interesting: full
second-order arithmetic is interpretable in the theory. For let N(x)
be the predicate

x is in all sets containing 0 and closed under the successor function

All of the axioms of second-order arithmetic are provable relativised
to N. From this (and the provability of it in second-order arithmetic)
it follows also that the conservativity result, while true, is not
provable in second-order arithmetic.

What would happen if you took from full second order arithmetic the
second order induction axiom, added the first order induction schema
from PA, then added all the first order arithmetic consequences of
second order arithmetic?

On 2008-05-11, in sci.logic, kleptomaniac666_@hotmail.com wrote:

You would get a theory T with the following properties

o Full second-order arithmetic is interpretable in T, and hence T is
equiconsistent with full second-order arithmetic. (The
interpretability of T in second-order arithmetic is trivial).

o Full second-order arithmetic is conservative over T for
arithmetical statements.

o The induction schema of T is superfluous; all instances are already
contained in the arithmetical consequences of second-order
arithmetic.

On May 11, 3:47 pm, Aatu Koskensilta
wrote:

On 2008-05-11, in sci.logic, kleptomaniac666_@hotmail.com wrote:

Just what I explained a few posts ago: there is a predicate N(x) in
the language of second-order arithmetic such that every axiom of
second-order arithmetic is provable in T when relativised to N.

The consistency of PA is an obvious example.

On May 10, 10:21 pm, kleptomaniac6...@hotmail.com wrote:

I do not at all approve of the line of answers you have been getting
to this so far.
You can't just say "the induction schema form Peano Arithmetic".
The mere fact that it HAS a schema means that Peano Arithmetic has
BOTH A FIRST AND A SECOND - order version.
"The induction schema from Peano Arithmetic" looks something like

[ phi(0) /\ Ax[phi(x)-->phi(s(x))] ] --> An[phi(n)] ]

Whether this is a 1st-order schema or a 2nd-order sentence
simply IS NOT something ANYone can TELL just from LOOKING at it.
It depends on context. It depends on what you are SUPPOSED TO DO with
phi. Phi is implicitly universally quantified IN BOTH THE FIRST AND
SECOND
order versions of this. At BOTH orders, this is being asserted FOR
ALL phi.
ANY legitimate instantation of phi will yield an axiom.

On May 11, 7:20 pm, Aatu Koskensilta
wrote:

On May 11, 8:17 pm, george cs.unc.edu> wrote: