Existence of particular formula 
Let $A$ and $B$ be propositional formulas such that $A$ has only variables from the sets $\{a_i : i\in\mathbb{N}\}$ and $\{b_j : j\in\mathbb{N}\}$ and $B$ only has variables from the sets $\{b_j : j\in\mathbb{N}\}$ and $\{c_k : k \in\mathbb{N}\}.$ If $\{A\} \vDash B$ (i.e. for any truth valuation $t$ so that $A^t = 1, B^t = 1$), show that there is a formula $C$ that has only variables from $\{b_j : j \in\mathbb{N}\}$ so that $\{A\} \vDash C$ and $\{C\}\vDash B.$

I suppose I might be able to show this by contradiction. That is, if we assume that for all formulas $C$ with only variables from $\{b_j : j\in\mathbb{N}\},$ either $\{A\}\not\vDash C$ or $\{C\}\not\vDash B.$ However, it seems difficult to arrive at a contradiction from this alone; it might be easier to construct the formula $C,$ but I don't know how to do this with arbitrary formulas. This statement seems true in general; trying it for $A = b_1$ and $B = b_1\vee c_1$, we see that $C = b_1$ works. And trying it for $A = b_1\to (a_1\vee b_1)$ and $B = b_1\to (b_1\vee c_1),$ we see that $C = b_1\to b_1$ works.
 A: Hint: Proceed by structural induction on $B$.
As the base case:

*

*If $\{ A \} \models b_i$, then taking $C = b_i$ works.

*Note $\{ A \} \not \models c_i$, for each $c_i$, so we can proceed vacuously.

As a sample induction step:
Let $B = \varphi \land \psi$.
$$
\begin{align*} 
\{ A \} \models B 
&\Longrightarrow \{ A \} \models \varphi \land \psi \\
&\Longrightarrow \{ A \} \models \varphi \text{ and } \{ A \} \models \psi\\
&\overset{\text{IH}}{\Longrightarrow} \{ A \} \models C_\varphi \text{ and } \{ C_\varphi \} \models \varphi \text{ and } \{ A \} \models C_\psi \text{ and } \{ C_\psi \} \models \psi\\
&\Longrightarrow \{ A \} \models C_\varphi \land C_\psi \text{ and } \{ C_\varphi \land C_\psi \} \models \varphi \land \psi\\
&\Longrightarrow \{ A \} \models C_\varphi \land C_\psi \text{ and } \{ C_\varphi \land C_\psi \} \models B
\end{align*}
$$
Here we used the inductive hypothesis at the marked implication. Notice $C_\varphi \land C_\psi$ uses only variables coming from $\{b_i\}$, since (by induction), each of $C_\varphi$ and $C_\psi$ do.
Do you see how to finish the proof from here?

I hope this helps ^_^
