Proving a Theorem (Predicate Logic)

Prove the case for the following theorem when C has the form :

"Let A and B be predicate forms with , 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 ."

__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 , , etc. But I'm only required to prove the case case F-->G (F implies G).

So, has the form . Then is , where either or is obtained from by replacing one or more instances of A with B. Similarly or is obtained from 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:

But that requires us to show that we have . How do we show that? Any help and suggestion is really appreciated.

Re: Proving a Theorem (Predicate Logic)

Re: Proving a Theorem (Predicate Logic)

Quote:

Originally Posted by

**emakarov** I don't see why this is required. By induction hypothesis, for every

and

we have

iff

, and also

iff

. Thus, for any

and

,

iff

iff

(

implies

) iff

(

implies

) iff

iff

.

I see. Yes, either way, by inductive hypothesis we have and . But thank you for confirming, I appreciate that.