2
$\begingroup$

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?

$\endgroup$
7
  • 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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 19:58

1 Answer 1

Reset to default
3
$\begingroup$

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$.

$\endgroup$
7
  • $\begingroup$ Thanks, I need to take a moment and think with detail in all the steps:) $\endgroup$
    – Jose Antonio
    Jun 28, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 20:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .