Results 1 to 2 of 2

Thread: Fol 4

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    Fol 4

    This is another exercise problem (Exercise 3 of Section 2.4) of Enderton's "A mathematical introduction to logic".

    (a) Let $\displaystyle A$ be a structure and let $\displaystyle s:V \rightarrow |A|$. Define a truth assignment $\displaystyle v$ on the set of prime formulas by $\displaystyle v(\alpha)=T$ iff $\displaystyle \models_A \alpha[s]$. Show that for any formula (prime or not), $\displaystyle \bar{v}(\alpha) = T$ iff $\displaystyle \models_A \alpha[s]$.

    (b) Conclude that if $\displaystyle \Gamma$ tautologically implies $\displaystyle \phi$, then $\displaystyle \Gamma$ logically implies $\displaystyle \phi$.

    ==============================
    What I have tried so far is

    For (a), if $\displaystyle \alpha$ is a prime formula, nothing needs to be done. If $\displaystyle \alpha$ is not a prime formula, two cases have to be considered, i.e., $\displaystyle \alpha = \neg \beta$ or $\displaystyle \alpha = (\beta \rightarrow \gamma)$, where $\displaystyle \beta$ and $\displaystyle \gamma$ are both atomic formulas.

    For (b), if $\displaystyle \bar{v}(\psi) = T$ for every $\displaystyle \psi \in \Gamma$, then $\displaystyle \bar{v}(\phi)=T$ by assumption. Then I need to show if $\displaystyle \models_A \psi[s]$, then $\displaystyle \models_A \phi[s]$. I am stuck here.

    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 4

    Quote Originally Posted by logics View Post
    (a) Let $\displaystyle A$ be a structure and let $\displaystyle s:V \rightarrow |A|$. Define a truth assignment $\displaystyle v$ on the set of prime formulas by $\displaystyle v(\alpha)=T$ iff $\displaystyle \models_A \alpha[s]$. Show that for any formula (prime or not), $\displaystyle \bar{v}(\alpha) = T$ iff $\displaystyle \models_A \alpha[s]$.
    It seems that only quantifier-free formulas are considered here.

    Quote Originally Posted by logics View Post
    For (a), if $\displaystyle \alpha$ is a prime formula, nothing needs to be done. If $\displaystyle \alpha$ is not a prime formula, two cases have to be considered, i.e., $\displaystyle \alpha = \neg \beta$ or $\displaystyle \alpha = (\beta \rightarrow \gamma)$, where $\displaystyle \beta$ and $\displaystyle \gamma$ are both atomic formulas.
    You cannot assume that $\displaystyle \beta$ and $\displaystyle \gamma$ are atomic formulas (does it mean the same as prime formulas?) in the induction step. E.g., $\displaystyle (\alpha\to \alpha)\to \alpha$ where $\displaystyle \alpha$ is a prime formula has the form $\displaystyle \beta\to\gamma$, but $\displaystyle \beta$ is not prime. I assume you can finish the definition and the proof that $\displaystyle \bar{v}(\alpha) = T$ iff $\displaystyle \models_A \alpha[s]$.

    Quote Originally Posted by logics View Post
    For (b), if $\displaystyle \bar{v}(\psi) = T$ for every $\displaystyle \psi \in \Gamma$, then $\displaystyle \bar{v}(\phi)=T$ by assumption.
    I believe this holds for any truth assignment v. Call this fact (*).

    Quote Originally Posted by logics View Post
    Then I need to show if $\displaystyle \models_A \psi[s]$, then $\displaystyle \models_A \phi[s]$.
    Suppose $\displaystyle \models_A\psi[s]$ for every $\displaystyle \psi$ in $\displaystyle \Gamma$. Let $\displaystyle v_{A,s}$ be the truth assignment constructed from $\displaystyle A$ and $\displaystyle s$ as described in (a). Then $\displaystyle \bar{v}_{A,s}(\psi)=T$ by (a), so by putting $\displaystyle v=v_{A,s}$ in (*) we have $\displaystyle \bar{v}_{A,s}(\phi)=T$, which again by (a) implies $\displaystyle \models_A\phi[s]$.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum