2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – seeker Dec 20 '15 at 21:18
  • $\begingroup$ 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? $\endgroup$ – JimmyK4542 Dec 20 '15 at 21:18
  • $\begingroup$ @JimmyK4542 fixed it. Thank you. $\endgroup$ – dreamin Dec 20 '15 at 21:21
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Steve Kass Dec 20 '15 at 21:38
  • $\begingroup$ 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? $\endgroup$ – dreamin Dec 20 '15 at 21:41
  • $\begingroup$ 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|$? $\endgroup$ – JimmyK4542 Dec 20 '15 at 21:46
  • $\begingroup$ @SteveKass I would then I have to come up with a bijective function from |$A \cup B$| to |$C \cup D$|? $\endgroup$ – dreamin Dec 20 '15 at 22:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Steve Kass Dec 20 '15 at 22:55
1
$\begingroup$

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

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