[Math] cardinality of the union of 2 sets with at least two elements and cardinality of cartesian product

elementary-set-theory

Suppose X,Y are sets with at least 2 elements. Show that
$X\cup Y\le X\times Y$

So my first thought was that cardinality $|X|\ge 2$ and the same for $|Y|\ge 2$ but by the inclusion-exclusion principle we have $|X\cup Y|=|X|+|Y|-|X\cap Y|$ but the problem does not say if they are disjoint or not.
If we assume that they are disjoint then $|X\cup Y|\ge 4$ right?
But from the definition of the cardinality for the cartesian product we have similar
$|X\times Y|\ge 4$. But I have to find an injective function (including the number of elements) s.t $f:X\cup Y\to X\times Y$ and thus conclude the result.
How should I do it?

Best Answer

Suppose $x_1$ and $x_2$ are distinct elements of $X$, $y_1$ and $y_2$ are distinct elements of $Y$.

If $X$ and $Y$ are disjoint, you can define $f\colon X\cup Y\to X\times Y$ by $$ \begin{cases} f(x)=(x,y_1) & \text{if $x\in X$, $x\ne x_1$}\\ f(x_1)=(x_1,y_2) \\ f(y)=(x_2,y) & \text{if $y\in Y$, $y\ne y_1$}\\ f(y_1)=(x_1,y_1) \end{cases} $$ This function is injective. Two distinct elements in $X$ have distinct images and two distinct elements in $Y$ have distinct images. So we can check whether it's possible that an element in $X$ and one in $Y$ have the same image: suppose $f(x)=f(y)$; if $x=x_1$, we have $f(x)=(x_1,y_2)$, but $f(y)=(x_2,y)$ or $f(y)=(x_1,y_1)$ and equality is impossible. So $x\ne x_1$ and $f(x)=(x,y_1)$. But, again $f(y)=(x_2,y)$ or $f(y)=(x_1,y_1)$; the second case is impossible, so we should have $y\ne y_1)$ and so $f(y)=(x_2,y)\ne(x,y_1)=f(x)$.

Suppose now $X$ and $Y$ are not disjoint and write $X\cup Y=X\cup(Y\setminus X)$.

If $Y\setminus X$ has at least two elements, we get an injective map $X\cup Y\to X\times(Y\setminus X)\subseteq X\times Y$ by the argument above. Otherwise $Y\setminus X$ is empty or it has just one element.

If $Y\setminus X=\emptyset$, we have $Y\subseteq X$ and we can define $f\colon X\to X\times Y$ by $f(x)=(x,y_1)$ which is injective.

If $Y\setminus X=\{y_0\}$ we can define $f\colon X\cup\{y_0\}\to X\times Y$ by $f(x)=(x,y_0)$ for $x\in X$ and $f(y_0)=(x_1,y_1)$ if $y_0\ne y_1$ or $f(y_0)=(x_1,y_2)$ if $y_0=y_1$.

Related Question