Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

5 Answers 5

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
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).

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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