In class I proved
For an arbitrary nonempty set $S$ there exist a bijection between the power set of $S$ and the set $\{0,1\}^S$.
The table below illustrates the proof. Consider $S=\{\blacktriangle,\diamond,\bullet,\star\}$. The table below indicates what the bijection should be. The top part of the table contains sixteen functions in $\{0,1\}^S$; the bottom part contains the subsets of $A$ that are related to the functions above them.
$f_1$ | $f_2$ | $f_3$ | $f_4$ | $f_5$ | $f_6$ | $f_7$ | $f_8$ | $f_9$ | $f_{10}$ | $f_{11}$ | $f_{12}$ | $f_{13}$ | $f_{14}$ | $f_{15}$ | $f_{16}$ | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
$\blacktriangle$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
$\diamond$ | $0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ |
$\bullet$ | $0$ | $0$ | $1$ | $1$ | $0$ | $0$ | $1$ | $1$ | $0$ | $0$ | $1$ | $1$ | $0$ | $0$ | $1$ | $1$ |
$\star$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ |
s u b s e t |
$\emptyset$ | $\{\star\}$ | $\{\bullet\}$ | $\left\{\begin{array}{c}\!\!\bullet\!\!\\\!\!\star\!\! \end{array}\right\}$ | $\{\diamond\}$ | $\left\{\begin{array}{c}\!\!\diamond\!\!\\\!\!\star\!\!\end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\diamond\!\!\\\!\!\bullet\!\!\end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\diamond\!\!\\\!\!\bullet\!\!\\\!\!\star\!\! \end{array}\right\}$ | $\{\blacktriangle\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\star\!\!\end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\bullet\!\! \end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\bullet\!\!\\\!\!\star\!\! \end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\diamond\!\! \end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\diamond\!\!\\\!\!\star\!\! \end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\diamond\!\!\\\!\!\bullet\!\! \end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\diamond\!\!\\\!\!\bullet\!\!\\\!\!\star\!\! \end{array}\right\}$ |
The function \[ \Phi: \mathcal{P}(S) \to \{0,1\}^S \] defined in the proof of Proposition 3.2.17 is given in the columns of the above table. For example, in the above table, if $A = \{\blacktriangle,\bullet,\star\}$, then $\Phi(A) = f_{12}$, that is the function \[ f_{12}(\blacktriangle)=1, \quad f_{12}(\diamond)=0, \quad f_{12}(\bullet)=1, \quad f_{12}(\star)=1. \]
Let $S$ be a nonempty set. Then there is no surjection with domain $S$ and codomain $\mathcal{P}(S)$.
In the proof of this theorem we prove \[ \forall\mkern+1.2mu \Theta: S \to \mathcal{P}(S) \quad \exists\mkern+1.5mu A \subseteq S \quad \forall\mkern+1.2mu x \in S \quad \Theta(x) \neq A. \] To prove the preceding displayed statement, let $\Theta: S \to \mathcal{P}(S)$ be an arbitrary function with domain \(S\) and codomain \(\mathcal{P}(S)\). To prove that $\Theta$ is not a surjection, we need to discover a subset $A$ of $S$ such that \[ \forall\mkern+1.2mu x \in S \quad \Theta(x) \neq A. \] The definition of such subset $A$ is truly ingenious, due to Georg Cantor: \[ A = \bigl\{ s \in S : s \not\in \Theta(s) \bigr\}. \]
I want to illustrate the universality of the definition of \(A\) on the example considered in the preceding item. Let \[ S=\{\blacktriangle,\diamond,\bullet,\star\}. \]
$f_1$ | $f_2$ | $f_3$ | $f_4$ | $f_5$ | $f_6$ | $f_7$ | $f_8$ | $f_9$ | $f_{10}$ | $f_{11}$ | $f_{12}$ | $f_{13}$ | $f_{14}$ | $f_{15}$ | $f_{16}$ | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
$\blacktriangle$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
$\diamond$ | $0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ |
$\bullet$ | $0$ | $0$ | $1$ | $1$ | $0$ | $0$ | $1$ | $1$ | $0$ | $0$ | $1$ | $1$ | $0$ | $0$ | $1$ | $1$ |
$\star$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ | $0$ | $1$ |
s u b s e t |
$\emptyset$ | $\{\star\}$ | $\{\bullet\}$ | $\left\{\begin{array}{c}\!\!\bullet\!\!\\\!\!\star\!\! \end{array}\right\}$ | $\{\diamond\}$ | $\left\{\begin{array}{c}\!\!\diamond\!\!\\\!\!\star\!\!\end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\diamond\!\!\\\!\!\bullet\!\!\end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\diamond\!\!\\\!\!\bullet\!\!\\\!\!\star\!\! \end{array}\right\}$ | $\{\blacktriangle\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\star\!\!\end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\bullet\!\! \end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\bullet\!\!\\\!\!\star\!\! \end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\diamond\!\! \end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\diamond\!\!\\\!\!\star\!\! \end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\diamond\!\!\\\!\!\bullet\!\! \end{array}\right\}$ | $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\diamond\!\!\\\!\!\bullet\!\!\\\!\!\star\!\! \end{array}\right\}$ |
How to read the above table? The top part of the table lists all the functions with domain $S=\{\blacktriangle,\diamond,\bullet,\star\}$ and codomain \(\{0,1\}\). For example, the function \(f_{12} : S\to \{0,1\}\) is the following function \[ f_{12}(\blacktriangle)=1, \quad f_{12}(\diamond)=0, \quad f_{12}(\bullet)=1, \quad f_{12}(\star)=1. \] In the bottom part of the table, below the function \(f_{12}\) you can find the subset $\{\blacktriangle,\bullet,\star\}$ of \(S = \{\blacktriangle,\diamond,\bullet,\star\}\).
Is there a relationship between the function \(f_{12}\) and the subset $\{\blacktriangle,\bullet,\star\}$?
This relationship is the key for the proof of Proposition 3.2.22 in the class notes. A more detailed proof of this proposition is given below in this post.
Let $S$ be a nonempty set and let \(A \subseteq S\). The function \({\large \chi}_{_{\mkern -3mu \Large A}}\mkern -4mu: S \to \{0,1\}\) defined by \[ \forall \mkern 1mu x \in S \qquad {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = \begin{cases} 1 & \text{if} \quad x \in A \\[5pt] 0 & \text{if} \quad x \in S\setminus A \end{cases} \] is called the indicator function of \(A\) relative to \(S\).
In the next two lemmas, I present two properties of indicator functions. The proofs of these lemmas are straightforward, but I include detailed proofs to illustrate how reasoning proceeds even in the most straightforward cases.
Let \(S\) be a nonempty set, \(A\subseteq S\) and let \({\large \chi}_{_{\mkern -3mu \Large A}}:S\to \{0,1\}\) be the indicator function for \(A\). Then \[ \forall \mkern 1mu x \in S \qquad {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1 \quad \Leftrightarrow \quad x \in A. \]
The statement \[ \forall \mkern 1mu x \in S \qquad {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1 \quad \Leftrightarrow \quad x \in A \] involves a universal quantifier. To prove a statement that involves a universal quantifier, we begin by letting the quantified element be arbitrary. So, let \(x \in S\) be arbitrary.
Part 1. The implication \[ x \in A \quad \Rightarrow \quad {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1 \] follows from the first line in the definition of \({\large \chi}_{_{\mkern -3mu \Large A}}\) which says "if \(x\in A\), then \({\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1\)."
Part 2. The implication \[ {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1 \quad \Rightarrow \quad x \in A \] follows from the second line in the definition of \({\large \chi}_{_{\mkern -3mu \Large A}}\) which says "if \(x\notin A\), then \({\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 0\)." The contrapositive of this implication from the definition is \[ {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) \ne 0 \quad \Rightarrow \quad x \in A. \] However, since \({\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) \in \{0,1\}\), we have \[ {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1 \ \lor \ {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 0. \] Therefore, by disjunctive syllogism, we deduce \[ {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) \ne 0 \quad \Leftrightarrow \quad {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1. \] Hence, the implication from the second line in the definition of \({\large \chi}_{_{\mkern -3mu \Large A}}\) is equivalent to \[ {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1 \quad \Rightarrow \quad x \in A. \]
Since \(x\in S\) was arbitrary, we proved \[ \forall \mkern 1mu x \in S \qquad {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1 \quad \Leftrightarrow \quad x \in A. \]It is common to end a mathematical proof with a symbol. In some texts, the symbol ■ is used instead. In some texts, the proofs end with ■. Others use QED, short for the Latin phrase quod erat demonstrandum, meaning “that which was to be demonstrated.” On this webpage, I use a custom design QED that combines the black square ■ with the abbreviation QED.
Let \(S\) be a nonempty set. For every \(f \in \{0,1\}^{\large S}\) there exists \(A\subseteq S\) such that \(f = {\large \chi}_{_{\mkern -3mu \Large A}}\).
Let \(f: S \to \{0,1\}\) be arbitrary. Set \[ A = \bigl\{ x\in S : f(x) = 1 \bigr\}. \] Next we prove \(f = {\large \chi}_{_{\mkern -3mu \Large A}}\). That is, we must prove \[ \forall \mkern 1mu x \in S \qquad f(x) = {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x). \] Let \(x\in S\) be arbitrary. Since \(f: S \to \{0,1\}\) we have two exclusive cases. Case 1: \(f(x) = 1\). By the definition of \(A\), in this case we have \(x\in A\). Therefore, \({\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1\), and hence \(f(x) = {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x)\). Case 2: \(f(x) = 0\). In this case \(x\notin A\). Therefore, \({\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 0\), and hence \(f(x) = {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x)\). Thus, in each case \(f(x) = {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x)\). Since \(x\in S\) was arbitrary, we have proved \[ \forall \mkern 1mu x \in S \qquad f(x) = {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x). \]
Let $S$ be a nonempty set. The function \(\Phi: \mathcal{P}(S) \to \{0,1\}^S\) defined by \[ \forall\mkern 1mu A \in \mathcal{P}(S) \qquad \Phi(A) = {\large \chi}_{_{\mkern -3mu \Large A}} \] is a bijection.
In Theorem 3.2.17 in the class notes we proved that a function is a bijection if and only if it is invertible. In this proof, we will prove that the function \(\Phi: \mathcal{P}(S) \to \{0,1\}^S\) defined in the proposition is invertible by defining its inverse.
To get inspiration for the definition of the inverse of \(\Phi: \mathcal{P}(S) \to \{0,1\}^S\) we look at the table in the first item in today's post. Ask yourself: where in the table do we see the function \(\Phi: \mathcal{P}(S) \to \{0,1\}^S\)? Since the function \(\Phi: \mathcal{P}(S) \to \{0,1\}^S\) maps subsets into functions, and the subsets are at the bottom part of the table and the functions are at the top part of the table, we conclude that we see the function \(\Phi: \mathcal{P}(S) \to \{0,1\}^S\) as associating functions at the top of the table to the sets at the bottom. Therefore its inverse associates the sets at the bottom of the table to the functions at the top.
I asked this question immediately below the table: How are the sets at the bottom associated with the functions at the top? Here is the connection expressed as the function \(\Psi : \{0,1\}^S \to \mathcal{P}(S)\) defined as \[ \forall\mkern 1mu f \in \{0,1\}^S \qquad \Psi(f) = \bigl\{ x \in S : f(x) = 1\bigr\}. \] To prove that \(\Psi : \{0,1\}^S \to \mathcal{P}(S)\) is the inverse of \(\Phi: \mathcal{P}(S) \to \{0,1\}^S\) we must prove two statements: \[ \forall\mkern 1mu A \in \mathcal{P}(S) \qquad \Psi\bigl( \Phi(A) \bigr) = A, \] and \[ \forall\mkern 1mu f \in \{0,1\}^S \qquad \Phi\bigl( \Psi(f) \bigr) = f. \]
Part 1. First we prove \[ \forall\mkern 1mu A \in \mathcal{P}(S) \qquad \Psi\bigl( \Phi(A) \bigr) = A, \] Let \(A \in \mathcal{P}(S)\) be arbitrary. Since both \(\Psi\bigl( \Phi(A) \bigr)\) and \(A\) are subsets of \(S\) we are proving a set equality. Since \(\Phi(A) = {\large \chi}_{_{\mkern -3mu \Large A}}\) we must prove \[ \Psi\bigl( {\large \chi}_{_{\mkern -3mu \Large A}} \bigr) = A. \] Recall the definition \(\Psi\): \[ \Psi\bigl( {\large \chi}_{_{\mkern -3mu \Large A}} \bigr) = \bigl\{ x \in S : {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1 \bigr\}. \] In Lemma 1 above, we proved that \[ {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1 \quad \Leftrightarrow \quad x \in A. \] Consequently \[ \Psi\bigl( {\large \chi}_{_{\mkern -3mu \Large A}} \bigr) = \bigl\{ x \in S : {\large \chi}_{_{\mkern -3mu \Large A}}\mkern-3mu(x) = 1 \bigr\} = \bigl\{ x \in S : x\in A \bigr\} = A. \]
Part 2. Next we prove \[ \forall\mkern 1mu f \in \{0,1\}^S \qquad \Phi\bigl( \Psi(f) \bigr) = f, \] Let \(f \in \{0,1\}^S\) be arbitrary. Set \[ A = \Psi(f) = \bigl\{ x \in S : f(x) = 1\bigr\}. \] By Lemma 2 proved above, we have \[ f = {\large \chi}_{_{\mkern -3mu \Large A}}. \] By the definition of \(\Phi: \mathcal{P}(S) \to \{0,1\}^S\) we have \[ \Phi(A) = {\large \chi}_{_{\mkern -3mu \Large A}} = f. \] Since \(A = \Psi(f)\), the preceding equality means \[ \Phi\bigl( \Psi(f) \bigr) = \Phi(A) = {\large \chi}_{_{\mkern -3mu \Large A}} = f. \] Since \(f \in \{0,1\}^S\) was arbitrary, this completes the proof of Part 2 and the proposition is proved.