5
$\begingroup$

In the set theory NFU (described by M. Randall Holmes in "Elementary Set Theory with a Universal Set"), it is possible to define the set of all sets, and the set of all one-element sets. An object is a set if and only if $\emptyset$ is a subset of it, so we can define $V^*$, the set of all sets, as $\{x\ |\ \emptyset \subseteq x\}$. We can also define the set of all one-element sets, $V^1$, as $\{x\ |\ x \text{ has exactly one element}\}$.

Is there a bijection between $V^*$ and $V^1$? Clearly, since $V^1$ is a subset of $V^*$, we can define an injection $f : V^1 \to V^*, f(x) = x$. It's not obvious how one could define an injection $V^* \to V^1$. The "most obvious" candidate, $g(x) = \{x\}$, does not exist; its definition is not stratified.

For finite sets, we can define an injection easily enough:

$\begin{align} g(\emptyset) &= \{(0, \textit{anything})\}\\ g(\{x\}) &= \{(1, x)\}\\ g(\{x,y\}) &= \{(2, x, y)\}\\ g(\{x,y,z\}) &= \{(3, x, y, z)\} \end{align}$

And so on. But this definition cannot be extended to infinite sets.

  • 0
    @PaulPlummer Same answer as my reply to your comment to my answer...2016-07-11

1 Answers 1

4

The answer is that NFU disproves any injection of the universe into the set of all singletons. The thing that disproves the existence of the function $x\mapsto\{x\}$ is not the lack of stratification, but that you can prove that $\mathcal{P}(V)$ must be properly larger than $V^1$. Assume a bijection $f:X^1\to \mathcal{P}(V)$ for whatever set $X$; then we can form $\{x:\{x\}\not\subset f(\{x\})\}$ (this is stratified, and $f^{-1}$ would obviously be an injection $\mathcal{P}(V)\to V^1$), and we get Cantor's paradox in much the usual way: there must be some $\{a\}$ such that $f(\{a\})=\{x:\{x\}\not\subset f(\{x\})\}$, and we find a contradiction when we ask if $\{a\}\subset f(\{a\})$. Notice that this proof via Cantor's paradox doesn't care what the bijection is, so nothing hinges on it being the singleton function in particular.

Thus there is no injection $\mathcal{P}(V)\to V^1$; more generally, while NF(U) may contain sets $X$ with $X\cong\mathcal{P}(X)$, $X^1$ (to keep this notation) is always properly smaller than $\mathcal{P}(X)$. If the above sketch is still too vague, the proof can be found in 17.2 of Elementary Set Theory with a Universal Set, or as Theorem XI.1.6 of Rosser's Logic for Mathematicians (the latter is in the context of NF, but the argument is the same).

  • 0
    @TannerSwett - Sorry, I normally work in NF where $\mathcal{P}(V)=V$, so I reflexively wrote under that assumption. However, $V^*=\mathcal{P}(V)$ in NFU, and it's really $\mathcal{P}(V)$ that counts. Updated with some references to proofs.2016-07-12