# Thread: Help with set theory proof

1. ## Help with set theory proof

I've been given a question on my problem set which I'm a bit stuck with. I'm getting the sense that the first part is easier than the second part, but I can't even seem to get the first part!

a) Let A, X, Y be sets such that $X\preceq A$. Show that $X^Y\preceq A^Y$. Therefore show that, for cardinals $\kappa, \lambda, \mu$, if $\kappa \leq \lambda$ then $\kappa^\mu \leq \lambda^\mu$.

b) Let A, B, X, Y be sets with $X\preceq A$ and $Y\preceq B$. Show that, apart from some exceptional cases, $X^Y\preceq A^B$. What are the exceptional cases?

2. Originally Posted by longhorn22
a) Let A, X, Y be sets such that $X\preceq A$. Show that $X^Y\preceq A^Y$. Therefore show that, for cardinals $\kappa, \lambda, \mu$, if $\kappa \leq \lambda$ then $\kappa^\mu \leq \lambda^\mu$.
From $X\preceq A$ we know that there is an injection $f:X\to A$.
Using $f$ find an injection $\Phi:X^Y\to A^Y$.

3. Thank you - I was able to find an injection for (a), and then deduce the result about cardinals. However, I'm still stuck on (b), which seems to be a fair bit more difficult.

4. Originally Posted by longhorn22
I've been given a question on my problem set which I'm a bit stuck with. I'm getting the sense that the first part is easier than the second part, but I can't even seem to get the first part!

a) Let A, X, Y be sets such that $X\preceq A$. Show that $X^Y\preceq A^Y$. Therefore show that, for cardinals $\kappa, \lambda, \mu$, if $\kappa \leq \lambda$ then $\kappa^\mu \leq \lambda^\mu$.

b) Let A, B, X, Y be sets with $X\preceq A$ and $Y\preceq B$. Show that, apart from some exceptional cases, $X^Y\preceq A^B$. What are the exceptional cases?

Here's something to get you started for the second one. Let f be an injection from X to A, and g an injection from Y to B. Now, let h be an arbitrary function from Y to X. The most natural thing to do is let F(h) be the function k from B to A where to compute k(b), you take $g^{-1}(b)$ if possible (this gives an element of Y), then apply h (this gives an element of X), and finally apply f (this gives an element of A). Now think about how you would define k on elements not in the range of g. Going through the argument carefully will probably shed some light on the exceptional cases.