Re: Question about induction

Aatu Koskensilta <aatu.koskensi...@xxxxxx> wrote:
Bill Dubuque <w...@xxxxxxxxxxxxxxxxxxxx> writes:
Aatu Koskensilta <aatu.koskensi...@xxxxxx> wrote:

The least number principle and the principle of mathematical
induction are (classically) equivalent.

That's far too informal to make any sense.

Why?

Because this is sci.math, not sci.logic. Most readers here have
not taken a course in mathematical logic. Rather, they practice
their logic - like their set theory - fairly naively. As such
what may seem trivial to you or I may not be so for them.

Can you state a more formal version that is actually true?

Consider the theory T in the second-order language of arithmetic with

(x)(x = 0 \/ (Ey)(x = S(y)))
~(Ex)(S(x) = 0)
(x)(y)(S(x) = S(y) --> x = y)

and the comprehension schema as axioms. The least number principle and
the principle of mathematical induction are provably equivalent in T.

Ok, you've added the axiom that every nonzero element is a successor
(which is not included in Peano's axioms since it is a consequence
of them). When replacing induction with the minimum principle (or
any other such principle that holds for all ordinals) one needs to
adjoin some such axiom that serves to restrict down to omega. That's
the point that I want to emphasize here for the logical layperson.

--Bill Dubuque
.

Relevant Pages

  • Re: infinitely many nns = infinite nns?
    ... What is wrong with Phil studying set theory? ... I'll agree but with one caveat: Phil wants to prove induction, ... or actual infinity would LEGITIMATELY arise. ... Since I presented those axioms 4 times and Phil ...
    (sci.logic)
  • Re: Well Ordering the Reals
    ... >>>Induction is stated axiomatically by Peano and used without regard to the ... then there must be some principle of set theory ... of the set of natural numbers and the axioms of set theory. ... > According to the inductive axiom, but the naturals are not *defined* to be ...
    (sci.math)
  • Re: Question about induction
    ... induction are equivalent. ... their logic - like their set theory - fairly naively. ... and the comprehension schema as axioms. ... the principle of mathematical induction are provably equivalent in T. ...
    (sci.math)
  • Re: A recursion axiom for N?
    ... needs a stronger version of induction to do so." ... it, "It's valid using some basic axioms of set theory, or some basic ... recursion is defined in this system, ...
    (sci.math)
  • Re: Have They Formalized Even Peano or Hilbert?
    ... Peano axioms as pointed out by the australian philosopher colin leslie ... any way his proof proved maths to be inconsistent ... This is the principle of complete induction, ...
    (sci.logic)
Quantcast