14
$\begingroup$

A recent question asked for graph properties that are first order axiomatizable but not finitely axiomatizable. Connectedness was mentioned in the context. Connectedness can be axiomatized in infinitary logic, but not in ordinary first order logic. Just take an ultraproduct of the paths $P_n$ of length $n$, $n\in\mathbb N$. The paths are connected, but the ultraproduct has exactly two vertices of degree 1 and these two are not joined by a path of any finite length. If connectedness was axiomatizable by a first order theory $\Phi$, then all the $P_n$ would satisfy $\Phi$ and hence the ultraproduct satisfies $\Phi$. But the ultraproduct is not connected, a contradiction.

I was wondering whether non-connectedness is first order axiomatizable. I guess it is not, but I don't have an argument for this right now.

An attempted proof goes as follows: Let $G_n$ be the disjoint union of two cycles of length $n$. Take an ultraproduct $H$ of the $G_n$. Now all vertices of $H$ have degree $2$ and there are no finite cycles. In other words, $H$ is the disjoint union of a family of infinite (in both directions) paths.
We were done if we could show that $H$ is elementary equivalent to the bi-infinite path (is there a notation for this graph?). I assume that this is the case, but I don't see why.

A different proof that non-connectedness is not first order axiomatizable would also be welcome (or an axiomatization).

$\endgroup$
8
  • $\begingroup$ ? Surely if $P$ is a first-order property then not-$P$ is too? $\endgroup$ Aug 29, 2010 at 7:49
  • 2
    $\begingroup$ @RC: If by a "first-order property" you mean the class of models of a theory, the answer to your question is no: see e.g. Section 2.5 of math.uga.edu/~pete/modeltheory2010Chapter2.pdf. (If you mean closed under elementary equivalence, the answer is yes. This is indeed an unfortunate terminological pitfall.) $\endgroup$ Aug 29, 2010 at 8:03
  • 1
    $\begingroup$ Thanks for the comments - I was indeed missing the point. :-( But isn't the ultraproduct of a bunch of disconnected graphs like the $G_n$ also disconnected. Map the vertices of each $G_n$ onto its set of components $C_n$. This will extend to a map of the corresponding ultraproducts $H$ and $D$. Won't adjacent vertices of $H$ map to the same element of $D$? And $D$ will have more than one point. I suspect I'm again missing something obvious... $\endgroup$ Aug 29, 2010 at 11:01
  • 1
    $\begingroup$ @RC: Yes, the ultraproduct of the G_n is disconnected, but I somehow believe that every component of the ultraproduct has the same first order theory as the whole thing. (I.e., first order logic does not distinguish between a single bi-infinite path and the disjoint union of several disjoint bi-infinite paths (in this case, the ultraproduct).) Whether my intuition is correct in this point is part of the question. $\endgroup$ Aug 29, 2010 at 11:39
  • 1
    $\begingroup$ I just realized that my ultraproduct construction is probably pointless. If a single bi-infinite path is elementarily equivalent to the disjoint union of two such paths, then neither connectedness nor disconnectedness is axiomatizable in first order logic. Thanks to Robin Chapman for the last comment. $\endgroup$ Aug 29, 2010 at 11:44

3 Answers 3

11
$\begingroup$

Stefan's original idea is realized in the following observation, which shows that one $\mathbb{Z}$-chain is elementary equivalent to two such chains.

Theorem. The theory of nontrivial cycle-free graphs where every vertex has degree $2$ is complete.

Proof. All models of uncountable size $\kappa$ consist of $\kappa$ many $\mathbb{Z}$ chains, and hence are isomorphic. Thus, the theory is $\kappa$-categorical, and hence complete. QED

Thus, all cycle-free graphs with every vertex of degree $2$ have the same first order theory. In particular, the graph consisting of one $\mathbb{Z}$-chain is elementary equivalent to the graph consisting of any number of such $\mathbb{Z}$ chains. Since the first graph is connected and the latter are not, it follows that neither connectivity nor disconnectivity are first-order expressible as theories in the language of graph theory.

$\endgroup$
6
  • $\begingroup$ +1: if you had given this argument in July, I probably would have mentioned it in my (half)-course on introductory model theory and its applications. $\endgroup$ Aug 29, 2010 at 16:41
  • $\begingroup$ Thanks Joel. I have no idea why I didn't think of categoricity in the uncountable. $\endgroup$ Aug 29, 2010 at 17:17
  • $\begingroup$ This is a nice argument! It is also true, by reduction from the property over linear orders "the cardinality of the universe is even", that neither connectedness nor disconnectedness is FO-definable over finite graphs. See Section 3.6 of Libkin's Elements of Finite Model Theory. $\endgroup$ Aug 30, 2010 at 10:06
  • 2
    $\begingroup$ @AS: I believe that you are talking about properties that can be described by a single first order axiom. My question was about an infinite set of axioms. Every property of finite graphs can be axiomatized by infinitely many axioms. Why? Every property is described by countably many forbidden finite graphs. For each forbidden finite graph, there is a sentence that says that the graph under consideration is not isomorphic to that forbidden graph. The collection of all these sentences axiomatizes the property over finite graphs. $\endgroup$ Aug 30, 2010 at 17:03
  • $\begingroup$ Stefan, you are right: my comment above is tangential. Thanks for suggesting a canonical construction of a countable axiomatization for any property of finite structures. Could this be made to work for $\omega$-categorical structures also? Poizat, Marker and (shorter) Hodges don't obviously cover this. $\endgroup$ Aug 30, 2010 at 20:53
10
$\begingroup$

The class of non-connected graphs is not axiomatizable. To see this, consider $\mathbb{Z}$ as a graph with $i$, $j$ connected by an edge if and only if $|i-j|=1$. Then a simple compactness argument yields a non-connected graph $\Gamma$ such that $\Gamma$ is elementarily equivalent to $\mathbb{Z}$; ie $\Gamma$ and $\mathbb{Z}$ satisfy precisely the same first order sentences. Since $\mathbb{Z}$ is connected and $\Gamma$ is non-connected, the result follows.

$\endgroup$
1
  • $\begingroup$ Simon, thanks for the answer. I accepted Joel's because his is more explicit and he directly verifies my conjecture. $\endgroup$ Aug 29, 2010 at 17:25
0
$\begingroup$

I haven't thought about model theory in a while but I'll give this a shot. First, by bi-infinte graph, I assume that you mean $\mathbb{Z}$ in which the only edges are those adjoining adjacent vertices, right?

Does the theory of cycle-free graphs admit quantifier elimination? If so, elementary equivalence follows from the fact that the isomorphism type of every finite substructure (or "type") in $H$ and $\mathbb{Z}$ is expressible by a formula.

However, if I think about a direct back-and-forth argument, I'm worried about the following apparent obstruction. Say $H= H_0 \cup H_1$, where $H_i$ are the paths. Suppose that one already has a partial isomorphism $\{(h_0, z_0), (h_1, z_1)\}$ starting a back-and-forth argument, where $h_i\in H_i$. Now $\mathbb{Z}$ satisfies a sentence, call it $f$, asserting that $z_0$ and $z_1$ are joined by a path of length $n$; clearly $H \not\models f$.

Did I just prove that the theory cannot not eliminate quantifiers? Sorry, I didn't mean to turn your question into another one.

$\endgroup$
1
  • 3
    $\begingroup$ Yes, by "bi-infinite path" I mean the graph on $\mathbb Z$ with successive numbers connected by an edge. I don't think the theory of cycle-free graphs (or, more specifically, of cycle-free graphs with all vertices of degree 2) has quantifier elimination. How would you say "$x$ and $y$ are connected by a path of length 7" without using quantifiers? Your proof shows that the back-and-forth argument fails, but we knew that the theory of cycle-free graphs with all vertices of degree 2 is not $\omega$-categorical. $H_0$ could still be an elementary substructure of $H$, which is what I believe. $\endgroup$ Aug 29, 2010 at 9:15

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.