0
$\begingroup$

Let $\kappa$ be an infinite cardinal number. Prove, without appealing to the Axiom of Choice, that $$\aleph_0 \leq 2^{2^\kappa}$$

I am struggling to answer this question. If I had the axiom of choice available, I would have that there is an injection from natural numbers to k, by cardinal comparability. I'm not sure how to approach this question without axiom of choice being available.

$\endgroup$
  • $\begingroup$ Does the theorem that states that $|/mathcal P(X)|>|X|$ use axiom of choice? $\endgroup$ – André Porto May 20 '17 at 23:09
  • 1
    $\begingroup$ @AndréPorto Cantor's theorem shows (without choice) that $$2^{2^\kappa}\gt2^\kappa\gt\kappa.$$ That does not in itself establish $$2^{2^\kappa}\ge\aleph_0$$ because, in the absence of the axiom of choice, we do not know that $\kappa\ge\aleph_0;$ as far as we know, $\kappa$ could be incomparable with $\aleph_0.$ $\endgroup$ – bof May 21 '17 at 1:27
  • 3
    $\begingroup$ Oh man! It's everything so confusing without choice! $\endgroup$ – André Porto May 21 '17 at 5:09
  • 2
    $\begingroup$ @AndréPorto No, that's not true. By definition, a set is infinite if it has more than $n$ elements for every natural number $n.$ In the real world, where the axiom of choice is true, every infinite set has cardinality $\ge\aleph_0.$ However, in some weird fantasy worlds where the axiom of choice fails, there are sets which can't be well-ordered; the cardinality of such a set is not equal to any aleph, and is not necessarily comparable with $\aleph_0.$ $\endgroup$ – bof May 21 '17 at 6:56
  • 1
    $\begingroup$ Yeah, but I was thinking. Let X be an infinite set. Define $f:\aleph_0\to X$ as follows: $f(0)=x_0$ for some fixed $x_0$; For each $n$, $X$ must contain more than $n$ elements, so there exists $x_{n+1}$ in $X$ which is not in $\{f(x_0),...,f(x_n)\}$ and we define $f(n+1)=x_{n+1}$. This way we constructed an injective function from $\aleph_0$ to $X$. Then $aleph_0\leq |X|$ for every infinite set $X$. What am I missing? $\endgroup$ – André Porto May 21 '17 at 10:29
4
$\begingroup$

If $S$ is an infinite set, we can define an injection $f:\mathbb N\to\mathcal P(\mathcal P(S))$ by setting $$f(n)=\{X\subset S:X\text{ is an }n\text{-element set}\}.$$ This shows that $\aleph_0\le2^{2^\kappa},$ a result which I believe is due to Bertrand Russell. Of course it's actually a strict inequality; there is no bijection between $\mathbb N$ and $\mathcal P(\mathcal P(S)).$

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

By assumption, there exists a non-surjective injective map $f\colon\kappa\to\kappa$. Define $g_0=f$ and recursively $g_{n+1}=f\circ g_n$. Finally, define $\Bbb \omega\to 2^{2^\kappa}$, $n\mapsto g_n(\kappa)$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ No, the assumption is that $\kappa$ is infinite, i.e., $\kappa\gt n$ for every natural number $n.$ Some kind of choice is needed to conclude that $\kappa$ is Dedekind infinite, i.e., that there is a non-surjective injection $f:\kappa\to\kappa.$ $\endgroup$ – bof May 21 '17 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.