Let $\operatorname{ZFC}^{-}$ be the theory of $\operatorname{ZFC}$ minus the axiom of foundation and define the proper classes $G$ and $V$ as follows:

$G:=$ The proper class of all sets.

$V:=$ The proper class of Von neumann cumulative heirachy.

And let the statements $G=V$ and $|G|=|V|$ be:

$G=V~:~~\forall x~\exists y~(\operatorname{ord}(y)~ \wedge "x\in V_{y}")$

$|G|=|V|~:~~\exists F\colon G \longrightarrow V~~$ a one to one function.

Using the axiom of foundation it is clear that we have $G=V$ and $|G|=|V|$ means that $G$ is as "small" as Von Neumann's cumulative hierarchy.

Now the question is: "How big is the proper class of all sets in the absence of the axiom of foundation? "

In the other words which one of the following statements are true?

(1) $\operatorname{Con}(\operatorname{ZFC}) \longrightarrow \operatorname{Con}(\operatorname{ZFC}^{-} + G\neq V)$

(2) $\operatorname{Con}(\operatorname{ZFC}) \longrightarrow \operatorname{Con}(\operatorname{ZFC}^{-} + |G|\neq|V|)$

  • 1
    $\begingroup$ What does “$\exists F\colon G\to V$” mean? “There exists a formula in the language of set-theory defining such a function”? Or: “Given some model, there exists such a function on this model”? Or are you using some kind of class theory? $\endgroup$ – The User Jun 29 '13 at 16:37
  • $\begingroup$ It's not quite what you were asking about, but you might also be interested in the Axiom of Limitation of Size (see wikipedia). $\endgroup$ – Mark S. Jul 1 '13 at 0:54

Both the statement are true, which is fine because we talk about relative consistency here.

If $\sf ZFC$ is consistent then we know how to generate a model of $\sf ZFC^-+\it G\neq V$.

On the other hand, it is consistent that we have a proper class of atoms: sets of the form $x=\{x\}$, with global choice. Then by taking a class sized permutation model we can ensure that the class of the atoms is not well-orderable, while the axiom of choice for sets holds, and global choice for well-founded sets holds.

In that case we have $G\models\sf ZFC^-$ but $|G|\neq|V|$.

  • $\begingroup$ I would add a remark that in modern set theory sets are considered well-founded, because there is a big advantage to this assumption: we get $\in$-induction, and ranks and whatnot; so in some sense "proper class of all sets" is taken, in the modern context, to be $V$ from the start. $\endgroup$ – Asaf Karagila Jun 29 '13 at 11:45
  • $\begingroup$ Dear Asaf. Thank you for your answer. But I think about some disadvantages of the axiom of foundation in set theory. For example it imposes a limitation on the tree of large cardinals by the Kunen inconsistency theorem which uses this axiom in its proof and implies that the Reinhardt cardinal does not exist. One can compare this situation between assumption "V=L" (in my notation "G=L") and the large cardinal axiom "0-sharp". So the axiom of foundation is a constructibility kind axiom which says "G=V" and limits our imagination of the largeness of the world as same as "useful" axiom "G=L"! $\endgroup$ – user36136 Jun 29 '13 at 12:14
  • 1
    $\begingroup$ But usefulness of an axiomatic system comes from what you can do with it, not from what limitation it may free you from. We can do a whole lot in $\sf ZFC$ which makes it useful. And we use transfinite recursion often enough to suggest that regularity is essential. What would the consistency of a Reinhardt cardinal without regularity do you much good? $\endgroup$ – Asaf Karagila Jun 29 '13 at 12:19
  • $\begingroup$ We can do anything in ordinary mathematics without foundation. In the other words the axiom of foundation is not necessary for the foundation of mathematics which is the main goal of stating the axioms of set theory. Other assumptions just simplify the life of set theorists by removing "hidden" and "odd" objects of the Cantor's "heaven" such as large cardinals and non well founded sets. $\endgroup$ – user36136 Jun 29 '13 at 12:34
  • $\begingroup$ Ali, take it from someone who has been working on the axiom of choice related questions for the past two years. You always start with the notion that you can go to the farthest generalization, and remove a lot of unnecessary assumptions. However that is rarely the case. Much more often than not when you remove all the assumptions you are left without much structure to work with. See how Presburger arithmetic is complete, while Robinson isn't. Why is that? Because Presburger is too weak, and lacks structure for a meaningful manipulation of Godel numbers. $\endgroup$ – Asaf Karagila Jun 29 '13 at 12:35

It seems that most of the usual anti-foundational set theories, when combined with the axiom of choice, imply that $|V|=|G|$. For example, in the case of Aczel's anti-foundation axiom AFA, we have

Theorem. ZFC-foundation + AFA proves $|V|=|G|$.

Proof. Since $V$ is contained in $G$, it suffices to find an injection of $G$ into $V$. Consider any set $x$, not necessarily well-founded. Let $y$ be the transitive closure of $\{x\}$, so $y$ has $x$ and all the hereditarily elements of $x$, and let $\langle y,{\in},x\rangle$ be the corresponding accessible pointed graph, using the $\in$ relation. By AC, this graph has isomorphic copies $\langle h,\to,a\rangle$ in $V$, since we may well-order the nodes and thus find an isomorphic copy built on ordinals. Let $F(x)$ be the collection of all such graphs isomorphic to $\langle y,{\in},x\rangle$ chosen of $\in$-minimal rank in $V$. This is a set in $V$, and furthermore, $F$ is injective, since we can recover $y$ and hence $x$ from any graph isomorphic to $\langle y,{\in},x\rangle$. So we have injections both ways $V\to G$ and $G\to V$, and so they are bijective. QED

The same argument works with many of the other anti-foundational set theories, provided that equality of sets is determined by properties of the underlying $\in$-graph on the hereditary closure of the set. One prominent exception to this is that the Boffa AFA does not have this property.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy