Notes on Analysis

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

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

---

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.

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.