Logic

An Idiotic Paradox

Posted by richardelwes on June 6, 2011
Posted in: Logic, Nonsense. 7 Comments

A.   B-san, may I ask you a question?

B.   Please do.

A.   Thank you. Are you an idiot?

B.   That question is hardly of the intellectual calibre that I have come to expect from you, but I shall answer it nevertheless. No, A-san, I am not an idiot.

A.   Are you entirely sure? I believe that I can demonstrate that you are indeed an idiot.

B.   Are my trousers unbuttoned? Have I forgotten your birthday? If I have made some careless mistake you could tell me kindly rather than with insults.

A.   Other than being somewhat old and ill-fitting, your trousers are fine. And my birthday is not for 3 months, as I believe you know. I do not have any such mistake in mind. Rather, I claim that I can demonstrate that you are an idiot using only this pen and paper. What is more, you will be forced by your own words to accept it. May I try?

B.   I suppose so.

A.   Very well. I shall write a sentence on this paper, and you must tell me whether or not you believe it.

B.   What if I don’t know?

A.   If you don’t know, then say you don’t believe it.

B.   Hmm. It’s going to be one of those sentences which asserts its own falsity, isn’t it? Like that Cretan who said “all Cretans always lie”. Utterances like that can’t sensibly be called either true or false.

A.   A good point, but my sentence is fully capable of supporting a truth value. Indeed, I shall attempt to persuade you that the sentence is true. And very likely I shall succeed. Nevertheless you will continue to insist that you do not believe it.

B.   What? You say I will be convinced of your sentence’s truth, but at the same time I will refuse to believe it? That would indeed make me a supreme idiot.

A.   Exactly! [Writes something down and hands it to B.]

B.   [Reads] “Only idiots believe this sentence.”

A.   So, do you believe it?

B.   If I believe it, then I must be an idiot.

A.   Precisely!

B.   But I maintain that I am not an idiot. So, no, A-san, I do not believe this sentence.

A.   That’s what I said when I first read it. And that’s what C-san and D-san said too. In fact, I expect your reaction is the same as that of any intelligent person.

B.   I agree. Anyone who read that sentence and declared that they believed it would be a self-admitted idiot.

A.   In other words, B-san, you are saying that only idiots believe that sentence.

B.   Yes!

A.   Ok! Now read it again.

B.   [Reads it again. Thinks.] Bollocks.

A.   And B-san?

B.   Yes?

A.   Your trousers are undone.

Book review: Naming Infinity

Posted by richardelwes on March 13, 2011
Posted in: Logic, Maths, Reviews. 3 Comments

 

Naming Infinity by Loren Graham & Jean-Michel Kantor tells the story of the beginnings of the mathematical subject called descriptive set theory. The backdrop to the story is the pioneering work performed by Georg Cantor in the late 19th century.

Cantor’s great revelation was that infinity is not a single entity, but comes in a variety of flavours (an infinite variety, in fact). With Pandora’s box opened, there then followed an almighty scramble throughout the mathematical world, to make sense of this extraordinary revelation.

A particularly pressing question was how the two most familiar levels of infinity relate to each other. The first of these is countable infinity, that is the infinity of the natural numbers: 1,2,3,4,… The second is the larger infinity of the real numbers (meaning all possible infinite decimal strings). This level of infinity is known as the continuum. A major question left unanswered by Cantor (to his considerable distress) was whether there are any levels sitting between these two. The assertion that there are no such intermediate infinities is known as the continuum hypothesis.

A solution to the continuum hypothesis was a major goal in the early days of set theory. One angle of attack was to try to understand the possible subsets of the collection of real numbers, and to determine their sizes, as well as understand the many other phenomena which emerged during this investigation. This was descriptive set theory, where Cantor’s abstract modern subject met the more mature areas of calculus, continuity, and analysis.

Although the continuum hypothesis was a continuing motivation to these mathematicians, with hindsight we can see that the story rather deviates at this stage. The enduring importance of the work that followed was to begin cataloguing and classifying the immense variety of possible sets and functions of real numbers, using set theory to enrich our understanding of analysis, and to dig into the logical foundations of the real numbers. (The continuum hypothesis was eventually settled by Paul Cohen in 1963, through essentially different means.)

 

Transfinite Numbers and Name Worshipping

The early running in descriptive set theory was made in France, notably by the trio of Émile Borel, Henri Lebesgue, and René Baire. Great as their achievements were, they were reluctant to embrace the full power of Cantor’s transfinite numbers, and in the narrative of Naming Infinity, the French trio “lost their nerve”.

The baton then passed to Russia, where the intellectual climate was better suited to handle the conceptual challenges posed by the new theory. This fortuitous match of cultures is the main focus of Naming Infinity.

The trouble was that the higher rungs of Cantor’s infinite ladder corresponded to nothing else in the history of human thought. This caused a division in the mathematical world. Many felt that a mathematician’s job was to analyse objects whose roots were in the physical universe (albeit abstracted and idealised), rather than disappearing into a world of weird concoctions of their own invention. Naming Infinity provides a concise account of this crisis in mathematics, tracing its roots to the difference between the old Aristotelian and Platonic schools of thought.

In Moscow, set theory found fertile soil among thinkers whose religious beliefs allowed them to embrace Cantor’s radical new ideas. The mathematical heavyweights were Dmitri Egorov and Nikolai Luzin, while the group’s religious mentor was the priest Pavel Florensky. These mathematicians were inspired by a Christian mystic movement known as Name Worshipping. The crux of Name Worshipping is expressed at the beginning of John’s Gospel (my emphasis): “In the beginning was the Word, and the Word was with God, and the Word was God.”

For these mystics, the act of naming had a profound meaning. To name something was to grasp its essence, and to utter the name of God, in particular, was to commune with him at the very deepest level. The name-worshippers developed their own sacred practices, consisting of repeating the names of Jesus and God over and over again, like a meditative mantra. These practices were judged heretical by many in the Russian Orthodox Church.

The emphasis on naming gelled well with Cantor’s set theory, in which the transfinite numbers were named in turn, as the ladder was ascended: the countable level was denoted ℵ0 (ℵ being the aleph, first letter of the Hebrew alphabet). Then come ℵ1, ℵ2, and so on. For Egorov, Luzin, and Florensky, the fact that such concepts could be pinned down enough to be named leant them a deep legitimacy, irrespective of their seeming unworldliness.

The heart of the Naming Infinity is the fascinating story of this meeting of mathematics and mysticism. The authors are at pains not to overstate their case, as they say: “when we emphasize the importance of Name Worshipping to men like Luzin, Egorov, and Florensky, we are not claiming a unique or necessary relationship… It could have happened another way; but it did not.”

 

The Moscow School of Mathematics

The story can be read as the birth of not only of descriptive set theory, but of the Moscow School of Mathematics, whose influence was extensive throughout the 20th century and continues today. Among other legacies, this school gave us (through Alexandrov) point-set topology and (through Kolmogorov) the modern axiomatic approach to probability. Its founding fathers were Luzin and Egorov, and the circle of young men and women who worked with them: the Lusitania.

It was not just the world of mathematics which was turned upside-down during this period. This was the time of the Russian revolution, and the turmoil and terror that followed. Naming Infinity tells extraordinary stories of the dedication with which these mathematicians worked, continuing their seminars through terrible poverty and hunger, and even bitter cold.

In times of political oppression, as in Stalin’s Russia, it is comforting to think of mathematicians and scientists as the innocent victims of the political ideologues. So the most troubling chapter of the book concerns the so-called Luzin affair. The mathematician Nikolai Luzin found himself not only pursued by the Soviet authorities for his supposed counter-revolutionary activity, but also denounced and betrayed by his colleagues and pupils. To modern eyes, it seems almost incomprehensible that Aristotle and Plato’s debate about the foundations of mathematics could be dragged into the the swirl of political and ideological intolerance, and all the accompanying suspicion and hatred. But it was, all the same. The Moscow School of Mathematics was condemned for its supposed beourgois and anti-Soviet tendencies, while the Name Worshippers, having already been declared heretical by the Church, now found themselves pursued by the State.

 

History and Mathematics

