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?

Solution 1:

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\}$.

Solution 2:

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

Solution 3:

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.