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