# 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

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!

• Of course we don't know that $f_M$ will map the entire X to Y. Hence why we only have to show that $f_M$ can be viewed as a one to one function (in the case of |Y| greater than |X|) or as a surjective function (in the other case). Commented Aug 14, 2022 at 3:40

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