Full question: Suppose that $\models \phi \supset \psi$, and that $\phi$ is not a contradiction nor $\psi$ a tautology. Show that there is a propositional variable variable $p$ that occurs in both $\phi$ and $\psi$.
My initial thought was just to chase definitions around, but after doing so I'm not seeing where to assert that there is a propositional variable. What should I appeal to? Recursion theorem?
Just a small push, please.
By contradiction: Suppose $\phi$ and $\psi$ have no variable in common, but still $\models \phi \supset \psi$. Let $V_{\phi}, V_{\psi}$ be the variables of $\phi$, $\psi$ respectively.
Because $\phi$ is not a contradiction, there is some assignment of truth values $val_{\phi}\colon V_{\phi} \to \{0,1\}$ to the variables of $\phi$ such that the value $\phi^{val_{\phi}}$ of $\phi$ under $val_{\phi}$ is 1.
Similarly, because $\psi$ is not a tautology, there is some assignment of truth values $val_{\psi}\colon V_{\psi} \to \{0,1\}$ to the variables of $\psi$ such that the value $\psi^{val_{\psi}}$ of $\psi$ under $val_{\psi}$ is 0.
Since $V_{\phi}$ and $V_{\psi}$ are disjoint, the valuations $val_{\phi}$ and $val_{\psi}$ can be extended to a common valuation $$val_{(\phi \supset \psi)} \colon V_{(\phi \supset \psi)} \to \{0,1\} $$ where $V_{(\phi \supset \psi)} = V_{\phi} \cup V_{\psi}$ is the set of variables of $(\phi \supset \psi)$, and where $$ val_{(\phi \supset \psi)} \restriction V_{\phi} = val_{\phi} \\ val_{(\phi \supset \psi)} \restriction V_{\psi} = val_{\psi} $$
So the value of $\phi \supset \psi$ under the valuation $val_{(\phi \supset \psi)}$ is $0$. But supposedly $\models \phi \supset \psi$, so the value of $\phi \supset \psi$ under any valuation is 1. Contradiction.
