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.