1  Preliminaries

Theorem 1

The number \(\sqrt{2}\) does not belong to \(\mathbb{Q}\).

Proof

Aassume by contradiction that \[ \sqrt{2} \in \mathbb{Q}\,. \tag{1.1}\]

1. Therefore, there exist \(m \in \mathbb{Z}\), \(n \in \mathbb{N}\), \(n \neq 0\), such that \[ \frac{m}{n} = \sqrt{2} \,. \]

2. Withouth loss of generality, we can assume that \(m\) and \(n\) have no common factors.

3. Square the equation to get \[ \frac{m^2}{n^2} = 2 \quad \implies \quad m^2 = 2 n^2 \,. \tag{1.2}\] Therefore the integer \(m^2\) is an even number.

4. Since \(m^2\) is an even number, it follows that also \(m\) is an even number. Then there exists \(p \in \mathbb{N}\) such that \[ m = 2p \,. \tag{1.3}\]

5. Substitute (1.3) in (1.2) to get \[ m^2 = 2n^2 \, \implies \, (2p)^2 = 2n^2 \, \implies \, 4 p^2 = 2 n^2 \] Dividing both terms by \(2\), we obtain \[ n^2 = 2p^2\,. \tag{1.4}\]

Now, observe that:

• Equation (1.4) says that \(n^2\) is even. The argument in Step 4 guarantees that also \(n\) is even.
• Therefore \(n\) and \(m\) are both even, meaning they have \(2\) as common factor.
• But Step 2 says that \(n\) and \(m\) have no common factors. Contradiction

The contradiction stems from assumption (1.1). Thus, (1.1) is false, ending the proof.

1.1 Set Theory

Definition 2

Let \(A\) be a set.

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

Definition 3

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 4

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

Proposition 6

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

Definition 7: Infinite union and intersection

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

1. 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}\} \,. \]

2. 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 8

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

1. Prove that \[ \bigcup_{n \in \mathbb{N}} A_n = \mathbb{N}\,. \tag{1.5}\]

2. Prove that \[ \bigcap_{n \in \mathbb{N}} A_n = \emptyset \,. \tag{1.6}\]

Solution.

1. 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 (1.5).

2. Suppose that (1.6) 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 (1.6) holds.

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

Example 10

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

Proposition 11: 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 \,. \]

Definition 12

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

Example 13

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

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

1.2 Eequivalence Relations

Definition 15: Binary relation

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

Definition 16: Equivalence relation

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

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

2. Symmetric: We have \[ (x,y) \in R \implies (y,x) \in R \]

3. Transitive: We have \[ (x,y) \in R \,, \,\, (y,z) \in R \implies (x,z) \in R \]

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

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

Proposition 18: Well-posedness of Definition 17

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

1. For each \(x \in A\) we have \([x] \neq \emptyset\).

2. For all \(x,y \in A\) it holds \[ x \sim y \quad \iff \quad [x] = [y] \,. \]

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

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

Solution.

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

2. 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}\} \,. \]

Example 20

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

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

Solution.

1. 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}\).

2. 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{1.7}\] 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 (1.7). In particular (1.7) implies that for each \(x \in \mathbb{Q}\) there exists \(q \in [0,1) \cap \mathbb{Q}\) such that \[ [x] = [q] \,. \]

3. From Point 2 we conclude that \[ \mathbb{Q}/ R = \{ [x] \, \colon \,x \in \mathbb{Q}\} = \{ q \in \mathbb{Q}\, \colon \,0 \leq q <1 \} \,. \]

1.3 Order relations

Definition 21: Partial order

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

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

2. Antisymmetric: We have \[ (x,y) \in R \, \text{ and } \, (y,x) \in R \implies x = y \]

3. Transitive: We have \[ (x,y) \in R \,, \,\, (y,z) \in R \implies (x,z) \in R \]

Definition 22: Total order

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

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

Example 23: 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 \} \,. \]

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

Solution.

1. 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\).
2. 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.

Example 24: Inequality is a total order

Question. Consider the binary relation \[ 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:

1. Reflexive: It holds, since \(x \leq x\) for all \(x \in \mathbb{Q}\),

2. Antisymmetric: If \(x \leq y\) and \(y \leq x\) then \(x = y\).

3. 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 \,. \]

1.4 Induction

Axiom 25: Principle of Inducion

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

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

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

Example 26: 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{1.8}\]

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

1. It is immediate to check that (1.8) holds for \(n=1\).
2. Suppose (1.8) 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 (1.8) 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 (1.8) computed at \(n = k+1\). Therefore, we have shown that formula (1.8) holds for \(n = k+1\).

By the Principle of Induction, we conclude that (1.8) holds for all \(n \in \mathbb{N}\).

Example 27: 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{1.9}\] Prove Bernoulli’s inequality by induction.

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

• Base case: (1.9) holds with equality when \(n=1\).

• Induction hypothesis: Let \(k \in \mathbb{N}\) and suppose that (1.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 (1.9) holds for \(n=k+1\).

By induction we conclude (1.9).

1.5 Absolute value

Definition 28: 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} \]

Proposition 29: Properties of absolute value

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

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

Lemma 30

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

Corollary 31

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

Theorem 32: Triangle inequality

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

Proposition 33

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