Walk me through the proof that the class of graphs is elementary.

97 Views Asked by At

I am attempting problem 1.4.5 in "Model Theory" by Marker, but I am very lost in terms of how to get started. So to help me with the process I would like someone to show me that the class of graphs is elementary. Note I picked graphs because it is not included in question 1.4.5. My primary problem is I am not sure what it entails to prove that the class of graphs is elementary. For example, if wrote down the axioms of graphs: $$\forall x \forall y ~ R(x,y) \rightarrow R(y,x)\\ \forall x ~ \neg R(x,x)$$

then have I shown the class of graph is elementary?

1

There are 1 best solutions below

2
On BEST ANSWER

Yes, this shows that the class of (undirected simple) graphs is elementary (in the language with one binary relation symbol).

This is because you have found a set of (first order) axioms which are satisfied precisely by graphs (in this language).

For some classes, it might be harder to find such an axiom system. It is also sometimes quite hard to show that a given class is not elementary -- the usual tool for that is Łoś's theorem (we find a set of elements of the class whose ultraproduct is not within it).