# Is every set a subset?

Is every set a subset of a larger set? In other words, for an arbitrary set S, can one always construct a set S' such that S is a proper subset of S'?

Is this question even meaningful?

-

Yes, one can: $S\cup\{S\}$ is a proper superset of $S$, since $S\in S\cup\{S\}$, but $S\notin S$. Thus, $S\subseteq S\cup\{S\}$, but $S\ne S\cup\{S\}$.

-
Too obvious. Thanks! –  Aqwis Jul 23 '12 at 7:09
Perhaps it's worth mentioning that this is a consequence of Axiom of regularity. On an unrelated note - congrats on hitting 2k answers, Brian; it's pretty impressive. –  Martin Sleziak Jul 23 '12 at 7:13
@Martin: Thanks; I honestly had no idea that I’d written so many. –  Brian M. Scott Jul 23 '12 at 7:14
To amplify a little further on Martin's comment, there are set theories in which the answer to the OP's question is no. For example, New Foundations en.wikipedia.org/wiki/New_Foundations has a universal set V which contains all sets as members, and therefore there is no proper superset of V. So really the answer to the question is yes in some set theories including ZF, but no in some other set theories. –  Ben Crowell Jul 23 '12 at 17:48

To build on Brian's answer, one can also ensure that the new set is strictly larger in cardinality, adding one element need not imply that, but we can instead take $S\cup{\cal P}(S)$.

Cantor's theorem ensures that the cardinality of ${\cal P}(S)$ (and thus of the union) is strictly larger than that of $S$.

-

You can even prove it without the Axiom of Regularity.

Lemma. Given a set $A$, there exists a set $B$ such that $B\notin A$.

Proof. Let $B=\{a\in A\mid a\notin a\}$. This is a set, by the Axiom of Separation.

I claim that $B\notin A$. Indeed, if $B\in A$ and $B\in B$, then $B\notin B$ by the definition of $B$. But if $B\in A$ and $B\notin B$, then $B\in B$ by the definition of $B$. This contradiction arises from the assumption that $B\in A$, hence $B\notin A$. $\Box$

Now, given the set $A$, let $B$ be a set such that $B\notin A$. By the Axiom of Power Set, there is a set $P$ such that $B\in P$; by the Axiom of Separation, we obtain the set $\{B\}$.

Now we have $A$ and $\{B\}$ are sets. By the Axiom of Pairs, we have a set that consists exactly of $A$ and $\{B\}$, $X=\{A,\{B\}\}$.

Finally, by the Axiom of Union, there is a set $Y$ such that $Y=\cup\{A,\{B\}\} = \{x\mid x\in A\text{ or }x\in\{B\}\}$ (normally, we would write $Y = A\cup\{B\}$, but this is the notation in the Axiom of Union).

Now, $A\subseteq Y$ is immediate. And since $B\in Y$ but $B\notin A$, we have $A\neq Y$. Thus, $A\subsetneq Y$, as desired.

Note. If we assume the Axiom of Regularity, then $a\notin a$ holds for all sets $a$, hence $B=A$, and the construction just yields the set given by Brian Scott.

-
+1, very nice. Ps. In light of Ben Crowell's comment to Brian M. Scott's answer, I was wondering how this proof must fail for the universal set $V$ in New Foundations. It's pretty simple, though: $a \notin a$ (and thus equivalently $a \in V \land a \notin a$) is not a stratified formula, and so the definition of $B$ for $A = V$ (which would be the Russell set, if it existed) is not valid in NF. –  Ilmari Karonen Jul 23 '12 at 19:26
@IlmariKaronen: I don't know enough about New Foundations to know how things go badly; if this were GBN Set Theory, the problem would be that you cannot guarantee that $B$ is a set if you don't know that $A$ is a set, only a class, and so you cannot apply Power Set or Pairs to it. –  Arturo Magidin Jul 23 '12 at 19:28