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