Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

All stuff is from Page 1 - 6, Non-Well-Founded Sets, Peter Aczel, which can be found here.

Here a GRAPH will consist of a set of NODES and a set of EDGES, each edge being an ordered pair $(n, n')$ of nodes. If $(n, n')$ is an edge then I will write $n \to n'$ and say that $n' $is a CHILD of $n$. A PATH is a finite or infinite sequence

A DECORATION of a graph is an assignment of a set to each node of the graph in such a way that the elements of the set assigned to a node are the sets assigned to the children of that node.

One important relevant result is

Mostowski's Collapsing Lemma: Every well-founded graph has a unique decoration

Why this version of Mostowski's Collapsing Lemma doesn't require graph to be extensional?

Another question is what kind of Leap of faith do we need, if we want to accept that unique decoration property holds not only with respect to well-founded graphs, but to any graphs.

Or put it other way, what is it render AFA neither obviously true, nor obviously wrong?


It occurred to me, what if there is a graph has more than one decorations. It seems to me it is consistent with the existence of non-well-founded sets. So why we have to stress the uniqueness property? What is the undesired consequence, if we choose not to stick to it?

share|cite|improve this question
So Christmas is not well-founded, as it does not have a unique decoration? Interesting. – Asaf Karagila Dec 7 '12 at 9:32
The same set can be assigned to more than one node. $\:$ – Ricky Demer Dec 7 '12 at 9:33
up vote 3 down vote accepted

Aczel's version of the Mostowski Collapsing Lemma appears to be a generalisation of the usual one. Recall that the Mostowski Collapsing Lemma in Jech (p.69) says the following (emphasis mine):

If $E$ is a well-founded and extensional relation of a class $P$, then there is a transitive class $M$ and an isomorphism $\pi$ between $(P,E)$ and $(M,\in)$. The transitive class $M$ and the isomorphism $\pi$ are unique.

Note that the above version requires not only there to be a strong relationship between the decoration of a node/set and its children/elements, but also that each decoration is given to a unique node/set. Aczel's version does not require that the mapping $x \mapsto dx$ be injective (let alone be an isomorphism), but only that there be a strong relationship between the decoration of a node and the decorations of its children.

A consequence of the construction would be that if the edge relation of the graph is additionally extensional, then you would produce such an isomorphism. But clearly not all graphs have an extensional edge relationship.

At one level, AFA provides for the existence of sets which are somewhat counterintuitive (in my eye, anyway);

  • Consider how you would produce a decoration for the graph whose set of nodes is $\mathbb{N}$ and $n \rightarrow m$ iff $m = n+1$. This is a single infinite path, and if $d$ were a decoration you must have $d0 \ni d1 \ni d2 \ni \cdots$.
  • For finite cyclic graphs you must accept that there are sets satisfying $d0 \ni d1 \ni \cdots \ni dn \ni d0$.

But AFA works a dual function in this theory. Suppose we are given the directed $2$-cycle $a \rightarrow b \rightarrow a$. If $d$ is any decoration for this graph, then $$da = \{ db \}; \quad db = \{ da \} \quad \Longrightarrow \quad da = \{ db \} = \{ \{ da \} \},$$ and also note that $db = \{ \{ db \} \}$. It is quite easy to show that by switching the decorations of the nodes $a$ and $b$ ($\partial a = db , \partial b = da$) we get another decoration of the graph. But AFA says that decorations are unique, so in fact $db = da$! To make a more concrete statement, by AFA there is a unique set $x$ satisfying $x = \{ \{ x \} \}$. It is not too difficult to extend this to say that for each natural number $n \geq 1$ there is a unique set $x$ satisfying $$x = \overbrace{ \{ \{ \cdots \{ }^{n \text{ times}} x \} \cdots \} \}.$$ (Similar statements can be made about witnessing sets for all ill-founded graphs.)

As for the Leap of Faith required to believe or disbelieve AFA? I guess it depends on whether you believe the $\in$ relation to be really well-founded, or possibly ill-founded (and perhaps additionally that ZF(C) only focuses on the well-founded fragment of these sets). But these appear to me to be meta-theoretical issues that cannot be proved or refuted.

share|cite|improve this answer
Thank you for your well-written answer. But it seems to me, the second part of your answer addresses more of the issue of existence of non-well-founded sets, which I have trouble to link, with the uniqueness of a decoration of a graph. – Metta World Peace Dec 7 '12 at 14:41
@MettaWorldPeace: I may not have thought this out fully in my answer. I think we agree that only the ill-founded graphs make unique decorating probematic. In this case AFA comes to the rescue on two fronts! It first of all posits the existence of the ill-founded sets required to give such graphs decorations. But we could also imagine that, e.g., there are different sets $x$ and $y$ which saisify $x=\{\{x\}\}$ and $y=\{\{y\}\}$. These would be decorations for the the directed $2$-cycle. AFA then actually says that these two sets are the same! – arjafi Dec 7 '12 at 14:59
Thank you so much for your excellent answer. I wish I could upvoted it ten times:-) – Metta World Peace Dec 7 '12 at 16:14
As taught in Economics 101, rational person prefers more over less in terms of goods, which, of course, include upvotes. So, congrats, you are rational. By the way, I prefer the name Metta World Peace, which appears, significantly, less aggressive. – Metta World Peace Dec 7 '12 at 22:51
Note that under AFA, the solution to $x=\{x\}$ is unique, and since it also solves $x=\{\{\cdots\{x\}\cdots\}$ for any number ($\ge 1$) of braces, this same set is the unique decoration for every plain cyclic graph, including the single infinite path of your first example. (This is also why it wouldn't make much sense for Aczel to require extensional graphs, because the uniqueness requirement may force some nodes to have identical decorations anyway). – Henning Makholm Jan 6 '15 at 18:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.