Product of Cardinals is Associative

From ProofWiki
Jump to navigation Jump to search


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


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

where $\mathbf {a b}$ denotes the product of $\mathbf a$ and $\mathbf b$.


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

By definition of product of cardinals:

$\mathbf a \paren {\mathbf {b c} }$ is the cardinal associated with $A \times \paren {B \times C}$.

Consider the mapping $f: A \times \paren {B \times C} \to \paren {A \times B} \times C$ defined as:

$\forall a \in A, b \in B, c \in C: \map f {a, \tuple {b, c} } = \tuple {\tuple {a, b}, c}$

Let $a_1, a_2 \in A, b_1, b_2 \in B, c_1, c_2 \in C$ such that:

$\map f {a_1, \tuple {b_1, c_1} } = \map f {a_2, \tuple {b_2, c_2} }$


\(\ds \map f {a_1, \tuple {b_1, c_1} }\) \(=\) \(\ds \map f {a_2, \tuple {b_2, c_2} }\)
\(\ds \leadsto \ \ \) \(\ds \tuple {\tuple {a_1, b_1}, c_1}\) \(=\) \(\ds \tuple {\tuple {a_2, b_2}, c_2}\) Definition of $f$
\(\ds \leadsto \ \ \) \(\ds \tuple {a_1, b_1}\) \(=\) \(\ds \tuple {a_2, b_2}\) Equality of Ordered Tuples
\(\, \ds \land \, \) \(\ds c_1\) \(=\) \(\ds c_2\)
\(\ds \leadsto \ \ \) \(\ds a_1\) \(=\) \(\ds a_2\) Equality of Ordered Tuples
\(\, \ds \land \, \) \(\ds b_1\) \(=\) \(\ds b_2\)
\(\, \ds \land \, \) \(\ds c_1\) \(=\) \(\ds c_2\)
\(\ds \leadsto \ \ \) \(\ds a_1\) \(=\) \(\ds a_2\) Equality of Ordered Tuples
\(\, \ds \land \, \) \(\ds \tuple {b_1, c_1}\) \(=\) \(\ds \tuple {b_2, c_2}\)
\(\ds \leadsto \ \ \) \(\ds \tuple {a_1, \tuple {b_1, c_1} }\) \(=\) \(\ds \tuple {a_2, \tuple {b_2, c_2} }\) Equality of Ordered Tuples

Thus $f$ is an injection.

\(\ds \forall x \in \paren {A \times B} \times C: \exists a \in A, b \in B, c \in C: \, \) \(\ds x\) \(=\) \(\ds \tuple {\tuple {a, b}, c}\)
\(\ds \) \(=\) \(\ds \map f {a, \tuple {b, c} }\)

Thus $f$ is a surjection.

So $f$ is both an injection and a surjection, and so by definition a bijection.

Thus a bijection has been established between $A \times \tuple {B \times C}$ and $\tuple {A \times B} \times C$.

It follows by definition that $A \times \tuple {B \times C}$ and $\tuple {A \times B} \times C$ are equivalent.

The result follows by definition of cardinal.