# Compactness theorem

Let $$\Sigma$$ be a set of theorems, such that for every $$\varphi\in\Sigma$$ exists an arbitrarily large (<--- edited) finite model $$\mathcal{M}$$, with $$\mathcal{M}\models\varphi$$.

Show: It exists an infinite modell $$\mathcal{M}$$ with $$\mathcal{M}\models\varphi$$ for every $$\varphi\in\Sigma$$.

Hello,

I want to proof this statement, and might need some help. I think the compactness theorem is needed.

My idea ist the following:

I want to extend $$\Sigma$$, such that it has an infinite carrier set $$M$$ and conclude that for the resulting model $$\mathcal{M}=(M,\dotso )\quad\mathcal{M}\models\varphi$$ by using the compactness theorem. The actuall proof seems to be trivial:

Let $$\Sigma':=\Sigma\cup\{v_i\neq v_j: i\neq j\}$$. By assumption every finite $$\overline{\Sigma}\subset\Sigma$$ is satisfiable. Therefor $$\Sigma'$$ is satisfiable by the compactness theorem and has obviously an infinite carrier set, since we added an infinite amount of variables.

My thoughts do not need that $$\Sigma$$ contains theorems (hence formulas without free variables) and not general formulas. Am I mistaken with my proof?

• Do you mean to assume the models of each individual $\varphi$ are infinite, rather than finite? Otherwise this is trivially false (for instance, if the formula $\exists x\forall y(x=y)$ is in $\Sigma$). Commented May 29, 2016 at 2:12
• You need more hypotheses, unless "set of theorems" means something stronger than I think it is, let $\varphi$ be any formula that is neither a tautology or a contradiction, then $\Sigma = \{\varphi, \neg\varphi\}$ satisfies your hypotheses but not the conclusion. Commented May 29, 2016 at 2:15
• @Eric Wofsey: The task should be correct. The models of each individual $\varphi$ are assumed to be finite, which means, that the model has a finite carrier set. Commented May 29, 2016 at 2:28
• I found this statement on the internet, which seems related to mine: Let $T$ be a theory (therefor a set of formulas) with finite models. Than has $T$ an infinite model. The proof is similar to mine. Commented May 29, 2016 at 2:31
• That statement is certainly false: the theory consisting of only the sentence $\exists x\forall y(x=y)$ has a finite model but no infinite models. You need an additional hypothesis, such as that the theory has models of arbitrarily large finite cardinality. Commented May 29, 2016 at 2:36

Theorem: Let $\Sigma$ be a set of sentences such that every finite set of sentences from $\Sigma$ has arbitrarily large finite models. Then there is an infinite model of $\Sigma$.

Proof. Let $\pi_n$ be the assertion that our structure has at least $n$ distinct elements, and let $\Pi$ be the set of all the $\pi_n$. Since $\Pi$ has only infinite models, it is sufficient to show that $\Sigma \cup \Pi$ is consistent. By compactness, it is sufficient to show that $\Sigma \cup \Pi$ is finitely consistent.

Assume we are given a finite subset of $\Sigma \cup \Pi$. That is, we are given $\Sigma_0$ a finite subset of $\Sigma$ and $\Pi_0$ a finite subset of $\Pi$. Since $\Pi_0$ is finite, it can only include sentences $\pi_n$ up to some finite maximum $n_\max$. Therefore, to be a model of $\Pi_0$, it is sufficient to have size at least $n_\max$. By assumption, we can find $M \models \Sigma_0$ of size at least $n_\max$. Therefore $M \models \Sigma_0 \cup \Pi_0$. By previous statements, we have shown the desired result.

Note that it is necessary to strengthen the hypothesis to talk about finite sets of sentences from $\Sigma$, rather than just individual sentences. Otherwise, as @James mentioned in a comment, we obtain a counterexample whenever we allow $\Sigma$ to contain two sentences that contradict each other. Also, that's how compactness works: you need to know that $\Sigma$ is finitely consistent, not just that every sentence of $\Sigma$ is consistent.

We also have to allow that that every finite set of sentences has arbitrarily large finite models: it doesn't work if you just require $\Sigma$ to be finitely consistent and that each individual sentence has arbitrarily large finite models. Let $\varphi$ be a sentence such that both $\varphi$ and $\neg \varphi$ have arbitrarily large finite models. Then let $\Sigma$ consist of the following two sentences:

• "either the structure has exactly one element or $\varphi$ holds"
• "either the structure has exactly one element or $\neg\varphi$ holds."

Then $\Sigma$ is consistent, its only models have exactly one element, and each sentence in $\Sigma$ has arbitrarily large finite models.