This portion is dedicated to some fun theorems and proofs that I personally think are kinda cool and simple enough so that it doesn't take much to write it down here. To those who rolled their eyes at the “universal algebra” section and its textbook appearance (I'm sorry, but I love textbooks just the way they are), this may be less demanding and boring.

2024/december/16.
\(2^X\), the power set!

There are many notations regarding the power set of a given set \(X\), but my favorite one is \(2^X\). Despite being a font of confusion at first sight, it relies on the useful information that for any set \(X\), the power set \(2^X\) has cardinality \(2^{|X|}.\) That's exactly what we will prove today with the help of a nice construction of a set with two elements (imagine a set with the "true" and "false" values) and some mappings. Though I'm not entirely sure, I think you can find analogous ideas in some Number Theory demonstrations.

Definition. Two sets A and B have the same cardinality if there exists a bijection \(f : A \rightarrow B\). We denote \(|A| = |B|.\)

Say \(X\) is a set and \(2^X = \{A : A \subseteq X\}.\) Lets define \(\mathcal{B} = \langle f: X \rightarrow \{0,1\} \rangle\) as the set of mappings from \(X\) to \(\{0,1\}.\) Lets also define \(\phi : 2^X \rightarrow \mathcal{B}\) such that, for any \(A\) subset of \(X\), \(\phi(A) = f_A : X \rightarrow \{0,1\}\) where:

1. For any \(x \in X\), \(f_A(x) = 1\) when \(x \in A.\)
2. For any \(x \in X\), \(f_A(x) = 0\) when \(x \notin A.\)

Then, lets make another definition which will guide our proof. We define \(\psi : \mathcal{B} \rightarrow 2^X\) such that, for any \(f \in \mathcal{B}\), \(\psi(f) = A_f = \{x \in X : f(x) = 1 \} \subseteq X.\)

The objective is to prove that \(\phi\) and \(\psi\) are both bijections, and for this we will use the fact that \(g : A \rightarrow B\) is a bijection if and only if there exists \(g^{-1} : B \rightarrow A\) such that \(g^{-1} \circ g = id_A\) and \(g \circ g^{-1} = id_B.\)

For any \(A \subseteq X\), \((\psi \circ \phi)(A)\) = \(\psi(\phi(A)) = \psi(f_A) = A_{f_A}.\)
If \(x \in A\), then \(f_A(x) = 1\). Thus, \(x \in A_{f_A}\) so that \(A \subseteq A_{f_A}.\)
If \(x \in A_{f_A}\), then \(f_A(x) = 1\). Thus, \(x \in A\) so that \(A_{f_A} \subseteq A\).
These inclusions tell us that \(A_{f_A} = A.\)
Therefore, \((\psi \circ \phi)(A) = id_{2^X}(A) = A\), which means that \(\psi \circ \phi = id_{2^X}.\)

For any \(f \in \mathcal{B}\), \((\phi \circ \psi)(f) = \phi(\psi(f)) =\) \( \phi(A_f) = f_{A_f} : X \rightarrow \{0,1\}.\)
If \(f(x) = 1\), then \(x \in A_f\) so that \(f_{A_f}(x) = 1.\)
If \(f(x) = 0\), then \(x \notin A_f\) so that \(f_{A_f}(x) = 0.\)
These results tells us that \(f_{A_f} = f.\)
Therefore, \((\phi \circ \psi)(f) = f_{A_f} = f = id_{\mathcal{B}}(f)\) which means that \(\phi \circ \psi = id_{\mathcal{B}}.\)

Thus, as we wanted to prove, \(\phi\) and \(\psi\) are both bijections. Therefore, the definition we stated at the beginning let us finally conclude that \(|2^X| = |\mathcal{B}| = |\{0,1\}|^{|X|} = 2^{|X|}.\) \(\square\)