Let $\{x_n\}$ be a bounded sequence. Recall that a limit point of $\{x_n\}$ is the limit of some subsequence $\{x_{n_k}\}$ of $\{x_n\}$.

1. Show that if the sequence $\{x_n\}$ converges to $l\in\mathbb{R}$, every subsequence of $\{x_n\}$ also converges to $l$.
2. Show that the following are equivalent.
   • (a) $\{x_n\}$ is convergent.
   • (b) $\limsup x_n = \liminf x_n$.
   • (c) $\{x_n\}$ has a unique limit point.
3. Let $L$ be the set of limit points of ${x_n}$. Show that $\limsup x_n = \sup L$ and $\liminf x_n = \inf L$.

Quotients of sets.

Let $A$ be a set and let $\sim\subset A \times A$. We call $\sim$ a binary relation and write $a \sim b$ for $(a, b)\in \sim$. A subset $S\subset A$ is said to be closed under $\sim$ if whenever $x\sim y$ and one of $x$ and $y$ is in $S$, so is the other.

1. For $a\in A$, show that there is a (unique) set $[a]\subset A$ such that
   • $a$ is closed under $\sim$
   • if $S$ is closed under $\sim$ and $a\in S$ then $[a]\subset S$
2. Show that for $x\in A$, $x\in [a]$ if and only if $[x]=[a]$.
3. Conclude that $\bar{A} = \{S \subset A: \text{$S = [a]$ for some $a\in A$}\}$ is a collection of disjoint sets whose union is $A$.
4. Define the map $q: A\to \bar{A}$ by $q(a) = [a]$. Let $B$ be a set and $f: A \to B$ be a function. Show that the following are equivalent.
   • for all $a, b \in A$, $a\sim b \implies f(a) = f(b)$
   • there is a function $\bar{f} : \bar{A} \to B$ such that $\bar{f} \circ q = f$

1. Write down a formula expressing the statement that the set $S$ is a singleton (i.e., $S$ has exactly one element).
2. Write down a formula expressing the statement that the set $S$ contains $x$ and $y$ but no other elements.
3. Using the axiom of extensionality, show that there is a unique set $S$ that contains $x$ and $y$ but no other elements.
4. Prove Proposition 3.1.28 from the text (Analysis I by Terence Tao).

Assignments can be submitted either handwritten on paper or by e-mail using latex. For e-mail submissions please submit a pdf file with um202 as a word in the subject.

For those of you who want to start using latex (for example to submit assignments), there are two good cloud based latex editors Overleaf and ShareLatex, both with latex documentation (and adequate free plans).

The following problems are from Terence Tao: Analysis I.

1. Exercise 2.2.1
2. Exercise 2.2.2
3. Exercise 2.2.3
4. Exercise 2.2.5
5. Exercise 2.2.6

We see, following the text how to axiomatize the natural numbers and define addition and multiplication from these. We elaborate on only one result, namely one allowing us to make recursive definitions.

Theorem: Let $X$ be a set, let $x_0\in X$ and let $g(n, x)$ be a function $g: \mathbb{N} \times X \to X$. There is a unique function $f: \mathbb{N}\to X$ such that $f(0)= x_0$ and $\forall n \in\mathbb{N}\ f(n++) = g(n, f(n))$.

Proof: The idea is to construct the graph of $f$ as the smallest set containing a specified starting point and closed under a shift.

Let $\mathcal{U} = \{S \subset \mathbb{N}\times X : (0, x_0)\in S,\ (n, x)\in S\Rightarrow (n++, g(n++, x))\in S\}$. Note that $\mathcal{U}$ is non-empty as $\mathbb{N}\times X \in \mathcal{U}$.

Consider the set

$$S_0 = \bigcap\limits_{S \in \mathcal{U}} S$$

It is easy to see that $S_0\in \mathcal{U}$.

Lemma: For every $n\in \mathbb{N}$, there exist a unique $x_n\in X$ such that $(n, x_n) \in S_0$.

Proof: We prove this by induction on $n$. First, let $n=0$. Note that $(0, x_0)\in S$ for all $S\in \mathcal{U}$, and so $(0, x_0) \in S_0$. Now suppose $(0, x_0’)\in S_0$ with $x_0’\neq x_0$. Let $S = \{(n, x) \in S_0: (n, x) \neq (0, x_0’)$. We claim that $S\in \mathcal{U}$.

Firstly, as $(0, x_0) \in S_0$ and $x_0’ \neq x_0$, $(0, x_0)\in S$. Next, suppose $(n, x)\in S \subset S_0$, then $(n++, g(n++, x))\in S_0$. Further, as $n++ \neq 0$, we see that $(n++, g(n++, x)) \neq (0, x_0’)$. Hence $(n++, g(n++, x))\in S$. Thus $S\in \mathcal{U}$.

By definition of $S_0$, as $S\in \mathcal{U}$, $S_0 \subset S$. But $(0, x_0’)$ is in $S_0$ but not $S$, a contradiction. This shows that $x_0\in X$ is the unique point $x \in X$ such that $(0, x)\in S_0$.

The induction step is similar. Assume $(n, x_n)\in S_0$ and this is unique, i.e., $(n, x)\in S_0 \implies x = x_n$. Then $(n, x_n)\in S$ for all $S \in \mathcal{U}$, from which we deduce that $(n++, g(n++, x))\in S_0$. To show uniqueness, suppose $x_{n++}’\in X$ is a point with $(n++, x_{n++}’)\in S_0$ but $x_{n++}’ \neq x_{n++} := g(n++, x)$. Let $S = S_0 \setminus \{(n++, x_{n++}’)\}$. We again show that $S \in \mathcal{U}$ and obtain a contradiction to $S_0 \subset S$.

Namely, as $(0, x_0) \in S_0$ and $n++ \neq 0$, $(0, x_0)\in S$. Next, suppose $(m, x)\in S \subset S_0$, then $(m++, g(m++, x))\in S_0$. If $(m++, g(m++, x)) \notin S$, then we must have $(m++, g(m++, x)) = (n++, x_{n++}’)$. Hence $n = m$, so $x = x_n$. It follows that $x_{n++}’ = g(m++, x) = g(n++, x_n)$, a contradiction. Thus, if $(m, x)\in S$, $(m++, g(m++, x)) \in S$, completing the proof that $S\subset \mathcal{U}$, and contradicting $S_0 \subset S$.

This completes the proof of the lemma.

$$\tag*{$\square$}$$

To prove the theorem, we define the function $f$ by $f(n) = x_n$. As we will see, in terms of set theory the function just corresponds to the set $S_0$. It is straightforward to show by induction than $f$ indeed has the desired properties, and is the unique such function.

$$\tag*{$\square$}$$

Just like a Dictionary, which can define words only in terms of other words, foundations of mathematics cannot be fully self-contained, but must make reference to the external world. This is done through rules governing the foundations. However, what we can, and do, insist on is that the collection of rules is small and clean, so that

• they can be communicated to at least all scientifically literate people, who will all interpret them the same way.
• they can be machine implemented, and we can be convinced that the machine implementation of the rules coincides with our understanding of them.

Such rules are generally specified in terms of a Formal Grammar.

Formal Grammars

A formal grammar has an alphabet $\mathcal{A}$ (mathematically a set), whose elements are letters. This may be finite or infinite, but in the latter case we must have agreement (as above) on what are the letters. Further, these letters can be divided into classes (e.g. variables, constants, paranthesis). We should be able to agree upon and determine when a letter belongs to a given class.

An expression is a finite sequence of letters. We can concatenate two expressions, i.e., write one after the other. In a formal language,

• we define certain distinguished classes of expressions (e.g. Terms, Formulas) by specifying how these can be built by (non-trivial) concatenation from
  • letters in a specific class,
  • specific letters,
  • words in appropriate distinguished classes, including in general the class being defined.
• as words from which a given word is built must be shorter, we can determine when a word belongs to a distinguished class.
• we can more generally pattern match on one or more words: for example, given two words, we can determine whether the two words are of the form $P$ and $P \implies Q$ where $P$ and $Q$ are formulas.

Syntactic foundations of mathematics: First-order logic and Set theory.

As sketched earlier, we can define first-order languages in a formal grammar, with two distinguished classes of expressions - terms and formulas. A theory consists of a first order language together with a collection of formulas, which we call the Axioms of the theory. Typically, we insist that these include a set of logical axioms.

Rules of deduction (inference), i.e., rules telling us how to deduce formulas from other formulas, can be described in terms of pattern matching and concatenation as above. Mathematics has foundations the language and axioms of Set Theory. In principle, any mathematical theorem can be written in this language, and a proof can be written as a sequence of applications of the rules of deduction starting with the axioms of set theory and the logical axioms.

We begin by taking a deeper look at the foundations of natural numbers and their arithmetic. Generally students see the formalization of mathematics, in a tradition going back to Euclid, as beginning with axioms or definitions. So for instance, one of the axioms concerning the natural numbers can be:

$$\forall n\ 0 + n = n.$$

Theorems are the logical consequences of the axioms.

But, for the axiomatic approach to make sense, we first need certain rules. These are purely syntactic in nature.

Language:

Suppose we want to create an alien version of the natural numbers. We could remove some axioms and add new ones. However, we cannot have axioms such as:

$$\forall n\ 0 + n - = \exists \forall.$$ $$3 + (4 - n).$$

Indeed the first is nonsense - it is not a valid mathematical expression. The second is a mathematical expression, but represents a natural number, not an expression that can be true or false. Thus, we need rules for specifying what are valid mathematical expressions, and also which of these represent formulas, i.e., which can be true or false.

Rules of inference:

Once we know what are valid formulas, we can declare some of them to be our axioms, i.e., we declare that they are true. The rules of inference tell us what formulas we can deduce as consequences of others. Thus theorems are consequences of the axioms.

First-Order Logic:

The logic that underlies the usual foundations of mathematics is called Predicate Calculus or first-order logic. The natural numbers can be represented in first-order logic, as we see briefly below. However, the usual way of viewing natural numbers, and everything else, in mathematics is to describe Sets in first order logic and then view natural numbers as corresponding to certain sets.

First-order languages

We have to first describe valid mathematical expressions. In first order logic, these are of two kinds, Terms and Formulas. Terms represent elements in a fixed domain of discourse, such as natural numbers or the collection of all sets, while formulas can be true or false. Both terms and formulas may depend on some variables.

More precisely,

• a first-order language is determined by collections of
  • constants
  • variables (we can assume the variables to always be, say, $x_1$, $x_2$, $x_3$, …)
  • functions - with a specified degree for each function.
  • predicates (relations) - with a specified degree for each predicate.
• Terms are expressions that can be built recursively by:
  • constants and variables are terms.
  • if $f(x_1, \dots, x_n)$ is a function of degree $n$ and $t_1$, …, $t_n$ are terms then $f(t_1, \dots, t_n)$ is a term.
• Formulas are expressions that can be built recursively by:
  • if $p(x_1, \dots, x_n)$ is a predicate of degree $n$ and $t_1$, …, $t_n$ are terms then $p(t_1, \dots, t_n)$ is a formula.
  • If $P$ and $Q$ are formulas, so are $P\wedge Q$, $P \vee Q$, $P \implies Q$, $P\iff Q$ and $\neg P$.
  • If $P$ is a formula and $x$ is a variable, then $\forall x P$ and $\exists x P$ are formulas.

Rules of inference

Some of the most important rules of inference are as below.

Tautologies

Tautologies are formulas built from formula variables $P$, $Q$ etc. (i.e., $P$ , $Q$ are variables representing formulas) which are true for all truth values of the variables. For instance, the statement “P or (not P)” is true if $P$ is true and also if $P$ is false. Similarly, we have the tautology $P \implies (Q \implies P)$.

We can deduce (without any axioms) that any formula obtained by substituting formulas for the formula variables in a tautology is true.

Modus Ponens

The main rule of inference, going back to antiquity, is Modus Ponens: given $P$ and $P \implies Q$, we can deduce $Q$.

Natural numbers in first-order logic

The natural numbers can be described in first-order logic.

• The language of natural numbers has
  • a single constant $0$.
  • a function $S$ (successor) of degree $1$ and functions $+$, $\cdot$ of degree $2$.
  • a predicate $=$ of degree $2$
• Equality is often taken as part of the logic, so in first-order logic with equality, we are assumed to have a predicate $=$ and some axioms
  • $\forall x\ x = x$
  • $\forall x\forall y\ x = y \implies y = x$
  • $\forall x \forall y\forall z\ (x = y)\wedge (y = z) \implies x = z$
• The Peano axioms for natural numbers in first-order logic are
  • $\forall x\ 0 \neq S(x)$
  • $\forall x,y\ S(x) = S(y) \implies x = y$
  • $\forall x\in \mathbb{N} x + 0 = x$
  • $\forall x,y\in \mathbb{N} x + S(y) = S(x + y)$
  • $\forall x\in \mathbb{N} x \cdot 0 = 0$
  • $\forall x,y\in \mathbb{N} x \cdot S(y) = x \cdot y + x$

Natural numbers as sets

We will not pursue in detail the first-order theory of natural numbers, but instead view them as sets. Thus, each natural number is a set, and the set of natural numbers is a set whose elements are sets. Formally, sets are defined as a first-order theory.

The details of axiomatizing natural numbers (as sets), as the details of most of this course, are in Terence Tao’s books Analysis I & II.

This course is a basic introduction to Analysis and related foundations of Mathematics, going beyond and deeper than the first year courses. We will follow Terence Tao’s books Analysis I and (part of) Analysis II. However, the background assumed in those books is less than the first year courses at I.I.Sc., so some parts will be covered rapidly or the treatment in the course will be at a more sophisticated level.

A brief outline of material covered, and occasionally more detailed notes, will be posted in this blog. For timings, syllabus etc please visit the home page.