If $\mathfrak{A}$ is a finite $\tau$-structure and $\tau$ is a finite signature, is the isomorphic class $K_{\mathfrak{A}} = \{\mathfrak{B} \, | \, \mathfrak{A} \cong \mathfrak{B} \}$ FO-axiomatizable?

We know that for the case of infinite structures, this is clearly not FO-axiomatizable and we can prove that with Löwenheim-Skolem's theorem. However, is this also the case for a finite structure?

My guess is that since we can finitely count the number of elements in a finite structure, we can too axiomatize (in FO logic) the number of elements to ensure isomorphism. But the problem is we are not able to axiomatize the relations and functions to ensure that the isomorphism is valid under this signature?


The (more general) issue is whether a possibly infinite number of relation and function symbols can be axiomatized. The solution is that, when the model is finite, there are only a finite number of possible relations (of a given arity) and functions (of a given arity). So, for the relations and functions that are realized, we can axiomatize just one of them, and then for the other relation or functions symbols that do the same, we can write an axiom saying so.

For example, say $R(x)$ is a unary relation and $S(x)$ is realized as the same relation. Say $|M| = \{ a, b, c\}$ and $R(a)$, $\lnot R(b)$, and $R(c)$ hold. Then we can have axioms $(\exists x_1)(\exists x_2)(\exists x_3)(R(x_1) \land \lnot R(x_2) \land R(x_3))$ and $(\forall x)(R(x) \leftrightarrow S(x))$. More generally, we can make the first axiom specify some set of representatives of all the relations and functions that are realized, then we can add another axiom of the second type for each additional relation or function symbol.

If the signature is finite and the model has size $n$, then it only takes one sentence with $n$ leading existential quantifiers to completely specify the structure up to isomorphism, because the matrix of the sentence can completely specify everything.

  • $\begingroup$ Carl, while your comment is very much in place, $\tau$ is a finite signature here. $\endgroup$ – Asaf Karagila Aug 17 '14 at 3:58
  • $\begingroup$ @Asaf: Hmm. Thanks. Then the problem is entirely trivial, because a finite structure in a finite language is axiomatized up to isomorphism by a single sentence. $\endgroup$ – Carl Mummert Aug 17 '14 at 4:05
  • $\begingroup$ Quite. This was discussed before, too. $\endgroup$ – Asaf Karagila Aug 17 '14 at 4:11
  • $\begingroup$ Hmm. I didn't notice a vote to close, and the question is a couple days old. Is it a duplicate, then? $\endgroup$ – Carl Mummert Aug 17 '14 at 4:12
  • $\begingroup$ Most definitely probably. I remember answering it at least twice. :-) $\endgroup$ – Asaf Karagila Aug 17 '14 at 4:28

I assume by a 'first-order axiomatization' of $K_\mathfrak{A}$ you mean a consistent first-order theory in the language of $\mathfrak{A}$ whose models are all isomorphic to $\mathfrak{A}$. In this case, the answer is yes, the isomorphism class of any finite model is first-order axiomatizable. A standard back-and-forth argument should show you that elementary equivalence of finite models gives rise to an isomorphism, so $\text{Th}(\mathfrak{A})$ is your axiomatization.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.