502 – Predicate logic

These exercises (due September 28) are mostly meant to test your understanding of compactness.

  1. Let M be a nonstandard model of {\rm Th}({\mathbb N},+,\times,0,1,<). Show:
    1. (Overspill) Suppose that A\subset M is definable (with parameters) and that A\subseteq{\mathbb N}. Show that A is finite.
    2. (Underspill) Suppose that A\subset M is definable and that A\cap {\mathbb N}=\emptyset. Show that there is some infinite c such that all the elements of A are larger than c.
  2. Let M be a nonstandard model of {\rm Th}({\mathbb R},{\mathbb N},+,\times,<,\dots). Here, {\mathbb N} is treated as a relation, and in \dots 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 ({}^*{\mathbb R},{}^*{\mathbb N},{}^*+,{}^*\times,{}^*<,\dots) for M. The convention is that we identify actual reals in {\mathbb R} with their copies in {}^*{\mathbb R}, so we write \pi rather than {}^*\pi, etc.
    1. Show that ({}^*{\mathbb N},{}^*+\upharpoonright {}^*{\mathbb N}\times {}^*{\mathbb N},{}^*\times\upharpoonright {}^*{\mathbb N}\times {}^*{\mathbb N},0,1,{}^*<\upharpoonright {}^*{\mathbb N}\times {}^*{\mathbb N}) is a nonstandard model of the theory of problem 1. (In particular, check that the indicated restrictions of {}^*+ and {}^*\times have range contained in {}^*{\mathbb N}.)
    2. A (nonstandard) real r is finite iff there is some (finite) natural number n such that -n<r<n. Otherwise, it is infinite. A (nonstandard) real r is infinitesimal iff r\ne 0 but for all positive (finite) natural numbers n, one has that -1/n<r<1/n. We write r\approx 0 to mean that either r is infinitesimal, or else it is 0. Show that infinite and infinitesimal numbers exist. The monad of a real r is the set of all s such that r-s\approx 0, which we may also write as r\approx s; and say that r and s are infinitesimally close. Show that the relation \approx 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 s={\rm st}(r) to indicate that the (actual) real s is in the monad of r. We also say that s is the standard part of r.
    3. Show that a function f is continuous at a real a iff {\rm st}({}^*f(a+h))=f(a) for all infinitesimal numbers h.
    4. Suppose that f is continuous on the closed interval {}[0,1]. Argue as follows to show that f attains its maximum: For each positive integer n, there is some integer i with 0\le i\le n such that f(i/n)={\rm max}\{f(j/n)\mid 0\le j\le n\}. Conclude that the same holds if n is some infinite natural number, i.e., there is some (perhaps infinite) “natural number” i with 0\le i\le n such that {}^*f(i/n)={\rm max}\{{}^*f(j/n)\mid 0\le j\le n\}. Let r={\rm st}(i/n), and argue that the maximum of f is attained at r.

9 Responses to 502 – Predicate logic

  1. What was the precise definition of “definable” again. I can’t find it in the book anywhere.

    • Given a language {\mathcal L} and an {\mathcal L}-structure {\mathcal M}=(M,\dots), a set A\subseteq M is definable iff there is a formula \phi with (distinct) free variables x,x_1,\dots,x_k and there are elements a_1,\dots,a_k\in M such that, letting P be the set of assignments p:{\rm Var}\to M such that p(x_i)=a_i for 1\le i\le k, then A=\{m\in M\mid {\mathcal M}\models_p\phi for all p\in P with p(x)=m\}.

      In human: A is definable if it is the set of elements of M that satisfy some formula. We allow said formula to use parameters, i.e., to refer to some fixed elements of M.

  2. Is 0 considered an infinitesimal? By the definition above, 0 would be, but I always thought it was otherwise.

  3. Now my concern is: if 0 is not an infinitesimal, then is \approx reflexive. Namely, if r \approx r then r - r \approx 0. That is, -1/n < r-r < 1/n for all positive n. But r-r = 0. So, r -r cannot be infinitesimal. What am I missing here?

    [Addressed by the revised definition. -A.]

  4. Thank you. It’s clear now.

    Also, how do you get LaTex to work on your blog? I noticed that you got the approximation symbol to show, but when I tried \approx it didn’t work

    • Type ‘latex’ immediately following the dollar sign, leave a space, and then the math text as you’d do in latex usually. See this announcement for more info.

      The wordpress people tweak with the way latex is compiled every now and then, so sometimes strange errors that were not there before appear; but it works pretty decently, and it is getting better. (There seem to be a few silly things still: you want to write {} right before a [ if this is the first symbol in a math display, for example.)

      Luca Trevisan devised a nice program, LaTeX2WP, to make the use of \LaTeX in WordPress pleasant rather than traumatic; I use it whenever I have a long post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: