This document serves as my notes for Terence Tao’s Analysis. The book is nice in that it uses the topic as an opportunity to build the foundations of mathematics, and only starts discussing sequences after 100 pages or so! There are no solutions available for the text, so I thought I would provide some along with my own observations so that in the future I can reconstruct the major ideas with brief review.
These notes are not self-contained and are incomplete. The numbers map to corresponding parts of the text. Discussions or results without numbers are my own remarks.
If $n\pp = m\pp$, then we must have $n=m$.
Remark. This axiom is equivalent to the well-ordering principle, which states that every non-empty subset of $\N$ has a least element. We can derive the well-ordering principle with strong induction (which is itself proved in Exercise 2.2.5). First, a lemma.
Lemma. $0$ is the least element of the natural numbers.
Proof. Consider some $n \in \N$ such that $n \leq 0$. By definition of ordering, there is some $a \in \N$ such that $n + a = 0$. But this implies $n=a=0$. (It can be shown by induction that if $x$ is positive and $y$ is a natural number, then $x+y$ is positive.)
For any positive natural number $a$, there exists exactly one natural number $b$ such that $b\pp = a$.
Proofs.
By induction. Let $P(n)$ be the implication that if $n$ is positive, then there is some natural number $b$ such that $b\pp = n$. Then $P(0)$ is vacuously true. Suppose $P(n)$ is true (we state but do not use this inductive hypothesis). By definition, $n$ is the natural number whose successor is $n\pp$. So for $P(n\pp)$ to hold, we need only show that $n$ is the unique predecessor of $n\pp$. But this is true by Axiom 2.4.
By well-ordering (see below). We know by Axiom 2.4 that if $b\pp = a$, then there is no other $c \neq b$ such that $c\pp = a$; we need only prove that such a number $b$ exists for all positive $a$. Let $S$ be the set of positive natural numbers with no predecessors (that is, for $a \in S$, there does not exist a number $b \in \N$ such that $b\pp = a$). There is a least element $x \in S$. […]
Every non-empty subset of the natural numbers has a least element.
Proof. Consider any subset $S \subseteq \N$. Suppose for the sake of contradiction that it does not have a least element; and consider $T := N \setminus S$. Then by the lemma above, $0 \in T$. Now suppose $\{i : 0 \leq i \leq n\} \subseteq T$ for some $n$. Then $n+1$ cannot be in $S$, for otherwise it would be the least element of $S$. So $\{i : 0 \leq i \leq n+1\} \subseteq T$. Then by strong induction, $\N = T$, and $S$ is empty.
Remark. The well-ordering principle implies the principle of induction.
Proof. Consider a proposition $P(n)$ such that $P(0)$ is true and that $P(n)$ implies $P(n\pp)$. Define $S$ as the set $\{k \in \N : P(k) \text{ is false}\}$. Suppose $S$ is nonempty, and let $k’$ be its least element. We know $k’ \neq 0$ because $P(0)$ is true; then by Lemma 2.2.10 (Lemma 2.2.10 was proved using induction (circular); argument works if lemma proved using well-ordering) there exists an $m \in \N$ such that $m\pp = k’$. By minimality, $m \notin S$, which implies $P(m)$ is true; but this would mean $P(m\pp = k’)$ is true, contradicting $k’ \in S$. Therefore $S$ is empty and $P(n)$ is true for all $n \in \N$.
By the induction axiom (2.5), we have $a=0\mathrel{++}$ as our base case. Let $b=0$. Then $a=b\mathrel{++}$, and there cannot be other values of $b$ satisfying $a=b\mathrel{++}$ by Axiom 2.4. Suppose $a=b\mathrel{++}$. Then $a\mathrel{++}=(b\mathrel{++})\mathrel{++}$, and by Axiom 2.4 $b\mathrel{++}$ is the only value whose successor is $a\mathrel{++}$.
Use Lemma 2.2.10.
Suppose for $m \geq m_0$, we have the following implication: If $P(m’)$ is true for $m_0 \leq m’ \lt m$, then $P(m+1)$ is true. (In particular, this implies $P(m_0)$ is true, because in that case the hypothesis is vacuous). Then $P(m)$ is true for all $m \geq m_0$.
Proof. Let $Q(n)$ be the proposition that $P(m)$ is true for $m_0 \leq m \lt n$. ($Q(n)$ is vacuously true for $n \leq m_0$). We show $Q(n)$ holds for all $n$ using induction. $Q(0)$ holds vacuously. Suppose $Q(n)$ holds for some $n$. If $n \lt m_0$, then $Q(n\pp)$ holds vacuously. If $n \geq m_0$, then by the implication, $Q(n\pp)$ is true. Then by induction, $Q(n)$ holds for all $n \in \N$. For any $m \geq m_0$, $P(m)$ is true because $Q(m\pp)$ is true.
If $A$ is a set, then $A$ is also an object.
Two sets $A$ and $B$ are equal, $A = B$, iff every element of $A$ is an element of $B$ and vice versa.
There exists a set $\emptyset$, known as the empty set, which contains no elements, i.e., for every object $x$ we have $x \notin \emptyset$.
If $a$ is an object, then there exists a set $\{a\}$ whose only element is $a$. Furthermore, if $a$ and $b$ are objects, then there exists a set $\{a,b\}$ whose only elements are $a$ and $b$.
Given any two sets $A,B$, there exists a set $A \cup B$, called the union of $A$ and $B$, which consists of all the elements which belong to $A$ or $B$ or both.
Let $A$ be a set, and for each $x \in A$, let $P(x)$ be a property pertaining to $x$ (i.e., $P(x)$ is either a true statement or a false statement). Then there exists a set, called $\{x \in A : P(x) \text{ is true} \}$ (or simply $\{x \in A : P(x) \}$ for short), whose elements are precisely the elements $x$ in $A$ for which $P(x)$ is true.
Remark. Specification allows the construction of subsets.
Let $A$ be a set. For any object $x \in A$, and any object $y$, suppose we have a statement $P(x,y)$ pertaining to $x$ and $y$, such that for each $x \in A$ there is at most one $y$ for which $P(x, y)$ is true. Then there exists a set $\{y : P(x,y) \text{ is true for some } x \in A \}$.
Remark. Replacement allows the construction of sets “related” to an existing set by swapping each element of the set with at most one object. Use it when you need to build sets that are related to existing sets element-wise and are no larger.
There exists a set $\N$, whose elements are called natural numbers, as well as an object $0$ in $\N$, and an object $n\pp$ assigned to every natural number $n \in \N$ such that the Peano axioms hold.
Suppose for every object $x$ we have a property $P(x)$ pertaining to $x$ (so that for every $x$, $P(x)$ is either a true statement or a false statement). Then there exists a set $\{x : P(x) \text{ is true}\}$.
Remark. This axiom allows the creation of sets out of the collection of all objects, rather than out of existing sets as our other axioms do. It implies all the other axioms that construct sets, and so would greatly simplify the foundations of set theory. However it leads to Russell’s paradox. So instead we enforce that we can only build sets from existing sets (via union, specification, replacement, and power set axioms), where sets can only be created directly from objects by the axioms of empty, singleton, pair sets, and infinity.
If $A$ is a non-empty set, then there is at least one element $x$ of $A$ which is either not a set, or is disjoint from $A$.
Remark. This axiom protects sets against bizarre behavior. The intuition is that, in building sets, we should only deal with elements that are lower on the hierarchy of objects (i.e., primitives $ < $ primitive sets $ < $ sets of primitives and primitive sets $ < $ …).
Sets are no longer allowed to contain themselves. To see this, consider a set $S$ such that $S \in S$. By the singleton set axiom, $A := \{S\}$ is a set. By regularity, $S$ must be disjoint from $A$; but $S$ and $A$ both contain $S$ by construction, a contradiction.
Sets $A, B$ cannot contain each other. Suppose $A \in B$ and $B \in A$. Then $C := \{A,B\}$ is a set by pair set axiom. But $C$ meets $A$ and $B$, contradicting regularity.
This axiom is included for completeness but never needed in analysis.
Let $X$ and $Y$ be sets. Then there exists a set, denoted $Y^X$, which consists of all the functions from $X$ to $Y$.
Remark. Given a set $X$, this axiom allows the existence of $\{Y : Y \subseteq X\}$, i.e. the set of all subsets of $X$, which is called the power set of $X$. One can show this by taking $\{0,1\}^X$, then using replacement to get $\{ f^{-1}(\{1\}) : f \in \{0,1\}^X\}$.
Let $A$ be a set, all of whose elements are themselves sets. Then there exists a set $\cup A$ whose elements are precisely those objects which are elements of the elements of $A$.
Remarks.
We can define an ordered $n$-tuple in multiple equivalent ways, e.g.:
A valid definition must obey the major property of ordered $n$-tuples, which is that
\[(x_i) _ {1 \leq i \leq n} = (x’ _ i) _ {1 \leq i \leq n } \iff x_i = x’ _ i \text{ for all } 1 \leq i \leq n \]
If $(X_i) _ { 1 \leq i \leq n }$ is an ordered $n$-tuple of sets, we define their Cartesian product by
\[\prod _ { 1 \leq i \leq n } X _ i := \{ (x_i) _ {1 \leq i \leq n } : x_i \in X_i \text{ for all } 1 \leq i \leq n \} \]
which can be shown to be a set by considering the set of all functions $x : 1 \leq i \leq n \rightarrow \cup _ {1 \leq i \leq n } X _ i$ and restricting them such that $x(i) \in X_i$ for all $1 \leq i \leq n$.
Let $f : \N \times \N \rightarrow \N$ be a function, and let $c$ be a natural number. Show that there exists a function $a : \N \rightarrow \N$ such that \[a(0) = c \] and \[a(n\pp) = f(n, a(n)) \text{ for all } n \in \N, \] and furthermore that this function is unique.
Proof. We show inductively that for every $N \in \N$, there exists a unique function $a_N : \{n \in \N : n \leq N \} \rightarrow \N$ such that $a_N(0) = c$ and $a_N(n\pp) = f(n, a_N(n))$ for all $n \in \N $ such that $n \lt N$.
The conditions hold for base cases $N \in \{0,1\}$. As the inductive hypothesis, assume a unique $a_N$ exists for some $N$ that satisfying $a_N(0) = c$ and $a_N(n\pp) = f(n, a_N(n))$ for all $n \in \N $ such that $n \lt N$. We want to show that a unique function $a _ {N\pp}$ exists satisfying $a _ { N\pp } (0) = c$ and $a _ {N\pp} (n\pp) = f(n, a _ {N\pp} (n))$ for all $n \in \N $ such that $n \lt N\pp$.
We define $a _ {N\pp}(n) := a _ N(n)$ for $n \leq N$ and $a _ {N\pp}(N\pp) := f(N, a _ {N\pp} (N))$. So $a _ {N\pp} (0) = a_N (0) = c$ by the inductive hypothesis. For $n < N\pp$, $a _ {N\pp}(n\pp) = a _ {N} (n\pp) = f(n, a _ N (n)) = f(n, a _ {N\pp} (n)) $. Observe that these conditions completely specify the values of $a _ {N\pp} (n) \text{ for all } n \leq N\pp$, and so $a _ {N\pp} (n)$ must be unique.
Sets $X,Y$ have equal cardinality iff there is a bijection $f: X \rightarrow Y$. A set $X$ has cardinality $n \in \N$ iff there is a bijection between $X$ and $\{i : 1\leq i \leq n \}$.
Lemma 3.6.9. Suppose that $n \geq 1$, and $X$ has cardinality $n$. Then $X$ is non-empty, and if $x$ is any element of $X$, then the set $X - \{x\}$ has cardinality $n - 1$.
Proof. We have a bijection $f$ from $X$ to $\{i \in \N : 1 \leq i \leq n \}$. Define a function $g : X - \{x\} \rightarrow \{ i \in \N : 1 \leq i \leq n - 1 \}$ by the following rule: for any $y \in X - \{x\}$, we define $g(y) := f(y)$ if $f (y) \lt f(x)$, and define $g(y):=f(y) - 1$ if $f(y) \gt f(x)$.
We show $g$ is a bijection. Suppose $g(y) = g(y’)$ for some $y, y’$. Then by definition of $g$, either $f(y) = f(y’)$ or $f(y) - 1 = f(y’) - 1$; in either case $y = y’$ by injectivity of $f$. To show that $g$ is surjective, consider $m \in \{ i \in \N : 1 \leq i \leq n - 1 \}$. If $m < f(x)$, we can consider $y’ \in X$ such that $y’ = f^{-1}(m)$ because $f$ is surjective. Then $g(y’) := f(y’) = m$. If $m \geq f(x)$, consider $y’ = f^{-1}(m + 1)$. Because $m + 1 > f(x)$, we have $g(y’) := f(y’) - 1 = (m+1) - 1 = m$.
Proposition 3.6.8 (Uniqueness of cardinality). Let $X$ be a set with some cardinality $n$. Then $X$ cannot have any other cardinality, i.e., $X$ cannot have cardinality $m$ for any $m \neq n$.
Proof. We induct on $n$. If $n=0$, then $X$ must be empty and cannot have any other cardinality. Now suppose the proposition is proven for some $n$; we now prove it for $n\pp$. Let $X$ have cardinality $n\pp$; and suppose $X$ has some other cardinality $m \neq n$. By Lemma 3.6.9, $X$ is non-empty, and if $x$ is any element of $X$, then $X - \{x\}$ has cardinality $n$ and $m-1$ which implies that $m=n\pp$, a contradiction. This closes the induction.
Exercise 3.6.14 (Cardinal arithmetic).
(c) Let $X$ be a finite set, and let $Y$ be a subset of $X$. Then $Y$ is finite, and $\#(Y) \leq \#(X)$. If in addition $Y \neq X$ (i.e. $Y$ is a proper subset of $X$), then we have $\#(Y) \lt \#(X)$.
Proof. We first prove the proposition $P(n)$ that any subset $S \in 2^{\{i : 1 \leq i \leq n\}}$ is finite with $\#(S) \leq n$ (in addition, $\#(S) \lt n$ if $S \neq \{i : 1 \leq i \leq n\}$). We induct on $n$. $P(0)$ is trivially true. Suppose $P(n)$ is true. To show $P(n\pp)$, observe that $2^{\{i:1\leq i \leq n\}} \subseteq 2^{\{i:1\leq i \leq n\pp\}}$; so if we define $M := 2^{\{i:1\leq i \leq n\pp\}} \setminus 2^{\{i:1\leq i \leq n\}}$, we need only check that any $T \in M$ is finite. By definition of power set, $n\pp \in T$, and $T \setminus \{n\pp\} \in 2^{\{i:1\leq i \leq n\}}$. Letting $S := T \setminus \{n\pp\}$, by the inductive hypothesis we know $S$ is finite; i.e. $S$ has a bijection $f_S$ from $S$ to $\{i : 1 \leq i \leq k_S\}$ for some $k_S \leq n$ (with $k_S \lt n$ if $S \neq \{i : 1 \leq i \leq n\}$). We can then construct a bijection $f_T$ from $T$ to $\{i : 1 \leq i \leq k_S + 1\}$ such that $f_T (m) := f_S (m)$ for $m \in S$ and $f_T (n\pp) := k_S + 1$. So $T$ is finite with cardinality $k_S + 1 \leq n+1$. In addition, if $T \neq \{i: 1 \leq i \leq n+1 \}$, then $S \neq \{i: 1 \leq i \leq n \}$ because $T$ must contain $n\pp$ by construction. By the inductive hypothesis, this implies $k_S \lt n$; therefore $k_S +1 \lt n + 1$. This closes the induction.
Now consider the bijection $f$ from $X$ to $\{i : 1 \leq i \leq n\}$. Then $f(Y) \in 2^{\{i : 1 \leq i \leq n \}}$, and by the proposition above, there is a bijection $g: f(Y) \rightarrow \{i:1\leq i \leq k \}$ for some natural number $k$. Then the existence of the bijection $g \circ f : Y \rightarrow \{i:1\leq i \leq k \}$ implies that $Y$ is finite with cardinality $k$, where $k \leq n$. In addition, if $X \neq Y$, then $k \lt n$.