Proposition 1.4.1.
A set \(I \subset \R\) is an interval if and only if \(I\) contains at least 2 points and for all \(a,c \in I\) and \(b \in \R\) such that \(a < b < c\text{,}\) we have \(b \in I\text{.}\)
Section 1.4 Intervals and the size of \(\R\)
Note: 0.5–1 lecture (proof of uncountability of \(\R\) can be optional)
You surely saw the notation for intervals before, but let us give a formal definition here. For \(a, b \in \R\) such that \(a < b\text{,}\) we define
\begin{equation*}
\begin{aligned}
& [a,b] \coloneqq \{ x \in \R : a \leq x \leq b \}, \\
& (a,b) \coloneqq \{ x \in \R : a < x < b \}, \\
& (a,b] \coloneqq \{ x \in \R : a < x \leq b \}, \\
& [a,b) \coloneqq \{ x \in \R : a \leq x < b \} .
\end{aligned}
\end{equation*}
The interval \([a,b]\) is called a closed interval and \((a,b)\) is called an open interval. The intervals of the form \((a,b]\) and \([a,b)\) are called half-open intervals.
The intervals above are bounded intervals, since both \(a\) and \(b\) are real numbers. We define unbounded intervals,
\begin{equation*}
\begin{aligned}
& [a,\infty) \coloneqq \{ x \in \R : a \leq x \}, \\
& (a,\infty) \coloneqq \{ x \in \R : a < x \}, \\
& (-\infty,b] \coloneqq \{ x \in \R : x \leq b \}, \\
& (-\infty,b) \coloneqq \{ x \in \R : x < b \} .
\end{aligned}
\end{equation*}
For completeness, we define \((-\infty,\infty) \coloneqq \R\text{.}\) The intervals \([a,\infty)\text{,}\) \((-\infty,b]\text{,}\) and \(\R\) are sometimes called unbounded closed intervals, and \((a,\infty)\text{,}\) \((-\infty,b)\text{,}\) and \(\R\) are sometimes called unbounded open intervals.
The proof of the following proposition is left as an exercise. In short, an interval is a set with at least two points that contains all points between any two points. 1
We have already seen that every open interval \((a,b)\) (where \(a < b\) of course) must be nonempty. For example, it contains the number \(\frac{a+b}{2}\text{.}\) An unexpected fact is that from a set-theoretic perspective, all intervals have the same “size,” that is, they all have the same cardinality. For instance, the map \(f(x) \coloneqq 2x\) takes the interval \([0,1]\) bijectively to the interval \([0,2]\text{.}\)
Maybe more interestingly, the function \(f(x) \coloneqq \tan(x)\) is a bijective map from \((-\nicefrac{\pi}{2},\nicefrac{\pi}{2})\) to \(\R\text{.}\) Hence the bounded interval \((-\nicefrac{\pi}{2},\nicefrac{\pi}{2})\) has the same cardinality as \(\R\text{.}\) It is not completely straightforward to construct a bijective map from \([0,1]\) to \((0,1)\text{,}\) but it is possible.
And do not worry, there does exist a way to measure the “size” of subsets of real numbers that “sees” the difference between \([0,1]\) and \([0,2]\text{.}\) However, its proper definition requires much more machinery than we have right now.
Let us say more about the cardinality of intervals and hence about the cardinality of \(\R\text{.}\) We have seen that there exist irrational numbers, that is \(\R \setminus \Q\text{,}\) is nonempty. The question is: How many irrational numbers are there? It turns out there are a lot more irrational numbers than rational numbers. We have seen that \(\Q\) is countable, and we will show that \(\R\) is uncountable. In fact, the cardinality of \(\R\) is the same as the cardinality of \(\sP(\N)\text{,}\) although we will not prove this claim here.
Theorem 1.4.2. Cantor.
\(\R\) is uncountable.
We give a version of Cantor’s original proof from 1874 as this proof requires the least setup. Normally this proof is stated as a contradiction, but a proof by contrapositive is easier to understand.
Proof.
Let \(X \subset \R\) be a countably infinite subset such that for every pair of real numbers \(a < b\text{,}\) there is an \(x \in X\) such that \(a < x < b\text{.}\) Were \(\R\) countable, we could take \(X = \R\text{.}\) We will show that \(X\) is necessarily a proper subset, and so \(X\) cannot equal \(\R\text{,}\) and \(\R\) must be uncountable.
As \(X\) is countably infinite, there is a bijection from \(\N\) to \(X\text{.}\) We write \(X\) as a sequence of real numbers \(x_1, x_2, x_3,\ldots\text{,}\) such that each number in \(X\) is given by \(x_n\) for some \(n \in \N\text{.}\)
We inductively construct two sequences of real numbers \(a_1,a_2,a_3,\ldots\) and \(b_1,b_2,b_3,\ldots\text{.}\) Let \(a_1 \coloneqq x_1\) and \(b_1 \coloneqq x_1+1\text{.}\) Note that \(a_1 < b_1\) and \(x_1 \notin (a_1,b_1)\text{.}\) For some \(k > 1\text{,}\) suppose \(a_1,a_2,\ldots,a_{k-1}\) and \(b_1,b_2,\ldots,b_{k-1}\) have been defined, suppose \(a_1 < a_2 < \cdots < a_{k-1} < b_{k-1} < \cdots < b_2 < b_1\text{,}\) and suppose for each \(j=1,2,\ldots,k-1\text{,}\) we have \(x_\ell \notin (a_{j},b_{j})\) for \(\ell=1,2,\ldots,j\text{.}\)
- Define \(a_k \coloneqq x_n\text{,}\) where \(n\) is the smallest \(n \in \N\) such that \(x_n \in (a_{k-1},b_{k-1})\text{.}\) Such an \(x_n\) exists by our assumption on \(X\text{,}\) and \(n \geq k\) by the assumption on \((a_{k-1},b_{k-1})\text{.}\)
- Next, define \(b_k\) to be some real number in \((a_{k},b_{k-1})\text{.}\)
Notice that \(a_{k-1} < a_k < b_k < b_{k-1}\text{.}\) Also notice that \((a_{k},b_{k})\) does not contain \(x_k\) and hence does not contain \(x_j\) for \(j=1,2,\ldots,k\text{.}\) The two sequences are now defined.
Claim: \(a_n < b_m\) for all \(n\) and \(m\) in \(\N\text{.}\) Proof: Let us first assume \(n < m\text{.}\) Then \(a_n < a_{n+1} < \cdots < a_{m-1} < a_m < b_m\text{.}\) Similarly for \(n > m\text{.}\) The claim follows.
Let \(A \coloneqq \{ a_n : n \in \N \}\) and \(B \coloneqq \{ b_n : n \in \N \}\text{.}\) By Proposition 1.2.7 and the claim above,
\begin{equation*}
\sup\, A \leq \inf\, B .
\end{equation*}
Define \(y \coloneqq \sup\, A\text{.}\) The number \(y\) cannot be a member of \(A\text{:}\) If \(y = a_n\) for some \(n\text{,}\) then \(y < a_{n+1}\text{,}\) which is impossible. Similarly, \(y\) cannot be a member of \(B\text{.}\) Therefore, \(a_n < y\) for all \(n\in \N\) and \(y < b_n\) for all \(n\in \N\text{.}\) In other words, for every \(n \in \N\text{,}\) we have \(y \in (a_n,b_n)\text{.}\) By the construction of the sequence, \(x_n \not\in (a_n,b_n)\text{,}\) and so \(y \not= x_n\text{.}\) As this was true for all \(n \in \N\text{,}\) we have that \(y
\not\in X\text{.}\)
We have constructed a real number \(y\) that is not in \(X\text{,}\) and thus \(X\) is a proper subset of \(\R\text{.}\) The sequence \(x_1,x_2,\ldots\) cannot contain all elements of \(\R\) and thus \(\R\) is uncountable.
Subsection 1.4.1 Exercises
Exercise 1.4.1.
For \(a < b\text{,}\) construct an explicit bijection from \((a,b]\) to \((0,1]\text{.}\)
Exercise 1.4.2.
Suppose \(f \colon [0,1] \to (0,1)\) is a bijection. Using \(f\text{,}\) construct a bijection from \([-1,1]\) to \(\R\text{.}\)
Exercise 1.4.3.
Prove Proposition 1.4.1. That is, suppose \(I \subset \R\) is a subset with at least 2 elements such that if \(a < b < c\) and \(a, c \in I\text{,}\) then \(b \in I\text{.}\) Prove that \(I\) is one of the nine types of intervals explicitly given in this section. Furthermore, prove that the intervals given in this section all satisfy this property.
Exercise 1.4.4.
(Hard) Construct an explicit bijection from \((0,1]\) to \((0,1)\text{.}\) Hint: One approach is as follows: First map \((\nicefrac{1}{2},1]\) to \((0,\nicefrac{1}{2}]\text{,}\) then map \((\nicefrac{1}{4},\nicefrac{1}{2}]\) to \((\nicefrac{1}{2},\nicefrac{3}{4}]\text{,}\) etc. Write down the map explicitly, that is, write down an algorithm that tells you exactly what number goes where. Then prove that the map is a bijection.
Exercise 1.4.5.
(Hard) Construct an explicit bijection from \([0,1]\) to \((0,1)\text{.}\)
Exercise 1.4.6.
- Show that every closed interval \([a,b]\) is the intersection of countably many open intervals.
- Show that every open interval \((a,b)\) is a countable union of closed intervals.
- Show that an intersection of a possibly infinite family of bounded closed intervals, \(\bigcap\limits_{\lambda \in I} [a_\lambda,b_\lambda]\text{,}\) is either empty, a single point, or a bounded closed interval.
Exercise 1.4.7.
Suppose \(S\) is a set of disjoint open intervals in \(\R\text{.}\) That is, if \((a,b) \in S\) and \((c,d) \in S\text{,}\) then either \((a,b) = (c,d)\) or \((a,b) \cap (c,d) = \emptyset\text{.}\) Prove \(S\) is a countable set.
Exercise 1.4.8.
Prove that the cardinality of \([0,1]\) is the same as the cardinality of \((0,1)\) by showing that \(\abs{[0,1]} \leq \abs{(0,1)}\) and \(\abs{(0,1)} \leq \abs{[0,1]}\text{.}\) See Definition 0.3.28. This proof requires the Cantor–Bernstein–Schröder theorem, which we stated without proof. Note that this proof does not give you an explicit bijection.
Exercise 1.4.9.
(Challenging) A number \(x\) is algebraic if \(x\) is a root of a polynomial with integer coefficients, in other words, \(a_n x^n + a_{n-1} x^{n-1} + \cdots
+ a_1 x + a_0 = 0\) where \(a_0,a_1,\ldots,a_n \in \Z\text{.}\)
- Show that there are only countably many algebraic numbers.
- Show that there exist non-algebraic (transcendental) numbers (follow in the footsteps of Cantor, use the uncountability of \(\R\)).
Hint: Feel free to use the fact that a polynomial of degree \(n\) has at most \(n\) real roots.
Exercise 1.4.10.
(Challenging) Let \(F\) be the set of all functions \(f \colon \R \to \R\text{.}\) Prove \(\abs{\R} < \abs{F}\) using Cantor’s Theorem 0.3.34. 2
Sometimes single point sets and the empty set are also called intervals, but in this book, intervals have at least 2 points. That is, we only defined the bounded intervals if \(a < b\text{.}\)
Interestingly, if \(C\) is the set of continuous functions, then \(\abs{\R} = \abs{C}\text{.}\)
