2
$\begingroup$

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

$\endgroup$

2 Answers 2

6
$\begingroup$

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

$\endgroup$
1
  • $\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$ Jun 8, 2011 at 22:09
6
$\begingroup$

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.

$\endgroup$
6
  • $\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$ Jun 9, 2011 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, 2011 at 1:55
  • $\begingroup$ I guess one needs to carry out some kind of iterated quotient procedure... $\endgroup$ Jun 9, 2011 at 2:03
  • $\begingroup$ Yes, the iterated quotient certainly works, but I wrote up a solution that bypasses that. $\endgroup$
    – Ali Enayat
    Jun 9, 2011 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 anti-foundation 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$ Jun 9, 2011 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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