2.1. Real Line#

The set of real numbers is also known as real line.

2.1.1. Prelude#

We look at some justification for why real numbers are needed.

Proposition 2.1

There is no rational number whose square root is 2.

Proof. Let us assume that there indeed is a rational number whose square root is 2:

\[ \left ( \frac{p}{q} \right )^2 = 2. \]

We assume that $p$ and $q$ have no common factor. Then we have: $p^2 = 2 q^2$. This means that $p^2$ is even. Thus, $p$ is even. Let $p = 2r$. Then $4r^2 = 2q^2 \implies q^2 = 2r^2$. This means that $q^2$ is even. Thus, $q$ is even. But this contradicts our assumption that $p$ and $q$ have no common factor.

This argument shows that the set of rational numbers is not complete in the sense that we can posit the existence of numbers which are not rational.

We extend the set further to a larger number system known as real numbers. The completeness axiom plays a major role in the definition of real numbers.

2.1.2. Real numbers#

We present the axiomatic definition of real numbers.

Definition 2.1 (Real Numbers)

The real numbers are the members of a nonempty set $\RR$ equipped with two operations $+$ and $\cdot$ from $\RR \times \RR$ into $\RR$ called addition and multiplication, that satisfy following axioms. We will denote arbitrary members of $\RR$ as $x, y$ and $z$. We will also abbreviate multiplication $x \cdot y$ as $x y$.

$x + y = y + x$ and $x y = y x$; commutative laws.
$x + (y + z) = (x + y) + z$ and $x (y z) = (x y) z$; associative laws.
$x(y + z) = x y + x z$; distributive law.
There exists an element $0 \in \RR$ such that $x + 0 = x \Forall x \in \RR$; additive identity.
For each $x \in \RR$ there exists an element in $\RR$ denoted by $-x$ such that $x + (-x) = 0$; additive inverse.
There exists an element $1 \in \RR$ with $1 \neq 0$ satisfying $1\cdot x = x \Forall x \in \RR$; multiplicative identity.
For each $x \neq 0$ there exists an element in $\RR$ denoted by $x^{-1}$ satisfying $x x^{-1} = 1$; multiplicative inverse.
For any $x, y \in \RR$ either $ x \geq y$ or $y \geq x$ holds; total order.
If $x \geq y$, then $ x + z \geq y + z$ holds for each $z \in \RR$.
If $x \geq y$ and $z \geq 0$ then $x z \geq y z$.
Every nonempty set of real numbers that is bounded from above has a least upper bound; completeness axiom.

Axioms (1-7) are field axioms. Axioms (8-10) establish that $\RR$ is an ordered field. Axiom (11) is discussed further in Axiom 2.1.

It can be shown that if $\RR$ and $\SS$ are two different sets satisfying these axioms then they are isomorphic and for all practical purposes identical.

Several remarks immediately follow from the definition.

The zero element (additive identity) is unique.
The one element (multiplicative identity) is unique.
The additive inverse $-x$ is unique.
$-x= (-1)x$ holds.
The multiplicative inverse $x^{-1}$ for $x \neq 0$ is unique.
$0 \cdot x = 0$.
$ - ( - x) = x$.
$(-x) (-y) = x y$.
$ x - y = x + (-y) = - (y - x)$.
$(x^{-1})^{-1} = x \Forall x \neq 0$.

Remarks above are derived from field properties of real line.

Further remarks on order property

An alternative notation for $x \geq y$ is $y \leq x$.
$x > y$ means that $x \geq y$ and $x \neq y$.
$x < y$ means that $x \leq y$ and $x \neq y$.
$ x < y \iff y > x \iff y - x > x - x = 0$.

Definition 2.2 (Positive and negative numbers)

Any number $x \in \RR$ satisfying $ x > 0$ is called a positive number.
Any number $x \in \RR$ satisfying $ x < 0$ is called a negative number.
Any number $x \in \RR$ satisfying $ x \geq 0$ is called a non-negative number.
Any number $x \in \RR$ satisfying $ x \leq 0$ is called a non-positive number.

Proposition 2.2

If $x + \epsilon \geq y$ for each $\epsilon > 0$, then $ x \geq y$ holds.

Proof. If the result doesn’t hold, then $x < y \implies y - x > 0$. Let $ \epsilon = \frac{1}{2} (y - x)$. Then $ x + \epsilon = \frac{1}{2} (x + y) \geq y$. This implies $ \frac{1}{2} ( y - x) \geq 0 \iff y - x < 0$, which is a contradiction.

Definition 2.3 (Absolute value)

The absolute value $| a |$ of a real number $a \in \RR$ is defined as follows. if $a \geq 0$, then $| a | = a$ and if $a < 0$, then $| a | = -a$. $a \vee b$ denotes the larger of the two numbers. $a \wedge b$ denotes the smaller of the two numbers.

Remark 2.1

Thus $| a | = a \vee (-a) \Forall a \in \RR$. Further $| a | = |-a |$.

Proposition 2.3

The absolute value satisfies following properties:

$| a | \geq 0$ for each $a \in \RR$, and $ | a | = 0 \iff a = 0$.
$ | a b | = | a | \cdot | b | \Forall a, b \in \RR$.
$ | a + b | \leq | a | + | b | \Forall a, b \in \RR$; the triangle inequality.

Proof. If $a=0$ then by definition $| a | = 0$. Again from definition, for any non-zero value, $| a |$ is not zero. Hence $ | a | = 0 \iff a = 0$.

Let $a$ and $b$ two non-negative numbers. Then $| a | = a$ and $ | b | = b$. Thus, $| a | | b | = a b = | a b | $. Further $| a | + | b | = a + b = | a + b |$.

Now, let $a$ and $b$ two non-positive numbers. Then $| a | = - a$ and $ | b | = - b$. $a b$ is non-negative, hence $| a b | = a b$. $a + b$ is non-positive, hence $| a + b | = - (a + b)$. Thus, $| a | | b | = (- a) ( - b) = a b = | a b | $. Further, $| a | + | b | = (-a) + (-b) = -(a + b) = | a + b |$.

Now lets consider when $a$ and $b$ are of opposite signs. WLOG (without loss of generality), let us assume that $a$ is positive and $b$ is negative. Further let us assume that $| a | \geq | b |$. Clearly, then $ | a + b | < | a | + | b |$. Also $| a b | = - a b = | a | | b |$.

Corollary 2.1

For $a , b \in \RR$ the following hold:

\[ | a - b | \leq | a | + | b |. \]

\[ | | a | - | b | | \leq | a - b |. \]

Proof. We know that

\[ | a + b | \leq | a | + | b |. \]

Replacing $b$ with $-b$ we get:

\[ | a - b | \leq | a | + | b |. \]

Again, replacing $b$ with $b - a$, we get:

\[ | a + b - a | \leq | a | + | b - a | \implies | b | - | a | \leq | a - b |. \]

Further, replacing $a$ with $a - b$ in $|a + b | \leq |a | + |b|$, we get:

\[ | a - b + b | \leq | a - b | + | b | \implies | a | - | b | \leq | a - b |. \]

Combining the two, we get our result.

Proposition 2.4 (Distance triangle inequality)

Let $ a, b, c \in \RR$. Then:

\[ | a - b | \leq | a - c | + | c - b |. \]

This is straight-forward application of Proposition 2.3.

\[ | a - c | + | c - b | \geq | (a - c) + (c - b) | = | a - b |. \]

Proposition 2.5

Two real numbers $a$ and $b$ are equal if and only if for every real number $\epsilon > 0$, $| a - b | < \epsilon$ holds.

Proof. If $a = b$, then $a - b = 0 \implies | a - b | = 0 < \epsilon$ for every $\epsilon > 0$. Now for the converse, we are given that for every $\epsilon > 0$, $| a - b | < \epsilon$. We have to show that $a = b$. Let as assume that $a \neq b$. Choose $\epsilon_0 = | a - b |$. Clearly, for $\epsilon_0 > 0$, $ | a - b | < \epsilon_0$ doesn’t hold. This contradicts our assumption that for every $\epsilon > 0$ $| a - b | < \epsilon$. Hence $a = b$.

2.1.3. Intervals#

Definition 2.4 (Interval)

A subset $S$ of $\RR$ is called an interval if for every $a,b \in S$ such that $a < b$, $S$ contains all the real numbers between $a$ and $b$. In other words, if $a < x < b$, then $x \in S$.

An open interval does not include its endpoints and is denoted as $(a,b) \triangleq \{ x \in \RR \ST a < x < b\}$.
A closed interval does not include its endpoints and is denoted as $[a,b] \triangleq \{ x \in \RR \ST a \leq x \leq b\}$.
A half-open interval includes one of its its endpoints : $[a,b) \triangleq \{ x \in \RR \ST a \leq x < b\}$; $(a,b] \triangleq \{ x \in \RR \ST a < x \leq b\}$.
A degenerate interval is an interval of the form $[a,a]$ which is a singleton containing $a \in \RR$.

2.1.4. Completeness Axiom#

Definition 2.5 (Upper and lower bounds)

Let $A$ be a nonempty subset of $\RR$.

An upper bound of $A$ is any $u \in \RR$ such that $ x \leq u \Forall x \in A$.
A lower bound of $A$ is any $ l \in \RR$ such that $ x \geq l \Forall x \in A$.
If $A$ has an upper bound it is said to be bounded from above.
If $A$ has a lower bound it is said to be bounded from below.
If $A$ is both bounded from above and below, then $A$ is said to be bounded.
A real number is called a least upper bound or supremum of $A$ if it is an upper bound of $A$, and it is less than or equal to every other upper bound of $A$. The least upper bound is denoted by $\sup (A)$.
A real number is called a greatest lower bound or infimum of $A$ if it is a lower bound of $A$, and it is greater than or equal to every other lower bound of $A$. The greatest lower bound is denoted by $\inf(A)$.

Remark 2.2

A set $A$ can have at most one least upper bound and at most one greatest lower bound.

Remark 2.3

The infimum or supremum of a set $A$ need not belong to the set itself.

The set $S = \{ x \ST 0 < x < 1\}$ has an infimum $0$ and a supremum $1$. Neither belong to the set.

The completeness axiom asserts that every nonempty set bounded from above has a least upper bound. We restate the axiom independently for emphasis.

Axiom 2.1 (Completeness axiom)

Every nonempty set of real numbers that is bounded from above has a least upper bound.

Example 2.1 (Least upper and greatest lower bounds)

Let

\[ A = \left \{ \frac{1}{n} : n \in \Nat \right \}. \]

The set is bounded from above with $\sup(A) = 1$. The set is bounded from below with $\inf(A) = 0$.

The open interval $(0, 2) = \{x \in \RR : 0 < x < 2 \}$ has lower and upper bounds as $0$ and $2$ respectively. So does the closed interval $[0, 2] = \{x \in \RR : 0 \leq x \leq 2 \}$. But $(0,2)$ has no maximum or minimum element. $[0,2]$ has both. Further, $(0,2]$ has maximum element but not minimum, and $[0,2)$ has minimum element but not maximum.

Example 2.2 (Distinction with rational numbers)

The set $S = \{ x \in \QQ : x^2 \leq 2\}$ doesn’t have a least upper bound in the set of rational numbers. For every $x \in S$, it is possible to find a $y \in \QQ$ such that $ y > x$ and $y^2 < 2$.

The axiomatic definition of real numbers claims that since the set $S = \{ x \in \RR : x^2 \leq 2\}$ is bounded from above, hence there exists a real number which is the least upper bound of this set. We simply denote this number as:

\[ \sqrt{2} \triangleq \sup \{ x \in \RR : x^2 \leq 2\}. \]

Corollary 2.2

Every nonempty set of real numbers that is bounded from below has a greatest lower bound.

Proof. Let $A \subset \RR$ be a nonempty set bounded from below. Consider the set of lower bounds for $A$ defined as

\[ B = \{b \in \RR : b \leq x \Forall x \in A \}. \]

Since $B$ is bounded from above by numbers in $A$, hence by completeness axiom, $B$ has a least upper bound denoted by $\sup (B)$. This indeed is the greatest lower bound of $A$ as $\sup (B) = \inf(A)$.

This result demonstrates that we only need an axiom for the least upper bound. The idea of existence of greatest lower bound immediately follows from it. We could have easily started with the existence of greatest lower bound as an axiom and derived the existence of least upper bound from it.

Remark 2.4

If a set $A$ has a maximum (resp. minimum) element, then $\max(A) = \sup (A)$ (resp. $\min(A) = \inf (A)$ ).

On the other hand, if the supremum of a set $A$ exists and $\sup (A) \in A$, then $\sup(A)$ is the maximum element of $A$. Similarly if the infimum of a set $A$ exists and $\inf(A) \in A$, then $\inf(A)$ is the minimum element of $A$.

Proposition 2.6

Assume that the supremum of a subset $A$ of $\RR$ exists. Then for every $\epsilon > 0$, there exists some $x \in A$ such that

\[ \sup (A) - \epsilon < x \leq \sup (A). \]

Conversely, let $a$ be an upper bound of $A \subseteq \RR$ such that for every $\epsilon > 0$, there exists an $x \in A$ such that $ a - \epsilon < x$, then $a$ is the least upper bound of $A$.

Proof. Clearly, if $x \in A$ then $ x \leq \sup (A)$. Now, if for every $x \in A$ we have $x \leq \sup (A) - \epsilon$, then $\sup (A) - \epsilon$ is an upper bound of $A$, which is less than the least upper bound. This is a contradiction. Thus, for every $\epsilon > 0$, there exists an $x \in A$ such that $\sup (A) - \epsilon < x \leq \sup (A)$.

Conversely, no matter how small $\epsilon > 0$ is chosen, $a - \epsilon$ cannot be an upper bound of $A$ since there exists some $x \in A$ such that $x > a - \epsilon$. Hence $a$ is indeed the least upper bound of $A$.

Proposition 2.7

Let $A$ and $B$ be two subsets of $\RR$ bounded above with $B \subseteq A$. Then

\[ \sup(B) \leq \sup(A). \]

Proof. Let $a$ be an upper bound of $A$. Then $a \geq x \Forall x \in A$. Since $B \subseteq A$, hence $a \geq y \Forall y \in B$ too. Thus, every upper bound of $A$ is also an upper bound of $B$. Thus, $\sup(A)$ is also an upper bound of $B$. Since $\sup(B)$ is least upper bound of $B$, it is smaller than or equal to any other upper bound of $B$. Thus $\sup(B) \leq \sup(A)$.

Proposition 2.8

The set of natural numbers $\Nat$ is unbounded.

Proof. Assume by contradiction that $\Nat$ is bounded. Since $\Nat \subset \RR$, hence by completeness axiom, there exists a least upper bound of $\Nat$. Let $s = \sup(\Nat)$. Then $ n \leq s \Forall n \in \Nat$. Then by Proposition 2.6, for $\epsilon = 1$ there exists some $k \in \Nat$ such that $ s - 1 < k$. This implies $ s < k+1$. Further since $s$ is the supremum, hence $ k + 1 \leq s$. Thus, $ s < k+1 \leq s$, which is impossible.

Proposition 2.9 (Nested interval property)

For each $n \in \Nat$, assume that we are given a closed interval $I_n = [a_n, b_n] = \{x \in \RR : a_n \leq x \leq b_n\}$. Assume also that each $I_n$ contains $I_{n + 1}$. Then, the resulting nested sequence of closed intervals

\[ I_1 \supseteq I_2 \supseteq \dots \supseteq I_n \supseteq I_{n + 1} \supseteq \dots \]

has a nonempty intersection; i.e.

\[ \bigcap_{n= 1}^{\infty} I_n \neq \EmptySet. \]

Proof. Consider the set of lower bounds

\[ A = \{ a_n : n \in \Nat \}. \]

Due to completeness axiom, the set has a least upper bound. Let $x = \sup (A)$. Further, due to nested structure, each $b_n$ is also an upper bound of $A$. Since $x$ is the least upper bound, hence $x \leq b_n \Forall n \in \Nat$. Thus, we have $a_n \leq x \leq b_n$ $\Forall n \in \Nat$. Hence, $x \in I_n \Forall n \implies x \in \bigcap_{n= 1}^{\infty} I_n$ .

2.1.5. Archimedian Property#

Proposition 2.10 (Archimedian property)

If $x$ and $y$ are two positive real numbers, then there exists some natural number $n$ such that $n x > y$.

Proof. For contradiction assume that $ n x \leq y$ holds for every $n \in \Nat$. Since, $x, y > 0$, $ n \leq y x ^{-1} \Forall n \in \Nat$. This contradicts Proposition 2.8.

This also tells us that for any real number $x > 0$, there exists an $n \in \Nat$ satisfying $\frac{1}{n} < x$. By choosing $y = 1$ in above, we get $n x > 1 \implies x > \frac{1}{n}$.

Example 2.3

Let $A = \{\frac{1}{n} : n \in \Nat \}$. We show that $\inf (A) = 0$. Clearly 0 is a lower bound. Now if $x > 0$ then we can find $n_0 \in \Nat$ such that $1/n_0 < x$. Thus $x > 0$ cannot be a lower bound of $A$. Hence $0$ is the greatest lower bound of $A$.

2.1.6. Rational Numbers#

Proposition 2.11 (Density of $\QQ$ in $\RR$)

Between any two distinct real numbers there exists a rational number.

Proof. Let $a$ and $b$ be the two distinct real numbers. If the two numbers are of opposite sign, then 0 is an obvious rational number between them. If $a$ and $b$ are both non-positive, then the rational number can be chosen to be the negative of the rational number between $-a$ and $-b$. We now consider the case where both $a$ and $b$ are non-negative. Without loss of generality, we assume that $0 \leq a < b$. Consider the set

\[ A = \left \{n \in \Nat : n > \max\left \{\frac{1}{b - a}, \frac{1}{b} \right \} \right \}. \]

Since $\Nat$ is not bounded from above, $A$ is nonempty. Fix an element $q \in A$. Clearly, $0 < \frac{1}{q} < b - a$ and $ 1 < b q$. Now, let

\[ B = \{n \in \Nat : n < b q \}. \]

Since $1 \in B$, B is nonempty. Also, $B$ is a finite set. Let $p = \max (B)$. Clearly, $p \in B$ and $p + 1 \notin B$.

Finally, we will show that $ a < \frac{p}{q} < b$. Since $p \in B$, $ p < b q \implies \frac{p}{q} < b$. Further,

\[ p + 1 \geq b q \implies b \leq \frac{p}{q} + \frac{1}{q} < \frac{p}{q} + b - a \implies a < \frac{p}{q}. \]

Proposition 2.12

There exists a real number $\alpha \in \RR$ satisfying $\alpha^2 = 2$.

Proof. Consider the set

\[ A = \{ x \in \RR : x^2 < 2 \}. \]

Clearly, A is bounded above. Now, choose $\alpha = \sup(A)$. We show that $\alpha^2 = 2$ by ruling out $\alpha^2 < 2$ and $\alpha^2 > 2$. Assume that $\alpha^2 < 2$. Consider for some $n \in \Nat$:

\[\begin{split} \left ( \alpha + \frac{1}{n}\right )^2 &= \alpha^2 + \frac{2 \alpha}{n} + \frac{1}{n^2}\\ &< \alpha^2 + \frac{2 \alpha}{n} + \frac{1}{n}\\ & = \alpha^2 + \frac{2 \alpha + 1}{n}. \end{split}\]

Now choose $n_0 \in \Nat$ large enough so that

\[ \frac{1}{n_0} < \frac{2 - \alpha^2}{ 2 \alpha + 1}. \]

This implies $\frac{2 \alpha + 1}{n_0} < 2 - \alpha^2$. Thus,

\[ \left ( \alpha + \frac{1}{n_0}\right )^2 < \alpha^2 + (2 - \alpha^2) = 2. \]

Thus $\alpha + \frac{1}{n_0} \in A$ contradicting the assumption that $\alpha^2$ is an upper bound of $A$. Hence $\alpha^2 < 2$ is not possible.

Now assuming $\alpha^2 > 2$, we show that it cannot be the least upper bound of $A$. We start with

\[\begin{split} \left ( \alpha - \frac{1}{n}\right )^2 &= \alpha^2 - \frac{2 \alpha}{n} + \frac{1}{n^2}\\ & > \alpha^2 - \frac{2 \alpha}{n}. \end{split}\]

Choosing $n_0 > 2 \alpha / (\alpha^2 - 2)$, we get $\frac{2 \alpha}{n_0} < \alpha^2 - 2$. Thus

\[ \left ( \alpha - \frac{1}{n_0}\right )^2 > \alpha^2 - (\alpha^2 - 2) = 2. \]

Thus $\left ( \alpha - \frac{1}{n_0}\right )^2$ is also an upper bound of $A$. But

\[ \left ( \alpha - \frac{1}{n_0}\right )^2 < \alpha^2. \]

Hence, $\alpha^2$ cannot be the least upper bound of $A$. Thus, $\alpha^2 > 2$ is not possible. Since for every real number $\alpha^2$, exactly one of the possibilities $\alpha^2 < 2$, $\alpha^2 > 2$ or $\alpha^2 = 2$ has to be true, hence $\alpha^2 = 2$.

2.1.7. Irrational Numbers#

Definition 2.6 (Irrational number)

A real number which is not rational is known as irrational number. The set of irrational numbers is denoted by $\II$.

Clearly, $\II = \RR \setminus \QQ$. Also, $\RR = \QQ \cup \II$. Although $\QQ$ forms a field, but $\II$ does not. For example $\sqrt{2} \times \sqrt{2} = 2$ is rational. Thus $\II$ is not closed under multiplication. Further, $0$ and $1$ (the additive and multiplicative identities) don’t belong to $\II$.

Proposition 2.13

The sum of a rational and an irrational number is irrational. The product of a non-zero rational number and an irrational number is irrational.

Proof. Let $q \in \QQ$ and $i \in \II$. Let $r = q + i$. Then $i = r - q$. If $r$ were rational, then $i$ would have to be rational (since $\QQ$ is closed under addition). But $i$ is irrational, hence $r$ is irrational.

Now let $q \neq 0$. Let $r = q i$. Then $i = r / q$. If $r$ were rational, then $i$ would have to be rational since $\QQ$ is closed under multiplication.

Proposition 2.14 (Density of $\II$ in $\RR$)

Between any two distinct real numbers there exists an irrational number.

Proof. Let $a, b \in \RR$. Without loss of generality, assume $a < b$. Consider the numbers: $a - \sqrt{2}, b - \sqrt{2}$. Since $\QQ$ is dense in $\RR$ (Proposition 2.11), there exists a rational number $q$ such that

\[ a - \sqrt{2} < q < b - \sqrt{2}. \]

Clearly $a < q + \sqrt{2} < b$. But by Proposition 2.13, $q + \sqrt{2}$ is irrational. This completes the proof.

Proposition 2.15 (Existence of roots)

For a real number $a$ and any natural number $n \geq 2$, we have the following:

If $a \geq 0$ and $n$ is even, there exists a unique $b \geq 0$ such that $ b^n = a$.
If $a \in \RR$ and $n$ is odd, then there exists a unique $b \in \RR$ such that $b^n = a$.

2.1.8. Uncountability#

Proposition 2.16

The set $\RR$ is uncountable.

Proof. Assume that $\RR$ is countable. Then it is possible to enumerate $\RR$ as $\RR = \{ x_1, x_2, \dots \}$. Consider a closed interval $I_1$ which doesn’t contain $x_1$. Further, consider a second closed interval $I_2 \subseteq I_1$ which doesn’t contain $x_2$. If $I_1 = [a, b]$, then by choosing $c_1 = (a + b) / 3$, and $c_2 = 2 (a + b) / 3$, we get disjoint closed sub-intervals $[a, c_1]$ and $[c_2, b]$. $x_2$ can lie in at most one of them, hence it is always possible to choose $I_2 \subseteq I_1$ as desired. Now given $I_n$ has been chosen, choose $I_{n + 1}$ such that:

$I_{n + 1} \subseteq I_n$ and
$x_{n + 1} \notin I_{n + 1}$.

Now, consider the countable intersection of nested closed sets

\[ I = \bigcap_{n = 1}^{\infty} I_n. \]

If $x_i \in \RR$ (as an element in the enumeration of $\RR$), then $x_i \notin I_i$. Thus $x_i \notin I$. Thus, if $\RR$ is countable, then no real number lies in $I$. But by nested interval property, $I$ is not empty. This contradicts our assumption that $\RR$ is countable.

Corollary 2.3

The set of irrational numbers is uncountable.

Proof. If $\II$ were countable, then $\RR = \QQ \cup \II$ would also be countable. But this is not true. Hence $\II$ is uncountable.

2.1.9. Algebraic Numbers#

Definition 2.7 (Algebraic real number)

A real number is called algebraic if it is the root of a polynomial with integer coefficients. i.e. $x \in \RR$ is algebraic if there exist integers $a_0, a_1, \dots, a_n \in \ZZ$, not all zero, such that

\[ a_n x^n + a_{n -1} x^{n - 1} + \dots + a_1 x + a_0 = 0. \]

Example 2.4 (Algebraic real numbers)

