I'm trying to learn some model theory with David Marker's book, and came across the exercise of showing that the class of Acyclic Finite Graphs is elementary. Here's my attempt:

Let $\mathcal L = \{\sim\}$ be the language of graphs, where $v_1 \sim v_2$ if there is an edge from $v_1$ to $v_2$. Then we can define

$$ \phi(n) = \exists v_1 \exists v_2 \exists p_1 \cdots \exists p_n v_1 \sim p_1 \land p_1 \sim p_2 \land \cdots \land p_n \sim v_2 \land \left(\bigwedge_{i \neq j} p_i \neq p_j \right) \land v_1 \sim v_2$$

Basically $\phi(n)$ states that there exists two vertices $v_1, v_2$ such that there is a path of length $n$ connecting them through distinct vertices $p_1, \dots, p_n$. Then, we also require that $p_1, \dots, p_n$ are distinct. Lastly we requrie that $v_1$ and $v_2$ share an edge.

So if we define

$$T = \{\phi(n) : n > 0\} \cup \text{Graph Axioms}$$

it would seem to me that we have defined a theory in the language of graphs such that exactly all graphs with no finite cycles.

I also want to require that the graph is finite, but I'm unsure how to do so. Requiring it to be infinite is easy, since we can for each $n$ write a sentence that there are exactly $n$ distinct elements and no more, and then take the collection of the negation of those sentences. But I'm unsure how to write a collection of sentences that force a finite structure.

My questions are:

1) How would I require that the graph is finite in FO?

2) If I can't do so, is there any way for me to also require that an infinite cycle cannot exist?

Any help would be appreciated.

  • $\begingroup$ What is an "infinite cycle"? $\endgroup$ Apr 1 '20 at 16:07
  • $\begingroup$ I just assumed that infinite cycles could exist. I was imagining the graph of real numbers $[0, 1]$, where there is an undirected edge from $a$ to $b$ if $a < b$, so the path that goes through all numbers reals in order from $0$ to $1$, and lastly from $1$ to $0$ immediately would be an infinite cycle. It's possible that this path is not well-defined though, since of course the first "step" from $0$ doesn't really exist. In the case that infinite cycles don't exist, then maybe only the first of my questions makes sense. $\endgroup$ Apr 1 '20 at 16:14
  • $\begingroup$ Note that the graph you describe is the complete graph on $[0,1]$, since for any $a\neq b$, either $a < b$ or $b < a$, an in either case you put an undirected edge between $a$ and $b$. The notion of "infinite cycle" doesn't really make sense. $\endgroup$ Apr 1 '20 at 16:17
  • $\begingroup$ Ah yes you're correct, it would be a complete graph. So I guess there are no Hamiltonian paths on infinite graphs, even if they are complete then? $\endgroup$ Apr 1 '20 at 16:19
  • $\begingroup$ In any case, where did you come across this exercise? I don't think it's in Marker (unless you're referring to Exercise 1.4.5(e), which is to show that the class of trees is elementary). $\endgroup$ Apr 1 '20 at 16:20

First, you mention "infinite cycles". Let's agree that a cycle in a graph is a path which starts and ends at a vertex $v$ and otherwise does not visit any vertex more than once. By this definition, every cycle is finite, since an infinite path fails to have a starting point or fails to have an ending point or both.

Your sentence $\phi(n)$ almost expresses "there exists a cycle of length $n+2$". I say almost because you've forgotten to require that $v_1$ and $v_2$ are distinct from the $p_i$ as well. So for example the graph $$a\sim b\sim c$$ satisfies $\varphi(2)$, setting $v_1 = a$, $v_2 = b$, $p_1 = b$, $p_2 = c$. But this graph does not have a cycle (of any length).

Ok, let's say we've fixed this problem, and now we have a family of sentences $\phi(n)$ where $\phi(n)$ expresses "there exists a cycle of length $n+2$". Now we want to axiomatize the acyclic graphs. Your theory $$T = \{\varphi(n)\mid n>0\}\cup \text{Graph Axioms}$$ axiomatizes the class of graphs which do contain a cycle of every possible length. Do you see what you need to do to fix this axiomatization?

Once you've fixed that problem, you'll be convinced it's possible to axiomatize the class of acyclic graphs. But you've asked about finite acyclic graphs.

The class of finite ayclic graphs is not elementary. Usually, if you want to show that some class is not elementary, you use the compactness theorem. Let $\psi_n$ be the sentence asserting "there are at least $n$ distinct elements". Suppose for contradiction that there was some theory $T$ axiomatizing the finite acyclic graphs. Consider $T' = T \cup \{\psi_n\mid n\in \mathbb{N}\}$. By compactness, $T'$ is consistent: if $\Delta \subseteq T'$ is a finite subset, let $N$ be maximum such that $\psi_n\in \Delta$. Then any finite acyclic graph of size greater than $N$ is a model of $\Delta$ (for example, take a large graph with no edges). So $T'$ has a model $M$. But then $M\models T$ is a finite acyclic graph, but $M\models \psi_n$ for all $n$, so $M$ is infinite. Contradiction.

The exact same argument shows that if $K$ is any class of finite structures containing arbitrarily large finite structures, $K$ is not elementary. So usually, you cannot axiomatize the class of "finite X".

The exercise in Marker you refer to asks you to show that the class of trees is elementary. Unfortunately, there are many definitions of "tree" in mathematics. I think the definition that Marker has in mind is the one from order theory: a tree is a partially ordered set $T$ with a minimal element such that for each element $v\in T$, the set of predecessors of $v$, ${\downarrow}v = \{u\in T\mid u\leq v\}$, is linearly ordered.

Here are some other common definitions of "tree" which are not elementary (and it's a good exercise to try to prove this in each case by compactness):

  • A tree is a connected acyclic graph.
  • A tree is a partially ordered set with a minimal element, such that for each element, the set of predecessors of that element is well-ordered.
  • A tree is a directed graph with a specified vertex (the root), such that each vertex other than the root has exactly one outgoing edge, and the path formed by following these outgoing edges from each vertex eventually leads to the root.

You can find lots of relevant questions on this site by searching for "not elementary" or "not axiomatizable".

  • $\begingroup$ Forgot to add the $\neg$ to my question. Thanks for the not about $v_i$ being distinct from $p_i$, and for the information on the compactness theorem. $\endgroup$ Apr 1 '20 at 17:39

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.