Results 1 to 2 of 2

Math Help - 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 A be a structure and let s:V \rightarrow |A|. Define a truth assignment v on the set of prime formulas by v(\alpha)=T iff \models_A \alpha[s]. Show that for any formula (prime or not), \bar{v}(\alpha) = T iff \models_A \alpha[s].

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

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

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

    For (b), if \bar{v}(\psi) = T for every  \psi \in \Gamma, then \bar{v}(\phi)=T by assumption. Then I need to show if \models_A \psi[s], then \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,535
    Thanks
    778

    Re: Fol 4

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

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

    Quote Originally Posted by logics View Post
    For (b), if \bar{v}(\psi) = T for every  \psi \in \Gamma, then \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 \models_A \psi[s], then \models_A \phi[s].
    Suppose \models_A\psi[s] for every \psi in \Gamma. Let v_{A,s} be the truth assignment constructed from A and s as described in (a). Then \bar{v}_{A,s}(\psi)=T by (a), so by putting v=v_{A,s} in (*) we have \bar{v}_{A,s}(\phi)=T, which again by (a) implies \models_A\phi[s].
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum