Re: doubting successor

From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 03/21/05 

Date: Mon, 21 Mar 2005 11:26:51 +0100

Helene.Boucher@wanadoo.fr wrote:
> Mitch Harris wrote:

<stuff about doubting some axiom of PA

>>What is it exactly that
>>you consider the successor axiom? Is it the Peano axiom "if x is a
>>number then x+1 is a number too"?
>
> Yes, almost, well anyway here's a long answer.
>
> Second-order PA contains these axioms/schema:
> (PA1) N0
> (PA2) (n)(m)(Nn & Sn,m => Nm)
> (PA3) (n)(Nn => [m] Sn,m)
> (PA4) (n)(m)(m')(Nn & Sn,m & Sn,m' => m = m')
> (PA5) (n)(m)(n')(Nn & Nn' & Sn,m & Sn',m => n = n')
> (PA6) (n)(Nn => ! Sn,0)
> (PA7) Induction schema. From phi(0) and (n)(m)(Nn & Sn,m & phi(n)
> =>
> phi(m)) deduce (n)(Nn => phi(n))
>
> Note: [m] means "there exists m".
>
> (PA2) seems to be the axiom you are asking about - I don't think it has
> a name. The successor axiom is (PA3). In any case, while it's the
> Successor Axiom for which I have doubts, to be precise, the system that
> I am talking about is FPA = (PA4) + (PA5) + (PA6) + (PA7). While I
> have doubts about the Successor Axiom, the other two axioms are just
> rarely needed so I leave them out to make the technical results
> stronger.
>
>>If you're in a doubting mood, I would expect
>>more energy would be more profitably spent in doubting the induction axiom.
>
> The cynical answer is that has already been done.

OK, that's what I expected.

> The longer - and
> correct - answer is that I don't see any problem with the induction
> axiom. If a property is true of 0 and it's true of every successor of
> a natural number, then it's true of all numbers. That's obvious, no?

No, not obvious at all (to me). Or rather, PA7 is much less obvious
than PA2+PA3, if anything by virtue of its 2nd-orderedness.

Anyway, couldn't one formally show that PA2+PA3 are somehow a specific
case of PA7?

> If there were no numbers, or if 0 were the only number, or if 0 and 1
> were the only numbers, etc. then induction is valid. You can just
> check it.

What about induction over infinite sets?

> On the other hand, the assertion of the existence of lots
> and lots of number, stretching on ad infinitum, well (to be brief) that
> can't be checked and strikes me as less sure.

One could use the same (intuitive) argument against PA6.
Hypothetically, how can you be sure there isn't some number out there
that annoyingly has 0 as its successsor?

This all seems more of an indictment of the "forall" operator or
infinity rather than the particular axioms.

>>or if that is just too obviously "difficult", then what about
>>the axiom about successor being one-to-one?
>
>
> Since I thnk the successor relationship mirrors our counting, I don't
> think I could make sense of this.

I was referring to what corresponds to your PA5, I think.

...

>>>Moreover, the Successor Axiom is not needed for a surprisingly amount
>>>of mathematics (anyway, it was surprising to me!).
>>
>>That is definitely surprising. Do you have any references for these kinds
>>of results?
>
> Probably the best paper is (sorry, it's mine);
>
> http://www.andrewboucher.com/papers/consistency.pdf
>
> It uses F as the base theory, not FPA, so either you'll have to take my
> word they are proof-theoretically equivalent, or look at another paper
> which is:
>
> http://www.andrewboucher.com/papers/equivalence.pdf
>
> In any case the important thing about the systems FPA or F is that,
> given any number n, you can prove that all numbers less than n exist.
> But they cannot prove, given a natural number n, that numbers greater
> than n exist.

Really? PA2 doesn't do that?

>>I really have a hard time imagining -any- arithmetic theorems (at least
>>those requiring induction) that don't require that the successor of
>>number x must also be a number.
>
> Commutavity of addition is pretty easy. Define addition +(x,y,z)
> to be
> (there exists P, Q,R s.t. Mx,P & My,Q & Mz,R & (P union Q) = R &
> (P intersect Q) = empty set).
>
> It's then simple logic to show that +(x,y,z) implies +(y,x,z).

OK, I see what kinds of transformations you're doing.

But this makes me have -more- confidence that PA2/PA3 are -true-.
Since you can prove lots of the same things with it as well as
without... hmm... have you looked into to what would happen if you
-deny- your successor axiom? That would tell you lots more.

By the way, (pardon me if this has been already discussed) but why is
your email address different from what appears to be your given name?
It looks like you are impersonating a relative. 

-- 
Mitch Harris
(remove q to reply)

Relevant Pages

  • Re: Cantor and the binary tree
    ... the induction axiom quite definitely stated ... >>> finite successor), exhausts the naturals. ... >> maintain a property of finiteness over an infinite range of numbers ... Just because I am not adhering to your pet axiom set ...
    (sci.math)
  • Re: Galileos Paradox and the Project of the Reals
    ... too many times already exactly what the axiom of infinity is. ... There is no general definition of 'one after' in set theory, ... That's how successor rests on "<". ...
    (sci.math)
  • Re: ZFC in another shape.
    ... The successor is x is x union. ... x is the successor of d (mentioned in axiom 3). ... case your theory is equivalent to ZFC without the union axiom. ...
    (sci.math)
  • Re: Galileos Paradox and the Project of the Reals
    ... It is a CONSEQUENCE of the axiom of infinity that there are certain ... Is an inductive successor set ordered? ... get a decent set theory textbook already! ...
    (sci.math)
  • Re: Why Regularity?
    ... set is a member of itself it will be either x or x'. ... First he said the successor of U was ... By axiom of Pairing if x is a set, y is a set, so is ... You are saying big statements without giving any proof for what you are ...
    (sci.math)
Quantcast