2 Preliminaries

Before introducing \(\mathbb{R}\) we want to make sure that we cover all the basics needed for the task.

2.1 Sets

A set is a collection of objects. These objects are called elements of the set. For example in the previous section we mentioned the following sets:

\(\mathbb{N}\) the set of natural numbers
\(\mathbb{Z}\) the set of integers
\(\mathbb{Q}\) the set of rational numbers
\(\mathbb{R}\) the set of real numbers

Definition 1

Let \(A\) be a set.

We write \(x \in A\) if the element \(x\) belongs to the set \(A\).
We write \(x \notin A\) if the element \(x\) does not belong to the set \(A\).

Remark 2

A set can contain all sorts of elements. For example the students in a classroom can be modelled by a set \(S\). The elements of the set are the students. For example

\[ S = \{ \text{Alice, Olivia, Jake, Sahab} \} \]

In this case we have

\[ \text{Alice} \in S \] but instead

\[ \text{Silvio} \notin S \,. \]

2.2 Logic

In this section we introduce some basic logic symbols. Suppose that you are given two statements, say \(\alpha\) and \(\beta\). The formula \[ \alpha \implies \beta \] means that \(\alpha\) implies \(\beta\). In other words, if \(\alpha\) is true then also \(\beta\) is true.
The formula \[ \alpha \impliedby \beta \] means that \(\alpha\) is implied by \(\beta\): if \(\beta\) is true then also \(\alpha\) is true.
When we write \[ \alpha \iff \beta \tag{2.1}\] we mean that \(\alpha\) and \(\beta\) are equivalent. We also say that \(\alpha\) is true if and only if \(\beta\) is true. Note that (2.1) is equivalent to \[ \alpha \implies \beta \,\, \text{ and } \,\, \beta \implies \alpha \,. \]

Example 3

We have that \[ x > 0 \implies x>-100 \,, \] and \[ \text{ contradiction } \impliedby \sqrt{2} \in \mathbb{Q}\,. \] Concerning \(\iff\) we have \[ x^2 < 2 \iff - \sqrt{2} < x < \sqrt{2} \,. \]

We now introduce logic quantifiers. These are

\(\forall\) which reads for all
\(\exists\) which reads exists
\(\exists !\) which reads exists unique
\(\not\exists\) which reads does not exists

These work in the following way. Suppose that you are given a statement \(\alpha(x)\) which depends on the point \(x \in \mathbb{R}\). Then we say

\(\alpha(x)\) is satisfied for all \(x \in A\) with \(A\) some collection of numbers. This translates to the symbols \[ \alpha(x) \, \text{ is true } \, \forall \, x \in A \,, \]
There exists some \(x\) in \(\mathbb{R}\) such that \(\alpha(x)\) is satisfied: in symbols \[ \exists \, x \in \mathbb{R}\, \text{ such that } \, \alpha(x) \, \text{ is true}, \]
There exists a unique \(x_0\) in \(\mathbb{R}\) such that \(\alpha(x)\) is satisfied: in symbols \[ \exists ! \, x_0 \in \mathbb{R}\, \text{ such that } \, \alpha(x_0) \, \text{ is true}, \]
\(\alpha(x)\) is never satisfied: \[ \not\exists \, x \in \mathbb{R}\, \text{ such that } \, \alpha(x) \, \text{ is true}. \]

Example 4

Let us make concrete examples:

The expression \(x^2\) is always non-negative. Thus we can say \[ x^2 \geq 0 \,\, \text{ for all } \,\, x \in \mathbb{R}\,. \]
The equation \(x^2=1\) has two solutions \(x=1\) and \(x=-1\). Therefore we can say \[ \exists \, x \in \mathbb{R}\, \text{such that } \, x^2 = 1 \,. \]
The equation \(x^3=1\) has a unique solution \(x=1\). Thus \[ \exists ! \, x \in \mathbb{R}\, \text{such that } \, x^3 = 1 \,. \]
We know that the equation \(x^2=2\) has no solutions in \(\mathbb{Q}\). Then \[ \not\exists \, x \in \mathbb{Q}\, \text{such that } \, x^2 = 2 \,. \]

2.3 Operations on sets

Definition 5: Inclusion and equality

Given two sets \(A\) and \(B\), we say that \(A\) is contained in \(B\), in symbols \[ A \subseteq B \,, \] if all the elements of \(A\) are also contained in \(B\). Two sets \(A\) and \(B\) are equal, in symbols \[ A=B \,, \] if they contain the same elements.

Remark 6

The inclusion \(A \subseteq B\) is equivalent to the implication: \[ x \in A \,\, \implies \,\, x \in B \] for all \(x \in A\). The symbol \(\implies\) reads implies, and denotes the fact that the first condition implies the second.

Definition 7: Union and Intersection

For two sets \(A\) and \(B\) we define their union as the set \[ A \cup B := \{ x\, \colon \, x \in A \, \text{ or } \, x \in B \} \,. \] The intersection of \(A\) and \(B\) is defined by \[ A \cap B := \{ x\, \colon \, x \in A \, \text{ and } \, x \in B \} \,. \] We denote the empty set by the symbol \(\emptyset\). Two sets are disjoint if \[ A \cap B = \emptyset \,. \]

Example 8

Given two sets \(A\) and \(B\) we always have \[\begin{gather} (A \cap B) \subseteq A \,, \,\, (A \cap B) \subseteq B \,,\\ A \subseteq (A \cup B) \,, \,\, B \subseteq (A \cup B) \,. \end{gather}\]

Example 9

Define the subset of rational numbers \[ S:= \left\{ x \in \mathbb{Q}\, \colon \, 0 < x < \frac52 \right\} \,. \] Then we have \[ \mathbb{N}\cap S = \{1, 2 \} \,. \] We can also define the sets of even and odd numbers by

\[\begin{align} E & := \{ 2n \, \colon \, n \in \mathbb{N}\} \,,\\ O & := \{ 2n+1 \, \colon \, n \in \mathbb{N}\} \,. \end{align}\]

Then we have

\[\begin{align} \mathbb{N}\cap E & = E \,, \,\, \mathbb{N}\cap O = O \,, \\ O \cup E & = \mathbb{N}\,, \,\, O \cap D = \emptyset \,. \end{align}\]

Example 10

The sets \[ A =\{ 1,2,3 \} \,, \quad B= \{ 3 ,1,2\} \] are equal, that is \(A=B\). This is because they contain exactly the same elements: order does not matter when talking about sets.
Consider the sets \[ A =\{ 1,2 \} \,, \quad B = \{ 1, 2 ,5 \} \,. \] Then \(A\) is contained in \(B\), but \(A\) is not equal to \(B\). Therefore we write \(A \subseteq B\) or \(A \neq B\).

The next proposition is very useful when we need to prove that two sets are equal: rather than showing directly that \(A = B\), we can prove that \(A \subseteq B\) and \(B \subseteq A\).

Proposition 11

Let \(A\) and \(B\) be sets. Then \[ A=B \quad \iff \quad A \subseteq B \,\, \text{ and } \,\, B \subseteq A \,. \]

Proof

The proof is almost trivial. However it is a good exercise in basic logic, so let us do it.

First implication \(\implies\):
Suppose that \(A=B\). Let us show that \(A\subseteq B\). Since \(A = B\), this means that all the elements of \(A\) are also contained in \(B\). Therefore if we take \(x \in A\) we have \[ x \in A \,\, \implies \,\, x \in B \,. \] This shows \(A \subseteq B\). The proof of \(B \subseteq A\) is similar.
Second implication \(\impliedby\):
Suppose that \(A \subseteq B\) and \(B \subseteq A\). We need to show \(A=B\), that is, \(A\) and \(B\) have the same elements. To this end let \(x \in A\). Since \(A \subseteq B\) then we have \(x \in B\). Thus \(B\) contains all the elements of \(A\). Since we are also assuming \(B \subseteq A\), this means that \(A\) contains all the elements of \(B\). Hence \(A\) and \(B\) contain the same elements, and \(A=B\).

2.3.1 Infinite union and intersection

Definition 12: Infinite union and intersection

Let \(\Omega\) be a set, and \(A_n \subseteq \Omega\) a family of subsets, where \(n \in \mathbb{N}\).

The infinte union of the \(A_n\) is the set \[ \bigcup_{n \in \mathbb{N}} A_n := \{ x \in \Omega \, \colon \, x \in A_n \,\, \text{ for at least one } \,\, n \in \mathbb{N}\} \,. \]
The infinte intersection of the \(A_n\) is the set \[ \bigcap_{n \in \mathbb{N}} A_n := \{ x \in \Omega \, \colon \, x \in A_n \,\, \text{ for all } \,\, n \in \mathbb{N}\} \,. \]

Example 13

Question. Define \(\Omega:=\mathbb{N}\) and a family \(A_n\) by \[ A_n = \{ n, n+1, n+2, n+3, \ldots \} \,, \quad n \in \mathbb{N}\,. \]

Prove that \[ \bigcup_{n \in \mathbb{N}} A_n = \mathbb{N}\,. \tag{2.2}\]
Prove that \[ \bigcap_{n \in \mathbb{N}} A_n = \emptyset \,. \tag{2.3}\]

Solution.

Assume that \(m \in \cup_n A_n\). Then \(m \in A_n\) for at least one \(n \in \mathbb{N}\). Since \(A_n \subseteq \mathbb{N}\), we conclude that \(m \in \mathbb{N}\). This shows \[ \bigcup_{n \in \mathbb{N}} A_n \subseteq \mathbb{N}\,. \] Conversely, suppose that \(m \in \mathbb{N}\). By definition \(m \in A_m\). Hence there exists at least one index \(n\), \(n=m\) in this case, such that \(m \in A_n\). Then by definition \(m \in \cup_{n \in \mathbb{N}} A_n\), showing that \[ \mathbb{N}\subseteq \bigcup_{n \in \mathbb{N}} A_n \,. \] This proves (2.2).
Suppose that (2.3) is false, i.e., \[ \bigcap_{n \in \mathbb{N}} A_n \neq \emptyset \,. \] This means there exists some \(m \in \mathbb{N}\) such that \(m \in \cap_{n \in \mathbb{N}} A_n\). Hence, by definition, \(m \in A_n\) for all \(n \in \mathbb{N}\). However \(m \notin A_{m+1}\), yielding a contradiction. Thus (2.3) holds.

2.3.2 Complement

Definition 14: Complement

Let \(A,B \subseteq \Omega\). The complement of \(A\) with respect to \(B\) is the set of elements of \(B\) which do not belong to \(A\), that is \[ B \smallsetminus A := \{ x \in \Omega \, \colon \, x \in B \, \text{ and } \, x \notin A \} \,. \] In particular, the complement of \(A\) with respect to \(\Omega\) is denoted by \[ A^c := \Omega \smallsetminus A := \{ x \in \Omega \, \colon \, x \notin A \} \,. \]

Remark 15

Suppose that \(A \subseteq \Omega\). Then \(A\) and \(A^c\) form a partition of \(\Omega\), in the sense that \[ A \cup A^c = \Omega \,\, \text{ and } \,\, A \cap A^c = \emptyset \,. \]

Example 16

Question. Suppose \(A, B \subseteq \Omega\). Prove that \[ A \subseteq B \iff B^c \subseteq A^c \,. \]

Solution. Let us prove the above claim:

First implication \(\implies\):
Suppose that \(A \subseteq B\). We need to show that \(B^c \subseteq A^c\). Hence, assume \(x \in B^c\). By definition this means that \(x \notin B\). Now notice that we cannot have that \(x \in A\). Indeed, assume \(x \in A\). By assumption we have \(A \subseteq B\), hence \(x \in B\). But we had assumed \(x \in B\), contradiction. Therefore it must be that \(x \notin A\). Thus \(B^c \subseteq A^c\).
Second implication \(\impliedby\): Note that, for any set, \[ (A^c)^c = A \,. \] Hence, by the first implication, \[ B^c \subseteq A^c \, \implies \, (A^c)^c \subseteq (B^c)^c \, \implies \, A \subseteq B \,. \]

We conclude by stating the De Morgan’s Laws. The proof will be left as an exercise.

Proposition 17: De Morgan’s Laws

Suppose \(A,B \subseteq \Omega\). Then \[ (A \cap B)^c = A^c \cup B^c \,, \qquad (A \cup B)^c = A^c \cap B^c \,. \]

2.3.3 Power set

Definition 18: Power set

Let \(\Omega\) be a set. The power set of \(\Omega\) is \[ \mathcal{P}(\Omega) := \{ A \, \colon \,A \subseteq \Omega \}\,. \]

Hence, the power set of \(\Omega\) is the set of all subsets of \(\Omega\).

Remark 19

It holds that:

\(\mathcal{P}(\Omega)\) is always non-empty, since we have that \[ \emptyset \in \mathcal{P}(\Omega) \,, \quad \Omega \in \mathcal{P}(\Omega) \,. \]
Given \(A, B \in \mathcal{P}(\Omega)\), then the sets \[ A \cup B, \quad A \cap B ,\quad A^c , \quad B \smallsetminus A \] are all elements of \(\mathcal{P}(\Omega)\).
Suppose \(\Omega\) is discrete and finite, that is, \[ \Omega = \{x_1, \ldots, x_m\} \] for some \(m \in \mathbb{N}\). Then \(\mathcal{P}(\Omega)\) contains \(2^m\) elements.

Indeed, suppose that we want to define a subset \(A \subset \Omega\). Then for each element \(x_i \in \Omega\) there are two choices: either we include \(x_i \in A\), or we do not include \(x_i \in A\). Therefore there are \[ \underbrace{2 \cdot 2 \cdot \ldots \cdot 2 }_{m \, \text{times}} = 2^m \] ways of constructing \(A\). It follows that \(\Omega\) possesses exactly \(2^m\) subsets, so that \(\mathcal{P}(\Omega)\) contains \(2^m\) elements.

Example 20

Question. Compute the power set of \[ \Omega = \{ x, y, z \}\,. \]

Solution. \(\mathcal{P}(\Omega)\) has \(2^3 = 8\), and \[\begin{align*} \mathcal{P}(\Omega) = \{ \emptyset, & \, \{x\} , \, \{y\} , \, \{z\} , \{x,y\} \\ & \{x,z\}, \, \{y,z\} , \, \{x,y,z\} \} \,. \end{align*}\]

2.3.4 Product of sets

Definition 21: Product of sets

Let \(A,B\) be sets. The product of \(A\) and \(B\) is the set of pairs \[ A \times B := \{ (a,b) \, \colon \, a \in A, \, b \in B \} \,. \]

By definition, two elements in \(A \times B\) are the same, in symbols \[ (a, b) = (\tilde{a}, \tilde{b}) \] if and only if they are equal component-by-componenent, that is \[ a=\tilde{a}\,, \qquad b = \tilde{b} \,. \]

2.4 Equivalence relation

Definition 22: Binary relation

Suppose \(A\) is a set. A binary relation \(R\) on \(A\) is a subset \[ R \subseteq A \times A \,. \]

Definition 23: Equivalence relation

A binary relation \(R\) is called an equivalence relation if it satisfies the following properties:

Reflexive: For each \(x \in A\) one has \[ (x,x) \in R \,, \]

This is saying that all the elements in \(A\) must be related to themselves
Symmetric: We have \[ (x,y) \in R \implies (y,x) \in R \]

If \(x\) is related to \(y\), then \(y\) is related to \(x\)
Transitive: We have \[ (x,y) \in R \,, \,\, (y,z) \in R \implies (x,z) \in R \]

If \(x\) is related to \(y\), and \(y\) is related to \(z\), then \(x\) must be related to \(z\)

If \((x,y) \in R\) we write \[ x \sim y \] and we say that \(x\) and \(y\) are equivalent.

Definition 24: Equivalence classes

Suppose \(R\) is an equivalence relation on \(A\). The equivalence class of an element \(x \in A\) is the set \[ [x]:=\{ y \in A \, \colon \, y \sim x \} \,. \] The set of equivalence classes of elements of \(A\) with respect to the equivalence relation \(R\) is denoted by \[ A / R \, := A / \!\sim \, := \,\{ [x] \, \colon \, x \in A \} \,. \]

In order for the definition of \([x]\) to be well-posed we need to check that:

\([x]\) is non-empty.
\([x]\) does not depend on the representative \(x\): we need to check that \[ x \sim y \quad \iff \quad [x] = [y] \]

This is shown in the following proposition.

Proposition 25: Well-posedness of Definition 24

Let \(\sim\) be an equivalence relation on \(A\). Then

For each \(x \in A\) we have \([x] \neq \emptyset\).
For all \(x,y \in A\) it holds \[ x \sim y \quad \iff \quad [x] = [y] \,. \]

Proof

Proof of Point 1: By the reflexive property we have \(x \sim x\). By definition of equivalence class we conclude that \(x \in [x]\). This shows \[ [x] \neq \emptyset \]

Proof of Point 2: We need to prove a double implication. It is convenient to divide the proof into two parts.

Part 1: \(\,\, x \sim y \implies [x] = [y]\).

Assume \(x \sim y\). By the definition of an equivalence class \[ [x] = \{z \in A \mid z \sim x\} \] is the set of all elements in \(A\) that are related to \(x\). Similarly, \[ [y] = \{z \in A \mid z \sim y \} \,. \] We need to show that \[ [x] = [y] \,, \] meaning that every element in \([x]\) is also in \([y]\), and vice versa.

First, take an arbitrary element \(z \in [x]\).
- By definition, \(z \sim x\).
- Since \(\sim\) is an equivalence relation, it satisfies the transitive property.
- Therefore, from \(z \sim x\) and \(x \sim y\), we can conclude that \(z \sim y\)
- Hence, \(z \in [y]\).
- This shows that \([x] \subseteq [y]\).
Now, take an arbitrary element \(z \in [y]\).
- By definition, \(z \sim y\).
- Since \(\sim\) is an equivalence relation, it satisfies the symmetric property.
- Therefore, from \(x \sim y\), we also have \(y \sim x\).
- By the transitive property, from \(z \sim y\) and \(y \sim x\), we can conclude that \(z \sim x\).
- Hence, \(z \in [x]\).
- This shows that \([y] \subseteq [x]\).

Since \([x] \subseteq [y]\) and \([y] \subseteq [x]\), it follows that \([x] = [y]\), as required. Thus, we have shown that \(x \sim y \implies [x] = [y]\).

Part 2: \(\,\, [x] = [y] \implies x \sim y\).

Assume \([x] = [y]\). This means that the equivalence classes of \(x\) and \(y\) are the same.

By point (i) in the Proposition, we have \(x \in [x]\) and \(y \in [y]\).
Since \([x] = [y]\), we have \(x \in [y]\).
By the definition of \([y]\), this means \(x \sim y\).

Thus, we have shown that \([x] = [y] \implies x \sim y\).

Conclusion: Since we have proven both directions:

\(x \sim y \implies [x] = [y]\)
\([x] = [y] \implies x \sim y\)

we conclude that \[ x \sim y \iff [x] = [y] \,. \] This completes the proof.

The prototypical (and trivial) example of equivalence relation is the equality over \(\mathbb{Q}\).

Example 26: Equality is an equivalence relation

Question. The equality defines a binary relation on \(\mathbb{Q}\times \mathbb{Q}\), via \[ R:=\{ (x,y) \in \mathbb{Q}\times \mathbb{Q}\, \colon \, x=y \} \,. \]

Prove that \(R\) is an equivalence relation.
Prove that \([x] = \{x\}\) and compute \(\mathbb{Q}/ R\).

Solution.

We need to check that \(R\) satisfies the 3 properties of an equivalence relation:
- Reflexive: It holds, since \(x=x\) for all \(x \in \mathbb{Q}\),
- Symmetric: Again \(x = y\) if and only if \(y = x\),
- Transitive: If \(x = y\) and \(y = z\) then \(x = z\).
Therefore, \(R\) is an equivalence relation.
The class of equivalence of \(x \in \mathbb{Q}\) is given by \[ [x] = \{ x \}\,, \] that is, this relation is quite trivial, given that each element of \(\mathbb{Q}\) can only be related to itself. The quotient space is then \[ \mathbb{Q}/ R = \{ [x] \, \colon \,x \in \mathbb{Q}\} = \{ \{ x\} \, \colon \,x \in \mathbb{Q}\} \,. \]

We now give an example of a non-trivial equivalence relation over \(\mathbb{Q}\).

Example 27

Question. Let \(R\) be the binary relation on the set \(\mathbb{Q}\) of rational numbers defined by \[ x \sim y \iff x-y \in \mathbb{Z}\,. \]

Prove that \(R\) is an equivalence relation on \(\mathbb{Q}\).
Compute \([x]\) for each \(x \in \mathbb{Q}\).
Compute \(\mathbb{Q}/R\).

Solution.

We have:
- Reflexive: Let \(x \in \mathbb{Q}\). Then \(x-x = 0\) and \(0 \in \mathbb{Z}\). Thus \(x \sim x\).
- Symmetric: If \(x \sim y\) then \(x-y \in \mathbb{Z}\). But then also
  \[ -(x-y) = y - x \in \mathbb{Z} \] and so \(y \sim x\).
- Transitive: Suppose \(x \sim y\) and \(y \sim z\). Then \[ x - y \in \mathbb{Z}\, \text{ and } \, y - z \in \mathbb{Z}\,. \] Thus, we have \[ x-z = (x-y) + (y-z) \in \mathbb{Z} \] showing that \(x \sim z\).
Thus, we have shown that \(R\) is an equivalence relation on \(\mathbb{Q}\).
Note that \[ x \sim y \quad \iff \quad \exists \, n \in \mathbb{Z}\, \text{ s.t. } \, y = x + n \,. \] Therefore the equivalence classes with respect to \(\sim\) are \[ [x] = \{ x + n \ \colon \ n \in \mathbb{Z}\} \,. \] Each equivalence class has exactly one element in \([0,1) \cap \mathbb{Q}\), meaning that: \[ \forall x \in \mathbb{Q}\,, \,\, \exists! \, q \in \mathbb{Q}\, \text{ s.t. } \, 0 \leq q < 1 \, \text{ and } \, q \in [x]\,. \tag{2.4}\] Condition (2.4) is illustrated in Figure 2.1. Indeed: take \(x \in \mathbb{Q}\) arbitrary. Then \(x \in [n,n+1)\) for some \(n \in \mathbb{Z}\). Setting \(q:=x-n\) we obtain that \[ x = q + n \,, \qquad q \in [0,1) \,, \] proving (2.4). In particular (2.4) implies that for each \(x \in \mathbb{Q}\) there exists \(q \in [0,1) \cap \mathbb{Q}\) such that \[ [x] = [q] \,. \]
From Point 2 we conclude that \[ \mathbb{Q}/ R = \{ [x] \, \colon \,x \in \mathbb{Q}\} = \{ q \in \mathbb{Q}\, \colon \,0 \leq q <1 \} \,. \]

Figure 2.1: For each \(x \in \mathbb{Q}\) there exist unique \(q \in [0,1) \cap \mathbb{Q}\) such that \(x = q + n\). In particular \([x] = [q]\).

2.5 Order relation

Order relations are defined similarly to equivalence relations. However notice that symmetry is replaced by antisymmetry.

Definition 28: Partial order

A binary relation \(R\) on \(A\) is called a partial order if it satisfies the following properties:

Reflexive: For each \(x \in A\) one has \[ (x,x) \in R \,, \]
Antisymmetric: We have \[ (x,y) \in R \, \text{ and } \, (y,x) \in R \implies x = y \]
Transitive: We have \[ (x,y) \in R \,, \,\, (y,z) \in R \implies (x,z) \in R \]

Remark 29

Notice that conditions 1 and 3 are the same for equivalence and order relations. Instead condition 2 changes: it is symmetry for equivalence relation, and antisymmetry for order relations.

We say that a partial order is total if all the elements in the set are related.

Definition 30: Total order

A binary relation \(R\) on \(A\) is called a total order relation if it satisfies the following properties:

Partial order: \(R\) is a partial order on \(A\).
Total: For each \(x,y \in A\) we have \[ (x, y) \in R \,\, \mbox{ or } \,\, (y,x) \in R \,. \]

The operation of set inclusion is a partial order on \(P(\Omega)\) but not a total order.

Example 31: Set inclusion is a partial order but not total order

Question. Let \(\Omega\) be a non-empty set and consider its power set \[ \mathcal{P}(\Omega) = \{ A \, \colon \,A \subseteq \Omega \}\,. \] The inclusion defines binary relation on \(\mathcal{P}(\Omega) \times \mathcal{P}(\Omega)\), via \[ R:=\{ (A,B) \in \mathcal{P}(\Omega) \times \mathcal{P}(\Omega) \, \colon \, A \subseteq B \} \,. \]

Prove that \(R\) is an order relation.
Prove that \(R\) is not a total order.

Solution.

Check that \(R\) is a partial order relation on \(\mathcal{P}(\Omega)\):
- Reflexive: It holds, since \(A \subseteq A\) for all \(A \in \mathcal{P}(\Omega)\).
- Antisymmetric: If \(A \subseteq B\) and \(B \subseteq A\), then \(A=B\).
- Transitive: If \(A \subseteq B\) and \(B \subseteq C\), then, by definition of inclusion, \(A \subseteq C\).
In general, \(R\) is not a total order. For example consider \[ \Omega = \{x, y\}\,. \] Thus \[ \mathcal{P}(\Omega) = \{ \emptyset , \, \{x\} , \, \{y\} , \, \{x,y\} \}\,. \] If we pick \(A=\{x\}\) and \(B=\{y\}\) then \(A \cap B = \emptyset\), meaning that \[ A \not\subseteq B \,, \quad B \not\subseteq A \,. \] This shows \(R\) is not a total order.

The inequality on \(\mathbb{Q}\) is an example of total order.

Example 32: Inequality is a total order

Question. Consider the binary relation induced by the inequality on \(\mathbb{Q}\times \mathbb{Q}\): \[ R:=\{ (x,y) \in \mathbb{Q}\times \mathbb{Q}\, \colon \, x \leq y \} \,. \] Prove that \(R\) is a total order relation.

Solution. We need to check that:

Reflexive: It holds, since \(x \leq x\) for all \(x \in \mathbb{Q}\),
Antisymmetric: If \(x \leq y\) and \(y \leq x\) then \(x = y\).
Transitive: If \(x \leq y\) and \(y \leq z\) then \(x \leq z\).

Finally, we halso have that \(R\) is a total order on \(\mathbb{Q}\), since for all \(x,y \in \mathbb{Q}\) we have \[ x \leq y \,\, \text{ or } \,\, y \leq x \,. \]

Notation 33

If \(A\) is a set and \(R\) is a total order on \(A\), we write \[ (x,y) \in R \, \iff \, x \leq y \,. \] Therefore the symbol \(\leq\) will always denote a total order relation.

2.6 Intervals

In this section we assume to have available the set \(\mathbb{R}\) of real numbers, which we recall is an extension of \(\mathbb{Q}\). We now introduce the concept of interval.

Definition 34

Let \(a,b \in \mathbb{R}\) with \(a<b\). We define the open interval \((a,b)\) as the set \[ (a,b) := \{ x \in \mathbb{R}\, \colon \, a < x < b \}\,. \] We define the close interval \([a,b]\) as the set \[ [a,b] := \{ x \in \mathbb{R}\, \colon \, a \leq x \leq b \}\,. \]

In general we also define the intervals \[\begin{align} [a,b) & := \{ x \in \mathbb{R}\, \colon \, a \leq x < b \}\,, \\ (a,b] & := \{ x \in \mathbb{R}\, \colon \, a \leq x \leq b \}\,, \\ (a, \infty) & := \{ x \in \mathbb{R}\, \colon \, x > a \}\,, \\ [a, \infty) & := \{ x \in \mathbb{R}\, \colon \, x \geq a \}\,, \\ (-\infty, b) & := \{ x \in \mathbb{R}\, \colon \, x < b \}\,, \\ (-\infty, b] & := \{ x \in \mathbb{R}\, \colon \, x \leq b \}\,. \end{align}\]

Some of the above intervals are depicted in Figure 2.2, Figure 2.3, Figure 2.4, Figure 2.5 below.

2.7 Functions

Definition 35: Functions

Let \(A\) and \(B\) be sets. A function from \(A\) to \(B\) is a rule which associates at each element \(x \in A\) a single element \(y \in B\). Notations:

We write \[ f \ \colon A \to B \] to indicate such rule,
For \(x \in A\), we denote by \[ y:=f(x) \in B \] the element associated with \(x\) by \(f\).
We will often denote the map \(f\) also by \[ x \mapsto f(x) \,. \]

In addition:

The set \(A\) is called the domain of \(f\),
The range or image of \(f\) is the set \[ f(A) := \{ y \in B \, \colon \,y = f(x) \, \mbox{ for some }\, x \in A \} \subseteq B \,. \]

Warning

We want to stress the importance of the first two sentences in Definition 35. Assume that \(f \colon A \to B\) is a function. Then:

To each element \(x \in A\) we can only associate one element \(f(x) \in B\),
Every element \(x \in A\) has to be associated to an element \(f(x) \in B\).

Example 36

Assume given the two sets \[ A = \{ a_1,a_2 \} \,, \quad B=\{b_1,b_2,b_3\} \,. \] Let us see a few examples:

Define \(f \ \colon A \to B\) by setting \[ f(a_1) = b_1 \,, \quad f(a_2) = b_1 \,. \] In this way \(f\) is a function, with domain \(A\) and range \[ f(A) = \{ b_1 \} \subseteq B \,. \]
Define \(g \ \colon A \to B\) by setting \[ g(a_1) = b_2 \,, \quad g(a_1) = b_3 \,, \quad g(a_2) = b_3 \] Then \(g\) is NOT a function, since the element \(a_1\) has two elements associated.
Define \(h \ \colon A \to B\) by setting \[ h(a_1) = b_1 \,. \] Then \(g\) is NOT a function, since the element \(a_2\) has no element associated.

Example 37

Let us make two examples of functions on \(\mathbb{R}\):

Define \(f \ \colon \mathbb{R}\to \mathbb{R}\) by \[ f(x)=x^2 \,. \] Note that the domain of \(f\) is given by \(\mathbb{R}\), while the range is \[ f(\mathbb{R}) = [0,\infty)\,. \]
Define \(g \ \colon \mathbb{R}\to \mathbb{R}\) as the logarithm: \[ g(x) = \log (x) \,. \] This time the domain is \((0,\infty)\), while the range is \(g(\mathbb{R})=\mathbb{R}\).

2.8 Absolute value or Modulus

In this section we assume to have available the set \(\mathbb{R}\) of real numbers, which we recall is an extension of \(\mathbb{Q}\).

Definition 38: Absolute value

Let \(x \in \mathbb{R}\). The absolute value of \(x\) is \[ |x| = \begin{cases} x & \text{ if } \, x \geq 0 \\ -x & \text{ if } \, x < 0 \end{cases} \]

Example 39

