Question

Let the transitive closure graph of a set X be the graph G(X) with V(G)= TC({X}) and (x,y) ∈ E(G) iff x ∈ y. Let H(X) be the reverse graph of G(X) with (x,y) ∈ E(H) iff y ∈ x.

I assume that the following holds:

For every hereditarily finite set X there is a unique set Y such that G(X) is isomorphic to H(Y).

Questions

Is this assumption correct? [Edit: If the answer is no: for which X?] Has this set Y been given a name (as a function of X)? Something like the reverse set of X? And has it attracted some interest? Can someone give a reference?

---

Some simple facts:

• The finite von Neumann ordinals $\emptyset = 0, 1, 2, ...$ are reverse sets of themselves (self-reverse for short)

• The finite Zermelo ordinals $\emptyset = 0', 1', 2', ...$, i.e. $\lbrace\rbrace, \lbrace\lbrace\rbrace\rbrace, \lbrace\lbrace\lbrace\rbrace\rbrace\rbrace,...$, are self-reverse.

• The smallest pairs of not self-reverse sets are $\lbrace 2\rbrace$ vs. $\lbrace 1, 2'\rbrace$ and $\lbrace 0, 2\rbrace$ vs. $\lbrace 0, 1, 2'\rbrace$.

Further question:

• Is there a general correlation between the cardinalities of X, its reverse set Y and TC({X}) (= TC({Y}))?

Answer 1

I don't know if there is already a name for this kind of reverse set. I've been calling it a "dual", but "reverse" is just as good.

Non-extensional graphs represent multisets, which always have duals, and the dual of a set is a multiset but not necessarily a set.

The smallest sets mostly have dual sets, but this changes when the graphs get more complicated. Of the 112 sets in the class $A_4$, 76 have dual sets. Of the 11680 sets in $A_5$, just 1644 have dual sets. Of these, 136 are self-dual, for example the rather pretty {0,2,3,{1,2,3}}.

At the end of the question it seems to be implied that $TC({x}) = TC({dual(x)})$ but this isn't true in general.

Answer 2

In ZFC (the axiom of foundation is most essential), a graph is a transitive closure graph if and only if it is extensional (distinct vertices have distinct sets of incoming edges), well-founded (there is no descending infinite path) and there is a unique sink reachable by a path from every vertex. (The left-to-right direction is obvious, for the right-to-left direction the set can be constructed by well-founded recursion.) Moreover, the graph uniquely determines the set. (This can be proved easily by well-founded induction.) Finally, the graph is finite if and only if the corresponding set is hereditarily finite.

For your question, this entails:

• $Y$ is unique if it exists.

• For finite graphs, well-foundedness is equivalent to there being no directed cycles, which is a symmetric condition, and therefore is automatically satisfied for the converse of $G(X)$. Similarly, $G(X)$ always has a unique source (namely, the vertex corresponding to the empty set) and every vertex is reachable from it by a directed path. Thus,

  $Y$ exists if and only if the converse of $G(X)$ is extensional,

  which amounts to the following condition:

  For every $a\ne b$ in $\operatorname{TC}(\{X\})$, there is $c\in\operatorname{TC}(\{X\})$ such that $a\in c$ and $b\notin c$ or vice versa.

  Linda’s example shows that there are sets $X$ failing this condition.

With regards to the “further question”: there is almost no correlation, except for the obvious bound that $|X|,|Y| < |\operatorname{TC}(\{X\})|$. You gave the extreme examples yourself: on the one hand, von Neumann ordinals $n$ have $|X|=|Y|=n$, $|\operatorname{TC}(\{X\})|=n+1$. On the other hand, Zermelo ordinals $n'$ have $|X|=|Y|=1$, $|\operatorname{TC}(\{X\})|=n+1$. For a mixed example, $X=\{1',\dots,n'\}$ has $|X|=n$, $|Y|=1$, $|\operatorname{TC}(\{X\})|=n+2$. It’s easy to cook up similar examples for other combinations of cardinalities.

Answer 3

The assumption is incorrect because the reverse graph H(X) might not be extensional (i.e. it might not satisfy $(\forall z (z,x) \leftrightarrow (z,y)) \rightarrow x=y$). An example is $X=\{\{1\},\{2\}\}$.