Results 1 to 8 of 8

Math Help - Fol 10

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    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.
    Last edited by logics; November 14th 2011 at 01:20 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Fol 10

    Quote Originally Posted by logics View Post
    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<k.

    Consider the set T\cup\{\lambda_2,\lambda_3,\dots\} and use the form of compactness theorem from this thread.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Fol 10

    Quote Originally Posted by emakarov View Post
    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<k.

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Fol 10

    Quote Originally Posted by logics View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Re: Fol 10

    Quote Originally Posted by emakarov View Post
    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.
    Last edited by logics; November 15th 2011 at 01:35 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Fol 10

    Quote Originally Posted by logics View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Fol 10

    Quote Originally Posted by logics View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum