80-310/610 Logic and Computation Fall 2001

Solutions to Homework #10

6. Each line below combines a number of steps. In the first step I rename all variables that are “different,” and use the fact that for arbitrary formulas η and θ, ¬(η → θ) is equivalent to η ∧ ¬θ. In the last step, there is flexibility in the order in which you bring quantifiers to the front.

¬(∃x φ(x, y) ∧ (∀y ψ(y) → φ(x, x)) → ∃x ∀y σ(x, y))

≡ ∃z φ(z, y) ∧ (∀w ψ(w) → φ(x, x)) ∧ ¬∃u ∀v σ(u, v)
≡ ∃z φ(z, y) ∧ (∃w ¬ψ(w) ∨ φ(x, x)) ∧ ∀u ∃v ¬σ(u, v)
≡ ∃z φ(z, y) ∧ ∃w (¬ψ(w) ∨ φ(x, x)) ∧ ∀u ∃v ¬σ(u, v)
≡ ∃z, w ∀u ∃v (φ(z, y) ∧ (¬ψ(w) ∨ φ(x, x)) ∧ ¬σ(u, v)).

7. Let M be any structure. I need to show that

M ⊧ ∃x (φ(x) → ∀y φ(y)).

Applying Lemma 2.4.5, this amounts to showing that there is an element a in the universe of M such that either M ⊧ ¬φ(ā) or M ⊧ ∀y φ(y).

If M ⊧ ∀y φ(y), then we are done; any element a of the universe of M will do. (Remember, we are assuming that our structures have nonempty universes.) Otherwise, M |̸= ∀y φ(y), which is to say, it is not the case that for every b in |M|, M ⊧ φ(b̄). In other words, for some b in |M|, M ⊧ ¬φ(b̄). In that case, we can take a = b, and again we’re done.

Alternatively, you can use the transformations in Section 2.5 to show that the following are all equivalent:

∃x (φ(x) → ∀y φ(y))
∃x (¬φ(x) ∨ ∀y φ(y))
∃x ¬φ(x) ∨ ∀y φ(y)
¬∀x φ(x) ∨ ∀y φ(y)
¬∀x φ(x) ∨ ∀x φ(x)

Clearly the last formula is valid.

11. a. ∀x (Cow(x) → EatsGrass(x))

b. ∃x (Car(x) ∧ Blue(x) ∧ Old(x))

c. ¬∃x (Car(x) ∧ ¬Pink(x))

d. ∀x (Car(x) ∧ Old(x) → MustBeInspectedAnnually(x))

14. To separate 𝔄_{1} and 𝔄_{2}, let σ say that there is a smallest element:

∃x ∀y (x ≤ y).

To separate 𝔄_{2} and 𝔅, let σ say that between any two elements, there is another element:

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

where x < y abbreviates x ≤ y ∧ ¬(x = y).

15. σ “says” that there is something that is comparable with every element. Let 𝔄 and 𝔅 be the posets below:

In other words, 𝔅 is the poset with two incomparable elements, and 𝔄 is the poset with two elements, one of which is less than the other. Then 𝔄 ⊧ σ and 𝔅 ⊧ ¬σ. (For 𝔄, the 1-element poset would also work.)

19. a. P rime(x) ≡ x ≠ 0 ∧ x ≠ S(0) ∧ ∀y, z (x = y × z → y = x ∨ z = x)

b. OddSquare(x) ≡ ∃y (x = y × y) ∧ ∃z (x = (z + z) + 1)

c. T hreeP rimeF actors(x) ≡ ∃u, v, y, z (x = u × v × y × z ∧ P rime(u) ∧ P rime(v) ∧ P rime(y) ∧ u ≠ v ∧ u ≠ y ∧ v ≠ y)

Once again, there are many reasonable variations of these.