5. (a) Let L be a first-order language with one two-place predicate symbol P. Write an L sentence varphi so that \langle\{a, b\} ;\{(a, a),(b, b)\}\rangle \vDash \varphi and \langle\{a, b\} ;\{(a, a),(b, a)\}\rangle \not \forall \varphi . ) Let varphi be the sentence Jr(f(f(x))) # f(x)). For each of the following sentences, explain if it is satisfiable or not. If it is satisfiable,find a structure which satisfies it, and if not, explain why it is unsatisfiable. \text { (i) } \varphi \wedge(\exists y \forall x f(x)=y) \text { (ii) } \varphi \wedge(\forall x \exists y f(x)=y) \text { (iii) } \varphi \wedge(\exists y \forall x f(y)=x) \text { (iv) } \varphi \wedge(\forall x \exists y f(y)=x) (c) Consider the structure \boldsymbol{X}=\left\langle\mathbb{N} ; f^{\boldsymbol{X}}, 0_{\mathbf{N}}\right\rangle where fX is the function defined by f*(n) = n + 1. (i) Show that \boldsymbol{\Gamma}=\operatorname{Th}(\boldsymbol{X}) \cup\{(\boldsymbol{x} \neq \underbrace{f \cdots f}_{n \text { times }} 0\} is satisfiable. (ii) Give an example of a structure y and a substitution s so that y ET[s].
Fig: 1
Fig: 2
Fig: 3
Fig: 4
Fig: 5
Fig: 6
Fig: 7
Fig: 8
Fig: 9
Fig: 10
Fig: 11
Fig: 12
Fig: 13
Fig: 14
Fig: 15
Fig: 16