[FOM] FOM: Natural numbers and inductive sets

[Dean Buckner]

I have been trying to understand how induction can be derived from ZF, for
which there are many proofs to hand, many of them convoluted and difficult.
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.

Why can't we just invoke Separation to define

N = {x in X: ~ (exist A) [ inductive(A) & x notin A] }

where X is any inductive set. Suppose some inductive set N* is a proper
subset of N, meaning that there is an object n in N, that is not in N*.
Then

n in X, inductive (N*), ~ n in N*

which contradicts the definition of N.  So there is no "smaller" set than N.

This does not invoke power set, and it is much less convoluted than the
others.  Is it correct?

2.  I still don't completely follow how Axiom of Choice fits in with
induction.  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?






Dean Buckner
London
ENGLAND

Work 020 7676 1750
Home 020 8788 4273