# If $A,B,C$ are sets and $|A \cup B| = |C \times C|$, prove that there is either a surjection from $A$ to $C$, or an injection from $C$ to $B$ [duplicate]

My initial idea was to take an existing bijection from $$A\cup B$$ to $$C\times C$$ and use it to construct two functions which satisfy the condition, but I am not sure how to do it.

Proof must be in ZF without the axiom of choice.

Let $$f: C \times C \to A \cup B$$ be a bijection, we define $$g: A \to C$$ by letting $$g(a)$$ be the $$c$$ such that $$f(c, c') = a$$ for some $$c'$$. Such a $$c$$ and $$c'$$ always exist because of surjectivity of $$f$$, and $$c$$ is unique because of injectivity of $$f$$. So $$g$$ is indeed a well-defined function.
If $$g$$ is a surjection, we are done. If $$g$$ is not a surjection, then there is some $$c$$ not in its image. That means that $$f(c,c') \not \in A$$ for all $$c' \in C$$, hence $$f(c,c') \in B$$ for all $$c' \in C$$. This allows us to define $$h: C \to B$$ as $$h(c') = f(c,c')$$, and then $$h$$ is injective because $$f$$ is injective.