80-310/610 Logic and Computation Fall 2001

Solutions to Homework #13

4. Suppose Mod(T_{1} ∪ T_{2}) = ∅. By compactness, there is a finite subset of T_{1} ∪ T_{2} that has no model. In other words, there is a set {φ_{1}, …, φ_{k}} of sentences in T_{1}, and another set {ψ_{1}, …, ψ_{l}} of sentences in T_{2}, such that {φ_{1}, …, φ_{k}, ψ_{1}, …, ψ_{l}} has no model.

Let σ = φ_{1} ∧…∧φ_{k}. Since each φ_{i} is in T_{1}, it is easy to see that T_{1} ⊧ σ. But any structure that satisfies T_{2} has to satisfy {ψ_{1}, …, ψ_{l}}, so it can’t satisfy all of the φ_{i}’s. So T_{2} ⊧ ¬σ.

5. Suppose T_{1} ≠ T_{2}. Then there is a sentence that is in one but not the other. Without loss of generality, suppose φ is a sentence in T_{1} but not T_{2}. Since T_{2} is a theory, T_{2} ⊬ φ, and so T_{2} ∪ {¬φ} is consistent.

Let A be a model of T_{2} ∪ {¬φ}. Since A ⊧ ¬φ, A is a model of T_{2} but not T_{1}.

8. a. It is easy to verify that the map f(x) = x + 1 is an isomorphism.

b. By Lemma 3.3.3, any two isomorphic structures are elementarily

equivalent. c. Clearly |A| ⊆ |B|, and the ordering is the same on both universes. d. A ⊧ ∃x (x < ¯1), but not B.

10. It is easy to verify that f(x) = 2x is an automorphism of this structure. But 1 × 1 = 1, while

f(1) × f(1) = 2 × 2 = 4 ≠ f(1).

13. Here is the algorithm: on input φ, in parallel look for a proof of φ and a proof of ¬φ from the axioms of T. Since T is complete, you are bound to find one or the other. If it is a proof of φ, answer “yes,” φ ∈ T; otherwise, answer “no,” φ ∉ T.

15. I cancelled this question because we did not cover second-order logic in time. But just FYI, note that being well ordered is naturally a secondorder property, since we can use a second-order variable to range over subsets:

∀S(∃x S(x) → ∃x (S(x) ∧ ∀y (y < x → ¬S(y)))).