Re: a < b implies 2^a < 2^b

quasi wrote (in part):

Consider the following statement (E) ...

(E): If a,b are cardinal numbers such that a < b,
then 2^a < 2^b.

Is (E) true in the standard model (S) of set theory?

Dave L. Renfro wrote (in part):

I'm pretty sure (E) is an independent statement.
In fact, I believe even the special case in which
a = aleph_0 and b = aleph_1 is independent, as this
special case is sometimes called "Lusin's Hypothesis"
(because Lusin first drew attention to it, sometime
in the 1920s I think), and I'm pretty sure Lusin's
Hypothesis has been proved independent (probably back
in the late 1960s).

Actually, this was proved in the Summer or Fall
of 1963, by Robert Solovay.

I looked over some notes I have at home on this
topic and here's a brief summary. Incidentally,
when I say "we can have", this roughly means
there is a model of the ZFC axioms in which the
statement is true. Some of what follows came from
expository papers (Gregory H. Moore has written
a couple), some from paper abstracts or summaries
or Math. Reviews, and some from Solovay himself
(who wrote a nice letter to me back in Summer 2001
in reply to some questions I asked him).

By the way, I know very little about the technical
aspects of these things, but I do know that many of
these results have more precise versions that have to
do with how "nice" the model is in certain ways.

In the Spring of 1963 (it may have been the month
of May), Paul Cohen gave two talks at Princeton
on his results. The first was for experts and
Robert Solovay, who at the time was a topologist
visiting from Berkeley, didn't attend, but Solovay
did attend the second talk that was for a more
general audience. At the talks Cohen outlined his
results, one of which was that 2^(aleph_0) can be
arbitrarily large. Cohen mentioned that he didn't
know, for example, whether 2^(aleph_n) being equal
to aleph_(n+1) for n = 1, 2, 3, 4, 5 implies
that 2^(aleph_6) = aleph_7. [I think his actual
question was a bit more precise, something along
the lines of if aleph_6 Cohen reals are added to
a transitive model of ZFC + GCH, then in the new
model does the set of real numbers have cardinality
aleph_6 or cardinality aleph_7. And don't ask me
what this means!]

Solovay decided to work on this problem and was
able to solve it later that year. Solovay's announcement
is in a 1963 issue of the Notices of the AMS and had
the catchy title "2^aleph_0 can be anything it ought
to be". In this announcement (it later also appeared
as a one-page announcement on p. 435 of "The Theory
of Models", North-Holland, 1965; this is a publication
for a conference held at Berkeley in 1963), Solovay
states these 3 results ('cf' is 'cofinality'; see the
end of this post for an explanation):

1. Let be be a cardinal with uncountable cofinality,
i.e. cf(b) > aleph_0. Then we can have 2^(aleph_0) = b.

By the time Solovay announced this, I believe Cohen
had also proved it. Note this is a bit more precise
than "2^(aleph_0) can be arbitrarily large".

2. Let b' = cf(b') < cf(b). Then we can have
2^(b') = b and
(for all a)(aleph_a < b' implies 2^(aleph_a) = aleph_(a+1)).

3. Let 0 <= n_1 <= n_2 <= ... <= n_k be finite cardinals.
Then we can have 2^(aleph_j) = aleph_(n_j)
for each j = 1, 2, ..., k.

Note: #3 implies that what I called "Lusin's Hypothesis"
(yesterday) can hold. By the way, "Lusin's [Luzin's]
Hypothsis" is also called the "second continuum hypothesis".

Solovay's method in #3 only allowed him to control
the values of a finite number of cardinals. Although
the published statement was for alephs with finite
ordinal subscripts, I believe Solovay's method worked
for any finite number of regular cardinals. However,
I'm not very sure about this point. In the following
year (1964), William B. Easton managed to control the
powers (with base 2) of all the regular cardinals at
once. This was Easton's 1964 Ph.D. Dissertation at
Princeton, under Alonzo Church. For some reason it
wasn't published until 1970 [in Annals of Mathematical
Logic, volume 1, pp. 139-178].

Easton's main result was that, given any "function" f
from the regular ordinals to the cardinals that satisfies
certain very general conditions, we can have 2^b = f(b)
for all regular cardinals b. There are two conditions on f:

A. a < b implies f(a) <= f(b).

B. For all b, we have b < cf( f(b) ).

Condition A obviously must hold, and condition B is
a restriction that arises from Konig's strict inequality
involving transfinite sums and products. What happened
is that at the 1904 International Congress of Mathematicians,
J. Konig gave a talk in which he used some cardinal
computations to disprove the continuum hypothesis.
In fact, I think he went much further, asserting
that the cardinality of the continuum cannot be equal
to aleph_b for any ordinal b. It was not long afterwards
(at most a few days, I think) that an error was found
in Konig's "proof", but one of the things that survived
the corrections to what Konig presented is the result that
the cardinality of the continuum cannot have countable
cofinality. Thus, 2^(aleph_0) cannot equal aleph_w or
aleph_(w^2 + w) or aleph_(epsilon_0), among other things.

The situation for singular cardinals is, from what
I understand, much more involved and problematic.
I think Jack Silver was the first to come up with
some definitive results showing that the kind of
behavior Solovay and Easton obtained for the possible
behavior of the function 2^b for regular cardinals b
does not hold for singular cardinals. [Easton's methods
simply didn't allow singular cardinals to be treated,
which of course still allows for the possibility
that some other method might do the trick. Silver
showed this doesn't happen, however.] An example of
the result that Silver proved (announced in the summer
of 1974, I think) is that if [in certain "nice" models
of ZFC] 2^(aleph_b) = aleph_(b+1) for each ordinal
b < omega_1, then we must have 2^(aleph_omega_1)
equal to aleph_(omega_1 + 1). In fact, Silver proved
this for any singular cardinal with uncountable
cofinality replacing aleph_omega_1.


COFINALITY OF A CARDINAL -- This is the least limit
ordinal through which the cardinal can be reached
(as a limit of) by using a transfinite ordinal sequence
of smaller cardinals. The cofinality of a cardinal is
itself a cardinal.

Examples.

The cofinality of each of these is omega (i.e. w, or w_0):
(1) aleph_0, (2) aleph_omega, (3) the smallest cardinal b
such that aleph_b = b.

(1) aleph_0 = sup{1, 2, 3, ...}

(2) aleph_omega = sup{aleph_1, aleph_2, aleph_3, ...}

(3) sup{aleph_w, aleph_(aleph_w), aleph_(aleph_(aleph_w))), ...}

The cofinality of any cardinal of the form aleph_(b+1) for
some ordinal b is aleph_(b+1).

A cardinal b is regular if cf(b) = b and singular
if cf(b) < b. [It is not possible to have cf(b) > b.]

Dave L. Renfro
.

Relevant Pages

  • Re: Power sets with same cardinal => sets have same cardinal?
    ... It is clear that ZF + GCH implies your conjecture. ... and some from Solovay himself ... Let be be a cardinal with uncountable cofinality, ... the values of a finite number of cardinals. ...
    (sci.math)
  • Re: a question
    ... shown that the cofinality of aleph_omega is aleph_0. ... necessarily the natural order on ordinals or cardinals (which is ... consider the real numbers R, with "<" the natural order of the reals, ...
    (sci.logic)
  • Re: Set Theory question
    ... cardinal has cofinality omega." ... In fact, the only possible cofinalities are 0, 1, and infinite cardinals. ... No, the union of any collection of ordinals is in fact an ordinal, since we are taking the union of a chain of well-ordered sets. ...
    (sci.math)