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
    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
    @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.

  • 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