Musings in set theory: Reverse sets? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T09:21:04Z http://mathoverflow.net/feeds/question/66249 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66249/musings-in-set-theory-reverse-sets Musings in set theory: Reverse sets? Hans Stricker 2011-05-28T00:07:26Z 2011-06-11T18:30:40Z <p>Let the <a href="http://mathoverflow.net/questions/63993/characterization-of-transitive-closure-graphs" rel="nofollow"><em>transitive closure graph</em></a> of a set <em>X</em> be the graph <em>G(X)</em> with V(<em>G</em>)= TC({<em>X</em>}) and (<em>x,y</em>) ∈ E(<em>G</em>) iff <em>x</em> ∈ <em>y</em>. Let <em>H(X)</em> be the reverse graph of <em>G(X)</em> with (<em>x,y</em>) ∈ E(<em>H</em>) iff <em>y</em> ∈ <em>x</em>. </p> <p>I assume that the following holds:</p> <blockquote> <p>For every hereditarily finite set <em>X</em> there is a unique set <em>Y</em> such that <em>G(X)</em> is isomorphic to <em>H(Y)</em>.</p> </blockquote> <p><strong>Questions</strong></p> <p>Is this assumption correct? <em>[<strong>Edit</strong>: If the answer is no: for which X?]</em> Has this set <em>Y</em> been given a name (as a function of <em>X</em>)? Something like the <em>reverse set of X</em>? And has it attracted some interest? Can someone give a reference?</p> <hr> <p>Some simple facts:</p> <ul> <li><p>The finite von Neumann ordinals $\emptyset = 0, 1, 2, ...$ are reverse sets of themselves (<em>self-reverse</em> for short)</p></li> <li><p>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.</p></li> <li><p>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$. </p></li> </ul> <p>Further question:</p> <ul> <li>Is there a general correlation between the cardinalities of <em>X</em>, its reverse set <em>Y</em> and TC({<em>X</em>}) (= TC({<em>Y</em>}))?</li> </ul> http://mathoverflow.net/questions/66249/musings-in-set-theory-reverse-sets/66253#66253 Answer by Linda Brown Westrick for Musings in set theory: Reverse sets? Linda Brown Westrick 2011-05-28T02:09:50Z 2011-05-28T02:09:50Z <p>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\}\}$.</p> http://mathoverflow.net/questions/66249/musings-in-set-theory-reverse-sets/66440#66440 Answer by Emil Jeřábek for Musings in set theory: Reverse sets? Emil Jeřábek 2011-05-30T11:36:56Z 2011-05-30T13:26:49Z <p>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.</p> <p>For your question, this entails:</p> <ul> <li><p>$Y$ is unique if it exists.</p></li> <li><p>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,</p> <blockquote> <p>$Y$ exists if and only if the converse of $G(X)$ is extensional,</p> </blockquote> <p>which amounts to the following condition:</p> <blockquote> <p>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.</p> </blockquote> <p>Linda’s example shows that there are sets $X$ failing this condition.</p></li> </ul> <p>With regards to the “further question”: there is almost no correlation, except for the obvious bound that $|X|,|Y| &lt; |\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.</p> http://mathoverflow.net/questions/66249/musings-in-set-theory-reverse-sets/67530#67530 Answer by Laurence Kirby for Musings in set theory: Reverse sets? Laurence Kirby 2011-06-11T18:30:40Z 2011-06-11T18:30:40Z <p>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.</p> <p>Non-extensional graphs represent multisets, which always have duals, and the dual of a set is a multiset but not necessarily a set.</p> <p>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}}.</p> <p>At the end of the question it seems to be implied that $TC({x}) = TC({dual(x)})$ but this isn't true in general. </p>