15
$\begingroup$

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?

3 Answers 3

20

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

  • 5
    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 http://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.2012-07-23
13

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

12

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.

  • 0
    @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.2012-07-23