Introduction to Cambridge IA Analysis I 2014

This term I shall be giving Cambridge’s course Analysis I, a standard first course in analysis, covering convergence, infinite sums, continuity, differentiation and integration. This post is aimed at people attending that course. I plan to write a few posts as I go along, in which I will attempt to provide further explanations of the new concepts that will be covered, as well as giving advice about how to solve routine problems in the area. (This advice will be heavily influenced by my experience in attempting to teach a computer, about which I have reported elsewhere on this blog.)

I cannot promise to follow the amazing example of Vicky Neale, my predecessor on this course, who posted after every single lecture. However, her posts are still available online, so in some ways you are better off than the people who took Analysis I last year, since you will have her posts as well as mine. (I am making the assumption here that my posts will not contribute negatively to your understanding — I hope that proves to be correct.) Having said that, I probably won’t cover exactly the same material in each lecture as she did, so the correspondence between my lectures and her posts won’t be as good as the correspondence between her lectures and her posts. Nevertheless, I strongly recommend you look at her posts and see whether you find them helpful.

You will find this course much easier to understand if you are comfortable with basic logic. In particular, you should be clear about what “implies” means and should not be afraid of the quantifiers \exists and \forall. You may find a series of posts I wrote a couple of years ago helpful, and in particular the ones where I wrote about logic (NB, as with Vicky Neale’s posts above, they appear in reverse order). I also have a few old posts that are directly relevant to the Analysis I course (since they are old posts you may have to click on “older entries” a couple of times to reach them), but they are detailed discussions of Tripos questions rather than accompaniments to lectures. You may find them useful in the summer, and you may even be curious to have a quick look at them straight away, but for now your job is to learn mathematics rather than trying to get good at one particular style of exam, so I would not recommend devoting much time to them yet.

What do I need to know before taking the course?

For the rest of this post, I want to describe briefly the prerequisites for this course. One of the messages I want to get across is that in a sense the entire course is built on one axiom, namely the least upper bound axiom for the real numbers. I don’t really mean that, but it would be correct to say that it is built on one new axiom, together with other properties of the real numbers that you are so familiar with that you hardly give them a second’s thought.

If I want to say that more precisely, then I will say that the course is built on the following assumption: there is, up to isomorphism, exactly one complete ordered field. If the phrase “complete ordered field” is unfamiliar to you, it doesn’t matter, though I will try to explain what it means in a moment. Roughly speaking, this assumption is saying that there is exactly one mathematical structure that has all the arithmetical and order properties that you would expect of the real numbers, and also satisfies the least upper bound axiom. And that structure is the one we call the real numbers.

And now let me make that more precise.

What is a field?

A field is a set X with two binary operations \square and * that behave in the same nice ways that addition and multiplication behave in the real numbers. That is, they have the following properties.

(i) \square is commutative and associative and has an identity element. Every element of X has an inverse under \square.

(ii) * is commutative and associative and has an identity element. Every element of X other than the identity of \square has an inverse under *.

(iii) * is distributive over \square. That is, for any three elements x,y,z of X we have x*(y\square z)=(x*y)\square(x*z).

If we define an algebraic structure with some notions of addition and multiplication, then to say that it is a field is to say that all the usual rules we use to do algebraic manipulations are valid. It can be amusing and instructive to prove facts such as that (-x)(-y)=xy assuming nothing more than the field axioms, but in this course I shall take these slightly less elementary facts as read as well. But I assure you that they do follow from the field axioms.

Some examples of fields that you have already met are \mathbb{Q}, \mathbb{R}, \mathbb{C} and \mathbb{F}_p. (That last one is the field that consists of integers mod p for a prime p, with addition and multiplication mod p. The only axiom that is not easy to verify is the existence of multiplicative inverses for non-zero elements of the field, which follows from the fact that if a and b are coprime then there are integers h and k such that ha+kb=1.)

What is an ordered field?

This question splits into two. First we need to know what an ordering is, and then we need to know how the ordering relates to the algebraic operations. Let me take these two in turn.

A totally ordered set is a set X together with a relation < that has the following properties.

  1. < is transitive: that is, if x<y and y<z, then x<z.
  2. < satisfies the law of trichotomy: that is, for any x,y\in X exactly one of the statements x<y, x=y, y<x holds.

