1. A translation problem: Give a formula that
defines the set of primes in the structure
(N; 0, S, +, x).
That is, translate "v_1 is prime" into the language of this structure.
Another translation problem: Find a sentence that is
true in (R*; x) (the non-zero reals with
multiplication) and false in (Z; +)
(the integers with addition).
2. A problem about structures:
Exactly what subsets of the real line are definable
in (R; <)?
For a language whose only parameters are the quantifier symbol
and a two-place predicate symbol, how many structures of size
2 are there, up to isomorphism? List them.
3. A deduction problem or a logical implication problem: Page 146, Exercises 7(b) and 7(c).
4. A compactness problem: Assume the language includes equality. Assume that Sigma has arbitrarily large finite models. (That means that for any natural number n, Sigma has a finite model whose universe has at least n members.) Show that Sigma has an infinite model.
5. An enumerability problem: Assume the language is finite. Assume that Sigma is a decidable set of sentences. Further assume that for every sentence tau, either Sigma logically implies tau, or else Sigma logically implies not-tau. Show that the set of sentences logically implied by Sigma is decidable.
Answers
1. Page 91 for the first one.
A sentence that works for the second one is
forall x exists y [y o y o y = x].
2. R and the empty set. There are ten structures of size 2, up to isomorphism.
3. See the solutions to Problem Set VII.
4. See page 147, Theorem 26A.
5. See #4 in the first midterm, or Corollary 25G on page 144.