80-310/610 Logic and Computation Fall 2001

Homework #10

Due Wednesday, November 7

1. Finish reading Chapter 2 in van Dalen.

2. Do problems 1, 2, and 3 on page 80.

3. Do problems 4 and 6 on page 80. (In each case, show that for some formula φ in a language of your choosing, the equivalence shown is not valid.)

4. Do problem 5 on page 80. Note that this relies on the convention that we do not consider structures with empty universes.

5. Do problem 12 on page 81. You can use any of the lemmas and theorems in section 2.5 to make your argument as clear as possible. Note that the barber paradox reads as follows: “In a certain town the barber shaves all and exactly those people who do not shave themselves. Who shaves the barber?”

6. ⋆ Do problem 14c on page 81, assuming φ, ψ, and σ are quantifier-free.

7. ⋆ Do problem 15 on page 81.

8. In the language of arithmetic, with constant symbols 0 and 1, functions symbols + and ×, and a relation symbol <, formalize the following:

a. the statement, “x is prime.”

b. the statement, “There are infinitely many primes.”

c. the principle of induction for a formula φ(x)

d. the least-element principle for a formula φ(x)

9. The language of sets has a single binary relation symbol ∈, where x ∈ y is meant to denote the fact that x is an element of y. In the intended interpretation, everything is a set; that is, every object is a set, whose elements are sets, and so on. In this language, formalize the following statements:

a. x is a subset of (or equal to) y.

b. Two sets are equal if and only if they have the same elements. c. For any set z, there is another set w consisting of all the subsets of

z. (You can use the symbol ⊆ to abbreviate the formula you found in part (a).)

10. In a language with a binary relation symbol <, formalize the following statements:

a. < is transitive.

b. Between any two things there is another thing.

c. There is a smallest thing.

d. There is no largest thing.

11. ⋆ Let A be the structure consisting of “all objects on the planet Earth” with relations IsCow(x), EatsGrass(x), IsCar(x), etc. Give reasonable formalizations of the following sentences:

a. All cows eat grass.

b. There is a car that is blue and old.

c. No car is not pink.

d. All cars that are old must be inspected annually.

12. Consider the language of orderings with a single binary relation symbol ≤. Use x < y as shorthand for x ≤ y ∧ ¬(x = y). An element a in a partial ordering P is minimal if there is no element smaller than it; that is, P ⊧ ∀x ¬(x < ā). An element a is minimum if it is at least as small as every other element; that is, P ⊧ ∀x (ā ≤ x).

a. Describe a partial ordering with a minimal element, but no minimum element. (You can use a diagram.)

b. Show that in a linear ordering, an element is minimum iff it is minimal.

c. Describe a linear ordering with no minimal element.

You can argue informally about what is “true in P,” without having to use Lemma 2.4.5 explicitly; but your argument should be mathematically rigorous.

13. Do problem 2 on page 90.

14. ⋆ Do problem 3 on page 90. Help out the grader by explaining, informally, what your formula is supposed to say.

15. ⋆ Do problem 4 on page 90.

16. Do problem 5 on page 90.

17. Do problem 6 on page 90.

18. Do problem 10 on page 91. This really means, using the language of arithmetic on page 87, define the given relations in the “standard” structure ⟨ℕ, 0, S, +, ×⟩. Note that “x and y are relatively prime” means that they have no common factor other than 1.

19. ⋆ In ⟨ℕ, 0, S, +, ×⟩, define

a. the set of primes (i.e. the unary relation “x is a prime”)

b. the set of odd perfect squares

c. the set of numbers with at least 3 different prime factors

Use the symbol “0” to denote the element 0, the symbol “S” to denote the successor function S, and so on.

20. In the structure ⟨ℕ, <⟩, define

a. 0 (i.e. the unary relation x = 0)

b. 1

c. The relation “y is the successor of x”

21. Do problem 14 on page 91. Note that the second relation amounts to “reordering” the natural numbers, so that all the even numbers come first, and all the odd ones come next. (This problem is not easy! Give it your best shot.)

22. ∘ Try to define the class of structures with finite universes in the language of equality, or explain why this is impossible. Do the same for well orderings in the language with ≤. (In fact, you can add any function or relation symbols you want to these languages.)

23. ∘ If you have some background in abstract algebra, do probems 7, 8, and 9 on page 91.

24. ∘ Do problem 12 on page 91.