# Power set and set of all mappings

I'm working with the Terence Tao's Analysis book. And I have a question in the part of set theory.

As power set axiom, Tao use the set of all function: "If X, and Y be sets. Then there exist a set which consist of all the functions from X to Y."

Using that axiom and the replacement axiom, I need to prove:

"Let X be a set. Then $$\left \{ A : A \subseteq X \right \} \$$ is a set"

I have worked in the next way, but I'm not satisfy with the result:

$$Let\: \; P(X) : = \left \{ A : A\subseteq X \right \}$$ $$\ g: \left \{ 0,1 \right \}^{X}\rightarrow P(X)$$ $$\forall f \left ( f \in \left \{ 0,1 \right \}^{X} \wedge g(f) := f^{-1} [\, \left \{ 1 \right \} \, ] \right )$$

Then, using the axiom of replacement and the axiom of power set (as the book use it) I get the next:

$$G: = \left \{ g(f) : f \in \left \{ 0,1 \right \}^{X} \right \}$$

And I supposed that I need: G = P(X)

Therefore $$A \in G \leftrightarrow f[A] = \left \{ 1 \right \}$$

And to some B be in P(X), we have: $$B\in P(X) \leftrightarrow B \subseteq X$$ and as the images conserves the inclusion $$f [B] \subseteq f[X]$$

I thought that only I needed to show it $$f [A] \subseteq f[X]$$ but I'm stack here, so my approach was the next:

$$\bigcup_{f\in \left \{ 0,1 \right \}^{X} } f [X] = \left \{ 0,1 \right \}$$

$$f[A] \subseteq \bigcup_{f\in \left \{ 0,1 \right \}^{X} } f [X]$$

and in other exercise I proved that the image conserves the union, so "I can conclude something a little odd (haha)"

$$A\subseteq \bigcup X = X$$

I really don't feel comfortable with the result and also I don't know how to show :

$$P(X)\subseteq G$$

(sorry for my mistakes, the English is not my mother language).

My question is indeed how can I prove that?

• What is it that you're not satisfied with? That's the usual way of establishing a correspondence $2^X \simeq \mathscr P(X)$. In fact, what is your question? Please edit to clarify. Jun 27, 2013 at 19:12
• When you say, "Let $P(X)=\dots$," how do you know you can do that? And if you defining a class rather than a set, how can you define $g$ as a function with a class as its target? Jun 27, 2013 at 19:14
• You are on the right track, but probably want $P(X):=\{ f^{-1}[\{1\}]\mid f\in \{0,1\}^X\}$. Jun 27, 2013 at 19:20
• @ThomasAndrews Andrews The exercise is indeed show that P(X) is a set. Assuming only as a power set, the set of all function, and the axiom of replacement. So, I don't know. some hint? Jun 27, 2013 at 19:23
• @HagenvonEitzen in this context is arbitrary use the inverse map of the set {1} instead of {0}. The book didn't speak about it, thanks for the hint :) Jun 27, 2013 at 19:58

You cannot begin by letting $\wp(X)=\{A:A\subseteq X\}$, because you don’t yet know that this object exists: that’s what you’re trying to prove. You do, however, know that $\{0,1\}^X$ exists. Let $\varphi(x,y)$ be the following formula:

$$\left(x\in\{0,1\}^X\land y=x^{-1}[\{1\}]\right)\lor\left(x\notin\{0,1\}^X\land y=0\right)$$

Then $\varphi(x,y)$ is functional: $\forall x\exists!y\,\varphi(x,y)$. Now you can apply replacement to conclude that there is a set $G$ such that

$$y\in G\leftrightarrow\exists x\in\{0,1\}^X\,\varphi(x,y)\;,$$

i.e., $$y\in G\leftrightarrow\exists f\in\{0,1\}^X\left(y=f^{-1}\big[\{1\}\big]\right)\;.\tag{1}$$

It remains to show that $\forall y(y\in G\leftrightarrow y\subseteq X)$, i.e., that this set $G$ really is the power set of $X$.

It’s straightforward to see that $\forall y(y\in G\to y\subseteq X)$. For the other implication, suppose that $y\subseteq X$, and define a function $f:X\to\{0,1\}$ that demonstrates (using $(1)$) that $y\in G$.

• Thanks, I need to take a moment and think with detail in all the steps:) Jun 28, 2013 at 2:49
• I don't understand the last point. If $$y\subseteq X \; and\; f: X\rightarrow \left \{ 0,1 \right \}$$ It is obvious that f is in the set define above, the set of all functions maps X into {0,1}, but It's not clear for me that, if $$y\subseteq X \rightarrow y\in G$$ as the definition says, if $$y\in G\leftrightarrow y =f^{-1} [\left \{ 1 \right \}]\leftrightarrow f[y] = \left \{ 1 \right \}$$ but what's happen if f maps Y only in {0} ? (sorry, maybe it is a kinda stupid question but I don't get it :P) Jun 28, 2013 at 3:30
• I think I got it: if f is defined as follow: if f is 1 when some x is in Y and is 0 if x is not in Y (It's a characteristic function, right?) I'm happy :D Jun 28, 2013 at 4:38
• @user84164: Yes, you got it: you want to define $f$ to be the characteristic function of $y$, and then you have $y=f^{-1}[\{1\}]$ and therefore $y\in G$ by $(1)$. Jun 28, 2013 at 7:58
• Hi again, before all thanks. I have a little question: is it possible to establish a collection of partial function between a set X into Y and show it is a set, only with generate a set consisting: $$\left\{ y^{x}: y\in P(Y) \wedge x\in P(X) \right\}$$ or is too naive to do that :P? Jun 28, 2013 at 20:03