3 Pure
Number theory and Analysis, topics apparently elevated from immediate application. Pure mathematics. Rigour, maturity and the small print (well behaved, subject to conditions) not urgently required for basic understanding.
Principle reference texts:
A Pythagorean Introduction to Number Theory* Takloo-Bighash (2018)
interestingly motivated
Cambridge (2022/23) courses covered:
- analysis I
3.1 Real Analysis
Following Tao.
3.1.1 Peano Axioms
Defining the set of natural numbers \(\mathbb{N}:={0,1,2,\dots}\).
- \(0\) is a natural number.
- if \(n\) is a natural number, \(n++\) is also a natural number (closure under ++)
- can assign the labels as define \(1:=0++\), \(2:=1++\), …
- \(n++\neq 0\) for any \(n \in \mathbb{N}\).
- if \(n++=m++\) then \(n=m\) (different natural numbers have different successors).
- (induction) Let \(P(n)\) be any property pertaining to a natural number \(n\). Suppose that \(P(0)\) is true, and suppose that whenever \(P(n)\) is true, \(P(n++)\) is also true. Then \(P(n)\) is true for every natural number \(n\).
Can define addition and multiplication recursively:
- define \(0+m:=m\). then define \((n++)+m:=(n+m)++\)
- define \(1 \times m := m\) then define \((n++)\times m := (n \times m) + m\)
As a corollary of addition we have cancellation \(a+b=a+c \implies b=c\), prove by induction, base case \(a=0\).
strong induction: Let \(P(n)\) be any property pertaining to a natural number \(n\). Suppose that whenever \(P(a_0), P(a_0++), \dots P(n)\) are true, \(P(n++)\) is also true. Then \(P(n)\) is true for every natural number \(n>a_0\)
example If all \(c\) cities are each connected by a one-way road, show that there is a route through all cities.
Take a city \(c_0\). Divide other cities into set \(A\): cities to \(c_0\) and set \(B\): cities from \(c_0\). Then there is a route through \(A\) (strong induction), and a route through \(B\). Since all cities are connected, the last city of the \(A\) route connects to \(c_0\) which also connects to the first city of the \(B\) route by construction. \(\qquad\blacksquare\)
3.1.2 Sets
Modern analysis, like most of modern mathematics, is concerned with numbers, sets, and geometry (Tao)
Set axioms (includes redundancy):
We can define equality of sets: \(A=B\) iff \(x \in A \implies x \in B\) and \(y \in B \implies y \in A\).
Then we have (includes redundancy) a set of set axioms:
- If \(A\) is a set, then \(A\) is also an object. It is meaningful to ask if set \(A\) \(\in\) set \(B\).
- (empty set). \(\exists\) a set \(\varnothing\), such that \(\forall x, x \notin \varnothing\).
- single-choice: we can choose an element \(x\) from a non-empty set \(A\)
- finite-choice: we can choose one element \(x_1,\dots,x_n\) from each of non-empty sets \(A_1, \dots , A_n\)
- axiom of choice: choose from infinitely many sets \(A_1,A_2, \dots\)
- (Singleton sets and pair sets). If \(a\) is an object, then there exists a set \({a}\) whose only element is \(a\), i.e., for every object \(y\), \(y \in {a}\) if and only if \(y = a\). Furthermore, if \(a\) and \(b\) are objects, then there exists a set \({a, b}\) whose only elements are \(a\) and \(b\).
- (Pairwise union). Given any two sets \(A\), \(B\), there exists a set \(A \cup B\) such that \(x \in A \cup B \iff (x \in A \, \textrm{or} \,x\in B)\)
Note associative and commutative, \(A \cup (B \cup C)=(A \cup B) \cup C\). - (Axiom of specification). Let \(A\) be a set, and for each \(x \in A\), let \(P(x)\) be a property pertaining to \(x\). Then there exists a set, \(\{x \in A : P(x)\,\, \textrm{is true}\,\,\}\) (or simply \(\{x ∈ A : P(x)\}\), i.e. \(y \in \{ x \in A:P(x) \,\,\textrm{is true}\,\,\} \iff (y \in A \,\,\textrm{and} \,\, P(y) \,\,\textrm{is true}\,\,)\).
Can now define:
- define subset: \(A \subset B := x \in A \implies x \in B\). \(A\) is a proper subset if \(A \neq B\).
- define intersection: \(A \cap B := \{x : x\in A\,\, \textrm{and}\,\, x \in B\}\)
- define difference: \(A - B\) or \(A \backslash B := \{x \in A \,\, \textrm{and}\,\,x \notin B\}\)
With Intersection and Union, sets form a Boolean algebra. Let \(A,B,C\) be subsets of set \(X\):
- (minimal element) \(A \cup \varnothing = A\) and \(A \cap \varnothing = \varnothing\)
- (maximal element) \(A \cup X = X\) and \(A \cap X = A\)
- (identity) \(A \cup A = A\) and \(A \cap A = A\)
- (associativity) \(A \cup (B \cup C)=(A \cup B) \cup C\) and \(A \cap (B \cap C)=(A \cap B) \cap C\)
- (commutativity) \(A \cup B = B \cup A\) and \(A \cap B = B \cap A\)
- (distributivity) \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\) and \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)
- (partition) \(A \cup X \backslash A = X\) and \(A \cap X \backslash A = \varnothing\)
- (De Morgan Laws) \(X\backslash (A \cup B) = (X \backslash A) \cap (X \backslash B)\) and \(X\backslash (A \cap B) = (X \backslash A) \cup (X \backslash B)\)