502 – First order (or predicate) logic

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 »


598 – Structuring mathematical proofs

September 27, 2009

Here is a link to Uri Leron’s paper Structuring Mathematical Proofs, The American Mathematical Monthly 90 (3), (Mar., 1983), 174-185. Dr. Leron talks here about the non-linear nature of proofs (remember the examples I mentioned from Szemeredi and Shelah) and discusses what he calls the “structural method.” It is worth keeping in mind his ideas as you continue through graduate school, and especially when faced with the tasks of giving a talk or writing up your results (even if you disagree with him). 

The basic idea of the structural method is that proofs should perhaps be presented in levels, each giving at least an outline of a complete argument. As you descend through the levels, you fill in details. It is a fairly natural approach (like dividing a result into a series of lemmas), and it has the advantage that it helps the audience understand where the argument is going and have a better global picture of what is going on. It is also harder than one would think, in actual practice, to organize one’s arguments according to this method and, even if just for practice, I find it useful every now and then to see how to present a result, even one whose proof I understand fairly well, following this approach rather than the more standard linear technique.


502 – Completeness

September 25, 2009

 
1. Preliminaries

Just as with propositional logic, one can define a proof system for first order logic. We first need two definitions.

Definition 1 If {\phi} is a formula, a generalization of {\phi} is any formula of the form

 

\displaystyle \forall x_1\forall x_2\dots\forall x_n\,\phi.

 

(We are not requiring in the definition above that the {x_i} are different or that they are present in {\phi.})

Definition 2 Let {t} be a term, let {x} be a variable, and let {\phi} be a formula. We say that {t} is substitutable for {x} in {\phi} iff no free occurrence of {x} in {\phi} is within the scope of a quantifier {\exists z} or {\forall z} with {z} a variable occurring in {t.}

Read the rest of this entry »


175 – Midterm 1

September 25, 2009

Here is the midterm.

1. Hooke’s law says that the force required to stretch a spring a distance of x units from its natural length is given by F(x)=kx, where k is a constant that only depends on the spring.

We are told that for the spring of problem 1 we have F(2)=20, where units of distance are measured in meters, and forces in Newtons. This means that k2=20, or k=10. The work required to stretch the spring 10 m beyond its natural length is then \displaystyle \int_0^{10}10x\,dx=10x^2/2|^{10}_0=500 \,N\cdot m.

2. We are given a curve with equation x=\sqrt{2y-1} and asked to rotate about the y-axis the segment where 1/2\le y\le 2. To find the area of the resulting surface, we can consider splitting the surface into little shells. A typical `thin’ shell, at height y has surface  area 2\pi r\,ds where r is the radius of the shell, in this case just the value of x corresponding to y, i.e., \sqrt{2y-1}. Also, ds is here the arc length element, given by \sqrt{(x')^2+1}\,dy. 

We have: \displaystyle x'=\frac12(2y-1)^{-1/2}2=\frac1{\sqrt{2y-1}}, so \displaystyle (x')^2+1=\frac1{2y-1}+1=\frac{2y}{2y-1}.

Hence the requested area is given by \displaystyle\int_{1/2}^2 2\pi\sqrt{2y-1}\sqrt{\frac{2y}{2y-1}}\,dy=\int_{1/2}^2 2\pi\sqrt{2y}\,dy.

This expression reduces to \displaystyle 2\pi\sqrt2\,\frac23\,y^{3/2}|^2_{1/2}=2\pi\sqrt2\frac23\left(2\sqrt2-\frac1{2\sqrt2}\right)=\frac{14\pi}3.

3. We are given the region bounded by the curve y=\sqrt x and the lines y=2 and x=0. We rotate it about the x-axis, and are asked to find the volume of the resulting solid. A first attempt is to use the washer method. A typical thin washer consists of a slice of the solid for a fixed value of x and with thickness dx. Its volume is \pi (r_1^2-r_2^2)\,dx. Here, r_1 is the exterior radius, which in this case is always 2, and r_2 is the interior radius, given by y=\sqrt x. This means the washer contributes \pi(4-x)\,dx of the full volume, and adding all of them together we obtain \int_0^4 \pi(4-x)\,dx. The upper limit of 4 comes from observing that the curves y=2 and y=\sqrt x cross precisely at the point (4,2).

Unfortunately, this integral is not one of the given expressions.

So we attempt a different approach, using now the shell method. Now a typical thin shell is obtained by fixing a height y and rotating about the x-axis the slice of the figure of thickness dy and height y. Its volume is 2\pi r\,l\,dy, where r is the radius of the shell, in this case y; and l is the length of the shell, in this case x. We thus proceed to express x in terms of y: Since y=\sqrt x, then x=y^2. Hence the thin shell contributes 2\pi y\,y^2\,dy=2\pi y^3\,dy of the full volume, and the volume is obtained by adding all these contributions, obtaining \int_0^2 2\pi y^3\,dy. This is expression (c).

4. The length of the curve y=\sqrt{1-x^2} for -1\le x\le 1 is given by the integral \displaystyle \int_{-1}^1\sqrt{1+(y')^2}\,dx. In this case, \displaystyle y'=\frac12\,\frac{-2x}{\sqrt{1-x^2}}=-\frac x{\sqrt{1-x^2}}, so \displaystyle (y')^2=\frac{x^2}{1-x^2}, and \displaystyle 1+(y')^2=\frac1{1-x^2}, so the integral reduces to \displaystyle\int_{-1}^1\frac 1{\sqrt{1-x^2}}\,dx, which is expression (b).

[There is a small problem with this integral, though, because the denominator vanishes at both endpoints. Later, in Chapter 7, we will learn how to handle integrals of this kind. Note that if the question had been to actually find the length, there is an easier method: The curve is half a circumference of radius 1, so the length is \pi.]

5. (a) The differential equation \displaystyle \frac{dy}{dx}=\frac{e^{3x+4y}}{e^{x^2-7y}} can be rewritten as \displaystyle\frac{dy}{dx}=e^{3x-x^2}e^{11 y}, which is clearly separable. (T)

(b) The area swept by r=2f(\theta) for \alpha\le\theta\le\beta, is four times the area swept by r=f(\theta). Intuitively, we are making lengths twice as long, and areas carry two dimensions of length. Think of the area of a square of side 2, for example. Formally, we can check that this is the case: The area swept by the first curve is given by \displaystyle\int_\alpha^\beta\frac12 (2f(\theta))^2\,d\theta=4\int_\alpha^\beta\frac12(f(\theta))^2\,d\theta, while the area swept by the second curve is given by \displaystyle\int_\alpha^\beta\frac12 (f(\theta))^2\,d\theta. (T)

(c) The half life of a given element is 3 days. This means that 50% of the given amount of the element has decayed after 3 days. After 3 more days, another 25% would have decayed. After 3 more days, another 12.5%. After 3 more days, another 6.25%. Since 50+25+12.5+6.25>90, the given statement is clearly true.

A longer way of checking the same is by recalling that the total amount of the element that remains after time t if originally the amount is y_0 is given by y=y_0e^{-kt}, where k is a given constant. Measure t in days. We are told that y(3)=y_0/2, so e^{3k}=2. Then e^{27 k}=(e^{3k})^9=2^9=512, and y(27)=y_0/512<y_0/10. (T)


502 – Compactness

September 25, 2009

First, two exercises to work some with the notion of ultrapower: Check that |\prod_n M_n/{\mathcal U}|=|{\mathbb R}| whenever {\mathcal U} is a nonprincipal ultrafilter on the natural numbers, and

  1. M_n={\mathbb N} for all n, or
  2. \lim_{n\to\infty}|M_n|=\infty.

Our argument for compactness required the existence of nonprincipal ultrafilters. One might wonder whether this is a necessity or just an artifact of the proof. It is actually necessary. To see this, I will in fact show the following result as a corollary of compactness:

Theorem.  If {\mathcal F} is a nonprincipal filter on a set I, then there is a nonprincipal ultrafilter on I that extends {\mathcal F}.

(Of course, this is a consequence of Zorn’s lemma. The point is that all we need is the compactness theorem.)

Proof. Consider the language {\mathcal L}=\{\hat X\mid X\subseteq I\}\cup\{c,\hat\in\}. Here, each \hat X is a constant symbol, c is another constant symbol, and \hat\in is a symbol for a binary relation (which we will interpret below as membership).

In this language, consider the theory \Sigma=\{c\hat\in\hat X\mid X\in {\mathcal F}\}\cup{\rm Th}(I\cup{\mathcal P}(I),\in,X\mid X\subseteq I). A model M of this theory \Sigma would look a lot like I\cup{\mathcal P}(I), except that the natural interpretation of {\mathcal F} in M, namely, \{\hat X^M\mid X\in{\mathcal F}\} is no longer nonprincipal in M, because c^M is a common element of all these sets.

Note that there are indeed models M of \Sigma, thanks to the compactness theorem.

If M\models\Sigma, let {\mathcal U}=\{X\subseteq I\mid M\models c\hat\in \hat X\}, and note that {\mathcal U} is a nonprincipal ultrafilter over I that contains {\mathcal F}. \Box


502 – Tilings

September 22, 2009

Since we covered some material on tilings, I figured you may find interesting the following nice expository paper by Richard Stanley and my friend and colleague Federico Ardila.


175 – Dandelin spheres

September 22, 2009

Here is a link to the Wikipedia page on Dandelin spheres, giving us the “modern” proof of the equivalence between the definition of conic sections as regions of intersection of planes and cones, with the standard definition in terms of distance to foci. The links on the Wikipedia page provide further explanations and nice graphics illustrating the argument.


175 – Quiz 2

September 19, 2009

Here is quiz 2.

Problem 1 is (simplification of part of) exercise 6.6.16 from the book.

To solve the question, use coordinates as in the accompanying figure in the book, so the origin is at ground level, and y increases downwards. The units of y are feet. For a fix y with 0\le y\le 20, the thin slice of water in the tank at depth y and of tickness dy has volume dV=10\times 12\times dy and weighs dF=62.4\times dV=7488\,dy. This is a constant force, so the work required to remove it to ground level is just dW={\rm distance}\times dF, where {\rm distance} is the depth at which the slice is located, i.e., y. Hence, dW=7488 y\,dy. The total work is obtained by adding all these contributions, i.e., W=\int_0^{20} 7488 y\,dy=7488\times 200=1497600 ft-lb.

Problem 2 is exercise 9.2.16 from the book. 

The curve is r^2=-\cos\theta. Since \cos\theta=\cos(-\theta), the graph is symmetric about the x-axis (because whenever (r,\theta) is in the graph, then so is (r,-\theta)).

Since (-r)^2=r^2, the graph is symmetric about the origin (because whenever (r,\theta) is in the graph, then so is (-r,\theta)).

Since the graph is symmetric about both the origin and the x-axis, it is also symmetric about the y-axis.

To sketch the curve, look first at 0\le \theta< \pi/2. Here \cos\theta>0, so r^2<0, which is impossible, so there is nothing to graph here. Consider now what happens when \pi/2\le\theta\le \pi. As \theta increases, -\cos\theta increases, from 0 to 1. So the same occurs with r^2. This means that r increases from 0 to 1, and -r decreases from 0 to -1. The part with r gives us a curve in the second quadrant, and the part with -r gives us its reflection about the origin. This part of the curve is in the fourth quadrant. Their reflections on the x-axis complete the curve, which can be seen here.

Note that \tan(\pi/2) is undefined. This corresponds to the fact that at the origin the tangent to the curve is the y-axis, as can be seen from the graph.


502 – Predicate logic

September 19, 2009

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.

502 – Propositional logic (4)

September 14, 2009

11. Completeness

 

We now want to show that whenever {S\models A,} then also {S\vdash A.} Combined with the soundness Theorem 22, this shows that the notions of provable and true coincide for propositional logic, just as they did for the tree system. The examples above should hint at how flexible and useful this result actually is. This will be even more evident for first order (predicate) logic.

Theorem 26 (Completeness) For any theory {S} and any formula {A,} if {S\models A,} then {S\vdash A.}

 

Read the rest of this entry »