Permutation Models of Set Theory - meaning of "ZFA does not distinguish between atoms"

Question

Halbeisen Combinatorial Set Theory on page 169 states "ZFA does not distinguish between the atoms and so a permutation of the set of atoms induces an automorphism of the universe".

How does the inability to determine the truth or falsity of "atom a = atom b = atom c = atom d" (assuming thats what the above means) affect the ability of ZFA to determine whether, for example,

{a} = {b}

or

{a,1}={b,1}

or

{a,b}={c,d}

To do this appears to require only the use of the $\in$ relation in the modified extensionality axiom (A is the set of atoms):

$\forall$x$\forall$y ((x $\notin$ A $\land$ y $\notin$ A) $\implies$ $\forall$z(z $\in$ x $\iff$ z $\in$ y) $\implies$ x=y)

The "Axiom of Atoms" suggests the $\in$ relation can be used on atoms, so can $\in$ not distinguish between atoms, e.g. to determine whether {a}={b}, is "a $\in$ {b}" not false?

Answer 1

ZFA is a formal system whose language is almost as spare as that of ZF. When you write down an expression with constants in it and ask if ZFA proves it, it's on you to explain how to actually define those constants in ZFA, and thus form a bona-fide sentence in ZFA's language. I suspect if you try that with some of the expressions you've written above, you won't have much luck, and, well, this is one way to understand what is meant by ZFA not distinguishing between the atoms.

Intuitively, within a model of ZF, we can take any set and unroll it into its transitive closure: make a with the set at its root, its elements at the next level, its elements' elements at the next level, and so on. Well-foundedness implies that after a finite number of levels, everything has terminated at sets with no elements. Extensionality implies each of these leaves are the empty set and working recursively back upwards we see that extensionality requires us to identify any two sets whose tree above is structurally identical. Any automorphism of the set will need to extend to an automorphism of this graph, since it was just built by the membership relation, so will need to map structurally identical subgraphs onto structurally identical subgraphs, and as we just said, these are necessarily the same set, so this action is trivial.

But when we allow atoms, no longer is every leaf necessarily the empty set, so the sets in the graph can no longer be distinguished only by the shape of the tree above: now we need to know which atoms are at the leaves as well. When we permute the atoms on the leaves, it results in a (possibly) distinct, but structurally identical set, so acts as an $\in$-automorphism of the set's transitive closure.

Note, there is morally nothing distinguishing the empty set from an atom (just as there is nothing morally distinguishing the various zeros in Asaf's analogy) , since they are just possible objects that go at the leaves (i.e. objects with no elements). The only thing that distinguishes is the fact that we have put the empty set into our language, so now any automorphism of a model must fix it by definition. You can think of the empty set as just an atom that's been distinguished as 'pure' by fiat, and the pure sets are the ones where all the leaves of their transitive closure is the empty set. We have not made any further distinctions amongst the atoms, and hopefully seeing how this aligns with the formalism closes the loop between my first paragraph and the long digression afterwards.

Answer 2

Not distinguishing between the atoms does not mean that they are equal, or that we somehow cannot tell in a given model if two atoms are equal.

Two things are equal if and only if they are the same thing. Two different atoms are not the same thing, so they are clearly not equal.

However, if we want to distinguish between two sets, we only need to examine their elements. In the case of atoms, this is not true anymore. Atoms have no elements.¹ So there is no way to distinguish between two atoms by investigating the $\in$ relationship "below them". Since modern set theory, in the form of theories related to $\sf ZF$, put a lot of weight into well-foundedness, this is also true here.

One can look at this as some sort of a "computable way of distinguishing things". In the natural numbers, if we want to compare two natural numbers, without knowing a lot about them, we only need to start asking if both are greater than $0$, or $1$, or $2$, etc. and at some point one of them will give a negative answer, so it is not larger than $k$. If the other is also not larger than $k$, then the two numbers are equal, otherwise the one is smaller than $k$ and the other one is not. (Note that the key point is that we have a concrete description of $0,1,2,\dots$, but our two numbers are somehow more... abstract.)

In that way, $=$ can be computed from $<$. And we want it to be computed from $\in$ in a similar way. Atoms violate this. Imagine the natural numbers with several different $0$'s, each spawning its own copy of what you'd normally thing about the natural numbers, and these copies also mix together in some coherent way. But you're building everything "upwards". You can still compare any non-$0$ objects, but between the different $0$s it's impossible to say which one is which. And that is what Halbeisen means.

---

Footnotes.

1. Sometimes $\varnothing$ is referred to as an atom, but in this context we mean "non-set atoms"; or in the Quine sense, that $x=\{x\}$ is an atom, as those can serve for the same purpose as the atoms in $\sf ZFA$.

Answer 3

"Distinguish", here, is in the sense of a predicate that can be used to discriminate between different things.

As an example, in ZF, we can distinguish the empty set from other sets by writing the predicate

• $P(x) \equiv \forall y : y \notin x $

The empty set is the only set which satisfies this predicate, and so we can say that the language of set theory can distinguish between the empty set and nonempty sets.

Similarly, in ZFA, if we take a parameter $a$ that refers to an atom, we can write down a predicate on atoms

• $Q_a(b) \equiv (a = b) $

Then the predicate $Q_a$ can distinguish between atoms that are $a$ and atoms that are not $a$.

The key thing to note here is that $Q_a$ has a free parameter $a$, so it is qualitatively different from the example of $P$ above which didn't have any free parameters.

What Halbeisen is saying is that if $R$ is any predicate in the language of ZFA that doesn't have any parameters, then $R$ cannot be used to distinguish between atoms. That is, $R(a) \equiv R(b)$ for all atoms $a$ and $b$.