Set theory, injective and surjective functions task Prove that if
$$|Z \times Z| = |X \cup Y| $$
then: there exists injective function (one-to-one) $f: Z \rightarrow Y$ OR there exists a surjective function $k : X \rightarrow Z$ .
If Z is finite, I've come with this: If $|X| \geq|Z|$, then there is a surjective  for X to Z.
If $|X| < Z$ then $|Y| >=|Z|$ so there is an injective function from Z to Y.
But I can't express it in the language of set theory.
And I can't figure out when Z is infinite. Any tups?
 A: Usually, when you have to prove something of the form
$$proposition_1 \ \ \mbox{ OR } \ \ proposition_2$$
You can assume that $proposition_1$ is false, and prove that $proposition_2$ is true. We use this strategy to prove this theorem.
First of all, fix a bijection $f: X \cup Y \to Z \times Z$.
Now, assume that "there exists a surjective function $X \to Z$" is false. Let's prove that there exists an injective function $Z \to Y$.
Consider the projection on the first coordinate $\pi: Z \times Z \to Z$
$$\pi (z_1,z_2)=z_1$$
Clearly $\pi$ is surjective. Consider the composition map $\pi \circ f : X \to Z$ (restricted to $X$) defined by
$$( \pi \circ f )(x) = \pi (f(x))$$
By our assumption, $\pi \circ f$ is not surjective. Hence there exists $z \in Z$ such that
$$\forall x \in X, \ \ \pi (f(x)) \neq z$$
Fix such an element $z_0 \in Z$. Then we can say that
$$\forall x \in X, \ \ \forall z \in Z, \ \ f(x) \neq (z_0,z)$$
this is equivalent to
$$\forall x \in X, \ \ \forall z \in Z, \ \ f^{-1}(z_0,z) \neq x$$
this is equivalent to
$$\forall z \in Z, \ \ f^{-1}(z_0,z) \notin X$$
However, for all $z \in Z$ you have $f^{-1}(z_0,z) \in X \cup Y$. This means that necessarily
$$\forall z \in Z, \ \ f^{-1}(z_0,z) \in Y$$
This defines a function $g: Z \to Y$
$$g(z)= f^{-1}(z_0,z)$$
I leave to you to check that $g$ is indeed injective (use the fact that $f^{-1}$ is injective). This completes the proof.
