Help with set theory proof

Printable View

March 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 $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?

I'd really appreciate any help you can provide! (Nod)
March 8th 2011, 06:30 AM
Plato

Quote:

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

I'd really appreciate any help you can provide! (Nod)

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.