Math Help - Fol 10

1. Fol 10

Enderton 2.6.8

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

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

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

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

$\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 $k$ things for $k \geq 2$ is

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

$\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 $\lambda_k$ alone says that there are at least $k$ elements in the universe of the structure. In other words, $\lambda_k\models\lambda_j$ for $j.

Consider the set $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 $\lambda_k$ alone says that there are at least $k$ elements in the universe of the structure. In other words, $\lambda_k\models\lambda_j$ for $j.

Consider the set $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 $T\cup\{\lambda_2,\lambda_3,\dots\}$ has a model, then $T\cup\{\lambda_2,\lambda_3,\dots\}$ has a model. Therefore, $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 $T\cup\{\lambda_2,\lambda_3,\dots\}$ has a model, then $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,

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

However, the problem claims $\models_{A_1} \sigma$ , $\models_{A_1} \lambda_{k+r}$, and $\not\models_{A_1} \lambda_{k+r+1}$, .... as well, for some positive number r and some $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,

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

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

7. Re: Fol 10

My understanding is,

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

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

However, I think we still have to establish that $\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,

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

By compactness theorem, $\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.