(Analysis 1 by Tao) Show that Axiom 3.10 can in fact be deduced from Lemma 3.4.9 and the other axioms of set theory, and thus Lemma 3.4.9 can be used as an alternate formulation of the power set axiom. (Hint: for any tow sets $X$ and $Y$, use Lemma 3.4.9 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.)

Axiom 3.10 (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 (\text{$f$ is a function with domain $X$ and range $Y$}).$$

Lemma 3.4.9. Let $X$ be a set. Then the set $$\{Y: \text{$Y$ is a subset of $X$}\}$$ is a set.

Exercise 3.5.10. If $f: X \to Y$ is a function, define the graph of $f$ to be the subset of $X \times Y$ defined by $\{(x, f(x)) : x \in X\}$. Show that two functions $f: X \to Y$, $\tilde{f}: X \to Y$ are equal if and only if they have the same graph. Conversely, if $G$ is any subset of $X \times Y$ with the property that for each $x \in X$, the set $\{y \in Y: (x,y) \in G\}$ has exactly one element (or in other words, $G$ obeys the vertical line test), show that there is exactly one function $f: X \to Y$ whose graph is equal to $G$.

Attempt: We know the existence of $2^X$ and $2^Y$ from Lemma 3.4.9. Then, we can create the set $\{X \times Y: X \in 2^X, Y\in 2^Y\}$ (?). Using the axiom of specification with ($P(X \times Y) \iff \text{there exists a unique $y$ for each $x$ for $(x,y) \in X \times Y$}$), we have $\{X \times Y: X \in 2^X, Y\in 2^Y ; \text{$P(X \times Y)$ is true}\}$. Each element of this set is the same as the set $G$ in Exercise 3.5.10. Therefore, similarly with Exercise 3.5.10, using the replacement theorem (?), we have $\{y \in Y: (x,y) \in X\times Y; X \in 2^X, Y\in 2^Y ; \text{$P(X \times Y)$ is true}\}$.

I am first wondering if my argument sounds okay. Also, my attempt fails to derive Axiom 3.10. How can I proceed from here?


I did something similar but applied the property to a subset of $X \times Y$ instead of applying it directly to $X \times Y$. Not 100% about it but here is my full answer:

Let $X, Y$ be sets. Let $G$ be a subset of $X \times Y.$ If $G \subseteq X \times Y$, then $G \in 2^{\{X\times Y\}}$ (Lemma 3.4.9). For all the ordered pairs in $G$, we can apply the axiom of specification to form the subset of $G$ with the property $P(x,y)$ such that for each $x \in X$ there is at most one $y \in Y$ for which $P(x,y)$ is true $(\forall x \exists !y((x,y)\in G))$. Hence, we get the subset {$z \in G: P(x,y)$ is true}. From exercise 3.5.10 and the axiom of substitution, we know that given the existence of such a property, $P(x,y)$, there is a function $f: X \rightarrow Y$, and the image of the domain under the function generates a new set. Thus, for each $x \in X$, the set $\{y \in Y: (x,y) \in G\}$ has exactly one element, and $G$ is indeed associated with a unique function (proved in last exercise). From this we get our definition of the graph of $f$ (still a subset of $X \times Y$) as $G_f = \{(x,f(x)):x \in X\}.$ Then the collection of all the functions from $X \rightarrow Y$, is the collection of all the subsets of $X \times Y$ (like $G$), with a property $P(x,y)$ satisfying the vertical line test: $\forall x \forall y \forall z ((P(x,y) \wedge P(x,z)) \implies y = z)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.