3
$\begingroup$

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?

$\endgroup$
9
  • 3
    $\begingroup$ 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". $\endgroup$ Aug 28, 2010 at 7:35
  • 1
    $\begingroup$ And if you want conjunction, you can use the negation of Robin's example, i.e. "$G$ is infinite". $\endgroup$
    – Kaveh
    Aug 28, 2010 at 8:03
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 28, 2010 at 13:26
  • 1
    $\begingroup$ 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? $\endgroup$ Aug 28, 2010 at 18:01
  • 1
    $\begingroup$ @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?". $\endgroup$
    – Asaf Karagila
    Aug 28, 2010 at 23:00

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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