# Musings in set theory: Reverse sets?

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

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}))?
-
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 –  Gerhard Paseman May 28 '11 at 0:22
I should restrict my question to finite sets, shouldn't I? I'll do! –  Hans Stricker May 28 '11 at 0:27
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 –  Gerhard Paseman May 28 '11 at 1:16
You probably want to restrict to hereditarily finite sets, that is sets whose transitive closures are finite. –  Amit Kumar Gupta May 29 '11 at 2:36
Isn't the transitive closure of a finite well-founded set finite? –  Hans 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\}\}$.

-
@Linda: You are right, of course. I made a small addition to my original question to reflect your answer. –  Hans 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.

-
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. –  Emil Jeřábek Jun 11 '11 at 19:01
Welcome to MathOverflow! –  Joel David Hamkins Jun 12 '11 at 1:16
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. –  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.

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

-