Explain carefully what is meant by syntactic entailment and semantic entailment in the propositional calculus. State the Completeness Theorem for the propositional calculus, and deduce the Compactness Theorem.

Suppose $P, Q$ and $R$ are pairwise disjoint sets of primitive propositions, and let $\phi \in \mathcal{L}(P \cup Q)$ and $\psi \in \mathcal{L}(Q \cup R)$ be propositional formulae such that $(\phi \Rightarrow \psi)$ is a theorem of the propositional calculus. Consider the set

$$X=\{\chi \in \mathcal{L}(Q) \mid \phi \vdash \chi\}$$

Show that $X \cup\{\neg \psi\}$ is inconsistent, and deduce that there exists $\chi \in \mathcal{L}(Q)$ such that both $(\phi \Rightarrow \chi)$ and $(\chi \Rightarrow \psi)$ are theorems. [Hint: assuming $X \cup\{\neg \psi\}$ is consistent, take a suitable valuation $v$ of $Q \cup R$ and show that

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

is inconsistent. The Deduction Theorem may be assumed without proof.]