Skip to main content

Cantor's diagonalization argument

Kurt gödel.jpg

Yesterday's post as gotten me into one of my rare stern-logician frames of mind, so I think I'll stick with that today.

I wonder if I've ever discussed Cantor's "diagonal" proof in my blogging. If not, I'll make good on that now. Cantor refuted the common idea that "infinity" is a single all-inclusive category. Once we get beyond enumeration we've gotten to "infinity" and there is nothing more to be said. Or, at least, so we're inclined to think.

Yes there is, though, Cantor replies, much more to be said. Because for example not every infinity is equal to every other. Some "trans-finite" numbers are bigger than others. The number of real numbers is a larger transfinite number than the number of integers.

Why? Well, diagonals! The question is -- could we in principle create a one-to-one correspondence between every real number and every integer that would allow room for every one of each to show up, eventually, corresponding to the other? No answer is "no," because a skeptic about the value of our correspondence could always use a diagonal technique to prove its incompleteness.

So our effort at demonstrating correspondence may include this:

1 ~ 0.1254364
2 ~ 0.1254372
3 ~ 0.1297478
4 ~ 0.1597523
5 ~ 0.2145678
6 ~ 0.2732589
7 ~ 0.3001233
8 ~ 0.3112589

 Now obviously there is an arbitrary seeming starting point and there are gaps in the list of reals numbers and there are no gaps in the list on the left hand side of the page of the list of integers. That will always be the case. BUT we might suppose that our theorist claims he has a system that will allow the ordering to double back (and triple back ...) and fill in all those gaps in the fullness of time as the infinite scroll unrolls.

The skeptic will reply, "no you don't either." because  we can always look at the list diagonally and create a number in which the Nth digit of our new number is different from the corresponding Nth digit of the Nth number on the list.

Looking at the above list diagonally as indicated by the bold facing gives us this: 0.1295539. So in the corresponding number we construct, the first digit would be any digit OTHER THAN 0. The second digit would be anything OTHER THAN 1, the third digit OTHER THAN 2 and so forth. We could end up with this


Which, you'll notice, is not on the list. The point is that however long the list is, and whatever method is used to create it, it will always be possible to defeat the real or alleged system by creating, through such a diagonalization, a number that differs from each digit of the official list in at least one spot, the Nth spot, defined by that official digit's place in the ordering.

For a much better explanation, get George Gamow's book, One, Two, Three ... Infinity, and turn to page 20.

Why should we care that there are trans-finite numbers of different values? Because this diagonal proof has proven fruitful, indeed foundational in a lot of subsequent developments, including the "Turing Halting Problem" in computer science, and the Gödel Incompleteness Theorem showing the limits of formal logic itself.                             

As a convenient parting thought, let's remember that one of the most important places in the magical world of Harry Potter, the street with all the shops where he buys magic books and wands and such school supplies, is called "Diagon Alley," which is pronounced a lot like "diagonally." A magical place, indeed!

That's Kurt Gödel above, though his glasses look a bit like Harry's.


Popular posts from this blog

England as a Raft?

In a lecture delivered in 1880, William James asked rhetorically, "Would England ... be the drifting raft she is now in European affairs if a Frederic the Great had inherited her throne instead of a Victoria, and if Messrs Bentham, Mill, Cobden, and Bright had all been born in Prussia?"

Beneath that, in a collection of such lectures later published under James' direction, was placed the footnote, "The reader will remember when this was written."

The suggestion of the bit about Bentham, Mill, etc. is that the utilitarians as a school helped render England ineffective as a European power, a drifting raft.

The footnote was added in 1897. So either James is suggesting that the baleful influence of Bentham, Mill etc wore off in the meantime or that he had over-estimated it.

Let's unpack this a bit.  What was happening in the period before 1880 that made England seem a drifting raft in European affairs, to a friendly though foreign observer (to the older brother…

Cancer Breakthrough

Hopeful news in recent days about an old and dear desideratum: a cure for cancer. Or at least for a cancer, and a nasty one at that.

The news comes about because investors in GlaxoSmithKline are greedy for profits, and has already inspired a bit of deregulation to boot. 

The FDA has paved the road for a speedy review of a new BCMA drug for multiple myeloma, essentially cancer of the bone marrow. This means that the US govt has removed some of the hurdles that would otherwise (by decision of the same govt) face a company trying to proceed with these trials expeditiously. 

This has been done because the Phase I clinical trial results have been very promising. The report I've seen indicates that details of these results will be shared with the world on Dec. 11 at the annual meeting of the American Society of Hematology. 

The European Medicines Agency has also given priority treatment to the drug in question. 

GSK's website identifies the drug at issue as "GSK2857916," althou…

Francesco Orsi

I thought briefly that I had found a contemporary philosopher whose views on ethics and meta-ethics checked all four key boxes. An ally all down the line.

The four, as regular readers of this blog may remember, are: cognitivism, intuitionism, consequentialism, pluralism. These represent the views that, respectively: some ethical judgments constitute knowledge; one important source for this knowledge consists of quasi-sensory non-inferential primary recognitions ("intuitions"); the right is logically dependent upon the good; and there exists an irreducible plurality of good.

Francesco Orsi seemed to believe all of these propositions. Here's his website and a link to one relevant paper:

What was better: Orsi is a young man. Born in 1980. A damned child! Has no memories of the age of disco!

So I emailed him asking if I was right that he believed all of those things. His answer: three out of …