2
$\begingroup$

The transitive closure of a set $X$ is usually seen as a set, but it can also be seen as a graph $G(X)$ with $V(G)= TC({X})$ and $(x,y)\in E(G)$ iff $x\in y$. Such a (transitive closure) graph reveals irredundantly everything that is to know about the set ("its hidden $\in$-structure"). It is known that $G(X)\simeq G(Y)$ iff $X=Y$.

G(X) obviously

  1. contains exactly one vertex with no out-arrows
  2. contains no two vertices with the same parents (→ axiom of extensionality)
  3. contains no directed loops (→ axiom of foundation)

Is this enough to characterize the class of transitive closure graphs of hereditarily finite sets:

Is there a 1:1 correspondence between the (isomorphism types of) finite digraphs with properties (1)-(3) and $V_\omega$?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
9
$\begingroup$

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 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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ ad (2): Sorry for the confusion, but since I assume an arrow from x to y iff x is an element of y, x is a "parent" of y iff x is an element. $\endgroup$
    – Hans-Peter Stricker
    Commented May 5, 2011 at 12:52
  • $\begingroup$ Oh, I see. That part is fine then. I usually picture the graph with $X$ at the top, and each node would be the parent of its elements, which has a certain easy and coherent sense. In any case, the inductive labeling idea still works, and shows you how to turn the graph into a set. $\endgroup$
    – Joel David Hamkins
    Commented May 5, 2011 at 12:58
  • $\begingroup$ So in my answer, you should exchange "children" and "parent" in the labeling procedure. $\endgroup$
    – Joel David Hamkins
    Commented May 5, 2011 at 13:00
  • $\begingroup$ I see X at the top, too, and the empty set at the bottom, but the arrows pointing upwards. "As you like it." $\endgroup$
    – Hans-Peter Stricker
    Commented May 5, 2011 at 13:14
  • $\begingroup$ What I wonder: How can a class of objects with so seemingly weak and simple properties like (1)-(3) provide a model for a theory which has about ten independent axioms, only two of which are directly related to (1)-(3)? $\endgroup$
    – Hans-Peter Stricker
    Commented May 5, 2011 at 14:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .