# First-Order Definability of finite structures (negative result)

I am trying to wrap my head around this proof sketch that we did in class:

Proof: Finite structures are not first-order definable

Suppose that the set $$\Gamma$$ of first-order sentences defines the set of finite structures. Let $$\Sigma$$ be the set of sentences that defines the set of infinite structures$$~^{[1]}$$. Then every finite subset of $$\Gamma \cup \Sigma$$ is satisfiable. Therefore by compactness: $$\Gamma \cup \Sigma$$ is satisfiable. The witnessing structure must satisfy $$\Gamma$$ and hence is finite, but a finite structure cannot satisfy $$\Sigma$$ so we have obtained a contradiction.

$$~^{[1]}$$ This was established earlier in the lecture. $$\Sigma$$ is defined as $$\Sigma = \bigcup_{n \in \mathcal N} \exists^{\geq n}$$, where $$\exists ^{\geq n}$$ is defined as $$\exists x_1 \ldots x_n \bigwedge_{i \not= j} \neg (x_i = x_j)$$

The part that is unclear to me is marked in bold. How can I prove this result?

My take is:

• $$\Sigma$$ is satisfiable by any infinite structure. It's easy to see that all subsets of $$\Sigma$$, e.g. $$\{\exists^{\geq 10}\}$$, are satisfiable by any infinite structure.

• $$\Gamma$$ is satisfiable by assumption. By the compactness theorem, every finite subset of $$\Gamma$$ is satisfiable as well.

• Since every subset of $$\Sigma$$ is satisfiable and every subset of $$\Gamma$$ is satisfiable, any union of those subsets is satisfiable too.

I am fairly happy with the first two bullet points. But the last one looks incorrect to me. Any better suggestions? :)

## 1 Answer

As you may see, your last conclusion only guarantees $$\Gamma$$ and $$\Sigma$$ is satisfiable respectively; that is, we do not know $$\Gamma\cup\Sigma$$ is satisfiable or not.

Here is a correct argument: We can see that $$\Gamma\cup \{\exists^{\ge k} : k\le n\}$$ is satisfiable (by taking any finite structure of cardinality $$\ge n$$.) Since every finite subset of $$\Gamma\cup \Sigma$$ is a subset of $$\Gamma\cup \{\exists^{\ge k} : k\le n\}$$ for some $$n$$, $$\Gamma\cup\Sigma$$ is satisfiable.