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$?
 A: 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|$.
A: 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).