Naming Infinity is a short book about the history of mathematics, and as such it is excellent. It relates with great clarity and humanity a chapter in the history of our subject which was previously unfamiliar to me. The interplay of mathematical and religious ideas is fascinating, and the story of mathematics flourishing in such adverse conditions is at once tragic and inspiring.

In purely historical terms, the book takes a terrifying slice through Stalin’s Russia. It describes the lives of just a few individuals, behind whom can be imagined hundreds of thousands of others, whose stories will very likely never been heard. The history is told with a respect for the main characters, neither indulgently excusing their crimes, nor wrenching them from their historical context.

I do have a quibble though, and that is in the book’s account of the mathematics itself. I cannot say that I really got a sense of what the breakthroughs of the principle characters really were. To my mind, too little time is spent on that side of the tale. In the end, I took to reading it in parallel with some old lecture notes on descriptive set theory. That was a hugely satisfying combination, but not one I can suggest to my non-mathematical friends and family, much as I would like to recommend them this book.

Perhaps I am wrong, but I can’t help feeling that a non-mathematical reader might be rather bemused by some of the technical terms in the book, which tend to come and go, without ever being fully fleshed out. The continuum hypothesis, for instance, begins centre stage, but then disappears from view over the course of the book. While mathematically understandable, I can’t help worrying that this might perplex the reader who wishes to understand the many intellectual triumphs which lie behind the human tragedy.

Concrete Incompleteness 1

Posted by richardelwes on October 21, 2010
Posted in: Logic, Maths.

I’ve just uploaded the slides [pdf] from a talk I gave yesterday at the University of Leeds, about concrete incompleteness. The topic is the same as my recent New Scientist article, but in greater technical detail, though the intention was still that it be reasonably accessible to non-logicians. I’ll tell the central story here as a sort of commentary, and there are equations and other gory details available in the slides.

Since Kurt Gödel proved his celebrated first incompleteness theorem, we have known that arithmetic (that is to say the positive whole numbers with addition and multiplication) will always contain unprovable statements. This means that no matter what fundamental axioms we choose to underlie arithmetic, there will always be some statement T such that neither it nor its negation ‘not T’ can be deduced from our axioms. These are called independent or unprovable statements[1].

But of course, it never makes sense to say “T is an unprovable statement” without reference to some specific axiomatic system: different axioms, different provable & unprovable statements.

The standard axioms for arithmetic were written down by Giuseppe Peano in 19th century Italy. Forty years later, Gödel’s theorem implied that Peano’s axioms must be incomplete. The question for today is: are they incomplete in a way that matters to non-logicians? In the course of studying number theory, or combinatorics, are you liable to run into an unprovable statement? Or are such things really curiosities of no wider importance?

Since then, several concrete instances of incompleteness have been found, examples being the termination of Goodstein sequences, the Paris-Harrington variant of Ramsey’s theorem, and Kruskal’s theorem on finite trees as well as Harvey Friedman’s finite miniaturization of that result.

Now, that last result of 2002 represented a big step forward in unprovability theory, for the following reason: attempts to axiomatise arithmetic did not stop with Peano. In the mean time, a wealth of stronger axiomatic systems have been investigated. In particular, for much modern mathematics, it is not enough to talk just about plain whole numbers. We also need to consider how sets of such numbers behave. This is the key, for example, to building a coherent theory of real and complex numbers. Peano’s axioms are first order, meaning that they discuss only numbers. To axiomatise the behaviour of sets of numbers, we need what is known as second order logic. But which sets of numbers should we axiomatize? The minimum second-order system which extends Peano arithmetic is called ACA0, or “arithmetical comprehension”. Here we can sensibly analyse all the sets of numbers which Peano describes. However there are also many stronger systems, notably ATR0, or “arithmetical transfinite recursion”. This system provides a much richer class of sets, defined via certain infinite processes, unavailable in weaker systems. This is the right level at which to build up a large amount of analysis, calculus, and topology. On the other hand, Friedman’s variant of Kruskal’s theorem is purely finitary in nature, involving only plain whole numbers. It’s natural home would seem to be ACA0, and yet it is unprovable not just at that level, but in ATR0 too.

