# creating an infinite model

From the syntactic compactness theorem for first order logic, we get this nice (and useful) result:

Let T be a theory of first-order logic. If T has finite models of unboundedly large sizes, then T also has an infinite model.

###### Proof.

Define the propositions

 $\Phi_{n}\equiv\underline{\exists x_{1}\cdots\exists x_{n}.(x_{1}\neq x_{2})% \wedge\cdots\wedge(x_{1}\neq x_{n})\wedge(x_{2}\neq x_{3})\wedge\cdots\wedge(x% _{n-1}\neq x_{n})}$

($\Phi_{n}$ says “there exist (at least) $n$ different elements in the world”). Note that

 $\cdots\vdash\Phi_{n}\vdash\cdots\vdash\Phi_{2}\vdash\Phi_{1}.$

Define a new theory

 $\textbf{T}_{\infty}=\textbf{T}\cup\left\{\Phi_{1},\Phi_{2},\ldots\right\}.$

For any finite subset $\textbf{T}^{\prime}\subset\textbf{T}_{\infty}$, we claim that $\textbf{T}^{\prime}$ is consistent: Indeed, $\textbf{T}^{\prime}$ contains axioms of T, along with finitely many of $\left\{\Phi_{n}\right\}_{n\geq 1}$. Let $\Phi_{m}$ correspond to the largest index appearing in $\textbf{T}^{\prime}$. If $\mathcal{M}_{m}\models\textbf{T}$ is a model of T with at least $m$ elements (and by hypothesis, such as model exists), then $\mathcal{M}_{m}\models\textbf{T}\cup\{\Phi_{m}\}\vdash\textbf{T}^{\prime}$.

So every finite subset of $\textbf{T}_{\infty}$ is consistent; by the compactness theorem for first-order logic, $\textbf{T}_{\infty}$ is consistent, and by Gödel’s completeness theorem for first-order logic it has a model $\mathcal{M}$. Then $\mathcal{M}\models\textbf{T}_{\infty}\vdash\textbf{T}$, so $\mathcal{M}$ is a model of T with infinitely many elements ($\mathcal{M}\models\Phi_{n}$ for any $n$, so $\mathcal{M}$ has at least $\geq n$ elements for all $n$). ∎

Title creating an infinite model CreatingAnInfiniteModel 2013-03-22 12:44:29 2013-03-22 12:44:29 CWoo (3771) CWoo (3771) 9 CWoo (3771) Example msc 03B10 msc 03C07 CompactnessTheoremForFirstOrderLogic GettingModelsIModelsConstructedFromConstants