Tao Analysis I 3.5.11

Exercise 3.5.11

Show that Axiom 3.11 can in fact be deduced from Lemma 3.4.10 and the other axioms of set theory, and thus Lemma 3.4.10 can be used as an alternate formulation of the power set axiom. (Hint: for any two sets $X$ and $Y$ , use Lemma 3.4.10 and the axiom of specification to construct the set of all subsets of $X \times Y$ which obey the vertical line test. Then use Exercise 3.5.10 and the axiom of replacement.)

Let's remind ourselves of Axiom 3.11

Axiom 3.11 (Power set axiom). 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$$

And also remind ourselves of Lemma 3.4.10

Lemma 3.4.10. Let $X$ be a set. Then the set $\{Y: Y \subseteq 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$.

Discussion

Interestingly, most people in my experience, think of the "power set axiom" as that described in Lemma 3.4.10 and not the formulation in Axion 3.11.

Solution

For any two sets $X$ and $Y$ we can form the cartesian product, $X \times Y$ as per Definition 3.5.4.

Now we apply Lemma 3.4.10 to $X \times Y$ to form the set of all subsets of $X \times Y$, which we can call $P(X \times Y)$.

Not every set in $P(X \times Y)$ will obey the vertical line test, so we can use the axiom of specification to filter out those that do, to form a set $Z$

$$Z = \{G \in P(X \times Y): G \text{ obeys the vertical line test}\}$$

The elements $G$ of $Z$ are all the graphs from $X \to Y$ which obey the vertical line test.

We can use the axiom of replacement on $Z$ to replace each element $G$ with an ordered triple $(X, Y, G)$, which we can do because for each $G$ there is a unique $(X, Y, G)$. 

This gives us a set of all the ordered triples $(X, Y, G)$ where $G$ is a graph from $X$ to $Y$ which obeys the vertical line test. Thus, by exercise 3.5.10 part (iii), this is a set of all the functions from $X$ to $Y$. $\square$