By definition one has \(|x|=x\) if \(x \geq 0\). For example \[ |\pi| = \pi \,, \,\, \left|\sqrt{2}\right| = \sqrt{2} \,, \,\, |0|=0 \,. \] Instead \(|x|= -x\) if \(x < 0\). For example \[ |-\pi| = \pi \,, \,\, \left|-\sqrt{2}\right| = \sqrt{2} \,, \,\, |-10|=10 \,. \]

Let us highlight some basic properties of the absolute value.

Proposition 40: Properties of absolute value

For all \(x \in \mathbb{R}\) they hold:

\(|x| \geq 0\).
\(|x| = 0\) if and only if \(x = 0\).
\(|x| = |-x|\).

We can use the definition of absolute value to define the absolute value function. This is the function \[ f \ \colon \mathbb{R}\to \mathbb{R}\,, \quad f(x):=|x| \,. \] You might be familiar with the graph associated to \(f\), as seen below.

Plot of the absolute value function \(f(x)=|x|\)

It is also useful to understand the absolute value in a geometric way.

Remark 41: Geometric interpretation of \(|x|\)

A number \(x \in \mathbb{R}\) can be represented with a point on the real line \(\mathbb{R}\).The non-negative number \(|x|\) represents the distance of \(x\) from the origin \(0\). Notice that this works for both positive and negative numbers \(x_1\) and \(x_2\) respectively, as shown in Figure 2.6 below.

Figure 2.6: Geometric interpretation of \(|x|\)

Remark 42: Geometric interpretation of \(|x-y|\)

If \(x,y \in \mathbb{R}\) then the number \(|x-y|\) represents the distance between \(x\) and \(y\) on the real line, as shown in Figure 2.7 below. Note that by Point 3 in Proposition 40 we have \[ |x-y| = |y-x| \,. \]

Figure 2.7: Geometric interpretation of \(|x-y|\)

In the next Lemma we show a fundamental equivalence regarding the absolute value.

Lemma 43

Let \(x,y \in \mathbb{R}\). Then \[ |x| \leq y \iff -y \leq x \leq y \,. \]

The geometric meaning of the above statement is clear: the distance of \(x\) from the origin is less than \(y\), in formulae \[ |x| \leq y\,, \] if and only if \(x\) belongs to the interval \([-y,y]\), in formulae \[ -y \leq x \leq y \,. \] A sketch of this explanation is seen in Figure 2.8 below.

Figure 2.8: Geometric meaning of Lemma 24

Proof: Proof of Lemma 24

Step 1: First implication.
Suppose first that \[ |x| \leq y \,. \tag{2.5}\] Recalling that the absolute value is non-negative, from (2.5) we deduce that \(0 \leq |x| \leq y\). In particular it holds \[ y \geq 0 \,. \tag{2.6}\] We make separate arguments for the cases \(x \geq 0\) and \(x<0\):

Case 1: \(x \geq 0\). From (2.5), (2.6) and from \(x \geq 0\) we have \[ -y \leq 0 \leq x = |x| \leq y \] which shows \[ -y \leq x \leq y \,. \]
Case 2: \(x < 0\). From (2.5), (2.6) and from \(x < 0\) we have \[ -y \leq 0 < - x = |x| \leq y \] which shows \[ -y \leq - x \leq y \,. \] Multiplying the above inequalities by \(-1\) yields \[ -y \leq x \leq y \,. \]

Step 2: Second implication.
Suppose now that
\[ -y \leq x \leq y \,. \tag{2.7}\] We make separate arguments for the cases \(x \geq 0\) and \(x<0\):

Case 1: \(x \geq 0\). Since \(x \geq 0\), from (2.7) we get \[ |x| = x \leq y \] showing that \[ |x| \leq y \,. \]
Case 2: \(x < 0\). Since \(x < 0\), from (2.7) we have \[ -y \leq x = - |x| \,. \] Multiplying the above inequality by \(-1\) yields \[ |x| \leq y \,. \]

With the same arguments, just replacing \(\leq\) with \(<\), one can also show the following.

Corollary 44

Let \(x,y \in \mathbb{R}\). Then \[ |x| < y \iff -y < x < y \,. \]

2.9 Triangle inequality

The triangle inequality relates the absolute value to the sum operation. It is a very important inequality, which we will use a lot in the future.

Theorem 45: Triangle inequality

For every \(x, y \in \mathbb{R}\) we have \[ | |x| - |y| | \leq |x+y| \leq |x| + |y| \,. \tag{2.8}\]

Before proceeding with the proof, let us discuss the geometric meaning of the triangle inequality.

Remark 46: Geometric meaning of triangle inequality

The notion of absolute value can be extended also to vectors in the plane. Suppose that \(x\) and \(y\) are two vectors in the plane, as in Figure 2.9 below. Then \(|x|\) and \(|y|\) can be interpreted as the lengths of these vectors.
Using the rule of sum of vectors, we can draw \(x+y\), as shown in Figure 2.10 below. From the picture it is evident that \[ |x+y| \leq |x| + |y|\,, \tag{2.9}\] that is, the length of each side of a triangle does not exceed the sum of the lengths of the two remaining sides. Note that (2.9) is exactly the second inequality in (2.8). This is why (2.8) is called triangle inequality.

Figure 2.10: Summing the vectors \(x\) and \(y\). The triangle inequality relates the length of \(x+y\) to the length of \(x\) and \(y\)

Proof: Proof of Theorem 46

Assume that \(x,y \in \mathbb{R}\). We prove the two inequalities in (2.8) individually.

Step 1. Proof of the second inequality in (2.8).
Trivially we have \[ |x| \leq |x| \,. \] Therefore we can apply Lemma 24 and infer \[ -|x| \leq x \leq |x| \,. \tag{2.10}\] Similarly we have that \(|y| \leq |y|\), and so Lemma 24 implies \[ -|y| \leq y \leq |y| \,. \tag{2.11}\] Summing (2.10) and (2.11) we get \[ -(|x| + |y|) \leq x + y \leq |x| + |y| \,. \] We can now again apply Lemma 24 to get \[ |x + y| \leq |x| + |y| \,, \tag{2.12}\] which is the second inequality in (2.8).

