Explain carefully what is meant by a deduction in the propositional calculus. State the completeness theorem for the propositional calculus, and deduce the compactness theorem.

Let $P, Q, R$ be three pairwise-disjoint sets of primitive propositions, and suppose given compound propositions $s \in \mathcal{L}(P \cup Q)$ and $t \in \mathcal{L}(Q \cup R)$ such that $(s \vdash t)$ holds. Let $U$ denote the set

$$\{u \in \mathcal{L}(Q) \mid(s \vdash u)\} .$$

If $v: Q \rightarrow 2$ is any valuation making all the propositions in $U$ true, show that the set

$$\{s\} \cup\{q \mid q \in Q, v(q)=1\} \cup\{\neg q \mid q \in Q, v(q)=0\}$$

is consistent. Deduce that $U \cup\{\neg t\}$ is inconsistent, and hence show that there exists $u \in \mathcal{L}(Q)$ such that $(s \vdash u)$ and $(u \vdash t)$ both hold.