From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik)
Subject: Re: Is exponentiation injective on infinite cardinals?
Date: 3 Jun 1999 13:50:10 -0400
Newsgroups: sci.math
Keywords: Easton's theorem, Luzin's conjecture undecidable in ZFC
In article <7j60s9$o2j$1@nntp.stanford.edu>,
Vaughan R. Pratt wrote:
:Is the function 2^x injective, where x is an infinite cardinal? That
:is, if x < y, does it follow that 2^x < 2^y, where 2^x is defined as
:the cardinal of the power set of a set of cardinality x.
:
:I don't see how to avoid having x < y yet 2^x = 2^y.
:
:Vaughan Pratt
I recall vaguely that the formula
2^aleph0 = 2^aleph1
is called Luzin's conjecture, and that it was proved to be undecidable in
ZF, or even ZFC.
Of course, in Goedel's "minimal model" the generalized Continuum
Hypothesis is a theorem, so that x < y implies 2^x < 2^y because it
reduces to x' < y' where x' is the smallest cardinal number greater than
x (indeed: x' <= y < y').
Anyone with a reference (on Luzin's conjecture and its generalizations)?
Cheers, ZVK(Slavek).
==============================================================================
From: Brandsma
Subject: Re: Is exponentiation injective on infinite cardinals?
Date: Fri, 04 Jun 1999 09:27:37 +0200
Newsgroups: sci.math
"Vaughan R. Pratt" wrote:
> Is the function 2^x injective, where x is an infinite cardinal? That
> is, if x < y, does it follow that 2^x < 2^y, where 2^x is defined as
> the cardinal of the power set of a set of cardinality x.
>
> I don't see how to avoid having x < y yet 2^x = 2^y.
>
> Vaughan Pratt
Indeed, there is no way to avoid it. It is e.g. consistent to have
2^aleph_0 = 2^aleph_1=2^aleph_2=....= 2^aleph_481 = aleph_482. to give an
example. Only weak monotonicity is true, plus the fact that the
cofinality of 2^x must be strictly more than x. In fact, for every
"function" E from cardinals to cardinals that satisfies these two
requirements (weak monotonicity, and the cf(E(x)) > x ) there is a model
of ZFC that has E(x)=2^x. This is Easton's theorem. So, as so often, it's
independent of ZFC...
Henno
==============================================================================
From: Mike Oliver
Subject: Re: Is exponentiation injective on infinite cardinals?
Date: Fri, 04 Jun 1999 00:55:06 -0700
Newsgroups: sci.math
"Vaughan R. Pratt" wrote:
>
> Is the function 2^x injective, where x is an infinite cardinal? That
> is, if x < y, does it follow that 2^x < 2^y, where 2^x is defined as
> the cardinal of the power set of a set of cardinality x.
>
> I don't see how to avoid having x < y yet 2^x = 2^y.
I don't follow. It's certainly relatively consistent with
ZFC that the function x |-> 2^x is injective. For example
it follows from GCH. It doesn't imply GCH, though; for
example if for every alpha one has 2^{Aleph_alpha}=Aleph_{alpha+2},
(which is consistent with ZFC by Easton forcing), one
still has that the continuum function is injective.
What do you mean "you don't see how to avoid it"? Do
you see an argument that the continuum function should
*not* be injective? That would certainly be interesting.
==============================================================================
From: ikastan@sol.uucp (ilias kastanas 08-14-90)
Subject: Re: Is exponentiation injective on infinite cardinals?
Date: 4 Jun 1999 20:06:31 GMT
Newsgroups: sci.math
In article <37577FE9.F8A41446@twi.tudelft.nl>,
Brandsma wrote:
@
@"Vaughan R. Pratt" wrote:
@
@> Is the function 2^x injective, where x is an infinite cardinal? That
@> is, if x < y, does it follow that 2^x < 2^y, where 2^x is defined as
@> the cardinal of the power set of a set of cardinality x.
@>
@> I don't see how to avoid having x < y yet 2^x = 2^y.
@>
@> Vaughan Pratt
@
@Indeed, there is no way to avoid it. It is e.g. consistent to have
@2^aleph_0 = 2^aleph_1=2^aleph_2=....= 2^aleph_481 = aleph_482. to give an
@example. Only weak monotonicity is true, plus the fact that the
@cofinality of 2^x must be strictly more than x. In fact, for every
@"function" E from cardinals to cardinals that satisfies these two
@requirements (weak monotonicity, and the cf(E(x)) > x ) there is a model
@of ZFC that has E(x)=2^x. This is Easton's theorem. So, as so often, it's
@independent of ZFC...
@
@Henno
@
Footnote: yes, for any such E from _regular_ cardinals to cardinals,
Easton forcing shows it is consistent that 2^x behave like E(x). At singular
cardinals, though, there is less freedom. E.g. for k singular (cf(k) < k),
if 2^x is eventually constant below k, i.e. for some b, x in [b,k) ->
2^x = 2^b, then 2^k = 2^b.
For k singular of uncountable cofinality there are quite a few
results. Sample: If GCH holds below k, then it holds at k. If k is
strongly limit and k < aleph_k, then 2^k < aleph_k (hi, Fred!).
Ilias
==============================================================================
From: ah170@FreeNet.Carleton.CA (David Libert)
Subject: Re: Axiom of choice question
Date: 19 Oct 1999 05:29:33 GMT
Newsgroups: sci.math
Dave L. Renfro (dlrenfro@gateway.net) writes:
> Stephen Montgomery-Smith [sci.math Sun, 17 Oct 1999 22:14:27 -0500]
>
>
> wrote
>
> [snip]
>
>>I am no expert, but I believe that you are correct, in that there
>>is a countable version of the axiom of choice that is weaker than
>>the full version.
>>
>>For example, to show that the countable union of a countable
>>collection of sets is countable requires the countable
>>version of axiom of choice. (One has to choose a bijection
>>from each set to the natural numbers before starting the
>>usual proof.)
>>
>>Well, this is not reliable info, just what a friend told me. But
>>apparently there is a model of set theory in which omega_1 (the
>>first uncountable ordinal) is a countable union of countable sets.
>
> It's worse than this, I'm afraid. There is a model of ZF set
> theory in which the reals are a countable union of countable
> sets. To get the full grasp of this, it is consistent with
> ZFC for the cardinality of the reals to exceed any specified
> cardinal of the form omega_{alpha} for an ordinal alpha.
> (In particular, I'm pretty sure that it is consistent in
> ZFC for any successor cardinal to be the cardinality of
> the continuum.)
Yes. It was known from the 1910's or 1920's that ZFC proves the
continuum cannot have countable cofinality (ie with AC the reals are not
a countable union of sets each of cardinality strictly smaller than the
continuum). Shortly after Paul Cohen's original results Solovay
published a paper with the amusing title "The Continuum can be anything
it ought to be" which I think proved that this is the only restriction:
given any starting countable ground model M of ZFC with a cardinal kappa
of uncountable cofinality there is a forcing extension of M modelling the
continuum is exactly kappa. In particular, AC -> all infinite successor
cardinals are regular (ie their cofinality = themselves), hence
uncountable cofinality, so Solovay's result applies as Dave said above.
Later, Easton in "Powers of regular cardinals" extended this result to
all regular cardinals simultaneously: the only restriction on
phi |-> 2^phi for phi regular is that the function be nondecreasing and
not have cofinality(2^phi) = phi.
> I believe the "problem" with the ZF model I mentioned is that a
> countable union of countable sets need not be well-orderable
> in that model, whereas any cardinal is an ordinal number, and
> hence is a well ordered set in any model of ZF.
Dave is talking about the model where the reals are a countable union
of countable sets. A model like this is discussed in Cohen's _Set
Theory and the Continuum Hypothesis_ and is there credited to Fefferman
and Levy.
If I am not mistaken, the old ZFC proof mentioned above that the
continuum has uncountable cofinality can be pushed through in ZF + the
reals are well-orderable. So I think ZF + the reals are well-orderable
implies the reals are not a countable union of countable sets. If so
Dave's comment about non-well-orderablility is inevitable for models of
ZF + the reals are a countable union of countable sets.
Note that this necessity of non-well-orderablility of the reals is
using special properties of the reals. As Cohen discusses in his book,
the same Fefferman Levy model not only satisfies that the reals are a
countable union of countable sets, but also that aleph_1 has countable
cofinality. Recall from above that AC -> every successor cardinal is
regular, so AC -> cofinality(aleph_1) = aleph_1.
Aleph_1 having countable cofonality means that aleph_1 (as the set of
all lesser ordinals using the von Neumann definition of ordinals) is a
countable union of countable sets. Aleph_1 is well-orderable (the
natural well ordering). So in general knowing a base set is
well-orderable and uncountable is not enough to conclude it can't be a
countable union of countable sets. But in the special case of the reals
this can be concluded.
> Dave L. Renfro
>
--
David Libert (ah170@freenet.carleton.ca)
1. I used to be conceited but now I am perfect.
2. "So self-quoting doesn't seem so bad." -- David Libert
3. "So don't be a morron." -- Marek Drobnik bd308 rhetorical salvo IRC sig