MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Recently I saw the abstract of a paper by Nash-Williams: ``Should axiomatic set theory be translated into graph theory?''. The abstract, taken from Mathscinet says the following:

The author translates the Zermelo-Fraenkel axioms for set theory ($ZF$) into graph-theoretic language by replacing "set'' by "vertex'' and the membership relation "$∈$'' by the preneighborhood relation "$→$''. A digraph $D$ is an ordered pair $(V(D),E(D))$ such that $V(D)$ is a class (of vertices) and $E(D)⊆V(D)×V(D)$ is the subclass of ordered pairs $(ξ,η)$ such that $ξ$ is a preneighbor of $η$. He describes those graph-theoretic properties a digraph must satisfy in order to be a model of $ZF$ (with or without the axiom of choice ($AC$)). The theorem that $AC$ is independent of $ZF$ can then be formulated as a theorem of graph theory asserting the existence of certain kinds of digraphs.

The author proposes that a translation of this and other independence proofs might yield further insight into why the theorems are true. He also suggests that a textbook on axiomatic set theory as the study of digraphs satisfying certain conditions might increase its accessibility to nonspecialists. However he cautions that translations of independence theorems from one language to another must justify their existence by achieving some substantial progress in either set theory or graph theory.

Now my question is:

Question. Are there any extra works regarding the authors's suggestion ``other independence proofs might yield further insight into why the theorems are true.''?

share|cite|improve this question
Unfortunately I could not find the paper itself, but I am very interested in obtaining a file of the paper too. – Mohammad Golshani Jan 6 at 8:11
Some set theoretic axioms also have a graph theoretic equivalent version. For example the failure of Freiling's axiom of symmetry at $\kappa$ ($\sf AS_{\kappa}$) is equivalent to the statement that the complete graph on $P(\kappa)$, can be so directed, that every node leads to at most $\kappa$ - many nodes. – Morteza Azad Jan 6 at 14:38
What is really interesting (at least to me) is the following (from the same wikipedia entry): " the case of $\kappa$=$\aleph_0$, this translates to: The complete graph on the unit circle can be so directed, that every node leads to at least countably-many nodes." I find, in this case, the term "unit circle" extremely vague. Since, for $\kappa$=$\aleph_0$, $2^{\aleph_)}$ $\Leftrightarrow$ $\lnot$$\mathbf AX_{\aleph_0}$ (just the continuum hypothesis for $ZFC$), since $CH$ is independent of $ZFC$, how would graphically define the notion of adding one Cohen (or Random) real to the – Thomas Benjamin Jan 6 at 15:35
(cont.) "unit circle"? – Thomas Benjamin Jan 6 at 15:36

Although it may seem on the face of it that this proposal is just a question of terminology — yes, a model of set theory is a certain kind of acyclic digraph — nevertheless, my opinion is that one can indeed get some insight by thinking this way.

In particular, the main results of my paper on the embedding phenomenon arose out of an explicitly graph-theoretic perspective on the models of set theory, viewing the models of set theory as certain special acyclic digraphs.

Joel David Hamkins, Every countable model of set theory embeds into its own constructible universe, J. Math. Log. 13 (2013), no. 2, 1350006, 27. blog post

For example, I proved that the countable models of set theory are linearly pre-ordered by embeddability: for any two such models, one of them is isomorphic to an induced subgraph of the other. Furthermore, embeddability is determined by the heights of the models, and from this it follows that there are precisely $\omega_1+1$ many bi-embeddability classes. So actually, the countable models of set theory are pre-well-ordered by embeddability! Every nonstandard model of set theory is universal for all countable acyclic digraphs.

The proof uses universal digraph combinatorics, including an acyclic version of the countable random digraph, which I call the countable random $\mathbb{Q}$-graded digraph, and higher analogues arising as uncountable Fraisse limits, leading eventually to what I call the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, which is closely connected with the surreal numbers.

It happens that I am just now at the JMM in Seattle, where I will speak on The hypnagogic digraph, with applications to embeddings of the set-theoretic universe on Friday afternoon at the special session on the surreal numbers.

Finally, let me mention that it is an open question whether one can prove in ZFC that there is no graph-embedding of the set-theoretic universe $V$ to the constructible universe $L$, when $V\neq L$. In a joint project currently underway with many authors, however, we have made some significant progress, without yet settling the full question.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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