Non-elementary

Not first-order, not easy.

Model Theory

Not first-order, not easy

In model theory, a class of structures is elementary if some single first-order theory axiomatises it exactly: $K$ is elementary iff there is a theory $T$ with $K = \{M : M \vDash T\}$. Most properties a working mathematician reaches for turn out not to be elementary. Finiteness is the standard example, and the proof is short enough to write out in full.

Suppose $T$ is a first-order theory, in some language $\mathcal{L}$, with arbitrarily large finite models, say a theory of groups or of linear orders. Suppose, for contradiction, that every model of $T$ is finite. For each $n \geq 1$, let

$$\varphi_n \;\equiv\; \exists x_1 \cdots \exists x_n \bigwedge_{1 \le i < j \le n} x_i \neq x_j,$$

the sentence asserting at least $n$ distinct elements, and set $\Gamma = T \cup \{\varphi_n : n \in \mathbb{N}\}$. Any finite subset $\Gamma_0 \subseteq \Gamma$ mentions only finitely many of the $\varphi_n$, so some $N$ bounds the ones it contains; since $T$ has a finite model with at least $N$ elements, $\Gamma_0$ is satisfiable. By compactness, $\Gamma$ is satisfiable too, so there is some $M \vDash \Gamma$. But $M \vDash \varphi_n$ for every $n$, so $M$ is infinite, while $M \vDash T$, contradicting the assumption that every model of $T$ is finite. No first-order theory can have exactly the finite structures as its models: finiteness is not elementary. Well-ordering fails to be elementary for the same reason, and so does torsion in groups.

Non-elementary is that theorem, and also a joke about how the subject feels twenty years after I last did any of it seriously.

I wrote an undergraduate thesis on Gödel's incompleteness theorems two decades ago. After that came a master's in logic and formal grammar, a PhD in computational linguistics, and a career in AI. Along the way, most of the logic itself quietly fell out of my head. This blog is where it's getting put back, evenings and weekends, alongside full-time work. It's a multi-year project, not a course with an end date.

Most of my work in AI rewards moving fast and staying on the surface, and I wanted something that rewards the opposite: understanding one thing properly, all the way down, rather than just well enough to use it. Logic is what I already know how to do that with. It takes doing the proofs, not reading about them, and it takes years rather than weekends.

What ends up here will mostly be notes from that work: proofs that took longer than they should have, places where the intuition was wrong, occasionally some history or philosophy when it changes how a piece of mathematics reads. There is no fixed schedule, and no promise that the whole plan survives contact with the material.