The ground rules: closed book; no calculators; paper is provided. The format will be similar to the first test. A list of the logical axioms will be provided.
I will hold a "last chance" office hour on Thursday, March 3, 5:30-6:30pm. (This is in addition to the usual office hours, and in addition to the "virtual office hours" website.)
A Practice Test
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.
Click here for answers.
Click here for information on Math 197.