# Proof containing pairwise disjoint sets

I came across the following question while studying.
Let $A,B,C,D$ be pairwise disjoint sets. Prove that if $|A| = |B|$ and $|C| = |D|$ then $|A \cup C| = |B \cup D|$.

I thought of the fact that they intersections are obviously empty but this doesn't help with the progression to a solution. I also tried to find any properties of the pairwise disjoint union that might help but I am stuck. Can anyone offer some suggestions/solutions?

• Are you sure that you have written the complete question ? Consider $A=\{a,b,c\}$, $B=\{d,e,f\}$, $C\{1,2,3\}$ and $D=\{1,2,3\}$. Then it contradicts your conclusion. – seeker Dec 20 '15 at 21:18
• If $A,B = \emptyset$, $C = \{1\}$, $D = \{2\}$, then $|A| = |B| = 0$, $|C| = |D| = 1$, and $A,B,C,D$ are pairwise disjoint (as mentioned in your title), but $|A \cup B| = 0 \neq 2 = |C \cup D|$. Are you sure the problem statement is correct? – JimmyK4542 Dec 20 '15 at 21:18
• @JimmyK4542 fixed it. Thank you. – dreamin Dec 20 '15 at 21:21

You know that $$|A \cup C| = |A|+|C|-|A \cap C|.$$ Similarly, $$|B \cup D| = |B|+|D|-|B \cap D|.$$ Also, since $A,B,C,D$ are pairwise disjoint, the intersection of any two of them is the empty set. Hence, $$|A \cap C| = |B \cap D| = 0.$$

Now, do you see how to prove that $|A \cup C| = |B \cup D|$?

• Just in case the sets are not necessarily finite: Because of the cardinality assumptions, there are one-to-one and onto functions $f:A\to B$ and $g:C\to D$. Define $h:A\cup C\to B\cup D$ by letting $h(x)$ be $f(x)$ or $g(x)$, depending on whether $x$ is in $A$ or $C$. Using the pairwise disjointness where necessary, show that $h$ is well-defined, one-to-one, and onto. – Steve Kass Dec 20 '15 at 21:38
• I still don't exactly see how to proceed. Is it similar to the property of equality stating that a + b = b + c implies a = b? – dreamin Dec 20 '15 at 21:41
• SteveKass: Good point, the sets might not be finite. dreamin: Look at the right sides of first two equations. You are given that $|A| = |B|$ and that $|C| = |D|$. We also know that $|A \cap C| = |B \cap D| = 0$. Do you see how $|A|+|C|-|A \cap C| = |B|+|D|-|B \cap D|$? – JimmyK4542 Dec 20 '15 at 21:46
• @SteveKass I would then I have to come up with a bijective function from |$A \cup B$| to |$C \cup D$|? – dreamin Dec 20 '15 at 22:01
• The function $h$ I described is a bijection from $A\cup B$ to $C\cup D$ (what you asked, but without the absolute value signs). If you can show that $h$ is in fact a bijection, that will prove that the sets in question have equal cardinality. – Steve Kass Dec 20 '15 at 22:55

Here is my inductive of cardinality for finite sets:

$|\emptyset| = 0$.

If $x \in A$ then $|A \cup \{x\}| =|A|$. If $x \not\in A$ then $|A \cup \{x\}| =|A|+1$.

Theorem: If $A$ and $B$ are pairwise disjoint, then $|A \cup B| =|A| + |B|$.

Proof by induction on $|B|$.

If $|B| = 0$, then $A \cup B = A$, so the base case is proven.

Suppose it is true for $|B| \le n$. If $|B| =n+1$ and $|A \cap B| =\emptyset$, then $B = B' \cup \{x\}$ where $x \not\in B'$ and $x \not\in A$.

Then

$\begin{array}\\ |A \cup B| &=|A \cup (B' \cup \{x\})|\\ &=|(A \cup \{x\}) \cup B'|\\ &=|(A \cup \{x\})|+ |B'|\\ &=|A|+1+ |B'|\\ &=|A|+(|B'|+1)\\ &=|A|+|B|\\ \end{array}$