Results 1 to 2 of 2

Math Help - Fol 12

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Fol 12

    Enderton 2.2.18

    A universal ( \forall_1) formula is one of the form \forall x_1 \cdots \forall x_n \theta, where \theta is a quantifier free. An existential ( \exists_1) formula is of the dual form \exists x_1 \cdots \exists x_n \theta. Let A be a substructure of B, and let s:V \rightarrow |A|.

    (a) Show that if  \models_A \psi[s] and \psi is existential, then \models_B \psi[s]. And if \models_B \phi[s] and \phi is universal, then \models_A \phi[s].

    (b) Conclude that the sentence  \exists Px is not logically equivalent to any universal sentence, nor \forall x Px to any existential sentence.

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

    (a) Since A is a substructure of B, we have an identity map i from A into B.
    Suppose \models_A \exists x_1 \cdots \exists x_n \theta[s]. Then, there are some d_1, d_1, \ldots, d_n \in |A| such that \models_A \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)]. By homomorphism theorem, we have \models_A \theta[s] iff \models_B\theta[i \circ s]. Therefore, \models_B \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)] for d_1, d_1, \ldots, d_n \in |B| , i.e., \models_B \exists x_1 \cdots \exists x_n \theta[s].

    Now, to prove,
    "If \models_B \phi[s] and \phi is universal, then \models_A \phi[s]".

    For any d_1, d_2, \ldots, d_n \in B, we have
    \models_B \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)] by assumption. If d_1, d_2, \ldots, d_n in |B| are also in |A|, then I may use the similar method to the above. But it does not look O.K to assume d_1, d_2, \ldots, d_n \in |A| as well.

    Any help will be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Fol 12

    Quote Originally Posted by logics View Post
    (a) Since A is a substructure of B, we have an identity map i from A into B.
    Rather, the identity map is a homomorphism.

    Quote Originally Posted by logics View Post
    Suppose \models_A \exists x_1 \cdots \exists x_n \theta[s]. Then, there are some d_1, d_1, \ldots, d_n \in |A| such that \models_A \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)]. By homomorphism theorem, we have \models_A \theta[s] iff \models_B\theta[i \circ s]. Therefore, \models_B \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)] for d_1, d_1, \ldots, d_n \in |B| , i.e., \models_B \exists x_1 \cdots \exists x_n \theta[s].
    This makes sense.

    Quote Originally Posted by logics View Post
    Now, to prove,
    "If \models_B \phi[s] and \phi is universal, then \models_A \phi[s]".

    For any d_1, d_2, \ldots, d_n \in B, we have
    \models_B \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)] by assumption. If d_1, d_2, \ldots, d_n in |B| are also in |A|, then I may use the similar method to the above. But it does not look O.K to assume d_1, d_2, \ldots, d_n \in |A| as well.
    You should start proving this statement as you would any other universal statement. Namely, one proves "for all x, P(x)" by fixing an arbitrary x and showing P(x). Here \models_A \phi[s] is such a universal statement. By this I don't mean that \phi is a string of characters that starts with \forall; rather, I mean that the whole claim \models_A \phi[s], when you unfold some definitions, starts with the words "for all."
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum