In $\mathsf{ZF}$ we have the Power Set Axiom: if $x$ is a set, then $\mathcal P(x)$ is a set (see here for a nice listing of the axioms of $\mathsf{ZF}$). Yesterday I was explaining to some students the notion of ordered pairs à la Kuratowski: $(a,b):=\bigl\{\{a,b\},\{a\}\bigr\}$. Then I argumented that, given sets $A$ and $B$ and elements $a\in A,b\in B$, one has $(a,b)\in\mathcal P\bigl(\mathcal P(A\cup B)\bigr)$. And then I became stuck: I wanted to say "Therefore $A\times B\subseteq\mathcal P\bigl(\mathcal P(A\cup B)\bigr)$, hence $A\times B$ is a set." But something is wrong here: we only write "$X\subseteq Y$" when we know beforehand that $X$ and $Y$ are indeed sets! This lead me to ask these two questions:
$\endgroup$ 41) I thought about defining $A\times B$ using the Comprehension Scheme, via
$$Q(x,A,B): \exists a\,\exists b\bigl[a\in A\,\wedge\,b\in B\,\wedge\,\varphi(x,a,b)\bigr]\,,$$
being $\varphi(x,a,b)$ the formula defining the pair $(a,b)$ as a set. Am I right?
2) It is true, in $\mathsf{ZF}$, that not every subset of a set is indeed a set?
4 Answers
$\begingroup$1) Yes using the Comprehension Scheme you can define $A\times B$ as the set $$A \times B := \left\{ x \in \mathcal{P}(\mathcal{P}(A \cup B)) \ \mid \ \psi[x,A,B] \right\} $$ where $\psi[x,A,B]$ is the formula $$ \exists a \exists b (a \in A \land a \in B \land x = \left\{\left\{a,b\right\},\left\{b\right\}\right\}) $$ Firstly you know that the set $\mathcal{P}(\mathcal{P}(A \cup B))$ exists after you've constructed it using the Powerset axiom and you know that this set containns all the ordered pairs. Then the Comprehension Axiom Scheme asserts that all the things that can be extracted from existing sets with first order formulas are sets that exist as well. With that you can assert that the constructed set $A\times B$ exists and it has the right properties that you want containing only the ordered pairs because of the way you've constructed it. There is no need to mention "subset" anywhere. In fact subset notation $X \subseteq Y$ is just abbreviation for the formula $\phi[X,Y]$
$$ \forall a (a \in X \implies a \in Y) $$
2) In order to say something is a subset of a set it has to be set in the first place. $ZF$ works only with sets and nothing else. If something is "not a set" there is no way to even refer to it in $ZF$ because the first order formulas of the meta-language quantify only over sets. This means that even if we ignore the Power Set axiom with which you can show that all subsets of an existing set are sets that exist, we cannot express the statement that there exist a subset of a set that is "not a set".
$\endgroup$ $\begingroup$Let $A,B$ be sets.
Then by Pair there exists a set $C$ with $\forall x\colon x\in C\leftrightarrow x=A\lor x=B$. (The Pairing axiom can be expelled by using Infinity and Power and Replacement, but I like to use it for convenience).
Then by Union, there exists a set $D$ with $\forall x\colon x\in D\leftrightarrow\exists y\colon x\in y\land y\in C$.
Then by Power, there exists a set $E$ with $\forall x\colon x\in E\leftrightarrow\forall y\colon y\in x\to y\in D$.
Then by Power, there exists a set $F$ with $\forall x\colon x\in F\leftrightarrow\forall y\colon y\in x\to y\in E$.
Then by Comprehension, there exists a set $G$ with $$\begin{align}\forall x\colon x\in G\leftrightarrow {}&{}x\in F\\&\land\exists a\exists b\exists u\exists v\forall t\colon\\ &\qquad\ a\in A\\ &\quad\land\ b\in B\\ &\quad\land\ t\in u\leftrightarrow t=a\\ &\quad\land\ t\in v\leftrightarrow (t=a\lor t=b)\\ &\quad\land\ t\in x\leftrightarrow (t=u\lor t=v)\end{align}$$ is a set by Comprehension.
About $G$, we readily prove that each of its elements is a Kuratowski pair of an element of $A$ and an element of $B$ (in fact, the convoluted formula states precisely what could be abbreviated as $x=\{\{a\},\{a,b\}\}$)
On the other hand, let $x=\{\{a\},\{a,b\}\}$ be a Kuratowski pair of an element of $A$ and an element of $B$. We directly find that $A\in C$, hence $a\in D$. Likewise $B\in C$ and $b\in D$. By Pair, the set we write down as $\{a\}$ (i.e., a set $X$ with $\forall z\colon z\in X\leftrightarrow z=a$) exists. As $a\in D$, we conclude $\{a\}\in E$. Similarly, we conclude that $\{a,b\}\in E$ from $a\in D$ and $b\in D$. Similarly, we conclude that $\{\{a\},\{a,b\}\}\in F$ from $\{a\}\in E$ and $\{a,b\}\in E$. Finally, we verify the condition for $G$ (with $u=\{a\}$ and $v=\{a,b\}$, of course) and see that $x\in G$.
Therefore $G$ is precisely the set of all Kuratoski pairs of elements of $A$ and elements of $B$, in short $G=A\times B$.
While the above shows that all works out nicely, there is some way in which your doubt is justified: Suppose we have a set $X$ and a magical oracle that gives us what might be called a sub-collection $Y$ of $X$. Does that make $Y$ an element of $\mathcal P(X)$? Well, it does as long $Y$ is a set, but this may not be the case. In principle, it might happen that $Y$ is "undescribable" and the powerset only contains all "describable" subsets. But then again, $Y$ is not the subject of set theory because it fails to be set. The subset relation then exists only in a meta theory ... and fortunately there is no such thing as a magical oracle.
$\endgroup$ 1 $\begingroup$If you accept that
elements of sets are sets (in ZF, $\in$ is a relation between sets),
and that $\mathcal P(X)$ is a set whenever $X$ is,
then you have to conclude that the elements of $\mathcal P(X)$ (i.e. subsets of $X$) are sets.
$\endgroup$ $\begingroup$The simplest answer to your question is the following. Suppose $x$ is a set and $y \subseteq x$. Then $y \in \mathcal{P}(x)$, and $\mathcal{P}(x)$ is a set by the Power Set Axiom. Every element of a set is a set, so $y$ is a set.
If you have suspicions about the last statement (every element of a set is a set), that is well-founded; so extra work/ground-laying must be done to have this make rigorous sense.
$\endgroup$ 3
