Notes on Analysis

Table of Contents

David Wakeham
The University of British Columbia

These notes give a brief introduction to real analysis. The emphasis is on applications, problem-solving and beautiful results, rather than complete rigour. We assume prior exposure to calculus, linear algebra, and basic set theory, but develop everything else from scratch.

1 Outline

We can split up the branches of pure mathematics according to their objects and the type of results they tend to provide. For our purposes, the contrast between analysis and algebra will be of most interest:

  • Algebra studies structure in an abstract, rule-governed way. It tends to produce results with a discrete, exact character, characterised by equations.
  • Analysis specialises to structures where points get very close to each other (such as on the real line) and we can therefore take limits. This lets us define new operations using limits, and by going partway along a limit, we can approximate operations. Thus, the currency of analysis is no longer equalities, but the inequalities needed to control approximations coming from limits.

In these notes, algebra will be rich source of basic structures, but our focus be on limits, approximation and inequalities. More specifically, our goals will be to:

  • understand what structures allow limits ("where");
  • precisely define the limiting process ("how");
  • introduce related operations like differentation, integration and power series ("what");
  • give powerful results on approximation and inequalities ("when");
  • and finally, discuss applications in applied and pure mathematics, physics, and other areas ("why").

Much of the interesting material in these notes has been deliberately placed in the exercises. The goal is to give students a strong incentive to do them! These include computational problems, which require access to a computer and basic facility with a programming language. Python is a popular, high-level languge for scientific programming which looks very similar to psuedocode. For this reason, any code snippets in the exercises (or their solutions) will be written in Python 3.

Finally, a few notes on format. Theorems, definitions, corollaries, etc, are stated in blue boxes, while examples and applications live in grey boxes. Boxes of different colour are numbered separately. White triangles (△) are used to denote harder exercises, and sections which can be skipped on first reading. Black triangles (▲) denote particularly hard exercises, or sections for advanced readers. Finally, exercises tagged with exclamation marks (!) are used later in the notes.

2 Number systems

2.1 TODO Number systems and the birth of rigour

We start by looking at some different number systems:

  • the natural numbers \(\mathbb{N}\) and integers \(\mathbb{Z}\) used for counting;
  • the rational numbers \(\mathbb{Q}\), where we see the first hints of continuous structure due to the density of fractions;
  • and finally the real numbers \(\mathbb{R}\), which are in one-to-one correspondence with the points on a line.

We will see some other, more exotic number systems in exercises. The approach will be to start with something simple and try to define interesting operations on these sets. When sets are in some sense "incomplete" with respect to these operations, we add the missing elements to get a bigger set. To give a sneak peak: \[ \mathbb{N} \overset{\text{additive inverses}}{\longrightarrow} \mathbb{Z} \overset{\text{multiplicative inverses}}{\longrightarrow} \mathbb{Q} \overset{\text{metric completion}}{\longrightarrow} \mathbb{R}. \] There are several ways to construct the real from the rationals, which we lump together under the heading "completion".

We then abstract in a couple of different directions. First, we use set theory to get a feel for the different "size" of number systems. We will see that the natural numbers, integers and rationals are all the same "size", which is unimaginably smaller than the real numbers! Secondly, we do ????

2.2 The natural numbers and integers

2.2.1 Peano arithmetic