Note that the trichotomy law implies that < is antisymmetric: that is, if x<y then it cannot also be the case that y<x.

In the above situation, we say that < is a total ordering on X. Given a total ordering < we can make some obvious further definitions. For instance, we can define > by saying that x>y if and only if y<x. (Note that > is also a total ordering on X.) Also, we can define \leq by saying that x\leq y if and only if either x<y or x=y, and similarly we can define \geq.

Here’s an example of a totally ordered set that is not just a subset of the real numbers. We take X to be the set of all polynomials with real coefficients, and if P and Q are two polynomials, we say that P<Q if there exists a real number M such that P(x)<Q(x) for every x\geq M. (That is, P<Q if Q is “eventually bigger than P“.) It is easy to check that this relation is transitive, and an instructive exercise to prove that the trichotomy law holds. (It is also not too hard, so I think it is better not to give the proof here.)

How should we define an ordered field? A first guess might be to say that it is a field with a total ordering on it. But a moment’s thought shows that that is a ridiculous definition, since we could define a “stupid” total ordering that had nothing to do with any natural ordering we might want to put on the field. For example, we could define an ordering on the rationals as follows: given two rational numbers p/q and r/s, written in their lowest terms with q and s positive, say that p/q<r/s if either p<r or p=r and q<s. That is certainly a total ordering on the rationals, but it is a rather strange one. For example, with this ordering we have 2/3<3/100 and also 2/5<3/7<3/11.

What has gone wrong? The answer is that it is not interesting to have two structures on a set (in this case, the algebraic structure and the order structure) unless those structures interact. In fact, we have already seen this in the field axioms themselves: we have addition and multiplication, and it is absolutely crucial to have some kind of relationship between them. The relation we have is the distributivity law. Without that, we would allow “stupid” examples of pairs of binary operations that had nothing to do with each other.

An ordered field is a field F together with a total ordering < that satisfies the following properties.

  1. For every x,y,z\in F, if x<y, then x+z<y+z.
  2. For every x,y,z\in F, if x<y and z>0, then xz<yz.

Basically what these properties are saying is that the usual rules we use when manipulating inequalities, such as adding the same thing to both sides, apply.

In practice, we tend to use a rather larger set of rules. For example, if we know that 0<x<y, we will feel free to deduce that 0<1/y<1/x. And nobody will bat an eyelid if you have a real number x and state without proof that x^2\geq 0. Both these facts can be deduced fairly easily from the properties of ordered fields, and again it is quite a good exercise to do this if you haven’t already. However, in this course we shall take the following attitude. There are the axioms for an ordered field. There are also some simple deductions from these axioms that provide us with some further rules for manipulating equations and inequalities. All of these we will treat in the same way: we just use them without comment.

Abstract versus concrete

Before I get on to the most important axiom, and the one that very definitely will not be used without comment, I want to discuss a distinction that it is important to understand: the distinction between the abstract and the concrete approaches to mathematics. The abstract approach is to concentrate on the properties that mathematical structures have. We are given a bunch of properties and we see what we can deduce from them, and we do that quite independently of whether any object with those properties exists. Of course, we do like to check that the properties are consistent, which we do by finding an object that satisfies them, but once we have carried out that check we go back to concentrating on the properties themselves.

The concrete approach to mathematics is much more focused on the objects themselves. We take an object, such as the set of all prime numbers, and try to describe it, prove results about it, and so on.

The boundary between the two approaches is extremely fuzzy, because we often like to convert the concrete approach into a more abstract one. For example, consider the function x\mapsto\sin(x). This can be defined concretely as the function given by the formula \sum_{n=0}^\infty (-1)^nx^{2n+1}/(2n+1)!. (That’s just a concise way of writing x-x^3/3!+x^5/5!-\dots.) And a similar definition can be given for \cos(x). But somewhere along the line we will want to prove basic facts such as that \sin(x+y)=\sin(x)\cos(y)+\cos(x)\sin(y), or that \sin^2(x)+\cos^2(x)=1, or that \frac d{dx}\sin(x)=\cos(x). And once we’ve proved a few of those facts, we find that we no longer want to use the formula, because everything we need to know follows from those basic facts. And that is because with just a couple more facts of the above kind, we find that we have characterized the trigonometric functions: that is, we have written down properties that are satisfied by \sin and \cos and by no other pair of functions. When this kind of thing happens, our approach has shifted from the concrete (we are given the formulae and want to prove things about the resulting functions) to the abstract (we are given some properties and want to use them to deduce other properties).

