• direct proof

  Assume $p$ is true, then show that $q$ must also be true.

• proof of contrapositive

  Assume $q$ is false, then show that $p$ must also be false.

• proof by contradiction

  Assume $p$ is true and $q$ is false. Then show that this leads to a contradiction.

a statement is a sentence that is either true or false.

[see the comp182 logic section]

$A \rightarrow B$

• Converse: $B \rightarrow A$
• Contrapositive: $\neg B \rightarrow \neg A$

Disjoined conclusions §

[see the comp182 logic section]

$P \rightarrow (Q \vee R)$

Sets §

[see the comp182 sets section]

Indexed families of sets §

$x \in \bigcup_{n=1}^{\infty} S_n \leftrightarrow \exists n_x \in \mathbb{N} : x \in S_{n_x}$

$x \in \bigcap_{n=1}^{\infty} S_n \leftrightarrow \forall n \in \mathbb{N} : n \in S_{n_x}$

Induction §

[see the comp182 induction section]

Real vs Rational numbers §

Upper and lower bounds §

A number $u \in \mathbb{R}$ is an upper bound of $S$ if for any $x \in S$, $u \geq x$. We say that $S$ is bounded from above.

Supremum: least upper bound.

If $u$ is the supremum of $S$ and $u \in S$, $u$ is the maximum of $S$.

A number $l \in \mathbb{R}$ is a lower bound of $S$ if for any $x \in S$, $l \leq x$. We say that $S$ is bounded from below.

Infimum: greatest lower bound.

If $l$ is the infimum of $S$ and $l \in S$, $l$ is the minimum of $S$.

Let $S \subseteq \mathbb{R}$ and let $u \in \mathbb{R}$ be an upper bound of $S$. $u$ is the supremum of $S$ iff:

• $u$ is the maximum of $S$ or
• for every $\epsilon > 0$ there is an element of $S$ such that $u - \epsilon$ is less than that element

Least upper bound property (aka completeness property): Every non-empty subset of the real numbers that is bounded from above has a least upper bound that is a real number.

Bounded and nested intervals §

Archimedian property: For every real number $x$, there exists a natural number $n_x$ such that $n_x > x$.

Successor axiom: If $n \in \mathbb{N}$, $n + 1$ exists and is a natural number.

A family of sets $S_n$ indexed by the natural numbers is nested iff $S_{n + 1} \subseteq S_n \forall n \in \mathbb{N}$.

Nested intervals property: If $I_n$ is a nested family of non-empty, closed, bounded^[1] intervals in $\mathbb{R}$, then $\bigcap_{n = 1}^\infty I_n$ is non-empty.

Bounded Infinite sets have cluster points §

Neighbourhoods: Given $x \in \mathbb{R}$ and $\epsilon > 0$, the $\epsilon$-neigbourhood is the open interval $(x - \epsilon, x + \epsilon)$.

A real number $x$ ix a cluster point ^[2] of a set $S \subseteq \mathbb{R}$ if $(x - \epsilon, x + \epsilon)$ contains a non-$x$ element of $S$ for all $\epsilon > 0$.

Cluster points of a set need not be elements of the set.

Bolsano-Weierstrass Theorem: Every bounded, infinite set of real numbers has a cluster point.

Functions §

Given sets $X$ and $Y$, a function $f$ from $X$ to $Y$ is denoted $f : X \rightarrow Y$, and it is a relation between $X$ and $Y$ such that every $x \in X$ has exactly one $y \in Y$ such that $f(x) = y$.

$X$ is the domain and $Y$ is the co-domain of $f$.

$f = g$ iff they have the same domain and $f(x) = g(x)$ for all $x$ in their domain.

Let $f: X \rightarrow Y$, and $A \subseteq X$. The restriction of $f$ to $A$ is the function $f_A : A \rightarrow Y$ defined by $f_A(a) = f(a) \forall a \in A$.

Let $f: X \rightarrow Y$ be a function. Given $A \subseteq X$, the image of $A$ under $f$ is the subset $f(a) \subseteq Y$ given by $f(a) = \{y \in Y : \exists a \in A : f(a) = y\}$.

Open sets §

