Tao Analysis I - 3.4.6

Exercise 3.4.6 (edited as per errata)

Prove Lemma 3.4.10. (Hint: start with the set $\{0, 1\}^X$ and apply the replacement axiom, replacing each function $f$ with the object $f^{-1}(\{1\})$.)

Let's write out Lemma 3.4.10. (edited as per errata)

Let $X$ be a set. Then $\{Y :Y \text{ is a subset of } X\}$ is a set. That is to say, there exists a set $Z$ such that $Y \in Z \iff Y \subseteq X$ for all objects $Y$.

Let's also remind ourselves of the Axiom of Replacement 3.7.

Let $A$ be a set. For any object $x \in A$, and any object $y$, suppose we have a statement $P(x, y)$ pertaining to $x$ and $y$, such that for each $x \in A$ there is at most one $y$ for which $P(x, y)$ is true. Then there exists a set 

$$\{y : P(x, y) \text{ is true for some } x \in A\}$$

such that for any object $z$,

$$ z \in \{y : P(x, y) \text{ is true for some } x \in A\} \iff P(x,z) \text{ is true for some } x \in A$$

And the Power Set Axiom 3.11.

Let $X$ and $Y$ be sets. Then there exists a set, denoted $Y^X$, which consists of all the functions from $X$ to $Y$, thus

$$f  \in Y^X \iff (f : X \to Y )$$

Exploration

The lemma we need to prove is about existence. We need to prove that the given set exists. We also note that the axiom of replacement and the power set axiom are also about existence.

Let's also sketch out what the proof might look like illustrating the axioms and lemma with a small example (not proof). The following diagram shows $A=\{a, b\}$ and $Y=\{0,1\}$, and the four functions which make up the power set $Y^X=\{f_1, f_2, f_3, f_4\}$.

We can see the inverse images $f^{-1}(\{1\})$ are all the subsets of $X$. Note that $f_2$ does not have an inverse image $f_2^{-1}(\{1\})$ because it does not map any element of $X$ to $1 \in Y$.

Solution

Let's start arbitrary set $X$ and a specific set $Y=\{0,1\}$. 

The Power Set Axiom 3.7 tells us that there exists a set $\{0,1\}^X$, which consists of all the functions $f$ from $X$ to $\{0,1\}$. 

$$\{0,1\}^X = \{f: X \to \{0,1\}\}$$

Now let's apply the Axiom of Replacement 3.7 to this set. Consider a statement $P$ as follows:

$$P(f, A) : A = f^{-1}(\{1\})$$

The statement $P$ is true if the set $A$ is the inverse image of $\{1\}$ with respect to the function $f$.

By definition of inverse images, there is exactly one $A$ satisfying the statement $P$ for each $f$, thus we can use the replacement axiom. 

Thus, by the Axiom of Replacement, there exists a set

$$B=\{A: A=f^{-1}(\{1\})\}$$

This set $B$ consists of the inverse images of $\{1\}$ for every $f \in \{0,1\}^X$.

We now need to show that:

• each $A=f^{-1}(\{1\})$ is a subset of $X$
• the set $B$ consists of all subsets of $X$

If $x \in A = f^{-1}(\{1\})$ then by definition of inverse images, $f(x) \in \{1\}$. Since $\{1\}$ is in $Y$, and the function is $f$, by definition of a function (domain, co-domain, mapping) we conclude $x \in X$. Thus $x \in f^{-1}(\{1\}) \implies x \in X$. That is $x \in A \implies A \subseteq X$. We have shown that each $A$ is a subset of $X$.

Every subset of $A$ can characterised by a function:

$$f_A(a) = \begin{cases} 1  & x \in A \\  0 & x \notin A \end{cases}$$

Such a function is a member of $\{0,1\}^X$ by definition. And as such, $A=f_A^{-1}(\{1\})$ is a member of $B$. Thus, all subsets of $X$ are in $B$.

Thus, we have shown that if $X$ is a set, then there exists a set of subsets of $X$. $\square$

Further Discussion

The above argument will work for any $Y$ with cardinality more than 1.  This is because an element of $Y$ can have an inverse image which is any subset of $X$. 

This is not possible if the cardinality of $Y$ is 1. In this case, all elements of $X$ map to this single element of $Y$ and no partitioning of $X$ into subsets is possible.