1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Note that $|A\cup B|=|A|+|B|-|A\cap B|$. $\endgroup$ – Marra Feb 24 '13 at 16:22
  • 1
    $\begingroup$ you just reorder the sets, for example $A=\{1,2,3\}$ and $B=\{3,4,5\}$ $\endgroup$ – Dominic Michaelis Feb 24 '13 at 16:23
  • 1
    $\begingroup$ @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$. $\endgroup$ – Git Gud Feb 24 '13 at 16:24
  • $\begingroup$ I don't think they actually need to be finite for this to be true. $\endgroup$ – Michael Hardy Feb 24 '13 at 16:29
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.