Re: On-line Godel book updated

Helene.Boucher_at_wanadoo.fr
Date: 03/20/05 

Date: 20 Mar 2005 13:45:15 -0800

Mitch Harris wrote:
> <Helene.Boucher@wanadoo.fr> wrote:
> >Mitch Harris wrote:
> >> <Helene.Boucher@wanadoo.fr> wrote:
> >> >Aatu Koskensilta wrote:
> >> >>
> >> >> What in Robinson arithmetic or Sigma_1-induction engenders
doubts?
> >> >
> >> >The Successor Axiom.
> >>
> >> Now that's just being contrary.
> >>
> >> Do you sincerely doubt it or are you just curious about the power
of
> >that
> >> specific axiom?
> >
> >Oh I sincerely and really doubt it. I don't doubt it to the extent
> >that I believe it is *not* true (at least not yet!). Rather I'm
just
> >agnostic.
> >
> >The other axioms of arithmetic tend to have an analytic flavor.
E.g.
> >in the Frege-Arithmetic-like formulation of the system of which I'm
> >speaking, one assumes "Something numbers 0 precisely when it is
> >equivalent to the empty set." That just seems to follow directly
from
> >the meaning of "0". The assertion of the existence of entities ad
> >infinitum (which is what the Successor Axiom does) seems clearly not
to
> >be analytic, so it would seem, irregardless of belief, the grounds
for
> >those beliefs are different and (although I won't try to clarify
this
> >assertion) less certain. Whatever the case, the Successor Axiom
seems
> >special.
>
> OK, I've lost the history of this conversation. 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. 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?
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. 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.

> 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. FPA is proof-equivalent to the
system F, which has as axioms:

(F1) (n)(m)(Nn & Mn,P & Mm,P => n = m)
(F2) (P)(M0,P <=> (x) ! Px)
(F3) (n)(m)(P)(Q)(a)(Nn & Sn,m & !Pa & (x)(Qx <=> Px v x = a) => (Mn,P
<=> Mm,Q))
(F4) Induction schema. From phi(0) and (n)(m)(Nn & Sn,m & phi(n)
=>
phi(m)) deduce (n)(Nn => phi(n)).

Here Mn,P means "P numbers n." That S is 1-1 can be proved from these
axioms. To deny the one-to-oneness of S, I think you would have to
deny either (F1) - the uniqueness of numbering - or (F3) - which seems
to be pretty minimal as an assumption.

>
> >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.

>
> >Even a theorem
> >which needs it per se can often be restated, often trivially, so
that
> >it is not needed.
>
> Really? what kinds of theorems? things like x + 0 = 0? (or whatever
the
> reverse order of the axiom for the base case for addition)

(x)(Nx => x + 0 = 0)

can be proved in FPA, so you don't need to restate it. The existence
and uniqueness of prime factorization, the Euclidean Algorithm, and
Quadratic Reciprocity can all be proved as is.

Commutativity of addition is an example which can be trivially
restated. One cannot prove:
(x)(y)(x + y = y + x)
because, given x and y, one cannot prove that x + y and y + x exist so
a fortiori that they are equal. But one can prove
(x)(y)(z)(x + y = z => y + x = z).
The second assumes the existence of x + y in its premise. Given that
assumption one can prove that y + x exists and indeed equals x + y.

>
> >If a theorem cannot be restated, even non-trivially,
> >that is if a theorem uses the Successor Axiom essentially, that
seems
> >to me to raise a red flag.
>
> What kinds of examples of this do you have? commutativity of
addition?

No, commutativity of addition, as I just said, can be trivially
restated. More like the Second Incompleteness Theorem (I think) and
the assertion that every consistent theory has a model.

>
> 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).

Anyway if you have any more questions, feel free !

Relevant Pages

  • Re: Successor Axiom: on what grounds TF?
    ... The Successor Axiom says that every ... > SuccAx a very natural assumption. ... of 0 that it numbers the empty set and nothing but the empty set seems ...
    (sci.logic)
  • Re: On-line Godel book updated
    ... >infinitum (which is what the Successor Axiom does) seems clearly not to ... That is definitely surprising. ... I really have a hard time imagining -any- arithmetic theorems (at least ...
    (sci.logic)
  • Re: Successor Axiom: on what grounds TF?
    ... Don't know if any interesting maths derives from these ... > for the Successor Axiom. ... > derived without assuming the Successor Axiom or its alternative. ... Therefore, forall naturals X, sucis a natural. ...
    (sci.logic)
  • Re: Successor Axiom: on what grounds TF?
    ... > the successor axiom, and what does that model have to do ... The models of PA minus the successor axiom are the intended model of PA ... usually write Mx,P etc. to emphasize this partialness.) ...
    (sci.logic)
  • Re: proof of (-1).a= -a
    ... Daniel W. Johnson wrote: ... > I suppose you also wouldn't see a problem with using commutativity to ... Or using the Axiom of Choice to prove the Axiom of ...
    (sci.math)