From: Fred Galvin <galvin@math.ukans.edu>
Subject: Re: Power Set Cardinality & Axiom of Choice
Date: Tue, 4 Jan 2000 19:25:10 -0600
Newsgroups: sci.math
Summary: Aleph-nought as the cardinality of a power set?

On 4 Jan 2000, Daryl McCullough wrote:

> Fred Galvin says...
> >
> >On Tue, 4 Jan 2000, Jonathan Hoyle wrote:
> >
> >> Can it be proven without the Axiom of Choice that Aleph-nought is not
> >> the cardinality of any power set?  Thanks in advance.
> >
> >Of course. Cantor's theorem, 2^m > m, does not involve the Axiom of
> >Choice. For 2^m = aleph_0 to hold, m would have to be less than
> >aleph_0; and the only cardinals less than aleph_0 are the finite
> >cardinals. (Every infinite subset of N has cardinality aleph_0.)
> 
> You seem to be assuming that every set is either finite 
> (i.e., can be enumerated by a finite ordinal) or has a
> countably infinite subset. Is that true without choice?

No, that's not true without choice; an infinite set with no countably
infinite subset (equivalently, an infinite set which cannot be put in
1-to-1 correspondence with any of its proper subsets) is called a
Dedekind set, and the existence of such sets is consistent with ZF.

But I wasn't assuming anything about the existence or nonexistence of
Dedekind sets. When I wrote "Every infinite subset of N has
cardinality aleph_0" I was using N to denote the set of natural
numbers, not an arbitrary set; I should have been more explicit.

It *is* true that every subset of omega is either finite or countably
infinite: if X is a subset of omega, the function f defined by setting
f(x) = |{y in X: y < x}| is a bijection from X to some ordinal less
than or equal to omega.