The natural numbers \(\mathbb{N}\) are the numbers we use to count: \[ \mathbb{N} = \{0, 1, 2, \ldots\} \] In fact, zero is not an obvious inclusion and was one of the great developments of antique mathematics. The Egyptians were using zero arond 1770 BC both in accounting and pyramid design, where it denoted the base level. The hieroglyph used (Nefer, or F35 in Gardiner's sign list) means "pleasant, good", which is rather apt for such a good idea. Zero was independently rediscovered in many other cultures.

As a warm-up for later construction efforts, we will start by building the natural numbers, using a simplified version of the Peano axioms (we ignore the axioms for equality, and simply take these as given). The basic idea is to start with zero and get everything else by iteratively adding \(1\). We will use the usual notation \(0\), but to avoid conflict with our informal intuitions, we will add \(1\) using a successor function \[ \mathsf{S}(n) = n+1. \] We need this function to be injective, i.e. different numbers should have different successors: \[ \mathsf{S}(m) = \mathsf{S}(n) \quad \Longrightarrow \quad m = n. \] This means we have a chain of distinct natural numbers \[ 0, \quad \mathsf{S}(0), \quad \mathsf{S} \mathsf{S} (0), \quad \mathsf{S} \mathsf{S} \mathsf{S} (0), \quad \ldots \] To guarantee these are the only natural numbers, we define \(\mathbb{N}\) as the smallest set containing \(0\) and its successors. What does it mean to be the "smallest" set though? This is a technical notion we need to define.

Definition 2.1. Smallest set. Let \(P\) be some property of sets, and write \(P(B)\) if the set \(B\) satisfies \(P\). The set \(A\) is the smallest set satisfying \(P\) just in case:
  1. \(P(A)\), that is, \(A\) enjoys the property.
  2. Any other set satisfying the condition \(P\) also contains \(A\), i.e. \(P(B) \implies A \subseteq B\).

In general, there may be no unique smallest set with some property. For instance, there is no smallest nonempty set of integers. A more subtle issue is that the property may depend on assigning roles. For instance, in constructing the natural numbers, we need to identify an element to play the role of \(0\), and some injective map to act as the successor function. This is the realm of model theory, a rather deep area we will not enter into here. Using Definition 2.1 we can now define the natural numbers.

Axiom 2.2. The set of natural numbers. The natural numbers \(\mathbb{N}\) is the smallest set satisfying the following two axioms:
  1. Zero. Zero is a natural number, \(0 \in \mathbb{N}\).
  2. Successor. The set \(\mathbb{N}\) is closed under an injective successor function, \(\mathrm{S}\).

Now that we have a set, we can define the familiar arithmetical operations of addition and multiplication. Having canonically identified the structure of the set, we can avail ourselves of the Hindu-Arabic numerals and label elements in base \(10\): \[ 0, \quad 1: = \mathsf{S}(0), \quad 2:= \mathsf{S} \mathsf{S} (0), \quad 3:=\mathsf{S} \mathsf{S} \mathsf{S} (0), \quad \ldots \] Addition is defined by its action on \(0\) and successors, and also using the basic properties of commutativity and associativity.

Axiom 2.3. Addition on natural numbers. Addition is a binary operation \(+: \mathbb{N}\times \mathbb{N} \to \mathbb{N}\) defined by the following properties:
  1. Commutative. For any \(m, n \in \mathbb{N}\), \[m + n = n + m.\]
  2. Associative. For any \(\ell, m, n \in \mathbb{N}\), \[\ell + (m+ n) = (\ell + m) + n.\]
  3. Zero. For any \(n \in \mathbb{N}\), \[n + 0 = n.\]
  4. Successor. For any \(n, m \in \mathbb{N}\), \[\mathsf{S}(n) + m = \mathsf{S}(n + m).\]Axiom 2.3.2 follows from the remaining axioms, but we include it for convenience.

Using the axioms for addition, we can prove what is probably the most famous result of mathematics.

Example 2.1. One plus one is two. Technically, we

\begin{align} 1 + 1 & = \mathsf{S}(0) + \mathsf{S}(0) &\\ & = \mathsf{S}(0 + \mathsf{S}(0)) & (2.3.4)\\ & = \mathsf{S}(\mathsf{S}(0) + 0) & (2.3.1)\\ & = \mathsf{S}\mathsf{S}(0) & (2.3.3) \\ & = 2. \end{align}

We define multiplication in a similar way.

Axiom 2.4. Multiplication on natural numbers. Multiplication is a binary operation \(\cdot: \mathbb{N}\times \mathbb{N} \to \mathbb{N}\) defined by the following properties:
  1. Commutative. For any \(m, n \in \mathbb{N}\), \[ m \cdot n = n \cdot m.\]
  2. Associative. For any \(\ell, m, n \in \mathbb{N}\), \[\ell \cdot (m\cdot n) = (\ell \cdot m) \cdot n.\]
  3. Zero. For any \(n \in \mathbb{N}\), \[ n \cdot 0 = 0.\]
  4. Successor. For any \(n, m \in \mathbb{N}\), \[\mathsf{S}(n) \cdot m = (n \cdot m) + m.\]As with multiplication, Axiom 2.4.2 follows from the other.

We use these to prove another basic arithmetic result.

Example 2.2. One times one is one. This is less famous than our previous example, but still worth proving:

\begin{align} 1 \cdot 1 & = \mathsf{S}(0) \cdot \mathsf{S}(0) &\\ & = (0 \cdot \mathsf{S}(0)) + \mathsf{S}(0) & (2.4.4)\\ & = (\mathsf{S}(0)\cdot 0) + \mathsf{S}(0) & (2.4.1)\\ & = 0 + \mathsf{S}(0) & (2.4.3) \\ & = \mathsf{S}(0) & (2.3.1)\\ & = 1. \end{align}

Note that we need to define addition before defining multiplication, since as we can see from Axiom 2.3.4, multiplication is just iterated addition. Similarly, we can iterate multiplication to obtain integral powers (you are invited to figure out the relevant axioms yourself in §2.2.4).

2.2.2 Mathematical induction

Let's revisit Axiom 2.3, which defined the natural numbers as the smallest set containing \(0\) and closed under the successor function. Combined with Definition 2.1, this leads to a very powerful method for proving results about the natural numbers, called mathematical induction. Note that, from now on, we will drop the successor notation and simply write \(\mathsf{S}(n) = n + 1\).

Theorem 2.5. Mathematical induction. Consider a property of natural numbers, \(P(n)\). Suppose the following hold:
  1. Base case. \(P(0)\) is true.
  2. Induction step. If \(P(n)\) is true for any \(n \in \mathbb{N}\), then \(P(n+1)\) is true.
Then \(A = \mathbb{N}\). Note that in step (2), the assumption of \(P(n)\) in order to prove \(P(n+1)\) is called the induction hypothesis.

Proof. Define \(A\) as the set of natural numbers for which \(P(n)\) holds, \(A := \{n\in\mathbb{N}: P(n)\}\). Then the result follows immediately from Axiom 2.2 and the definition of smallest set, applied to \(A\). \(\blacksquare\)

Example 2.3. Suppose we prove the base case for some natural number \(n_0 > 0\), and the induction step \(P(n) \implies P(n+1)\) for all \(n \geq n_0\). (Most often, we use \(n_0 = 1\).) Theorem 2.5 then implies that \(P(n)\) is true for all natural numbers \(n \geq n_0\). The proof is simple: we define a new statement \(P'(n)\), which is true if and only if \(P(n + n_0)\) is true. We then apply Theorem 2.5 to \(P'\).

Mathematical induction is well-suited to proving axiomatic results about the natural numbers.

Theorem 2.6. Associativity of addition. Axiom 2.3.2 follows from the remaining axiom of 2.3.

Proof. The main question is what to induct on; let's try \(\ell\). First, the base case follows from Axiom 2.3.3: \[ 0 + (m + n) = m + n = (0 + m) + n. \] Now for the induction step. We make the induction hypothesis that, for \(\ell \in \mathbb{N}\), \[ \ell + (m + n) = (\ell + m) + n. \tag{2.7.1} \] Consider the successor \(\textsf{S}(\ell)\):

\begin{align} \text{LHS} & = \textsf{S}(\ell) + (m + n) \\ & = \textsf{S}(\ell + (m + n)) & (2.3.4) \\ & = \textsf{S}((\ell + m) + n) & (2.7.1) \\ & = \textsf{S}(\ell + m) + n & (2.3.4) \\ & = (\textsf{S}(\ell) + m) + n & (2.3.4) \end{align}

and we are done. \(\blacksquare\)

Our second illustration is the binomial theorem, a classical result which is a little more involved and requires some new notation. It will prove very useful below, however. First, we recall binomial coefficients and Pascal's triangle from high school combintorics.

Definition 2.7. Binomial coefficients. The number of ways of choosing a subset of \(k\) objects from a set of \(n\) objects is given by the binomial coefficients
\binom{n}{k} := \frac{n!}{k!(n-k)!}, \quad n, k \in \mathbb{N}.
\]These satisfy a recursion relation encoded by Pascal's triangle,
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k},
with boundary values
\binom{n}{0} = \binom{n}{n} = 1.
\]We also set \(\binom{n}{k} = 0\) for \(k < 0\) and \(k > n\).

