I'm trying to prove the following result, found in Tao's Analysis 1 book: "Let A and B be two non-empty sets such that A does not have lesser or equal cardinality to B. Using Zorn's lemma, prove that B has lesser or equal cardinality to A."
Definition (I): $\#(A)\leq\#(B)$ iff $\exists f\colon A\to B$ injective.
Definition (II) - (Maximal element): Let $X$ be a poset and let $Y$ be a subset of X. We say that $y$ is a maximal element of $Y$ if $y\in Y$ and $\nexists y'\in Y$ such that $y<y'$.
I assume the following:
Zorn's lemma: Let $X$ be a non-empty poset, with the property that every totally ordered subset $Y$ of $X$ has an upper bound. Then $X$ contains at least one maximal element.
Proposition (I): Let $X$ and Y be sets, and let $P(x,y)$ be a property pertaining to an object $x\in X$ and an object $y\in Y$ such that $\forall x\in X\exists y\in Y$ such that $P(x,y)$ is true. Then $\exists f\colon X\to Y$ such that $P(x,f(x))$ is true $\forall x\in X$.
Proposition (II): Let $X$ be a poset with ordering relation $\leq$ and let $x_0$ be an element of $X$. Then there is a well-ordered subset $Y$ of $X$ which has $x_0$ as its minimal element, and which has no strict upper bound.
Proposition (III): Let $A$ and $B$ be sets such that there exists a surjection $g\colon B\to A$. Then there exists an injection $f\colon A\to B$ i.e. $\#(A)\leq\#(B)$.
Here's what I've done:
"$\forall X\subseteq B$ let $P(X)$ denote the property that there exists an injective map from $X$ to $A$. Consider the sets $Y:=\{X\subseteq B | P(X)\ is\ true\}$ and $Y':=\{f\colon X\to A | X\subseteq B, f\ injective\}$; by Proposition (I) above we can assign an injective function $f$ to each subset of $B$. It's easy to see that $(Y,\subseteq)$ is a poset. Now let $Z$ be a well-ordered subset of $Y$(at least one such set must exists by Proposition (II) above since there is at least one element in $Y$, the empty function from $\emptyset$ to $A$): then if we take $V:=\bigcup_{W\subseteq Z} W$ we have that $W\in Z$ and $W\subseteq V\ \forall W\in Z$ so $V$ is a maximal element for $Z$. By Zorn's lemma Y has thus (at least) one maximal element and we claim that it is $B$ itself. In fact, suppose for the sake of contradiction that $\tilde{X}\in Y$, $\tilde{X}\neq B$ were the maximal element of $Y$; then if we take $\bar{x}\in B-\tilde{X}$ (such an element must exist, for if it didn't that would mean $B-\tilde{X}=\emptyset$ i.e. $\tilde{X}=B$ a contradiction) we have that $\tilde{X}\cup\{\bar{x}\}\subseteq B$, and there exists an injective function $f:\tilde{X}\cup\{\bar{x}\}\to A$ defined by setting $f(x):=f_{\tilde{X}}(x) \forall x\in\tilde{X}$ and $f(\bar{x})=\bar{a}$ ($f_{\tilde{X}}$ is the injective function from $\tilde{X}$ to $A$, which exists by Proposition (I) since the set $\tilde{X}$ belongs to $Y$ and $\bar{a}$ is an element of $A-f_{\tilde{X}}(A)$ which must be non-empty otherwise $f_{\tilde{X}}$ would be surjective thus by Proposition (III) there would exist an injection $\tilde{f}\colon A\to\tilde{X}$ and thus also an injection $f_A\colon A\to B$, defined by $f_A (a):=\tilde{f}(a) \forall a\in A$ which would mean that $\#(A)\leq\#(B)$, a contradiction) so $\tilde{X}\cup\{\bar{x}\}\in Y$ and since $\tilde{X}\subset \tilde{X}\cup\{\bar{x}\}$ we have that $\tilde{X}$ is not a maximal element of $Y$, a contradiction. Thus $B$ must be the maximal element of $Y$ and so we can find $f\colon B\to A$ injective and therefore $\#(B)\leq \#(A)$, as desired.
Is my proof correct? I'd appreciate any hint, comment or improvement whatsoever.
Best regards,
lorenzo.
While the general idea of your attempt is correct and you are close to a proof, there is one serious flaw: The issue lies in defining $f = f_{\tilde{X}} \cup f_{\{\tilde{x}\}}$. This will - in general - not be injective. In order to guarantee that $f$ can be chosen to be injective, you have to use the assumption that $\# (A) \not \le \# (B)$.
Furthermore note that Proposition II - as stated - is false. Consider for example a poset $\mathbb P = (P; \le)$ with only one element - or any poset with a maximum.
Proposition II will be true if we only consider posets without maxima, but then it already follows from Proposition I by letting $X=Y = \{ p \in P \mid x_0 \le p \}$ and $P(x,y) \equiv x < y$. This yields a function $g \colon \omega \setminus \{0\} \to P$ such that $g(n) < g(m)$ for all $0 < n < m < \omega$. By letting $g(0) := x_0$ we then obtain a well-ordered subset $\{ g(n) \mid n < \omega \} \subseteq P$ with minimum $g(0) = x_0$.