Results 1 to 3 of 3

Math Help - Proving a Theorem (Predicate Logic)

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    224

    Proving a Theorem (Predicate Logic)

    Prove the case for the following theorem when C has the form F \to G:
    "Let A and B be predicate forms with A \iff B, and let C be a predicate form which contains (one or more instances of) A. Let D be a predicate form obtained from C by replacing some instances of A with B. Then C \iff D."

    Attempt:

    We apply induction on the complexity of C.

    Base: the simplest case, C is C=A. In this case we have D=B so C \iff D by hypothesis. So, for the insuctive case we can consider different cases like \neg F, (F \wedge G), etc. But I'm only required to prove the case case F-->G (F implies G).

    So, C has the form (F \to G). Then D is (F \to G), where either  F=F or F is obtained from F by replacing one or more instances of A with B. Similarly G=G or G is obtained from G by replacing one or more instances of A with B. I think we need to show for any interpretation I and any I-assignment v, something like this holds:

    I \models_v C \iff (I \models_v F \to I \models_v G)
    \iff ((I \models_v F) \to (I \models_v G))
    \iff I \models_v D

    But that requires us to show that we have (F \iff F) \to (F \iff G). How do we show that? Any help and suggestion is really appreciated.
    Last edited by demode; October 13th 2011 at 12:39 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Proving a Theorem (Predicate Logic)

    Quote Originally Posted by demode View Post
    I \models_v C \iff (I \models_v F \to I \models_v G)
    \iff ((I \models_v F) \to (I \models_v G))
    \iff I \models_v D

    But that requires us to show that we have (F \iff F) \to (F \iff G).
    I don't see why this is required. By induction hypothesis, for every I and v we have I\models_v F iff I\models_v F', and also I\models_v G iff I\models_v G'. Thus, for any I and v,

    I\models_v C iff
    I\models_v (F\to G) iff
    ( I\models_v F implies I\models_v G) iff
    ( I\models_v F' implies I\models_v G') iff
    I\models_v (F'\to G') iff
    I\models_v D.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2009
    Posts
    224

    Re: Proving a Theorem (Predicate Logic)

    Quote Originally Posted by emakarov View Post
    I don't see why this is required. By induction hypothesis, for every I and v we have I\models_v F iff I\models_v F', and also I\models_v G iff I\models_v G'. Thus, for any I and v,

    I\models_v C iff
    I\models_v (F\to G) iff
    ( I\models_v F implies I\models_v G) iff
    ( I\models_v F' implies I\models_v G') iff
    I\models_v (F'\to G') iff
    I\models_v D.
    I see. Yes, either way, by inductive hypothesis we have F \iff F' and G \iff G'. But thank you for confirming, I appreciate that.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 29th 2010, 03:51 PM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 21st 2010, 08:39 PM
  3. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 6th 2010, 06:23 AM
  4. Proving the Validity of an Argument in Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 12th 2009, 02:04 PM
  5. Help with predicate logic
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 10th 2008, 05:05 PM

Search Tags


/mathhelpforum @mathhelpforum