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 xy. Let H(X) be the reverse graph of G(X) with (x,y) ∈ E(H) iff yx.

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


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}))?
  • $\begingroup$ If you are not assuming a form of the Foundation axiom, it may be possible. Otherwise, the directed graph of a set would resemble a well founded partial order whereas its reverse would often not. (Might not, anyway. I don't know what set would give rise to a graph that is the reverse of the graph of the first uncountable ordinal. Foundation or no.) Gerhard "Ask Me About System Design" Paseman. 2011.05.27 $\endgroup$ – Gerhard Paseman May 28 '11 at 0:22
  • $\begingroup$ I should restrict my question to finite sets, shouldn't I? I'll do! $\endgroup$ – Hans-Peter Stricker May 28 '11 at 0:27
  • 1
    $\begingroup$ I think if you can prove that the (finite) graph is a Hasse diagram of a lattice, then you can prove uniqueness by induction. Further, you can prove that given a finite lattice (possibly meeting some extra conditions), one can construct a unique set whose graph corrresponds to that lattice. Then you might find in the finite lattice theory literature more of what you want. I would add a partial-orders tag if I could. I also suspect the lattice is distributive. Gerhard "Ask Me About System Design" Paseman, 2011.05.27 $\endgroup$ – Gerhard Paseman May 28 '11 at 1:16
  • $\begingroup$ You probably want to restrict to hereditarily finite sets, that is sets whose transitive closures are finite. $\endgroup$ – Amit Kumar Gupta May 29 '11 at 2:36
  • $\begingroup$ Isn't the transitive closure of a finite well-founded set finite? $\endgroup$ – Hans-Peter Stricker May 29 '11 at 8:19

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\}\}$.

| cite | improve this answer | |
  • $\begingroup$ @Linda: You are right, of course. I made a small addition to my original question to reflect your answer. $\endgroup$ – Hans-Peter Stricker May 28 '11 at 6:37

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.

| cite | improve this answer | |
  • $\begingroup$ I think it's just a slightly sloppy formulation; the implied property is that $\operatorname{TC}(\{x\})$ and $\operatorname{TC}(\{\operatorname{dual}(x)\})$ have the same cardinality, which is true. $\endgroup$ – Emil Jeřábek Jun 11 '11 at 19:01
  • $\begingroup$ A more relaxed formulation allows a set to be represented by a non-extensional graph by ignoring repetitions. This is what Peter Aczel does in his book "Non-well-founded Sets". (Incidentally, in Aczel's formulation, which I follow, the arrows in the graph are reversed compared to the version stated in this question, so that the unique sink in Jerabek's answer becomes a unique source.) In this formulation a set has many graph representations but only one "canonical" (extensional) one. The problem is now that different representations of the same set give rise to different reverse sets. $\endgroup$ – Laurence Kirby Jun 13 '11 at 12:55

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.