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:

  1. Antireflexive
  2. Antisymmetric
  3. 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}$?


1 Answer 1


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:

The class of planar graphs is computably axiomatizable.

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}$.)

  • $\begingroup$ In your sentence $\phi_G$, you also need to assert the $x_i$ are distinct. And the characterization of planarity says you don't have copies of the bad graphs as subgraphs, not induced subgraphs (adding edges only makes it harder to be planar), so you should drop the conjunctions asserting non-edges. $\endgroup$ Dec 28, 2020 at 18:30
  • 2
    $\begingroup$ Also to the OP: it's a useful general fact (which is what's going on in Noah's ultraproduct construction in the last paragraph) that if a class is axiomatizable by an infinite set of sentences $T$, and it is finitely axiomatizable, then it is axiomatized by a finite subset of $T$. So to see that the class of planar graphs is not finitely axiomatizable, it suffices to show that there is no finite set of subdivided $K_5$s and $K_{3,3}s$ such that omitting that finite set implies omitting all subdivided $K_5$s and $K_{3,3}$s. $\endgroup$ Dec 28, 2020 at 18:33
  • $\begingroup$ @AlexKruckman Derp, fixed! $\endgroup$ Dec 28, 2020 at 18:43
  • $\begingroup$ Thanks for the answer and comments! $\endgroup$ Dec 28, 2020 at 18:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .