September 28, 2009
These notes cover in some more detail what the textbook discusses in Chapter 5. Some details of my presentation will be different in irrelevant ways from the details in the book. I will be somewhat terse in terms of examples. Let me know if you feel that they are sorely needed, and I’ll amend the notes accordingly.
Predicate logic extends propositional logic in that we now allow the presence of quantifiers, and therefore we also allow the presence of statements that depend on variables. This complicates the definition of semantics, and also introduces additional complications at the syntactic level. On the other hand, this new flexibility allows us to code in straightforward ways many theories actually used in practice. Set theory is but on example of a theory that can be formalized in this context, and we will see others.
Read the rest of this entry »
September 19, 2009
These exercises (due September 28) are mostly meant to test your understanding of compactness.
- Let be a nonstandard model of Show:
- (Overspill) Suppose that is definable (with parameters) and that Show that is finite.
- (Underspill) Suppose that is definable and that Show that there is some infinite such that all the elements of are larger than
- Let be a nonstandard model of Here, is treated as a relation, and in we may have placed whatever functions and relations we may have need to reference in what follows; moreover, we assume that in our language we have a constant symbol for each real number. (Of course, this means that we are lifting the restriction that languages are countable.) To ease notation, let’s write for The convention is that we identify actual reals in with their copies in so we write rather than etc.
- Show that is a nonstandard model of the theory of problem 1. (In particular, check that the indicated restrictions of and have range contained in )
- A (nonstandard) real is finite iff there is some (finite) natural number such that Otherwise, it is infinite. A (nonstandard) real is infinitesimal iff but for all positive (finite) natural numbers one has that We write to mean that either is infinitesimal, or else it is Show that infinite and infinitesimal numbers exist. The monad of a real is the set of all such that which we may also write as and say that and are infinitesimally close. Show that the relation is an equivalence relation. Show that if a monad contains an actual real number, then this number is unique. Show that this is the case precisely if it is the monad of a finite number. In this case, write to indicate that the (actual) real is in the monad of We also say that is the standard part of
- Show that a function is continuous at a real iff for all infinitesimal numbers
- Suppose that is continuous on the closed interval Argue as follows to show that attains its maximum: For each positive integer there is some integer with such that Conclude that the same holds if is some infinite natural number, i.e., there is some (perhaps infinite) “natural number” with such that Let and argue that the maximum of is attained at