Let's define a simple graph as a model of $\{ \forall x (\lnot xRx), \forall x y (xRy \to yRx) \}$.
Consider the property of a graph $G$ being bipartite.
This property can be encoded with a first-order theory in the language of graphs but NOT with a first-order sentence in the language of graphs.
My question is twofold:
- Which notion of a first-order property does "first-order property" usually refer to?
- How do you distinguish properties that can be encoded with a sentence from ones that can be encoded with a theory?
What follows is a proof of the claim I'm making to support my question.
A graph is bipartite if and only if it does not contain any odd cycles.
As proof, pick a vertex in each connected component arbitrarily and begin coloring the graph greedily, alternating colors each time. This process succeeds if and only if there are no odd cycles. And the presence of an odd cycle would defeat any attempt to 2-color the graph.
This can be expressed with a first-order theory (called $T$) in the language $(R)$:
- $R$ is a simple graph.
- for all odd $n$, $\lnot \exists x_1 \cdots x_n ( \text{$x_1 \cdots x_n$ are all distinct and form a cycle of length $n$} )$
However, it cannot be expressed with a first-order $(R)$-sentence.
Proof:
- Suppose the sentence $\lnot \varphi$ held if and only if $R$ was bipartite.
- Thus $\varphi$ holds if and only if $R$ is not bipartite.
- Consider the theory $T \cup \{\varphi\}$. I will show that it is finitely satisfiable.
- Any finite subset $\Delta_0$ of $T \cup \{\varphi\}$ contains only finitely many sentences prohibiting odd cycles. Let $k$ be the smallest odd number such that a cycle of length $k$ is not prohibited by $\Delta_0$. Let the graph $G$ consist exactly of a cycle of length $k$. $G$ is not $2$-colorable, so it follows that $G \models \Delta_0$. $G$ is also a simple graph and so it satisfies the first pair of conditions in $T$ as well.
- Since $T \cup \{\varphi\}$ is finitely satisfiable, there exists a model $M$ such that $M \models T, \varphi$.
- However, $T$ is equivalent to $\lnot \varphi$, thus $M \models \varphi, \lnot \varphi$. This is a contradiction.