Lesson 1

In this section, we will show that not all infinite sets are countable. We will prove, in particular, that the set of real numbers is uncountable.

Let's first discuss a technical nuance related to real numbers. Some real numbers can be written in two ways: for example, \(0{,}7=0{,}69999\dotsc\) and \(1=0{,}9999\dotsc\). But each positive real number has a unique infinite (decimal) representation. The same is true for binary (rather than decimal) representations. Specifically, each number \(0 < x \le 1\) can be represented as an infinite binary fraction: the first bit (after the decimal point) is zero if \(0 < x \le 1/2\), and it is one otherwise. The next bit is determined by which half of the new interval \(x\) lies in. And again, some numbers will have two representations (for example, \(\frac{3}{8}= 0{,}011 = 0{,}0101111\dotsc\)), but each number will have a unique infinite representation (we consider a representation with an infinite number of zeros at the end to be finite).