This was certainly a striking result, but recent developments have taken us much further. Way, way beyond second order arithmetic is the the system of Zermelo-Fraenkel set theory, ZFC[2]. This allows not just all possible sets of numbers, but also sets of sets of numbers, sets of sets of sets, and so on ad infinitum (and indeed considerably beyond that). As such, ZFC has become the standard foundation for the whole of mathematics. For most purposes it represents massive overkill.

Of course though, Gödel’s theorem applies here too: there must be questions which even ZFC cannot answer. From a set theorist’s perspective, the primary examples concern the existence of large cardinals.

ZFC is the modern setting for the great work that Georg Cantor did in the late 19th century, disassembling the concept of infinity. Cantor showed that there is not just one level of infinity, but an infinite ladder with each rung infinitely higher the last. What’s more, there is no ultimate infinity beyond all the others: this ladder has no top rung. One can ask though, whether or not there are rungs so far up that that they are unapproachable from below. These, if they exist, are called “large cardinals”, and their existence is independent of the axioms of ZFC. Set theorists have been studying multiple varieties of large cardinals, and the logical dependencies between them, for over 100 years.

Returning to the finite realm, and the arithmetic of the plain whole numbers, Gödel assures us that here too, not even ZFC will be enough to resolve all possible queries. There must be statements about numbers which are unprovable in ZFC. So we can repeat the earlier question: are these the sort of things which working mathematicians, who are not logicians or set theorists, need to worry about?

This question has received a brand new answer, in the subject of Boolean Relation Theory developed by Harvey Frieman in a forthcoming book (section 3 on this page has downloadable pdfs). In it, he considers a very simple class of functions of whole numbers, known as the Expansive Linear Growth (ELG) functions, and then identifies a certain configuration of inputs and outputs which such functions may exhibit. (The details are on my slide number 12.) The question is: does every ELG function exhibit such a configuration? And the answer is not deducible within ZFC. Certainly, one cannot construct a counterexample. But we have to pass to a stronger system, which contains certain large cardinals, in order to prove the answer “yes”.

I believe that this is an important result. The situations described by Boolean relation theory are indisputably elementary, and (perhaps somewhat disputably) they seem natural. What is more, they are ripe for generalisation. Replacing the natural numbers with different underlying structures, and considering different classes of sets and functions defined by analytic or geometric conditions, we can ask similar questions about the configurations of inputs and outputs which emerge. This may well represent a door through which questions of provability enter mainstream mathematics, not in ones and twos, but in truly significant quantities.

In syntactic terms, the unprovable statements of Boolean relation theory have complexity at the level of Π02. Friedman additionally set himself the goal of finding a simpler Π01 sentence, which depends on large cardinals, while at the same time providing “clear and compelling information in the finite mathematical realm”. In a separate development, he claims to have found exactly that, in the form of a statement about directed graphs living among the rational numbers. Unfortunately there are several intermediate definitions needed to present it. None of them are at all difficult, but they do mount up, to the point where I can’t say I have much of a mental picture of what exactly is being asserted. Some details, pared down as much as I can, are in my slides 14-16, and a fuller account is in section 0.14D of the introduction [large pdf] to Harvey’s book.

Ok, that’s it for now, but I do intend to write more on this topic – hence the “1” in the post title. Next time I’ll be musing about the philosophical implications of having syntactically simple statements about natural numbers, which can only be resolved using large cardinals.

[1] They’re sometimes called ‘undecidable’ statements, but – warning! – that word is also used in a different way, to do with algorithms. Generally I prefer ‘uncomputable’ for the algorithmic notion, but maybe that’s just me.

[2] Technically, that’s Zermelo-Fraenkel set theory plus the Axiom of Choice. But I don’t want to think about that here – there’s already enough unprovability on the table. So we’ll just take Choice as given.

Book Review: Meta Maths, The Quest For Omega

Posted by richardelwes on June 28, 2008
Posted in: Logic, Maths, Reviews. 3 Comments

