Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If a certain property of graphs cant not be expressed by a first order logic sentence $\phi$ over $\Sigma$ then can we say with confidence that such as property can not be expressed even by a an infinite family of FOL sentences $\eta$ over $\Sigma$ ?

$\Sigma$ is the vocabulary {E,=} used to represent graph where E is a binary predicate and = has the usual meaning.

EDIT: What if the graph is directed?

share|improve this question
3  
I'm not sure what you mean by "infinite FOL sentences" here. But what about the property "$G$ is finite"? This is not a first order property but is expressible by the infinite disjunction of the sentences "$G$ has $n$ vertices". –  Robin Chapman Aug 28 '10 at 7:35
1  
And if you want conjunction, you can use the negation of Robin's example, i.e. "$G$ is infinite". –  Kaveh Aug 28 '10 at 8:03
3  
Another standard example would be "bipartite" which is not expressable by a first order formula but can be axiomatized by an infinite first order theory. –  Dave Marker Aug 28 '10 at 13:26
1  
Could someone expand their comment as an answer? I realize the question is still a little vague, but a reasonable enough interpretation would be: is every first-order theory finitely axiomatizable? –  François G. Dorais Aug 28 '10 at 18:01
1  
@Francois: Rado graph (known sometimes as "the random graph") isn't finite. I think that if anything then the answer should be directed towards "Are there SOL (or higher) theories about graphs that cannot be expressed in FOL?". –  Asaf Karagila Aug 28 '10 at 23:00

2 Answers 2

up vote 6 down vote accepted

I think none of the two answers so far really addresses the edited version of the question which deals with infinite families of first order sentences.
The following graph properties (among others) can be expressed by infinitely many first order sentences, but not by finitely many (note that finitely many is equivalent to a single one):

(1) The graph is infinite: Take the collection of all sentences $\phi_n$ where $\phi_n$ states that the graph has at least $n$ vertices. A compactness argument shows that this is not finitely axiomatizable. (This is Kaveh's comment.)

(2) The graph is bipartite. Take the collection of sentences $\psi_n$ where $\psi_n$ says that the graph has no cycles of length $2n+1$. (This is Dave Marker's comment.)

It is possible to construct infinitely many different properties of graphs or directed graphs of this nature. Just take the property saying that for a fixed finite graph $H$, the graph $G$ contains infinitely many disjoint copies of $H$.

It is worth pointing out that "the graph is finite" i.e., the opposite of (1), cannot be expressed by even infinitely many first order sentences.
(Given a first order theory $\Phi$ that is satisfied by all finite graphs, add infinitely many constants to your vocabulary. Then, by compactness, the theory consisting of $\Phi$ together with infinitely many sentences saying that the constants are pairwise distinct has a model, an infinite graph satisfying $\Phi$.)

Similarly, not being bipartite is not axiomatizable by a first order theory (take an ultraproduct of the graphs $C_{2n+1}$, $n\in\mathbb N$, where $C_{2n+1}$ is the cycle of length $2n+1$).

Being connected is also not expressible even by an infinite first order theory. I currently don't know whether non-connectedness is first order axiomatizable. I asked this here.

share|improve this answer

For directed graphs, the notion P(x,y) which represents "there is a directed path from vertex x to vertex y" can be stated as a disjunction (or) of existential statements of differing lengths (one for each nonnegative integer), one of which could be "there exists u,v,w such that xEu and uEv and vEw and wEy", or "there is a directed path from x to y that has exactly 4 edges" . The comments give more examples, some of which can be extended to "The model admits one of a certain (in some sense increasing) family of configurations" .

Gerhard "Ask Me About System Design" Paseman, 2010.08.29 IST

share|improve this answer

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.