80-310/610 Logic and Computation Fall 2001

Homework #12

Due Wednesday, November 28

1. Continue reading sections 3.2 and 3.3 in van Dalen, in conjunction with the class notes.

2. ⋆ Assuming θ(x) and η are any formulas and x is not free in η, prove ∃x θ(x) → η from ∀x (θ(x) → η).

3. ⋆ Suppose φ and ψ(x) are any formulas, and x is not free in φ. Prove

(φ → ∃x ψ(x)) ↔ ∃x (φ → ψ(x))

using the following steps:

a. First prove the ← direction. b. From ∃x ψ(x), prove ∃x (φ → ψ(x)). c. From ¬∃x ψ(x) and φ → ∃x ψ(x), conclude ∃x (φ → ψ(x)). (Hint:

from the hypotheses, show that φ implies anything.) d. Put parts (b) and (c) together with a proof of ∃x ψ(x) ∨ ¬∃x ψ(x)

(you don’t have to write out the latter) to obtain a proof the → direction.

Note that this → direction of this problem, together with problem 11, are used in the proof of van Dalen’s Lemma 3.1.7.

4. Show that any maximally consistent set of sentences is a theory.

5. ⋆ Suppose T is a maximally consistent theory. Prove that φ is in T if and only if ¬φ is not in T.

6. Suppose T is a maximally consistent theory. Prove that φ → ψ is in T if and only if either φ is not in T, or ψ is in T. You may use the previous two problems.

7. ∘ Do problem 1 on page 112.

8. Do problem 2 on page 112.

9. ∘ Do problems 3 and 4 on page 112.

10. Consider the following two statements of the completeness theorem:

Version A: If Γ is any consistent set of sentences, then Γ has a model. Version B: If Γ is any set of sentences, φ is any sentence, and Γ ⊧ φ, then Γ ⊢ φ.

Show directly that these two statements are equivalent, i.e. that each one implies the other. (Hint: to show that B implies A, take φ to be ⊥.)

11. ⋆ Let L_{1}, L_{2}, and L_{3} be languages, with L_{1} ⊇ L_{2} ⊇ L_{3}. (In other words, L_{1} has all the constant, function, and relation symbols of L_{2}, and possibly more; and similarly for L_{2} and L_{3}.) Suppose T_{1}, T_{2}, and T_{3} are theories in the languages L_{1}, L_{2}, and L_{3} respectively. Show that if T_{1} is a conservative extension of T_{2}, and T_{2} is a conservative extension of T_{3}, then T_{1} is a conservative extension of T_{3}. (You can find the definition of “conservative extension” on page 106 in van Dalen, Definition 3.1.5.)

12. Do problems 1 through 5 on page 118–119.

13. ⋆ Let (0, 1) denote the open interval of real numbers between 0 and 1:

(0, 1) = {x ∈ ℝ | 0 < x < 1}.

Let [0, 1] denote the closed interval

[0, 1] = {x ∈ ℝ | 0 ≤ x ≤ 1}.

Let (0, ∞) denote the positive real numbers,

(0, ∞) = {x ∈ ℝ | x > 0}.

a. Show that ⟨(0, 1), <⟩ is isomorphic to ⟨(0, 1), >⟩, by exhibiting a bijective function from (0, 1) to (0, 1) and proving that it is an isomorphism of the two structures. Note that the underlying language has a single binary relation r that is interpreted as < in the first structure and > in the second.

b. Show that ⟨(0, 1), <⟩ is isomorphic to ⟨(0, ∞), <⟩. (Hint: consider

the function f(x) = \frac{x}{1−x}.) c. Show that ⟨(0, 1), <⟩ is not isomorphic to ⟨[0, 1], <⟩. (Hint: use

Lemma 3.3.3 in van Dalen, and find a sentence that is true in one structure but false in the other.)

14. ⋆ Let P = ⟨P, <⟩ be a linear ordering. P is said to be a well-ordering if every nonempty subset of P has a least (minimum) element. Note that ⟨ℕ, <⟩ has this property, so you can think of elements of a well-ordering as “generalized numbers” (a.k.a. “ordinals”). a. Show that the structure B in exercise 14 on page 91 of van Dalen is

a well-ordering.

b. Do problem 6 on page 119. In other words, use the suggestion to show that there is no set of sentences Γ such that the models of Γ are exactly the well-orderings.