Step 2. Proof of the first inequality in (2.8).
Note that the trivial identity \[ x = x+y - y \] always holds. We then have \[\begin{align} |x| & = |x+y - y| \\ & = |(x+y) + (-y)| \\ & = |a+b| \end{align}\] with \(a=x+y\) and \(b=-y\). We can now apply (2.12) to \(a\) and \(b\) to obtain \[\begin{align} |x| & = |a+b| \\ & \leq |a| + |b| \\ & = |x+y| + |-y| \\ & = |x+y| + |y| \end{align}\] Therefore \[ |x| - |y| \leq |x+y| \,. \tag{2.13}\] We can now swap \(x\) and \(y\) in (2.13) to get \[ |y| - |x| \leq |x+y| \,. \] By rearranging the above inequality we obtain \[ -|x+y| \leq |x| - |y| \,. \tag{2.14}\] Putting together (2.13) and (2.14) yields \[ -|x+y| \leq |x| - |y| \leq |x+y| \,. \] By Lemma 24 the above is equivalent to \[ ||x| - |y|| \leq |x+y| \,, \] which is the first inequality in (2.8).

An immediate consequence of the triangle inequality are the following inequalities, which are left as an exercise.

Proposition 47

For any \(x,y \in \mathbb{R}\) it holds \[ ||x|-|y|| \leq |x-y| \leq |x|+|y|\,. \tag{2.15}\] Moreover for any \(x,y,z \in \mathbb{R}\) it holds \[ |x-y| \leq |x-z| + |z-y| \,. \]

Notice that the inequality in (2.15) differs from the triangle inequality (2.8) by a sign. Indeed it can be shown tha (2.8) and (2.15) are equivalent.

2.10 Proofs in Mathematics

In a mathematical proof one needs to show that \[ \alpha \implies \beta \tag{2.16}\] where

\(\alpha\) is a given set of assumptions, or Hypothesis
\(\beta\) is a conclusion, or Thesis

Proving (2.16) means convincing ourselves that \(\beta\) follows from \(\alpha\). Common strategies to prove (2.16) are:

Contradiction: Assume that the thesis is false, and hope to reach a contradiction: that is, prove that \[ \neg \beta \implies \, \mbox{ contradiction} \] where \(\neg \beta\) is the negation of \(\beta\).

For example we already proved by contradiction that \[ \mbox{Definition of } \mathbb{Q}\, \implies \, \sqrt{2} \notin \mathbb{Q}\,, \] In the above statement \[ \alpha = \left( \mbox{Definition of } \mathbb{Q}\right) \,. \] \[ \beta = \left( \sqrt{2} \notin \mathbb{Q}\right) \,. \] Therefore \[ \neg \beta = \left( \sqrt{2} \in \mathbb{Q}\right) \,. \]
Direct: Sometimes proofs will also need direct arguments, meaning that one need to show directly that (2.16) holds.
Contrapositive: The statement (2.16) is equivalent to \[ \neg \beta \, \implies \, \neg \alpha \,. \tag{2.17}\] Thus, instead of proving (2.16), one could show (2.17). The statement (2.17) is called the contrapositive of (2.16).

Let us make an example.

Proposition 48

Two real numbers \(a,b\) are equal if and only if for every real number \(\varepsilon>0\) it follows that \(|a-b|<\varepsilon\).

Before proceeding with the proof, note that the above stetement is just saying that:

Two numbers are equal if and only if they are arbitrarily close

By arbitrarily close we mean that they are as close as you want the to be.

Proof: of Proposition 38

Let us first rephrase the statement using mathematical symbols:

Let \(a, b \in \mathbb{R}\). Then it holds: \[ a=b \, \iff \, |a-b| < \varepsilon\,, \,\, \forall \, \varepsilon>0 \,. \]

Setting \[\begin{align} \alpha & = \left( a=b \right) \\ \beta & = \left( |a-b| < \varepsilon\,, \,\, \forall \, \varepsilon>0 \right) \end{align}\] the statement is equivalent to \[ \alpha \iff \beta \,. \] To show the above, it is sufficient to show that \[ \alpha \implies \beta \quad \mbox{ and } \quad \beta \implies \alpha \,. \]

Step 1. Proof that \(\alpha \implies \beta\).
This proof can be carried out by a direct argument. Since we are assuming \(\alpha\), this means \[ a=b \,. \] We want to see that \(\beta\) holds. Therefore fix an arbitrary \(\varepsilon>0\). This means that \(\varepsilon\) can be any positive number, as long as you fix it. Clearly \[ |a-b| = |0| = 0 < \varepsilon \] since \(a=b\), \(|0|=0\), and \(\varepsilon>0\). The above shows that \[ |a-b| < \varepsilon\,. \] As \(\varepsilon>0\) was arbitrary, we have just proven that \[ |a-b| < \varepsilon\,, \,\, \forall \, \varepsilon>0 \,, \] meaning that \(\beta\) holds and the proof is concluded.

Step 2. Proof that \(\beta \implies \alpha\).
Let us prove this implication by showing the contrapositive \[ \neg \alpha \implies \neg\beta \,. \] So let us assume \(\neg \alpha\) is true. This means that \[ a \neq b \,. \] We have to see that \(\neg \beta\) holds. But \(\neg \beta\) means that \[ \exists \, \varepsilon_0> 0 \, \text{ s.t. } \, |a-b| \geq \varepsilon_0 \,. \] The above is satisfied by choosing \[ \varepsilon_0 := |a-b| \,, \] since \(\varepsilon_0 >0\) given that \(a \neq b\).

2.11 Induction

Another technique for carrying out proofs is induction, which we take as an axiom.

Axiom 49: Principle of Induction

Let \(S \subseteq \mathbb{N}\). Suppose that

We have \(1 \in S\), and
Whenever \(n \in S\), then \((n+1) \in S\).

Then we have \[ S=\mathbb{N}\,. \]

Important

The above is an axiom, meaning that we do not prove it, but rather we just assume it holds.

Remark 50

It would be possible to prove the Principle of Induction starting from elementary axioms for \(\mathbb{N}\), called the Peano Axioms, see the Wikipedia page.
However, in justifying basic principles of mathematics, one at some point needs to draw a line. This means that something which looks elementary needs to be assumed to hold, in order to have a starting point for proving deeper statements.
In the case of the Principle of Induction, the intuition is clear:

The Principle of Induction is just describing the domino effect: If one tile falls, then the next one will fall as well. Therefore if the first tile falls, all the tiles will fall.

It seems reasonable to assume such evident principle.

