Is there a (finite) axiomsystem for the union of all classes of undirected graphs which are not finitely axiomatizable?

Question

Let $K$ be the class which contains all structures in the union of all classes of undirected graphs which are not finitely axiomatizable

I noticed that for example there are arbitrrily infinite many of such classes, for example one can look at the classes of infinite graphs which are distinguished by the existence of a node that has $m$ edges where $m\in M$ where $M$ is an arbitrary set. So I cannot use Skolem to say $K$ has only structures where the cardinality is bounded to say it is not axiomatizable. I have lso tried to find a way to prove that is not axiomatizeable by completeness theorem (Vollständigkeitssatz) and EF games. But I cannot find a way. I also cannot provide an axiom system.

Answer 1

This turns out to have a rather silly answer: every graph is an element of some non-finitely-axiomatizable class of graphs, and so your class of graphs is just the class of all graphs (hence axiomatized by $\{\forall x(x=x)\}$).

Here's one way to prove this. (Below I conflate graphs with their isomorphism types, so I'm only looking at isomorphism-closed sets of graphs.)

• First, consider a finite graph $G$. Let $\mathcal{X}$ be any non-finitely-axiomatizable set of graphs. If $\mathcal{X}$ contains $G$, we're done. Otherwise, consider $\mathcal{Y}=\mathcal{X}\cup\{H: H\cong G\}$; I claim that $\mathcal{Y}$ is also non-finitely-axiomatizable. To see this, note that since $G$ is finite there is a single sentence $\gamma$ characterizing $G$ up to isomorphism. If $\mathcal{Y}$ were finitely axiomatizable as $Mod(\psi)$ then we would have $\mathcal{X}=Mod(\psi\wedge\neg\gamma)$, which we know isn't the case.

• OK, now consider an infinite graph $G$. The set $\{H: H\cong G\}$ cannot be finitely axiomatizable (or indeed elementary at all), since every elementary class containing an infinite structure contains arbitrarily large structures.

So we're done.

---

We can try to avoid this by rephrasing the question as something like the following:

When is a graph $G$ an element of some axiomatizable but not finitely axiomatizable class?

The first bulletpoint above would still apply (in particular, note that $\mathcal{Y}=Mod(\{\varphi\vee\psi: \varphi\in Th(\mathcal{X})\}$), but the second would not. Instead, per bof's comment below we have to be a little more careful (and less silly): we observe that the set of all infinite graphs itself is not finitely axiomatizable.

(That's a consequence of the compactness theorem: the complement of a finitely axiomatizable class is an elementary class, and the class of finite graphs can't be elementary by compactness.)