Simple City  

This is a sequel to the first hat game post, please read for the background. Everything here is based on a recent talk by Robert Lubarsky, about work of his with Stefan Geschke, though any errors are mine. This post will end up with some unsolved questions: if you think you know the answers (either because you can solve them yourself, or you know where solutions can be found), please leave a comment here or drop Robert an email. (He told me he was quite happy to throw this material out into the public domain, and I would obviously be delighted if this blog helps find some answers!)

So… the basic puzzle in this post is as before, but this time the first person in line sees an infinite queue of hat wearers standing in front of him. What strategy can our team adopt, to maximize the number of hats they are able to name correctly? Have a think about it… and a discussion follows this picture:

 

 

Hats and Tails

 
Last time we started representing our hat-wearers using binary sequences, that is strings of 0s and 1s. The new puzzle plunges us into a world of infinite binary sequences. Infinite things are generally not easy to write down, so let’s take a very simple example consisting only of ones:
A = 1111111111111111……..

We’ll say that two infinite binary sequences are equivalent if they share the same tail, meaning that are identical beyond some point, before which they may differ (or to put it another way, the two only differ in finitely many places). So the sequence A above is equivalent to B = 0010111111111111……..

This notion of equivalence divides the whole space of all possible binary sequences into ‘classes’, inside each of which all sequences are equivalent. Getting back to our hat-wearing friends, everyone in the line has infinitely many people in front of them, and only finitely many behind. So everyone can tell at a glance which class they are in. They all know whether or not they are equivalent to A, or to any other specified sequence.

This doesn’t immediately help them. But we can take it a little further. We say two sequences are evenly equivalent if they differ in an even number of positions. Obviously, if two sequences are evenly equivalent, then they are equivalent. But not vice versa: A and B are equivalent but not evenly so.

A little thought reveals that any sequence which is in the same class as A (and therefore B) must be evenly equivalent to either A or to B. (Think about it!) Now this really is a useful fact for the hatters to exploit. In their strategy-meeting before the game, they go through every class, and they select one special sequence from it, to act as a reference point. Let’s say, for the class containing A & B, they choose A.

When they come to line up, let’s suppose the sequence of hats which emerges is B = 0010111111111111…….. Now, everyone can see which class they are in. So everyone knows to follow the plan and compare their own sequence to A. But they do not know which subclass they’re in i.e. whether they are evenly equivalent to A. However, the first person (who is hatless in this version) can see the whole sequence. So she can discern the subclass, in particular she sees that the sequence is not evenly equivalent to A. So she calls out “1”. (It would have been “0”, had the sequence been evenly equivalent to A.)

Now, as far as the next person is aware, the sequence is X010111111111111…….. where X is his own hat colour. He doesn’t know the value of X, but he knows from what he hears over his shoulder that the overall sequence is not evenly equivalent to A. So, he deduces that X=0, which he calls out. The next person knows 0Y101111111111….., and that the whole sequence is not evenly equivalent to A, so concludes that Y=0, and so on.

 

Millinery Strategists

 
So our team has its strategy. The nub of it is to use the meeting beforehand to select one special sequence from every class, to which they will then compare their own via even equivalence. Call this strategy 1.

