In first order logic, consider the language $L$ consisting of one binary relation symbol. Consider the class $P$ of binary relations satisfying the following properties:
- Antireflexive
- Antisymmetric
- Planar (the relations can be drawn on a plane as digraphs without the edge-intersection)
Is $P$ (finitely/decidably) axiomatizable?
Can we use here the fact that finite graphs are planar iff they do not contain some subdivision (obtained by adding vertices to the edges) of $K_5$ and $K_{3,3}$?
Best Answer
For any finite graph $G$, there is a sentence $\varphi_G$ which holds exactly in the graphs containing no copy of $G$ as a (possibly non-induced) subgraph. Basically, fix an enumeration $\{a_i: 1\le i\le n\}$ of the vertices of $G$, let $X\subseteq\{1,...,n\}^2$ be the pairs of indices corresponding to edges in $G$, and let $$\varphi_G\equiv \neg\exists x_1,...,x_n([\bigwedge_{1\le i<j\le n}x_i\not=x_j]\wedge [\bigwedge_{\langle i,j\rangle\in X}x_iEx_j]).$$ This is very similar to the construction of a sentence characterizing a given finite structure (in a finite language) up to isomorphism.
The construction of $\varphi_G$ from $G$ is computable, and so we get that for any computable set of finite graphs $\mathcal{G}$ there is a computable theory $T_\mathcal{G}$ whose models are exactly the graphs not containing any element of $\mathcal{G}$ as a subgraph. The characterization of planarity by forbidden subgraphs corresponds to such a $\mathcal{G}$ (namely the set of all subdivisions of $K_5$ and $K_{3,3}$), and so we get:
Of course this leaves open the question of finite axiomatizability. In fact the class of planar graphs is not finitely axiomatizable, and this can be shown by proving that the class of non-planar graphs is not axiomatizable at all. This in turn can be proved via compactness - think about "stretching" a copy of (say) $K_5$ by subdividing the edges more and more. (Or if you prefer, run an ultraproduct construction: let $G_0=K_5$, let $G_{i+1}$ be gotten from $G_i$ by adding a vertex in the middle of each edge, and consider $\prod_{i\in\mathbb{N}}G_i/\mathcal{U}$ for some nonprincipal ultrafilter $\mathcal{U}$ on $\mathbb{N}$.)