MTH 355
Homework 4
Assigned 12 Nov, due 3 Dec

  1. Exercise 2.5.3: prove that if predicate symbol P doesn't appear in the premises or conclusion of a proof, it can't have been necessary for the proof.

  2. Exercise 2.5.6. (I can't say this any shorter than Enderton did)

  3. Exercise 2.5.8: Start with the integers with an adjacency predicate. Prove that there's a structure elementarily equivalent to it, but not connected.

  4. Exercise 2.6.1: prove that certain sentences are finitely valid.

  5. Exercise 2.6.4: prove that any two countable dense linear orderings are isomorphic.

  6. Exercise 2.6.7: Start with the natural numbers with the < predicate. Prove that there's a structure elementarily equivalent to it, but with infinite descending chains (i.e. there's an infinite sequence of objects, each less than the previous one; this is obviously not true of the naturals).

  7. Exercise 2.6.8: Prove that if a statement is true in all infinite models of a particular theory, then it's also true in all finite models larger than a particular size (i.e. those models are "effectively infinite" as far as this statement is concerned).

  8. Exercise 2.6.9: You're given a set of sentences and the promise that, for each such sentence, either it has a finite model or it has no model at all. Give a decision procedure that tells which ones have models.


Last modified: 
Stephen Bloch / bloch@adelphi.edu