A problem: Exists a proposition $r \in Prop(A \cup B)$ such that $\vDash (p \rightarrow r) \land (r \rightarrow q)$ Let $A,B$ two arbitrary iof propositions. Show that if $p \in Prop(A)$ and $q \in Prop(B)$ are two propositions such that $\vDash p \rightarrow q$ then exists a proposition $r \in Prop(A \cup B)$ such that $\vDash (p \rightarrow r) \land (r \rightarrow q)$.
I have a hint wich says that I should use induction in the numbers of letters wich are in p but not are in q.
My attemp:
Base case:
Since we do not have letters on $p$ wich are not in $q$, we have that $p = q$. As $\vDash p \rightarrow q$ we have that for all model $t: A \cup B \rightarrow \{0,1\}$ it follows that $t(p \rightarrow q) = 1$; then, $t(p)\leq t(q)$. If we consider the same model for:
$$\begin{array}{r c l c r}
            t(R) & = & t[(p \rightarrow r) \land (r \rightarrow q)] & \hspace{1cm} & \left(\text{$R$ definition}\right)\\
                 & = & \min\{t[(\neg p \lor r), t(\neg r \lor q)\} & \hspace{1cm} & \left(\text{$\land$ definition $\rightarrow$abreviation}\right)\\
                 & = & \min\{\max\{(1 - t(p), t(r), 1 - t(r), t(p)\}\} & \hspace{1cm} & \left(\text{$\lor$ definition and $\neg$ definition}\right)\\
\end{array}$$
And then I do not want to do. Can any one help me with the following step.
 A: As stated, your question is trivial: is enough to take $r=p$; you certainly have both $p\rightarrow r$ (tautology) and $r\rightarrow q$ (from the hypothesis), and since $p$ is a formula with variables in $A$, $r$ is clearly a formula with variables in $A\cup B$.
What you probably wanted to prove is Craig's interpolation theorem (of which Wikipedia presents the standard proof), stating that you can find a formula $r$ satisfying $\vDash(p\rightarrow r)\wedge(r\rightarrow q)$ and that lies in $Prop(A\cap B)$: notice it is an intersection instead of an union.
The hint you received leads to what is probably the most standard proof of the theorem. If we denote the set of propositional variables appearing in the formula $p$ by $var(p)$, what you are doing is induction on the cardinality of $var(p)\setminus var(q)$.
Base case: I don't think you can actually prove, from the fact that $|var(p)\setminus var(q)|=0$, that $p=q$, but what you can prove is that by making $r=p$ you are done (since, whenever $var(p)\setminus var(q)=\emptyset$, $var(p)\subseteq var(q)$).
Inductive step: Assume, as induction hypothesis, that the result holds for any formulas $s$ and $t$ such that $|var(s)\setminus var(t)|\leq n$ and $\vDash s\rightarrow t$, and suppose $|var(p)\setminus var(q)|=n+1$. Then, take a propositional variable $x$ in $p$, but not in $q$, and define
$$p'=p[\top/x]\vee p[\bot/x],$$
where $p[\top/x]$ is the formula obtained from $p$ by replacing every occurrence of $x$ by the top element (if you do not want to add a symbol to your language, just make $\top=x\vee \neg x$), and $p[\bot/x]$ is obtained from $p$ by replacing every occurrence of $x$ by $\bot$ (equal to $x\wedge\neg x$, if you want to). Now, we may prove a few properties of $p'$.

*

*$p\vDash p'$: To see this, take any valuation $\nu$ such that $\nu(p)=1$; if $\nu(x)=1$, $\nu(p[\top/x])=1$ (since $\nu(\top)=1$) and so $\nu(p')=1$; if $\nu(x)=0$, $\nu(p[\bot/x])=1$ and again $\nu(p')=1$.


*$|var(p')\setminus var(q)|=n$: Since $p'$ has the same variables as $p$, except for $x$.


*$p'\vDash q$: Take a valuation $\nu$ such that $\nu(p[\top/x])=1$; if you define the valuation such that $\nu^{*}(y)=\nu(y)$, for every propositional variable $y\neq x$, and $\nu^{*}(x)=1$, one sees that $\nu^{*}(p)=\nu(p[\top/x])=1$, and since $p\vDash q$, $\nu^{*}(q)=1$. Given that $x$ is not a variable in $q$, $\nu^{*}(q)=\nu(q)$, meaning $p[\top/x]\vDash q$. Analogously you prove that $p[\bot/x]\vDash q$, and so $p'\vDash q$.
Now, from induction hypothesis, there exists $t$ such that $p'\vDash t$, $t\vDash q$ and $var(t)\subseteq var(p')\cap var(q)$; but since $p\vDash p'$ and $var(p')\subseteq var(p)$, you get that $p\vDash t$, $t\vDash q$ and $var(t)\subseteq var(p)\cap var(q)$, what ends the proof!
