Let A and B be two non-empty sets such that A does not have lesser or equal cardinality to B. Using the principle of transfinite induction, prove that B has lesser or equal cardinality to A. (Hint: for every subset X~ B, let P(X) denote the property that there exists an injective map from X to A.)
The problem states that you need to use Zorn's lemma, but I can't get my head around it. My idea is that to prove that the cardinality of B < cardinality of A, then there must exist a injective function from B to A. How can I prove that ?
(Zorn's Lemma) Let X be a non-empty partially ordered set, with the property that every totally ordered subset Y of X has an upper bound. Then X contains at least one maximal element.
My Solution: Suppose there exists a value X that is a subset of B, s.t P(X) is false. This implies that there doesn't exist a function f, s.t f:X -> A is not injective. So for set X it does not hold. Since it holds for any set Y from A s.t Y<=X, this is a contradiction to Zorn's Lemma.
P.S: Sorry for the verbal question, I don't know to use LaTex.
To use Zorn's Lemma, you want a clever choice p.o. set. Consider the set of pairs $(X,f_X)$ where $X\subset B $ and $f_X:X\to A$ injective. Say $(X,f_X) < (Y,f_Y)$ if $X\subset Y$ and $f_Y=f_X$ on $X$. Upper bounds on chains can be given by union in the obvious manner. Also, as A and B are non empty, we can certainly find one such pair so the p.o. set is non empty.
Now, we can derive a contradiction if the maximal element is not of the form $(B,f_B)$. Otherwise, we have an injection from a proper subset of B to A that we can't extend. To be unable to extend forces the map to be onto. But then we have a bijection from a proper subset of B to A.