Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

9.3: Cardinality of a Union

( \newcommand{\kernel}{\mathrm{null}\,}\)

We know that if A and B are disjoint, then the cardinality of AB is #A+#B. Here is a formula that works even when the sets are not disjoint:

Proposition 9.3.1.

For any finite sets A and B, we have

\boldsymbol{#(A \cup B)=\# A +\# B-\#(A \cap B).}

Proof

From Exercise 4.5.6, we know that AB, BA, and AB are pairwise-disjoint, and that their union is AB, so #(AB)+#(BA)+#(AB)=#((AB)(BA)(AB))=#(AB).

Also, we have #A=#((AB)(AB))=#(AB)+#(AB)

(First: Exercise 4.5.4(2) Second: Exercise 4.5.5(4)).

Similarly, we have #B=#(BA)+#(AB).

Therefore #A+#B=(#(AB)+#(AB))+(#(BA)+#(AB))=#(AB)+#(BA)+2#(AB)=#(AB)+#(AB).

The desired conclusion is obtained by subtracting #(AB) from both sides.

clipboard_ee5684fbd022ddfa4a7eda378d37eca3f.png
Figure 9A. The sum #A+#B includes all the elements of AB, but counts the elements of AB twice, so #A+#B=#(AB)+#(AB). Therefore #(AB)=#A+#B#(AB).

Example 9.3.2.

Let A={p,r,o,n,g} and B={h,o,r,n,s}. Then

Solution

#A=5,#B=5, and #(AB)=#{r,o,n}=3,

so Proposition 9.3.1 tells us that #(AB)=#A+#B#(AB)=5+53=7.

This is correct, since #(A ∪ B) = #{p,r, o, n, g, h,s} = 7.

Example 9.3.3.

Every one of the 4000 students at Modern U owns either a cell phone or an iPod (or both). Surveys show that:

  • 3500 students own a cell phone, and
  • 1000 students own an iPod.

How many students own both a cell phone and an iPod?

Solution

Let

  • S be the set of all students at Modern U,
  • C be the set of students who own a cell phone, and
  • I be the set of students who own an iPod.

Then, by assumption, #S=4000,#C=3500,#I=1000

Since every student owns either a cell phone or an iPod, we have S=CI. Therefore, Proposition 9.3.1 tells us that #S=#(CI)=#C+#I#(CI),

so #(CI)=#C+#I#S=3500+10004000=500

Hence, there are exactly 500 students who own both a cell phone and an iPod.

Exercise 9.3.4.

  1. Assume #U=15, #V=12, and #(UV)=4. Find #(UV).
  2. Assume #R=13, #S=17, and #(RS)=25. Find #(RS).
  3. Assume #J=300, #(JL)=500, and #(JL)=150. Find #L.
  4. At a small university, there are 90 students that are taking either Calculus or Linear Algebra (or both). If the Calculus class has 70 students, and the Linear Algebra class has 35 students, then how many students are taking both Calculus and Linear Algebra?
  5. (harder) Suppose A, B, and C are finite sets. Show #(ABC)=#A+#B+#C#(AB)#(AC)#(BC)+#(ABC).
    [Hint: We have formulas for #((AB)C) and #(AB). Another useful formula comes from the equality (AB)C=(AC)(BC).].]

The following exercises are examples of another type of application of the formula for the cardinality of a union.

Exercise 9.3.5.

  1. Suppose A and B are subsets of a finite set C. Show that if #A+#B>#C, then AB. [Hint: Use Proposition 9.3.1 to show that #(AB)0.]
  2. Show that if A is a set of at least 600 natural numbers that are less than 1000, then two of the numbers in A differ by exactly 100. [Hint: Let B={a+100aA}, and use the preceding exercise to show that AB.]

Exercise 9.3.6.

  1. Suppose A1,A2,,An are finite sets. Show #(A1A2An)#A1+#A2++#An.
    [Hint: The induction step uses Proposition 9.3.1.]
  2. Prove the Pigeonhole Principle (9.2.1).
    [Hint: The contrapositive states that if #Ai1 for every i, then #(A1A2An)n.]

Remark 9.3.7.

Generalizing Exercise 9.3.4(5), the Inclusion-Exclusion formula calculates the cardinality of the union of any number of sets: |A1An|=ni=1|Ai|1i<jn|AiAj|+1i<j<kn|AiAjAk|+(1)n+1|A1An|.

(The sign +/− depends on the number of sets being intersected: odd intersections are added, and even intersections are subtracted, which agrees with both Proposition 9.3.1 and Exercise 9.3.4(5).) We do not need this formula, but you can read about it in a Combinatorics textbook (or on Wikipedia).


This page titled 9.3: Cardinality of a Union is shared under a CC BY-NC-SA 2.0 license and was authored, remixed, and/or curated by Dave Witte Morris & Joy Morris.

Support Center

How can we help?