Axiomatizable class

From Learning Logic for Computer Science

An axiomatizable class is a class of structures over a fixed signature which can be described by first-order formulas.

Example The class of all strict partial orders is the class of all structures over the signature $\{ {<}/2\}$ where $<$ is interpreted by an irreflexive and transitive relation. In other words, this is the class of structures satisfying \begin{align} & \forall x_0 (\neg x_0 < x_0)\\ & \forall x_0 \forall x_1 \forall x_2 (x_0 < x_1 \wedge x_1 < x_2 \rightarrow x_0 < x_2) \end{align}

Formal definitions

Definition Let $\mathcal S$ be a signature and $\Phi$ a set of formulas without free variables. Then the class axiomatized by $\Phi$ is denoted $\text{Mod}(\Phi)$ and defined by \begin{align} \text{Mod}(\Phi) & = \{\mathcal A \mid \text{$\mathcal A$ is an $\mathcal S$-structure and $\mathcal A \mymodels \Phi$}\} \enspace. \end{align}

A class $\mathcal K$ of $\mathcal S$-structures is axiomatizable if there is some set $\Phi$ of $\mathcal S$-formulas without free variables such that $\mathcal K = \text{Mod}(\Phi)$.

Simplifying notation:

  • $\text{Mod}(\varphi)$ for $\text{Mod}(\{\varphi\})$.
  • $\text{Mod}(\varphi_0, \dots, \varphi_{n-1})$ for $\text{Mod}(\{\varphi_0, \dots, \varphi_{n-1}\})$.

Definition A class $\mathcal K$ of $\mathcal S$-structures is finitely axiomatizable if it is axiomatized by a finite set of $\mathcal S$-formulas without free variables.


There are many examples of axiomatizable classes, simply because first-order logic is quite expressive in this respect.


The basic orderings are finitely axiomatizable.

Algebraic structures

The basic algebraic structures are finitely axiomatizable:

  • groupoids and semigroups in the signature $\{ {\cdot}/\!/2 \}$,
  • monoids in the signatures $\{ {\cdot}/\!/2 \}$ and $\{1, {\cdot}/\!/2 \}$,
  • groups in the signatures $\{ {\cdot}/\!/2 \}$ and $\{1, {\cdot}/\!/2, {}^{-1}/\!/1 \}$,
  • commutative semigroups, monoids, and groups,
  • rings and fields in the signature $\{0, {+}/\!/2, 1, {\cdot}/\!/2, {<}/2\}$.

A good example for a class which is axiomatizable, but not finitely axiomatizable is the class of fields in the signature $\{0, {+}/\!/2, 1, {\cdot}/\!/2\}$, algebraically closed fields].