Proving a Theorem (Predicate Logic)

**demode** · October 12th 2011, 09:46 PM

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.

**emakarov** · October 13th 2011, 03:37 AM

Originally Posted by demode

$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$ .

**demode** · October 13th 2011, 03:57 AM

Originally Posted by emakarov

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.

Thread: Proving a Theorem (Predicate Logic)

LinkBack

Thread Tools

Display

Proving a Theorem (Predicate Logic)

Re: Proving a Theorem (Predicate Logic)

Re: Proving a Theorem (Predicate Logic)

Similar Math Help Forum Discussions

Predicate Logic

Predicate Logic

Predicate Logic

Proving the Validity of an Argument in Predicate Logic

Help with predicate logic

Search Tags