80-310/610 Logic and Computation Fall 2001

Homework 14

(Entirely optional)

1. This homework assignment is designed to keep you busy for a while after the course is over. Some of the problems are very hard; none are required for the course.

2. ∘ Show that addition is definable in the structure ⟨ℕ, ×, <⟩.

3. ∘ Show that exponentiation (and, in fact, any primitive recursive function) is definable in the structure ⟨ℕ, +, ×⟩.

4. ∘ Use the suggestion in the notes to show that < is not definable in ⟨ℕ, S⟩.

5. ∘ Show that addition is not definable in ⟨N, S, <⟩.

6. ∘ Do problem 10 on page 134.

7. ∘ Do problem 11 on page 134.

8. ∘ Fill in some of the details left out of the notes, and verify that there is a categorical description of the structure ⟨ℕ, 0, S, +, ×, <⟩ in second-order logic. (For this problem and the ones that follow, you can assume that we are using the full second-order semantics.)

9. ∘ Show how to define the class of finite structures such that the cardinality of the universe is a multiple of 5.

10. ∘ Find a second-order formula φ(x, y) in the language of graphs, which defines the relation “there is a path from x, y” in any graph.

11. ∘ (Hard!)

a. Provide a categorical description of ⟨ℝ, 0, 1, +, ×, <⟩

b. ∘ Find a formula φ which is valid in full second-order semantics if and only if the continuum hypothesis is true. (Hint: φ should assert that there exist appropriate functions on relations on the universe, making it isomorphic to the structure in (a), and that every subset of the universe is either countable or has the same cardinality as the entire universe.)

12. ∘ Come up with simple Kripke model to show that each of the following propositional formulas is not intuitionistically valid:

a. (p → q) ∨ (q → p)

b. ¬(p ∧ q) → (¬p ∨ ¬q)

Note that they are classically valid.

13. ∘ (Hard!) A linear order 𝔓 = ⟨P, <⟩ is dense if between any two elements, there is another element. The “theory of dense linear orderings” is T h(K), where K is the class of dense-linear orderings. This theory can be axiomatized by the axioms for linear orderings, together with the axiom

∀x, y (x < y → ∃z (x < z ∧ z < y)).

a. Show that any two countable dense linear orders with no greatest or least element are isomorphic. (Hint: Cantor was the first to prove this, using a “back-and-forth” argument. Build the isomorphism in stages.)

b. Using the Los-Vaught test, show that the theory of dense linear orders with no greatest or least element is complete, and hence decidable.

c. Show that there are exactly four complete theories containing the theory of dense linear orderings, and that each one of these is decidable.

d. Show that the theory of dense linear orderings is decidable.

e. Show that the theory of dense linear orderings is not categorical in the cardinality of ℝ.