Maximal Directed Graph in Well-Foundedness and Extensionality? In my Introduction to Set Theory, we were told that an Intended Model of Set Theory can be a maximal directed graph in the following property $\Phi$.
Let $\Phi$ be the property of a directed graph $G$ saying:


*

*$G$ has no looping paths;

*$G$ has no infinite descending paths; and

*$G$ has no two vertices with exactly the same arrows pointing into them.


My question is: how can a graph $G$ be maximal in $\Phi$?
Consider $G$ to be a single vertex, $v_0$, with no edges. Then $G$ is satisfies $\Phi$.
But then construct a new graph $G'$ that is $G$ with a new vertex, $v_1$, and an edge from $v_0$ to $v_1$. Then $G'$ satisfies $\Phi$ with $G$ a proper subgraph of $G'$.
But then construct a new graph $G''$ that is $G'$ with a new vertex, $v_2$, and an edge from $v_1$ to $v_2$. Then $G''$ satisfies $\Phi$ with $G'$ a proper subgraph of $G''$.
Continue to do this forever, and you will never end up with a maximal graph in $\Phi$. Picture related. Help me understand where I'm thinking wrong?

 A: If you want to get a maximal such graph, it's true the sort of construction you have above won't work. Firstly, the graphs above are too simple: take the graph $G''^*$ which is $G''$ with a new vertex $v_{2.5}$ and new edges to $v_{2.5}$ from both $v_0$ and $v_1$. It's easy to check this satisfies $\Phi$, contains $G''$.
To show a construction that works, I first need to set up some gear. For a graph $G$ that satisfies $\Phi$, let $\mathsf S(G)$ be the collection of subgraphs that (A) satisfy $\Phi$, and (B) whose transitive closures have a unique top element. For $x\in \mathsf S(G)$, this top element will be denoted $\top_x$. Further, let us call an $A\in \mathcal P(\mathsf S(G))$ topless if there is no vertex $v$ in $G$ such that for every $v'\to v$, $v'=\top_x$ for some $x\in A$. Similarly, we say that $v$ tops $A\subset\mathsf S(G)$ if exactly the vertices $\top_x$, for $x\in A$, have an edge to $v$.
With that in place, we can produce larger and larger graphs by the following transfinite recursion:


*

*$G_0$ is the graph with one vertex and no edges.

*$G_{\alpha+1}$ has as vertices all those of $G_\alpha$, plus a vertex $v_A$ for each topless $A\subset\mathsf S(G_\alpha)$; it has all the edges of $G_\alpha$, plus new edges so that each $v_A$ tops $A$.

*For limit ordinal $\xi$, $G_\xi$ is $\bigcup_{\alpha < \xi}G_\alpha$.


I leave it to you to convince yourself that at each stage the graphs satisfy $\Phi$. The maximal graph is then the proper class $G_*$ with edges any edge that's in $G_\alpha$ for some ordinal $\alpha$, and likewise edges. It may be unsatisfying for it to be a proper class, but we already knew this was going to be the case: we already know that if we're working in $\mathsf{ZF}$ or some such, our theory can't prove the existence of a model of itself. But one can show that this graph $G_*$ would be isomorphic to one taking the sets of the cumulative hierarchy to be the vertices, and taking as edges the pairs $\langle a,b\rangle$ such that $a\in b$; if this graph were a set, then we could show that the cumulative hierarchy was, too.
So in a sense you're right that "there is no maximal $\Phi$ graph"; it will certainly not be a set. On the other hand, if we care to look at proper class graphs, then we have the above.
