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

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

• Note that $|A\cup B|=|A|+|B|-|A\cap B|$. – Marra Feb 24 '13 at 16:22
• you just reorder the sets, for example $A=\{1,2,3\}$ and $B=\{3,4,5\}$ – Dominic Michaelis Feb 24 '13 at 16:23
• @user63787 It could very well be that $a_1\not \in A\cap B$. However you can argue without loss of generality that $A\cap B=\{a_1, \dots ,a_k\}$ for some $k\in \Bbb N$ such that $k\leq n$. – Git Gud Feb 24 '13 at 16:24
• I don't think they actually need to be finite for this to be true. – Michael Hardy Feb 24 '13 at 16:29

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