(a) Consider the set of propositions PROP using only the logical con-nectives → and ¬. Define what it means for a map v: PROP →{0, 1} to be a valuation.

Define what it means for a proposition oto be satisfiable. \text { (b) Show that if }\left\{\alpha, \gamma_{1}\right\} \vDash \chi \text { and }\left\{\beta, \gamma_{2}\right\} \vDash \chi \text { then }\left\{(\alpha \vee \beta), \gamma_{1}, \gamma_{2}\right\} \vDash \chi (c) Suppose that I is a set of propositions. Show that if = varphi then there is a finite subset of i c i that i= varphi (d) Let X be a countably infinite set. (i) Find a set of propositional variables VAR and a bijection f: 2^{\mathrm{VAR}} \rightarrow\left\{(A, B, R) \mid A, B \subseteq X, R \subseteq X^{2}\right\} (ii) Find a set of propositions I so that V(\Gamma)=\{v \mid v(\varphi)=1 \text { for all } \varphi \in \Gamma\} corresponds to P=\{(A, B, R) \mid A, B \subseteq X, R \subseteq((A \cap B) \times(A \cup B)) \cup((A \cup B) \times(A \cap B))\} under the bijection f. You must prove that f(V(T)) = P.