5
$\begingroup$

Suppose we want to define a notion of graph modulo isomorphism. The first thought that comes to mind is to consider the set of all graphs and then quotient it with respect to the equivalence relation induced by the notion of graph isomorphism, i.e. two graphs are equivalent if and only if they are isomorphic. A graph modulo isomorphism would be defined as an element of the quotient set. However, there is a small problem with this approach: the "set of all graphs" is actually not a set but a proper class in ZFC. And yet it seems pretty natural to me to consider two graphs as the same if they only differ by the name of their vertices and/or edges. We have the same problem if we restrict ourselves to finite graphs and also when we consider other mathematical structures such as groups or partial orders. Is there a way to overcome this issue and define standard mathematical objects modulo isomorphism in ZFC?

$\endgroup$
4
  • $\begingroup$ Why do "We have the same problem if we restrict ourselves to finite graphs"? $\endgroup$
    – Daron
    Dec 11, 2022 at 11:04
  • $\begingroup$ @Daron Because, if the class of finite graphs were a set, then the subclass of trivial graphs consisting of a single vertex would be a set. This essentially amounts to claiming that the class of all singletons is a set, which is false because, if it were a set, then the union of the elements of that set would be the set of all sets. $\endgroup$
    – Lele99_DD
    Dec 11, 2022 at 14:52
  • $\begingroup$ Oh you're right. $\endgroup$
    – Daron
    Dec 11, 2022 at 14:54
  • $\begingroup$ Not a way to overcome this in ZFC, but... You should check out the structure identity principle in univalent foundations, and univalent foundations more generally. It takes to heart the idea that equivalent (isomorphic) structures are the same. $\endgroup$ Dec 15, 2022 at 14:13

3 Answers 3

15
$\begingroup$

First, it should be noted that we rarely need isomorphism types to be treatable as individual objects. For example, "There are $17$ isomorphism types of fleem graphs" is shorthand for "There is a set $\mathcal{X}$ of fleem graphs such that $\vert\mathcal{X}\vert=17$ and every fleem graph is isomorphic to exactly one graph in $\mathcal{X}$." So this is usually not even something we want to do.

But what if you really want isomorphism types to be represented by sets somehow? Well, in fact there is a standard trick for handling this sort of issue: Scott's trick. Instead of the proper class sized "collection of all graphs isomorphic to $G$," we use the much smaller "collection of all graphs isomorphic to $G$ and of minimal rank." Precisely, say that the Scott isomorphism type of a graph $G$ is the unique set of the form $$S_G=\{H: H\cong G\mbox{ and }\forall\alpha<rk(H), \forall J\in V_\alpha(J\not\cong G)\}.$$ This is always a set. Here $rk(X)$ is the smallest ordinal $\beta$ such that $X\in V_\beta$.

Now this trick does not require the axiom of choice, but it does require the axiom of foundation (also called "regularity"). In the absence of foundation, if choice holds bof's alternate approach will work; if neither choice nor foundation hold, we're likely in trouble.

$\endgroup$
2
  • $\begingroup$ Can you point out, how $S_G$ ist not unrestricted comprehension? $\endgroup$
    – Damian
    Dec 11, 2022 at 9:59
  • $\begingroup$ @Damian Note that $S_G\subseteq V_\beta$ for some appropriate ordinal $\beta$ (namely, the smallest $\beta$ such that $V_\beta$ contains a graph isomorphic to $G$). So the existence of $S_G$ as a set follows from separation. $\endgroup$ Dec 11, 2022 at 17:28
5
$\begingroup$

"Graphs modulo isomorphism" are called isomorphism types of graphs. Scott's trick is useful when the axiom of choice is unavailable. In ZFC (which includes the axiom of choice) every set is in bijection with some ordinal number, so you can simply define the isomorphism type of a graph $G$ to be the set of all graphs $H$, isomorphic to $G$, whose vertex set $V(H)$ is the least ordinal number in bijection with $V(G)$.

$\endgroup$
1
  • 3
    $\begingroup$ It's worth noting that this is not just an "if-you-have-choice" alternative to my answer. Scott's trick does crucially rely on the axiom of foundation/regularity, while this approach doesn't. Basically, if you have foundation or choice you're good to go via whichever of these two tricks works (and if you've got both, then dance happily). In their simultaneous absence, though, things are wonky-badonky. $\endgroup$ Dec 10, 2022 at 20:35
1
$\begingroup$

Fix a Vertex Set

Suppose you are only interested in isomorphism classes of graphs with exactly 5 vertices. Then rather than consider the class of all 5 element sets, it is enough to consider graphs with vertex set $\{1,2,3,4,5\}$.

If you only want to deal with isomorphism classes of graphs with at most $\alpha$ many vertices, it is enough to fix a set $V$ with $|V|=\alpha$ and only consider graphs whose vertex set is contained in $V$.

There are no foundational problems here since there are at most $|\mathcal P(\mathcal P(V))|$ many such graphs.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .