How can i prove the cardinality of the union of two sets is equal or less than the cardinality of each added?

Question

I have |S1| = n and |S2| = m. I need to prove |S1 U S2| <= n+m

I need to formally prove this. I think i should just substitute the n and m for |S1| and |S2| respectfully, however im kinda confused if that actually proves that.

The union simply means that the new set will be all of the elements in each set and if there are duplicates they are only counted once.

Thanks

Answer 1

First, assume that S1 and S2 are subsets of a universal set A. Then S1 U S2 is also a subset of A. S1 and S2 may be disjoint or not.

Since S1|=n and |S2|=m, then
S1 = {a1,a2,a3,...,an} and
S2 = {b1,b2,...,bm}

then S1 U S2 = {a1, a2, a3, ...an, b1, b2, ...,bm}

If S1 and S2 are disjoint, then no member repeats. Therefore
|S1 U S2| = n + m

However, if S1 and S2 are not, then they have a common element. (AKA ai = bj) Hence the union will only list it once. Therefore
|S1 U S2| < n+m

Answer 2

You just need to use the fact that S1 union S2 = S1 +S2 - (S1 intersect S2) and then you use the triangle inequality.

Answer 3

First, argue that if all elements of both sets are unique then the cards are equal; if there are repeats, the card of the union set wil be less then the two combined cards.

Answer 4

Sure, let A = {even integers}, B = {odd integers}, A U B = {all integers} Then A≠B, but |A| = |B| = |A U B|.