In fact, strategy 1 is overkill. The players don’t need to specify an individual sequence from each class. All they really need to select is one of the two subclasses. Of course, a unique sequence gives you a subclass (`the subclass containing A’), but not vice versa. Strategy 2 is to go through all the possible classes of sequences, selecting one subclass from each.

To put this into action, the first person will call “0” if the sequence is in the selected subclass, and “1” if it’s in the other. The next player now knows which subclass they’re in. Combining that with what he can see will tell him his hat-colour, and so on.

There is also a third possible strategy: the players use their meeting to decide upon a non-principal ultrafilter on the natural numbers. (I won’t go into further details here, people who care about such things can fill them in themselves.)

 

The Superpower to Choose

 
We have arrived at three solutions to the puzzle. But there are further questions: which strategy is the easiest? And what superpowers do the players need to follow it? Leaving aside their infinitely good eyesight, hearing, mental acuity, and patience, each strategy gives them a job to do during their planning meeting. These tasks are not at all straightforward!

In the example above, A is a very easy-to-describe sequence. Most sequences are not like this, but are uncomputable, random, and generally indescribable. In general, there is no procedure or algorithm that the players can hope to use to pick out a single sequence from each class, as strategy 1 requires. This can only be done using a superpower, meaning some version of the axiom of choice. But full choice is certainly excessive, and there is an assortment of weaker axioms. What is actually required here?

Strategy 2 appears slightly easier than 1: the players don’t have to select one sequence from the infinitely many in each class, they just need to pick one of the two subclasses. Nevertheless Lubarsky & Geschke have shown that this still requires more choosing-power than comes freely with the ZF axioms. What is more, strategy 2 is minimal: any strategy which solves the puzzle will allow a subclass to be selected from each class. Together these two facts imply that a team of hat-wearers working purely within ZF cannot solve the problem, but one with the full power of ZFC can. What is the minimum superpower, in terms of ability to choose, that the players need for each strategy?

We know from the above remarks that strategies 1 and 3 are each at least as strong as strategy 2. The conjecture here is that they are both strictly stronger than 2, and what is more that 1 & 3 are themselves inequivalent. Any further thoughts?

Yesterday I heard a great talk by Robert Lubarsky, which provided a delightfully easy route into fairly deep logical waters. He was talking about joint work of his with Stefan Geschke.

This is the first of two two posts about it, each based around a puzzle. So let’s get going with the first, which is something of a classic. The second is altogether trickier, indeed a complete answer seems to be as yet unknown…

Here’s the first puzzle: ten (or a hundred or any number) people stand in a line, one in front of the other. Each is wearing either a black or a white hat. If you’re in the queue, you don’t know your own hat-colour, or those of the the people behind you. But you can see the ones in front. Starting from the back of the line, the challenge is for each person to call out in turn, trying to guess the colour of their own hat. They are allowed to discuss strategy beforehand. So what plan can they hatch to maximise the number of right answers?

Here is one possibility: the first person says the colour of the hat directly in front of him. So the second knows her hat colour, which she calls out. The third person then does the same favour for the fourth, and so on. This way, the team are guaranteed to get half the hats right. (We only care about guaranteed correct answers in this game, not lucky guesses.) In fact, there is a much better strategy. If you don’t know the answer, have a think about it now. The solution is on the other side of this picture.

Here’s an answer: the person at the back counts the number of black hats in front of him. If that’s an odd number, he says “black”. If it’s even, he calls “white”. Now, the next person can see all the same hats the first could see, except her own. Say she sees 5 black hats, and hears “black”. Can her own hat be black too? No, because otherwise that would make 6 black hats in front of the first person, an even number. So she knows her own hat must be white. Similarly, if she hears “white” then she knows that her own hat must be black. All the people in front can work out their own hat in the same way, by combining what they can see with what the people behind have said.

Now, this strategy allows everyone to discover their own hat colour, except for first the very first person. It is easy to see this is the best that can be done: no-one can see the first hat, so any tactic the team try will be immune to a change in its colour. To avoid this exception, in the next post we’ll assume the person at the head of the queue is hatless.

To set things up for the next post, I’ll write this another way, using “1” to represent black and “0” for white. So the sequence of hats might read 0010001111. The first person sees the whole sequence, adds up all the digits to get 5, and says “1”. (This is the total modulo 2, if you like.). The second person sees 010001111, and so on, with everyone seeing the same binary sequence, but with the beginning chopped off in different places.

I hope you agree that this hat game is a fun puzzle, with a neat answer. Its solution uses what computer scientists call a parity bit, a technique used to guard against data becoming corrupted.

In the next post things will become a little more serious, when we allow the queue of hat-wearers to grow infinitely long. In this new version, we have to assume that the hatters have various superpowers: they can see infinitely far in front of them, for example. It is obvious that the same tactic will not work in this setting, since everyone is likely to see infinitely many black hats in front of them (and of course it makes no sense to ask whether ‘infinity’ is odd or even). So what is the optimal result here, and what strategy will produce it? And, critically, what further superpowers do the people need to enact it?

Update: the second post is here.

Over on G+, Alexander Kruel pointed me towards an article by Alex Knapp entitled “Why your brain isn’t a computer”.

The point of this post is not to argue whether it is or it isn’t, but to draw attention to a salient point, which I think Alex waves away rather too quickly (and which in any case is important and interesting).

One might reason that there are plenty of different types of ‘computation’ around these days: ordinary computer programs, embedded systems, neural nets, self-modifying code, and so on. So, with all this variety, why should we expect that a human brain, being a neurochemical network, should fall into the same computational category as a laptop? Might it not simply be that the two have different capabilities? As Alex argues “Electric circuits simply function differently then electrochemical ones”.

The problem with this argument is that it overlooks the great robustness of the notion of computability, specifically the Church-Turing thesis.

A bit of history: in the 1930s, Alan Turing was investigating the capabilities of Turing machines, funny little devices which creep along a ticker-tape, and respond to the symbols they find there. Meanwhile over in the US, Alonzo Church was exploring the semantics of a formal system he had developed, called lambda calculus.

On first sight, the two topics appear to have little in common. But when the two men encountered each others’ work, they quickly realised something unexpected and profoundly important: that anything which can be expressed in lambda calculus can also be computed by a Turing machine, and vice versa. Shortly afterwards, a third approach known as recursion was thrown into the mix. Again, it turned out that anything recursive is Turing-computable, and vice versa.

This leads to the assertion we know as the Church-Turing thesis: that a process which is computable by any means whatsoever, must also be computable by a Turing machine.

It is important to stress that the Church-Turing thesis has good experimental support. Every computational system we know of obeys it: cellular automata, neural networks, Post-tag systems, logic circuits, genetic algorithms, string rewriting systems, even quantum computers*. Anything that any of them can do can (in principle) be done by conventional computational means.

So when Alex comments that “the brain itself isn’t structured like a Turing machine”, the obvious response is, “well, no, and neither are lambda calculus, cellular automata, and the rest”. (Come to think of it my phone doesn’t much look like a Turing machine either.)

The ‘dualism’ which distinguishes software from hardware (which Alex argues fails for the human brain), is not something built in from the outset. Rather it emerges from the deep, non-obvious fact that computational systems beyond a certain complexity can all emulate each other.

Needless to say, there have been no shortage of people claiming to have developed systems of different kinds which go ‘Beyond the Turing Limit’. (See Martin Davis’ paper on The Myth of Hypercomputation.) And who knows, maybe our brain embodies such a process. (I have my doubts, but if we’re going to find such a system anywhere, the brain is certainly an obvious place to look.)

The bottom line here is that if you don’t want to accept that

  0)   The human mind is computable

then I’d say you have three positions open to you:

  1)   It requires an extra metaphysical ingredient;
  2)   It’s a hypercomputer which violates the Church-Turing thesis;
  3)  It relies in an essential way on a non-computable process, meaning some inherent element of randomness.

Personally I’d order these 0312, in order of likeliness. (At the same time, I’d say talk of reverse-engineering the human brain is like a toddler planning a manned expedition to Mars. How about we concentrate on crossing the room without falling over first?)

 

*Quantum computers may be able to compute certain things quicker than conventional ones, but they won’t be able to compute essentially different things.

I meant to post something about John Derrick, a long-standing and much loved member of the logic group at Leeds University, who died in December. I only knew John in his later years (some time after his official retirement), but would regularly see him at the Wednesday afternoon logic seminar, which was often followed by a trip to the pub. He was always a thoughtful and benevolent presence in the seminar room, and made for entertaining and knowledgeable company over a drink.

For younger members, he was also something of a link to an earlier era, the days when the group was led by Martin Löb (of Löb’s theorem fame).

It is a testamant to his strength of character, and his love of the subject, that he continued to attend and contribute to these seminars through many year of ill-health, up until only a few weeks before his death.

An obituary by Garth Dales appeared in the LMS news-letter and a longer one can be read on the University of Leeds website.

A.   B-san, may I aks 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.

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 ℵ₀ (ℵ being the aleph, first letter of the Hebrew alphabet). Then come ℵ₁, ℵ₂, 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.

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 ACA₀, or “arithmetical comprehension”. Here we can sensibly analyse all the sets of numbers which Peano describes. However there are also many stronger systems, notably ATR₀, 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 ACA₀, and yet it is unprovable not just at that level, but in ATR₀ 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 Π⁰₂. Friedman additionally set himself the goal of finding a simpler Π⁰₁ 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.

Mathematics:
Axioms → Formal System → Theorems

Computation:
Program → Computer → Output

Life:
DNA → Pregnancy → Organism

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