Diagonal arguments: once more with feeling

I’ve been thinking more about the diagonal argument this week, and realised my version for magmoidal cats with diagonals was insufficient to cover a massively important example: the category of partial recursive functions! This is because every partial endomorphism has a fixed global point, namely the undefined point: the partial function with empty domain. The same problem holds for arbitrary generalised points . So the diagonal argument can’t get started. Any general diagonal argument should be able to deal with the special case of partial recursive functions without special tweaks to deal with such behaviour. So while my magmoidal diagonal argument is valid, it needs more work to apply where one has partial functions.

The only curve with a unique focus is the parabola

Recently, an article with a breathless headline (since revised) was published on the ABC website about how a year 12 student in regional Victoria, Mubasshir Murshed, published a proof of the above result in an academic journal. I think this a good achievement and to be commended, but the way it is framed is…problematic.  The original headline, “Teenager’s parabola equation blows away maths world” could have done with some input from mathematicians (I understand how news works, the journalist probably had little choice in the matter). The quote from the editor of the Australian Mathematics Education Journal also seems to me to lack perspective. Publishing in an education journal is not the same as publishing in a mathematics journal, which requires something genuinely previously undiscovered.

I’m all for furthering the idea that everyone can discover interesting mathematics themselves, even if it was already known. That’s part of the fun in mathematics, figuring out how to understand existing work in a new way, or even the joy of realising you discovered a piece of ‘real’ mathematics that someone else had thought of. I definitely had fun deconstructing the proof and rewriting it (below!) in a way I felt more comfortable with. But heralding someone who does this as a “17-year-old mathematics genius” is, I feel, counterproductive to the promotion of mathematics more broadly. It can definitely prompt people to put themselves in the “I’m not a genius, I can’t do mathematics” box, when this is just not true. My colleague David Butler engages with people of all kinds of backgrounds with public mathematical play, and they often are doing little pieces of mathematical discovery without even realising it. Praising up doing mathematics as a work of “genius” alienates people.

It’s easy to praise such an achievement as Murshed’s, but the article missed an opportunity to highlight the way in which discovery in mathematics is cheap: you don’t need any special equipment! With access to the internet, and pen and paper there is little limit to what kinds of theoretical mathematics you can do. The idea that problems such as the result in the title are even amenable to proof is genuinely important. That abstract-looking mathematics can have a real-world impact (parabolic reflector design!) is important to know for non-mathematical policy-makers at the all levels, but also for people genuinely if there is to be an appreciation of mathematics in today’s society. There is also the message that mathematics is not ever truly finished, and that there can be more than one way to approach a theorem and its proof (see below).

With the grumpiness out the way (and I’m happy to discuss the pros and cons), I want to give a variation on the theorem and proof, assuming less than Murshed’s version. I am happy to take as a black box one of the equations he derives, because that is done by elementary geometry.

Theorem: A plane curve given by the graph of a differentiable function and with a unique focus is a parabola.

Third solution to writing 3 as a sum of three third powers!

Andrew Booker and Andrew Sutherland have found, using the the Charity Engine distributed computing platform, a third solution in integers to the equation , so we now know each of

• 1³ + 1³ + 1³

• 4³ + 4³ + (-5)³

• 569936821221962380720³ + (-569936821113563493509)³ + (-472715493453327032)³ (verify!)

is equal to 3. It is conjectured that there are infinitely many integer solutions, but we seem to be nowhere near that.

Talk notes from Groupoids, Graphs and Algebras

This week I am at the conference Groupoids, Graphs and Algebras in Sydney. I gave a talk based on these two blog posts:

• Cofibrations of internal groupoids and localisations by cospans
• Localisation by cospans redux

As well as the preprint

• The elementary construction of formal anafunctors

(which is a sequel to the papers Internal categories, anafunctors and localisations and
On Certain 2-Categories Admitting Localisation by Bicategories of Fractions).

The handwritten notes for my talk are here.

Believing in (in-)consistency

