Prove $|A| + |B| \ge |A \cup B|$ if $A$ and $B$ are finite sets

Question

I have a question like this:

Prove $|A| + |B| \ge |A \cup B|$ if $A$ and $B$ are finite sets.

Here is the solution but I don't agree with it:

Let $A = \{a_1, \dots, a_n\}$ and $B = \{b_1, \dots, b_m\}$. We can assume $n \le m$; otherwise just exchange $A$ and $B$. Let $A \cap B = \{a_1, \dots, a_k\},\quad k \le n$, for a suitable ordering of the elements of $A$ and $B$. Then $A \cup B = \{a_1, \dots, a_k, a_k+1, \dots, a_n, b_k+1, \dots, b_m\}$, by definition of union. So, by definition of cardinality, $|A|+|B| = n + m \ge n + (m – k) = |A \cup B|,$ since $k \ge 0$.

The point I don't understand is how $a_1$ can appear in $A \cap B$? What if it is $a_2$ or $a_3$?

Answer 1

The key words there are "for a suitable ordering of the elements of $A$ and $B$." (Another thing you may often see is "without loss of generality", or "WLOG".) It means that we may as well assume that it is precisely the first $k$ elements of $A$ are also in $B$--and if not, we'll simply reindex (relabel/rearrange) them so that it works that way.

The idea is that, sometimes, we can make some extra assumptions for simplicity's sake, without actually invalidating the proof (it's usually a good idea to justify these extra assumptions at least somewhat).

Answer 2

Here's an alternative approach:

Let $n=|A|$, $m=|B|$. Let $A=\{a_1,\ldots,a_n\}$, $B=\{b_1,\ldots,b_m\}$.Then create the new set of pairs $P=\{(a_1,1),\ldots,(a_n,n),(b_1,n+1),\ldots,(b_m,n+m)\}$. Since all elements of $P$ are disjoint, we have $|P|=n+m$.

Now consider the function $i:P\to A\cup B$ given by $i((x,k)) = x$. It should be clear that $i(P) = A \cup B$, and we must have $|i(P)| \leq |P|$. Hence $|A\cup B| \leq n+m = |A|+|B|$.