Are the sets of the form $a=\{a\}$ different?

Question

Suppose we adopt all the ZF axioms except the axiom of foundation. I suppose even adding the AC would not harm my question.
Somewhere on the internet, I read that in this case, the axiom of extensionality can't tell the difference between two sets of the form $a=\{a\}$ and $b=\{b\}.$ It seems believable, though I'm not fully convinced.
Can somebody explain to me why this should or shouldn't be true?
What kind of axiom would guarantee that these sets all are equal? or at least there are not that many pathological sets of this form?

Answer 1

The thing about equality is that it's kind of undefined in terms of anything else. Extensionality is attempting to define equality in terms of the $\in$ relationship, but when it comes to sets of the form $a=\{a\}$ (or, Quine atoms as they are known), it gets kinda weird and "seemingly circular".

If $a=\{a\}$ and $b=\{b\}$, how can you tell if $a=b$ or not? Normally, you'd find an element of $a$ which isn't in $b$, or vice versa, but then you're really just saying that $a\neq b$ or that $a=b$. Here we need to remember that equality is defined externally to our language and universe. Two things are equal if and only if they are the same thing. So, $a=b$ if and only if they are the same object, this is "dogmatic" to an extent, rather than "axiomatic" from the universe's perspective. So, if $a\neq b$, then $\{a\}\neq\{b\}$ which, in the case of them being Quine atoms, means that $a\neq b$.

The consequence of this is that in principle, if $a$ and $b$ are Quine atoms, we can extend the function that switches $a$ and $b$ to an automorphism of the entire universe. This is slightly inaccurate, but is generally the gist of things in the contexts we normally consider. This makes Quine atoms indiscernible (again, in the usual contexts), they have the same properties, with themselves as well as with the other sets in the universe.

Right. So, it is certainly consistent with $\sf ZF-Foundation$ that Quine atoms exist. But how many?

• The Axiom of Foundation implies there are none.
• Aczel's Anti-Foundation Axiom implies that there is a unique Quine atom. Since the "picture" that $a=\{a\}$ defines will only have a unique transitive solution.
• Other Anti-Foundation Axioms will posit there are numerous, perhaps even a proper class of, Quine atoms.
• We can also just require to begin with that the ill-founded part of the universe is really just generated by Quine atoms (this is how we get $\sf ZFA$ or $\sf ZFU$ in a sense (another sense is weakening Extensionality or using a two-sorted logic)).

You may choose one of those to limit the "feral and ill-founded" part of the set theoretic universe in one form or another.

Answer 2

The SEP article Non-well-founded set theory has a good treatment of some, but not all, of the material below. See also this expository paper by Will Brian. The main missing topic here is Boffa's axiom, for which I don't know an easily-accessible source.

---

In the foundationless context, sets satisfying $a=\{a\}$ are called Quine atoms. The following theories are equiconsistent (= if one is consistent, they all are, and this is provable in a very weak theory such as $\mathsf{PA}$):

• $\mathsf{ZF}$.

• $\mathsf{ZF-Foundation}$ + "There is exactly one Quine atom."

• $\mathsf{ZF-Foundation}$ + "There are multiple Quine atoms."

The second and third theories are subtheories of $\mathsf{ZF-Foundation+AFA}$ and $\mathsf{ZF-Foundation+BAFA}$ respectively, where $\mathsf{AFA}$ is Aczel's antifoundation axiom and $\mathsf{BAFA}$ is Boffa's antifoundation axiom. As the shorter acronym probably indicates, Aczel's is more common than Boffa's. Boffa's axiom is a bit technical to state, but Aczel's is rather snappy: basically, isomorphism types of connected rooted graphs satisfying a certain further property analogous to extensionality correspond exactly to sets. The fact that up to isomorphism there is exactly one "single-vertex single-edge" graph tells us, under $\mathsf{AFA}$, that there is exactly one Quine atom. Boffa's axiom is similar in spirit but more technical, and by bringing labels into the picture leads to a proper class of Quine atoms.

A quick comment on intuition: Aczel is "equality-maximizing" (two sets are equal unless there's a pressing reason for them not to be equal, and so in particular Quine atoms should be equal) while Boffa is "variety-maximizing" (since there's no immediate reason for two Quine atoms to be equal, we should have lots of them). In my opinion, all three axioms - Foundation, Aczel, and Boffa - have equal intuitive weight, although this is a minority view.

It's easy to go from the consistency of $\mathsf{ZF-Foundation}$ to the consistency of $\mathsf{ZF}$: given a model $\mathcal{M}$ of the former theory, simply building the cumulative hierarchy as usual inside $\mathcal{M}$ (being careful to define ordinals as "transitive sets well-ordered by $\in$" rather than "hereditarily transitive sets") as usual will yield a model of $\mathsf{ZF}$. This argument is presented in detail in Kunen's book if I recall correctly. In the other direction, the point is that the relevant antifoundation axioms actually tell you how to construct the model you want: e.g. for $\mathsf{AFA}$, given $\mathcal{M}\models\mathsf{ZF}$ we look at (what $\mathcal{M}$ thinks is) the class of rooted extensional graphs up to isomoprhism (using Scott's trick to pick representatives), with "$a\in b$" interpreted as "The graph below some child of the root of $b$ is isomorphic to $a$."

And as usual, choice doesn't impact the issues above at all.