By this I mean the consistency, or inconsistency, of certain systems of mathematical axioms. There are very few systems, of very low strength, that we know are consistent. Presburger arithmetic is complete and consistent (and even decidable, but the decision procedure is has at least doubly-exponential runtime) but cannot even define the multiplication function . Once one has a system of axioms with at least the expressive strength of Robinson arithmetic Q (which doesn’t include induction!), then Gödel’s theorem kicks in and one can construct undecidable statements in the system, including the self-consistency sentence. However, one can get consistency statements assuming an extra fact, namely that if one assumes that the system could prove a certain countable ordering is in fact well-founded then consistency follows. This is known as ordinal analysis, and the original result due to Gentzen is that if one has the axioms of Peano arithmetic (PA) plus the assumption that the set of finite rooted trees (with a certain natural ordering) is well-founded, then PA is consistent. This follows from careful analysis of PA proofs, which are represented (following Gentzen) as finite rooted trees. Another way to look at it is that this ordered set is the ‘smallest ordinal PA cannot prove is well-ordered’, though this requires an external viewpoint. Often people implicitly identify the set of finite rooted trees with the (von Neumann) ordinal ε₀.

One might ask in what system such implications are proved—what is the metatheory here? This leads to the remark in a blog post by Russell O’Connor:

As I understand, Gentzen showed that believing in the consistency of PA is equivalent to believing in the well-foundedness of ε₀. This can be rephrased as a claim that a particular program, say the hydra game, terminates on all inputs. Therefore, if you believe in the well-foundness of ε₀ and you believe Gentzen’s argument, which is done in PRA, then you believe PA is consistent, even if it has impredicative induction principles.

PRA has consistency strength equivalent to the well-foundness of ω^ω, which can be stated again as the termination of some other program on all inputs. Presumably this equivalence is proved in a still weaker system.

Curious about this ‘still weaker system’, I asked on MathOverflow “What is the weakest system that suffices to prove that well-foundedness of ω^ω implies consistency of PRA?” Emil Jeřábek provided a very nice answer, and even ironed out some wrinkles: it gets more difficult to talk about what well-foundedness means as the background theory gets weaker. Instead of the classical definition, which requires talking about subsets of the collection, one talks about induction schema instead, and how complex formulas can be that one wants to use. But in any case, the short answer is that the ‘still weaker system’ is the theory PA^–, which is roughly the part of PA that models an ordered semiring (ie the natural numbers with their ordering) with no induction. This is basically Robinson arithmetic, which while incomplete (after Gödel) it is “only just” incomplete.

This then gets to the heart of ordinal analysis: if one believes the fragment of arithmetic capturing the ordered semiring structure of is consistent, then well-foundedness of ω^ω implies consistency of PRA. So then one should feel comfortable with Gentzen’s proof that PA’s consistency follows from the well-foundedness of ε₀. One may, like Voevodsky, question the consistency of PA, but the soundness of the proof of the implication only requires ‘believing’ a much weaker system is consistent.

One can represent, as Jeřábek does on MathOverflow, the set ω^ω as the set of all finite tuples of natural numbers; in essence , with an ordering—the shortlex order—reminiscent of the plain ordering of the natural numbers expressed in some base (secretly this is base ω!). I have a hard time imagining how this can fail to be well-founded, if I make the background assumption that ω itself is well-founded. And that is the point: one reduces consistency arguments to very concrete syntactical structures. We try to bootstrap ourselves up into believing systems are consistent through this process, though we really don’t know what the ordinal consistency strength for eg ZFC or even Z is.

One could try to go down the rabbit hole, and ask what is the corresponding result for Q: what well-foundedness statement is enough to prove Q’s consistency? But it appears that the theories are getting so weak that one needs to resort to different tools. As far as PA is concerned, Timothy Chow gives a conceptual statement (see Theorem 2) equivalent to the well-foundedness of ε₀

THEOREM 2. If M is a Turing machine that given i as input, outputs an ordinal M(i), and M(i) ≥ M(i+1) for all i, then the sequence stabilizes.

with a footnote saying “the theorem can be further weakened to assert the stabilization of all primitive recursive descending sequences of ordinals”. (Here by “ordinals” Chow means something he describes in finitary terms using finite nested lists à la Lisp)

If you find it ‘intuitive’ that ω^ω is well-founded, and Theorem 2 of Chow’s note convincing, then you have just been convinced that PA is consistent.

Two Ada books

At the end of last year and beginning of this year I finally read Sydney Padua’s very entertaining graphic novel The thrilling adventures of Lovelace and Babbage about (parallel universe) Ada Lovelace, and then tracked down what seems like the only book on the Lovelace’s correspondence, Ada, Enchantress of Numbers, by Betty Toole.

