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

elementary-set-theoryfunctionsinverse functionreal-analysissolution-verification

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)$?
  1. $\{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\}$.

Best Answer

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

Related Question