# First order sentence modeled by an infinite graph

Suppose we have a sentence $\chi$ in the language $L = \left\{E\right\}$ of graphs, where $E$ is a binary relation symbol (intended to be there is an edge between $x$ and $y$).

And let the graph axioms be so that a model is a symmetric graph with no loops.

The question is suppose we have an infinite graph $\Gamma$ such that $\Gamma \models \chi$ ( $\chi$ is true in $\Gamma$) is it necessarily true that there are infinitely many finite graphs in which $\chi$ is true?

I feel like the answer is probably, yes. Because for any sentence it seems like if I have a subgraph of $\Gamma$ which somehow contains all the elements I "need" for $\chi$ , it must also model the sentence. However, I have been unable to formalize this intuition so I'm no longer even sure if its correct.

Also note that this is homework, so I'd appreciate if possible people can help me to get to the correct solution rather than posting an entirely complete solution.

-
Is $E$ a two-place predicate $E(x,y)$ intended to be interpreted as xy is an edge? If not, exactly what is it? – Brian M. Scott Nov 10 '12 at 6:16
@BrianM.Scott Yes sorry, let me add that in. – Deven Ware Nov 10 '12 at 6:17
What does it mean for a graph to entail a sentence? – Dan Brumleve Nov 10 '12 at 6:18
@DanBrumleve I mean that the graph is a model of the sentence, or that the sentence is true in $\Gamma$ I will edit this also. – Deven Ware Nov 10 '12 at 6:20
@Dan: That notation means that $\Gamma$ is a model of the sentence. – Brian M. Scott Nov 10 '12 at 6:20