314 – C+C=[0,2]

April 1, 2014

Recall that the Cantor set C is defined as the intersection \bigcap_n C_n where

C_0=[0,1]

and C_{n+1} is obtained by removing from each closed interval that makes up C_n its open middle third, so

C_1=[0,1/3]\cup[2/3,1],

C_2=[0,1/9]\cup[2/9,1/3]\cup[2/3,7/9]\cup[8/9,1],

etc. Each C_n is the union of 2^n closed intervals, each of length 1/3^n.

Let’s prove that C+C=\{x+y\mid x,y\in C\} is the interval {}[0,2]. (Cf. Abbott, Understanding analysis, Exercise 3.3.6.)

1.

The usual proof consists in showing inductively that C_n+C_n=[0,2] for all n. This is easy: Note first that

\displaystyle C_{n+1}=\frac13 C_n+\left(\frac13C_n+\frac23\right),

where

\displaystyle \frac13C_n=\left\{\frac x3\mid x\in C_n\right\}

and

\displaystyle\frac13 C_n+\frac23=\left\{\frac{x+2}3\mid x\in C_n\right\}.

This equality is verified by induction. Using this, we can use induction again to verify that, indeed, C_n+C_n=[0,2] for all n.

We clearly have that C+C\subseteq \bigcap_n C_n+C_n=[0,2]. To prove the converse, for each z\in[0,2] and each n, pick x_n,y_n\in C_n such that x_n+y_n=z_n. The sequence of x_n is bounded, so it has a convergent subsequence x_{n_k}. The corresponding subsequence y_{n_k} has itself a convergent subsequence y_{n_{k_m}}. One argues that their limit values x,y belong to C, because they belong to each C_n, since these sets are nested and closed. Finally, it follows immediately that x+y=z as well.

2.

A very elegant different argument is obtained by using an alternative characterization of C: Note that each x\in[0,1] can be written in base three as

\displaystyle x=0.x_1x_2x_3\dots=\sum_{n=1}^\infty\frac {x_n}{3^n}

where each x_i is 0, 1, or 2. By induction, one easily verifies that x\in C_n iff it admits such an expansion with x_n\ne1. It follows that x\in C iff it admits an expansion where no x_i is 1.

Given z\in[0,2], we have z/2\in[0,1], so we can write z/2=a+b where the ternary expansion of a has only 0s and 2s (so a\in C), and the expansion of b has only 0s and 1s: If

z/2=0.t_1t_2\dots,

we can set a=0.a_1a_2\dots where a_i=0 unless t_i=2, in which case a_i=2 as well, and similarly b=0.b_1b_2\dots where b_i=0 unless t_i=1, in which case b_i=1 as well.

We then have that z=2(a+b)=(a+2b)+a, and both a+2b and a are in C.

This construction has the further advantage of making clear that the typical z admits continuum many (=|\mathbb R|) representations as sum of two members of C: If we can split b=c+d (where the expansions of c,d only have 0s and 1s), we can set

z=(a+2c)+(a+2d).

This gives us as many representations as subsets of \{n\in\mathbb N\mid b_n=1\}.

3.

The related problem of describing C\cdot C appears to be much more complicated. See here and here.

Advertisements

314 – Suggested reading

March 19, 2014

This is a (somewhat expanding) list of suggested additional references. Some cover topics discussed in lecture, others add new material that complements what we covered. The level varies: Some are basic, others are more advanced and portions of them may require knowledge beyond this course.

For the group project: Choose one of these articles. Inform me by email, to make sure it has not already been chosen. Feel free to suggest different papers or other topics, I’ll see whether we can use them.

Write (type) a note on the topic discussed in the paper you have chosen, include details of some of the results discussed there. Make sure the proofs you include contain all needed details (typically proofs in articles are more sketchy than what we are aiming for through the course), and that the write up is your own, even if modeled on the arguments in the paper. Include references as usual. Turn this in by Thursday, May 15, at 10:30 am. Feel free to turn it in earlier, of course. I encourage you, as you work through the paper, to share your progress with me during office hours, so I can give you some feedback before your final submission.

Groups:

  • Booker Ahl, Dorthee Berman, and Stephanie Potter: Russ’s translation of Bolzano’s paper.
  • Tim Deidrick, Justin Durflinger, and Ariel Farber: Calkin-Wilf and Malter-Schleicher-Zagier on enumerating the rationals.
  • Carrie Smith, and Jordan Wilson: Fleron’s note on the history of the Cantor set and function.
  • Caleb Richards, and Chris VanDerhoff: McShane’s paper on the Henstock–Kurzweil integral.
  • Kenny Ballou, Sarah Devore, and Luke Warren: Nitecki’s paper on subseries.
  • Farrghun Abdulrahim, and Kenneth Coiteux: Burns and Hasselblatt’s paper on Sharkovsky’s theorem.
  • Tyler Clark: Niven’s paper on formal power series.
  • Joe Magdaleno, and Piper Gutridge: Bruckner and Bruckner-Leonard  on derivatives.

314 – On √n

March 10, 2014

Let’s prove that if n\in\mathbb N, then either \sqrt n is an integer, or else it is irrational. (Cf. Abbott, Understanding analysis, Exercise 1.2.1.) There are many proofs of this fact. I present three.

1.

The standard proof of this fact uses the prime factorization of n: There is a unique way of writing n as \prod_{i=1}^k p_i^{\alpha_i}, where the p_i are distinct primes numbers, and the \alpha_i are positive integers (the number n=1 corresponds to the empty product, but since 1 is a square, we may as well assume in what follows that n>1).

We show that if \sqrt{n} is rational, then in fact each \alpha_i is even, so \sqrt n is actually an integer. Write \sqrt n=a/b where a,b are integers that we may assume relatively prime. This gives us that b^2n=a.

Consider any of the primes p=p_i in the factorization of n. Let p^\beta and p^\gamma be the largest powers of p that divide a and b, respectively, say a=p^\beta c and b=p^\gamma d where p does not divide either of c and d. Similarly, write n=p^{\alpha}m, where p does not divide m (\alpha is what we called \alpha_i above). We have

p^{2\gamma} p^{\alpha}d^2m=p^{2\beta}c^2.

The point is that since p is prime, it does not divide c^2 or d^2m: If q is a prime and q divides a  product hj (where h,j are integers), then q divides h or it divides j.

This means that either \alpha is even (as we wanted to show), so that 2\gamma+\alpha=2\beta, or else (upon dividing both sides of the displayed equation by the smaller of p^{2\gamma+\alpha} and p^{2\beta}), p divides one of the two sides of the resulting equation, but not the other, a contradiction.

2.

The above is the standard proof, but there are other arguments that do not rely on prime factorizations. One I particularly like uses Bézout theorem: If c is the greatest common divisor of the positive integers a and b, then there are integers x,y such that ax+by=c.

Suppose \sqrt n=a/b. We may assume that a,b are relatively prime, and therefore there are integers x,y such that ax+by=1. The key observation is that \sqrt n=n/\sqrt n=nb/a. This, coupled with elementary algebra, verifies that

\displaystyle \sqrt n= \frac ab=\frac{nb}a=\frac {ay+nbx}{by+ax},

but the latter is an integer, and we are done.

3.

Another nice way of arguing, again by contradiction, is as follows: Suppose that \sqrt n is not an integer, but it is rational. There is a unique integer m with m<\sqrt n<m+1, so 0<\sqrt n -m<1. Let a be the least positive integer such that (\sqrt n-m)a is an integer, call it b. Note that 0<b<a, which gives us a contradiction if ({\sqrt n}-m)b is again an integer. But this can be verified by a direct computation:

(\sqrt n-m)b=(\sqrt n-m)^2a=(n+m^2)a-2m\sqrt n a =(n-m^2)a-2m(\sqrt n-m)a.

4.

As a closing remark, the three arguments above generalize to show that \root k\of n is either an integer or irrational, for all positive integers n,k. Similarly, if \displaystyle\root k\of {\frac ab} is rational for some positive integers a,b, then both a,b are kth powers. (It is a useful exercise to see precisely how these generalizations go.)

Pdf source.


314 – Foundations of Analysis – Syllabus

January 20, 2014

Math 314: Foundations of Analysis.

Andrés E. Caicedo.
Contact Information: See here.
Time: TTh 12:00 – 1:15 pm.
Place: Mathematics Building, Room 139.
Office Hours: Th, 1:30 – 3:00 pm, or by appointment. (If you need an appointment, email me a few times/dates that may work for you, and I’ll get back to you).

Textbook: Stephen Abbott. Understanding Analysis. Springer-Verlag, Undergraduate Texts in Mathematics, 2001; 257 pp. ISBN-10: 0387950605. ISBN-13: 978-0387950600.

Here is the publisher’s page. Additional information is available from the author’s page. Review (MR1807438 (2001m:26001)) by Robert Gardner Bartle at MathSciNet. Review by Jeffrey Nunemacher at the American Mathematical Monthly, Vol. 118, No. 2 (February 2011), pp. 186-189.

I will mention additional references, and provide handouts of additional material, as needed.

Contents: The department’s course description reads:

The real number system, completeness and compactness, sequences, continuity, foundations of the calculus.

I strongly suggest you read the material ahead of our meetings, and work on it frequently. You may find some of the topics challenging. If so, here is some excellent advice by Faulkner (from an interview at The Paris Review):

FaulknerPersonally, I find the topics we will study beautiful, and I hope you enjoy learning it as much as I did.

Please bookmark this post. I update it frequently with detailed week-to-week descriptions.

Detailed day to day description and homework assignments. All problems are from Abbott’s book unless otherwise explicitly specified:

  • January 21 – 30. Chapter 1. The real numbers. Irrationality. Completeness. Countable and uncountable sets.
  • January 21. Functions. Mathematical induction and the well-ordering principle.
  • January 23. Sets, logic, quantifiers. Completeness.
  • January 28. Completeness. Countable and uncountable sets. I recommend you read Errol Morris‘s essay on Hypassus of Metapontum, the apparent discoverer of the irrationality of \sqrt2.
  • January 30. Comparing infinities. Counting the rationals. I recommend the following two papers on this topic: 1 and 2. Office hours this week will be on Friday, 11:45-1:15.

Homework set 1 (Due February 4). Exercises 1.2.1, 1.2.2, 1.2.7, 1.2.8, 1.2.10; 1.3.21.3.9; 1.4.21.4.7, 1.4.11 1.4.13; 1.5.3, 1.5.4, 1.5.9. See below for the required format.

Solution to 1.2.1.

  • February 4 – 20. Chapter 2. Sequences and series. Limits. Cauchy sequences. Infinite series. Riemann‘s rearrangement theorem.
  • February 4. Rearrangements of infinite series, limits of sequences. Homework 1 is due today.
  • February 6. Limit theorems.
  • February 11. Limit theorems continued. Infinite series.
  • February 13. Monotone convergence. The BolzanoWeierstrass theorem.
  • February 18. The Bolzano-Weierstrass theorem continued. Absolute and conditional convergence. Cauchy sequences.
  • February 20. Riemann’s rearrangement’s theorem, and extensions (see here and here). The interesting paper by Marion Scheepers mentioned on the second of those links can be found here.
  • Additional topics: Products of series. Double series.

Homework set 2 (Due February 25). Exercises 2.2.1, 2.2.2, 2.2.5, 2.2.7, 2.3.2, 2.3.3, 2.3.6, 2.3.7, 2.3.9, 2.3.11, 2.4.2, 2.4.4, 2.4.5, 2.5.3, 2.5.4, 2.6.1, 2.6.3, 2.6.5, 2.7.1, 2.7.4, 2.7.6, 2.7.9, 2.7.11. See below for the required format.

  • February 25 – March 6. Chapter 3. Basic topological notions: Open sets. Closed, compact, and perfect sets. The Cantor set. Connectedness. The Baire category theorem.
  • February 25. The Cantor set. Open and closed sets.
  • February 27. Open and closed sets, continued. Extra credit problem: Find a set of reals such that we can obtain 14 different sets by applying to it (any combination of) the operations of complementation and closure. Kuratowski showed that 14 is the largest number that can be obtained that way, you are welcome to also try to show that. (See here.)
  • March 4. Open covers, compact sets. Perfect sets. Connectedness.
  • March 6. The Baire category theorem.
  • Additional topics: The study of closed sets of reals naturally leads to the Cantor-Bendixson derivative, and the Cantor-Baire stationary principle (See here for Ivar Otto Bendixson). A nice reference is Alekos Kechris‘s book, Classical descriptive set theory. For the Baire category theorem and basic applications, I recommend the beginning of John Oxtoby‘s short book, Measure and category. See also the nice paper Subsum Sets: Intervals, Cantor Sets, and Cantorvals by Zbigniew Nitecki, downloadable at the arXiv.

Homework set 3 (Due March 11). Exercises 3.2.1, 3.2.3, 3.2.7, 3.2.9, 3.2.11, 3.2.12, 3.2.14, 3.3.2, 3.3.43.3.7, 3.3.9, 3.3.10, 3.4.2, 3.4.4, 3.4.5, 3.4.73.4.10, 3.5.43.5.6.

Solution to 3.3.6.

  • March 11 – March 20. Chapter 4. Limits and continuity: “Continuous” limits. Continuity of functions. The interaction of continuity and compactness.  The intermediate value theorem.
  • March 11. The concept of function. Dirichlet‘s and Thomae‘s examples. Definition of limit and basic properties.
  • March 13. Properties of limits (continued). Definition of continuity and basic properties.
  • March 18. Applications of continuity: The intermediate value property. Banach‘s fixed point theorem.
  • March 20.  Continuity and compactness. Uniform continuity. Sets of discontinuity of functions.
  • Additional topics: The history of the concept of function is very interesting. The intermediate value property also has a curious history. Apparently, for a while it was expected that it sufficed to characterize continuity. Bolzano’s original paper is fairly accessible. A particularly interesting continuous function is the Cantor function, also called the devil’s staircase. The topic of fixed points (Exercise 4.5.7) leads to a beautiful theorem of Sharkovski, on the possible periods of continuous functions (See here for Oleksandr Mykolaiovych Sharkovsky).

Homework set 4 (Due April 1st). Exercises 4.2.1, 4.2.4, 4.2.6, 4.2.7, 4.3.1, 4.3.3, 4.3.4, 4.3.6, 4.3.84.3.10, 4.3.12, 4.4.1, 4.4.4, 4.4.6, 4.4.9, 4.4.10, 4.4.13, 4.5.2, 4.5.4, 4.5.7.

  • April 1 – April 10. Chapter 5. Derivatives: What is a derivative? Differentiability and continuity. Darboux theorem. The mean value theorem. Nowhere differentiable functions.
  • April 1. Sets of discontinuity of functions. Definition of derivative, basic properties. Baire class 1 functions.
  • April 3. Darboux theorem (the intermediate value property).
  • April 8. Rolle‘s theorem. The mean value theorem. L’Hôpital’s rule (see here for Guillaume de l’Hôpital).
  • April 10. Continuous nowhere differentiable functions. Weierstrass function. Proper understanding of this topic requires the notion of uniform convergence, that we will discuss in Chapter 6.
  • Supplemental reading: This is a very useful exercise to review the notions of continuity and uniform continuity. For more on the Baire classes of functions, I recommend Kechris’s book on Classical descriptive set theory. The problem of characterizing which functions are derivatives has led to a significant amount of research; these two notes (by Andrew Bruckner, and by Bruckner and J. L. Leonard) discuss some details: 1, 2. On continuous nowhere differentiable functions, the thesis linked to above (by Johan Thim) is a useful resource. Sections 1, 2, 4 of this “quiz” (by Louis A. Talman) complement well the discussion of similar topics in the book. For the history of the mean value theorem, see these slides by Ádám Besenyei.

Homework set 5 (Due April 15). Exercises 5.2.15.2.5, 5.3.2, 5.3.3, 5.3.5, 5.3.7.

  • April 15 – April 24. Chapter six: Sequences and series of functions. Pointwise vs. uniform convergence. Uniform convergence, continuity, and differentiability. Power series, Taylor series, C^\infty vs. real analytic.
  • April 15. Pointwise and uniform convergence of sequences of functions. The uniform limit of a sequence of continuous functions is continuous.
  • April 17. Section 6.3: Let (f_n)_{n=1}^\infty be a sequence of differentiable functions defined on a closed interval, that converges pointwise and such that their derivatives converge uniformly. Then the pointwise limit is indeed uniform, the resulting function is differentiable, and its derivative is the limit of the f_n'.
  • April 22. Series of functions. Weierstrass M-test. Power series.
  • April 24. Power series (continued). Taylor series. Real analytic functions.
  • Supplemental reading: On the topic of analytic vs C^\infty functions, see these two essays by Dave L. Renfro: 1, 2. The result of section 6.3 is false if we ask that the sequence of functions f_n converges uniformly while their derivatives converge pointwise. Darji in fact proved that we can have the limit of the f_n be a differentiable function whose derivative disagrees everywhere with the limit of the derivatives. See here. On Formal power series and applications in combinatorics, I recommend the nice paper by Ivan Niven on this topic. For more on real analytic functions, see the first two chapters of the book A primer of real analytic functions, by Steven Krantz and Harold Parks.

Homework set 6 (Due April 29). Exercises 6.2.1, 6.2.5, 6.2.8, 6.2.13, 6.2.15, 6.2.16, 6.3.1, 6.3.4, 6.4.1, 6.4.36.4.6, 6.5.1, 6.5.2, 6.6.1, 6.6.6.

  • April 29 – May 8. Chapter seven: The Riemann integral. Darboux’s characterization. Basic properties. The fundamental theorem of calculus. Lebesgue‘s criterion.
  • April 29. Darboux’s approach to the Riemann integral in terms of upper and lower sums. Continuous functions are integrable.
  • May 1. Basic properties of the integral, integrable discontinuous functions. A theorem on uniform convergence ensuring that the integral of a limit is the limit of the integrals.
  • May 6. The fundamental theorem of calculus. Sets of measure zero.
  • May 8. Lebesgue’s characterization of Riemann integrable functions.
  • Supplemental reading: For the interesting history of the early development of the Riemann integral, I suggest the first two chapters of Lebesgue’s theory of integration, by Thomas Hawkins.

Homework set 7 (Due May 13 at 10:30). Exercises 7.2.2, 7.2.5, 7.2.6, 7.3.1, 7.3.3, 7.3.6, 7.4.2, 7.4.4, 7.4.6, 7.5.1, 7.5.4, 7.5.10.

Group project due May 15 at 10:30.

A multiple-choice quiz, by Vicky Neale.

 

Grading: Based on homework. There will also be a group project, that will count as much as two homework sets. I expect there will be no exams, but if we see the need, you will be informed reasonably in advance.

There is bi-weekly homework, due Tuesdays at the beginning of lecture; you are welcome to turn in your homework early, but I will not accept homework past Tuesdays at 12:05 pm, or grant extensions. The homework covers some routine and some more challenging exercises related to the topics covered in the past two weeks (roughly, one homework set per chapter). It is a good idea to work daily on the homework problems corresponding to the material covered that day.

You are encouraged to work in groups and to ask for help. However, the work you turn in should be written on your own. Give credit as appropriate: Make sure to list all books, websites, and people you collaborated with or consulted while working on the homework. If relevant, indicate what software packages you used, and include any programs you may have written, or additional data.

Your homework must follow the format developed by the mathematics department at Harvey Mudd College. You will find that format at this link. If you do not use this style, unfortunately your homework will be graded as 0. In particular, please make sure that what you turn in is not your scratch work but the final product. Include partial attempts whenever you do not have a full solution.

I may ask you to meet with me to discuss details of sets, and I suggest that before you turn in your work, you make a copy of it, so you can consult it if needed.

I post links to supplementary material on Google+. Circle me and let me know if you are interested, and I’ll add you to my Analysis circle.

Twitter.