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 sets 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

Given an arbitrary set \(A\), we write \[ x \in A \]

if the element \(x\) belongs to the set \(A\). If an element \(x\) is not contained in \(A\), we say that

\[ x \notin A \,. \]

Remark 1

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. Note that (2.1) is equivalent to \[ \alpha \implies \beta \,\, \text{ and } \,\, \beta \implies \alpha \,. \] Such equivalence is very useful in proofs.

Example 2

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 3

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

2.3.1 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 4

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}\]

2.3.2 Inclusion and equality

Given two sets \(A\) and \(B\), we say that \(A\) is contained in \(B\) if all the elements of \(A\) are also contained in \(B\). This will be denoted with the inclusion symbol \(\subseteq\), that is, \[ A \subseteq B \,. \] In this case we say that

\(A\) is a subset of \(B\),
\(B\) is a superset of \(A\).

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.

Example 5

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}\]

We say that two sets \(A\) and \(B\) are equal if they contain the same elements. We denote equality by the symbol \[ A=B \,. \] If \(A \subseteq B\) and \(A \neq B\), we write \[ A \subset B \quad \mbox{ or } \quad A \subsetneq B \,. \]

Example 6

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 \subset B\) or \(A \subsetneq B\).

Proposition 7

Let \(A\) and \(B\) be sets. Then \[ A=B \] if and only if \[ 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\).

The above 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\).

2.3.3 Infinite unions and intersections

Suppose given a set \(\Omega\), and a family of sets \(A_n \subseteq \Omega\), where \(n \in \mathbb{N}\). Then we can define the infinte union \[ \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 is defined as \[ \bigcap_{n \in \mathbb{N}} A_n := \{ x \in \Omega \, \colon \, x \in A_n \,\, \text{ for all } \,\, n \in \mathbb{N}\} \,. \]

Example 8

Let the ambient set be \(\Omega:=\mathbb{N}\) and define the family \(A_n\) by \[\begin{align} A_1 & := \{ 1, 2, 3 , 4 , \ldots \} \\ A_2 & := \{ 2, 3 , 4 , 5, \ldots \} \\ A_3 & := \{ 3 , 4 , 5, 6, \ldots \} \\ & \ldots \ldots \\ A_n & := \{ n, n+1, n+2, n+3, \ldots \} \,, \end{align}\] for arbitrary \(n \in \mathbb{N}\). Then \[ \bigcup_{n \in \mathbb{N}} A_n = \mathbb{N}\,. \tag{2.2}\] The above equality can be easily proven using Proposition 7. Indeed, 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 \,. \] Hence we conclude (2.2) by Proposition 7.
We also have that \[ \bigcap_{n \in \mathbb{N}} A_n = \emptyset \,. \tag{2.3}\] We prove the above by contradiction. Indeed, 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.4 Complement

Suppose that \(A\) and \(B\) are subsets of a larger set \(\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 9

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 10

Suppose \(A, B \subseteq \Omega\). Then \[ A \subseteq B \iff B^c \subseteq A^c \,. \]

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\):
Essentially the same proof, hence we omit it.

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

Proposition 11: De Morgan’s Laws

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

2.3.5 Power set

Let \(\Omega\) be an arbitray set. We define the power set of \(\Omega\) as \[ \mathcal{P}(\Omega) := \{ A \, \colon \,A \subseteq \Omega \}\,, \] that is, the power set of \(\Omega\) is the set of all subsets of \(\Omega\).

Remark 12

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.

This is because for each \(x_i \in \Omega\) we have just two choices: either include \(x_i\) in a subset, or do not include \(x_i\) in a subset.

Example 13

Define the set \[ \Omega = \{ x, y, z \}\,. \] Then \(\mathcal{P}(\Omega)\) has \(2^3 = 8\) elements. These are

\(\emptyset\)
\(\{x\}\)
\(\{y\}\)
\(\{z\}\)
\(\{x,y\}\)
\(\{x,z\}\)
\(\{y,z\}\)
\(\{x,y,z\}\)

We therefore write \[\begin{align} \mathcal{P}(\Omega) = \{ \emptyset, & \, \{x\} , \, \{y\} , \, \{z\} , \{x,y\} \\ & \{x,z\}, \, \{y,z\} , \, \{x,y,z\} \} \,. \end{align}\]

2.3.6 Product of sets

Suppose \(A\) and \(B\) are two 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

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

Definition 14: 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 15: 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 \, := \,\{ [x] \, \colon \, x \in A \} \,. \]

Let us immediately clarify the above definitions by considering the prototypical example of equivalence relation: the equality.

Example 16: Equality is an equivalence relation

Consider the set of natural numbers \(\mathbb{N}\). The equality defines a binary relation on \(\mathbb{N}\times \mathbb{N}\), via \[ R:=\{ (x,y) \in \mathbb{N}\times \mathbb{N}\, \colon \, x=y \} \,. \] Let us check that \(R\) is an equivalence relation:

Reflexive: It holds, since \(x=x\) for all \(x \in \mathbb{N}\),
Symmetric: Again \(x = y\) if and only if \(y = x\),
Transitive: If \(x = y\) and \(y = z\) then \(x = z\).

The class of equivalence of \(x \in \mathbb{N}\) is given by \[ [x] = \{ x \}\,, \] that is, this relation is quite trivial, given that each element of \(\mathbb{N}\) can only be related to itself. The quotient space is then \[ \mathbb{N}/ R = \{ [x] \, \colon \,x \in \mathbb{N}\} = \{ \{ x\} \, \colon \,x \in \mathbb{N}\} \,. \]

Example 17

Suppose that \(R\) is a binary relation on the set \(\mathbb{Q}\) of rational numbers defined by \[ x \sim y \iff x-y \in \mathbb{Z}\,. \] Then \(R\) is an equivalence relation on \(\mathbb{Q}\). Indeed:

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\). This shows that \(R\) is an equivalence relation on \(\mathbb{Q}\).

Now note that \[ y \sim x \iff y -x \in \mathbb{Z} \] and the above is equivalent to \[ \exists \, n \in \mathbb{Z}\, \text{ s.t. } \, y - x = n \] which again is equivalent to \[ \exists \, n \in \mathbb{Z}\, \text{ s.t. } \, y = x + n \,. \] Therefore all the elements of \(\mathbb{Q}\) related to \(x\) by \(R\) are of the form \[ x + n \,, \, \forall \, n \in \mathbb{Z}\,. \] The equivalence classes with respect to \(R\) are then \[ [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]\,. \] Therefore \[ \mathbb{Q}/ R = \{ [x] \, \colon \,x \in \mathbb{Q}\} = \{ q \in \mathbb{Q}\, \colon \,0 \leq q <1 \} \,. \]

2.5 Order relation

Similarly, we define order relations.

Definition 18: 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 \,, \]
Transitive: We have \[ (x,y) \in R \,, \,\, (y,z) \in R \implies (x,z) \in R \]
Antisymmetric: We have \[ (x,y) \in R \, \text{ and } \, (y,x) \in R \implies x = y \]

This is the only new condition with respect to the definition of equivalence relation, and it replaces symmetry.

Definition 19: 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 \,. \]

This is saying that all elements in \(A\) are related.

An example of partial order is the operation of set inclusion.

Example 20: Set inclusion is a partial order

Consider an arbitrary non-empty set \(\Omega\) 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 \} \,. \] Let us check that \(R\) is an order relation:

Reflexive: It holds, since \(A \subseteq A\) for all \(A \in \mathcal{P}(\Omega)\),
Transitive: If \(A \subseteq B\) and \(B \subseteq C\), then by definition of inclusion \(A \subseteq C\).
Antisymmetric: If \(A \subseteq B\) and \(B \subseteq A\), then \(A=B\) by Proposition 7.

Therefore \(R\) is a partial order on \(\mathcal{P}(\Omega)\). Note that in general \(R\) is not a total order. For example if we 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 \,, \] showing that \(R\) is not a total order.

A very important example of total order is the inequality on \(\mathbb{Q}\).

Example 21: Inequality is a total order

Consider the set of rationals \(\mathbb{Q}\). The usual inequality defines a binary relation on \(\mathbb{Q}\times \mathbb{Q}\), via \[ R:=\{ (x,y) \in \mathbb{Q}\times \mathbb{Q}\, \colon \, x \leq y \} \,. \] Let us check that \(R\) is an order relation:

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

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 22

If \(\Omega\) is a set and \(R\) is a total order on \(\Omega\), 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 23

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.1, Figure 2.2, Figure 2.3, Figure 2.4 below.

2.7 Functions

