0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Within the context of this hint, also note that Łos' theorem will help prove that the resulting ultraproduct is infinite. $\endgroup$ – user231101 Oct 9 '15 at 22:30
  • $\begingroup$ 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. $\endgroup$ – user122424 Oct 10 '15 at 11:16
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 10 '15 at 16:39
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.