# cardinality of the union of 2 sets with at least two elements and cardinality of cartesian product

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?

-

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

-

HINT: max$(|X\cup Y|)$=$|X|+|Y| \leq |X|.|Y|$ f0r the given conditions.

-

Whenever $|X| \ge 2$ and $|Y| \ge 2$ you have $$|X| + |Y| - |X \cap Y| \le |X| + |Y| \le |X| \cdot |Y|$$ so it doesn't matter whether or not they're disjoint.

When $|X|=1$ or $|Y|=1$ the result isn't true in general, e.g. $|\{0\} \cup \{1,2\}| = 3$ but $|\{0\} \times \{1,2\}| = 2$.

Edit: So your real task it so prove that $m+n \le mn$ whenever $m,n \ge 2$. Suppose wlog that $2 \le m \le n$, then $$m+n \le n+n = \cdots$$ You finish it off.

-
Well, $|X|+|Y|\le |X|\cdot|Y|$ is precisely what's needed to prove. – egreg May 13 '13 at 14:37

We can do far better: suppose $(\kappa_{i})_{i \in I},(\lambda_{i})_{i \in I}$ are two families of cardinals with $\kappa_{i} <\lambda_{i} \forall i \in I$, then $\coprod_{i\in I} k_i < \prod_{i\in I}\lambda_i$ (the equality case is easily treated separatedly).

-

For any sets $A,B$ (either disjoint or not) the cardinality of the Cartesian product is the product of their cardinality, while the cardinality of their union is less or equal the the sum of their cardinality. Let $a:=|A|$ and $b:=|B|$, then $$|A\times B| = ab \quad\text{and}\quad |A\cup B|=|A|+|B|-|A\cup B|\leq a+b$$ It is sufficient to show that if $a,b\geq 2$ then $a+b\leq ab$. This is trivial since if $b\geq 2$ then $$a=a\cdot1\leq a(b-1) \quad\Rightarrow\quad a+b\leq ab$$ Note that it is not necessary that both sets have more than 2 elements and that the inequality trivially holds even considering infinite cardinality sets.

-