Results 1 to 2 of 2

Math Help - Fol 13

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Fol 13

    Enderton 2.2.19

    An \exists_2 formula is one of the form \exists x_1 \cdots x_n \theta, where \theta is universal.

    (a) Show that if an \exists_2 sentence in a language not containing function symbols (not even constant symbols) is true in A, then it is true in some finite substructure of |A|.

    (b) Conclude that \forall x \exists y Pxy is not logically equivalent to any \exists_2 sentence.

    ========================
    (a) We have \models_A \theta[s(x_1|d_1)(x_2|d_2)\ldots(x_n|d_n)] for some d_1, d_2, \ldots, d_n \in |A| by assumption. We have to show that there are some finite substructure B of A such that

    \models_B \theta[s(x_1|d_1)(x_2|d_2)\ldots(x_n|d_n)] for the above d_1, d_2, \ldots, d_n \in |B|.

    How do I proceed from here?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

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

    Re: Fol 13

    How about taking a substructure B with |B|=\{d_1,\dots,d_n\} and using problem 2.2.18 from your previous post? If the language had functional symbols, then the substructure generated by a finite number of elements may still have an infinite domain. E.g., the substructure of natural numbers with the successor function that contains 0 still has to contain all natural numbers.

    For (b), consider again natural numbers where Pxy is x<y.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum