Logicomix

Posted on May 28, 2012 by Tommy McGuire
Labels: theory, books, math
Logicomix (book)

I am tempted to begin by pointing out that someone once said something like, "Great minds talk about ideas; smaller minds talk about people." But I won't.

Logicomix: An Epic Search for Truth, by Apostolos Doxiadis and Christos H. Papadimitriou and illustrated by Alecos Papadatos and Annie Di Donna, is a biographical graphic novel about the life, philosophy, and logic of Bertrand Russell.

As a biography, it is excellent. Although I do not know the details of Russell's life beyond the Wikipedia entry and the graphic novel is admittedly not entirely accurate, I believe it does get to the heart of the lives of the logicians of the late nineteenth and early twentieth centuries. As a graphic novel, it is also very good. One of the artists, Annie Di Donna, is noted in the short biographies as having worked as an animator on Babar and Tintin, and Logicomix has a Tintin-esque, slightly archaic, somewhat realistic feel that matches well with the time period and telling of the story. The combination of caricatures and realistic backgrounds may not to be everyone's tastes, though. (I, personally, live in fear of Vint Cerf's career drawn in bubblegum-pop manga (the Japanese comics, not the dog).)

Now, back to the quote that I resisted the urge to start this review with. I'm at least theoretically a computer scientist and this is not the first book by Christos Papadimitriou I have read; I learned automata theory from Papdimitriou's and Harry Lewis' Elements of the Theory of Computation (the first edition, with the rotated square on the cover). The terrain which Russell's work in logic explored (or created, depending on your viewpoint) along with Cantor, Frege, Gödel and the other characters in Logicomix, represents some of humanity's most important intellectual territory. The properties of infinity, of formal systems, of logic and computation, represent fundamental ideas, no less than thermodynamics and relativistic or quantum physics. (If that sounds overblown to you, check out Gödel's Theorem: An Incomplete Guide to Its Use and Abuse by Torkel Franzén. You may well find that you're right.) And an understanding of the people involved does help in understanding how the ideas worked out.

Some of the reviewers of Logicomix have disliked the layered, self-referential method used to tell the story: the narration of Russell's life is framed by a biographical lecture given by Russell on the eve of World War II and that overall story is framed by the tale of Apostolos, Alecos, Annie, and a researcher, Anne, presenting their take on Russell's life to Christos and arguing over the best way to tell the story and indeed the meaning of it. This is capped off with an excursion to a performance of Aeschylus' Oresteia, I suppose making Athena and the Furies characters as well. However, a self-referential structure is in turn vital to the creation (or rather discovery) of Russell's, Cantor's, and Gödel's major works.

I'll leave Russell's Paradox and Gödel's Theorems (and Turing's, for that matter) as exercises for the reader and just show the example of my favorite proof: Cantor's diagonalization gag, the proof that the set of real numbers between 0 and 1 is more numerous than the set of counting numbers:

How do you count things? There are more than a few ways to define counting, but for my purposes here the best way is to put the things you want to count into some one-to-one relationship with the counting numbers: 1, 2, 3,..., also known as positive integers. Say you have some cherries. I'll label this cherry "1", that cherry "2", and the last cherry "3", and there's no more cherries here. Therefore, there were three.

How many integers are there? Integers, in case you don't remember, are ..., -2, -1, 0, 1, 2,..., which looks like more than 1, 2, 3,.... But check this relationship: \[ n = \left\{ \begin{array}{ll} 2i & \textrm{if}\ i > 0 \\ -2i + 1 & \textrm{if}\ i \leq 0 \end{array} \right. \] where \(n\) is a counting number and \(i\) is an integer. I will not go to the effort of proving this relation is one-to-one and onto, so you will just have to take my word for it: it means that the set of integers is the same size as the set of counting numbers.

But what about those reals? Say they are countable, that they can be put into a one-to-one relationship with the counting numbers. Then, there would be a list of them:

1-0.0030000...
2-0.9345522...
3-0.1415969...
......

Now, this list is infinite, mapping every counting number to a real greater than 0 and less than 1. Each real appears in the list as a non-terminating decimal representation: if the real is neither transcendental nor repeating, then it can be padded with zeros to the right without changing its value.

But let's construct another real number: take the nthdigit after the decimal point of each of the real numbers in the list, where n is the counting number, and add one to the digit modulo10. The result will be another digit; put it in the nthdigit after the decimal point of the new number, producing here 0.142.... This number is

  1. a real number greater than zero and less than one, and
  2. not in the list.

To see that it is not in the list, notice that it differs from the nth number in the list in at least one digit: the nth one, which is different by construction. As a result, the list cannot represent all of the real numbers between 0 and 1 and therefore the set of real numbers between zero and one is more numerous than the set of counting numbers.

This proof is self-referential, in a way. It takes the decimal representation of the real numbers and modifies that representation to create the representation of the novel number. I admit that I don't know if this is the proof that Cantor originally presented, although it was the first that I have seen, and that it would probably be possible to diagonalize the list with an arithmetical expression and without picking digits out of the representations. But this is the least self-referential of the examples I mentioned above. The idea that logic, that mathematics, would be able to talk about itself, would need to talk about itself, is likely the key to understanding the state of logic after Russell, Gödel, and the others. You see, I hope, why the layered and self-representational structure of Logicomix reminds me of this proof, and why I think that structure is so much fun for the biography.

I'm afraid I still don't understand the title, though.

sciseekclaimtoken-4fce361b67fd6

active directory applied formal logic ashurbanipal authentication books c c++ comics conference continuations coq data structure digital humanities Dijkstra eclipse virgo electronics emacs goodreads haskell http java job Knuth ldap link linux lisp math naming nimrod notation OpenAM osgi parsing pony programming language protocols python quote quotes R random REST ruby rust SAML scala scheme shell software development system administration theory tip toy problems unix vmware yeti
Member of The Internet Defense League
Site proudly generated by Hakyll.