Prove that $\{Y:Y \subseteq X\}$ is a set.

Question

I am a beginner and self-learning Real Analysis. Problem 3.4.6 from Tao's Analysis-I poses the following question. I'd like to someone to verify my proof, and help me write a technically correct proof.

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

(Hint given with the question: start with the set $\{0, 1\}^X$ and apply the replacement axiom, replacing each function $f$ with the object $f^{-1}(\{1\})$.)

My Attempt.

Using the Power set Axiom, if $X$ and $Y$ are sets, then $Y^X$ consists of all functions for $X \to Y$

I assume for simplicity that set $X$ has two elements $\{x_1,x_2\}$.

By definition of the power set axiom, the set $Y^X$ consists of 4 functions as follows :

$f_1 \text{ maps } x_1\to 0 \text{ and } x_2 \to 0$
$f_2 \text{ maps } x_1\to 0 \text{ and } x_2 \to 1$
$f_3 \text{ maps } x_1\to 1 \text{ and } x_2 \to 0$
$f_4 \text{ maps } x_1\to 1 \text{ and } x_2 \to 1$

I want to apply the replacement axiom, replacing each function $f_i$ with the object $f_i^{-1}(\{1\})$.

$\{ f_1^{-1}(\{1\}),f_2^{-1}(\{1\}),f_3^{-1}(\{1\}),f_4^{-1}(\{1\})\}$
$\implies$ $\{ \emptyset,\{x_2\},\{x_1\},\{x_1,x_2\} \} $ which consists of all subsets of $X$.

*** My Question***

1. I have simply replaced the functions$(f_1,f_2,f_3,f_4)$ with the object $f^{-1}(\{1\})$. In order to use the replacement axiom, I must show that for each $x$, the statement $P(x,y)$ is true for atmost one $y$. What should be the proposition $P(x,y)$?

2. $\{x_1,x_2\}$ consists of all the elements of $X$, but from the definition of a function we know that bijective functions are invertible, but in the last function both $\{x_1,x_2\}$ map to $1$, in that case, I don't think I can write $f_4^{-1}(\{1\})$=$\{x_1,x_2\}$.

Answer 1

To answer your last question first, if $f\in Y^X$, the notation $f^{-1}$ has two possible meanings. If $f$ is a bijection, it can denote the inverse function to $f$. In all cases, however, it can be applied to subsets of $Y$: for any $A\subseteq Y$,

$$f^{-1}[A]=\{x\in X:f(x)\in A\}\,.$$

In particular, $f_4^{-1}[\{1\}]$ is $\{x_1,x_2\}$ in your example. (See Tao’s Definition $\mathbf{3.4.4}$.)

It should be intuitively clear that

$$\{Y:Y\subseteq X\}=\left\{f^{-1}[\{1\}]:f\in\{0,1\}^X\right\}\,,\tag{1}$$

so we have two tasks: we must show that $(1)$ is actually true, and we must show that the object on the righthand side of $(1)$ is a set.

It’s for the second task that we want replacement. For each $f\in\{0,1\}^X$ let $P(f,y)$ be the statement

$$y=\{x\in X:f(x)=1\}\,.$$

It is straightforward to prove that for each $f$ in $X^{\{0,1\}}$ there is a unique $y$ such that $P(f,y)$ is true, and that $y$ is evidently $f^{-1}[\{1\}]$, so we can apply replacement to conclude that

$$\left\{f^{-1}[\{1\}]:f\in\{0,1\}^X\right\}$$

is a set.

I’ll leave it to you to prove $(1)$.

Answer 2

If you are working within the ZF set theory, this is an axiom.

Answer 3

To prove: $\{Y : Y\subseteq X\} = \{ f^{-1} [\{1\}] : f \in \{0,1\}^X\}$ is true .

Proof :

1. Definition of Inverse Images : If U is a subset of Y, we define the set $f^{-1}(U):= \{x \in X :f(x) \in U\}.$ ,
   where we call $f^{-1}(U)$ the inverse image of $U$.
   

2. Mapping our statement, to the definition of Inverse images,we understand,
   If $U = \{1\}^X$, is a subset to the larger set $f \in \{0,1\}^X$ thus, $U\subseteq f$.
   The statement $f^{-1}[\{1\}]$ corresponds to all the subsets of $X$ for which $U$ is true.
   Hence, the statement $\{ f^{-1} [\{1\}] : f \in \{0,1\}^X\}$ is well-defined as per the definition of inverse images.
   

3. To prove the equivalence, we first prove $\{Y : Y\subseteq X\}\subseteq \{ f^{-1} [\{1\}] : f \in \{0,1\}^X\}$
   Let $\{x\} \in Y \implies \{x\} \subseteq X \implies \{1\}^{\{x\}} \subseteq \{0,1\}^X \implies U \subseteq Y \implies f^{-1}(U) \subseteq f^{-1}(Y)$.
   Thus proving, $\{Y : Y\subseteq X\} \subseteq \{ f^{-1} [\{1\}] : f \in \{0,1\}^X\}$
   

4. To prove the other subset equivalent.
   Let $\{x\} \subseteq f^{-1}(U) \implies \{x\} \in Y$ as stated $\{Y \subseteq X\} \implies \{x\} \in \{Y : Y \subset X \}$
   Thus proving, $\{ f^{-1} [\{1\}] : f \in \{0,1\}^X\} \subseteq \{Y : Y\subseteq X\}$
   

Therefore, proving the equality $\{Y : Y\subseteq X\} = \{ f^{-1} [\{1\}] : f \in \{0,1\}^X\}$