Definitions:
a) Let $\sigma$ be a vocabulary. A property P is a set of $\sigma$-structures, P $\subset$ STRUCT($\sigma$).
b) Let $\phi$ be an FO sentence. Mod(φ) := {$\alpha$ : $\alpha$ ⊧ $\phi$} ($\alpha$ is a model)
b) A property P is said to be elementary/finitely axiomatizable (in FO)/FO-definable/FO-expressible if there is an FO sentence $\phi$ such that P = Mod($\phi$).
c) A property P is said to be extended elementary if there is a set of FO sentences Φ such that P = Mod($\phi$)
The task is as follows:
Let $\sigma$ be the graph vocabulary $\sigma$ = {E/2}
a) Show that the class of all bipartite graphs is extended elementary.
b) Show that bipartiteness is not FO-definable.
Does anyone have an idea on how to solve these tasks? My approch was to extend the graph vocabulary by the relations A/1 and B/1 which act as disjoint sets:
$\phi$ := $\forall x,y (E(x,y) \rightarrow (A(x) \land B(y))) \land \forall x (A(x)->\neg B(x) \land B(x) \rightarrow \neg A(x)) \land \forall x (A(x) \lor B(x)) \land \forall x,y ((A(x) \land B(y)) \rightarrow \neg E(x,y))$
I am unsure if my formula holds or how to express it without A,B (as an (infinite) set of formulas). Can someone please check this?
Please let me know if I used any terms incorrectly. I'll appreciate your help.
For (a), use that a graph is bipartite iff it contains no odd-length cycles. So bipartiteness can be defined by an infinite set of FO sentences, $\Phi=\{\phi_n:n\in\mathbb N\}$, where $\phi_n$ says that there is no cycle of length $2n+1$.
For (b), use the compactness theorem. If a single sentence $\psi$ expressed bipartiteness, then $\psi$ would be a logical consequence of $\Phi$ and therefore a logical consequence of a finite subset, say $\{\phi_n:n\in F\}$ for a finite set $F\subseteq\mathbb N$. But if $m$ is larger than all elements of $F$, then a cycle of length $2m+1$ satisfies $\{\phi_n:n\in F\}$ but does not satisfy $\psi$ (because it isn't bipartite).
The argument for (b) applies quite generally: If a property is extended elementary, say defined by $\Phi$, then the only way it can be elementary is to be defined by a finite subset of $\Phi$.