Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
    
Could you explain why you think g's definition isn't (and can't be) stratified? – Ben Crowell Oct 7 '12 at 18:21
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. – Andreas Blass Dec 24 '12 at 19:32
1  
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. – Tanner Swett Apr 30 '13 at 18:08
    
@PaulPlummer Same answer as my reply to your comment to my answer... – David C. Ullrich Jul 11 at 16:02
up vote 2 down vote accepted
+50

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

share|cite|improve this answer
    
By $X^1$, you mean the set of all one-element sets whose elements are drawn from $X$, correct? – Tanner Swett Jul 11 at 17:36
    
Correct. I generally prefer to write $\iota``X$ for that sort of thing, but I was going for the analogy with $V^1$. – Malice Vidrine Jul 11 at 17:45
    
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. – Tanner Swett Jul 12 at 3:41
    
@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. – Malice Vidrine Jul 12 at 4:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.