Gregory Chaitin’s Meta Maths is a short book, which meanders pleasantly through various topics: Biological Information (DNA), LISP, several proofs of the infinity of the primes, and the question of whether the universe is discrete or continuous, with accompanying (slightly strange[1]) arguments against the real numbers. Additionally, there’s a good amount of entertaining and idiosyncratic reflection on science, philosophy, and life (“I only really feel alive when I’m working on a new idea, when I’m making love to a woman…. or when I’m going up a mountain!”)

Meta Maths also covers that fascinating tie-in between logic and number theory, Hilbert’s 10th problem: whether or not there’s a procedure which can decide whether any integer-valued equation has integer-valued solutions. Some really ingenious mathematics tells us that this is equivalent to the Halting Problem, which asks whether there’s a procedure which can tell if an arbitrary computer program will halt, or continue to run for ever. The answer in both cases is no.

The meat of the story takes us from Gödel’s Incompleteness, to Turing’s Uncomputability (where the Halting Problem arises), and on to Chaitin’s home turf: Algorithmic Information Theory. Each of these areas subsumes the last, in exhibiting in ever more dramatic style the gaping unknowability at the heart of mathematics. The overwhelming majority of real numbers are completely inaccessible to us (other than through non-constructive existence results, of which Chaitin disapproves, I suppose).

The book is full of diagrams like this:

Mathematics:
Axioms → Formal System → Theorems

Computation:
Program → Computer → Output

Life:
DNA → Pregnancy → Organism

Leibniz’s metaphysics:
Ideas → Mind of God → Universe

In each case the first stage consists of compressed information, the middle stage is where this is unpacked, followed by the final result.

Chaitin’s “dangerous idea” is that almost all information (at least the sort of information which can be encoded in binary), is actually incompressible. That is to say, it cannot be deduced from any axioms simpler than itself. It is a striking thought, and rams home with some force that Gödelian gaps in our mathematics are the rule, not the exceptions. If you pick a real number at random, then with probability 1 you can have no way of writing it out, or naming it under any system you can think of, or indeed referring to it at all without hopeless ambiguity.

The basic definitions of Algorithmic Information Theory are perfectly natural: you define the complexity of a piece of binary information (or anything[2], such as a mathematical theorem, which can be encoded in binary) to be the length of the shortest program which computes it. (In fact the program must be “self-delimiting”, this is the book’s most technical matter.) A real number is defined to be random[3] if the complexity of its first N digits is equal to N (give or take a small error term).

The peg off which the book hangs is the number Ω (“sometimes called Chaitin’s number”, he helpfully adds): the average halting probability for self-delimiting programs.

I may be wrong, but it’s not obvious that you can really do much with Ω (so comparisons with other fundamental constants are surely hyperbole). It’s just a fact, whose interest is that it is a random real, but it is strikingly exceptional, since we can pick it out uniquely (in some sense[4]).

A final word about Chaitin’s punchy prose style! Lots of bold! And exclamation marks!! Loads!!! And more sex than most maths books!

[1] It wasn’t at all clear to me in what he means when he says he’s “against” them, especially as much of the material in the book is rather dependent on their existence.

[2] How long can it be before the “irreducible complexity” berks mangle this stuff?

[3] Be warned, the world abounds with different definitions of randomness.

[4] Of course, Ω is incomputable, and we can only access it via something else we can’t know, namely solutions to the Halting problem. But somehow this seems less unsatisfying when you translate it into the language of Diophantine equations: there is one such Q(n,x1,x2…) which has infinitely many solutions if the nth digit of the binary expansion of Ω is 1, and finitely many solutions if it’s 0.

An infinitely bored librarian

Posted by richardelwes on June 23, 2008
Posted in: Logic, Maths.

Matt, having read my recent articles about set-theory, feeds back:

The best “real world” example of Russell’s paradox I’ve seen (I forget where now) is this: A librarian, bored with work, sets about making two indexes of books in their library. In book one, she lists all books which don’t reference themselves. In book two, she lists all books which do reference themselves. But then she thinks: I’ve just created two new books, so I should list them as well. But neither book references itself, so they should both be listed in book one. But by doing this, book one now does reference itself! So book one should really be listed in book two instead. But if she does this, then book one goes back to not referencing itself!

I like it. Much better than the barber one.