[FOM] FOM: Natural numbers and inductive sets

[Jeff Hirst]

Hi-

Dean Buckner asked:

>My understanding is that, given the form of induction
>established here, it can be proved that no finite set (i.e. no proper subset
>of N) is equinumerous with any of its proper subsets. I.e. every finite set
>is "Dedekind finite".  But we cannot prove the converse, i.e. it is
>consistent with ZF that there exists an infinite set that is Dedekind
>finite.
>
>To prove the equivalence of "Dedekind finite" with "finite", we need the
>axiom of choice.  Is that correct?

I believe that ZF suffices to prove that every finite set (i.e. a set which
is equinumerous with a proper initial segment of omega) is Dedekind finite.
The converse is independent of ZF, but is strictly weaker than countable
axiom of choice.  For details (and just because I think it's a nice book)
I recommend Tom Jech's "The Axiom of Choice" (North-Holland, 1973,
ISBN:0444104844).

Dean also writes:
>Nearly all proceed as follows. Define an inductive set S as being such that
>0 is in S and for all x, if x is in S the successor of x is in S.
>Show there exists a "smallest" inductive set by constructing the set Z of
>all inductive sets (invoking power set).  Show the "smallest" set is the
>intersection of Z.  One proof argues that Axiom of Choice is necessary.

The collection of all inductive sets includes all the limit ordinals,
and is therefore a proper class whose existence is not provable in ZFC.
One development I like for this is in Judy Roitman's "Introduction
to Modern Set Theory" (John Wiley and Sons, 1990, ISBN:0471635197).  The
axiom of infinity asserts the existence of an inductive set, and the
existence of omega (i.e. N) follows from the axiom of separation.
The fact that N has no proper inductive subset follows from the
definition of finite ordinals (as transitive sets well ordered by
the epsilon relation having exactly one element with no successor
and 0 as their only limit element.)

Hope this helps...

-Jeff


-- 
Jeff Hirst   jlh at math.appstate.edu
Professor of Mathematics
Appalachian State University, Boone, NC  28608
vox:828-262-2861    fax:828-265-8617