Compactness theorem for first order logic on graphs

Question

I am having trouble answering a question on compactness theorem an cycles in graphs.

the problem is as follows:

Let $L$ be the first order language of graphs, where variables $ x,y,z $ represent vertices and $E(x, y)$ represents ‘there is an edge incident to $x, y$’. (It then asks to express in $L$ some statements such as the graph being simple and having a maximum degree which I have done.)

The next part: for each natural number $n$, the first order statement $σ_n$ of L expresses the statement that the graph has no cycles of length n or less. For each $n > 3$ give a finite graph $G_n$ that satisfies $σ_n$ which contains a cycle.

For this part I said for $n=3$: a graph on $w,x,y,z$ with only edges $E(w,x)∧E(x,y)∧E(y,z)∧E(z,w)$ satisfies this, and you can then extend this for any $n$: $G_n$ on vertices $x_1,x_2,....,x_{n+1}$ with only edges $E(x_1,x_2)∧E(x_2,x_3)∧....∧E(x_{n+1},x_1)$ satisfies $σ_n$.

The next part is where i get stuck: A statement $γ$ is true in all finite graphs containing a cycle. Use the Compactness Theorem and the graphs $G_n$ to show there is a graph satisfying $γ$ that has no finite cycle.

I know the compactness theorem states $Σ⊨σ→$ there is a finite $Σ_0⊆Σ$ such that $Σ_0⊨σ$ and we can use this the following way:

if for every finite $Σ_0⊆Σ$ there is a model $M_0⊨Σ_0$ then there is some $M⊨Σ$

but I'm not sure how to apply it here. Is it sufficient to say that if $G_c⊨$ means that for all finite graphs with cycles $γ$ is true, then taking the union of $G_c$ with one of $σ_n$ still keeps $γ$ true and this holds for all $n$, so taking $G_c$ with all $n$ means that $γ$ is true by compactness and therefore a graph in this union has no finite cycle but $γ$ is still true?

Answer 1

HINT: Let $\Sigma=\{\gamma\land\sigma_n:n\in\Bbb Z^+\}$. If $\Sigma_0$ is a finite subset of $\Sigma$, there is a maximum $n$ such that $\gamma\land\sigma_n\in\Sigma_0$; show that $G_{n+3}\vDash\Sigma_0$, and then apply the compactness theorem.

Answer 2

This is a standard exercise in compactness, and Brian's already pointed out the canonical solution, so I'll focus on addressing the questions you had about your approach.

Is it sufficient to say that if $G_c \models$ means that for all finite graphs with cycles $\gamma$ is true, then taking the union of $G_c$ with one of $\sigma_n$ still keeps $\gamma$ true and this holds for all $n$, so taking $G_c$ with all $n$ means that $\gamma$ is true by compactness and therefore a graph in this union has no finite cycle but $\gamma$ is still true?

The only way for "$G_c$" as you've described it to make sense is a series of statements of the form "for every induced finite subgraph of size $N$ of a model $\mathbb{M}$ of this theory, if any cycles show up in this subgraph, then $\gamma$ (reformulated as a quantifier-free proposition, with universal quantification replaced by a conjunction over the finitely many elements in the subgraph, and existential quantification replaced by a disjunction over the finitely many elements in the subgraph) holds on this subgraph."

If you try to take $G_c \cup \sigma_n$, then $\sigma_n$ will assert that the entire model $\mathbb{M}$ contains no cycles of length less than $n$.

If you take $G_c \cup \{\sigma_n\}_{n \in \mathbb{N}}$, then your entire model will have no finite cycles whatsoever. Of course, this applies to all of its finite induced subgraphs.

Note that this doesn't say anything about whether or not $\mathbb{M} \models \gamma$. This is where compactness comes in.

So, what if $G_c \cup \{\sigma_n\}_{n \in \mathbb{N}}\models \neg \gamma$? As you pointed out, by compactness, this is witnessed by a finite fragment $$\Delta \underset{\operatorname{fin}}{\subseteq} G_c \cup \{\sigma_n\}_{n \in \mathbb{N}}, \hspace{5mm} \operatorname{s.t.} \hspace{5mm} \Delta \models \neg \gamma.$$ Since by definition $\gamma$ holds for finite graphs containing cycles, it suffices to find such a graph, say $H$, with $H \models \Delta$. This will yield a contradiction.

For $\Delta$ and a model $H \models \Delta$, there is a largest $M$ and a largest $m$ such that the sentences "for all induced subgraphs of $H$ of size $M$, if a cycle shows up, then $\gamma$ holds", and "$H$ has no cycles of length $\leq m$" are asserted by $\Delta$ about $H$.

So you can take $H$ to be a long-enough cycle graph, say $\max(M,m) + 1$. Then all the sentences from $G_c$ are satisfied (vacuously), and all the sentences from $\{\sigma_n\}_{n \in \mathbb{N}}$ are satisfied, by construction. $H$ also satisfies $\gamma$, by construction. But this is a contradiction, so any model $\mathbb{M} \models G_c \cup \{\sigma_n\}_{n \in \mathbb{N}}$ also satisfies $\gamma$. In particular, you may as well take $\mathbb{M}$ to be the "infinite cycle graph", which is just an infinite line graph.

However, something fishy went on here: we never really needed the sentences in $G_c$, because we knew them a priori, so they would've showed up in the theories of our models anyways. So you really only need to look at $\gamma$ and the $\sigma_n$. Hence, why the canonical solution is the canonical solution.