3
$\begingroup$

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?

Thanks in advance for your comments.

$\endgroup$
6
  • $\begingroup$ 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$). $\endgroup$ May 29, 2016 at 2:12
  • 4
    $\begingroup$ 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. $\endgroup$
    – James
    May 29, 2016 at 2:15
  • $\begingroup$ @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. $\endgroup$ May 29, 2016 at 2:28
  • $\begingroup$ 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. $\endgroup$ May 29, 2016 at 2:31
  • $\begingroup$ 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. $\endgroup$ May 29, 2016 at 2:36

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .