502 – Ultraproducts of finite sets

October 2, 2009

I want to sketch here the proof that if {(M_n\mid n\in{\mathbb N})} is a sequence of finite nonempty sets, and {\lim_n |M_n|=\infty,} then {\prod_nM_n/{\mathcal U}} has size {|{\mathbb R}|} for any nonprincipal ultrafilter {{\mathcal U}} on {{\mathbb N}.}

The argument I present is due to Frayne, Morel, Scott, Reduced direct products, Fundamenta Mathematica, 51 (1962), 195–228.

The topic of the size of ultraproducts is very delicate and some open questions remain. For ultraproducts of finite structures, this is continued in Keisler, Ultraproducts of finite sets, The Journal of Symbolic Logic, 32 (1967), 47–57, and finally in Shelah, On the cardinality of ultraproduct of finite sets, The Journal of Symbolic Logic, 35 (1) (Mar., 1970), 83–84. Shelah shows that if an ultraproduct of finite sets is infinite, say of size {\kappa,} then {\kappa^{\aleph_0}=\kappa.} His argument is a very nice application of non-standard analysis. The case that interests us is easier.


\displaystyle |\prod_nM_n/{\mathcal U}|\le|\prod_n M_n|\le|{\mathbb N}^{\mathbb N}|=|{\mathbb R}|,

so it suffices to show that {|{\mathbb R}|\le|\prod_nM_n/{\mathcal U}|.}

Read the rest of this entry »


175 – Quiz 3

October 2, 2009

Here is quiz 3.

Problem 1 is Exercise 9.3.16 from the book. Here is a graph showing the cardioid and the circle. The easiest way to compute the required area is by subtracting the area of the circle from that of the cardioid. (Note that the circle is completely contained in the cardioid as, for each { \theta\in[0,\pi/2],} we have that {0<\cos\theta< 1+\cos\theta.} This shows that in the portion of the circle in the first quadrant is within the portion of the cardiod there. The same holds in the fourth quadrant by symmetry. Of course, all of this also follows directly from the graph.)

The area of the cardioid is given by { \displaystyle\int_0^{2\pi}\frac12(1+\cos\theta)^2\,d\theta} and the area of the circle is { \displaystyle\int_0^\pi \frac12(\cos\theta)^2\,d\theta} (note that as { \theta} varies from { 0} to { \pi} the whole circle is traveled once).

By symmetry, { \displaystyle\int_0^{2\pi}\frac12(1+\cos\theta)^2\,d\theta= \int_0^{\pi}(1+\cos\theta)^2\,d\theta,} so the area we want is given by

\displaystyle  \int_0^{\pi}\left((1+\cos\theta)^2-\frac12(\cos\theta)^2\right)\,d\theta \displaystyle =\int_0^\pi\left(\frac{\cos^2\theta}2+2\cos\theta+1\right)\,d\theta.

Recall that { \displaystyle\cos^2\theta=\frac{1+\cos2\theta}2,} so the integral is { \displaystyle\int_0^\pi\left(\frac{1+\cos2\theta}4+2\cos\theta+1\right)\,d\theta.}

Now note from the Cartesian graph of { \cos\theta} that { \displaystyle\int_0^\pi\cos2\theta\,d\theta=\int_0^\pi\cos\theta\,d\theta=0,} so the area we want is just { \displaystyle\int_0^\pi\frac14+1\,d\theta=\frac54\pi.}

Problem 2 is Exercise 9.5.50 from the book. Recall that the standard polar equation of a line not going through the origin is given by

\displaystyle  r = \frac{r_0}{\cos(\theta-\theta_0)},

where { r_0} is the distance from the line to the origin, and { \theta_0} is the angle of the point in the line that realizes this distance, i.e., { (r_0,\theta_0)} are the polar coordinates of the point on the line closest to the origin.

There are at least two ways we can proceed:

1) We can directly find the distance from the line to the origin. To do this, we recall that the line that goes through the origin and is perpendicular to { y=mx+b,} where { m\ne0,} is given by { \displaystyle y=-\frac1m x.} The point in { y=mx+b} closest to the origin is the intersection of these two lines. In the case that interests us, this is the intersection of { y={\sqrt3}x-1} and { \displaystyle y=-\frac1{\sqrt3} x,} so { \displaystyle{\sqrt3} x -1=-\frac1{\sqrt3} x} or { \displaystyle\left({\sqrt3}+\frac1{\sqrt3}\right)x=1,} or { \displaystyle x=\frac{\sqrt3}4,} so { \displaystyle y=-\frac1{\sqrt3} x=-\frac14.} We have found that the point { \displaystyle\left(\frac{\sqrt3}4,-\frac{1}4\right)} is closest in { y=\sqrt3-1} to the origin. Its distance is { r_0=\sqrt{x^2+y^2}=2/4=1/2.} Its angle { \theta_0} is on the fourth quadrant and satisfies { \tan\theta_0=1/\sqrt3,} i.e., { \theta_0=-\pi/6.}

Putting this together, { \displaystyle r=\frac{1/2}{\cos(\theta+\pi/6)}} is the desired equation.

2) The other method we saw in lecture is based in the fact that

\displaystyle  \cos(\theta-\theta_0)=\cos\theta_0\cos\theta+\sin\theta_0\sin\theta,

and consists in first writing the Cartesian equation of the line directly in polar coordinates, and then using the resulting expression to find { r_0} and { \theta_0:} We have { y={\sqrt 3} x-1,} so { r\sin\theta=\sqrt 3 r\cos\theta-1,} or { r(\sqrt 3\cos\theta-\sin\theta)=1.} This gives us

\displaystyle  r=\frac 1{\sqrt3 \cos\theta-\sin\theta}.

We find a constant { k} such that { k\sqrt3} and { -k} are the cosine and the sine of some angle, precisely { \theta_0.} We then have { k\sqrt3\cos\theta-k\sin\theta=\cos\theta_0\cos\theta+\sin\theta_0\sin\theta=\cos(\theta-\theta_0).}

To find this { k,} we use that { \cos^2\alpha+\sin^2\alpha=1} for any { \alpha,} so { k} must satisfy { {k^2}3+k^2=1,} or { k^2=1/4,} so { k=1/2.} The value of { \theta_0} such that { \cos\theta_0={\sqrt3}/2} and { \sin\theta_0=-1/2} is { \theta_0=-\pi/6.} This means that the equation we are looking for is

\displaystyle  r=\frac k{k\sqrt3 \cos\theta-k\sin\theta}=\frac{1/2}{\cos(\theta+\pi/6)},

just as with the previous method.

Typeset using LaTeX2WP.