The Principle of Induction can be used to prove statements which depend on some index \(n \in \mathbb{N}\). Precisely, the following statement holds.

Corollary 51: Principle of Inducion - Alternative formulation

Let \(\alpha(n)\) be a statement which depends on \(n \in \mathbb{N}\). Suppose that

\(\alpha(1)\) is true, and
Whenever \(\alpha(n)\) is true, then \(\alpha(n+1)\) is true.

Then \(\alpha(n)\) is true for all \(n \in \mathbb{N}\).

Proof

Define the set \[ S:= \{ n \in \mathbb{N}\, \text{ s.t. } \, \alpha(n) \mbox{ is true} \} \,. \] Then

We have \(1 \in S\), since \(\alpha(1)\) is true.
If \(n \in S\) then \(\alpha(n)\) is true. By assumption this implies that \(\alpha(n+1)\) is true. Therefore \((n+1) \in S\).

Therefore \(S\) satisfies the assumptions of the Induction Principle and we conclude that \[ S=\mathbb{N}\,. \] By definition this means that \(\alpha(n)\) is true for all \(n \in \mathbb{N}\).

Example 52: Formula for summing first \(n\) natural numbers

Question. Prove by induction that the following formula holds for all \(n \in \mathbb{N}\): \[ 1 + 2 + 3 + \ldots + (n-1) + n = \frac{n(n+1)}{2} \,. \tag{2.18}\]

Solution. To be really precise, consider the statement \[ \alpha(n) := \, \mbox{the above formula is true for } \, n \,. \] In order to apply induction, we need to show that

\(\alpha(1)\) is true,
If \(\alpha(n)\) is true then \(\alpha(n+1)\) is true.

Let us proceed: Define \[ S(n) = 1 + 2 + \ldots + n \,. \] This way the formula at (2.18) is equivalent to \[ S(n) = \frac{n(n+1)}{2} \,, \quad \forall \, n \in \mathbb{N}\,. \]

It is immediate to check that (2.18) holds for \(n=1\).
Suppose (2.18) holds for \(n = k\). Then \[\begin{align} S(k+1) & = 1 + \ldots + k + (k+1) \\ & = S(k) + (k+1) \\ & = \frac{k(k+1)}{2} + (k+1) \\ & = \frac{ k(k+1) + 2(k+1) }{2} \\ & = \frac{(k+1)(k+2)}{2} \end{align}\] where in the first equality we used that (2.18) holds for \(n=k\). We have proven that \[ S(k+1) = \frac{(k+1)(k+2)}{2}\,. \] The RHS in the above expression is exactly the RHS of (2.18) computed at \(n = k+1\). Therefore, we have shown that formula (2.18) holds for \(n = k+1\).

By the Principle of Induction, we then conclude that \(\alpha(n)\) is true for all \(n \in \mathbb{N}\), which means that (2.18) holds for all \(n \in \mathbb{N}\).

Example 53: Statements about sequences of numbers

Suppose you are given a collection of numbers \[ \{ x_n \, \text{ s.t. } \, n \in \mathbb{N}\} \,. \] Such collection of numbers is called sequence. Assume that \[\begin{align} & x_1 := 1 \\ & x_{n+1} := \frac{x_n}{2} + 1 \,. \end{align}\] A sequence defined as above is called recurrence sequence. Using the above rule we can compute all the terms of \(x_n\).

Let us compute the first 4 elements: \[\begin{align} x_1 & = 1 \\ x_2 & = \frac{x_1}{2} + 1 = 1 + \frac12 = x_1 + \frac{1}{2} \\ x_3 & = \frac{x_2}{2} + 1 = 1 + \frac12 + \frac{1}{4} = x_2 + \frac{1}{4} \\ x_4 & = \frac{x_3}{2} + 1 = 1 + \frac12 + \frac{1}{4} + \frac{1}{8} = x_3 + \frac{1}{8}\\ \end{align}\] We see a pattern: The successive term is obtained by adding a power of \(1/2\) to the previous term. We therefore conjecture that \[ x_{n+1} = x_n + \frac{1}{2^n} \tag{2.19}\]

We want to prove our conjecture rigorously, i.e. using induction.

Claim. (2.19) holds for all \(n \in \mathbb{N}\).

Proof of Claim. We argue by induction:

We see that \[ x_2 = 1 + \frac{1}{2} = x_1 + \frac{1}{2} \] proving (2.19) for \(n = 1\).
Suppose now that (2.19) holds for \(n=k\). We need to prove that (2.19) holds for \(n=k+1\), that is, \[ x_{k+2} = x_{k+1} + \frac{1}{2^{k+1}} \,. \tag{2.20}\] Starting with the definition of \(x_{k+2}\) we see that \[\begin{align*} x_{k+2} & = \frac{x_{k+1}}{2} + 1 & (\text{definition of } x_{k+2} ) \\ & = \frac{x_k + \frac{1}{2^k}}{2} + 1 & (\text{inductive hypothesis} ) \\ & = \frac{x_k}{2} + 1 + \frac{1}{2^{k+1}} & (\text{just calculations} ) \\ & = x_{k+1} + \frac{1}{2^{k+1}} & (\text{definition of } x_{k+1} ) \\ \end{align*}\] which proves (2.20).

Therefore the assumptions of the Induction Principle are satisfied, and (2.19) follows.

Example 54: Bernoulli’s inequality

Question. Let \(x \in \mathbb{R}\) with \(x>-1\). Bernoulli’s inequality states that \[ (1+x)^{n} \geq 1+n x \,, \quad \forall \, n \in \mathbb{N}\,. \tag{2.21}\] Prove Bernoulli’s inequality by induction.

Solution. Let \(x \in \mathbb{R}, x>-1\). We prove the statement by induction:

Base case: (6.9) holds with equality when \(n=1\).
Induction hypothesis: Let \(k \in \mathbb{N}\) and suppose that (6.9) holds for \(n=k\), i.e., \[ (1+x)^{k} \geq 1+k x \,. \] Then \[\begin{align*} (1+x)^{k+1} & = (1+x)^{k}(1+x) \\ & \geq(1+k x)(1+x) \\ & =1+k x+x+k x^{2} \\ & \geq 1+(k+1) x \,, \end{align*}\] where we used that \(kx^2 \geq 0\). Then (6.9) holds for \(n=k+1\).

By induction we conclude (6.9).