80-310/610 Logic and Computation Fall 2001

Solutions to Homework #9

2. a. Free; x = x b. Free; y = y c. Free; z = ¯0 d. Free; ∃x (¯0 + y = x) e. Free; ∃w (w + x = ¯0) f. Not free; ∀w (x + (x + w) = ¯0) g. Not free; ∀w (x + (x + y) = ¯0) ∧ ∃y (x + y = x) h. Free; ∀u (u = v) → ∀z (z = y)

3. a. There are lots of terms that denote 5 in this structure; for example,

S(S(S(S(S(c))))) and (S(S(S(S(S(c))))) + c). b. To denote n, just use the term S(S(S(… S(c)))), with n S’s in all.

More formally, use induction on n; if n = 0, use c; and if t denotes n, S(t) denotes n + 1.

c. If t denotes n, then so do (t + c), ((t + c) + c), (((t + c) + c) + c), and so on.

6. a. To show ∃x (φ(x) ∧ ψ(x)) → (∃x φ(x) ∧ ∃x ψ(x)) is valid, I need to show that it is true in every structure 𝔄. I will use Lemma 2.4.5 repeatedly. Saying that the formula above is true in 𝔄 amounts to saying that if ∃x (φ(x) ∧ ψ(x)) is true in 𝔄 then (∃x φ(x) ∧ ∃x ψ(x)) is true in 𝔄. To show this, suppose ∃x (φ(x) ∧ ψ(x)) is true in 𝔄. By Lemma 2.4.5, this means that there is some a in the universe of 𝔄 such that φ(ā) ∧ ψ(ā) is true in 𝔄. For this value of a, both φ(ā) and ψ(ā) are true in 𝔄. But this means that ∃x φ(x) is true in 𝔄, and ∃x ψ(x) is true in 𝔄, and hence ∃x φ(x) ∧ ∃x ψ(x) is true in 𝔄, which is what I needed to show. Note that saying “θ is true in 𝔄” is synonymous with “𝔄 ⊧ θ”; which phrasing you use is a matter of taste.

b. To show that the other direction is not valid, it’s enough to describe a counterexample. Let L be a language with two constant symbols a and b, and let 𝔄 be a structure in which a and b denote different objects (say, the structure with universe {0, 1}, where a^{𝔄} = 0, b^{𝔄} = 1). Then 𝔄 ⊧ ∃x (x = a) ∧ ∃x (x = b), but 𝔄 |̸= ∃x (x = a ∧ x = b). (There are many other simple counterexamples.)

7. a. This is false. For example, let φ be the formula ∀x ∀y R(x, y). Then φ is true in a structure 𝔄 where the denotation of R holds of everything (for example, take ⟨ℕ, Q⟩ where Q holds of every pair of natural numbers), and φ is false in a structure 𝔅 where there is at least one pair of values for which the denotation of R does not hold (for example, take ⟨ℕ, <^{ℕ}⟩).

b. This is true, by Lemma 2.4.5: for any structure 𝔄, 𝔄 ⊧ ¬φ iff 𝔄 |̸= φ.

c. This is false. For example, let Γ be the empty set, and use part (a).