Georg Cantor | A kind of library

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):

Personally, 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.2 – 1.3.9; 1.4.2 – 1.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 Bolzano–Weierstrass 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.4 – 3.3.7, 3.3.9, 3.3.10, 3.4.2, 3.4.4, 3.4.5, 3.4.7 – 3.4.10, 3.5.4 – 3.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.8 – 4.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.1 – 5.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.3 – 6.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.

1 Comment | 314: Foundations of Analysis | Tagged: Adam Besenyei, Aimeric Malter, Alexander S. Kechris, Andrew Michael Bruckner, Augustin Cauchy, Bernard Bolzano, Bernhard Riemann, Brook Taylor, Carl Johannes Thomae, Dave L. Renfro, Dierk Schleicher, Don Zaglier, Errol Morris, Georg Cantor, Guillaume de l'Hôpital, Harold R. Parks, Henri Lebesgue, Herbert S. Wilf, Ivan Niven, Ivar Otto Bendixson, Jean Gaston Darboux, Jeffrey Nunemacher, Johan Thim, John C. Oxtoby, John L. Leonard, Karl Theodor Wilhelm Weierstrass, Kazimierz Kuratowski, Louis A. Talman, Marion Scheepers, Michel Rolle, Neil J. Calkin, Oleksandr Mykolaiovych Sharkovsky, Peter Gustav Lejeune Dirichlet, Rene Baire, Robert Gardner Bartle, Stefan Banach, Stephen Abbott, Steven G. Krantz, Thomas Hawkins, Udayan B. Darji, Vicky Neale, William Cuthbert Faulkner, Zbigniew Notecki | Permalink
Posted by andrescaicedo

Analysis – HW 4 – Fractals

October 29, 2013

This set is due Friday, November 15, at the beginning of lecture.

We discuss the Hausdorff metric on the collection of compact subsets of a complete metric space, and fractals obtained by contractions. (But note that not all fractals one may want to study come from this procedure.)

TeX source.

Pdf file.

[Edit, Nov. 12, 2013: Problem 4 has been changed to: Provide an example showing that, in general, if $e\in\mathbb R^n$ and $L$ is compact, then $d_H(\{e\},L)\ne d(e,L)$ . (There are cases where the equality holds, and it may be useful to provide some examples of this as well.)]

Leave a Comment » | 414/514: Analysis I | Tagged: Alexander S. Kechris, Banach fixed-point theorem, David Hilbert, Diana Der-Hovanessian, Felix Hausdorff, Georg Cantor, Helge von Koch, Michael Barnsley, Stefan Banach, Wacław Franciszek Sierpiński | Permalink
Posted by andrescaicedo

Analysis – Counting the rationals

September 18, 2013

It is easy to see that to show that $\mathbb Q$ is countable, it suffices to show the countability of $\mathbb Q^+$ , or even of $\mathbb Q\cap(0,1]$ .

There is a straightforward way of enumerating the latter: First list the fractions with denominator $1$ , then those with denominator $2$ (skipping those already listed), then those with denominator $3$ (again, skipping repetitions), etc. This list begins

$\displaystyle \frac11;\frac12;\frac13,\frac23;\frac14,\frac34;\frac15,\frac25,\frac35,\frac45;\dots$

Cantor’s first proof of the uncountability of the reals (the nested intervals argument) from 1874 proceeds as follows:

Given any (injective) sequence $a_1,a_2,\dots$ of reals, we want to exhibit a real that was not listed. There are two cases: Either there are $i\ne j$ with $a_i<a_j$ , and such that there is no $k$ with $a_k\in(a_i,a_j)$ , in which case we are obviously done, or (more interestingly), whenever $a_i<a_j$ , we can find an $a_k$ strictly in between (the range of the sequence is dense in itself). Assume we are in this situation.

Define two sequences $b_1,b_2,\dots$ and $c_1,c_2,\dots$ as follows:

First, $b_1=a_1$ and $c_1=a_2$ .
For definiteness, suppose that $a_1>a_2$ . The other case is treated similarly. Let $b_2$ be $a_i$ , where $i$ is least such that $a_i\in(c_1,b_1)$ . Then define $c_2$ as $a_j$ , where $j$ is least such that $a_j\in(c_1,b_2)$ .
In general, given $c_n<b_n$ , we define $b_{n+1}$ as $a_k$ , where $k$ is least such that $a_k\in(c_n,b_n)$ , and then define $c_{n+1}$ as $a_m$ , where $m$ is least such that $a_m\in(c_n,b_{n+1})$ . Note that these sequences are well defined, because of our density assumption.

The construction just described ensures that if $I_n=[c_n,b_n]$ , then:

For any $n$ , we have that $a_n\notin I_{n+1}$ , and
The intervals are nested and decreasing: $I_1\supsetneq I_2\supsetneq I_3\dots$

It follows (from the completeness of the reals) that $\bigcap_n I_n\ne\emptyset$ , and (from 1.) that any real in this intersection is not in the range of the sequence $a_1,a_2,\dots$

It turns out that if we carry out Cantor’s construction when the sequence of $a_i$ is the enumeration of the rationals in $(0,1]$ we began with, then $\bigcap_n I_n=\{1/\phi\}$ , where $\phi$ is the golden ratio.

This is proved in the nice note

Mike Krebs, and Thomas Wright. On Cantor’s first uncountability proof, Pick’s theorem, and the irrationality of the golden ratio, Amer. Math. Monthly, 117 (7), (2010), 633–637. MR2681523 (2011e:11127).

II.

There is a very nice enumeration of $\mathbb Q^+$ with combinatorial significance.

The rationals are used to label the nodes of the infinite complete binary tree, and the resulting enumeration simply follows the nodes of the tree, lexicographically.

We begin by putting $1/1$ at the root of the tree. Once a node has been labelled $m/n$ , its left successor is labelled $m/(m+n)$ , and its right successor is latex $(m+n)/n$ .

And that’s all! The list so produced begins

$\displaystyle \frac11;\frac12,\frac21;\frac13,\frac32,\frac23,\frac31;\dots$

The proof that this is indeed a bijective listing of $\mathbb Q^+$ is remarkably simple; one verifies in order the following claims:

The numerator and denominator of any of the assigned fractions are relative prime.
Every positive rational is assigned to some node.
Every positive rational is assigned to some node.

For this, one proceeds by induction. For example, if there is a fraction $m/n$ not in reduced form, and used as a label, pick such a fraction appearing in as small a level as possible, and note that the fraction cannot be $1/1$ . A contradiction is now attained by noting that $\mathrm{gcd}(m,n)=\mathrm{gcd}(m-n,n)=\mathrm{gcd}(m,n-m)$ .

Similarly, if $m/n$ appears in more than one node, then $m\ne n$ , and its immediate predecessor (either $(m-n)/n$ or $m/(n-m)$ , depending on whether $m>n$ or $m<n$ ) must also appear more than once.

Finally, if some fraction is not listed, we can choose its denominator $n$ least among the denominators of all skipped fractions, and then choose its numerator $m$ least among the numerators of all skipped fractions with denominator $n$ . A contradiction follows because $m\ne n$ , and if $m>n$ , then $(m-n)/n$ must also have been skipped, but $m-n<m$ , while if $m<n$ , then $m/(n-m)$ must have been skipped, but $n-m<n$ .

This enumeration is due to Neil Calkin and Herbert Wilf, who also showed that it has the following nice combinatorial properties:

There is a sequence $b(0),b(1),b(2),\dots$ of positive integers such that the $n$ -th fraction in the enumeration is just $\displaystyle \frac{b(n)}{b(n+1)}$ (in reduced form). In particular, the denominator of a fraction is the numerator of its successor in the enumeration. So $b(0)=1$ , $b(1)=1$ , $b(2)=2$ , $b(3)=1$ , $b(4)=3$ , $b(5)=2$ , $b(6)=3$ , etc.
In fact, $b(n)$ is precisely the number of ways of writing $n$ as a sum of powers of $2$ , where each power can be used at most twice. For example, $b(6)=3$ , because we can write $6$ as $2^2+2^1$ , as $2^2+2^0+2^0$ , or as $2^1+2^1+2^0+2^0$ .

This is proved in the nice note

Neil J. Calkin, and Herbert S. Wilf. Recounting the rationals, Amer. Math. Monthly, 107 (4), (2000), 360–363. MR1763062 (2001d:11024).

Some natural questions:

What can we say about the real(s) that comes out when the procedure from Cantor’s proof from section I is applied to this enumeration?
Any infinite path through the binary tree defines a sequence of rationals. What reals appear as limit points of these sequences?

1 Comment | 414/514: Analysis I | Tagged: Georg Cantor, Herbert S. Wilf, Mike Krebs, Neil J. Calkin, Thomas Wright | Permalink
Posted by andrescaicedo

Analysis – Some remarks on continued fractions

September 18, 2013

Most introductory books on number theory have at least one section on the theory of continued fractions. I suggest

William Stein. Elementary number theory: primes, congruences, and secrets. A computational approach. Undergraduate Texts in Mathematics, Springer, New York, 2009. MR2464052 (2009i:11002).

downloadable from his webpage. Chapter 5 is on continued fractions. Of interest to us is the proof that for any integer $a_0$ and any infinite sequence of positive integers $a_1,a_2,\dots$ the corresponding continued fraction $\displaystyle {}[a_0;a_1,a_2,\dots]=a_0+\frac1{a_1+\frac1{a_2+\dots}}$ converges to an irrational number. This gives us an explicit bijection between the space of irrationals $\mathbb R\setminus\mathbb Q$ and Baire space, $\mathbb N^{\mathbb N}$ . The bijection is actually a homeomorphism, so the two spaces are equal, as topological spaces. This was first noted by Baire, in

René Baire. Sur la représentation des fonctions discontinues. Deuxième partie, Acta Math. 32 (1), (1909), 97–176. MR1555048.

For a very nice alternative proof of the homeomorphism that does not involve continued fractions, see Chapter 1 of

Arnold W. Miller. Descriptive set theory and forcing. How to prove theorems about Borel sets the hard way. Lecture Notes in Logic, 4. Springer-Verlag, Berlin, 1995.MR1439251 (98g:03119).

Arnie’s homeomorphism also has the nice feature of being an explicit order preserving bijection between $\mathbb Z^{\mathbb N}$ , ordered lexicographically, and the set of irrationals.

In William’s book, you may also want to look at section 5.4, where a proof is provided of Euler’s theorem from 1737 that the continued fraction of $e$ is given by

$e=[2;1,2,1,1,4,1,1,6,1,1,8,\dots].$

(No such nice pattern is known for $\pi$ .)

A few nice additional results on continued fractions, with references, are given in this blog entry.

A fascinating open problem, due to Zaremba from 1972, is discussed in

Alex Kontorovich. From Apollonius to Zaremba: local-global phenomena in thin orbits. Bull. Amer. Math. Soc. (N.S.), 50 (2), (2013), 187–228. MR3020826.

To state the problem, fix a positive integer $n$ , and consider the set

$\displaystyle N_n=\{m\mid \mbox{ there is an }r\mbox{ such that }1\le r\le m,$ $\displaystyle \mathrm{gcd}(m,r)=1,\mbox{ and if }\frac mr=[a_0;a_1,\dots,a_k],$ $\displaystyle \mbox{ then }a_i\le n\mbox{ for all }i\le k\}.$

For example, $N_1$ consists of all numerators appearing in finite continued fractions consisting solely of ones: ${}[1],[1;1],[1;1,1],[1;1,1,1],\dots$ , that is, $\displaystyle 1,2,\frac32,\frac53,\frac85,\dots$ , so $N_1$ is the set of positive Fibonacci numbers.

Zaremba’s conjecture is that $N_5=\mathbb N^+$ . In fact, much more is expected to be true. For example, Hensley conjectured in 1996 that $N_2$ contains all positive integers, with finitely many exceptions. The best result to date is that $N_{50}$ contains almost all positive integers, in the sense that

$\displaystyle \lim_{n\to\infty}\frac{N_{50}\cap[1,n]}n=1.$

For this, see the announcement,

Jean Bourgain, and Alex Kontorovich. On Zaremba’s conjecture, C. R. Math. Acad. Sci. Paris, 349 (9-10), (2011), 493–495. MR2802911 (2012e:11012),

and the preprint

Jean Bourgain, and Alex Kontorovich. On Zaremba’s conjecture. ArXiv:1107.3776.

(Of immediate interest to us is the fact described in Kontorovich’s survey that for $n\ge2$ , the set of infinite continued fractions

$[1;a_0,a_1,a_2,\dots]$

where $1\le a_i\le n$ for all $i$ is a Cantor set.)

Leave a Comment » | 414/514: Analysis I | Tagged: Alex Kontorovich, Arnold W. Miller, Cantor set, continued fraction, Doug Hensley, Georg Cantor, Jean Bourgain, Leonardo Pisano Bigollo Fibonacci, Leonhard Euler, Rene Baire, Stanislaw Krystyn Zaremba, William Stein | Permalink
Posted by andrescaicedo

515 – Homework 2

February 14, 2012

This set is due Feb. 29 at the beginning of lecture. Let me know if more time is needed or anything like that. Problem 4 was incorrect as stated; I have fixed it now. Thanks to Tara Sheehan for bringing the problem to my attention.

Read the rest of this entry »

Leave a Comment » | 515: Analysis II | Tagged: Alexander S. Kechris, Bernhard Riemann, Georg Cantor | Permalink
Posted by andrescaicedo

187 – List of all presentations

January 10, 2012

For ease, I re-list here all the presentations we had throughout the term. I also include some of them. If you gave a presentation and would like your notes to be included, please email them to me and I’ll add them here.

Jeremy Elison, Wednesday, October 12: Georg Cantor and infinity.
Kevin Byrne, Wednesday, October 26: Alan Turing and Turing machines.
Keith Ward, Monday, November 7: Grigori Perelman and the Poincaré conjecture.
David Miller, Wednesday, November 16: Augustin Cauchy and Cauchy’s dispersion equation.
Taylor Mitchell, Friday, November 18: Lajos Pósa and Hamiltonian circuits.
Sheryl Tremble, Monday, November 28: Pythagoras and the Pythagorean theorem.
Blake Dietz, Wednesday, November 30: $\mbox{\em Paul Erd\H os}$ and the Happy End problem.

Here are Jeremy’s notes on his presentation. Here is the Wikipedia page on Cantor, and a link to Cantor’s Attic, a wiki-style page discussing the different (set theoretic) notions of infinity.

Here are a link to the official page for the Alan Turing year, and the Wikipedia page on Turing. If you have heard of Conway’s Game of Life, you may enjoy the following video showing how to simulate a Turing machine within the Game of Life; the Droste effect it refers to is best explained in by H. Lenstra in a talk given at Princeton on April 3, 2007, and available here.

Here is a link to the Wikipedia page on Perelman, and the Clay Institute’s description of the Poincaré conjecture. In 2006, The New Yorker published an interesting article on the unfortunate “controversy” on the priority of Perelman’s proof.

Here are David’s slides on his presentation, and the Wikipedia page on Cauchy.

Here is a link to Ross Honsberger’s article on Pósa (including the result on Hamiltonian circuits that Taylor showed during her presentation).

Here are Sheryl’s slides on Pythagoras and his theorem. In case the gif file does not play, here is a separate copy:

The Pythagorean theorem has many proofs, even one discovered by President Garfield!

Finally, here is the Wikipedia page on $\mbox{Erd\H os}$ . Oakland University has a nice page on him, including information on the $\mbox{Erd\H os}$ number; see also the page maintained by Peter Komjáth, and an online depository of most of $\mbox{Erd\H os's}$ papers.

Leave a Comment » | 187: Discrete mathematics | Tagged: Alan Turing, Augustin Cauchy, Georg Cantor, Grigori Perelman, Lajos Posa, Paul Erdos, Pythagoras | Permalink
Posted by andrescaicedo

502 – Equivalents of the axiom of choice

November 11, 2009

The goal of this note is to show the following result:

Theorem 1 The following statements are equivalent in ${{\sf ZF}:}$

The axiom of choice: Every set can be well-ordered.

Every collection of nonempty set admits a choice function, i.e., if ${x\ne\emptyset}$ for all ${x\in I,}$ then there is ${f:I\rightarrow\bigcup I}$ such that ${f(x)\in x}$ for all ${x\in I.}$

Zorn’s lemma: If ${(P,\le)}$ is a partially ordered set with the property that every chain has an upper bound, then ${P}$ has maximal elements.

Any family of pairwise disjoint nonempty sets admits a selector, i.e., a set ${S}$ such that ${|S\cap x|=1}$ for all ${x}$ in the family.

Any set is a well-ordered union of finite sets of bounded size, i.e., for every set ${x}$ there is a natural ${m,}$ an ordinal ${\alpha,}$ and a function ${f:\alpha\rightarrow{\mathcal P}(x)}$ such that ${|f(\beta)|\le m}$ for all ${\beta<\alpha,}$ and ${\bigcup_{\beta<\alpha}f(\beta)=x.}$

Tychonoff’s theorem: The topological product of compact spaces is compact.

Every vector space (over any field) admits a basis.

Read the rest of this entry »

2 Comments | 502: Logic and set theory | Tagged: Andreas Blass, Andrey Tychonoff, Azriel Levy, David Pincus, Ernst Zermelo, Georg Cantor, Herman Rubin, John Kelley, Max Zorn, Thomas Jech, Ulrich Felgner | Permalink
Posted by andrescaicedo

502 – Cantor-Bendixson derivatives

November 8, 2009

Given a topological space $X$ and a set $B\subseteq X,$ let $B'$ be the set of accumulation points of $B,$ i.e., those points $p$ of $X$ such that any open neighborhood of $p$ meets $B$ in an infinite set.

Suppose that $B$ is closed. Then $B'\subseteq B.$ Define $B^\alpha$ for $B$ closed compact by recursion: $B^0=B,$ $B^{\alpha+1}=(B^\alpha)',$ and $B^\lambda=\bigcap_{\alpha<\lambda}B^\alpha$ for $\lambda$ limit. Note that this is a decreasing sequence, so that if we set $B^\infty=\bigcap_{\alpha\in{\sf ORD}}B^\alpha,$ there must be an $\alpha$ such that $B^\infty=B^\beta$ for all $\beta\ge\alpha.$

[The sets $B^\alpha$ are the Cantor-Bendixson derivatives of $B.$ In general, a derivative operation is a way of associating to sets $B$ some kind of “boundary.”]

Read the rest of this entry »

3 Comments | 502: Logic and set theory | Tagged: Cantor-Bendixon derivative, Georg Cantor, Ivar Otto Bendixson, Philip Jourdain, set of uniqueness | Permalink
Posted by andrescaicedo

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

A kind of library

314 – Foundations of Analysis – Syllabus

Analysis – HW 4 – Fractals

Analysis – Counting the rationals

Analysis – Some remarks on continued fractions

515 – Homework 2

187 – List of all presentations

502 – Equivalents of the axiom of choice

502 – Cantor-Bendixson derivatives

Categories

Recent Comments

Mathematical links

My pages

Others

Mathoverflow

Math.StackExchange

Archives