80-310/610 Logic and Computation Fall 2001

Homework #9

Due Wednesday, October 31

1. Read through section 2.6 in van Dalen.

2. ⋆ (Repeated from last assignment.) Do problem 4 on page 68. In each case, just indicate whether the term is “free” or “not free” for the specified variable in the specified term, and carry out the substitution either way.

3. ⋆ Do problem 1 on page 72. Use the symbols P, T, S, and c to denote addition, multiplication, successor (“+1”), and 0 respectively.

4. Do problems 2 and 3 on page 72.

5. ∘ Prove unique readability for terms and formulas in a given first-order language (and/or write a parser).

6. ⋆ Consider the equivalence

∃x (φ(x) ∧ ψ(x)) ↔ (∃x φ(x) ∧ ∃x ψ(x)).

a. Show that one direction of this equivalence is valid (i.e. true in every structure). Prove this carefully; you can use Lemma 2.4.5.

b. Find examples of φ and ψ where the other direction is not valid (and justify this claim).

7. ⋆ Fix a language, L, which has one binary relation symbol, R. Which of the following statements are true and which are false? Justify your answers.

a. If φ is any sentence, either ⊧ φ or ⊧ ¬φ.

b. If φ is any sentence and 𝔄 is any structure, either 𝔄 ⊧ φ or 𝔄 ⊧ ¬φ.

c. If φ is any sentence and Γ is any set of sentences, then either Γ ⊧ φ or Γ ⊧ ¬φ.

8. Do problems 6 and 7 on page 72.