We clarify some logical operations on statements. If $S_1$ and $S_2$ are two statements, we write $S_1 \implies S_2$ if $S_1$ implies $S_2$. $S_1$ if and only if $S_2$ is denoted by $S_1 \iff S_2$ or iff and means that $S_1 \implies S_2$ and $S_2 \implies S_1$.
Further, $:$ means such that, $\forall$ means for all and $\exists$ means there exists.
1.1 Sets
Definition 1.1 (Set): Sets are defined by their elements $A = \qty{\omega_1, \omega_2, \ldots, \omega_n}$ or upon a certain property $A = \qty{\omega : \omega \text{ has property } \mathcal{P} }$.
Example 1.2 (Empty set): The set which has no elements is called the empty set and denoted with $\varnothing$.
Example 1.3 (Natural numbers): The set which contains the strictly positive integers $1, 2, 3, \ldots$ is denoted with $\mathbb{N}$. If $n \in \mathbb{N}$, then so is $n+1$.
Note that it is a matter of convention whether $0 \in \mathbb{N}$ or not. For us, $0 \in \mathbb{N}$.
Example 1.4 (Integers): The set of integers is denoted with $\mathbb{Z}$ and it can be defined as $\mathbb{Z} = \qty{-n : n \in \mathbb{N}} \cap {0} \cap \mathbb{N}$.
Example 1.5 (Rational numbers): The set of rational numbers is $\mathbb{Q} = \qty{q= \frac{n}{m} : \ n,m \in \mathbb{Z}, \ m \neq 0 }$.
It can be shown that there does not exists $q \in \mathbb{Q}$ such that $q^2 = 2$ showing that $\sqrt{2} \notin \mathbb{Q}$. The same is true for $\pi$ and $e$. These numbers belong to the set of real numbers $\mathbb{R}$.
Definition 1.6 (Cartesian product): Let $A_1, \ldots, A_n$, $n \in \mathbb{N}$, be a family of sets. The cartesian product of $A_1, \ldots, A_n$ is given by
\begin{align*}
& \bigtimes_{i=1}^{n} A_i = A_1 \times \cdots \times A_n \\
=& \qty{\omega = (\omega_1, \ldots , \omega_n) : \omega_i \in A_i, \ i = 1, \ldots, n}
\end{align*}
An element $\omega$ of $A_1 \times \cdots \times A_n$ is referred to as a vector with coordinates $\omega_i \in A_i$, $i = 1, \ldots, n$. If $A_i = A$, $i = 1, \ldots, n$, we write $\bigtimes_{i=1}^{n} A_i = A^n$. The space $\mathbb{R}^k$ is reffered to as the real coordinate space of dimension $k$.
Definition 1.7 (Set operations)
: Let $A$ and $B$ be two sets, then we define the following set operations:
- Equality: $A = B$ iff $A$ and $B$ contain the same elements
- Inclusion: $A \subset B$ iff $\omega \in A$ implies $\omega \in B$
- Intersection: $A \cap B = \qty{\omega : \omega \in A \text{ and } \omega \in B}$
- Union: $A \cup B = \qty{\omega : \omega \in A \text{ or } \omega \in B}$
- Set difference: $A \setminus B = \qty{\omega : \omega \in A \text{ and } \omega \notin B}$
It is often of interest to consider the intersection and union of more than just two sets. Let $\qty{A_i : i \in I}$ be a family of sets, then the intersection of $A_i$, $i \in I$ is defined as the set
\begin{equation}
\bigcap_{i\in I} A_i = \qty{\omega : \qty(\forall i \in I : \omega \in A_i)}
\end{equation}
and the union of $A_i$, $i \in I$ is defined as the set
\begin{equation}
\bigcup_{i\in I} A_i = \qty{\omega : \qty(\exists i \in I : \omega \in A_i)}
\end{equation}
Theorem 1.8 (Properties of set operations)
: Let $A$, $B$ and $C$ be some sets. We note the following properties.
Inclusion:
- $A \subset A$
- $\varnothing \subset A$
- $A \subset B \qand B \subset A \iff A = B$
- $A \subset B \qand B \subset C \implies A \subset C$
Associativity:
- $(A \cup B) \cup C = A \cup (B \cup C)$
- $(A \cap B) \cap C = A \cap (B \cap C)$
Commutativity:
- $A \cup B = B \cup A$
- $A \cap B = B \cap A$
Distributivity:
- $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
- $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
Set difference:
- $C \setminus (A \cap B) = (C \setminus A) \cup (C \setminus B)$
- $C \setminus (A \cup B) = (C \setminus A) \cap (C \setminus B)$
- $(B \setminus A) \cap C = (B \cap C) \setminus A$
- $(B \setminus A) \cup C = (B \cup C) \setminus (A \setminus C)$
Definition 1.9 (Disjoint sets): Let $A$ and $B$ be two sets. $A$ and $B$ are said to be disjoint if $A \cap B = \varnothing$. More generally, a family of sets $\qty{A_i : i \in I}$ is said to be disjoint if $\forall i \neq j : A_i \cap A_j = \varnothing$.
In what follows, it is often the case that a particular set $\Omega$ is given and one only considers subsets $A \subset \Omega$.
Definition 1.10 (Complement): Let $A \subset \Omega$, then the complement of $A$ is $A^{c} = \Omega \setminus A$.
Proposition 1.11 (Properties of complements)
: Let $A$ and $B$ be subsets of $\Omega$, then:
- $A \cup A^{c} = \Omega$
- $A \cap A^{c} = \varnothing$
- $A \setminus B = A \cap B^{c}$
- $\varnothing^{c} = \Omega$
- $\Omega^{c} = \varnothing$
- $(A \subset B) \implies (B^{c} \subset A^{c})$
- $(A^{c})^{c} = A$
Theorem 1.12 (De Morgan's laws): Let $A$ and $B$ be subsets of $\Omega$, then:
\begin{align}
(A \cap B)^{c} = A^{c} \cup B^{c} \\
(A \cup B)^{c} = A^{c} \cap B^{c}
\end{align}
More generally, for an arbitrary family of subsets $\qty{A_i : A_i \subset \Omega, \ i \in I}$ we have:
\begin{align}
\qty(\bigcap_{i \in I} A_i)^{c} = \bigcup_{i \in I} A_i^{c} \\
\qty(\bigcup_{i \in I} A_i)^{c} = \bigcap_{i \in I} A_i^{c}
\end{align}
1.2 Order Structure of the Real Numbers
Definition 1.13 (Intervals)
: Let $a\lt b$, $a,b \in \mathbb{R}$. Then
- $[a,b] = \qty{x \in \mathbb{R} : a \leq x \leq b}$ is called a closed
- $(a,b) = \qty{x \in \mathbb{R}: a \lt x \lt b}$ is called an open
- $[a,b) = \qty{x \in \mathbb{R}: a \leq x \lt b}$ is called a right-open
- $(a,b] = \qty{x \in \mathbb{R}: a \lt x \leq b}$ is called a left-open
interval.
A set $I \subset \mathbb{R}$ is said to be an interval if it is either closed, open, right-open or left-open.
Definition 1.14 (Unbounded intervals)
: Let $a,b \in \mathbb{R}$. The unbounded real intervals are given by the sets
- $[a, \infty) = \qty{x \in \mathbb{R} : a \leq x \lt \infty}$
- $(a, \infty) = \qty{x \in \mathbb{R} : a \lt x \lt \infty}$
- $(\infty, b] = \qty{x \in \mathbb{R} : \infty \lt x \leq b}$
- $(\infty, b) = \qty{x \in \mathbb{R} : \infty \lt x \lt b}$
Definition 1.15 (Upper and lower bound): Let $A \subset \mathbb{R}$. An element $s \in \mathbb{R}$ is called an upper (lower) bound of $A$, if $x \leq s$ ($x \geq s$) for all $x \in A$.
If $A$ has an upper (lower) bound then we say that $A$ is bounded from above (below). If $A$ is bounded from both below and above, $A$ is called bounded.
Definition 1.16 (Supremum)
: Let $A \subset \mathbb{R}$ be a set. An element $s \in \mathbb{R}$ is called supremum of $A$ and we write $s = \sup A$ if $s$ is the smallest upper bound of $A$. That is, the following two items are satisfied:
- $s$ is an upper bound of $A$
- every $s' \lt s$ is not an upper bound of $A$
Example 1.17 (Supremum): Let $A = [0,1)$. We will later prove that $1$ is the smallest upper bound for $A$ and hence $\sup A = 1$. Note that $\sup A \notin A$, i.e. the supremum must not be an element of the set itself.
Definition 1.18 (Infimum)
: Let $A \subset \mathbb{R}$ be a set. An element $s \in \mathbb{R}$ is called infimum of $A$ and we write $s = \inf A$ if $s$ is the greatest lower bound of $A$. That is, the following two items are satisfied:
- $s$ is a lower bound of $A$
- every $s' \gt s$ is not an lower bound of $A$
Example 1.19 (Infimum): Let $A = [0,1)$, then $0$ is the minimum for $A$ and hence $\inf A = 0$.
Proposition 1.20 ($\mathbb{Q}$ is dense in $\mathbb{R}$): For any two real numbers $x_1, x_2 \in \mathbb{R}$, say $x_1 \lt x_2$, there exists a rational number $q \in \mathbb{Q}$ such that $x_1 \lt q \lt x_2$.
Example 1.21 (Proof of $\sup [0,1) = 1$): Suppose there exists a smaller upper bound $s' < 1$. Note that $[0,1) \cap (s',1) = (s',1)$ is not empty as per the aforementioned proposition we can find a $q \in \mathbb{Q} \subset \mathbb{R}$ such that $q \in (s',1)$, hence $s'$ is no lower bound.
Definition 1.22 (Infinity)
: Let $A \subset \mathbb{R}$ such that $A \neq \varnothing$. We define
- $\sup A = \infty$ if $A$ has no upper bound
- $\inf A = -\infty$ if $A$ has no lower bound
Clearly $\mathbb{R}$ is not bounded and hence $\inf \mathbb{R} = -\infty$ and $\sup \mathbb{R} = \infty$. Sometimes it is convenient to adjoin $\mathbb{R}$ with the objects $-\infty$ and $\infty$. We call this the extended real numbers and use the notation $\overline{\mathbb{R}} = \mathbb{R} \cup \qty{-\infty, \infty} = [-\infty, \infty]$.
Proposition 1.23 ($\inf$, $\sup$ of subsets): Let $A, B \subset \mathbb{R}$ be non-empty sets such that $A \subset B$, then $\inf A \geq \inf B$ and $\sup A \leq \sup B$.
Example 1.24 ($\forall \epsilon \gt 0 : a \leq b + \epsilon \implies a \leq b$): Let $a, b \in \mathbb{R}$ and assume that for any $\epsilon \gt 0$ we have $a \leq b + \epsilon$. Let $B = \qty{x+\epsilon: \epsilon \gt 0, \ x \geq b}$ and $A = {x : x\geq a}$. We note that $\inf B = b$ and $\inf A = a$. Clearly, $B \subset A$. By the latter proposition, it follows $\inf A = a \leq b = \inf B$.
Proposition 1.25 (Property of $\inf$, $\sup$)
: Let $A \subset \mathbb{R}$ be a nonempty set. Then, if $A$ is
- bounded from below, for any $\delta \gt 0$ we have $\exists x \in A : x \lt \inf A + \delta$
- bounded from above, for any $\delta \gt 0$ we have $\exists x \in A : x \lt \sup A - \delta$
Proposition 1.26 ($\inf$, $\sup$ of $\varnothing$): We have that $\inf \varnothing = \infty$ and $\sup \varnothing = -\infty$.