Foundation of mathematical objects modulo isomorphism in ZFC

Question

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?

Answer 1

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.

Answer 2

"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)$.

Answer 3

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.