If you are a bit rusty on Pascal's triangle, a few lines of algebra should suffice to convince you the relation holds. Now we introduce summation notation, and a related notation for products.

Definition 2.8. Summation and product notation. Consider a sequence of numbers \(\{a_0, a_1, \ldots, a_n\}\). We can define an iterated or "big sum" by
\sum_{k=0}^n a_k := a_1 + a_2 + \cdots + a_{n-1} + a_n.
\]More formally, for \(0 < j+1 \leq n\),
\sum_{k=0}^0 a_k := a_0, \quad \sum_{k=0}^{j+1} a_k := \sum_{k=0}^{j} a_k + a_{j+1}.
\]Similarly, we can define the "big product" by
\prod_{k=0}^n a_k := a_1 \cdot a_2 \cdot \cdots \cdot a_{n-1} \cdot a_n.
\]In slightly more formal terms, for \(0 < j+1 \leq n\),
\prod_{k=0}^0 a_k := a_0, \quad \prod_{k=0}^{j+1} a_k := \left(\prod_{k=0}^{j} a_k\right) \cdot a_{j+1}.
\]Finally, big sums (big products) over empty sets are defined to evaluate to \(0\) (respectively \(1\)).

Using our new notation, we can state the binomial theorem, and prove it using induction.

Theorem 2.9. Binomial theorem. For all \(n \in \mathbb{N}\),
(x + y)^n = \sum_{k=0}^n \binom{n}{k}x^k y^{n-k}.
\]Note that we can swap \(x\) and \(y\) in the identity by symmetry.

