15
$\begingroup$

I have figured out that $|A \cup B| = |A| + |B| - |A \cap B| $

and that

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$.

I have not managed to figure out what $|A \cup B \cup C \cup D|$ is equal to. What is the cardinality of $A \cup B \cup C \cup D$?

Furthermore, how can one the generalized question: What is the cardinality of the union $A_1 \cup A_2 \cup ... \cup A_n$?

$\endgroup$
20
$\begingroup$

The general fact you are looking for is called the Inclusion-Exclusion Principle, and is characterized by the kinds of alternating sums you've noticed already.

The Wikipedia page on this theorem contains a proof, as well as some explanations.

$\endgroup$
25
$\begingroup$

It's called the inclusion-exclusion principle and it looks like this: $$\left|\bigcup_{i=1}^n A_i\right| = {} \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i\cap A_j| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|$$

$\endgroup$
12
$\begingroup$

The other answers link to the generic formula. Here is the specific one for 4 sets:

$ |A \cup B \cup C \cup D| = |A|+|B|+|C|+|D|-|A \cap B|-|A \cap C|-|A \cap D|-|B \cap C|-|B \cap D|-|C \cap D|+|A \cap B \cap C|+|A \cap B \cap D|+|A \cap C \cap D|+|B \cap C \cap D|-|A \cap B \cap C \cap D| $

You don't want to write it down for 26 sets explicitely, though. It has $2^{26} - 1 = 67108863$ summands. It starts with:

