Comparability of cardinals from Zorn’s lemma

September 26, 2014

One of the basic consequences of the axiom of choice is that any two sets are comparable, that is, there is an injection from one into the other. The standard argument for this uses that choice is equivalent to the well-ordering theorem: One can prove (without choice) that any two well-ordered sets are comparable, and the well-ordering theorem states that any set is well-orderable.

If for some (foolhardy) reason (say, one is teaching an analysis or algebra course) one is interested in the result, but wants to avoid discussing the theory or well-orders, it seems desirable to have a proof based directly on Zorn’s lemma.

A few weeks ago, Sam Coskey and I found ourselves discussing such a proof. It turns out the argument, though not as well-known as may be expected, dates back at least to Chaim Samuel Hönig, and his short note Proof of the well-ordering of cardinal numbers, Proc. Amer. Math. Soc., 5, (1954), 312. MR0060558 (15,690a). It goes as follows: Let the sets A and B be given. Consider the collection of all partial injections f from A into B. That f is partial means that there is a C\subseteq A such that f:C\to B. Order this collection by extension: f\le f' iff f\subseteq f'. This poset satisfies the conditions of Zorn’s lemma, so it admits maximal elements. One easily verifies that, if f is maximal, then A is the domain of f, or B is its range. In either case, this gives us an injection from one of the sets into the other.

A natural extension of the idea allows us to recover that the class of cardinals is not just linearly ordered, but in fact well-ordered, but an additional use of the axiom of choice is needed now (namely, in the form: The product of non-empty sets is non-empty). Suppose first that \mathcal C is a set. We argue that one of the members of \mathcal C injects into all others. The proof is essentially the same as before: Let A\in \mathcal C, and consider the family of all sequences (f_B\mid B\in\mathcal C) such that for some A'\subset A and all B, we have that f_B:A'\to B is injective. This is a partial order under coordinatewise inclusion. Again, Zorn’s lemma applies, so there is a maximal element \vec f=(f_B\mid B\in \mathcal C); call A' the common domain of all the f_B. If A'=A, we are done. Else (and this is where the additional use of choice comes in), for some B, the range of f_B is B: Otherwise, we can pick a'\in A\setminus A' and a sequence (b_B\mid B\in\mathcal C) such that, for all B, b_B\in B\setminus f_B[A']. But then, setting f'_B=f_B\cup\{(a',b_B)\}, we see that (f'_B\mid B\in\mathcal C) contradicts the maximality of \vec f. The result follows: Letting B be such that f_B is onto, we see that B injects into A', and A' injects into all sets in \mathcal C.

Finally, consider a (proper) class \mathcal C. Again, fix A\in\mathcal C. Let \mathcal C' be the collection of subsets of A equipotent to sets in \mathcal C. Since \mathcal C' is a set, the previous analysis applies, and we can find a C\in \mathcal C that injects into all members of \mathcal C that inject into A. It follows that C actually injects into all members of \mathcal C. Otherwise, there is a B\in\mathcal C that C does not inject into. But then B itself injects into C, and therefore into A. But this means that C injects into B after all.

Coming attractions

September 26, 2014


414/514 Homework 1 – The reals

September 11, 2014

This set is due in two weeks, on Friday September 26, at the beginning of lecture.

1. Recall that in the construction of the reals via Dedekind cuts, a real is simply the left set of a pair (A\mid B) in a cut of \mathbb Q, that is, a “real” is a set A\subset \mathbb Q that is non-empty, bounded above, closed to the left (meaning, if x\in A, y\in\mathbb Q, and y<x, then y\in A), and such that A has no maximum. We also have a copy \mathbb Q^* of \mathbb Q inside \mathbb R, given by the identification q\mapsto q^*:=\{t\in\mathbb Q\mid t<q\}. We left a few details to be verified when we presented this construction.

Let r be a real (in the sense just described). Define carefully the real -r (meaning, describe -r as a specific set of rationals, and verify that it is a real in the sense under discussion), and verify that -r+r=0, and that -r is the only real with this property.

Define carefully the product rs of reals r and s, and verify that the distributive property holds.

Check that \mathbb R is Dedekind-complete, that is, any cut of \mathbb R is realized. (S0, ignoring the formal difference between \mathbb Q and \mathbb Q^*, this version of \mathbb R is the Dedekind-completion of \mathbb Q, and this gives us that it is also the Dedekind completion of itself. )

2. More generally, define the Dedekind completion of a dense order, and verify its existence and uniqueness (up to isomorphism). In particular, the field \mathbb R(x) of  rational functions admits a completion, call it \hat{\mathbb R}(x). Can we extend the addition operation on \mathbb R(x) so it is defined in all of \hat{\mathbb R}(x) and makes it into an abelian group? Can we extend the order so \hat{\mathbb R}(x) is in fact an ordered group? What, if any, is the problem trying to extend multiplication?

3. Recall that in the construction of the reals via Cauchy sequences, a real is an equivalence class of Cauchy sequences of rationals, under the equivalence relation that states that two Cauchy sequences q_0,q_1,\dots and r_0,r_1,\dots are equivalent iff q_0,r_0,q_1,r_1,\dots is a Cauchy sequence.

Verify that this is indeed an equivalence relation, and that, given equivalent sequences \vec q and \vec r, the resulting interleaving sequence is equivalent to both. Verify that the (pointwise) definitions of addition and multiplication make sense, and that the resulting set equipped with these operations is indeed a field. Define carefully the ordering relation, and prove that it gives us a field ordering. Finally, verify that the resulting ordered field is indeed Dedekind complete.

4. Recall the construction of the reals described in Street’s paper An efficient construction of real numbers. His short note makes many claims that are not proved there. Provide as many of the missing details as possible.

5. Given a linear order (X,<), in the order topology the open sets are (by definition) those subsets of X that are union of (bounded or unbounded) open intervals in X. Show that a linear order (X,<) is order isomorphic to \mathbb R iff the following three properties are verified:

  • X has no first or last elements.
  • X is connected, that is, we cannot write X=A\cup B where A and B are open, nonempty, and disjoint.
  • X is separable, that is, there is a countable subset of X that is dense in X.



Daniel Donado – Metric spaces on omega_1 under determinacy

August 24, 2014

Daniel was my first masters student, completing his M.S. in June 2010. I co-advised him together with my friend and colleague Ramiro de la Vega, at the Universidad de los Andes, in Bogota. The following picture is from his Facebook profile.

Daniel Donado


Daniel’s thesis, Metric spaces on \omega_1 under the axiom of determinacy (in Spanish), is part of a vastly unexplored field: general topology in the absence of choice.

Work on this area has been mostly about highlighting pathologies, illustrating how vastly different results can be when we keep standard definitions but work in setting where the axiom of choice fails badly. Even in the setting of the real numbers with the standard topology, things may not work as expected: Every set of reals may be Borel (in fact F_{\sigma\sigma}), there may be Borel infinite Dedekind-finite sets, etc. In his PhD thesis at UC Berkeley, Apollo Hogan showed that, instead, we can carry out a systematic and detailed study of general topology if instead of dealing with arbitrary models with absurd failures of choice, we concentrate on settings where the absence of choice is compensated by a rich combinatorial structure. Specifically, Apollo (who was a student at Berkeley at the same time I was there) considered topology under the axiom of determinacy. Daniel’s thesis is a survey of some of the results discovered by Apollo.

Daniel begins by reviewing some of the basic consequences of \mathsf{AD}, the axiom of determinacy. To state \mathsf{AD}, we need to consider certain ideal games between two players, that I will just call I and II. In all these games the format is the same: players I and II alternate with I playing first. In each turn, the corresponding player picks a natural number, repetitions being allowed, and both players having knowledge of all the moves both have made previously. They play for infinitely many rounds. At the end, a sequence of natural numbers \langle n_0,n_1,n_2,\dots\rangle has been produced, with n_0,n_2,n_4,\dots being the numbers picked by player I, and n_1,n_3,\dots being the ones picked by II. We have one of these games for each set A\subseteq\mathbb N^{\mathbb N}, where \mathbb N^{\mathbb N} is the set of all infinite sequences of natural numbers. In the game associated to such an A, player I wins iff the sequence \langle n_0,n_1,n_2,\dots\rangle is in A. Otherwise, player II is the winner.

A strategy \sigma for player I is a function that tells player I what to play each time. Formally, this is just a function from the set of finite sequences of numbers to \mathbb N. A strategy for II is defined similarly. We say that a strategy for I is winning if and only if player I wins the game whenever they play following the strategy. That is, in any such game we have  n_0=\sigma(\langle\rangle), n_2=\sigma(\langle n_1\rangle), n_4=\sigma(\langle n_1,n_3\rangle), etc, and at the end we have that \langle n_0,n_1,n_2,\dots\rangle\in A. Winning strategies for player II are defined similarly. We say that A is determined iff one of the players has a winning strategy.

It is easy to give examples of determined sets A. Using the axiom of choice, we can give examples of undetermined sets, but deep theorems in descriptive set theory indicate that no undetermined set can be particularly simple. For instance, it is a celebrated theorem of Martin that all Borel sets are determined. Here, \mathbb N^{\mathbb N} is made into a topological space by taking the product topology of countably many copies of the discrete set \mathbb N.

The axiom of determinacy is the statement that all A\subseteq \mathbb N^{\mathbb N} are determined. In particular, this statement contradicts the axiom of choice. See here for slides of a talk I gave a few years ago containing a quick introduction to the subject.

The short remainder of this post (after the fold) is by necessity more technical.

Read the rest of this entry »

287 Communication in the mathematical sciences – Syllabus

August 24, 2014

Instructor: Andrés E. Caicedo
Fall 2014

Time: MW 1:30-2:45 pm.
Place: Mathematics building, Room 139.

This class satisfies the CID requirement in mathematics.

Contact Information

  • Office: 239-A Mathematics building.
  • Phone number: (208)-426-1116. (Not very efficient.)
  • Office Hours: W 12:00-1:15 pm. (Or by appointment.)
  • Email:


Mount Holyoke College
Laboratories in mathematical experimentation. A bridge to higher mathematics.
Textbooks in Mathematical Sciences. Springer-Verlag, New York, 1997. xx+278 pp.
ISBN: 0-387-94922-4.

Contents (Thanks to Samuel Coskey for suggestions)

The course decription at the Department’s site describes this course as follows:

Integrates mathematics content with the opportunity to develop proof writing and communication skills important in the mathematical sciences. Content is drawn from discrete and foundational math and elementary analysis. Introduction to and engagement with written and verbal communication practices characteristic to mathematical sciences. Introduction to and use of technologies that support communication in the mathematical sciences.

Following up on the theme introduced in Math 187, this course will help you transition from computational to proof-based mathematics. Skill at computations is of course still essential. However, in deeper mathematical study, we ask broader questions, and require that the answers be justified by proofs. In this course we will practice proving theorems, and along the way we will participate in the whole mathematical process.

A key realization is that, in actual mathematical research, we are not told what statement to prove, but must instead ask good questions and investigate them methodically. Even if there is a statement we are interested in, we typically do not know whether it is indeed true. In this class we will get practical experience in discovery, conjecture, and exposition of mathematical truth. We will learn to gather data to inform our conjectures, usually with the aid of a computer program. In the process we will learn to distinguish between evidence and proof, and to use both in support of our statements.

In most classes, you are expected to work individually and you are assessed in a timed environment. In a CID course such as this one, we focus instead on the activities that actually take place in the discipline: collaboration with our peers, writing research papers, attending and giving talks, and so on.  Accordingly, we will take a look at some of the key technologies that mathematicians use to carry out and share their work. There are many mathematical programming languages, but we will use Sage. We will typeset papers in LaTeX, and presentations in Beamer.


Please visit Sharelatex, where you can start practicing right away and work in groups. LaTeX has been the primary tool for the dissemination of mathematics (and many other sciences, take a look at the ArXiv to get an idea of how widely used the program is), and it has been so for almost 35 years, even though it has changed very little in that time. It is important to master the LaTeX system, since the language it provides for expressing mathematics will certainly be the standard for many years to come. MathJax and other technologies are expected to eventually replace LaTeX as the standard, but for the time being, knowing it is essential. for instance, Scott Aaronson lists as the first of his Ten Signs a Claimed Mathematical Breakthrough is Wrong that the authors do not use (La)TeX.

LaTeX is available as free software, and abundant documentation exists. A few useful references are The (not so) short introduction to LaTeX, the NASA guide to LaTeX commands, and The comprehensive LaTeX symbol list. I recommend that you also bookmark and visit frequently the Q&A site on Stack Exchange.


Beamer is a LaTeX documentclass designed especially for creating powerpoint-style presentations. The output is a pdf file that you can click through page-by-page while you speak. In the code, you simply enclose each slide within \begin{frame}{My Title} and \end{frame}. Inside, simply use the LaTeX commands that you are used to. The ultimate Beamer reference is the full user guide, but this may contain too much information, and to get started the less intimidating short intro (and its source) may be more useful.

Sage and python

Sage is a computer algebra system and programming language. In the long term, knowing it may be just as important and useful if not more than knowing LaTeX. While you are welcome to use any language you prefer, I recommend Sage because it is free to use online, and has been developed as open source software from the beginning. The recently developed Sage Cloud makes its use even more convenient.

When getting started, check out the guided tour or the introductory video series. There is also a nice web site for the nuts and bolts of Python at learnpython. You can start using Sage very quickly by logging into using your google mail account.


Your grade will be based on your in-class work, your written reports, and short oral presentations.

All of your time in-class will be devoted to our research projects. Come to class every day prepared to listen, think, and discuss mathematics with your group. Buy a notebook just for Math 287 and keep careful track of your thoughts and data. Assign yourself homework each class so you can bring new ideas to the next meeting. Since attendance and participation are crucial to your success, absences will lower your grade rapidly. [Documented absences are always excused, and you may have one or two free unexplained absences.]

At the end of each unit you will turn in a written article called a “lab report” that summarizes and explains the results of your activities. The majority of your grade will be based on these reports, each of which receives a letter grade.

You will also be asked to give several (typically very short) presentations on your work, individually or as a group. In total, these will be worth about the same as a lab report.

Further details will be provided once we get started.

Additional information will be posted in this blog, and students are encouraged to use the comments feature. Please use full names, which will simplify my life filtering spam out.

On occasion, I post links to supplementary material on Google+ and Twitter.

414/514 Advanced Analysis (Analysis I) – Syllabus

August 20, 2014

Instructor: Andrés E. Caicedo
Fall 2014

Time: MWF 10:30-11:45 am.
Place: Mathematics building, Room 139.

Contact Information

  • Office: 239-A Mathematics building.
  • Phone number: (208)-426-1116. (Not very efficient.)
  • Office Hours: W 12:00-1:15 pm. (Or by appointment.)
  • Email:

We will use three textbooks and complement with papers and handouts for topics not covered there.

  • MR1886084 (2003e:00005).
    Pugh, Charles Chapman
    Real mathematical analysis.
    Undergraduate Texts in Mathematics. Springer-Verlag, New York, 2002. xii+437 pp.
    ISBN: 0-387-95297-7.
  • MR0655599 (83j:26001).
    van Rooij, A. C. M.; Schikhof, W. H.
    A second course on real functions.
    Cambridge University Press, Cambridge-New York, 1982. xiii+200 pp.
    ISBN: 0-521-23944-3; 0-521-28361-2.
  • MR1996162. See also MR0169961 (30 #204).
    Gelbaum, Bernard R.; Olmsted, John M. H.
    Counterexamples in analysis.
    Corrected reprint of the second (1965) edition. Dover Publications, Inc., Mineola, NY, 2003. xxiv+195 pp.
    ISBN: 0-486-42875-3.

The book by van Rooij and Schikhof will be our primary reference, supplemented naturally by the Counterexamples book.  The book assumes some knowledge beyond what is covered in our undergraduate course Math 314: Foundations of Analysis, and does not cover the theory in dimension n>1; for these topics, we will follow Pugh’s text.

Math 414/514 covers Analysis on Euclidean spaces ({\mathbb R}^n) with emphasis on the theory in dimension one. The approach is theoretical, as opposed to the more computational approach of calculus, and a certain degree of mathematical maturity is required. The course is cross-listed, and accordingly the level will be aimed at beginning graduate students.

From the Course Description on the Department’s site:

Introduction to fundamental elements of analysis on Euclidean spaces including the basic differential and integral calculus. Topics include: infinite series, sequences and series of function, uniform convergence, theory of integration, implicit function theorem and applications.

Here is a short list of topics we expect to cover. This list may change based on students’ interest:

  1. Set theoretic preliminaries.
    • Cantor’s approach to infinite cardinalities. Countable vs. uncountable sets. Sets of size continuum. The Bernstein-Cantor-Schröder theorem.
    • The axiom of choice. Zorn’s lemma. Countable and dependent choice.
    • Transfinite recursion. The first uncountable ordinal \omega_1.
  2. Axiomatization and construction of the set of reals.
    • The least upper bound property; uniqueness of \mathbb R up to isomorphism.
    • Dedekind cuts, and complete orders.
    • Metric spaces, and Cauchy completions. Banach contraction mapping theorem.
  3. Topology on \mathbb R.
    • Open and closed sets. Compact sets and Cantor sets. Baire space.
    • Borel sets. Analytic sets.
    • Notions of smallness.
      • Meagerness and the Baire category theorem. The Baire-Cantor stationary principle.
      • Sets of Jordan content zero and of measure zero.
      • Introduction to the theory of strong measure zero sets.
  4. Continuity.
    • Sets of discontinuity of functions.
    • Monotonicity. Functions of bounded variation.
  5. Differentiability.
    • The problem of characterizing derivatives. Baire class one functions. The intermediate value property. Sets of continuity of derivatives.
    • The mean value theorem. L’Hôpital’s rule.
    • The dynamics of Newton’s method.
    • The Baire hierarchy of functions.
    • Continuous nowhere differentiable functions.
  6. Power series.
    • Real analytic functions. Taylor series.
    • C^\infty functions. Zahorsky’s characterization of the sets of points where a C^\infty function fails to be analytic.
  7. Integration.
    • Riemann integration. Lebesgue’s characterization of Riemann integrability.
    • Weierstraß approximation theorem.
    • Lebesgue integration. The fundamental theorem of calculus.
    • The Henstock-Kurzweil integral. Denjoy’s approach to reconstructing primitives.
  8. Introduction to multivariable calculus.
    • (Frechet) derivatives.
    • The inverse and implicit function theorems.


Based on homework. No late homework is allowed. Collaboration is encouraged, although students must turn in their own version of the solutions, and give credit to books/websites/… that were consulted and people with whom the problems where discussed.

There will be no exams. However, an important component of being proficient in mathematics is a certain amount of mental agility in recalling notions and basic arguments. I plan to assess these by requesting oral presentations of solutions to some of the homework problems throughout the term. If I find the students lacking here, it will be necessary to have an exam or two. The final exam is currently scheduled for Wednesday, December 17, 2014, 12:00-2:00 pm.

Additional information will be posted in this blog, and students are encouraged to use the comments feature. Please use full names, which will simplify my life filtering spam out.

On occasion, I post links to supplementary material on Google+ and Twitter.

Pdf version of this post.

403 – HW 4 – Algebraic graph theory

April 28, 2014

This set is due Thursday, May 15, at 11am.

1. (Norman Biggs, Algebraic Graph Theory, Proposition 2.3) Let \Gamma be a (finite, simple) graph with n vertices, and let A be its adjacency matrix. Suppose that the characteristic polynomial of A is {\rm char}_A(x)=x^n+c_1x^{n-1}+c_2x^{n-2}+\dots+c_n. Verify that:

  1. c_1=0.
  2. -c_2 is the number of edges in \Gamma.
  3. -c_3 is twice the number of triangles in \Gamma.

2.  (Chris Godsil, Gordon F. Royle, Algebraic Graph Theory, Theorem 8.5.1) Let G be a finite simple graph on n vertices that is k-regular, that is, such that each vertex has degree k. Suppose G has n vertices and A is its adjacency matrix.

  1. Verify that k is an eigenvalue of A.
  2. Let \lambda_2,\dots,\lambda_n be the other eigenvalues of A. Let \bar G denote the complementary graph to G: This graph has the same vertices, but two vertices are joined by an edge iff they are not joined by an edge in G. Let B be the adjacency matrix of \bar G. Show that there is a basis of \mathbb R^n consisting of vectors that are common eigenvectors of B and A, and that the eigenvalues of B are n-k-1,-1-\lambda_2,\dots,-1-\lambda_n.


Get every new post delivered to your Inbox.

Join 49 other followers