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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Lord_Farin Jun 27 '13 at 19:12
  • $\begingroup$ 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? $\endgroup$ – Thomas Andrews Jun 27 '13 at 19:14
  • $\begingroup$ You are on the right track, but probably want $P(X):=\{ f^{-1}[\{1\}]\mid f\in \{0,1\}^X\}$. $\endgroup$ – Hagen von Eitzen Jun 27 '13 at 19:20
  • $\begingroup$ @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? $\endgroup$ – Jose Antonio Jun 27 '13 at 19:23
  • $\begingroup$ @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 :) $\endgroup$ – Jose Antonio Jun 27 '13 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$.

| cite | improve this answer | |
  • $\begingroup$ Thanks, I need to take a moment and think with detail in all the steps:) $\endgroup$ – Jose Antonio Jun 28 '13 at 2:49
  • $\begingroup$ 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) $\endgroup$ – Jose Antonio Jun 28 '13 at 3:30
  • $\begingroup$ 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 $\endgroup$ – Jose Antonio Jun 28 '13 at 4:38
  • $\begingroup$ @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)$. $\endgroup$ – Brian M. Scott Jun 28 '13 at 7:58
  • $\begingroup$ 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? $\endgroup$ – Jose Antonio Jun 28 '13 at 20:03

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.