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? 🙂
Best 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.