Something very similar happens with the real numbers. Up to now (at least until taking Numbers and Sets), you will have been used to thinking of the real numbers as infinite decimals. In other words, the real number system is just out there, an object that you look at and prove things about. But at university level one takes the abstract approach. We start with a set of properties (the properties of ordered fields, together with the least upper bound axiom) and use those to deduce everything else. It’s important to understand that this is what is going on, or else you will be confused when your lecturers spend time proving things that appear to be completely obvious, such as that the sequence 1/n converges to 0. Isn’t that obvious? Well, yes it is if you think of a real number as one of those things with a decimal expansion. But it takes quite a lot of work to prove, using just the properties of a complete ordered field, that every real number has a decimal expansion, and rather than rely on all that work it is much easier to prove directly that 1/n converges to 0.

The least upper bound axiom

What is a least upper bound?

Let A be a set of real numbers. A real number x is an upper bound for A if a\leq x for every a\in A. For example, if A is the open interval (0,1), then 2 is an upper bound for A.

A real number s is the least upper bound of A if it has the following two properties.

  1. s is an upper bound for A.
  2. If t<s, then t is not an upper bound for A.

Another way of writing these two properties is as follows. I’ll use quantifiers.

  1. \forall a\in A a\leq s.
  2. \forall t<s\ \exists a\in A\ a>t.

In words, everything in A is less than or equal to s, and for any t<s there is some a\in A that is bigger than t.

As an example, 1 is the least upper bound of the open interval (0,1). Why? Because if x\in (0,1) then x<1, and if u<1 then we can find x\in (0,1) such that x>u. (How do we do this? Well, if u<0 then take x=1/2 and if u\geq 0 then take (1+u)/2.)

The least upper bound property is the following statement: every non-empty subset of the reals that has an upper bound has a least upper bound.

But since we are thinking abstractly, we will not think of this as a property (of the previously given real numbers) but more as an axiom. To do so we can state it as follows.

Let F be an ordered field. We say that F has the least upper bound property if every non-empty subset of F that has an upper bound has a least upper bound.

For reasons that will become clear only after the course has started, we say that an ordered field with the least upper bound property is complete. There are then two very important theorems that we shall assume.

Theorem 1. There exists a complete ordered field.

Theorem 2. There is only one complete ordered field, in the sense that any two complete ordered fields are isomorphic.

I don’t propose to give proofs of either of these results, but let me at least give some indication, for those who are interested, of how they can be proved. The proofs are not required knowledge for the course, but it’s not a bad idea to have some inkling of how they go.

Why does there exist a complete ordered field?

One answer to this is that the reals are a complete ordered field! That is, if you take the good old infinite decimals that you are used to, and you say very carefully what it means to add or multiply two of them together, and you order them in the obvious way, then you can actually prove rigorously that you have a complete ordered field. It’s not very pretty (partly because of the fact that point nine recurring equals 1) but it can be done.

Here’s how one can prove the least upper bound property. For convenience let us take a non-empty set A that consists of positive numbers only. Assuming that A is bounded above, we would like to find a least upper bound. We can do this as follows. First, find the smallest integer that is an upper bound for A. (We know that there must be an integer — just take any integer that is bigger than the upper bound C we are given for A. If we are defining the reals as infinite decimals, then it is genuinely obvious that such an integer exists — you just chop off everything beyond the decimal point and add 1.) Call this integer m. Next, we find the smallest multiple of 0.1 that is an upper bound for A. This will be one of the numbers m, m-0.1, m-0.2,\dots, m-0.9. Then you take the smallest multiple of 0.01 that is an upper bound for A, and so on. This gives you a sequence that might be something like 17, 16.8, 16.74, 16.739, 16.7390, 16.73899,\dots. If you look at an individual digit of the numbers in this sequence, such as the fifth after the decimal point, it will eventually stabilize, and if you take these stabilized digits as the digits of a certain number, then that number will be an upper bound for A and no smaller number will be. (Both these statements need to be checked, but both are reasonably straightforward.)

