Textbook is Ben-Ari's Mathematical Logic for Computer Science. This question is taken directly from the homework that my professor assigned, not from the textbook. Definitions of interpretations and Sub are from the textbook.
I'm just lost at how to tackle this. First of all I don't really understand what the question is saying, especially the A. 2) part with the I'.
My attempt which is probably wrong:
It is useful to consider some simple cases.
Consider for simplicity the case without clause (2), i.e. a formula like :
$\mathcal A := \lnot p_1$
and consider a formula $\mathcal B_1$.
Then :
$\mathcal A' := \lnot \mathcal B_1$.
We have an interpretation $I$ such that $I(p_1)=T$ and consider a new interpretation $I'$ such that $v_{I'}(\mathcal B_1)=T$.
You have to note that $\mathcal B_1$ is a formula built-up with connectives and some propositional letters, in general different from $p_1$; let $\mathcal B_1$ be $(q_1 \land ((\lnot q_2) \lor q_3))$.
$I'$ must be defined on $q_1,q_2,q_3$ and not necessarily on $p_1$; but this does not matter. The fact is that $I'$ "induces" (by the truth-table "calculations") a value for $\mathcal B_1$ and we know that this value is the same that $I$ assign to $p_1$, i.e. (in our example) $v_{I'}(\mathcal B_1)=I(p_1)=T$.
What we want to prove is that :
$v_{I}(\mathcal A)=v_{I'}(\mathcal A')$.
And this holds because we have :
$v_{I}(\mathcal A)=v_{I}(\lnot p_1)=F$
and :
$v_{I'}(\mathcal A')=v_{I'}(\lnot \mathcal B_1)=F$.
The next step is to "test the mechanism" on a slightly more complex formula like $\mathcal A := p_1 \land p_2$, where $\mathcal A' := \mathcal B_1 \land \mathcal B_2$.
Having completed this "warm-up", we have to prove it by induction on the "complexity" of $\mathcal A$, i.e. by induction on the number $n$ of occurrences of connectives in $\mathcal A$, where $\mathcal A$ is a formula built-up with propositional letters $\{ p_1, \ldots, p_k \}$.
The base case for $n=0$ is trivial; we have that $\mathcal A := p_1$ and $\mathcal A' := \mathcal B_1$.
The induction step must be performed for all the connectives of the language : $\lnot, \land, \lor$.
We have that $\mathcal A := \lnot \mathcal A_1$ or $\mathcal A := \mathcal A_1 \land \mathcal A_2$, and so on.
We assume as induction hypotheses that the property holds for the $\mathcal A_i$'s [which, of course, being subformulae of $\mathcal A$, have less occurrences of connectives than $\mathcal A$] and we use the "mechanism" above to conclude that it holds also for $\mathcal A$.
The successive step is to consider also the other propositional letters $q \notin \{ p_1, \ldots, p_k \}$.
