I love (good!) surprises. I bet everyone does. And I had just one like that very recently. After a long year of hard work, I finally forgot all about computers, blockchains, cryptography and the chores of everyday life and went on holidays to the countryside. Amidst some books about farm life and country walks, I dug up an incoherent and unexpected find, a title that brought me memories from my PhD days: Logicomix.
I was sure I had heard the name before, and indeed I had. You see, one of the authors of the book is Christos Papadimitriou. For most readers, this name will mean nothing. For me, it is special because one of the first books I had to contend with in my PhD was his Computational Complexity, the sacred text on the subject when I started. Under his distant tutelage, I began my journey into the world of complexity, computational models, probabilities, algorithmic randomness, and so on.
It was at this time I first read about Logicomix. And although I was curious about this crossover from an academic researcher into, shall we say, popular literature, I could never lay hands on it. After more than a decade, I finally have, and I devoured it in one sitting.
The Authors
Before I go on, let me note that my emphasis in this post is on Computer Science (since that is my background). Because of that, I focus on Christos Papadimitriou mainly, but there are other 3 authors. The writing is shared with Apostolos Doxiadis, a writer/mathematician who also wrote the first novel focused on pure mathematical research.
Doxiadis and Papadimitriou share the talent to master academic literature and at the same time be able to write accessible fiction. It would be too much to ask for them to be accomplished graphical artists too. The artwork of Logicomix was done by two other authors, Alecos Papadatos and Annie di Donna.
The Book
Logicomix is a graphic novel, a comic, but no ordinary one. Its protagonists are not tragic superheroes, anguished mutants or tech-savvy teenagers. Although, indeed, they are tragic, anguished and quite math-savvy, embarking in a long quest for knowledge. How well suited this book is for this blog, then, that is all about quests and long journeys.
The heroes of this book, then. They are logicians at the turn of the 19th century, undertaking the fundamental quest for truth in mathematics.
Yes, this is out of the ordinary for a graphic novel. But it works surprisingly well. The main protagonist is Bertrand Russell, a towering figure in mathematics and philosophy in the 20th century, who tells his tale from a materially privileged and emotionally deprived childhood to adulthood as an accomplished researcher, thinker and speaker.
The book leads us through his studies in logic and philosophy and his much slower progress in life as a social endeavour, but the main story is one of ideas: the birth and development of mathematical logic; how its proponents sought to eliminate ambiguity and circularity in mathematical discourse; how for a few brief decades they had a dream of finding a method to prove anything in mathematics and how, in the end, this hope collapsed in the Incompleteness Theorem of Kurt Gödel.
In the backdrop of this novel, two main themes give it gravitas and importance to the real world: pacifism at the beginning of the second world war (Russell was markedly anti-war, and even went to prison during WWI for his beliefs) and madness (although its connection to logic may be a bit overplayed). It is a great read.
From Logic to Computer Science
From the point of view of a computer scientist, the book is entertaining but not much informative in theoretical terms. And that, of course, is not the point. For those with a more practical bent, like developers and engineers, this may be a small appetizer to other readings. But there is a lot hidden under the surface.
Those with a background in CS will be able to fill in the details by themselves. They will even understand the comments by Papadimitriou’s avatar (Logicomix is quite self-referential, as it describes the authors writing the book and telling the story they’re writing) about a second book, dedicated to algorithms, that would be the logical follow-up (and conclusion?) to this one. As far as I’m aware, there is no direct sequel to Logicomix, but Papadimitriou has written a novel, Turing, that may well fill that niche. It is now on my list of books to read.
As a first post after a short holiday, I don’t want to go very deep into theory. But before I go, I’d like to give a shot at listing the conceptual steps described or alluded to in the book, as a guideposts to those who wish to know more about the quest for truth in mathematics.
Logic
In the book, Russell’s interest in logic is triggered by a lack of precision in mathematical discourse. He is concerned that some terms are poorly or circularly defined (eg “infinitesimal is that which is infinitely small”). He searches for a way to describe and reason about mathematical statements rigorously.
His first step is the discovery of Boolean Algebra, invented by George Boole. This describes the fundamental logic operations and forms the basis for all logic. Indeed, this is mandatory knowledge for every programmer, but in Russell’s time, it was still not well known. According to the book, its place either in mathematics or philosophy was not even well-defined at that time.
Boolean operators can connect propositions (statements that can be either True or False) to form new propositions. Different connectors imply different rules to determine the logic value of the new proposition. For example, P AND Q is only true if both P and Q are true propositions. On the other hand, P OR Q is only false if both P and Q are false.
Basic propositions are simple absolute statements, like “Today it has rained in Spain”. Logic begins to become interesting when we introduce variables and quantifiers. Now, we can write statements about undefined things, and with quantifiers, we can precisely determine which things. For example, “All even numbers are divisible by 4” is a false proposition, since we can easily find counter-examples (eg 2).
Set Theory
From the introduction of quantifiers and variables it is a small step to sets. After all, a set is exactly those elements that satisfy a given predicate, that is, for which a certain logic proposition is True. Set Theory plays a big role in Logicomix, because it is at the centre of the difficulties met by these adventurers.
Georg Cantor was the first to discover that there are different kinds of infinity in mathematics. Before him, mathematicians knew integer and real numbers were infinite, but they thought they were equally so. Cantor demonstrated in a beautiful argument that the reals are uncountable, that is, it is not possible to make a 1-to-1 relation between the integers and the reals. In other words, you cannot put all the real numbers in a list and label them 1, 2, 3, …
If this sounds obvious, let me twist your mind a bit. You can make a 1-to-1 relation between even numbers and integer numbers. That is, there as many even integers as there are integers, both even and odd, since for every integer x you have a corresponding even number 2x.
Instead, the reals are infinitely more than the integers: between each two consecutive integer numbers we have an infinity of real numbers, such as, 1.1 or something as 1.432384629387629428763472721129...
Paradoxes
The different degrees of infinity were the first sign of the difficulties ahead. The next step in Logicomix is what is known as Russell’s Paradox, which can be described in many guises. For example, we can imagine sets as collections of anything, including other sets. One natural question is whether a set can contain itself. If so, this leads to a contradiction. For example, the set of sets that do not contain themselves. cannot exist.
Let this set be S. If S is a member of S, then by definition S cannot contain itself, while by assumption it does.
On the other hand, if S is not a member of S, then by definition S must contain itself, while by assumption it does not.
This led to more sophisticated definitions of Set Theory that still can be subjected to set operators that are consistent with logical operations on their defining predicates.
Incompleteness
At this stage, mathematicians had a working set theory that was consistent with logic. That is, they could reason about the properties of sets by describing them with logical predicates and combining them with quantifiers and Boolean operators. These can be combined to produce new sets.
But there were still difficulties. When you’re given a complex Boolean formula, and you know the logic values of all its arguments, it can be more or less annoying, but you can always get to the logical value of the whole proposition. So, mathematicians were hopeful that if they could define an adequate set of axioms for arithmetics they would be able to prove the truth or falsehood of any statement in arithmetics.
In 1931, Gödel crushed these dreams with his incompleteness theorem, stating that no matter what axiomatization you choose, there will always be statements that are unprovable. That is, it is not be possible to demonstrate they are either True or False.
Computability
The theoretical journey in Logicomix ends more or less here, but although that is a good ending from a mathematician’s point of view, for a computer scientist it is just the beginning. Papadimitriou’s avatar in the book makes this point several times. For Russell, the Incompleteness Theorem was the end of a research program. But on its tails, the work of Church, Alonso and Turing led to the creation of amazing computational models and the beginning of the theory of Computability.
Complexity itself can be seen as a branch of Computability, with several similarities.
In the journey up to here, we could describe sets as the set of elements in a well-defined universe that satify a given predicate. But now, with imagined computational devices like a Turing Machine, we can describe sets by computer programs. A set, or a language, is the collection of elements that are output by some program that descrcibes that set. For example, to describe the set of even numbers, we could write the program
Let i = 0 While TRUE PRINT 2 * i Let i = i + 1 End
I’m intentionally blurring the lines here between enumerating a set and recognizing whether an element belongs to a set. That is more technical than I care to go in this post.
Success or Failure?
It is important to reach this point for a couple of reasons.
Logicomix claims Russell saw his research as a failure because in the end there are statements no one can prove. Papadimitriou, instead, claims that this difficulty is resolved by the characterization of sets into classes like computable, uncomputable, enumerable, etc..These are based in the existence, or impossibility thereof, of an algorithm that “generates” the set.
The whole fundamental quest of Russell, Hilbert, Frege and others, should not be seen as a failure. Rather, they were the crowning achievement that enabled the idea of a Computer and the birth of Computer Science. The tragedy of Logicomix, therefore, should have a happy ending.
This may sound too abstract, but some of these notions should be well understood by developers in general. Computability is the basis of Complexity, and both are important for practitioners to understand the limits of their tools. The first answers the question “what can computers (not) do?”. The second answers the question “How well can computers do it?”.
Both seem fundamental to me.
I wish you can take some new reading ideas from this post. But more importantly, I wish your holidays can be as inspiring and satisfying as mine were to me.