Cuál es la cardinalidad de la Unión A∪B∪... ¿∪Z?

Question

He averiguado de que $|A \cup B| = |A| + |B| - |A \cap B| $

y

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

No he conseguido averiguar qué $|A \cup B \cup C \cup D|$ es igual a. ¿Cuál es la cardinalidad de $A \cup B \cup C \cup D$?

Además, ¿cómo se puede la pregunta generalizada: ¿Cuál es la cardinalidad de la Unión $A_1 \cup A_2 \cup ... \cup A_n$?

Answer 1

Se llama el principio de inclusión-exclusión y se parece a esto: $$\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|$ $

Answer 2

El hecho general de que buscas se llama el principio de inclusión-exclusión y se caracteriza por la los tipos de alterna sumas que has notado ya.

Página de la Wikipedia sobre este teorema contiene una prueba, así como algunas explicaciones.

Answer 3

Las otras respuestas vinculan a la fórmula genérica. Aquí es el específico para 4 sistemas:

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

No quiero escribirlo para 26 establece explícitamente, sin embargo. Tiene $2^{26} - 1 = 67108863$ sumandos marcas de verificación. Comienza con:

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