7
$\begingroup$

How do I prove this cardinality equality:$\mathfrak c^\mathfrak c=2^\mathfrak c$

I have failed to prove this after lots of trail - but I am certain it's true

How can I prove this?

  • 2
    Hint: recall that $\mathfrak{c} = 2^{\aleph_0}$, so $\mathfrak{c}^{\mathfrak{c}} = 2^{\aleph_0 2^{\aleph_0}}$.2011-08-14

3 Answers 3

8

$c^c = (2^{\aleph_0})^c = 2^{\aleph_0 \cdot c}=2^c$

Middle equality follows from this:

There is a bijection $f \colon (A^B)^C \to A^{B\times C}$.

Define $f \colon (A^B)^C \to A^{B\times C}$ by formula $f(g)(x,y) = g(x)(y)$. Here $g \in (A^B)^C$, $x \in B$, $y \in C$|. Define $f' \colon A^{B\times C} \to (A^B)^C$ by $f'(h)(x)(y) = h(x,y)$. It is easy to check that $f'$ and $f$ are inverses of each other, so they are bijections:

$f'(f(g))(x)(y) = f(g)(x,y) = g(x)(y)$ so $f'(f(g)) = g$

and

$f(f'(h))(x,y) = f'(h)(x)(y) = h(x,y)$ so $f'(f(h)) = h$.

This is known as "currying" in functional programming. It means that instead of a function taking a pair $(x,y)$ and giving result $z$, you can make a function that takes $x$ and returns a function that takes $y$ and gives result $z$.

  • 0
    interesting but how do i prove that bijection?2011-08-14
  • 0
    @Tom: Added the proof.2011-08-14
  • 0
    Notational nitpicking but I have never seen $B \cdot A$ where $A$, $B$ are sets. You use it to denote $A \times B$, right?2011-12-12
  • 0
    Yes, changed.${}$2011-12-12
7

(Assuming the axiom of choice) For every infinite cardinal $\kappa$ it holds: $\kappa^\kappa=2^\kappa$.

Proof: By Cantor's theorem $\kappa<2^\kappa$. Therefore $\kappa^\kappa\le (2^\kappa)^\kappa=2^{\kappa\cdot\kappa}=2^\kappa$. On the other hand, $2<\kappa$, so again $2^\kappa\le\kappa^\kappa$.

Combine these and you have $2^\kappa\le\kappa^\kappa\le 2^\kappa$, therefore equality.

Of course one would have to know two things first:

  1. If $\kappa\le\lambda$ then $\kappa^\mu\le\lambda^\mu$;
  2. For every infinite cardinal $\kappa\cdot\kappa=\kappa$;
  3. If $\kappa\le\lambda$ and $\lambda\le\kappa$ then $\lambda=\kappa$.

The former is quite simple, since we can assume without loss of generality that $\kappa\subseteq\lambda$ and therefore the identity function is from $\kappa^\mu$ into $\lambda^\mu$. The second point is also known as the Cantor-Bernstein theorem.

Here is a proof for the first fact:

Suppose $\kappa\le\lambda$, let $A$ be a set of size $\lambda$, we have that there is some $B\subseteq A$ such that $|B|=\kappa$ (this by the fact that from any set $B'$ of cardinality $\kappa$ there is an injective function into $A$, we can take the image of this function as $B$).

The set $A^\mu$ is exactly all the functions from $\mu$ into $A$. Since $f\in B^\mu$ means that $f\colon\mu\to B$, and therefore $f\colon\mu\to A$ so $f\in A^\mu$.

From this we have that $|B|^\mu\le|A|^\mu$, that is $\kappa^\mu\le\lambda^\mu$ as needed.

  • 0
    I've been thinking about how to prove $\kappa = \kappa \cdot \kappa$. I was wondering whether it's done by giving two injections $$ \begin{align} i: \kappa \hookrightarrow \kappa \times \kappa \\ k \mapsto (k,0) \end{align}$$ and $$\begin{align} j: \kappa \times \kappa \hookrightarrow \kappa \\ (k_1, k_2) \mapsto 2^{k_1} 3^{k_2}\end{align}$$ where $k_i$ are ordinals. But I'm not sure there is an exponentiation defined on ordinals. Can $k_i$ be treated as cardinals?2011-12-12
  • 0
    @Matt: There is a sense of ordinal exponentiation, however the result you want is shown in my answer to a question about a paper of Zermelo.2011-12-12
4

If you know that ${\mathfrak c}=2^{\aleph_0}$ and that $\aleph_0.{\mathfrak c}={\mathfrak c}$ then you get $${\mathfrak c}^{\mathfrak c}=(2^{\aleph_0})^{\mathfrak c}=2^{\aleph_0.{\mathfrak c}}=2^{\mathfrak c}.$$


So now we need to show $\aleph_0.{\mathfrak c}={\mathfrak c}$.

Clearly, ${\mathfrak c}\le \aleph_0.{\mathfrak c}$.

On the other hand; $\aleph_0.{\mathfrak c} \le {\mathfrak c}.{\mathfrak c} = 2^{\aleph_0}.2^{\aleph_0}=2^{\aleph_0+\aleph_0}=2^{\aleph_0}={\mathfrak c}$.

Since, we have both inequalities, the result follows from Cantor-Bernstein theorem.

In both proofs, we have used several well-known properties of cardinal exponentiation.

  • 0
    Great :) but how do I prove that $(k^m)^n = k^{mn}$?2011-08-14
  • 0
    @Tom: I have added the proof of this fact [here](http://math.stackexchange.com/questions/57398/). The proof is actually the same one as given by sdcvvc, but I have tried to fill in all details as much as possible. (However, the best thing you can do to understand things better would be to try to do it by yourself first.)2011-08-14
  • 0
    Is $\mathfrak{c} = 2^{\aleph_0}$ a definition or does one need to prove it?2011-12-12
  • 1
    @Matt I consider it as definition. But even if some book (lecture notes) define $\mathfrak c=|\mathbb R|$, there is no doubt that the proof of $\mathfrak c=2^{\aleph_0}$ will be given there too. So if someone is given the question posted here as an exercise, I do not suppose the proof of this expected. [Wikipedia](http://en.wikipedia.org/wiki/Cardinality_of_the_continuum) defines it as $\mathfrak c=|\mathbb R|$ and the proof of $\mathfrak{c} = 2^{\aleph_0}$ is given a few paragraphs later.2011-12-12