Proof

(related to Lemma: Finite Cardinal Numbers and Set Operations)

Let \(X, Y, U\) and \(W\) be finite sets.

(1)

We want to show that from \(|X|=|Y|, |U|=|W|\) and \(X\cap U=\emptyset, Y\cap W=\emptyset\) it follows for set unions that \(|X\cup U|=|Y\cup W|=|X|+|U|=|Y|+|W|\).

(2)

We want to show that from \(|X|=|Y|\) and \(|U|=|W|\) it follows for the Cartesian products that \(|X\times U|=|Y\times W|=|X|\cdot|U|=|Y|\cdot|W|\) * As in (1) from \(|X|=|Y|, |U|=|W|\) it follows that there are bijective maps \(f:X\mapsto Y\) and \(g:U\mapsto W\). * We define a new map \[h:\begin{cases} X\times U&\mapsto Y\times W\\ (a,b)&\mapsto (f(a),g(b)) \end{cases}\] * For a fixed cardinal number \(|X|\) we prove by induction on the cardinal number \(|U|=n\in\mathbb N\). * For \(n=0\) we have \(U=\emptyset\) and \(W=g(U)=g(\emptyset)=\emptyset\). Therefore \(h(X\times \emptyset)=h(\emptyset)=f(\emptyset)=\emptyset\). Thus it follows trivially that \(h\) is bijective as \(f\). * Thus \(|X\times\emptyset|=|Y\times\emptyset|=|X|\cdot|\emptyset|=|Y|\cdot|\emptyset|=0\), as required. * Let the claim \[(|X|=|Y|\wedge |U_0|=|W_0|)\Rightarrow|X\times U_0|=|Y\times W_0|=|X|\cdot|U_0|=|Y|\cdot|W_0|\] be proven for all \(U_0,W_0\) with \(|U_0|=|W_0|=n_0\ge 0\). * We observe that \(|X|=|X \times \{U_0\}|\), since the set \(\{U_0\}\) has only one element1.
* For the set \(U=U_0 \cup \{U_0\}\) we have then \[X\times U=X\times(U_0 \cup \{U_0\})=(X\times U_0) \cup (X\times \{U_0\}).\] * Taking the cardinal numbers on both sides we find \[|X\times U|=|(X\times U_0) \cup (X\times \{U_0\})|=|(X\times U_0)| + |(X\times \{U_0\})|,\] where the last equation follows from (1) and the fact that \((X\times U_0) \cap (X\times \{U_0\})=\emptyset\).2 * Therefore we have \[|X\times U|=|X|\cdot|U_0|+|X|\cdot|\{U_0\}|=|X|\cdot n_0+|X|\cdot 1=|X|\cdot(n_0+1)=|X|\cdot(|U_0|+1)=|Y|\cdot(|W_0|+1)=|Y\times W|\] * The claim can analogously be proven by induction for a fixed cardinal number \(|U|\) on the cardinal number \(|X|=n\in\mathbb N\).


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Ebbinghaus, H.-D.: "Einf├╝hrung in die Mengenlehre", BI Wisschenschaftsverlag, 1994, 3th Edition

Footnotes


  1. We also could have used \(\{\emptyset\}\) or any other set with only one element. 

  2. Note: There is no pair \((a,b)\) for which both \((a,b)\in (X\times \{U_0\})\) and \((a,b)\in (X\times U_0)\) can be true simultaneously, otherwise \(b\) would equal a set \(U_0\) which contains itself \(\{U_0\}\), which is forbidden by the axiom of foundation