4
$\begingroup$

What can $\sf{ZF}$ and $\sf{ZFC}$ tell us about the smallest cardinal $\lambda$ for which $2^{\lambda}\geq\kappa$ given a cardinal $\kappa$?

In $\sf{ZFC}$, the cardinals are well-ordered, and, hence, given a cardinal $\kappa$, for each cardinal $\lambda$ we have $2^{\lambda}\geq\kappa$ or $2^{\lambda}\leq\kappa$. Furthermore, $2^{\kappa}>\kappa$ by Cantor's theorem, so by the fact that the class of cardinals is well-ordered we see that the least $\lambda$ for which $2^{\lambda}\geq\kappa$ exists. However, is it possible to make any statments about $\lambda$ in terms of $\kappa$ without assuming any sort of Continuum hypothesis-like statement?

For example, $2^{\aleph_{0}}=\aleph_{1}$ is relatively consistent with $\sf{ZFC}$. However, is it true that $2^{\aleph_{0}}=\aleph_{\alpha}$ is also relatively consistent with $\sf{ZFC}$ for any $\alpha>0$? More generally, for any cardinal $\gamma$, can we assign $2^{\gamma}$ to be any cardinal greater than $\gamma$ as long as $\gamma<\delta\Rightarrow2^{\gamma}\leq2^{\delta}$ and have a result still consistent with $\sf{ZFC}$? If this were the case, then I imagine the question about the smallest cardinal $\lambda$ for which $2^{\lambda}\geq\kappa$ for a given cardinal $\kappa$ would have little meaning in $\sf{ZFC}$ since the answer could be almost anything less than $\kappa$. I am not super familiar with cardinal arithmetic so hopefully someone can shed some light on this.

The more interesting case (to me) is in the models of $\sf{ZF}$ where $\sf{AC}$ fails. Consider for example an amorphous set $A$. If I'm correct, because amorphous sets are Dedekind-finite, given some $a\in A$, we have $|A\setminus\{a\}|<|A|$. Is it the case then that $2^{|A\setminus\{a\}|}\geq2^{|A|}$? What can we say about the inequality in question with respect to cardinalities which are not ones describing well-ordered sets? Other interesting cases happen when we mix well-orderable and non-well-orderable cardinalities.

Sorry if this question is too broad. If this is too many questions for a single post I am happy to break it up into more posts or simply cut down on my questions.

In summary: Given a cardinal $\kappa$, can the smallest cardinal $\lambda$ for which $2^{\lambda}\geq\kappa$ be any cardinal less than or equal to $\kappa$ or does $\sf{ZFC}$ have more to say about this inequality (assuming of course that $\gamma<\delta\Rightarrow2^{\gamma}\leq2^{\delta}$)? And in $\sf{ZF}$, what happens if $\kappa$ is amorphous? Is there a way of expressing $\lambda$ in terms of $\kappa$?

$\endgroup$
5
  • 1
    $\begingroup$ the fraktur letters usually denote certain defined cardinals, such as $\frak c$ denoting the continuum, $\frak m$ denoting Martin's number, $\frak a$ denoting the almost disjoint number and $\frak b$ the bounding number. I personally prefer greek letters ($\kappa$, $\lambda$, $\theta$) to denote arbitrary cardinals. $\endgroup$
    – Vsotvep
    Commented Jun 28, 2019 at 8:24
  • $\begingroup$ @Vsotvep Thanks for letting me know! I'll edit my question to help avoid confusion. $\endgroup$
    – P-addict
    Commented Jun 28, 2019 at 8:40
  • $\begingroup$ The smallest $\lambda$ for which $2^\lambda\ge\kappa$ is sometimes denoted by $\log\kappa$. $\endgroup$
    – bof
    Commented Jun 28, 2019 at 9:14
  • $\begingroup$ Give me like 35 minutes to get to the office, and I'll sit down to write something longer than a comment. $\endgroup$
    – Asaf Karagila
    Commented Jun 28, 2019 at 9:35
  • 1
    $\begingroup$ @Vsotvep: While you're of course correct in the standard situations, note that $\kappa,\lambda,\theta$ and the likes of those tend to denote $\aleph$ numbers rather than "arbitrary cardinals". In the choiceless context it is not uncommon to see fraktur letters used to denote cardinals of sets that are not well-orderable. Of course, $\frak c$ is still the cardinality of the continuum, and one should avoid using this notation when also involving cardinal characteristics of the continuum. $\endgroup$
    – Asaf Karagila
    Commented Jun 28, 2019 at 13:30

