Results 1 to 3 of 3

Thread: Proving a Theorem (Predicate Logic)

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    225

    Proving a Theorem (Predicate Logic)

    Prove the case for the following theorem when C has the form $\displaystyle F \to G$:
    "Let A and B be predicate forms with $\displaystyle 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 $\displaystyle 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 $\displaystyle \neg F$, $\displaystyle (F \wedge G)$, etc. But I'm only required to prove the case case F-->G (F implies G).

    So, $\displaystyle C$ has the form $\displaystyle (F \to G)$. Then $\displaystyle D$ is $\displaystyle (F \to G)$, where either$\displaystyle F=F$ or $\displaystyle F$ is obtained from $\displaystyle F$ by replacing one or more instances of A with B. Similarly $\displaystyle G=G$ or $\displaystyle G$ is obtained from $\displaystyle 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:

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

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

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Proving a Theorem (Predicate Logic)

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

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

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

  3. #3
    Member
    Joined
    Dec 2009
    Posts
    225

    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 $\displaystyle I$ and $\displaystyle v$ we have $\displaystyle I\models_v F$ iff $\displaystyle I\models_v F'$, and also $\displaystyle I\models_v G$ iff $\displaystyle I\models_v G'$. Thus, for any $\displaystyle I$ and $\displaystyle v$,

    $\displaystyle I\models_v C$ iff
    $\displaystyle I\models_v (F\to G)$ iff
    ($\displaystyle I\models_v F$ implies $\displaystyle I\models_v G$) iff
    ($\displaystyle I\models_v F'$ implies $\displaystyle I\models_v G'$) iff
    $\displaystyle I\models_v (F'\to G')$ iff
    $\displaystyle I\models_v D$.
    I see. Yes, either way, by inductive hypothesis we have $\displaystyle F \iff F'$ and $\displaystyle 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: Apr 29th 2010, 03:51 PM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 21st 2010, 08:39 PM
  3. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Feb 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: Mar 12th 2009, 02:04 PM
  5. Help with predicate logic
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Dec 10th 2008, 05:05 PM

Search Tags


/mathhelpforum @mathhelpforum