Show there either a one-to-one function from $X$ into $Y$ or an onto function from $X$ onto $Y$ given a partially ordered set

Question

Let $X$ and $Y$ be non-empty sets. Let $F= \{(A,B,f): A \subset X, B \subset Y, f: A \rightarrow B \text{ is a bijection} \}$.

Partially order $F$ by $(A_1,B_1, f_1) \leq (A_2,B_2,f_2)$ if and only if $A_1 \subset A_2, B_1 \subset B_2$ and $f_2$ restricts to $f_1$ on $A_1$. Use this to show that one of the following two possibilities must hold :

1. There exists a one-to-one function from $X$ into $Y$.
2. There exists an onto function from $X$ onto $Y$.

Here are some thoughts:

By Zorn's Lemma, there exists a maximum $f\in F$, call$f_M$. Then $f_M$ by definition is a bijection. But the problem is that, we don't know if $f_M$ will map the entire $X$ to $Y$.

Another thought is to use the Schroder-Berstein's theorem to show that there exists an injective function from $X$ to $Y$ and an injective function from $Y$ to $X$. But I think that this one has the same problem as before.

Any help will be appreciated!

Answer 1

If the domain of $f_M$ is $X$, then alternative 1 holds, and we're done. Otherwise, the domain of $f_M$ is a proper subset of $X$. Using maximality of $f_M$, argue that in this case $f_M$ is onto $Y$.

Hint: proof by contradiction. By the assumption of this case, the domain of $f_M$, let's call it $A$, isn't all of $X$, so we can pick an element $x\in X\setminus A$. What can you do next if we've assumed (for our proof by contradiction) that the range of $f_M$ is not all of $Y$?