0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.