$ |A \cup B \cup C \cup D \cup E \cup F \cup G \cup H \cup I \cup J \cup K \cup L \cup M \cup N \cup O \cup P \cup Q \cup R \cup S \cup T \cup U \cup V \cup W \cup X \cup Y \cup Z| = |A|+|B|+|C|+|D|+|E|+|F|+|G|+|H|+|I|+|J|+|K|+|L|+|M|+|N|+|O|+|P|+|Q|+|R|+|S|+|T|+|U|+|V|+|W|+|X|+|Y|+|Z|-|A \cap B|-|A \cap C|-|A \cap D|-|A \cap E|-|A \cap F|-|A \cap G|-|A \cap H|-|A \cap I|-|A \cap J|-|A \cap K|-|A \cap L|-|A \cap M|-|A \cap N|-|A \cap O|-|A \cap P|-|A \cap Q|-|A \cap R|-|A \cap S|-|A \cap T|-|A \cap U|-|A \cap V|-|A \cap W|-|A \cap X|-|A \cap Y|-|A \cap Z|-|B \cap C|-|B \cap D|-|B \cap E|-|B \cap F|-|B \cap G|-|B \cap H|-|B \cap I|-|B \cap J|-|B \cap K|-|B \cap L|-|B \cap M|-|B \cap N|-|B \cap O|-|B \cap P|-|B \cap Q|-|B \cap R|-|B \cap S|-|B \cap T|-|B \cap U|-|B \cap V|-|B \cap W|-|B \cap X|-|B \cap Y|-|B \cap Z|-|C \cap D|-|C \cap E|-|C \cap F|-|C \cap G|-|C \cap H|-|C \cap I|-|C \cap J|-|C \cap K|-|C \cap L|-|C \cap M|-|C \cap N|-|C \cap O|-|C \cap P|-|C \cap Q|-|C \cap R|-|C \cap S|-|C \cap T|-|C \cap U|-|C \cap V|-|C \cap W|-|C \cap X|-|C \cap Y|-|C \cap Z|-|D \cap E|-|D \cap F|-|D \cap G|-|D \cap H|-|D \cap I|-|D \cap J|-|D \cap K|-|D \cap L|-|D \cap M|-|D \cap N|-|D \cap O|-|D \cap P|-|D \cap Q|-|D \cap R|-|D \cap S|-|D \cap T|-|D \cap U|-|D \cap V|-|D \cap W|-|D \cap X|-|D \cap Y|-|D \cap Z|-|E \cap F|-|E \cap G|-|E \cap H|-|E \cap I|-|E \cap J|-|E \cap K|-|E \cap L|-|E \cap M|-|E \cap N|-|E \cap O|-|E \cap P|-|E \cap Q|-|E \cap R|-|E \cap S|-|E \cap T|-|E \cap U|-|E \cap V|-|E \cap W|-|E \cap X|-|E \cap Y|-|E \cap Z|-|F \cap G|-|F \cap H|-|F \cap I|-|F \cap J|-|F \cap K|-|F \cap L|-|F \cap M|-|F \cap N|-|F \cap O|-|F \cap P|-|F \cap Q|-|F \cap R|-|F \cap S|-|F \cap T|-|F \cap U|-|F \cap V|-|F \cap W|-|F \cap X|-|F \cap Y|-|F \cap Z|-|G \cap H|-|G \cap I|-|G \cap J|-|G \cap K|-|G \cap L|-|G \cap M|-|G \cap N|-|G \cap O|-|G \cap P|-|G \cap Q|-|G \cap R|-|G \cap S|-|G \cap T|-|G \cap U|-|G \cap V|-|G \cap W|-|G \cap X|-|G \cap Y|-|G \cap Z|-|H \cap I|-|H \cap J|-|H \cap K|-|H \cap L|-|H \cap M|-|H \cap N|-|H \cap O|-|H \cap P|-|H \cap Q|-|H \cap R|-|H \cap S|-|H \cap T|-|H \cap U|-|H \cap V|-|H \cap W|-|H \cap X|-|H \cap Y|-|H \cap Z|-|I \cap J|-|I \cap K|-|I \cap L|-|I \cap M|-|I \cap N|-|I \cap O|-|I \cap P|-|I \cap Q|-|I \cap R|-|I \cap S|-|I \cap T|-|I \cap U|-|I \cap V|-|I \cap W|-|I \cap X|-|I \cap Y|-|I \cap Z|-|J \cap K|-|J \cap L|-|J \cap M|-|J \cap N|-|J \cap O|-|J \cap P|-|J \cap Q|-|J \cap R|-|J \cap S|-|J \cap T|-|J \cap U|-|J \cap V|-|J \cap W|-|J \cap X|-|J \cap Y|-|J \cap Z|-|K \cap L|-|K \cap M|-|K \cap N|-|K \cap O|-|K \cap P|-|K \cap Q|-|K \cap R|-|K \cap S|-|K \cap T|-|K \cap U|-|K \cap V|-|K \cap W|-|K \cap X|-|K \cap Y|-|K \cap Z|-|L \cap M|-|L \cap N|-|L \cap O|-|L \cap P|-|L \cap Q|-|L \cap R|-|L \cap S|-|L \cap T|-|L \cap U|-|L \cap V|-|L \cap W|-|L \cap X|-|L \cap Y|-|L \cap Z|-|M \cap N|-|M \cap O|-|M \cap P|-|M \cap Q|-|M \cap R|-|M \cap S|-|M \cap T|-|M \cap U|-|M \cap V|-|M \cap W|-|M \cap X|-|M \cap Y|-|M \cap Z|-|N \cap O|-|N \cap P|-|N \cap Q|-|N \cap R|-|N \cap S|-|N \cap T|-|N \cap U|-|N \cap V|-|N \cap W|-|N \cap X|-|N \cap Y|-|N \cap Z|-|O \cap P|-|O \cap Q|-|O \cap R|-|O \cap S|-|O \cap T|-|O \cap U|-|O \cap V|-|O \cap W|-|O \cap X|-|O \cap Y|-|O \cap Z|-|P \cap Q|-|P \cap R|-|P \cap S|-|P \cap T|-|P \cap U|-|P \cap V|-|P \cap W|-|P \cap X|-|P \cap Y|-|P \cap Z|-|Q \cap R|-|Q \cap S|-|Q \cap T|-|Q \cap U|-|Q \cap V|-|Q \cap W|-|Q \cap X|-|Q \cap Y|-|Q \cap Z|-|R \cap S|-|R \cap T|-|R \cap U|-|R \cap V|-|R \cap W|-|R \cap X|-|R \cap Y|-|R \cap Z|-|S \cap T|-|S \cap U|-|S \cap V|-|S \cap W|-|S \cap X|-|S \cap Y|-|S \cap Z|-|T \cap U|-|T \cap V|-|T \cap W|-|T \cap X|-|T \cap Y|-|T \cap Z|-|U \cap V|-|U \cap W|-|U \cap X|-|U \cap Y|-|U \cap Z|-|V \cap W|-|V \cap X|-|V \cap Y|-|V \cap Z|-|W \cap X|-|W \cap Y|-|W \cap Z|-|X \cap Y|-|X \cap Z|-|Y \cap Z|+|A \cap B \cap C|+|A \cap B \cap D|+|A \cap B \cap E|+|A \cap B \cap F|+|A \cap B \cap G|+|A \cap B \cap H|+|A \cap B \cap I|+|A \cap B \cap J|+|A \cap B \cap K|+|A \cap B \cap L|+|A \cap B \cap M|+|A \cap B \cap N|+|A \cap B \cap O|+|A \cap B \cap P|+|A \cap B \cap Q|+|A \cap B \cap R|+|A \cap B \cap S|+|A \cap B \cap T|+|A \cap B \cap U|+|A \cap B \cap V|+|A \cap B \cap W|+|A \cap B \cap X|+|A \cap B \cap Y|+|A \cap B \cap Z|+|A \cap C \cap D|+|A \cap C \cap E|+|A \cap C \cap F|+|A \cap C \cap G|+|A \cap C \cap H|+|A \cap C \cap I|+|A \cap C \cap J|+|A \cap C \cap K|+|A \cap C \cap L|+|A \cap C \cap M|+|A \cap C \cap N|+|A \cap C \cap O|+|A \cap C \cap P|+|A \cap C \cap Q|+|A \cap C \cap R|+|A \cap C \cap S|+|A \cap C \cap T|+|A \cap C \cap U|+|A \cap C \cap V|+|A \cap C \cap W|+|A \cap C \cap X|+|A \cap C \cap Y|+|A \cap C \cap Z|+|A \cap D \cap E|+|A \cap D \cap F|+|A \cap D \cap G|+|A \cap D \cap H|+|A \cap D \cap I|+|A \cap D \cap J|+|A \cap D \cap K|+|A \cap D \cap L|+|A \cap D \cap M|+|A \cap D \cap N|+|A \cap D \cap O|+|A \cap D \cap P|+|A \cap D \cap Q|+|A \cap D \cap R|+|A \cap D \cap S|+|A \cap D \cap T|+|A \cap D \cap U|+|A \cap D \cap V|+|A \cap D \cap W|+|A \cap D \cap X|+|A \cap D \cap Y|+|A \cap D \cap Z|+|A \cap E \cap F|+|A \cap E \cap G|+|A \cap E \cap H|+|A \cap E \cap I|+|A \cap E \cap J|+|A \cap E \cap K|+|A \cap E \cap L|+|A \cap E \cap M|+|A \cap E \cap N|+|A \cap E \cap O|+|A \cap E \cap P|+|A \cap E \cap Q|+|A \cap E \cap R|+|A \cap E \cap S|+|A \cap E \cap T|+|A \cap E \cap U|+|A \cap E \cap V|+|A \cap E \cap W|+|A \cap E \cap X|+|A \cap E \cap Y|+|A \cap E \cap Z|+|A \cap F \cap G|+|A \cap F \cap H|+|A \cap F \cap I|+|A \cap F \cap J|+|A \cap F \cap K|+|A \cap F \cap L|+|A \cap F \cap M|+|A \cap F \cap N|+|A \cap F \cap O|+|A \cap F \cap P|+|A \cap F \cap Q|+|A \cap F \cap R|+|A \cap F \cap S|+|A \cap F \cap T|+|A \cap F \cap U|+|A \cap F \cap V|+|A \cap F \cap W|+|A \cap F \cap X|+|A \cap F \cap Y|+|A \cap F \cap Z|+|A \cap G \cap H|+|A \cap G \cap I|+|A \cap G \cap J|+|A \cap G \cap K|+|A \cap G \cap L|+|A \cap G \cap M|+|A \cap G \cap N|+|A \cap G \cap O|+|A \cap G \cap P|+|A \cap G \cap Q|+|A \cap G \cap R|+|A \cap G \cap S|+|A \cap G \cap T|+|A \cap G \cap U|+|A \cap G \cap V|+|A \cap G \cap W|+|A \cap G \cap X|+|A \cap G \cap Y|+|A \cap G \cap Z|+|A \cap H \cap I|+|A \cap H \cap J|+|A \cap H \cap K|+|A \cap H \cap L|+|A \cap H \cap M|+|A \cap H \cap N|+|A \cap H \cap O|+|A \cap H \cap P|+|A \cap H \cap Q|+|A \cap H \cap R|+|A \cap H \cap S|+|A \cap H \cap T|+|A \cap H \cap U|+|A \cap H \cap V|+|A \cap H \cap W|+|A \cap H \cap X|+|A \cap H \cap Y|+|A \cap H \cap Z|+|A \cap I \cap J|+|A \cap I \cap K|+|A \cap I \cap L|+|A \cap I \cap M|+|A \cap I \cap N|+|A \cap I \cap O|+|A \cap I \cap P|+|A \cap I \cap Q|+|A \cap I \cap R|+|A \cap I \cap S|+|A \cap I \cap T|+|A \cap I \cap U|+|A \cap I \cap V|+|A \cap I \cap W|+|A \cap I \cap X|+|A \cap I \cap Y|+|A \cap I \cap Z|+|A \cap J \cap K|+|A \cap J \cap L|+|A \cap J \cap M|+|A \cap J \cap N|+|A \cap J \cap O|+|A \cap J \cap P|+|A \cap J \cap Q|+|A \cap J \cap R|+|A \cap J \cap S|+|A \cap J \cap T|+|A \cap J \cap U|+|A \cap J \cap V|+|A \cap J \cap W|+|A \cap J \cap X|+|A \cap J \cap Y|+|A \cap J \cap Z|+|A \cap K \cap L|+|A \cap K \cap M|+|A \cap K \cap N|+|A \cap K \cap O| + ...$

$\endgroup$
  • $\begingroup$ That definitely took some time. $\endgroup$ – Mohammad Zuhair Khan Jan 20 '18 at 16:50
  • $\begingroup$ @MohammadZuhairKhan: I wrote 2 lines of Python to generate the markup. :) $\endgroup$ – Eric Duminil Jan 20 '18 at 16:52
  • $\begingroup$ And I thought you took the entire day since the question was asked just writing this. ;) $\endgroup$ – Mohammad Zuhair Khan Jan 20 '18 at 16:55

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.