80-310/610 Logic and Computation Fall 2001

Solutions to Homework #12

2.

[∃x θ(x)]_{2}  \begin{aligned}[θ(x)]_{1} & {∀x (θ(x) → η) \atop θ(x) → η} \\ & η \end{aligned} 1 η 2 ∃x θ(x) → η

3.

a.

[∃x (φ → ψ(x))]_{3} \begin{matrix}[φ → ψ(x)]_{1} & [φ]_{2} \\ ψ(x) \end{matrix} ; ∃x ψ(x) 1 ∃x ψ(x) 2 φ → ∃x ψ(x) 3 (∃x (φ → ψ(x))) → (φ → ∃x ψ(x))

b.

∃x ψ(x) \begin{matrix}[ψ(x)]_{1} \\ φ → ψ(x) \end{matrix} ; ∃x (φ → ψ(x)) 1 ∃x (φ → ψ(x))

c.

\begin{aligned}¬∃x ψ(x) & \begin{matrix}φ → ∃x ψ(x) & [φ]_{1} \\ ∃x ψ(x) \end{matrix} \\ & ⊥ \end{aligned} ; ψ(x) ; 1 ; φ → ψ(x) ; ∃x (φ → ψ(x))

d. This is just the ∨ elimination rule:

∃x ψ(x) ∨ ¬∃x ψ(x)  {[∃x ψ(x)]_{1} \atop ⋮(b)} ; [∃x (φ → ψ(x))]_{2}  \begin{matrix}[¬∃x ψ(x)]_{1} ; ⋮ & {φ → ∃x ψ(x) \atop ⋮(c)} \\ ∃x (φ → ψ(x)) \end{matrix} 1 ∃x (φ → ψ(x)) 2 (∃x (φ → ψ(x)) → ∃x (φ → ψ(x)))

5. Suppose T is a maximally consistent theory.

For the forwards direction, suppose φ is in T. Since T is consistent, ¬φ is not in T.

For the other direction, suppose ¬φ is not in T. By maxmimality, T ∪ {¬φ} is inconsistent. So there is a proof of ⊥ from T and ¬φ. Using RAA, we get a proof of φ from T. Since T is a theory, φ is in T.

11. Suppose T_{1} is a conservative extension of T_{2}, and T_{2} is a conservative extension of T_{3}. I need to show that T_{1} is a conservative extension of T_{3}. In other words, I need to show that if φ is any sentence in L_{3}, then φ is in T_{1} if and only if it is in T_{3}.

Since T_{1} contains T_{2} and T_{2} contains T_{3}, it is clear that every sentence φ in T_{3} is in T_{1}. For the other direction, suppose φ is some sentence in the language L_{3} that is in T_{1}. Since L_{3} is a smaller language than L_{2}, φ is also a sentence in L_{2}. Since T_{1} is a conservative extension of T_{2}, φ is in T_{2}. And since T_{2} is a conservative extension of T_{3}, then φ is in T_{3}, as required.

13. a. Let f(x) = 1 − x. This is an isomorphism of the two structures, as follows. f is injective: if 1 − x = 1 − y then x = y. f is surjective: Given any z in (0, 1), z = f(1 − z). f is an isomorphism: If a < b then 1 − a > 1 − b.

b. Let f(x) = x/(1 − x). f is injective: if x/(1 − x) = y/(1 − y), then (cross multiplying) we have x − xy = y − xy and so x = y. f is surjective: if z is any positive real number, let x = z/(1 + z). Then x is an element of (0, 1), and it is easy to check that f(x) = z. f is an isomorphism: Assuming x and y are in (0, 1), 1 − x and 1 − y are both positive. So we have x/(1 − x) < y/(1 − y) iff x − xy < y − xy iff x < y.

c. [0, 1] satisfies “there is a smallest element,” ∃x ∀y (x ≤ y), while (0, 1) does not.

14. a. The structure B in the problem mentioned ordered the natural numbers so that all the even numbers come first, followed by the odd numbers:

0, 2, 4, 6, …, 1, 3, 5, 7, 9 …

Let X be any nonempty subset of the universe of B. If X has any even numbers, take the smallest even number in X, under the usual ordering on ℕ; this is the least element of X in the ordering on B. Otherwise, if there are no even numbers in X, there is at least one odd number in X. In that case, the smallest odd number in X, under the usual ordering on ℕ, is the least element of X in the ordering on B.

b. Let Γ be a set of sentences, such that every well-ordering is a model of Γ. Using compactness, I will show that there is a structure that is not a well-ordering, but is also a model of Γ. Add constants c_{0}, c_{1}, c_{2}, … to the language. Let Γ′ be the set of sentences

Γ ∪ {c_{1} < c_{0}, c_{2} < c_{1}, c_{3} < c_{2}, …}.

I claim that every finite subset of Γ′ is consistent. Let Δ be any such finite subset, and notice that for some n, Δ is a subset of

Γ ∪ {c_{1} < c_{0}, c_{2} < c_{1}, c_{3} < c_{2}, …, c_{n} < c_{n−1}}.

In other words, only finitely many of the sentences c_{i+1} < c_{i} can be in Δ. Since ⟨ℕ, <⟩ is a model of Γ, the structure

⟨ℕ, <, n, n − 1, n − 2, …, 3, 2, 1, 0, 0, 0, 0 …⟩

is a model of Δ (that is, the structure that assigns n to c_{0}, n − 1 to c_{1}, and so on). Note that the constants from c_{n+1} don’t appear in Δ, so we can just assign 0 to them. Since every finite subset of Γ′ has a model, Γ′ also has a model A′ (in the language with the new constants). Let A be the reduct of Γ′ to the original language. Then A is a model of Γ, but A has elements a_{0}, a_{1}, a_{2}, … such that a_{1} < a_{0}, a_{2} < a_{1}, and so on. Then the set

{a_{0}, a_{1}, a_{2}, …, }

doesn’t have a least element, so A is not a well-ordering.