Wikipedia:Reference desk/Archives/Mathematics/2016 August 11

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 11

Peano Arithmetic: Are there propositions provable in PA, yet not in the following similar system?

I'm asking, because I'd like to replace the (first order) axiom of induction by a new axiom claiming that every positive number can - be subtracted from every bigger (or not smaller) number - and divide some number lying in the "immediate local neighborhood" of the bigger number, i.e. $\forall x\forall y{\Biggl (}(y=0)\lor (y>x)\lor \exists z(x=y+z)\land \exists m\exists n{\Bigl (}(m<y)\land (x+m=y\cdot n){\Bigr )}{\Biggr )}$, and I hope this new axiom is not weaker than the (first order) axiom of induction. HOTmag (talk) 09:43, 11 August 2016 (UTC)

Yes. First order PA is not finitely axiomatizable, which is why the axiom of induction is actually an axiom schema, necessarily.

I don't have a reference handy other than Simpson's book, but for every n there is a model of (Robinson Arithmetic) + ($\Sigma _{n}$-induction) + (not $\Sigma _{n+1}$-induction). Recall that PA is (Robinson Arithmetic) + ($\Sigma _{n}$-induction for all n). So consider A a putative finite axiomatization of PA. Since proofs are finite, A is provable from a finite fragment of the standard axiomatization of PA, which means that there's some n such that A is provable from (Robinson Arithmetic) + ($\Sigma _{n}$-induction). So there is a structure that models A but not PA, and thus A is not an axiomatization of PA.

So there is some n such that your axiom cannot prove $\Sigma _{n}$-induction. I suspect n is 1 or 2.--2406:E006:178C:1:781F:A651:32E2:B81E (talk) 10:20, 11 August 2016 (UTC)

I still wonder how such a proposition (unprovable in my axiom system) looks like. HOTmag (talk) 10:39, 11 August 2016 (UTC)

Okay. Your axiom can be proved with bounded induction, which is weaker than $\Sigma _{1}$-induction. It's known that $\Sigma _{2}$-induction can prove that Ackermann's function is total, but $\Sigma _{1}$-induction cannot. So this is a statement unprovable in your axiom system.--2406:E006:178C:1:781F:A651:32E2:B81E (talk) 10:51, 11 August 2016 (UTC)

All right. Now I wonder if there are propositions, provable in $\Sigma _{1}$-induction, yet not in the system I've suggested. HOTmag (talk) 11:16, 11 August 2016 (UTC)