In chapter 24 of Halmos' Naive Set Theory the following problem is posed as an exercise (page 96):

Prove that if $a, b$ and $c$ are cardinal numbers such that ${a}\le{b}$, then $a^c\le{b^c}$. Prove that if $a$ and $b$ are finite, greater than $1,$ and if $c$ is infinite, then $a^c=b^c$.

My problem lies in proving the second proposition. The identity ${a}\cdot{a}=a$ for infinite cardinal numbers is not covered yet at that point of the text so that the direct proof ${2}\le{a}\le{2^c}=>{2^c}\le{a^c}\le{2^{{c}\cdot{c}}=2^c}$ is not available. Doing a bit of research, wikipedia points to the use of the axiom of choice on its cardinal number article. I let A, B, and C be sets such that card(A)=a, card(B)=b, card(C)=c, and $a\le{b}$. I then tried to apply Zorn's lemma to the set of functions $f$ such that: ${domf}\subset{B^C}$, ${ranf}\subset{A^C}$, and $f$ is one-to-one; which is partially ordered by inclusion. This yields a maximal element say $\phi$. That's where I am stuck.


If $a=b$, there’s nothing to prove, so assume that $a<b$. From the first part you know that $a^c\le b^c$. Since $a$ is finite and greater than $1$, and $b$ is finite, there is a positive integer $n$ such that $a^n\ge b$, and it follows from the first part that $b^c\le (a^n)^c$. If you can show that $a^c=(a^n)^c$, the result will follow from the Schröder-Bernstein theorem.

To show this, show that $nc=c$ for finite, non-zero $n$ and infinite $c$, and show that in general $(x^y)^z=x^{yz}$. I don’t own a copy of Halmos, but judging from what I can see at Google books, the latter has been stated but not proved. You should go ahead and prove it; there’s a very natural bijection between $\left(X^Y\right)^Z$ and $X^{Y\times Z}$. The former seems not to have been stated yet, but it can be proved by induction on $n$. The only hard step is showing that $2c=c$; after that the induction step just uses that same result. Just after the problem on which you’re working, Halmos proves that $c+c=c$, and there’s a natural bijection between $c+c$ and $2c$, so everything that you need is there.


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.