Ultraproduct, axiomatizability,models,finite structures,language of one biary symbol

Question

If we know that first order axiomatizable theories have classes of models in one binary relational symbol $R$,say, closed under ultraproducts, how can I see that finite graphs, i.e. finite models in the language $\{R \}$ is not an axiomatizable class?

Answer 1

HINT: For $n\in\Bbb Z^+$ let $G_n$ be a graph with at least $n$ vertices. Show that the ultraproduct $\prod_{\mathscr{U}}G_n$ by a free ultrafilter on $\Bbb Z^+$ is an infinite graph.

Answer 2

In fact, a first-order theory $T$ which has arbitrarily large finite model has an infinite model. It is a consequence of compactness theorem; By assumption $T$ there is a model of $T$ satisfying $$\sigma_n := \exists x_1\exists x_2\cdots \exists x_n:\bigwedge_{1\le i<j\le n}(x_i\neq x_j)$$ so for each finite subset of $T\cup \{\sigma_n: n\in\Bbb{N}\}$ we can find a model satisfying it.

Of course, you can use the ultraproduct instead of applying compactness. By Łoś's theorem, an ultraproduct of models of $T$ is also a model of $T$. Moreover an ultraproduct of increasing size of finite models is infinite.