Cardinality of the union of two sets
I am having trouble attempting to prove the inequality $|X\cup Y| \le |X|+|Y|$.
Here is my intuitive argument when we take the union of $X\cup Y$ if there are repeated elements then they are not counted twice. However, the sum $|X|+|Y|$ counts all of the elements of $X$ and $Y$, as well as any repeated elements.
My problem lies in attempting to make this argument rigorous. Could someone please help me? Thank you.
Edit: I don't believe I can assume functions? Also, these sets are finite. I don't know if this helps clarify some things.
$\endgroup$ 42 Answers
$\begingroup$You might need more details depending on what you can assume. But the sketch is like this.
Case 1: $X$ and $Y$ are disjoint. So $|X\cup Y| = |X| + |Y|$.
Case 2: $X$ and $Y$ are not disjoint. Take $Z=Y\setminus X$. Then $|Z|<|Y|$ and $Z,X$ are disjoint. $|X\cup Z| = |Z| + |X| < |X| + |Y|$ using case 1 and the fact that $Z$ was constructed by removing elements from $Y$. We know that $Z \cup X = Y \cup X$, so $|X\cup Y| < |X| + |Y|$.
$\endgroup$ 0 $\begingroup$Consider the fact that the cardinality of two disjoint finite sets is the sum of the cardinalities (not sure if you need the full rigorous proof using bijective functions for that, if you do, see below). Then consider $X \cup (Y\setminus{X})$.
$\endgroup$
