Simanaitis Says

On cars, old, new and future; science & technology; vintage airplanes, computer flight simulation of them; Sherlockiana; our English language; travel; and other stuff

YOU CAN COUNT ON ME—OR MAYBE NOT

COUNTING SEEMS the most basic of mathematics, so isn’t it puzzling that lots of things are genuinely uncountable? To make any sense of this, let’s begin with the essence of countability, then travel into the realm of the uncountable, and tip-toe into an infinity of infinities. Our journey starts with Homer’s Cyclops and ends with a comedy routine involving English philosopher Bertrand Russell.

Homer, left; Polyphemus, a Cyclops, pre-Odysseus, right. Images from the British Museum and Greek myth.

It is a commentary on our times that Googling “Homer” gives thousands more Simpsons than the Greek story teller. In the Homeric Odyssey, its hero Odysseus contests with Polyphemus, a Cyclops. Odysseus wins, leaving the one-eyed giant blinded. (See “Flabby Fun with the Word ‘Only’ “ for a spin on this.)

The blind Polyphemus devises a clever means of tending his flock of ewes. In the morning, Polyphemus picks up a pebble as he allows each ewe to leave his cave. In the evening, he discards a pebble as a ewe is readmitted.

Thus, Polyphemus identified the essence of countability: a one-to-one matching of two collections. Formally, thousands of years later, we call a set of things countable if there’s a one-to-one correspondence between its elements and some or all of the natural numbers, 1, 2, 3, ….

Countable sets can be finite like Polyphemus’ flock, or infinite like N itself, the totality of natural numbers. In fact, infinitude gives rise to subtleties in cardinality, the counting of things.

Arnold Schwarzenegger, left; Albert Einstein, right. Will the infinite counter please stand up.

Infinite countability can have nothing to do with a counter’s stamina. Otherwise, Arnold Schwarzenegger would be a better mathematician than Albert Einstein. Rather, it’s a matter of establishing that one-to-one correspondence with N.

A subtlety: Consider the set of integers, I, consisting of 0, 1, -1, 2, -2, 3, -3, …. Intuition suggests the cardinality of I is “twice as many, plus 1” as N, the natural numbers. However, it’s easy to devise a one-to-one correspondence between the two collections. And, thus, there are just as many natural numbers as there are integers, “countably many.”

Yet another: The set Q of rational numbers, i.e, fractions, anything of the form n/m, is also countable. Loosely, here’s the beginning of a correspondence of Q with N that works:  0, 1, -1, 2, -2, 1/2, -1/2, 3, -3, 1/3, -1/3, 2/3, -2/3, 4, -4, 1/4, -1/4, 3/4, -3/4, 4/3, -4/3, 5, -5, …. Notice, there’s no need to include 2/4 because it’s already counted as 1/2.

R, the real number line.

What about R, the real numbers, all the points of a line extending infinitely in either direction? Curiously, Q is dense in R; that is, anywhere in the real numbers, you’re never very far from a rational. However, it’s one of the 19th century’s mathematical discoveries that R is uncountable.

Georg Cantor, 1845 – 1918, German mathematician, discoverer of set theory and of the uncountability of the real number line.

In the 1870s, German mathematician Georg Cantor formalized ideas of one-to-one correspondence, countability and cardinality. His discoveries unsettled everyone—including himself. He wrote to a colleague, “Je le vois, mais je ne le crois pas!” (I see it, but I don’t believe it!)

Cantor used a clever indirect means to prove that R is uncountable: Assume the contrary, and show this leads to a contradiction. Assume that you can arrange a matching between N and all the elements of R. Then he shows how to construct a new real number, thus reaching a contradiction.

Cantor’s Diagonalization. Ginning up a new real number, given some ordering of the reals, rn.

A bit more formally, suppose r1, r2, r3, … is a listing of all the real numbers. Then, for the devised number s, choose its first digit d1 that’s different from the first decimal digit of r1; thus s is different from r1. Choose its second digit d2 to be different from the second digit of r2; thus, s differs from either r1 or r2.

Continue, and the number s will be different from anything in the listing because its nth digit is different from that of rn, thus contradicting the totality of the assumed listing. Neat, eh?

Cantor defined different levels of uncountability, an infinity of infinities. He also proposed the Continuum Hypothesis, that there are no cardinalities, no “how manys,” between those of N and R.

He never proved this hypothesis. In fact, no one has. One of the closest discoveries was offered in 1925, with the Incompleteness Theorems of Kurt Gödel. An implication of Gödel’s work, loosely, is that the Continuum Hypothesis is neither provable nor unprovable, that is, it’s undecidable.

Not unrelated to this is Russell’s Paradox (my double negative chosen purposely to prepare for further obscurity). Notes The Princeton Companion to Mathematics, 2008, “… loose talk about all sets of certain kinds causes real difficulties: for example, Russell’s paradox of the set of all sets that are not members of themselves (if it is a member of itself, then it is not, but if it is not, then it is.)”

Bertrand Russell, 1872 – 1970, English philosopher, logician, mathematician, social critic, political activist.

For wonderful insight into the intellectual quandaries that await anyone probing uncountability further, check out “Jonathan Miller As Bertrand Russell.” ds