# Thread: Fol 10

1. ## Fol 10

Enderton 2.6.8

Assume that $\displaystyle \sigma$ is true in all infinite models of a theory $\displaystyle T$. Show that there is a finite number $\displaystyle k$ such that $\displaystyle \sigma$ is true in all models $\displaystyle A$ of $\displaystyle T$ for which $\displaystyle |A|$ has $\displaystyle k$ or more elements.

=============

The sentence for there are at least $\displaystyle k$ things for $\displaystyle k \geq 2$ is

$\displaystyle \lambda_2 \wedge \lambda_3 \wedge \ldots \wedge \lambda_k$, where

$\displaystyle \lambda_k = \exists v_1 \exists v_2 \exists v_3 \ldots \exists v_k( (v_1 \neq v_2 \wedge v_1 \neq v_3 \wedge \ldots \wedge v_1 \neq v_k \wedge v_2 \neq v_3 \wedge \ldots \wedge v_2 \neq v_k \wedge \ldots \wedge v_{k-1} \neq v_k)$

========

Any hint to get started?

Thanks.

2. ## Re: Fol 10

Originally Posted by logics
The sentence for there are at least $\displaystyle k$ things for $\displaystyle k \geq 2$ is

$\displaystyle \lambda_2 \wedge \lambda_3 \wedge \ldots \wedge \lambda_k$, where

$\displaystyle \lambda_k = \exists v_1 \exists v_2 \exists v_3 \ldots \exists v_k( (v_1 \neq v_2 \wedge v_1 \neq v_3 \wedge \ldots \wedge v_1 \neq v_k \wedge v_2 \neq v_3 \wedge \ldots \wedge v_2 \neq v_k \wedge \ldots \wedge v_{k-1} \neq v_k)$
The formula $\displaystyle \lambda_k$ alone says that there are at least $\displaystyle k$ elements in the universe of the structure. In other words, $\displaystyle \lambda_k\models\lambda_j$ for $\displaystyle j<k$.

Consider the set $\displaystyle T\cup\{\lambda_2,\lambda_3,\dots\}$ and use the form of compactness theorem from this thread.

3. ## Re: Fol 10

Originally Posted by emakarov
The formula $\displaystyle \lambda_k$ alone says that there are at least $\displaystyle k$ elements in the universe of the structure. In other words, $\displaystyle \lambda_k\models\lambda_j$ for $\displaystyle j<k$.

Consider the set $\displaystyle T\cup\{\lambda_2,\lambda_3,\dots\}$ and use the form of compactness theorem from this thread.
Compactness theorem says,

If every finite subset of $\displaystyle T\cup\{\lambda_2,\lambda_3,\dots\}$ has a model, then $\displaystyle T\cup\{\lambda_2,\lambda_3,\dots\}$ has a model. Therefore, $\displaystyle T\cup\{\lambda_2,\lambda_3,\dots\}$ has an infinite model.

How do I use the compactness theorem? If I use the compactness theorem, the hypothesis has to be hold.

4. ## Re: Fol 10

Originally Posted by logics
Compactness theorem says,

If every finite subset of $\displaystyle T\cup\{\lambda_2,\lambda_3,\dots\}$ has a model, then $\displaystyle T\cup\{\lambda_2,\lambda_3,\dots\}$ has a model.
Yes, but for this problem it is more convenient to use the version of the compactness theorem from the link in post #2.

5. ## Re: Fol 10

Originally Posted by emakarov
Yes, but for this problem it is more convenient to use the version of the compactness theorem from the link in post #2.
By compactness theorem of the link in post #2,

$\displaystyle \models_A \sigma$ , $\displaystyle \models_A \lambda_k$, and $\displaystyle \not\models_A \lambda_{k+1}$, for some finite number $\displaystyle k$.

However, the problem claims $\displaystyle \models_{A_1} \sigma$ , $\displaystyle \models_{A_1} \lambda_{k+r}$, and $\displaystyle \not\models_{A_1} \lambda_{k+r+1}$, .... as well, for some positive number r and some $\displaystyle A_1 \in \text{Mod T}$.

So we need a construction to establish the above, right?

Thanks.

6. ## Re: Fol 10

Originally Posted by logics
By compactness theorem of the link in post #2,

$\displaystyle \models_A \sigma$ and $\displaystyle \models_A \lambda_k$ for some finite number $\displaystyle k$.
I am not sure how this follows or what A is.

The fact that $\displaystyle \sigma$ is true in all infinite models of a theory $\displaystyle T$ means that $\displaystyle T\cup\{\lambda_2,\lambda_3,\dots\}\models\sigma$. By compactness theorem, $\displaystyle T'\cup\{\lambda_{i_1},\dots,\lambda_{i_n}\}\models \sigma$ for some finite $\displaystyle T'\subseteq T$ and some indices $\displaystyle i_1,\dots,i_n$. Since $\displaystyle T\models T'$ and $\displaystyle \lambda_k\models\lambda_j$ for all $\displaystyle k\ge j$, we have $\displaystyle T\cup\{\lambda_k\}\models\sigma$ for $\displaystyle k=\max(i_1,\dots,i_n)$.

7. ## Re: Fol 10

My understanding is,

$\displaystyle \sigma$ is true in all infinite models of a theory T by assumption.

By compactness theorem, $\displaystyle \sigma$ is true in some finite models of a theory T having cardinality k.

However, I think we still have to establish that $\displaystyle \sigma$ is true in all finite models of a theory T having cardinality greater than k.

Is this idea wrong?

8. ## Re: Fol 10

Originally Posted by logics
My understanding is,

$\displaystyle \sigma$ is true in all infinite models of a theory T by assumption.

By compactness theorem, $\displaystyle \sigma$ is true in some finite models of a theory T having cardinality k.
How do you make this conclusion? Compactness theorem does not talk directly about cardinality of models. It talks about cardinality of formula sets.