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

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?

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.
• In fact I have got so far to consider this particular ultraproduct, but I don't see what it looks like. What are the elements and the interpretation of $R$. Say, that $G_n$'s are $n$-element chains for simplicity. – user122424 Oct 10 '15 at 11:16
• @user122424: Say that $G_n$ is an $n$-element chain with vertices $1,\ldots,n$ in that order. Let $x^{(m)}\in\prod_n G_n$ be defined by $x_k^{(m)}=n$ if $k\ge n$, and $x_k^{(m)}=1$ otherwise. Show that $\{x^{(m)}_{\mathscr{U}}:m\in\Bbb Z^+\}$ is an infinite chain in the ultraproduct. – Brian M. Scott Oct 10 '15 at 16:39
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.