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

$\begingroup$ YES, you are right, S(n) is W(n)/W(n+1. And thank you very much for answering so neatly to questions 1 and 2. GL $\endgroup$ – Gérard Lang Jun 8 '11 at 22:09
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 3element 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 3element 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 socalled BernaysRieger permutation method (not to be confused with the FraenkelMostowski 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.

$\begingroup$ Ali, do you really have extensionality? After all, the object a has elements exactly b and c, but so does the set {b,c} that you added when forming V(a,b,c), and if I understand you correctly, these are different objects in your final model. $\endgroup$ – Joel David Hamkins Jun 9 '11 at 0:24

$\begingroup$ @Joel: you are right, in my description of the model, Extensionality fails, but this can be easily fixed; I will update my answer shortly. $\endgroup$ – Ali Enayat Jun 9 '11 at 1:55

$\begingroup$ I guess one needs to carry out some kind of iterated quotient procedure... $\endgroup$ – Joel David Hamkins Jun 9 '11 at 2:03

$\begingroup$ Yes, the iterated quotient certainly works, but I wrote up a solution that bypasses that. $\endgroup$ – Ali Enayat Jun 9 '11 at 2:49

$\begingroup$ A very nice argument, Ali! I suppose that one can also think about it this way: start in a model of antifoundation AFA, where there is a set $X$ corresponding to your original extensional digraph (and incidentally, it seems you omitted the assumption that $X$ is extensional in your general construction, but this seems necessary), and now buiild the class V(X) by transfinite iterated powerset inside the model. I guess it amounts to nearly the same idea as your construction. $\endgroup$ – Joel David Hamkins Jun 9 '11 at 10:36