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