Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that the class of all cycle-free graphs can not be defined by a finite set of formulas.

I don't understand what definiability means in this context. Does it just mean that I could represent all cycle-free graphs with finitely many formulas? In that case, I think since each formla can only represent graphs with finitely many vertices, there is a limit to how many graphs a finite number of formulas could define. Therefore a finite set of formula can not define the class of all cycle-free graphs. Is this on the right track? If so, how should I make this argument more rigorous?

share|improve this question
    
Where did you get this problem? My guess is it means there does not exist a finite set of first-order formulas $\phi_1, ... \phi_n$ in the language of graphs such that $G$ is cycle-free if and only if $\phi_1, ... \phi_n$ are all true of $G$. –  Qiaochu Yuan Jul 21 '11 at 18:31
    
@Qiaochu Yuan: from my intro logic Course notes. Do you know where I can find similar problems? –  Mark Jul 21 '11 at 18:32
    
My interpretation is the same as Qiaochu’s. Have you seen the proof that the class of all finite sets cannot be defined in first-order logic? That might be helpful. The main tool that you need is the compactness theorem, specifically, the corollary that a sentence with arbitrarily large finite models has an infinite model. –  Brian M. Scott Jul 21 '11 at 19:11
add comment

1 Answer

up vote 3 down vote accepted

We will use the Compactness Theorem. Details depend on what book you are using, and where you are in the book. They depend also on whether we mean directed or undirected graphs, and also on whether we have loops and/or multiple edges. I will assume undirected, no loops, no multiple edges.

Consider the following infinite set of sentences $\phi_3$, $\phi_4$, $\phi_5$, and so on. We describe the $\phi_k$ informally, but they are easy to formalize.

The sentence $\phi_3$ says there is no cycle of length $3$. The sentence $\phi_4$ says there is no cycle of length $4$. And so on. It is not hard to write down $\phi_k$ that do the job. And it is clear that the cycle-free graphs are precisely the models of graph theory with added axioms the infinite list $\phi_3$, $\phi_4$, $\dots$.

Now suppose that there is a finite set of formulas, so without loss of generality a single formula $\psi$, such that the models of graph theory with $\psi$ added are precisely the cycle-free graphs.

Then the models of graph theory with $\psi$ added are precisely the same as the models of graph theory with the set $\{\phi_3,\phi_4,\phi_5,\dots\}$ added.

Then by Compactness (and Completeness) there is a finite collection of the $\phi_i$ which, together with the remaining axioms of graph theory, implies $\psi$.

So for some $n$, $\{\phi_3, \phi_4,\dots,\phi_n\}$ (plus graph theory) implies $\psi$.

This is impossible, for there are certainly graphs that have a cycle, but have no cycle of length $\le n$. Just take a necklace with $n+1$ beads.

To turn this into a proof using whatever theorems are, so far, in your particular book, may take a bit of translating.

A detail: How do we say there is no cycle of length $3$? Let us think about how to say there is no cycle from $x$ to $x$, of length $3$. We have to say that there do not exist $x_1$, $x_2$ which are distinct from each other and from $x$, such that $x$ is connected to $x_1$ by an edge, and $x_1$ is connected to $x_2$ by an edge, and $x_2$ is connected to $x$ by an edge. (Note again that this is for undirected graph, no loops, no multiple edges.) Now no cycle of length $4$ should be easy to write down.

Added: The post asks whether a certain kind of argument is on the right track. In a certain sense, the compactness argument above has a general flavour of the type that you describe, it may be a way of making your intuition rigorous. However, one could argue that since a formula can only "describe a finite number of groups," the notion of abelianness should not be definable by a formula. But it is definable by a simple formula. So one has to be careful. That said, many Compactness Theorem arguments have an almost mechanical character, and look much like the one detailed above. So after a while, in many cases, one can legitimately give the one-line proof "This follows from the Compactness Theorem."

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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