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

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < August 10 ! width="25%" align="center"|<< Jul | August | Sep >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded 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. $\mathrm{\forall }x\mathrm{\forall }y((y=0)\vee (y>x)\vee \mathrm{\exists }z(x=y+z)\wedge \mathrm{\exists }m\mathrm{\exists }n((m<y)\wedge (x+m=y\cdot n)\left)\right)$, 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) + (${\mathrm{\Sigma }}_n$-induction) + (not ${\mathrm{\Sigma }}_{n+1}$-induction). Recall that PA is (Robinson Arithmetic) + (${\mathrm{\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) + (${\mathrm{\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 ${\mathrm{\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 ${\mathrm{\Sigma }}_1$-induction. It's known that ${\mathrm{\Sigma }}_2$-induction can prove that Ackermann's function is total, but ${\mathrm{\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 ${\mathrm{\Sigma }}_1$-induction, yet not in the system I've suggested. HOTmag (talk) 11:16, 11 August 2016 (UTC)