7
$\begingroup$

I was wondering if anyone knew whether or not in ZFC (or any other set theory) if the object, $$\Bigg\{ \Big\{ \big\{ \{ \cdots \} \big\} \Big\} \Bigg\}$$ can exist. That is, it is the set containing the set containing the set containing...ad infinitum. Is this even a set? Can it make sense to talk about such a thing? I'm simply curious.

$\endgroup$
6
  • $\begingroup$ Now that I think of it, it may not be a set since it is both a subset and an element of itself. So it must not exist in the ZFC universe. $\endgroup$ Oct 8, 2015 at 16:23
  • $\begingroup$ There exist sets $A,B$ such that both $A\in B$ and $A\subseteq B$, for example take $A=\varnothing,B=\{\varnothing\}$. The reason why your set doesn't exist is explained in Rob's answer. $\endgroup$
    – Wojowu
    Oct 8, 2015 at 16:36
  • $\begingroup$ Existence of self-containing sets doesn't give us Russell's paradox. $\endgroup$
    – Wojowu
    Oct 8, 2015 at 16:45
  • $\begingroup$ Nevermind, you're right. Either way, we can't have sets which are members of themselves, right? $\endgroup$ Oct 8, 2015 at 16:55
  • 1
    $\begingroup$ To amplify Wojowu's comment: Russell's paradox is concerned with the class $U$ of sets $A$ such that $A$ is not a member of $A$. Allowing $U$ as a set causes the paradox. The axiom of foundation implies that $U$ is the entire universe. In non-well-founded set theory, it might be a proper subclass of the universe, but it still can't be a set. $\endgroup$
    – Rob Arthan
    Oct 8, 2015 at 16:58

2 Answers 2

17
$\begingroup$

The axiom of foundation (or regularity) explicitly bans your set. This axiom is independent of the other axioms of ZFC and, depending on your point of view is either just a technical convenience or a monster-barring axiom. Proponents of non-well-founded set theory like these monsters.

To see why your set gives rise to a violation of the axiom of foundation, note that (as explained on the wikipedia page), the axiom of foundation implies that that the membership relation is well-founded: i.e., there is no infinite sequence of sets $A_1, A_2, \ldots$ such that $A_1 \ni A_2 \ni A_3 \ldots$, but your set gives rise to such a sequence.

$\endgroup$
9
  • $\begingroup$ But is it trivial that $S=\{\{\cdots\}\}$ contains itself? After all, if the definition is "sets are equal if they have the same elements", this gives an infinite recursion when trying to determine whether the element of $S$ is the same set as $S$. $\endgroup$
    – JiK
    Oct 8, 2015 at 20:47
  • $\begingroup$ @JiK: Sets containing themselves are only one kind of thing foundation bans. Here, you want to apply the axiom to the transitive closure of $S$; that is, define the sequence $S_0 = S$ and $S_{n+1} \in S_n$, and apply foundation to $\{ S_0, S_1, S_2, \ldots \}$ to obtain a contradiction. $\endgroup$
    – user14972
    Oct 8, 2015 at 21:15
  • $\begingroup$ $S = \{\{ \ldots \}\}$ is an informational notation for a set that might exist. Its defining property would be $S \in S$ iff $S = S$. The potential infinite recursion involved here is just the kind of thing that proponents of non-well-founded set theory revel in. $\endgroup$
    – Rob Arthan
    Oct 8, 2015 at 22:25
  • $\begingroup$ @RobArthan: There is no guarantee that if $S$ has that shape, then $S \in S$ (of course, the converse holds; if $S = \{ S \}$, then it does have that shape). Having isomorphic membership trees isn't a guarantee that two sets are equal, unless they are well-founded (or you use a stronger form of extensionality). $\endgroup$
    – user14972
    Oct 8, 2015 at 23:50
  • $\begingroup$ As Hurkyl has noted, it does not follow from ZFC - regularity that such a set would contain itself. On the other hand, for example, Aczel's anti-foundation axiom would pose that such a set exists and is unique, which (I think, though I might be wrong in my ignorance of nonstandard set theory ;) ) is enough to conclude that indeed $S\in S$ (because, clearly, the sole element of $S$ has the same membership graph), so $S$ is in fact the Quine atom. $\endgroup$
    – tomasz
    Oct 9, 2015 at 1:03
-1
$\begingroup$

It depends very much on how you handle the informal "..." and the words ad-infinitum. The short answer is that the notation is not clear enough to answer whether it is a set or a class.

If you define your construct to be "a thing which has the property of having 1 element, which is itself," you have constructed a class, not a set, because a set cannot have those properties in most set theories.

On the other hand, if you construct it using a sequence S which starts with $S_0=\emptyset$ and is recursively constructed according to $S_{n+1}=\{S_n\}$, and define the thing you want to be $S_\omega$, then what you are constructing is not all that far from the standard set theory construction of natural numbers ($S_{n+1}=S_n \cup \{S_n\}$)

$\endgroup$
12
  • 1
    $\begingroup$ The problem is, you can't really do that, not in standard set theory anyway. What would $S_\omega$ be? There is no relevant notion of convergence here, except for the very naive, as far as I can tell. $\endgroup$
    – tomasz
    Oct 9, 2015 at 1:05
  • $\begingroup$ @tomasz I thought about that, which was why I pointed out how incredibly similar the construction of natural numbers is. To my knowledge, it's just a successor function. Is there a reason why $S(a) = \{a\}$ is not a valid successor function but $S(a) = a \cup \{a\}$ is? I always figured the union was just so to tie the number to cardinality, but I might have missed something. $\endgroup$
    – Cort Ammon
    Oct 9, 2015 at 1:10
  • 1
    $\begingroup$ @CortAmmon there is a very specific reason why the two are different. The second one allows an easy limit approach while the first doesn't. What I mean is if your successor function is $S(a)=a\cup\{a\}$ then you get inclusion giving you a linear ordering (without transitive closure $b < a$ iff $b\in a$) and moreover you get an obvious limit candidate for which the inclusion still gives a linear ordering namely the union of all preceding sets. Note that you still need a special axiom for $\omega$ to exist but it behaves much better. $\endgroup$
    – DRF
    Oct 9, 2015 at 5:03
  • 1
    $\begingroup$ If you took ZFC without the axiom of foundation (so that you would be at least allowed to make something like $\{\{...\}\}$ you couldn't prove it exists. You would need a special axiom to create it (as someone pointed out probably $W=\{W\}$). The trouble is this set now has nothing to do with the finite ordinals you have defined so far. They aren't part of it in any way. So if you did want this $W$ to be your "$\omega$" you would have to specifically extend the order to it. Worse still your successor function doesn't work on it. $S(W)=\{W\}=W$. $\endgroup$
    – DRF
    Oct 9, 2015 at 6:07
  • 1
    $\begingroup$ If you check the wikipedia article on axiom of regularity (foundation) they give the reference for the fact that you can't construct this set. It follows from the result by skolem which shows that ZFC with regularity is equiconsistent with ZFC without regularity. $\endgroup$
    – DRF
    Oct 9, 2015 at 7:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .