Characterization of transitive closure graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T20:16:01Z http://mathoverflow.net/feeds/question/63993 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63993/characterization-of-transitive-closure-graphs Characterization of transitive closure graphs Hans Stricker 2011-05-05T12:24:00Z 2011-05-05T12:51:48Z <p>The transitive closure of a set <em>X</em> is usually seen as a set, but it can also be seen as a graph <em>G(X)</em> with V(<em>G</em>)= TC({<em>X</em>}) and (<em>x,y</em>) ∈ E(<em>G</em>) iff <em>x</em> ∈ <em>y</em>. Such a (transitive closure) graph reveals irredundantly everything that is to know about the set ("<em>its hidden ∈-structure</em>"). It is known that <em>G(X)</em> ≅ <em>G(Y)</em> iff <em>X</em> = <em>Y</em>.</p> <p><em>G(X)</em> obviously </p> <ol> <li>contains exactly one vertex with no out-arrows</li> <li>contains no two vertices with the same parents (&rarr; axiom of extensionality)</li> <li>contains no directed loops (&rarr; axiom of foundation)</li> </ol> <p>Is this enough to characterize the class of transitive closure graphs of hereditarily finite sets: </p> <blockquote> <p>Is there a 1:1 correspondence between the (isomorphism types of) finite digraphs with properties (1)-(3) and $V_\omega$?</p> </blockquote> http://mathoverflow.net/questions/63993/characterization-of-transitive-closure-graphs/63995#63995 Answer by Joel David Hamkins for Characterization of transitive closure graphs Joel David Hamkins 2011-05-05T12:45:55Z 2011-05-05T12:51:48Z <p>There are a few problems with what you wrote. </p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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. </p> <p><a href="http://en.wikipedia.org/wiki/Aczel%27s_anti-foundation_axiom" rel="nofollow">Peter Aczel's theory of anti-foundation</a> extends this idea by allowing ill-founded graphs also to represent sets, in a context where the foundation axiom fails.</p>