A more elegant way to prove the existence of a complete ordered field is to use objects called Dedekind cuts. A Dedekind cut is a partition of the rational numbers into two non-empty subsets A and B such that every element of A is less than every element of B, and such that B does not have a minimal element.

To see why this might be a reasonably sensible definition, consider the sets A and B, where A consists of all rationals x such that either x<0 or x^2\leq 2, and B consists of all positive rationals y such that y^2>2. This is the Dedekind cut that corresponds to our ordinary conception of the number \sqrt{2}.

The condition that B should not have a minimal element is to make sure that we don’t have two different Dedekind cuts representing each rational number. (If the rational number is w, the partition we are ruling out is A=\{x\in\mathbb{Q}:x<w\} and B=\{x\in\mathbb{Q}:x\geq w\}. We just allow the partition A=\{x\in\mathbb{Q}:x\leq w\} and B=\{x\in\mathbb{Q}:x>w\}.)

If (A,B) and (C,D) are two Dedekind cuts, we can define their sum to be (A+C,B+D), where A+C is defined to be the set of all numbers a+c such that a\in A and c\in C, and similarly for B+D. It’s a bit harder to define products — you may like to try it. It’s not so hard to define a sensible total ordering on the set of all Dedekind cuts. And then there’s a lot of checking needed to prove that what results is a complete ordered field. (I may as well admit at this point that I’ve never bothered to check this for myself, or to read a proof in a book. I’m happy to know that it can be done, just as I’m happy to fly in an aeroplane without checking that the lift will be enough to keep me in the sky.)

Why is there essentially just one complete ordered field?

Here’s one answer. You just go back to your notes in Numbers and Sets and look at the proof that every real number has a decimal expansion. Obviously if you define real numbers to be things with decimal expansions, then this is saying nothing at all, but that’s not what Professor Leader did. He deduced the existence of decimal expansions from the properties of complete ordered fields. So effectively he proved the following result: every element of a complete ordered field has a decimal expansion. We can say slightly more: it has a decimal expansion that does not end with an infinite sequence of 9s. Oh, and two different elements have different decimal expansions. So now if you want an isomorphism between two complete ordered fields, you just match up an element of one with the element of the other that has the same decimal expansion.

Let me very briefly sketch a neater approach. You first match up 1 with 1. (That is, you match up the multiplicative identity with the multiplicative identity.) Then you match up 1+1 with 1+1, and so on, until you have “the positive integers” inside your two complete ordered fields matched together. Then you match up 0 with 0 and the additive inverses of the positive integers with the additive inverses of the positive integers. Then you match up the reciprocals of the positive integers (or rather, their multiplicative inverses) with the reciprocals of the positive integers, and finally all the rationals with all the rationals. What I’m saying here is that in any complete ordered field you can make sense in only one reasonable way of the fraction m/n when m and n are integers with n\ne 0, and you send each m/n in one complete ordered field to its counterpart in the other.

Now let’s take any element x of a complete ordered field. We can associate with x the set A of all “rationals” less than x and map that set over to the other complete ordered field, using our correspondence between rationals. That gives us a set A' in the other complete ordered field. The least upper bound of A' is then the element that corresponds to x.

As ever, there is work needed if you want to turn the above idea into a complete proof: if the map you’ve defined is \phi, then you need to check things like that \phi(xy)=\phi(x)\phi(y) or that if a set Y has least upper bound s, then \phi(Y) has least upper bound \phi(s). But all that can be done.

Conclusion

If you found what I’ve just written a bit intimidating, let me remind you that all you need to take away from it is that everything in this course will be deduced from the familiar algebraic and order properties of the reals, together with the least upper bound property. Since the algebraic and order properties should be very familiar to you, that means that the main things you need to learn are the definition of a least upper bound and the statement of the least upper bound property. The details matter, so a vague idea is not enough, but even so it’s not very much to learn.

About these ads

21 Responses to “Introduction to Cambridge IA Analysis I 2014”

  1. Anonymous Says:

    Any plans for a MOOC?

  2. Sean Eberhard Says:

    A small nitpick about Dedekind cuts: You must decide whether A = \{x\in\mathbf{Q} : x < 2\} is a cut or whether \{x\in\mathbf{Q} : x \leq 2\} is a cut. You cannot have both. This is essentially the "point nine recurring equals one" complication rearing its ugly head again.

  3. tomcircle Says:

    Reblogged this on Math Online Tom Circle.

  4. Globules Says:

    In “… say that p/1<r/s if either …" the 1 should be q.

    Many thanks — corrected now.

  5. Anonymous Says:

    “For example, if A is the open interval (0,1), then 2 is an upper bound for A.”

    I can’t understand above sentence. Isn’t 1 the upper bound for A?

  6. Introduction to Cambridge IA Analysis I 2014 | Math Online Tom Circle Says:

    […] Reblogged from Gowers's Weblog: […]

  7. Francois Says:

    In the definition of upper bound, the inequality should probably be nonstrict.

    Many thanks. I had corrected another of those but didn’t spot that one. I’ve changed it now.

  8. Anonymous Says:

    In line 43 in Section “Abstract versus concrete”, `Nunders’ should be `Numbers’.

    Thanks — corrected now. (Is it any defence that I actually wrote ‘Nunbers’? No, perhaps not.)

    • Anonymous Says:

      Well, since it is Cambridge, I first thought that the course is actually called “Nunbers and Sets” (old English + tradition?) until I saw “Numbers and Sets” a few paragraphs below.

  9. mathtuition88 Says:

    Reblogged this on Singapore Maths Tuition.

  10. Michael Hudson-Doyle Says:

    A minor point that I didn’t really get until much later in the Tripos was that to completely replace the concrete approach with the abstract the object should be unique up to unique isomorphism (which the reals obviously satisfy!)

    • Batata Says:

      That is not quite right, that’s absolutely not necessary to an “abstract” approach. Maybe this confusion is easy to make in real analysis because most of the time we think only of decimals as a concrete example of a complete ordered field and that is (maybe) good enough. Take for example ring theory, you have to have in mind a couple of rings to “get the feel” for the theorems we study.
      Last but not least, everything is unique up to some isomorphism (equivalence relation) in mathematics, that is the purpose of isomorphisms (morphisms, in general), to enable us to regard different objects as “the same” when studying specific properties.

    • gowers Says:

      A good example to illustrate Batata’s point is group theory. We can study something like the symmetry group of the cube or the group of all invertible n\times n real matrices in a concrete way, or we can look at the group axioms and their consequences. The latter is a perfectly valid abstract approach even though many objects satisfy the axioms: indeed, that is one of the main virtues of the abstract approach to group theory.

      But maybe your emphasis is on the word “completely”. Perhaps what you are saying is that we cannot deduce everything about a concrete object from certain properties unless those properties characterize the object. The natural response to that is that we often don’t want to deduce everything: we have certain specific statements in mind that we want to prove, and these may follow from properties that don’t characterize the object in question, in which case we will have proved a generalization of what we set out to prove.

  11. Marcelo de Almeida Says:

    Reblogged this on Being simple and commented:
    Cambridge’s course Analysis I

  12. NaN Says:

    I have never come across that total ordering on (real) polynomial functions before. Has it been of use somewhere? A part of me feels that is unlikely (since it depends of behaviour far away from the zeros), but I am an expert in being wrong.

  13. Nick T. Says:

    It is useful in many ways. Here is one:

    1. Show that this ordering extends in the obvious way to an ordering on the field of rational functions (i.e. fractions with polynomials as numerator and denominator), giving an ordered field.
    2. Show that this ordered field contains an isomorphic copy of the reals as an (ordered) subfield.
    3. Show that this copy of R is bounded in the field of rational functions.

    Thus, when we prove that R has the Archimedean property (for any real x there exists an integer n with n>x), we have to use the least upper bound property of R (in spite of the fact that Q has the same property).

  14. william e emba Says:

    Note that the straightforward proof that Dedekind cuts satisfy the associative law of multiplication has a ridiculous number of cases. (The others aren’t much fun either.) It is much simpler to prove everything for positive Dedekind cuts, then groupify a la Grothendieck.

  15. Timothy Gowers’s blog | Explaining mathematics Says:

    […] See http://gowers.wordpress.com/2014/01/11/introduction-to-cambridge-ia-analysis-i-2014/ for his introduction to first-year analysis in Cambridge. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 1,416 other followers

%d bloggers like this: