First-Order Definability of finite structures (negative result)

Question

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? :)

Answer 1

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.