Proof. Let \(P(n)\) be the property that the following statement is true: \[ (x + y)^n = \sum_{k=0}^n \binom{n}{k}x^k y^{n-k}. \tag{2.9.1} \] Using Theorem 2.5, we need to prove the base case and the induction step. First, the base case: \[ \text{LHS} = (x + y)^0 = 1 = \binom{0}{0}x^0 y^{0-0} = \sum_{k=0}^0 \binom{n}{k}x^k y^{n-k} = \text{RHS}. \] Thus, the base case is true. Now, for the induction step, assume that \(P(n)\) is true: \[ (x + y)^n = \sum_{k=0}^n \binom{n}{k}x^k y^{n-k}. \tag{2.9.2} \] We want to check if \(P(n + 1)\) follows. We start with the LHS of \(P(n + 1)\), and eventually derive the RHS:

\begin{align} \text{LHS} & = (x + y)^{n+1} \\ & = (x + y)^n(x + y) \\ & = \sum_{k=0}^n \binom{n}{k}x^k y^{n-k}(x + y) & (2.9.2) \\ & = \sum_{k=0}^n \binom{n}{k}x^{k+1} y^{n-k} + \sum_{k=0}^n \binom{n}{k}x^k y^{n+1-k} \\ & = \sum_{k=1}^{n+1} \binom{n}{k-1}x^{k} y^{n+1-k} + \sum_{k=0}^n \binom{n}{k}x^k y^{n+1-k} \\ & = \sum_{k=0}^{n+1} \left[\binom{n}{k} + \binom{n}{k-1} \right]x^{k} y^{n+1-k} - \binom{n}{0-1}y^{n+1} - \binom{n}{n+1}x^{n+1} \\ & = \sum_{k=0}^{n+1} \binom{n+1}{k}x^k y^{n+1-k} & (2.7) \\ & = \text{RHS}. \end{align}

