# Help with set theory proof

• Mar 8th 2011, 05:59 AM
longhorn22
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 $\displaystyle X\preceq A$. Show that $\displaystyle X^Y\preceq A^Y$. Therefore show that, for cardinals $\displaystyle \kappa, \lambda, \mu$, if $\displaystyle \kappa \leq \lambda$ then $\displaystyle \kappa^\mu \leq \lambda^\mu$.

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

• Mar 8th 2011, 06:30 AM
Plato
Quote:

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

From $\displaystyle X\preceq A$ we know that there is an injection $\displaystyle f:X\to A$.
Using $\displaystyle f$ find an injection $\displaystyle \Phi:X^Y\to A^Y$.
• Mar 8th 2011, 08:57 AM
longhorn22
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.
• Mar 8th 2011, 10:25 AM
DrSteve
Quote:

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 $\displaystyle X\preceq A$. Show that $\displaystyle X^Y\preceq A^Y$. Therefore show that, for cardinals $\displaystyle \kappa, \lambda, \mu$, if $\displaystyle \kappa \leq \lambda$ then $\displaystyle \kappa^\mu \leq \lambda^\mu$.

b) Let A, B, X, Y be sets with $\displaystyle X\preceq A$ and $\displaystyle Y\preceq B$. Show that, apart from some exceptional cases, $\displaystyle 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 $\displaystyle 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.