compactness model theory question

173 Views Asked by At

Let $\sigma$ be a set of first-order formulas including the axioms of equality. Suppose that for every $n\in\mathbb{N}, \sigma$ has a satisfying model $M_n$ whose domain is finite and has at least $n$ distinct elements. Prove that the set $\sigma$ must have a model with infinite domain.

Edit: Here's my revised attempt.

By the compactness theorem, a $\sigma$ has a model iff every finite subset of $\sigma$ has a model. To show that $\sigma$ has a model with infinite domain, I need to add sentences to $\sigma$ to construct an infinite model, that satisfies $\sigma$ equipped with these sentences and thus $\sigma$, though I'm not sure how to find these sentences.

1

There are 1 best solutions below

0
On BEST ANSWER

Define sentences $\phi_i$ as follows:

$$ \phi_i = \exists x_1, x_2, \ldots, x_i. \bigwedge_{1 \le m < n \le i} x_m \neq x_n $$

I.e., (given the equality axioms), $\phi_i$ holds in a model $M$ iff $M$ has at least $i$ distinct elements. Let $\sigma' = \sigma \cup \{\phi_1, \phi_2, \ldots\}$. By assumption, any finite subset of $\sigma'$ has a model. Hence by the compactness theorem, $\sigma'$ has a model,$M$, say. But then the equality axioms together with each $\phi_i$ all hold in $M$, so $M$ must be infinite.

[Aside: the only equality axiom that is actually relevant here is reflexivity: $\forall x. x = x$.]