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
    Could you explain why you think g's definition isn't (and can't be) stratified?2012-10-07
  • 1
    The fact that the natural definition of $g$ isn't stratified does not, by itself, imply that $g$ doesn't exist. NFU sometimes manages to cleverly prove the existence of sets whose straightforward definition isn't stratified. In the present case, though, I'm pretty sure it's known, not only that $g$ doesn't exist, but that the set of one-element sets has strictly smaller cardinality than the set of all sets.2012-12-24
  • 2
    If the function $g$ exists, then we can define the set from Russell's paradox, $R$, as $\{x | g(x) \not\subseteq x\}$. Then $R \in R$ if and only if $g(R) \not\subseteq R$ if and only if $R \not\in R$, which is a contradiction.2013-04-30
  • 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
    By $X^1$, you mean the set of all one-element sets whose elements are drawn from $X$, correct?2016-07-11
  • 0
    Correct. I generally prefer to write $\iota``X$ for that sort of thing, but I was going for the analogy with $V^1$.2016-07-11
  • 0
    Well, I'm having some trouble following your answer. Note that my question is asking about the set of all sets ($V^*$ or $\mathcal{P}(V)$), not the set of all things ($V$). I'm also not familiar enough with Cantor's paradox to see how the set that you gave leads to a contradiction. However, if you can give a proof or source for your last statement ($X^1$ is always smaller than $\mathcal{P}(X)$), that would be very helpful.2016-07-12
  • 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