Cantor’s diagonal argument is a purported proof that there are infinite sets which cannot be put into one-to-one correspondence with the natural numbers: 1,2,3, and so on. It is named after the mathematician Georg Cantor who published it in 1891. The argument runs as follows. Let S be the set of all infinite sequences of binary digits (i.e. each digit is 0 or 1) and let (s1,s2,s3,…) be a sequence of elements of S. Next, let s be the sequence whose nth digit is complementary to the nth element of the sequence sn. By construction, s is a member of S that differs from each element in the sequence (s1,s2,s3,…) since their nth digits differ. As the sequence (s1,s2,s3,…) was arbitrary, it follows that the set S cannot be put into one-to-one correspondence with the natural numbers.
In a recent YouTube video, the Scottish Marxist and computer scientist Paul Cockshott claims to have refuted Cantor’s proof. His argument runs as follows. Let sn be the sequence with digits equal to the digits in the binary representation of the natural number n-1 but placed in reverse order, so that s1 = (0,0,0,…), s2 = (1,0,0,…), s3 = (0,1,0,…), s4 = (1,1,0,…), s5 = (0,0,1,…), s6 = (1,0,1,…), and so on. Next, let sn be the sequence whose ith digit is complementary to the ith digit of the sequence sn for i ≤ n, and equal to 0 for i > n. Cockshott shows that for each n, the sequence sn belongs to the sequence (s1,s2,s3,…). This is clearly true for the first few values of n as s1 = (1,0,0,…) = s2, s2 = (0,1,0,…) = s3, and s3 = (0,0,1,…) = s5. Cockshott demonstrates by induction that this holds for arbitrary n.
So does this mean that Cockshott has refuted Cantor’s celebrated proof from over a century ago? Well, no. What Cockshott has actually demonstrated is that some of the rational numbers in the interval [0,1] can be placed into a one-to-one correspondence with the natural numbers. To see this, note s1 may be associated with the rational number 0, s2 with the binary rational number 0.1, s3 with the binary rational number 0.01, and so on. It is not difficult to see that every element of in the sequence (s1,s2,s3,…) can be associated with a rational number – that is, a number with a terminating binary expansion – in the interval [0,1]. But mathematicians have known since the time of Cantor that the rational numbers can be placed into a one-to-one correspondence with the natural numbers.
However, Cockshott’s alleged proof raises an interesting point about the real numbers. These numbers may be divided into two groups. The first group contains the rational numbers: those which can be represented as a/b where a and b are natural numbers; or equivalently, those with a terminating or repeating binary (or decimal) expansion. The second group contains the irrational numbers: those which can be represented as a/b where a and b are natural numbers; or equivalently, those with a non-terminating or non-repeating binary (or decimal) expansion. As already noted, the rational numbers can be placed into a one-to-one correspondence with the natural numbers, whereas the irrational numbers – and therefore, the real numbers – cannot.
Another thing that distinguishes the rationals from the irrationals is that the former can be constructed using a finite number of steps, whereas the latter cannot. Most mathematicians do not have any problem with things that cannot be constructed using a finite number of steps and are therefore perfectly happy to accept the existence of irrational numbers. However, there is a philosophy of mathematics known as finitism which only accepts the existence of finite mathematical objects – or equivalently, mathematical objects that can be constructed from other mathematical objects using a finite number of steps. According to this philosophy, infinite sets do not exist, and neither do irrational numbers.
I’m sure most mainstream mathematicians would scoff at the idea that irrational numbers do not exist. After all, many of the most ubiquitous constants in mathematics – √2, e, π, and so on – are irrational. Does it really make sense to say that these numbers are just figments of our collective imagination?! I would argue that it does, for the simple reason that irrational number such as √2, e, and π never occur in the natural world. How could they when they require an infinite number of steps to construct? What we actually find in the natural world are numbers very close to √2, e, and π, but never exactly equal to them. For example, the diagonal of a 1×1 square is never equal to √2 exactly, although it may come very close to it.
I am not the only one who is suspicious of irrational numbers. The Greek mathematician Pythagoras – he of the eponymous theorem – taught his followers that everything in the universe could be written as a natural number or a ratio of natural numbers. When a his contemporary Hippasus used geometry to prove that √2 could never be written as a fraction, Pythagoras’s followers took Hippasus out to sea and drowned him (at least, according to legend). Whilst I wouldn’t advocate following this approach – the philosophy of mathematics isn’t that important – I do think Pythagoras was on to something when he said that everything in the universe could be written as a rational number. We could even go so far as to say that Pythagoras was the first finitist mathematician.
Groucho Marxism 
Leave a comment