Let x1,...,xn be variables, a formula, t a term, and t1,...,tn terms. We define t(t1/x1, . . . , tn/xn) to be the expression obtained by replacing occurrences of x1, . . . , xn simultanously by t1, . . . , tn, and similarly let (t1/x1, . . . , tn/xn) be the expression that is obtained by replacing free occurrences of x1, . . . , xn in simultaneously by t1, . . . , tn.

(a) Show that t(t1/x1, . . . , tn/xn) is a term.

(b) Show that for any structure M and any tuple a from M we have

tM(t1/x1, . . . , tn/xn)(a) = tM(b), where b is the tuple that is obtained by replacing the ith component of a by tMi (a)

for each i {1,...,n}.

(c) Show that (t1/x1, . . . , tn/xn) is a formula.

(d) Suppose that ti is free for xi in for each i. Show that for any structure M and any tuple a from M we have that

M |= (t1/x1, . . . , tn/xn)(a) M |= (b), where b is defined as in part (b).