Thus, the induction step holds, and the statement is true for all \(n \in\mathbb{N}\) by mathematical induction, Theorem 2.5. \(\blacksquare\)

Corollary 2.10. For \(n \in \mathbb{N}\),
2^n = \sum_{k=0}^n \binom{n}{k}.

Proof. Set \(x = y = 1\) in Theorem 2.9. \(\blacksquare\)

2.2.3 TODO The integers

The natural numbers can be viewed as a semi-infinite chain. Extending the chain in both directions gives the integers \(\mathbb{Z}\). Algebraically, this corresponds to adding negative numbers.

2.2.4 TODO Exercises

  1. Closed forms. Show that, if \(\mathsf{S}^k(0)\) denotes the result of applying the successor function \(k\) times, the following definitions satisfy Axioms 2.3 and 2.4: \[ \mathsf{S}^m(0) + \mathsf{S}^n(0) = \mathsf{S}^{m+n}(0), \quad \mathsf{S}^m(0)\cdot \mathsf{S}^n(0) = \mathsf{S}^{m\cdot n}(0). \] Explain what is unsatisfactory (from an axiomatic standpoint) in such a definition.
  2. Exponentiation. Write a list of axioms for exponentiating natural numbers, \(n^m\). Hint: Two should suffice.
  3. The multiplicative identity. Prove using Axioms 2.3 and 2.4 that \(1 \cdot n = n\).
  4. Associativity of multiplication. Use induction to show that Axiom 2.4.2 follows from the remaining axioms of 2.4. Hint: The proof is similar to Theorem 2.6.
  5. Pascal's triangle. Verify the recursion relation stated in Definition 2.7.
  6. Coloured cows. The following induction argument supposedly shows that all cows are the same colour. We use the result of Example 2.3, with \(n_0 = 1\):
    • Base case. Clearly, a single cow has a single colour.
    • Induction step. Suppose any set of \(n \geq 1\) cows has the same colour. Now consider a set \(A\) of \(n + 1\) cows. Remove one cow, and we have a set \(B\) of \(n\) cows, which are all the same colour. Remove a different cow, and we have a set \(C\) of cows with the same colour which overlaps the first, \(A \cap B \neq \varnothing\). Thus, all cows in the set \(A\) are the same colour!
    • Since the base case and induction step hold, all cows are the same colour by induction. \(\quad \blacksquare\)

    What is wrong with the argument?

  7. !Triangular numbers. Use induction to show that the sum of the first \(n\) squares can be written in closed form: \[ 1 + 2 + 3 + \cdots + n = \sum_{k=1}^n k = \frac{1}{2}n(n+1). \] This is called the \(n\)-th triangular number, since the numbers in the sum may be arranged into a triangle (a fact which yields a different proof). The great German mathematician, Carl Friedrich Gauss (1777–1855), was asked as a schoolboy to add the numbers from \(1\) to \(100\). He flabbergasted his teacher by performing the sum almost instantaneously. His secret was this formula!
  8. !Strong induction and well-ordering.
  9. △Semigroups.

2.3 The rationals


2.3.1 Partitions and equivalence classes

2.4 Fields

2.5 The reals

2.6 Set theory

2.7 ★Metric spaces

2.8 ★Topological spaces

2.9 Exercises

3 Limits

3.1 ★Asymptotic notation

4 Differentiation

4.1 Definition

5 Integration

6 Series

7 References

Author: David Wakeham

Created: 2018-07-04 Wed 22:03

Emacs 25.1.1 (Org mode 8.2.10)