Results 1 to 2 of 2

Thread: Fol 12

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Fol 12

    Enderton 2.2.18

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

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

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

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

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

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

    For any $\displaystyle d_1, d_2, \ldots, d_n \in B$, we have
    $\displaystyle \models_B \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)]$ by assumption. If $\displaystyle d_1, d_2, \ldots, d_n$ in $\displaystyle |B|$ are also in $\displaystyle |A|$, then I may use the similar method to the above. But it does not look O.K to assume $\displaystyle 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,577
    Thanks
    790

    Re: Fol 12

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

    Quote Originally Posted by logics View Post
    Suppose $\displaystyle \models_A \exists x_1 \cdots \exists x_n \theta[s]$. Then, there are some $\displaystyle d_1, d_1, \ldots, d_n \in |A| $ such that $\displaystyle \models_A \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)]$. By homomorphism theorem, we have $\displaystyle \models_A \theta[s]$ iff $\displaystyle \models_B\theta[i \circ s]$. Therefore, $\displaystyle \models_B \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)]$ for $\displaystyle d_1, d_1, \ldots, d_n \in |B| $, i.e., $\displaystyle \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 $\displaystyle \models_B \phi[s]$ and $\displaystyle \phi$ is universal, then $\displaystyle \models_A \phi[s]$".

    For any $\displaystyle d_1, d_2, \ldots, d_n \in B$, we have
    $\displaystyle \models_B \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)]$ by assumption. If $\displaystyle d_1, d_2, \ldots, d_n$ in $\displaystyle |B|$ are also in $\displaystyle |A|$, then I may use the similar method to the above. But it does not look O.K to assume $\displaystyle 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 $\displaystyle \models_A \phi[s]$ is such a universal statement. By this I don't mean that $\displaystyle \phi$ is a string of characters that starts with $\displaystyle \forall$; rather, I mean that the whole claim $\displaystyle \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