2 Answers 2

9
$\begingroup$

First let me tackle the case of ordinals, with and without choice, then we can move on to non-well-orderable sets.

For the $\aleph$ numbers

The situation here is somewhat similar with and without choice, with a few minor points which diverge. First of all, the least $\lambda$ exists because as you point out $\kappa<2^{\kappa}$, so the class of ordinals satisfying $\kappa\leq2^\lambda$ is not empty, so there is a least one.

Easton's theorem, mentioned in an earlier answer, shows that if we start with $\sf GCH$, i.e. $2^\kappa=\kappa^+$ for all infinite $\kappa$, then any "reasonable function" can define the continuum function for regular cardinals in some extension of the universe which did not change cofinalities.

In Easton's construction we only talk about regular cardinals, not singular cardinals. And the singular cardinals in his construction take "the least possible value". For singular cardinals with uncountable cofinality, Silver showed that the behavior of the continuum function is dictated by the behavior below it "on a reasonably large set of points", but we can also prove that this reasonably large set can be taken to only contain singular cardinals with countable cofinality.

Shelah, Magidor, Gitik, Woodin, and many others showed that for cardinals with countable cofinality there's some we can say, but not a whole lot. For example, it is consistent that $\sf GCH$ holds below $\aleph_\omega$, and $2^{\aleph_\omega}=\aleph_{\alpha+1}$ where $\alpha$ is any (infinite) countable ordinal. But we don't know if it is possible for $\alpha$ to be $\omega_1$, for example. So it is hard to say what is the least $\lambda$ such that $2^\lambda\geq\aleph_{\omega_1}$ if we assume that $2^{\aleph_n}=\aleph_{n+1}$ for all $n<\omega$.

In general, the easy answer to your question, is we can't say anything for a given $\lambda$, since we can always push $2^{\aleph_0}$ to be at least as large as $\lambda$. It gets trickier if you define $\lambda$ in non-absolute terms, e.g. taking $\lambda=(2^{\aleph_0})^+$, so the meaning of $\lambda$ changes between models. But even then you can't say a whole lot more, because it's possible to have $2^{\aleph_0}=\lambda$ and for some uncountable and regular $\mu<\lambda$ make $2^\mu=\lambda^+$.

Without choice, though?

Well, if we assume the axiom of choice fails, then we can prove that there is a least $\kappa$ such that $2^\kappa$ is not an $\aleph$ anymore, in which case the $\leq$ immediately becomes $<$ for further cardinals. But we can also differentiate between "There is an injection from $\kappa$ into $2^\lambda$" and "There is a surjection from $2^\lambda$ onto $\kappa$". And those two are very different things.

The paper mentioned of Fernengel and Koepke deals with the surjections. There they show that pretty much the only restriction is that you need these to not decrease with the increase of $\lambda$. There's no requirement even on the cofinality. But they do not deal with the injection case.

When I was visiting Bonn a few years ago, I pointed out that it is possible to modify the construction to get some information also on the least $\kappa$ such that $\kappa\nleq2^\lambda$. Although here, since they do not use large cardinals and in fact their construction preserves cofinalities, we have more restrictions on what we can and cannot do. Of course, if you want to allow large cardinals in the mix, the whole things becomes significantly more complicated, and probably you can do almost anything as well.

But other than these small observations, the same things as before still hold. After all, just assuming choice fails does not tell us where in the universe it fails.

For arbitrary cardinals

Well, what about sets which cannot be well-ordered, then? That's a huge mess. First of all, you need to ask yourself what does "smallest" even mean? If there is a notion of "smallest" that means that the cardinals are well-ordered and choice holds.

So without choice you need to contend with the fact that there is no smallest. For example, if $A$ is amorphous, its power set is also Dedekind-finite. That means that if $B\subsetneq A$, then $2^B<2^A$, since $\mathcal P(B)\subsetneq\mathcal P(A)$.

But since either $B$ is finite, or $A\setminus B$ is finite, it is easy to show that $A<2^B$ for any infinite subset of an amorphous set (map $B$ to its singletons, and there are only finitely many points missing, which we can map to finitely many pairs, for example).

Also, you can't quite mix things here. If $A$ is amorphous, then it cannot be linearly ordered. But power sets of ordinals can always be linearly ordered. So there is no ordinal $\lambda$ such that $A\leq 2^\lambda$ to begin with. In the other direction, as remarked, $A$ has a Dedekind-finite power set, and so $\aleph_0\nleq 2^A$.

On the other hand, suppose that $A$ is an $\aleph_1$-amorphous set, namely every subset is countable or co-countable, and in a non-trivial way so every infinite subset of $A$ is Dedekind-infinite as well. In that case we can easily show that if $B\subseteq A$, then either $|A|=|B|$ or $|B|\leq\aleph_0$. But what can we say, in that case, about power sets? Not much, not much at all. We can't even say that $2^{\aleph_0}<2^A$ without additional assumptions.

The situation is in fact much worse without choice since we don't even understand how to control power sets of arbitrary sets in $\sf ZF$. We have no good understanding of forcing like a (generalised) Cohen forcing which does not add "bounded subsets", or even what it means for a cardinal to be regular or singular. The whole structure just immediately... breaks down.

In fact, even for $\aleph$ numbers if we wish to preserve the failure of the axiom of choice, then there is no forcing which is guaranteed to (1) add subsets to $\kappa$ without adding bounded sets, and (2) not make $2^\lambda$ well-orderable for any $\lambda<\kappa$. The only exception , of course, is $\kappa=\omega$, where we have Cohen reals to do the trick, mainly because finite sets have finite power sets anyway. (Things work out if $\operatorname{Add}(\kappa,1)$ is well-orderable, which is the same as saying that $\kappa^{<\kappa}$ can be well-ordered. But of course, that will fail at some point if the axiom of choice fails.)

In conclusion!

We can't say a whole lot. Sorry. And we can say even less if we want the axiom of choice to fail. And we can say a lot less if we want to focus on sets which cannot be well-ordered.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer. I'll have to take some time to understand it all (even things like cofinality are somewhat new to me). I feel like this is a dumb question, but: If we assume $\sf{GCH}$, isn't the continuum function already defined for all infinite $\kappa$? Hence, I'm not quite sure what you mean by "any 'reasonable function' can define the continuum function for regular cardinals." $\endgroup$
    – P-addict
    Commented Jun 28, 2019 at 18:24
  • $\begingroup$ Yes, Easton's theorem starts with GCH, then does a forcing extension. I'll clarify this up. $\endgroup$
    – Asaf Karagila
    Commented Jun 28, 2019 at 18:25
2
$\begingroup$

For example, $2^{\aleph_0}=\aleph_1$ is relatively consistent with ๐–น๐–ฅ๐–ข. However, is it true that $2^{\aleph_0}=\aleph_\alpha$ is also relatively consistent with ๐–น๐–ฅ๐–ข for any $\alpha>0$? More generally, for any cardinal $\gamma$, can we assign $2^\gamma$ to be any cardinal greater than $\gamma$ as long as $\gamma<\deltaโ‡’2^\gamma\leq 2^\delta$ and have a result still consistent with ๐–น๐–ฅ๐–ข?

Almost yes, to a certain extent: $2^\kappa$ can equal $\aleph_\alpha$ for arbitrarily large ordinals $\alpha$. The only other condition that needs to be satisfied is that $\kappa<\mathrm{cf}(2^\kappa)$, at least if $\kappa$ is a regular cardinal. For $2^{\aleph_0}=\aleph_\alpha$, this is what Paul Cohen originally proved to show that $\mathsf{ZFC}+\lnot\mathsf{CH}$ is consistent.

For general regular $\kappa$, Easton proved that if these restraints ($\kappa<\mathrm{cf}(2^\kappa)$ and $\kappa<\lambda\to2^\kappa\leq 2^\lambda$) are the only constraints that need to be satisfied. Moreover, in his forcing model, the power sets of singular cardinals are the minimal possible value as well, with regard to $\kappa<\lambda\to2^\kappa\leq 2^\lambda$.

Without choice, a similar thing can be consistent, see this paper.

$\endgroup$
2
  • 1
    $\begingroup$ For example, $2^{\aleph_0}\ne\aleph_\omega$. $\endgroup$
    – J.G.
    Commented Jun 28, 2019 at 9:05
  • 2
    $\begingroup$ This is not quite the same thing without choice. Also, note that for singular cardinals things are trickier. Easton's work is about regular cardinals and Silver's work on the matter for uncountable cofinality sort of "finish the job", but Shelah, Magidor, Gitik, Woodin, and others, all showed that for countable cofinality (e.g. $\beth_\omega$) there is a lot in the air. $\endgroup$
    – Asaf Karagila
    Commented Jun 28, 2019 at 9:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .