Return to Answer

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}\rangle$ be the corresponding graph, using the $\in$ relation. By AC, this graph has isomorphic copies $\langle h,\to\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 $g$ chosen of $\in$-minimal rank in $V$. This is a set in $V$, and furthermore, $F$ is injective, since we can recover $x$ from any graph isomorphic to $G=\langle y,{\in}\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 (an exception: the Boffa AFA does not have this property).

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.

Theorem. ZFC-foundation + Aczel's anti-foundation axiom AFA proves $|V|=|G|$.

Proof. Since $V$ is a subset of $V$, 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}\rangle$ be the corresponding graph, using the $\in$ relation. By AC, this graph has isomorphic copies $\langle h,\to\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 $g$ chosen of $\in$-minimal rank in $V$. This is a set in $V$, and furthermore, $F$ is injective, since we can recover $x$ from any graph isomorphic to $G=\langle y,{\in}\rangle$. So we have injections both ways $V\to G$ and $G\to V$, and so they are bijective. QED

The same argument seems to work with the other common 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.

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}\rangle$ be the corresponding graph, using the $\in$ relation. By AC, this graph has isomorphic copies $\langle h,\to\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 $g$ chosen of $\in$-minimal rank in $V$. This is a set in $V$, and furthermore, $F$ is injective, since we can recover $x$ from any graph isomorphic to $G=\langle y,{\in}\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 (an exception: the Boffa AFA does not have this property).

In the set theory determined by Aczel's anti-foundation axiom, then every set is determined by an accessible pointed graph, and if we also have AC then we may assume this graph is in $V$, since we may well-order the nodes and find a copy of the graph built on the ordinals.

In this case, we have a surjection from $V$ onto $G$. And of course we also have an injection from $V$ to $G$ via inclusion.

If we assume a global choice principle, this gives $|V|=|G|$ under AFA + global choice.

A similar analysis works with any other anti-foundational set theory, where the $\in$ relation on the transitive closure of a set is isomorphic to a graph on a set in $V$. The idea is that given any set $x\in G$, you consider the hereditary $\in$-closure of $x$ as a graph under the $\in$-relation. If you have AC, you can well-order the nodes of this graph and therefore find a copy of the graph inside $V$. In most of the common anti-foundational theories, the equality of sets is determined by properties of this graph, and so we get a surjection from $V$ to $G$. Thus, combining any of the usual anti-foundational set theories with global choice implies $|V|=|G|$.

Theorem. ZFC-foundation + Aczel's anti-foundation axiom AFA proves $|V|=|G|$.

Proof. Since $V$ is a subset of $V$, 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}\rangle$ be the corresponding graph, using the $\in$ relation. By AC, this graph has isomorphic copies $\langle h,\to\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 $g$ chosen of $\in$-minimal rank in $V$. This is a set in $V$, and furthermore, $F$ is injective, since we can recover $x$ from any graph isomorphic to $G=\langle y,{\in}\rangle$. So we have injections both ways $V\to G$ and $G\to V$, and so they are bijective. QED

The same argument seems to work with the other common 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.