Exercise 144. Let R be a binary relation symbol and f a unary function symbol. def 1. Show that the sentence of Vr R(x, f(x)) → Vry R(x, y) is valid.

Do it in two different ways: (a) proof-theoretically, p, using natural deduction, and (b) semantically, = 4. def 2. Show that the sentence Valy R(x,y) → Vr R(x, f(x)) is not valid. Note that is just the converse implication of . Hint: Try a semantic approach, i.e., show. You need to define a structure A so that the left-hand side of "" in is true in A but the right-hand side of "" is false in A. 3. Conclude that Vrly R(x, y) and Vr R(x, f(x)) are not equivalent first-order wff's. Remark: Despite the conclusion in part 3, Proposition 142 asserts Vray R(x, y) and Vr R(x, f(x)) are equisatisfiable, i.e., if there is a model for one, then there is a model for the other, and vice- versa. 42 Review the definition of o[a] in Section B.3.