Sum of Cardinals is Associative

Jump to navigation Jump to search

Theorem

Let $\mathbf a$, $\mathbf b$ and $\mathbf c$ be cardinals.

Then:

$\mathbf a + \paren {\mathbf b + \mathbf c} = \paren {\mathbf a + \mathbf b} + \mathbf c$

where $\mathbf a + \mathbf b$ denotes the sum of $\mathbf a$ and $\mathbf b$.

Proof

Let $\mathbf a = \card A, \mathbf b = \card B$ and $\mathbf c = \card C$ for some sets $A$, $B$ and $C$.

Let $A, B, C$ be pairwise disjoint, that is:

$A \cap B = \O$
$B \cap C = \O$
$A \cap C = \O$

Then we can define:

$A \sqcup B := A \cup B$
$B \sqcup C := B \cup C$
$A \sqcup C := A \cup C$

where $A \sqcup B$ denotes the disjoint union of $A$ and $B$.

Then we have:

$\mathbf a + \mathbf b = \card {A \sqcup B} = \card {A \cup B}$
$\mathbf b + \mathbf c = \card {B \sqcup C} = \card {B \cup C}$

Then:

 $\ds \paren {A \cup B} \cap C$ $=$ $\ds \paren {A \cap C} \cup \paren {B \cap C}$ Intersection Distributes over Union $\ds$ $=$ $\ds \O \cup \O$ as $A \cap C = \O$ and $B \cap C = \O$ $\ds$ $=$ $\ds \O$ Union with Empty Set

Then:

 $\ds \card {\paren {A \cup B} \cup C}$ $=$ $\ds \card {A \cup B} + \card C$ as $\paren {A \cup B} \cap C = \O$ from above $\ds$ $=$ $\ds \paren {\mathbf a + \mathbf b} + \mathbf c$ Definition of Sum of Cardinals

Similarly:

 $\ds A \cap \paren {B \cup C}$ $=$ $\ds \paren {A \cap B} \cup \paren {A \cap C}$ Intersection Distributes over Union $\ds$ $=$ $\ds \O \cup \O$ as $A \cap B = \O$ and $A \cap C = \O$ $\ds$ $=$ $\ds \O$ Union with Empty Set

Then:

 $\ds \card {A \cup \paren {B \cup C} }$ $=$ $\ds \card A + \card {B \cup C}$ as $A \cap \paren {B \cup C} = \O$ from above $\ds$ $=$ $\ds \mathbf a + \paren {\mathbf b + \mathbf c}$ Definition of Sum of Cardinals

Finally note that from Union is Associative:

$A \cup \paren {B \cup C} = \paren {A \cup B} \cup C$

$\blacksquare$