A set $U \subseteq \mathbb{R}$ is open if for every $x \in U$, there exists $\epsilon_x > 0$ such that $(x - \epsilon_x, x + \epsilon_x) \subseteq u$.

The intersection of any finite family of open sets is open.

Closed sets §

A set $F \subseteq \mathbb{R}$ is closed if $F$ contains all of its cluster points.

If a set has no cluster points, it is closed.

• the union of open sets is open
• the intersection of finitely many open sets is open
• the intersection of closed sets is closed
• the union of finitely many closed sets is closed

Continuity §

$f$ is continuous if and only if for every $x_0$ in the domain: for every $\epsilon > 0$, there exists $\delta > 0$ such that for all $x \in \mathbb{R}$, if $|x - x_0| < \delta$, then $|f(x) - f(x_0)| < \epsilon$.

A function $f : \mathbb{R} \rightarrow \mathbb{R}$ is continuous if for every open set $u$ in the codomain of $f$, its pre-image $f^{-1}(u)$ is also open.

Sequences §

a sequence is a function $\mathbb{N} \rightarrow \mathbb{R}$.

a sequence converges to a real number $L$ if for every $\epsilon$-neighbourhood of $L$, the sequence eventually remains in the $\epsilon$-neighbourhood.

$(\forall \epsilon > 0, \exists N_\epsilon \in \mathbb{N} : \forall n \geq N_\epsilon, |x_n - L| < \epsilon) \Leftrightarrow x_n \in (L - \epsilon, L + \epsilon)$

a sequence can have at most one limit.

Squeeze theorem: if $\lim l_n = L$, $\lim u_n = L$, and $l_n \leq x_n \leq u_n$, then $\lim x_n = L$.

• $\lim (x_n + y_n) = \lim x_n + \lim y_n$
• $\lim (c \cdot x_n) = c (\lim x_n)$ for any constant $c$
• $\lim (x_n \cdot y_n) = (\lim x_n) (\lim y_n)$
• $\lim (\frac{x_n}{y_n}) = \frac{\lim x_n}{\lim y_n}$ if $\lim y_n \neq 0$

A real number $L$ is a cluster point of a set $S$ of real numbers iff there exists a sequence of elements of $S$, all different from $L$, that converges to $L$.

A set $F \subseteq \mathbb{R}$ is closed iff for an arbitrary convergent sequence $x_n$ in $F$, the limit $\lim x_n$ is an element of $F$.

A sequence is monotone if it is either weakly increasing, or weakly decreasing.

Every bounded, monotone sequence of real numbers converges.

Given a sequence $(x_n)$, a subsequence is a sequence $(y_n)$ defined by $y_k = x_{n_k}$ for some choice of natural numbers $n_1 < n_2 < \cdots$.

Bolzano-Weierstrass Theorem: Every bounded sequence of real numbers has a convergent subsequence.

A sequence is a cauchy sequence if the terms of the sequence are “eventually” close to each other.

$\forall \epsilon > 0, \exists N \in \mathbb{N} : \forall m, n \geq N, |x_m - x_n| < \epsilon$

A sequence of real numbers is convergent if and only if it is a Cauchy sequence.

A set $S \subseteq \mathbb{R}$ is disconnected if there exist sets $U, V \subseteq S$ such that:

1. $U \cup V = S$
2. $U \neq \varnothing$ and $V \neq \varnothing$
3. $U \cap V = \varnothing$
4. $U$ and $V$ are open in $S$

Given $D \subseteq \mathbb{R}$, if $f : D \rightarrow \mathbb{R}$ is continuous, then the image of any connected set is continuous.

Extreme value theorem: Suppose $f: [a, b] \rightarrow \mathbb{R}$ is continuous. Then $f([a, b]) = \{f(x) : x \in [a, b]\}$ has a maximum and a minimum.

A set $K \subseteq \mathbb{R}$ is compact if it is closed and bounded.

Given $D \subseteq \mathbb{R}$, if $f : D \rightarrow \mathbb{R}$ is continuous, then the image of every compact set is compact.

Covering property (aka Heine-Borel theorem)" $K$ is closed and bounded if and only if every open cover of $K$ has a finite subcover.