Show that power set is a set.

elementary-set-theorysolution-verification

I came across following proposition author wants the reader to prove:

Proposition 1. For arbitrary set $X$, $\{A \mid A \subseteq X\}$ is a set.

My attempt (mainly based on hints given by the author):

I'll first state the power axiom presented in the book (which seems to be different from what is written the wikipedia article):

Power set axiom. Let $X$ and $Y$ be sets. Then there exists a set, denoted $Y^{X}$ , which consists of all the functions from $X$ to $Y$ , thus

$$f \in Y^{X} \iff \text{(f is a function with domain $X$ and range Y)}$$

Using power set axiom and replacement axiom, we can construct following set

$$S = \{Z \mid Z = f^{-1}(\{1\}) \text{ for some } f \in \{0,1\}^X \}$$

Now we need to show that for arbitrary $A \in S$, $A \in S$ iff $A \subseteq X$

$(\rightarrow)$ Take some $A \in S$ and take some $a \in A$. Since $A \in S$, exists some $f: X \rightarrow Y$ such that $f^{-1}(\{1\}) = A$. By definition of the backward image, we can conclude that $a$ is in the domain of $f$, that is $a \in X$.

$(\leftarrow)$ Take arbitrary subset of $X$, say $A$. We can define $f: X \rightarrow Y$ such that $f(x) = 1$ iff $x \in A$, and $f(x) = 0$ otherwise. We see that $f \in \{0,1\}^{X}$ and it is true that $A = f^{-1}(\{1\})$. Hence $A \in S$.

Hence $S = \{A \mid A \subseteq X\}$, which means that $\{A \mid A \subseteq X\}$ is a set.

$\blacksquare$

Question 1.

Is it correct?

Question 2.

If the proof above is correct, are there more concise alternatives? Before seeing hints by the author (that is, we need to use power set axiom and replacement axiom), I'd thought following argument would be sufficient: "Set is a collection of objects. Subset is an object. Hence collection of subsets of a particular set is a set."

Best Answer

This proof looks fine to me. Just a couple of comments on it:

  1. Unless it has been already proven somewhere else in the book you are reading, I would add a justification on why the elements of $S$ are sets, so something like $$f^{-1}(\{1\}) = \big\{ x \in X : f(x) = 1\big\}$$ is a set for each $f \in \{0,1 \}^X$ by the separation axiom.
  2. In the $(\to)$ direction you need to consider two cases, namely $A = \varnothing$ and $A \neq \varnothing$. If $A = \varnothing$, then trivially $A \subseteq X$; otherwise there is $a \in A$ (as you state), and the rest of the proof follows.

As hinted in the comments, the point of using such formalism to prove that for any set $A$, $\mathcal P(A)$ is also a set (instead of arguing as you first thought), comes from mathematicians trying to avoid getting into a position where certain collections of sets are so "big" that contradictions arise within your axiom system, such as the ones exemplified in Cantor's and Burali-Forti's paradoxes.

Related Question