Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
Hint: recall that $\mathfrak{c} = 2^{\aleph_0}$, so $\mathfrak{c}^{\mathfrak{c}} = 2^{\aleph_0 2^{\aleph_0}}$. –  Zhen Lin Aug 14 '11 at 11:06

3 Answers 3

up vote 8 down vote accepted

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

share|improve this answer
    
interesting but how do i prove that bijection? –  Tom Aug 14 '11 at 11:18
    
@Tom: Added the proof. –  sdcvvc Aug 14 '11 at 11:25
    
Notational nitpicking but I have never seen $B \cdot A$ where $A$, $B$ are sets. You use it to denote $A \times B$, right? –  Rudy the Reindeer Dec 12 '11 at 15:30
    
Yes, changed.${}$ –  sdcvvc Dec 12 '11 at 18:19

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

share|improve this answer
    
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? –  Rudy the Reindeer Dec 12 '11 at 16:52
    
@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. –  Asaf Karagila Dec 12 '11 at 17:02

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.

share|improve this answer
    
Great :) but how do I prove that $(k^m)^n = k^{mn}$? –  Tom Aug 14 '11 at 11:16
    
@Tom: I have added the proof of this fact here. 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.) –  Martin Sleziak Aug 14 '11 at 11:54
    
Is $\mathfrak{c} = 2^{\aleph_0}$ a definition or does one need to prove it? –  Rudy the Reindeer Dec 12 '11 at 15:21
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 defines it as $\mathfrak c=|\mathbb R|$ and the proof of $\mathfrak{c} = 2^{\aleph_0}$ is given a few paragraphs later. –  Martin Sleziak Dec 12 '11 at 15:33
    
Thanks, Martin! –  Rudy the Reindeer Dec 12 '11 at 15:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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