3
$\begingroup$

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?

EDIT:

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?

  • 1
    The same set can be assigned to more than one node. $\:$2012-12-07

1 Answers 1

3

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.

  • 0
    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).2015-01-06