3 Properties of \(\mathbb{R}\)

Theorem 1: Archimedean Property

Let \(x \in \mathbb{R}\) be given. Then:

There exists \(n \in \mathbb{N}\) such that \[ n > x \,. \]
Suppose in addition that \(x>0\). There exists \(n \in \mathbb{N}\) such that \[ \frac1n < x \,. \]

Theorem 2: Archimedean Property (Alternative formulation)

Let \(x,y \in \mathbb{R}\), with \(0<x<y\). There exists \(n \in \mathbb{N}\) such that \[ nx > y \,. \]

Theorem 3: Nested Interval Property

For each \(n \in \mathbb{N}\) assume given a closed interval \[ I_n := [a_n,b_n] = \{ x \in \mathbb{R}\, \colon \,a_n \leq x \leq b_n \} \,. \] Suppose that the intervals are nested, that is, \[ I_n \supset I_{n+1}\,, \quad \forall \, n \in \mathbb{N}\,. \] Then \[ \bigcap_{n=1}^\infty I_n \neq \emptyset \,. \tag{3.1}\]

Example 4

Question. Consider the open intervals \[ I_n := \left( 0, \frac1n \right) \,. \] These are clearly nested \[ I_n \supset I_{n+1}\,, \quad \forall \, n \in \mathbb{N}\,. \] Prove that \[ \bigcap_{n=1}^\infty I_n = \emptyset \,. \tag{3.2}\]

Solution. Suppose by contradiction that the intersection is non-empty. Then there exists \(x \in \mathbb{N}\) such that \[ x \in I_n \,, \quad \forall \, n \in \mathbb{N}\,. \] By definition of \(I_n\) the above reads \[ 0 < x < \frac1n \,, \quad \forall \, n \in \mathbb{N}\,. \tag{3.3}\] Since \(x>0\), by the Archimedean Property in Theorem 1 Point 2, there exists \(n_0 \in \mathbb{N}\) such that \[ 0 < \frac{1}{n_0} < x \,. \] The above contradicts (3.3). Therefore (3.2) holds.

3.1 Revisiting Sup and Inf

Proposition 5: Characterization of Supremum

Let \(A \subseteq \mathbb{R}\) be a non-empty set. Suppose that \(s \in \mathbb{R}\) is an upper bound for \(A\). They are equivalent:

\(s = \sup A\)
For every \(\varepsilon> 0\) there exists \(x \in A\) such that \[ s - \varepsilon< x \,. \]

Proposition 6: Characterization of Infimum

Let \(A \subseteq \mathbb{R}\) be a non-empty set. Suppose that \(i \in \mathbb{R}\) is a lower bound for \(A\). They are equivalent:

\(i = \inf A\)
For every \(\varepsilon\in \mathbb{R}\), with \(\varepsilon> 0\), there exists \(x \in A\) such that \[ x < i + \varepsilon\,. \]

Proposition 7

Let \(a, b \in \mathbb{R}\) with \(a<b\). Let \[ A:= (a,b) = \{ x \in \mathbb{R}\, \colon \,a < x < b \}\,. \] Then \[ \inf A = a \,, \quad \sup A = b \,. \]

Corollary 8

Let \(a, b \in \mathbb{R}\) with \(a<b\). Let \[ A:= (a,b) = \{ x \in \mathbb{R}\, \colon \,a < x < b \}\,. \] Then \(\min A\) and \(\max A\) do not exist.

Corollary 9

Let \(a, b \in \mathbb{R}\) with \(a<b\). Let \[ A:= [a,b) = \{ x \in \mathbb{R}\, \colon \,a \leq x < b \}\,. \] Then \[ \min A = \inf A = a \,, \quad \sup A = b \,, \] \(\max A\) does not exist.

Proposition 10

Define the set \[ A := \left\{ \frac1n \, \colon \,n \in \mathbb{N}\right\} \,. \] Then \[ \inf A = 0 \,, \quad \sup A = \max A = 1 \,. \]

Proof

Part 1. We have \[ \frac1n \leq 1 \,, \quad \forall \, n \in \mathbb{N}\,. \] Therefore \(1\) is an upper bound for \(A\). Since \(1 \in A\), by definition of maximum we conclude that \[ \max A = 1 \,. \] Since the maximum exists, we conclude that also the supremum exists, and \[ \sup A = \max A = 1 \,. \]

Part 2. We have \[ \frac1n > 0 \,, \quad \forall \, n \in \mathbb{N}\,, \] showing that \(0\) is a lower bound for \(A\). Suppose by contradiction that \(0\) is not the infimum. Therefore \(0\) is not the largest lower bound. Then there exists \(\varepsilon\in \mathbb{R}\) such that:

\(\varepsilon\) is a lower bound for \(A\), that is, \[ \varepsilon\leq \frac1n \,, \quad \forall \, n \in \mathbb{N}\,, \tag{3.4}\]
\(\varepsilon\) is larger than \(0\): \[ 0 < \varepsilon\,. \]

As \(\varepsilon>0\), by the Archimedean Property there exists \(n_0 \in \mathbb{N}\) such that \[ 0 < \frac{1}{n_0} < \varepsilon\,. \] This contradicts (3.4). Thus \(0\) is the largest lower bound of \(A\), that is, \(0 = \inf A\).

Part 3. We have that \(\min A\) does not exist. Indeed suppose by contradiction that \(\min A\) exists. Then \[ \min A = \inf A \,. \] As \(\inf A = 0\) by Part 2, we conclude \(\min A = 0\). As \(\min A \in A\), we obtain \(0 \in A\), which is a contradiction.

3.2 Cardinality

Definition 11: Cardinality, Finite, Countable, Uncountable

Let \(X\) be a set. The cardinality of \(X\) is the number of elements in \(X\). We denote the cardinality of \(X\) by \[ |X| := \# \, \mbox{ of elements in } \, X \,. \] Further, we say that:

\(X\) is finite if there exists a natural number \(n \in \mathbb{N}\) and a bijection \[ f \colon \{1,2,\ldots, n \} \to X \,. \] In particular \[ |X| = n \,. \]
\(X\) is countable if there exists a bijection \[ f \colon \mathbb{N}\to X \,. \] In this case we denote the cardinality of \(X\) by \[ |X| = |\mathbb{N}| \,. \]
\(X\) is uncountable if \(X\) is neither finite, nor countable.

Proposition 12

Let \(X\) be a countable set and \(A \subseteq X\). Then either \(A\) is finite or countable.

Example 13

Question. Prove that \(X = \{a,b,c\}\) is finite.

Solution. Set \(Y=\{ 1,2,3\}\). The function \(f \colon X \to Y\) defined by \[ f(1)=a \,, \quad f(2) = b \,, \quad f(3) = c \,, \] is bijective. Therefore \(X\) is finite, with \(|X| = 3\).

Example 14

Question. Prove that the set of natural numbers \(\mathbb{N}\) is countable.

Solution. The function \(f \colon X \to \mathbb{N}\) defined by \[ f(n):=n \,, \] is bijective. Therefore \(X = \mathbb{N}\) is countable.

Example 15

Question. Let \(X\) be the set of even numbers \[ X = \{ 2n \, \colon \,n \in \mathbb{N}\} \,. \] Prove that \(X\) is countable.

Solution. Define the map \(f \colon \mathbb{N}\to X\) by \[ f(n):= 2n \,. \] We have that:

\(f\) is injective, because \[ f(m)=f(k) \, \implies \, 2m=2k \, \quad \, m=k \,. \]
\(f\) is surjective: Suppose that \(m \in X\). By definition of \(X\), there exists \(n \in \mathbb{N}\) such that \(m = 2n\). Therefore, \(f(n) = m\).

We have shown that \(f\) is bijective. Thus, \(X\) is countable.

Example 16

Question. Prove that the set of integers \(\mathbb{Z}\) is countable.

Solution. Define \(f \colon \mathbb{N}\to \mathbb{Z}\) by \[ f(n):= \begin{cases} \dfrac{n}{2} & \,\, \mbox{ if } \, n \, \mbox{ even } \\ -\dfrac{n+1}{2} & \,\, \mbox{ if } \, n \, \mbox{ odd } \end{cases} \] For example \[\begin{align*} f(0) & = 0 \,, \quad f(1) = -1 \,, \quad f(2) = 1 \,, \quad f(3) = -2 \,, \\ f(4) & = 2 \,, \quad f(5) = -3 \,, \quad f(6) = 3 \,, \quad f(7) = -4 \,. \end{align*}\] We have:

\(f\) is injective: Indeed, suppose that \(m \neq n\). If \(n\) and \(m\) are both even or both odd we have, respectively \[\begin{align*} f(m) = \frac{m}{2} & \neq \frac{n}{2} = f(n) \\ f(m) = -\frac{m+1}{2} & \neq - \frac{n+1}{2} = f(n) \,. \end{align*}\] If instead \(m\) is even and \(n\) is odd, we get \[ f(m) = \frac{m}{2} \neq - \frac{n+1}{2} = f(n) \,, \] since the LHS is positive and the RHS is negative. The case when \(m\) is odd and \(n\) even is similar.
\(f\) is surjective: Let \(z \in \mathbb{Z}\). If \(z \geq 0\), then \(m:=2z\) belongs to \(\mathbb{N}\), is even, and \[ f(m) = f(2z) = z \,. \] If instead \(z < 0\), then \(m := -2z -1\) belongs to \(\mathbb{N}\), is odd, and \[ f(m) = f(-2z-1) = z \,. \]

Therefore \(f\) is bijective, showing that \(\mathbb{Z}\) is countable.

Proposition 17

Let the set \(A_n\) be countable for all \(n \in \mathbb{N}\). Define \[ A = \bigcup_{n \in \mathbb{N}} \, A_n \, . \] Then \(A\) is countable.

Theorem 18: \(\mathbb{Q}\) is countable

The set of rational numbers \(\mathbb{Q}\) is countable.

Theorem 19: \(\mathbb{R}\) is uncountable

The set of Real Numbers \(\mathbb{R}\) is uncountable.

Theorem 20

The set of irrational numbers \[ \mathcal{I}:=\mathbb{R}\smallsetminus \mathbb{Q} \] is uncountable.

Proof

We know that \(\mathbb{R}\) in uncountable and \(\mathbb{Q}\) is countable. Suppose by contradiction that \(\mathcal{I}\) is countable. Then \[ \mathbb{Q}\cup \mathcal{I} \] is countable by Proposition 17, being union of countable sets. Since by definition \[ \mathbb{R}= \mathbb{Q}\cup \mathcal{I} \,, \] we conclude that \(\mathbb{R}\) is countable. Contradiction.