# Thread: Proving a Theorem (Predicate Logic)

1. ## 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.

2. ## Re: Proving a Theorem (Predicate Logic)

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

3. ## Re: Proving a Theorem (Predicate Logic)

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.