Skip to main content
2 of 3
added 2 characters in body
Hans-Peter Stricker
  • 9.7k
  • 5
  • 53
  • 113

Characterization of transitive closure graphs

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) ∈ E(G) iff xy. Such a (transitive closure) graph reveals irredundantly everything that is to know about the set ("its hidden ∈-structure"). It is known that G(X)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$?

Hans-Peter Stricker
  • 9.7k
  • 5
  • 53
  • 113