$\sqrt{2}$ is algebraic since it is the root of the equation $x^2 - 2 = 0$.
$\sqrt[3]{2}$ is algebraic since it is the root of the equation $x^3 - 2 = 0$.
$\sqrt{2} + \sqrt{3}$ is algebraic since it is the root of the equation $x^4 - 10 x^2 + 1 = 0$.

Proposition 2.17

The set of algebraic numbers is countable.

Proof. Let $n \in \Nat$. Let $A_n$ be the algebraic numbers obtained as roots of polynomials with integer coefficients that have degree $n$ given by

\[ a_n x^n + a_{n -1} x^{n - 1} + \dots + a_1 x + a_0 = 0. \]

Each polynomial can be represented by an $n+ 1$-tuple given by

\[ (a_n, a_{n-1}, \dots, a_1, a_0). \]

Thus, it has a one-one correspondence with the Cartesian product $\ZZ^{n+ 1}$. Since finite Cartesian product of countable sets is countable, hence $\ZZ^{n + 1}$ is countable. This means that the number of polynomials of order $n$ is countable. Since each polynomial of order $n$ can have at most $n$ roots, hence $A_n$ is countable.

Now consider the union

\[ A = \bigcup_{n= 1}^{\infty} A_n \]

as the set of algebraic numbers. Since union of a countable family of countable sets is countable, hence $A$ is countable.

2.1.10. Transcendental Numbers#

Definition 2.8 (Transcendental numbers)

A real number is called transcendental if it is not algebraic.

Proposition 2.18 (Existence of transcendental numbers)

Transcendental numbers exist and they are uncountable.

Proof. Let $A$ denote the set of algebraic numbers and $B$ denote the set of transcendental numbers. Then $\RR = A \cup B$. Since $A$ is countable and $\RR$ is uncountable, hence $B$ is non-empty and is uncountable.

2.1.11. Intervals are Uncountable#

Proposition 2.19

The open interval $(0, 1) = \{x \in \RR : 0 < x < 1 \}$ is uncountable.

Proof. Assume that $(0, 1)$ is countable. Then, the numbers $x \in (0, 1)$ can be enumerated. Let $f : \Nat \to (0, 1)$ be such an enumeration. Let $f(m)$ be given by (in the decimal representation)

\[ f(m) = .a_{m 1} a_{m 2} \dots. \]

Define a real number $x \in (0, 1)$ with the decimal expansion

\[ x = . b_1 b_2 \dots \]

using the rule:

\[\begin{split} b_n = \left\{ \begin{array}{ll} 2 & \mbox{if $a_{n n} \neq 2$};\\ 3 & \mbox{if $a_{n n} = 2$}. \end{array} \right. \end{split}\]

The number $x$ cannot be $f(1)$ since $b_1 \neq a_{11}$. The number $x$ cannot be $f(n) \Forall n \in \Nat$ since $b_n \neq a_{n n}$. Thus $x$ doesn’t belong to the suggested enumeration of $(0, 1)$. Thus, $(0, 1)$ is uncountable.

Proposition 2.20

$(0, 1)$ is uncountable if and only if $\RR$ is uncountable.

Proof. If $\RR$ were countable, then $(0, 1)$ would be countable since $(0, 1) \subset \RR$. Thus, $(0, 1)$ can be uncountable only if $\RR$ is uncountable.

Now if $(0, 1)$ were countable then $\RR$ would be countable since $\RR$ can be written as

\[ \RR = \bigcup_{n = -\infty}^{\infty} (n, n + 1) \cup \ZZ. \]

Every open interval $(n, n + 1)$ has the same cardinality as $(0, 1)$ and $\ZZ$ is countable. Thus, $\RR$ is uncountable only if $(0, 1)$ is uncountable. In other words, $(0, 1)$ is uncountable if $\RR$ is uncountable.

Topics in Signal Processing

Real Line

Contents

2.1. Real Line#

2.1.1. Prelude#

2.1.2. Real numbers#

2.1.3. Intervals#

2.1.4. Completeness Axiom#

2.1.5. Archimedian Property#

2.1.6. Rational Numbers#

2.1.7. Irrational Numbers#

2.1.8. Uncountability#

2.1.9. Algebraic Numbers#

2.1.10. Transcendental Numbers#

2.1.11. Intervals are Uncountable#