# How are sets “trees with no symmetries”

In Vladimir Voevodsky's lecture Foundations of Mathematics and Homotopy Theory, in passing he mentions that the Zermelo-Fraenkel axioms describe objects which they call "sets", but which he would not call sets but rather "trees with no symmetries".

What might this mean?

-
Why won't you send him an email? I don't think he writes on this site, and I don't know how many people can read his mind... – Asaf Karagila Aug 12 '13 at 7:52
Well, a set as conceived in ZF is a thing which has other sets as members. So one could draw the membership graph as a tree. – Zhen Lin Aug 12 '13 at 8:25
@ZhenLin, yeah, I get that visual. I'm more interested in the "no symmetries" part. – luqui Aug 12 '13 at 12:07

Recall that in set theory everything is a set. In particular, if $x$ is a set, and $y\in x$, then $y$ itself is a set, and its elements are also sets, etc. The transitive closure $\mathrm{TC}(\{x\})$ of $\{x\}$ is the set $\{x\}\cup x\cup\bigcup x\cup\bigcup\bigcup x\cup\dots$

A straightforward picture of a set is as an oriented graph: You have a node for each element of the transitive closure of $\{x\}$, that is: A node for $x$, nodes for the elements of $x$, nodes for the elements of the elements of $x$, nodes for their elements, etc. You add an arrow from a node $a$ to a node $b$ iff $a\in b$. Of course, the resulting (unoriented) picture needs not quite be a tree, but never mind that. (We'll return to it.)

Note that $x$ can be reconstructed from this graph. This is the key reason why we even think about the graph: The top node corresponds to $x$. The arrows ending in this node correspond to its elements. Just looking at the graph, this tells us how many elements there are in $x$. But not only that, since each of those nodes has arrows ending in them, telling us how many elements each of these sets must have, etc.

In principle, one could think that this information is not quite enough to reconstruct $x$. For example, imagine that $x\ne y$ are sets, each satisfying $x=\{x\}$, and $y=\{y\}$. Then they would have the same graph: A single dot, and a single arrow starting and ending in this dot. However, one of the axioms of set theory is the axiom of foundation that tells us that there are no "loops" or infinite descending chains in the membership relation, that is, we cannot have a set $z$ with $z\in z$, or a sequence $z_5\in z_4\in z_3\in z_2\in z_1\in z_0\in z_5$, or an infinite sequence $\dots\in x_2\in _1\in x_0$. In terms of the graph, this means we do not have infinite chains of arrows without a beginning, and we do not have cycles. It is in this sense that the graph is a tree.

Rather than talking of trees, it is more common in set theory to say that the graphs are well-founded and, indeed, we have that any well-founded graph with a top node corresponds to a unique set. The proof proceeds by checking that we can assign an ordinal rank to each node of the graph, and then arguing by transfinite induction on ordinals $\alpha$ that any node of rank $\alpha$ in the graph corresponds to a unique set. To get started, note that a node of rank $0$ corresponds to a set with no elements, and the only such set is the empty set.

An automorphism of this oriented graph corresponds to a bijection $\pi:\mathrm{TC}(\{x\})\to\mathrm{TC}(\{x\})$ such that for any $z,w$, we have $z\in w$ iff $\pi(z)\in\pi(w)$.

A particular case of a very general result in set theory (the Mostowski collapse lemma) tells us that the only such bijection is the identity, which in terms of the graph means that it is rigid. In this sense it is that the tree has no symmetries. (This is more than a curiosity. It is actually very useful in applications.)

You may object that this all works simply because of the axiom of foundation (it works by design, rather than naturally being a result of more intuitive axioms). This is true. The graphs are rigid, because of Mostowski's result, and, more importantly, they completely determine the sets they picture (which is really what matters here). On the other hand, Peter Aczel's anti-foundation axiom is one of the most popular alternatives to the axiom of foundation, and even though Aczel's axiom allows for non-rigid graphs, still the graphs uniquely determine the sets they represent. For example, under this axiom, there is exactly one set $x$ with $x=\{x\}$. This answer goes into some detail on what the axiom says precisely, again emphasizing the pictorial representation of sets as graphs (definitely, no longer trees).

-
Fantastic answer, thanks! Just the right level, enough hints for me to investigate further. – luqui Aug 12 '13 at 14:45
@luqui Glad you find it useful. – Andrés Caicedo Aug 12 '13 at 14:53

If a rooted tree has a non-trivial symmetry, then it is necessarily true that there is a node in the tree that has two isomorphic sub-trees.

In the trees=sets picture, this means the tree has redundant information: recall, for example, that $\{ x,x \} = \{x \}$.

Conversely, if a tree has redundant information from this point of view, then it necessarily has a nontrivial automorphism: swap the two subtrees in any way you like. (I don't think I'm assuming the axiom of choice to make this statement...)

We could define two trees to be equivalent if they encode the same set. However, within every equivalence class, there is a unique rigid tree -- that is, one with no automorphisms. As such, it can be convenient to focus only on the rigid trees when making the correspondence between trees and sets.

-
Oh! The unique rigid tree thing just clicked. Thanks, that clarified the picture for me :-) – luqui Aug 12 '13 at 14:53