William Angus

---

Mereology and the Philosophy of Mathematics Part II

Posted on Monday the 13th of October, 2025.

What’s This About?

One year ago, I wrote a blog post about the intersection of Philosophy and Mathematics (in the aid of Philosophy). This post is a direct continuation of that one, so I suggest that you read that first.

A Graph Example!

I am pleased to say that I have managed to come up with two graphs such that they are both proper subgraphs of each other (and so are non-isomorphic). I am also pleased to say that one of these two graphs is the random graph, and the other is a simple extension of it. The reason for my pleasure is that this is one of Peter Cameron’s favourite subjects (or at least it was). Moreover, Peter was my advisor during my undergraduate maths dissertation (and one of his suggestions for the topic was the random graph!) at St Andrews, and he has recently retired. As such, this post is dedicated to his long and successful academic career (which is surely not yet over)!

All information about the random graph is taken from (Cameron 1997)¹, which is accessible on the ArXiv here.

The Random Graph

The random graph (of which we shall shortly see there is almost certainly one up to isomorphism, justifying “the”) is formed by the graph on a countably infinite set $V$ of vertices, where there is an edge $e_{i,j}$ between (distinct) vertices $v_i$ and $v_j$ with probability $\frac{1}{2}$.

In order to prove that there is almost certainly one up to isomorphism, we show that any two graphs which satisfy the following property are isomorphic (and that with probability $1$, a countable random graph has this property):

$(\ast)\quad$ Given finitely many distinct vertices $u_1, \ldots, u_m$, and $v_1, \ldots, v_n$, there exists a vertex $z$ which is adjacent to all of $u_1, \ldots, u_m$, and none of $v_1, \ldots, v_n$.

Please see the paper for proofs!

A remarkable fact of the random graph is that it is universal; that is, for any countable graph $G$, $G$ is a subgraph of the random graph, which I shall denote $R$ henceforth.

Again, please see Peter’s paper for the proof.

Extending the Random Graph

Now, consider the graph $R^\top$, formed by adding a new vertex $\top$ to $R$ such that $\top$ is adjacent to every other vertex in $R^\top$. Clearly, then, $R$ is a subgraph of $R^\top$; and moreover, $R^\top$ is a subgraph of $R$ as $R$ is universal. So, all that’s left to show is that $R$ and $R^\top$ are not isomorphic.

Finishing Up

First note that the defining property $(\ast)$ of $R$ is clearly preserved by isomorphism. Therefore, it suffices to show that $R^\top$ does not satisfy $(\ast)$.

To this end, let $u_1$ be any vertex in $R$, and $v_1$ be $\top$. Then $(\ast)$ requires the existence of a vertex $z$ such that $z$ is not adjacent to $\top$ but is adjacent to $u_1$. This is impossible, as $\top$ is adjacent to every vertex. So, $(\ast)$ cannot be satisfied by $R^\top$.

Hence, $R$ and $R^\top$ are two non-isomorphic graphs which are subgraphs of each other. This is a clear counterexample to the antisymmetry of parthood.

Or Is It?

Well, clearly there are some problems with this being a putative counterexample. For one, it is only true that $R$ and $R^\top$ are not isomorphic with probability $0$. Clearly $R^\top$ is a random graph with probability $0$.

So maybe these measure theoretic (i.e., probabilistic) concerns are a problem – again, this requires further analysis.

Furthermore, one may still take issue with the fact that the graph $R^\top$ contains a vertex, $\top$, which is not contained in $R$. Thusly, it is perfectly possible to say that $R^\top$ is not a part of $R$. But, Mathematicians are often very keen to say that it is the structure of the object that truly matters, not the underlying sets; and I am sensitive to this view. And, there the “not a part of” argument doesn’t work, leaving just the measure theoretic concerns.

---

Comments