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 exists \(m,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}\]

6. We now make a series of observations:

   • Equation (1.4) says that \(n^2\) is even.
   • The same 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

7. Our reasoning has run into a contradiction, stemming from assumption (1.1). Therefore (1.1) is FALSE, and so \[ \sqrt{2} \notin \mathbb{Q}\, \] ending the proof.

1.1 Set Theory

Definition 2

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

Proposition 3

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

Definition 4

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 5

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 6

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 7

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 8: 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 9

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

Example 10

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 11

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 Relations

Definition 12

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

Definition 13: 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 14: 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 15

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 16: 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 17

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

Definition 18: 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 19: 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 20: 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 21: 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.3 Induction

Definition 22: 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 23: 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 24: 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.4 Absolute value

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

Proposition 26

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 27

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

Corollary 28

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

Theorem 29: Triangle inequality

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

Proposition 30

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