MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Return to Answer

2 added 63 characters in body; added 2 characters in body

There are a few problems with what you wrote.

First, you probably want $TC(\{X\})$ rather than $TC(X)$, since you want $X$ to be an element, not just a subset, since it is the node corresponding to $X$ that has no out-arrows (but I see that you have now corrected this). Otherwise, a counterexample will arise from the fact that the transitive closure operation is not one-to-one; for example, any two infinite sets of natural numbers have the same transitive closure: the set of all natural numbers.

Secondly, your statement (2) is not quite stated correctly. For extensionality, what you need is that every node is characterized by the set of its children. That is, any two nodes with the same children are equal.

But once you fix those issues, then yes, there is a one-to-one correspondence between the graphs and $TC({x})$ TC(\{x\})$for hereditary finite$x$. You can prove this by showing inductively that every such graph can be labeled with the set of the labels on the children node. The label on the top node will be the set giving rise to the graph. No two nodes get the same label by the extensionality property. The set of labels is transitive, since every element of a label is a label on a child node. The same idea works with infinite graphs as well, provided that they are well-founded. The inductive labeling process allows the recursion to proceed even when there are infinitely many nodes. Peter Axel's Aczel's theory of anti-foundation extends this idea by allowing ill-founded graphs also to represent sets, in a context where the foundation axiom fails. 1 There are a few problems with what you wrote. First, you probably want$TC(\{X\})$rather than$TC(X)$, since you want$X$to be an element, not just a subset, since it is the node corresponding to$X$that has no out-arrows (but I see that you have now corrected this). Otherwise, a counterexample will arise from the fact that the transitive closure operation is not one-to-one; for example, any two infinite sets of natural numbers have the same transitive closure: the set of all natural numbers. Secondly, your statement (2) is not quite stated correctly. For extensionality, what you need is that every node is characterized by the set of its children. That is, any two nodes with the same children are equal. But once you fix those issues, then yes, there is a one-to-one correspondence between the graphs and$TC({x})$for hereditary finite$x\$. You can prove this by showing inductively that every such graph can be labeled with the set of the labels on the children node. The label on the top node will be the set giving rise to the graph. No two nodes get the same label by the extensionality property. The set of labels is transitive, since every element of a label is a label on a child node.

The same idea works with infinite graphs as well, provided that they are well-founded. The inductive labeling process allows the recursion to proceed even when there are infinitely many nodes.

Peter Axel's theory of anti-foundation extends this idea by allowing ill-founded graphs also to represent sets, in a context where the foundation axiom fails.