0

I want to check if the following statement holds:

If $a, b, c $ are cardinal numbers and $a<b$ then $a^c<b^c$.

If the statement would hold, given that there is a bijective funcion $f: a \to b$ there will also be a bijective function $g: a^c \to b^c$.

Since $f$ is bijective, we have that $f(a)=b$.

So there will be a $y$ such that $f(a^c)=y$.

Is this right so far? If so, how can we continue?

Arturo Magidin
  • 398,050
Mary Star
  • 13,956

1 Answers1

5

Your statement is false. For example, $\mathbb{N}^\mathbb{N}$ and $2^\mathbb{N}$ have the same cardinality - put another way, $$(\aleph_0)^{\aleph_0}=2^{\aleph_0}.$$

We can see this by invoking basic cardinal arithmetic rules, as $$2^{\aleph_0}\le (\aleph_0)^{\aleph_0}\le (2^{\aleph_0})^{\aleph_0}=2^{\aleph_0\times\aleph_0}=2^{\aleph_0},$$ with the first inequality being trivial, the second following from the weak monotonicity of exponentiation (which is also pretty trivial), and the third and fourth following from the definitions of cardinal multiplication and exponentiation (together with a bit of Currying).

However, we can also see this directly via Cantor-Bernstein (which, as a reminder, does not require Choice). Namely, fix your favorite pairing function $\langle\cdot,\cdot\rangle:\mathbb{N}^2\rightarrow\mathbb{N}$, and given $f:\mathbb{N}\rightarrow\mathbb{N}$ let $\hat{f}:\mathbb{N}\rightarrow 2$ be defined by $$\hat{f}(\langle a,b\rangle)=1\quad\iff\quad f(a)=b$$ (and $\hat{f}(\langle a,b\rangle)=0$ otherwise). It's easy to check that the map $$f\mapsto\hat{f}$$ is an injection from $\mathbb{N}^\mathbb{N}$ to $2^\mathbb{N}$. Since the identity provides an injection the other way, Cantor-Bernstein gives a bijection.

(Incidentally, your "proof" also gets cardinal inequality wrong: "$a<b$" means that there is an injection from $a$ to $b$ but there is not an injection from $b$ to $a$.)

It's worth pointing out that increasing the exponent doesn't necessarily increase the whole power either: letting $\kappa=2^{\aleph_1}$, we have $$\kappa^{\aleph_0}=2^{\aleph_1\times\aleph_0}=2^{\aleph_1}\quad\mbox{and}\quad \kappa^{\aleph_1}=2^{\aleph_1\times\aleph_1}=2^{\aleph_1}.$$ This is indeed the usual situation:

Operations on cardinals (including addition, multiplication, and exponentiation) are very often weakly monotonic in each of their arguments but not strongly monotonic in any of them.

Noah Schweber
  • 245,398
  • 2
    It's worth pointing out that increasing the exponent doesn't necessarily increase the whole power either --- Actually, your earlier example also shows this. Denoting $2^{\aleph_0}$ by $c,$ you showed that $c^1 = c^{\aleph_0}.$ For what it's worth, the fact that $c^{\aleph_0} = c$ has nothing to do with $c$ being too large to increase through exponentiation by $\aleph_0,$ because there exist arbitrarily large cardinals $b$ such that $b < b^{\aleph_0}$ and there exist arbitrarily large cardinals $b$ such that $b = b^{\aleph_0}.$ (continued) – Dave L. Renfro Aug 30 '19 at 17:34
  • To the proposer: In particular $\aleph_1^{\aleph_0}=2^{\aleph_0}.$ – DanielWainfleet Aug 30 '19 at 17:36
  • For strict inequality examples, let ${a_n}$ be any strictly increasing sequence of cardinal numbers (e.g. $a_1$ chosen arbitrarily large, $a_2 = 2^{a_1},$ $a_3 = 2^{a_2},$ etc.). Then by Konig's strict inequality lemma for infinite products and infinite sums, and letting $b$ be the sum of the cardinals in the sequence, we have $b$ less than the product of the cardinals in the sequence, which in turn is less than or equal to ${b}^{\aleph_0}$ (continued) – Dave L. Renfro Aug 30 '19 at 17:46
  • (the last $\leq$ is because $a_n < b$ for each $n,$ hence the product of the $a_n$'s is $\leq$ the product of $\aleph_0$ many $b$'s). For equality examples, let $b = a^{\aleph_0}$ for arbitrarily large cardinals $a.$ – Dave L. Renfro Aug 30 '19 at 17:46
  • @DaveL.Renfro That's absolutely true - I just thought that the separate example might help the OP. – Noah Schweber Aug 30 '19 at 17:53