80-310/610 Logic and Computation Fall 2001

Homework #13

Due Wednesday, December 5

1. Read Chapter 4 of van Dalen, and as much of Chapter 5 as you can.

2. Note that this is the last homework assignment to be turned in! The final exam is on Friday, December 14, from 1-3 PM. Next week, I will announce extra office hours. On the exam, I will only test you directly on material covered since the midterm. But note that this includes, implicitly, a lot of material from the first half of the course, such as the notion of a maximally consistent set, proof rules for the propositional connectives, etc.

3. Do problems 7–10 on page 119.

4. ⋆ Do problem 13 on page 119. (Note that saying that Mod(T_{1} ∪ T_{2}) = ∅ is equivalent to saying that T_{1} ∪ T_{2} is inconsistent. Use the compactness theorem.)

5. ⋆ Show that if T_{1} and T_{2} are theories, and T_{1} ≠ T_{2}, then Mod(T_{1}) ≠ Mod(T_{2}). In other words, if T_{1} ≠ T_{2}, then there is a structure that is a model of one but not the other. (Hint: show that if T_{1} ≠ T_{2}, there is a sentence φ in one but not the other. Without loss of generality, say φ is in T_{1} but not T_{2}. Using the fact that T_{2} is a theory, show T_{2} ∪ {¬φ} is consistent.)

6. ∘ Do problem 3 on page 133. This is a nice application of compactness.

7. Do problem 5 on page 134.

8. ⋆ Do problem 6 on page 134. Note that A ⊆ B means that A is a substructure of B, and A ≺ B means that A is an elementary substructure of B.

9. What subsets of the real numbers are first-order definable in the structure ⟨ℝ, <⟩?

10. ⋆ Show that multiplication (that is, the relation x×y = z) is not definable in ⟨ℝ, 0, +, <⟩. (Hint: find an automorphism f of this structure, such that for some a and b f(a × b) is not equal to f(a) × f(b).)

11. Show that addition is not definable in the structure ⟨ℕ, ×⟩. (Hint: consider an automorphism that switches two primes.)

12. Explain Skolem’s paradox, and why it isn’t really a paradox.

13. ⋆ Let T be a complete theory with an effective set of axioms (in other words, there is an algorithm which determines if a given string of symbols is an axiom of T). Show that T is decidable (that is, there is an algorithm which determines whether or not a given string of symbols is in T, i.e. provable from the axioms).

14. The “theory of a successor operation” is the theory in the language 0, S axiomatized by the following sentences:

• ∀x (¬S(x) = 0)

• ∀x, y (S(x) = S(y) → x = y)

• For each i, the sentence ∀x ¬S^{i}(x) = x

The last item is a schema; the notation S^{i}(x) means S(S(… S(x))) where S occurs i times.

a. What does a model of this theory look like?

b. Show that this theory is not categorical for countable structures.

c. ∘ Show that this theory is categorical for uncountable structures, and hence, by the Los-Vaught test, complete.

15. ⋆ Let L be the language with a single binary relation <. Show the the class of well-orderings is definable in second-order logic.

16. ∘

a. Let L be the language with no “built-in” function and relation symbols other than equality. Find a formula φ in the language of secondorder logic, such that for every (full) structure 𝔄, 𝔄 ⊧ φ if and only if |𝔄| is infinite. In other words, show that the class of infinite structures is definable by a single formula in second-order logic. (Hint: use the suggestions in the notes to express the assertion that there is an injective map from the universe to a proper subset of itself.)

b. Show that the class of finite structures is definable in second-order logic.

c. Show that compactness does not hold for second-order logic, by exhibiting a set of sentences which is finitely satisfiable, but not satisfiable.