Re: Can STRONG induction for N be derived from Peano's Axioms?

From: Dan Christensen (dchris_at_allstream.net)
Date: 02/24/05 

Date: Thu, 24 Feb 2005 16:58:33 -0500

"Arturo Magidin" <magidin@math.berkeley.edu> wrote in message
news:cvj6rd$1m72$1@agate.berkeley.edu...
> In article <ng8Td.29$g4.304@tor-nn1.netcom.ca>,
> Dan Christensen <dchris@allstream.net> wrote:
>>If so, can someone sketch out a proof starting from PA?
>
> If by "transfinite induction for N" you mean
>

Yes, I did mean "STRONG induction." Sorry about the confusion.

>
> "Let S be a subset of natural numbers such that
>
> for all n, if ({k in N: k<n} is contained in S) then (n is in S).
>
> Then S=N"
>
> then this is equivalent to regular induction in N (which is Peano's
> fifth axiom), and to the well-ordering principle.
>
>
> THEOREM: The following are equivalent:
>
> (i) Peano's fifth axiom
> (ii) Strong induction for N (as stated above).
> (iii) N is well-ordered.
>
>
> Proof. (i)->(ii). Assume S satisfies the conditions given.
>
> Let S' = { n in S: for all k in N, k<n -> k in S}.
>
> We show that S' satisfies the assumptions of Peano's fifth axiom.
>
> 0 is in S, since {k in N: k<0} is empty. Since 0 is in S and so are
> all "smaller natural numbers", it follows that 0 is in S'.
>
> Assume n is in S'. Then n and all k<n are in S. Therefore, all k<n+1
> are in S.

It seems an intuitively "obvious" point, but what specific property of N can
be used here to prove all k<n+1 are in S?

Dan

> By assumption on S, this means that n+1 is in S. Hence s+1
> and all k<n+1 are in S, so n+1 is in S'.
>
> Therefore, by Peano's fifth axiom, S' is equal to N. Since S' is
> contained in S, and S is contained in N, it follows that N=S, as
> desired.
>
> (ii)->(iii) Let A be a nonempty subset of N. Then S=N-A is not all of
> N, so by the contrapositive of (ii) there must exist n in S such that
>
> {k in N : k<n } is contained in S and n is not in S.
>
> Thus n is in A, and for all k in N, k<n -> k not in A.
>
> Therefore, n is in A, and for all k in N, k in A -> n<= k; that is, A
> has a least element. This is what we wanted to prove.
>
>
> (iii)->(i). Let S be a subset of N such that 0 is in S, and for all n
> in N, n in S -> (n+1) in S. We want to show that S=N.
>
> Let A=N-S. If A is nonempty, then by well ordering it has a least
> element k.
>
> k is not equal to 0, since 0 is in S by assumption. So k = n+1 for
> some n. Since n<k, and k is the least element of A, n is not in A.
>
> So n is in S. Therefore, n+1 is in S. But n+1 = k is not in S. This
> contradiction arises from assuming that A is nonempty. Therefore A is
> empty, so N=S as desired.
>
> QED
>
>
>
>
> --
> ======================================================================
> "It's not denial. I'm just very selective about
> what I accept as reality."
> --- Calvin ("Calvin and Hobbes")
> ======================================================================
>
> Arturo Magidin
> magidin@math.berkeley.edu
>

Relevant Pages

  • Re: Can STRONG induction for N be derived from Peanos Axioms?
    ... > then this is equivalent to regular induction in N (which is Peano's ... > fifth axiom), and to the well-ordering principle. ... > contradiction arises from assuming that A is nonempty. ...
    (sci.math)
  • Re: True = [ proven | provable ]
    ... The proof of this uses the Axiom of Choice. ... >> Incompleteness Theorem. ... > Incompleteness Theorem is that Goedel, using construction rules ... Well-Ordering Principle is nonconstructive. ...
    (comp.theory)
  • Re: True = [ proven | provable ]
    ... The proof of this uses the Axiom of Choice. ... >> Incompleteness Theorem. ... > Incompleteness Theorem is that Goedel, using construction rules ... Well-Ordering Principle is nonconstructive. ...
    (sci.math)
  • Re: True = [ proven | provable ]
    ... The proof of this uses the Axiom of Choice. ... >> Incompleteness Theorem. ... > Incompleteness Theorem is that Goedel, using construction rules ... Well-Ordering Principle is nonconstructive. ...
    (sci.logic)
  • Re: What is md5sum?
    ... Of course - unfortunately proof by contradiction only holds in boolean ... contradiction with the classical proof that the decimals are cardinally ... You seem to think that mathematics is stuck in socrates time. ... In the 1930s Cohen proved the independence of the axiom of choice from ...
    (comp.os.linux.setup)