Why finite structures are uniquely characterized?

Question

Somewhere I read that finite structures can be uniquely described (up to an isomorphism) using a sentence which is a conjunction of all atomic formulas, and their negation, and an another sentence that asserts the finiteness of the structure. Why this is true? How to prove it? What changes when the structure becomes of infinite cardinality?

Answer 1

Suppose $\mathcal{A}$ is a finite structure of size $n$, in a finite language $\mathcal{L}$. Let's first note that we can write a sentence $\varphi_n$ which asserts "There are exactly $n$ many elements": $$\varphi_n\quad\equiv\quad \exists x_1\exists x_2 . . . \exists x_n((\bigwedge_{1\le i<j\le n} x_i\not=x_j)\wedge\forall y(\bigvee_{1\le i\le n}x_i=y)).$$ This sentence says "There are $n$ elements, which are distinct, and such that any additional element is equal to one of them." That is, there are exactly $n$ elements.

Now, note that this sentence actually does a bit more: it gives names for each of the $n$-many elements. Namely, for $\psi$ a formula in the variables $x_1, x_2, . . . , x_n$, let $\varphi_n^\psi$ be the sentence $$\varphi_n^\psi\quad\equiv\quad \exists x_1\exists x_2 . . . \exists x_n((\bigwedge_{1\le i<j\le n} x_i\not=x_j)\wedge\forall y(\bigvee_{1\le i\le n}x_i=y)\wedge \psi(x_1, . . . , x_n)).$$ So $\varphi_n^\psi$ says $$\mbox{"The universe consists of the distinct elements $x_1, x_2, . . . , x_n$; and the statement $\psi$ is true about them."}$$

Now, what kind of information can we cram into $\psi$? The answer is, all the information (since the language $\mathcal{L}$ is finite)! Specifically, let $\mathcal{A}=\{a_1, a_2, . . . , a_n\}$ (note that there are many ($n!$) ways to enumerate $\mathcal{A}$; we pick one arbitrarily here). Since $\mathcal{L}$ is finite, there are only finitely many atomic and negated atomic sentences in the parameters $a_1, . . . , a_n$ (this is a good exercise); that is, the atomic diagram $At(\mathcal{A})$ of $\mathcal{A}$ is finite. This means we can take the conjunction of all these finitely many sentences, and the result is a single first-order sentence $\theta$ in the language $\mathcal{L}$ . . .

. . . using $a_1, a_2, . . . , a_n$ as parameters. But that's okay! Let $\psi$ be the formula gotten from $\theta$ by replacing $a_i$ with the variable $x_i$; then $\psi$ is a formula in the language $\mathcal{L}$, with free variables $x_1, . . . , x_n$. Now consider the sentence $\varphi_n^\psi$. This sentence says that there are exactly $n$ many elements, and that the way these elements relate to each other is precisely the way the elements of $\mathcal{A}$ relate to each other.

Exercise. Suppose $\mathcal{B}\models\varphi_n^\psi$ via a variable assignment $x_i\mapsto b_i$. Then show that the map $f: \mathcal{B}\rightarrow\mathcal{A}: b_i\mapsto a_i$ is an isomorphism.

---

Where does this go wrong if infinity slips in?

Well, if the structure is infinite - say, countably infinite - then in order to build "$\varphi_{\aleph_0}$," we need to quantify over countably infinitely many variables! That is, we need to write something like $$\exists x_1\exists x_2 ...\exists x_n...$$ But we can't do that in first-order logic. Additionally, we need to take infinite conjunctions and disjunctions, when we assert that the $x_i$s are distinct and that every element of the universe is an $x_i$. Again, not doable in first-order logic. What we need to make that work is infinitary logic; namely, to completely pin down a structure of size $\kappa$ for $\kappa$ infinite, we need the infinitary logic $\mathcal{L}_{\kappa^+\kappa^+}$.

Interestingly, if we just want to pin down a size-$\kappa$ structure $\mathcal{A}$ amongst structures of size $\le\kappa$, we can get away with less! For example, if $\mathcal{A}$ is countable in a countable language then there is an $\mathcal{L}_{\omega_1\omega}$-sentence $\varphi$ - the Scott sentence of $\mathcal{A}$ - such that any countable $\mathcal{B}$ satisfying $\varphi$ is isomorphic to $\mathcal{A}$. But $\varphi$ may have uncountable models . . .

For finite structures in an infinite language, things aren't so bad, but they still break. Building $\varphi_n$ still works; but when we come to the $\theta$-part, we get into trouble. In an infinite language, there are not only finitely many atomic and negated atomic sentences with finitely many parameters! So we need to use an infinite conjunction here. Specifically, a finite structure in an infinite language of cardinality $\kappa$ can be pinned down by a sentence in the infinitary logic $\mathcal{L}_{\kappa^+\omega}$.

(As an example of a finite structure in an infinite language, consider the language with countably infinitely many unary predicate symbols $U_i$, and the structure $\mathcal{A}$ with one element $a$ such that $U_i(a)$ holds for every $i$. It's a good exercise to show that no single sentence in the language pins down $\mathcal{A}$ up to isomorphism.)

EDIT: Actually, though, this is a bit misleading as Alex Kruckman points out above. Since all we need in this case is an infinite conjunction, it is still the case that a finite structure in an arbitrary language is characterized by its first-order theory. While this is not in general equivalent to a single first-order sentence, this is still much much better than an arbitrary $\mathcal{L}_{\kappa^+\omega}$-sentence.