(a) This part of the question is concerned with propositional logic.

Let $P$ be a set of primitive propositions. Let $S \subset L(P)$ be a consistent, deductively closed set such that for every $t \in L(P)$ either $t \in S$ or $\neg t \in S$. Show that $S$ has a model.

(b) This part of the question is concerned with predicate logic.

(i) State Gödel's completeness theorem for first-order logic. Deduce the compactness theorem, which you should state precisely.

(ii) Let $X$ be an infinite set. For each $x \in X$, let $L_{x}$ be a subset of $X$. Suppose that for any finite $Y \subseteq X$ there exists a function $f_{Y}: Y \rightarrow\{1, \ldots, 100\}$ such that for all $x \in Y$ and all $y \in Y \cap L_{x}, f_{Y}(x) \neq f_{Y}(y)$. Show that there exists a function $F: X \rightarrow\{1, \ldots, 100\}$ such that for all $x \in X$ and all $y \in L_{x}, F(x) \neq F(y)$.