Andreas van Cranenburgh Basic Logic, Predicate Logic homework 2 Exercise 9 We have M = such that: D = {0, 1}, I(R) = {<0, 1>} I(t) = v(y) and v such that: v(x) = 1 v(y) = 0 and phi = ∃y: Rxy Now M |= [t/x]phi is false But M |= phi [v(x/[t]vM)] is true Exercise 10 Claim: M |= [t/x]phi [v] iff M |= phi [v(x/[t]vM)] There are two cases: i) x does not occur freely in phi. Trivial, because x does not occur freely neither the substitution nor the valuation of x affect the truth value of phi. ii) x does occur freely in phi: base case: phi = Q(t_1, ... x, ..., t_n) assume M |= [t/x]phi [v], then is in I(Q) so M |= phi [v(x/[t]vM)] must also hold, because either t is substituted for x or x receives the value of t. Similarly for the converse. induction step: induction hypothesis: property holds for psi. then the following case occur: a) phi = chi * psi, for an arbitrary logical constant *, for some chi and psi for which the property holds. b) phi = ∃x: psi i) x does not occur free in psi: trivial again. ii) x does occur free in psi: Since the property holds for psi it will also hold for phi, the quantifier binds x after which the substitution and valuation no longer have any effect. c) phi = ∀x: psi: analogous to above. Exercise 11 We have M = such that: D = {0, 1}, I(R) = {<1, 1>} I(t) = v(y) and v such that: v(x) = 1 v(y) = 0 and phi = Rxy Now M |= phi [v] is false But M |= [y/x]phi [v(y/v(x))] is true Exercise 12 Claim: if x_1 till x_n occur freely in phi, then M |= phi iff M |= ∀x_1 .. x_n phi => Suppose M |= phi. Then for all assignments v, phi is valid. Following the semantic definition of the universal quantifier, M |= ∀x_1 .. x_n phi if for each variable x_i, the formula holds after assigning any individual from the domain to x_i. Since phi is valid in all possible assignments, this must hold. Contrapositive: Suppose M |/= phi. Then there is some assignment v such that M |/= phi [v]. So there must be individuals d_1 .. d_n, where v(x_i) = d_i, such that phi is falsified. These individuals form the counterexamples for M |= ∀x_1 .. x_n phi. Exercise 13 Suppose M |= phi [v], then also M |= psi [v], where psi is an alphabetic variant of phi. Following the definition of validity, all steps except for the quantifiers hold trivially. The steps for the quantifiers: a) We have phi and an alphabetic variant psi. Then: M |= ∀x phi [v] iff M |= ∀y psi [v] for some y such that y is free for x and y does not occur freely in phi. Then psi = [y/x] phi, and it can easily be seen that: M |= ∀x phi [v] iff M |= ∀y [y/x] phi [v] b) ∃x phi. Analogous to previous case. Exercise 14 Claim: If we have a derivation of phi from Delta, then phi is valid if all of the formulas in Delta are true. Delta |- phi => Delta |= phi. Base case: Let phi_1 be the sentence derived at this step. At step 1 the following can happen: 1) a premise is introduced: phi_1 is in Delta 2) an assumption is made: phi_1 is in Gamma_1 In both cases phi_1 is in Delta U Gamma_1, so Delta U Gamma_1 |= phi_1 Induction step: Induction hypothesis: claim holds up till n. At step n + 1 the following can happen: a) one of the rules also in natural deduction for propositional logic is applied. Correctness follows from correctness of natural deduction of propositional logic. b) ∀ is eliminated. At some step m we have ∀x phi. At step n+1 we conclude [t/x] phi, for some arbitrary individual t, which is free for x in phi. No new assumptions are made or withdrawn, so Gamma_n+1 = Gamma_n. So by the induction hypothesis we have that Delta U Gamma_n+1 |= ∀x phi. By the semantic definition of the universal quantifier we know that this implies that for any individual assigned to x, phi holds. Thus it also holds for v(x/[t]vM). By proposition 3 we see that this is equivalent to [t/x] phi being the case. c) ∀ is introduced At some step m we have [y/x] phi, at step n+1 we conclude ∀x psi. The variable y is arbitrary, it does not occur in any premise or active assumption. By the induction hypothesis we know that m is valid, so psi is valid for any individual assigned to y. From this it follows that ∀x psi is the case, because this is the semantic definition of ∀. d) ∃ is introduced. We have: m. [t/x]psi n+1. ∃x: psi According to step m there is a term t for which phi holds. Now consider the valuation v(x/[t]vM]). In this case psi will hold (proposition 3). Now take d = [t]vM, and we have satisfied the semantic definition of ∃. e) ∃ is eliminated. We have: m. ∃x: psi n. [a/x]psi -> chi n+1. chi The constant a is arbitrary, it does not occur in any open assumption or conclusion that holds, nor in chi. By the induction hypothesis step m and n are valid. Because m is valid, there is some object in the domain that satisfies psi. Now suppose this object is assigned to the constant a. Then [a/x]psi will hold as well, and thus chi can be concluded by the deduction theorem. Since a does not occur in chi, this conclusion holds regardless of the assignment of a. f) = is introduced At step n+1 a formula of the form t=t is introduced. This is a tautology, so it is valid. g) + is eliminated m. s = t n. [s/x] phi n+1. [t/x] phi From step m it follows that s and t denote the same object. From step n we see that the property expressed by phi holds for s. By the induction hypothesis these steps are valid, so it is easy to see that the property must also hold for t.