From: "Brian M. Scott" <scott@math.csuohio.edu>
Newsgroups: sci.math
Subject: Re: Power set of finite set
Date: Fri, 11 Sep 1998 12:53:46 -0400

Jeremy Boden wrote:

> In article <6t8l2c$od4@b.stat.purdue.edu>, Herman Rubin
> <hrubin@b.stat.purdue.edu> writes

[snip]

> >However, if one defines finite by other means, such as not having
> >a 1-1 mapping properly into the set, there are models in which such
> >sets exist and are not well orderable.  If X is such a set,
> >P(P(P(X))) is not, and there must be a counterexample.

> I would be most interested to see an example of this!

> According to my understanding of ZFC,
> ALL sets can be well-ordered, regardless of whether they are finite or
> not.

True.  The models in question are of ZF + ~AC, Zermelo-Fraenkel set
theory with the negation of the axiom of choice, not of ZFC.

> In addition the power set always exists.

True but irrelevant.  (Herman's last comment is perhaps phrased a trifle
opaquely.)  Call a set X Dedekind infinite if there is a 1-1 map from X
onto a proper subset of X; a set that is not Dedekind infinite is said
to be Dedekind finite.  Say that a set is finite if there's a bijection
between it and a finite ordinal; otherwise it's infinite.  It's easy to
show that every finite set is Dedekind finite; the question is whether
every infinite set is Dedekind infinite.  If the answer were 'yes',
finite and Dedekind finite would coincide; in order for them to be
distinct concepts, there must be an infinite, Dedekind finite set.  It's
also easy to show that every infinite, well-ordered set is Dedekind
infinite: well-order it as {x(i) : i < k} for some infinite cardinal k,
and let f(x(i)) = x(i+1).  Thus, if there's an infinite, Dedekind finite
set, it cannot be well-orderable.  Herman's assertion is that there are
models of ZF in which there is an infinite, Dedekind finite set (which
must of necessity not be well-orderable).

However, if X is an infinite, Dedekind finite set, P(P(P(P(X)))) is
not.  (I don't at the moment see how to prove Herman's claim that
P(P(P(X))) is not.)  It's infinite, but it's also Dedekind infinite.  To
see this, note that each ordered pair in X x X is an element of P(P(X)),
so each binary relation on X is an element of P(P(P(X))).  In
particular, each well-order of a subset of X is a member of P(P(P(X))). 
For any ordinal k let W(k) be the set of these well-orders of type k;
W(k) is an element of P(P(P(P(X)))).  Because X is infinite, it's easy
to show that W(k) is non-empty for each finite k.  Define f on
P(P(P(P(X)))) so that f(W(k)) = W(k+1) if k is a finite ordinal, and
make f the identity everywhere else.  Then f is 1-1, and W(0) isn't in
the range of f, so f witnesses the fact that P(P(P(P(X)))) is Dedekind
infinite.

Brian M. Scott