3 xpand

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.

2 fix typo

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,
For every $a\ne b$ in $\operatorname{TC}(\{X\})$, there is $c\in\operatorname{TC}(\{x\})$ 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. 1 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.