Finitely nested Singletons and the axiom of Regularity

Question

Let V be the universe (the class of all sets), let W(0)=V, W(1) be the class of all singletons whose unique member element is a member set of W(0), and for n>0 let W(n+1) be the class of all singletons whose unique member element is a member set of W(n). Let, for every n>=0 S(n)=W(n+1)/W(n) be the class that is the difference of the class W(n+1) and of the class W(n). We are interested with the proposition (S): "For every set x, there exists an unique natural number n such that x is a member set of S(n)" . Question 1: Let ZFC be our set theory; does ZFC prove (S) ? Question 2: Suppose the answer to question 1 is YES, and let now our set theory be ZF-(I mean ZF with the omission of the axiom of Regularity (or Foundation)); does ZF- prove (S) ? Question 3: Suppose the answer to question 2 is NO; does ZF- prove the equivalence of (S) with the axiom of regularity ? Gérard Lang

Answer 1

I assume that you meant to write $S(n)=W(n)-W(n+1)$, rather than what you have written, since inductively one can show $W(n+1)\subseteq W(n)$. With this understanding, all the $S(n)$ are disjoint, and the question is whether every set eventually falls out, or whether there can be a set in every $W(n)$.

In ZFC, there can be no set $x$ in every $W(n)$, since the transitive closure of such an $x$ would consist of the set containing as members the unique element of $x$, the unique element of that set, and so on, and thus have no $\in$-minimal element, contrary to the foundation axiom. So the answer to question 1 is Yes.

Meanwhile, it is relatively consistent with ZF- that there is a set $x$ which has $x=\{x\}$; for example, such sets exist under the Anti-Foundation axiom. Such a set is in every $W(n)$, and so is not in any $S(n)$, and so the answer to question 2 is No.

Question 3 is quite interesting, but I don't know the answer. You may want to add the axiom of Dependent Choices DC, a mild version of AC, for with this axiom a violation of the foundation axiom will give rise to an $\in$-descending $\omega$-sequence $x_0,x_1,\ldots$ with $x_{n+1}\in x_n$, and from such a sequence one might hope to build a set that is in every $W(n)$. But I don't see this how to complete this idea just yet...

Answer 2

Since Joel has already answered Questions (1), and (2), I will only offer an answer for Question 3.

This is a revised version of my answer; thanks to Joel Hamkins for pointing out that my previous construction was not quite right.

Start with a simple graph with 3 elements {$a,b,c$}, where each of the three nodes has an edge to the other two. So in this 3-element model of "set theory", $a$ = {$b$, $c$}, $b$ = {$c$, $a$}, and $c$ = {$a$, $b$}.

Given an extensional digraph $G=(X,E)$, with $X$ as the vertex set and $E$ as the edge set, define the deficiency set $D(G)$ of $G$ to be the collection of subsets $S$ of $X$ that are not "coded" in $G$, i.e., there is no element $a$ in $X$ such that $S$ = {$x \in X : xEa$}.

We now can define by recursion a digraph $G_\alpha = (X_\alpha, E_\alpha)$ for each ordinal $\alpha$ as follows:

$G_0 = G$;

$G_{\alpha+1} = (X_{\alpha+1}, E_{\alpha+1})$, where $X_{\alpha+1} = X_{\alpha} \cup D(G_{\alpha})$, and $E_{\alpha+1} = E_{\alpha}$ together with edges of the form $(x,X)$, where $x\in X_{\alpha}$, $X \in D(G_{\alpha})$, and $x\in X$.

For limit $\alpha$, $G_\alpha$ is the union of $G_\beta$ for $\beta<\alpha$.

The model/digraph we are interested in is the union of all the $G_\alpha$, as $\alpha$ ranges over the ordinals, and $G$ is the 3-element digraph on {$a,b,c$} mentioned earlier. Let's call this model $V(a,b,c)$. It satisfies all the axioms of $ZF$ with the exception of Foundation.

$V(a,b,c)$ also satisfies $S$ since any infinite descending epsilon chain must eventually hit $a$, $b$, or $c$.

So this shows that Question 3 has a negative answer.

Since {$a,b,c$} are indiscernibles in $V(a,b,c)$, I suspect that $DC$ fails in $V(a,b,c)$, but a variation on this theme might produce a model with enough asymmetry for $DC$ to hold as well.

PS. Models of $ZF$ in which the Foundation fails are often constructed using the so-called Bernays-Rieger permutation method (not to be confused with the Fraenkel-Mostowski permutation method of constructing models of $ZF$ in which the axiom of choice fails). The model constructed above is based on a different idea, explored in detail for models of finite set theory in the following paper:

A. Enayat, J. Schmerl, and A. Visser, Omega Models of Finite Set Theory , to appear in Set theory, Arithmetic, and Foundations of Mathematics: Theorems, Philosophies (edited by J. Kennedy and R. Kossak), Cambridge University Press, to appear October 2011.

A preprint can be found here.