The title of the latter is a slight misquote of something Babbage wrote of Lovelace, describing her as “Enchantress of Number”. I have skimmed through the Lovelace–de Morgan correspondence before, painstakingly and faithfully LaTeXed by Christopher Hollings, and was hoping for something in the latter book of a similar nature. Unfortunately all mathematical content is excised. And even some minor typographical changes are pervasive, such as rendering abbreviations like Wed^dy (for Wednesday) as Weddy. More unfortunate in Toole’s book is the forced analogies that the author tries to make between the conceptual ideas of Ada the person with the design and structure of the Ada programming language. While undoubtedly a thorough treatment of Lovelace’s correspondence would require familiarity with 19th century cultural norms and social history, any examination of precedents of 20th century computer science nascent in the letters to Babbage also requires more than passing knowledge of computer science. Such enthusiastic sections can be safely skipped. But overreaching claims aside, one can see that Lovelace thought deeply about the mathematics she was learning, and how it might be applied to other situations, some rather novel. In the following letter of 1840 she is thinking about how one might mathematically analyse a peg solitare game.

I feel Toole’s book, which consists of chapters of (edited) letters of Lovelace together with explanatory text, lacks somewhat in that one almost always only gets the letters in one direction (there are a few letters from Babbage or de Morgan, for instance, to Lovelace)—unlike the digital Lovelace–de Morgan correspondence. However, at the least, one gets to see the development of Lovelace’s personality from childhood to married life and being a parent while trying to study mathematics, and on to her decline and slow death from cancer. The letters paint a fascinating picture of Victorian Society, whereby mesmerism is seen as a form of medical treatment (though not without some scepticism on Ada’s part against her mother’s urging), and electromagnetism is in the process of being discovered, and mathematics is just about to go through somewhat of a revolution (in the 1830s-40s rigorous analysis was just being established, as was logic as a mathematical discipline). Lovelace’s creativity is surprising, but I would not be surprised if there were periods of real mania, either drug-induced or due to mental health issues. This BBC article notes “At times, Ada certainly had an exaggerated sense of her own destiny. Many of her letters are very long and self-obsessed and often a bit over the top.” Metaphor is used freely and richly, though sometimes it is not clear whether it is fanciful and playful writing or being taken seriously; Toole at times says that Lovelace really did mean the more ‘spacey’ of the descriptions, though it really is not clear. As Stephen Wolfram describes it, some of the letters between Lovelace and Babbage during the drafting and editing of the translation of Meabrea’s article and Lovelace’s attached Translator’s Note read like thick and fast email conversation around modern research (there were of course at the time multiple post deliveries per day, plus servants dispatched with additional letters).

It is this type of modern metaphor that Sydney Padua, freed from the constraints of needing to be historically accurate, plays with freely. The only time the cyberpunk/alternate history asthetic with its modern metaphors feels out of place is in the one ‘real history’ chapter (the opener), where Lovelace goes to tweet about a Babbage party she is at, momentarily mistaking her fan for a smartphone. But once the alternate history starts, the jodhpurs-wearing, pipe-smoking Lovelace is a wonderful character. Padua infuses the writing with a Victorian feel by lifting phrases and dialogue from Lovelace’s and Babbage’s letters, giving pointers when this is done and where they came from, in footnotes. Oh yes, the footnotes. There are footnotes on footnotes. There are pages of endnotes on each chapter, giving real-world historical insight into the fictionalised version. Other historical characters get a look in, such as the engineer Isambard Kingdom Brunel (here seen in the two bottom left panels), or Queen Victoria, whose offer of a variety of knighthood Babbage refused (in real life as in the comic) as it did not come with the honorific ‘sir’.

There is also a lot of historical material in the appendices, including contemporary  articles that Padua sourced by trawling through Google scans of 19th century newspapers. Despite the fictional treatment of the historical characters, one can use Padua’s book at a stepping-off point to find real sources, which she carefully tracked down to inform her fiction, to read more about these larger-than-life personalities.

If only someone would edit a Lovelace–Babbage correspondence and included the mathematics and technical details, and gave informed commentary on the context coming from the history of mathematics at the time….

No rational number squares to 2, after D. Zeilberger

If is a given rational number, the process

write p/q = n + k/q, where 0 ≤ k/q < 1, equiv 0 ≤ k < q.
if k = 0: 
    halt;
else return q/k, and loop.

is guaranteed to halt, since we must eventually hit , as the denominator is strictly smaller after each non-terminating cycle.

Assume is a rational number satisfying . By inspection, . Apply the process above:

r = 1 + (r-1) 
--> 1/(r-1) = (r+1)/(r^2 - 1) = r+1 = 2 + (r-1)
--> 1/(r-1)

Which will never halt, so no such rational number can exist.

I learned this nice proof from Doron Zeilberger’s manuscript Two Motivated Concrete Proofs (much better than the usual one) that the Square-Root of 2 is Irrational .