Definition 24: 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 of \(f\) is the set \[ \{ 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 24. 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 25

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 26

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 27: Absolute value

For \(x \in \mathbb{R}\) we define its absolute value as the quantity \[ |x| = \begin{cases} x & \text{ if } \, x \geq 0 \\ -x & \text{ if } \, x < 0 \end{cases} \]

Example 28

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 also make the following basic remark, whose proof will be left as an exercise.

Remark 29

For all \(x \in \mathbb{R}\) one has \[ |x| \geq 0 \,. \] Moreover \[ |x| = 0 \iff x = 0 \,. \]

Another basic remark (proof by exercise).

Remark 30

For all \(x \in \mathbb{R}\) one has \[ |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 31: 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.5 below.

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

Remark 32: 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.6 below. Note that by Remark 30 we have \[ |x-y| = |y-x| \,. \]

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

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

Lemma 33

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.7 below.

Figure 2.7: Geometric meaning of Lemma 33

Proof: Proof of Lemma 33

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

Case 1: \(x \geq 0\). From (2.4), (2.5) 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.4), (2.5) 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.6}\] We make separate arguments for the cases \(x \geq 0\) and \(x<0\):

Case 1: \(x \geq 0\). Since \(x \geq 0\), from (2.6) we get \[ |x| = x \leq y \] showing that \[ |x| \leq y \,. \]
Case 2: \(x < 0\). Since \(x < 0\), from (2.6) 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.

Lemma 34

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 35: Triangle inequality

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

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

Remark 36: 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.8 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.9 below. From the picture it is evident that \[ |x+y| \leq |x| + |y|\,, \tag{2.8}\] 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.8) is exactly the second inequality in (2.7). This is why (2.7) is called triangle inequality.

Figure 2.9: 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 35

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

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

Step 2. Proof of the first inequality in (2.7).
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.11) 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.12}\] We can now swap \(x\) and \(y\) in (2.12) to get \[ |y| - |x| \leq |x+y| \,. \] By rearranging the above inequality we obtain \[ -|x+y| \leq |x| - |y| \,. \tag{2.13}\] Putting together (2.12) and (2.13) yields \[ -|x+y| \leq |x| - |y| \leq |x+y| \,. \] By Lemma 33 the above is equivalent to \[ ||x| - |y|| \leq |x+y| \,, \] which is the first inequality in (2.7).

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

Remark 37

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

2.10 Proofs in Mathematics

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

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

Proving (2.14) means convincing ourselves that \(\beta\) follows from \(\alpha\). Common strategies to prove (2.14) 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.14) holds.
Contrapositive: The statement (2.14) is equivalent to \[ \neg \beta \, \implies \, \neg \alpha \,. \tag{2.15}\] Thus, instead of proving (2.14), one could show (2.15). The statement (2.15) is called the contrapositive of (2.14).

Let us make an example.

Proposition 38

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 39: 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 40

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 41: 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 42: Formula for summing first \(n\) natural numbers

Using the Principle of Induction we can prove that \[ 1 + 2 + 3 + \ldots + (n-1) + n = \frac{n(n+1)}{2} \tag{2.16}\] holds for all \(n \in \mathbb{N}\).

Proof. 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:

It is immediate to check that (2.16) holds for \(n=1\).
Suppose (2.16) holds for \(n\). Then \[\begin{align} 1 + \ldots + n + (n+1) & = \frac{n(n+1)}{2} + (n+1) \\ & = \frac{ n(n+1) + 2(n+1) }{2} \\ & = \frac{(n+1)(n+2)}{n} \end{align}\] where in the first equality we used that (2.16) holds for \(n\). We then have \[ 1 + \ldots + n + (n+1) = \frac{(n+1)(n+2)}{n}\,, \] which shows that (2.16) holds for \(n+1\).

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

Example 43: 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\).

For example \[\begin{align} x_2 & = \frac{x_1}{2} + 1 = \frac12 + 1 =\frac{3}{2} \\ x_3 & = \frac{x_2}{2} + 1 = \frac34 + 1 = \frac74 \,. \end{align}\]

By computing these terms, we suspect that the sequence might be increasing, meaning that \[ x_{n+1} \geq x_n \tag{2.17}\] for all \(n \in \mathbb{N}\).

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

Proof of Claim.
We argue by induction:

We have seen that \(x_1 = 1\) and \(x_2 = 3/2\). Thus \[ x_2 \geq x_1 \,. \]
Suppose now that \[ x_{n+1} \geq x_{n} \,. \tag{2.18}\] We need to prove that \[ x_{n+2} \geq x_{n+1} \,. \tag{2.19}\] Indeed, we can multiply the inequality (2.18) by \(1/2\) and add \(1\) to get \[ \frac{x_{n+1}}{2} + 1 \geq \frac{x_{n}}{2} + 1 \,. \] The above is equivalent, by definition, to (2.19).

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