Archive for the 'Math' Category

The Generalist

groth2I never met Alexander Grothendieck. I was never in the same room with him. I never even saw him from a distance. But whenever I think about math — which is to say, pretty much every day — I feel him hovering over my shoulder. I’ve strived to read the mind of Grothendieck as others strive to read the mind of God.

Those who did know him tend to describe him as a man of indescribable charisma, with a Christ-like ability to inspire followers. I’ve heard it said that when Grothendieck walked into a room, you might have had no idea who he was or what he did, but you definitely knew you wanted to devote your life to him.

And people did. In 1958, when Grothendieck (aged 30) announced a massive program to rewrite the foundations of geometry, he assembled a coterie of brilliant followers and conducted a seminar that met 10 hours a day, 5 days a week, for over a decade. Grothendieck talked; others took notes, went home, filled in details, expanded on his ideas, wrote final drafts, and returned the next day for more. Jean Dieudonne, a mathematician of quite considerable prominence in his own right, subjugated himself entirely to the project and was at his desk every morning at 5AM so that he could do three hours of editing before Grothendieck arrived and started talking again at 8:00. (Here and elsewhere I am reporting history as I’ve heard it from the participants and others who followed developments closely as they were happening. If I’ve got some details wrong, I’m happy to be corrected.) The resulting volumes filled almost 10,000 pages and rocked the mathematical world. (You can see some of those pages here).

I want to try to give something of the flavor of the revolution that unfolded in that room, and I want to do it for an audience with little mathematical background. This might require stretching some analogies almost to the breaking point. I’ll try to be as honest as I can. In the first part, I’ll talk about Grothendieck’s radical approach to mathematics generally; after that, I’ll talk (in a necessarily vague way) about some of his most radical and important ideas.

Continue reading ‘The Generalist’

Share/Save

The Rising Sea

grothAround 1970, Alexander Grothendieck, the greatest of all modern mathematicians and arguably the greatest mathematician of all time, announced — at the age of 42 — the official end of his research career. Another great mathematician once told me that he thought he knew why. Following two decades of discoveries and insights that, one after the other, stunned the mathematical world, Grothendieck had, for the first time, achieved an insight so unexpected and so consequential that he himself was stunned. Grothendieck had discovered his own mortality.

I am told that just a few hours ago, his vision proved accurate. But the notion of Grothendieck as a mortal seems hard to swallow. He dominated pure mathematics not just through the force of his ideas — ideas that seemed eons ahead of everyone else’s — but through the force of his personality. When, around 1960, he announced his audacious plan to solve the notoriously difficult Weil conjectures by first rewriting the foundations of geometry, dozens of superb mathematicians put the rest of their careers on hold to do their parts. The project’s final page count, including the twelve volumes known as SGA (Seminaire de Geometrie Algebrique) and the eight known as EGA (Elements de Geometrie Algebrique) approached 10,000 pages. The force and clarity of Grothendieck’s unique vision scream forth from nearly every one of those pages, demanding that the reader see the mathematical world in a new and completely original way — a perspective that has proved not just compelling, but unspeakably powerful.

In Grothendieck, modesty would have been ridiculous, and he was never ridiculous. Here, in his own words — words that ring utterly true — is Grothendieck’s own assessment of how he stood apart (translated from French by Roy Lisker):

Most mathematicians take refuge within a specific conceptual framework, in a “Universe” which seemingly has been fixed for all time – basically the one they encountered “ready-made” at the time when they did their studies. They may be compared to the heirs of a beautiful and capacious mansion in which all the installations and interior decorating have already been done, with its living-rooms , its kitchens, its studios, its cookery and cutlery, with everything in short, one needs to make or cook whatever one wishes. How this mansion has been constructed, laboriously over generations, and how and why this or that tool has been invented (as opposed to others which were not), why the rooms are disposed in just this fashion and not another – these are the kinds of questions which the heirs don’t dream of asking . It’s their “Universe”, it’s been given once and for all! It impresses one by virtue of its greatness, (even though one rarely makes the tour of all the rooms) yet at the same time by its familiarity, and, above all, with its immutability.

Continue reading ‘The Rising Sea’

Follow the Bouncing Ball

If you want to compute the circumference of the observable universe to within, say, the width of a human hair, you’ll need to know about 35 digits of π, though this never seems to deter a certain sort of person from memorizing the first 100, 200 or 500 digits. But it turns out there’s no need to memorize anything at all! You can recover any number of digits you like from a simple little physics experiment that I just learned about, though it was invented over ten years ago by Professor Gregory Galperin of Eastern Illinois University. His lovely little paper is here.

To see how it works, start with two identical billiards lined up in front of a wall like so:

Now push Ball 2 toward Ball 1 and count the collisions: First Ball 2 collides with Ball 1 and pushes it toward the wall. (At this point Ball 2 has transferred all its momentum to Ball 1 and stops moving). Then Ball 1 collides with the wall and bounces back toward Ball 2. Then Ball 1 collides with Ball 2 and pushes it off to a far-away place. Three collisions. That tells you that π starts with a 3.

If you want more accuracy, make Ball 2 exactly 100 times as heavy as Ball 1. This time the sequence of events is a little more complicated, but it turns out there are exactly 31 collisons. That tells you that π starts with 3.1.

Or if you prefer, make Ball 2 exactly 10,000 times as heavy as Ball 1. You’ll get exactly 314 collisions. π starts with 3.14.

Continue reading ‘Follow the Bouncing Ball’

Flashback

Last week, I posted video of my talk to the undergraduate math students on truth, provability and the fabric of the universe — and heard from several readers who requested that I post it in a non-flash format.

My readers’ wish is my command. Here is the file for download in an m4v format.

This is relatively low resolution. The best viewing is still the flash version here.

Click here to comment or read others’ comments.

Truth, Provability and the Fabric of the Universe

Here is my talk to the University of Rochester’s Society of Undergraduate Math Students on “Truth, Provability and the Fabric of the Universe”. The audience was great, and except for a couple of slips of the tongue (like “Sir William of Ockham” for “William of Ockham”), I thought it went very well.

Get the Flash Player to see this content.

(Click the lower right hand corner to view fullscreen, or click here for higher quality video).

Faithful readers will recognize multiple themes from the book The Big Questions, and from numerous past blog posts, including:

Continue reading ‘Truth, Provability and the Fabric of the Universe’

Many Many Worlds

tegmarkMax Tegmark is a professor of physics at MIT, a major force in the development of modern cosmology, a lively expositor, and the force behind what he calls the Mathematical Universe Hypothesis — a vision of the Universe as a purely mathematical object. Readers of The Big Questions will be aware that this is a vision I wholeheartedly embrace.

Tegmark’s new book Our Mathematical Universe is really several books intertwined, including:

  1. A brisk tour of the Universe as it’s understood by mainstream cosmologists, touching on many of the major insights of the past 2000 years, beginning with how Aristarchos figured out the size of the moon, and emphasizing the extraordinary pace of recent progress. In just a few years, cosmologists have gone from arguing over whether the Universe is 10 billion or 20 billion years old to arguing over whether it’s 13.7 or 13.8.

    Continue reading ‘Many Many Worlds’

A Pi-Day Treat

In 1706, the British astronomer John Machin calculated π to 100 digits (by hand of course). His trick was to notice that π = 16A – 4B where A and B are given by

If you’re computing by hand, this is an excellent discovery, because the series for A involves a lot of divisions by 5, which are a lot easier to calculate than, say, divisions by 7, and the series for B converges very fast, so just a few terms buys you a whole lot of accuracy. (Try using, say, just the first four terms of A and just the first term of B to see what I mean.)

Machin’s 100 digits were a substantial improvement over the 72 digits obtained just a little earlier by Abraham Sharp, using the far less efficient series

In 1729, a Frenchman named de Lagny got all the way to 127 digits, but, in the words of the scientist/engineer/philosopher/historian Petr Beckmann (of whom more later), de Lagny “sweated these digits out by Sharp’s series, and so exhibited more computational stamina than mathematical wits.”

Machin’s methods were ingenious, but no more ingenious — and certainly no more striking — than John Wallis’s 1655 discovery that


which still looks awesome to me after decades of familiarity.

Continue reading ‘A Pi-Day Treat’

Hi, Mom!

MomMy mother, who reads this blog, reports that she’s lost a few nights’ sleep lately, tormented by thoughts of Knights, Knaves and Crazies. Serves her right. Once when she and I were very young, she tormented me with a geometry puzzler that I now know she must have gotten (either directly or indirectly) from Lewis Carroll; you can find it here. If she remembers the solution, she should be able to sleep tonight.

Herewith, a proof that a right angle can equal an obtuse angle. The puzzle, of course, is to figure out where I cheated.

But wait! Let’s do this as a video, since I’m starting to fool around with this technology and could use the practice. Consider this more or less a first effort. If you prefer the old ways, you can skip the video and read the (identical) step-by-step proof below the fold.

Get the Flash Player to see this content.

Or, if you prefer to skip the video, start here:

Continue reading ‘Hi, Mom!’

News From The Math World

Big news from the math world:

One of the oldest problems in number theory is the twin primes problem: Are there or are there not infinitely many ways to write the number 2 as a difference of two primes? You can, for example, write 2 = 5 -3, or 2 = 7 – 5, or 2 = 13 – 11. Does or does not this list go on forever? There are very strong reasons to believe the answer is yes, but many a great mathematician has tried and failed to find a proof.

Here’s a related problem: Are there or are there not infinitely many ways to write the number 4 as a difference of two primes? What about the number 6? Or 8? Or any even number you care to think about? It seems likely that the answer is yes in every case, though no proof is known in any case. But….

Continue reading ‘News From The Math World’

Seven Trees in One

When you met the late Armen Alchian on the street, he used to greet you not with “Hello” or “How ya doin’?”, but with “What did you learn today?” Today I learned that there are contexts in which the most ludicrous reasoning is guaranteed to lead you to a correct conclusion. This is too cool not to share.

But first a little context. The first part is a little less cool, but it’s still fun and it will only take a minute.

First, I have to tell you what a tree is. A tree is something that has a root, and then either zero or two branches growing out of that root, and then either zero or two branches (a “left branch” and a “right branch”) growing out of each branch end, and then either zero or two branches growing out of each of those branch ends, and so on. Here are some trees. (The little red dots are the branch ends and the big black dot is the root; these trees grow upside down.)

A pair of trees is, as you might guess, two trees — a first and a second.

There are infinitely many trees, and infinitely many pairs of trees, and purely abstract considerations tell us that there’s got to be a one-one correspondence between these two infinities. But what if we ask for a simple, easily describable one-one correspondence? Well, here’s an attempt: Starting with a pair of trees, you can create a single tree by creating a root with two branches, and then sticking the two trees from the pair onto the ends of the two branches. Like so:

Continue reading ‘Seven Trees in One’

A Sip of Monstrous Moonshine


You and a stranger have been instructed to meet up sometime tomorrow, somewhere in New York City. You (and the stranger) can decide for yourselves when and where to look for each other. But there can be no advance communication. Where do you go?

Me, I’d be at the front entrance to the Empire State Building at noon, possibly missing my counterpart, who might be under the clock at Grand Central Station. But, because there are only a small number of points in New York City that stand out as “extra-special”, we’ve at least got a chance to find each other.

A Schelling point is something that stands out from the background so sharply that we can expect people to coordinate around it. Schelling points are on my mind this week, because I’ve just heard David Friedman give a fascinating talk about the evolution of property rights, and Schelling points play a big role in his story. But that story is not the topic of this post.

Instead, I’m curious about the Schelling points that say, two mathematicians, or two economists, or two philosophers, or two poets, or two street hustlers might converge on. Suppose, for example, that you asked two mathematicians each to separately pick a number between 200 and 300, with a prize if their answers coincide. I’m guessing they both go for 256, the only power of two within range.

Continue reading ‘A Sip of Monstrous Moonshine’

Accounting for Numbers

Over at Less Wrong, the estimable Eliezer Yudkowsky attempts to account for the meaning of statements in arithmetic and the ontological status of numbers. I started to post a comment, but it got long enough that I’ve turned my comment into a blog post. I’ve tried to summarize my understanding of Yudkowsky’s position along the way, but of course it’s possible I’ve gotten something wrong.

It’s worth noting that every single point below is something I’ve blogged about before. At the moment I’m too lazy to insert links to all those earlier blog posts, but I might come back and put the links in later. In any event, I think this post stands alone. Because it got long, I’ve inserted section numbers for the convenience of commenters who might want to refer to particular passages.

1. Yudkowsky poses, in essence, the following question:

Main Question, My Version: In what sense is the sentence “two plus two equals four” meaningful and/or true?

Yudkowsky phrases the question a little differently. What he actually asks is:

Main Question, Original Version: In what sense is the sentence “2 + 2 = 4″ meaningful and/or true?”

This, I think, threatens to confuse the issue. It’s important to distinguish between the numeral “2″, which is a formal symbol designed to be manipulated according to formal rules, and the noun “two”, which appears to name something, namely a particular number. Because Yudkowsky is asking about meaning and truth, I presume it is the noun, and not the symbol, that he intends to mention. So I’ll stick with my version, and translate his remarks accordingly.

2. Yudkowsky provisionally offers the following answer:

Continue reading ‘Accounting for Numbers’

Simple as ABC

The (really really) big news in the math world today is that Shin Mochizuki has (plausibly) claimed to have solved the ABC problem, which in turn suffices to settle many of the most vexing outstanding problems in arithmetic. Mochizuki’s work rests on so many radically new ideas that it will take the experts a long time to digest. I, who am not an expert, will surely die with only a vague sense of the argument. But based on my extremely limited (and possibly mistaken) understanding, it appears that Mochizuki’s breakthrough depends at least partly on his willingness to abandon the usual axioms for the foundations of mathematics and replace them with new axioms. (See, for example, the first page of these notes from one of Mochizuki’s lectures. You can find other related notes here.)

That’s interesting for a lot of reasons, but the one that’s most topical for The Big Questions is this: No mathematician would consider rejecting Mochizuki’s proof just because it relies on new axiomatic foundations. That’s because mathematicians (or at least the sort of mathematicians who study arithmetic) don’t particularly care about axioms; they care about truth.

There’s a widespread misconception that arithmetic is about “what can be derived from the axioms”, which is a lot like saying that astronomy is about “what can be discovered through telescopes”. Axiomatic systems, like telescopes, are investigative tools, which we are free to jettison when better tools come along. The blather of thoughtless imbeciles notwithstanding, what really matters is the fundamental object of study, whether it’s the system of natural numbers or the planet Jupiter.

Mathematicians care about what’s true, not about what’s provable; if a truth isn’t provable, we’re fine with changing the rules of the game to make it provable.

Continue reading ‘Simple as ABC’

The Visionary

I mentioned earlier this week that I’d been crafting a long post on the fabric of the Universe when I was sidetracked by relatively mundane political events. Now I’ve been sidetracked again by the entirely unexpected (to me) news of the death from melanoma, at age 65, of the Fields Medalist Bill Thurston, who devoted his life to understanding the shape of space.

One-dimensional topology is the study of curves and two-dimensional topology is the study of surfaces. Both subjects are quite well understood. Thurston was the king of three-dimensional topology, which gains additional interest from the fact that we perceive ourselves as living in a three-dimensional Universe. Three-dimensional topology attempts to classify all the possible shapes for that Universe.

One of course is also interested in four, five, six and many-dimensional topology, four dimensions being of particular interest because they can be used to model space together with time. But although three dimensions are more complicated than two and two are more complicated than one, it turns out that when you go much higher, a lot of things get simpler. Consider knots, for example. There are no knots inside a one or two dimensional space; a knot needs three dimensions in which to pass over and under itself. But in more than three dimensions, you can untie any knot just by pulling on its ends — roughly because the additional dimensions give it so much space in which to untangle itself. For those and related reasons, topology is often hardest in three and four dimensions — coincidentally (or maybe not) the very dimensions most relevant to the way we experience the world.

Thurston revolutionized three-dimensional topology in the 1980s with his geometrization conjecture, which says that any three-manifold (the three-dimensional analogue of a smooth curve or surface) can be cut up into pieces, each of which exhibits one of eight permissible geometries. The simplest of those geometries is the flat three-dimensional space you think you see around you, where you can draw three straight lines in mutually perpendicular directions and extend them forever. Another is the geometry of the three-dimensional sphere, which is an analogue of the two-dimensional surface of the earth, where any “straight” line eventually circles back to meet itself.

The geometrization conjecture was important, but what really mattered was the vast array of new techniques Thurston introduced for visualizing and understanding the structure of three-manifolds. When those techniques came on line in the early 1980s, he was widely acclaimed as the mathematician of the decade.

One thing that set Thurston apart was his insistence that mathematics is a human study, and that it’s the mathematician’s job to communicate not just theorems and proofs, but a unique way of thinking. Stories are often told of mid-twentieth century mathematicians (usually French) who, when asked a question about their work, would scribble a picture on the blackboard, deliberately stand in front of that picture to shield it from everyone else’s view, and then, having studied it a few minutes, erased the picture, turned around, and gave a purely formal explanation designed to obscure all of the motivation and insight. Nobody ever told a story like that about Bill Thurston. Here he is, talking about the mystery of three-manifolds; dip in at a random moment and chances are excellent you’ll hear him talking not about how he proved a theorem but about how he sees the world:

Continue reading ‘The Visionary’

Chain Reaction


If you study economics, or statistics, or chemistry, or mathematical biology, or thermodynamics, you’re sure to encounter the notion of a Markov chain — a random process whose future depends probabilistically on the present, but not on the past. If you travel through New York City, randomly turning left or right at each corner, then you’re following a Markov process, because the probability that you’ll end up at Carnegie Hall depends on where you are now, not on how you got there.

But even if you work with Markov processes every day, you’re probably unaware of their origins in a dispute about free will, Christianity, and the Law of Large Numbers.

Continue reading ‘Chain Reaction’

Tuesday Puzzle

There’s an old puzzle popular among a certain type of schoolchildren that challenges the solver to write as many positive integers as possible using exactly four 4′s, together with some set of mathematical operations. (As is often the case with school children, the exact rules tend to get negotiated in real time as the puzzle is being solved.) Some examples are:

But when I became a man, I put away childish things. So here’s the grown-up version of the problem, which I got from Mel Hochster over 20 years ago, and still don’t know how to solve:

This being a grown-up problem, the rules are carefully specified:

Continue reading ‘Tuesday Puzzle’

The Number Devil

devilIn the comments section of Bob Murphy’s blog, I was asked (in effect) why I insist on the objective reality of the natural numbers (that is, the counting numbers 0,1,2,3…) but not of, say, the real numbers (that is, the numbers we use to represent lengths — and that are themselves represented by possibly infinite decimal expansions).

There seem to be two kinds of people in the world: Those with enough techncal backgroud that they already know the answer, and those with less technical background, who have no hope — at least without a lot of work — of grasping the answer. I’m going to attempt to bridge that gap here. That means I’m going to throw a certain amount of precision to the winds, in hopes of being comprehensible to a wider audience.

Continue reading ‘The Number Devil’

That Does Not Compute

stanleyStanley Tennenbaum was an itinerant mathematician with, for much of his adult life, no fixed address and no permanent source of income. Sometimes he slept on park benches. He didn’t have a lot of teeth.

But if you were involved with mathematics in the second half of the twentieth century, sooner or later you were going to cross paths with Stanley, probably near the coffee machine in a math department. He’d proudly show you the little book he carried in his breast pocket, with the list of people to whom he owed money. Then he’d teach you something, or he’d tell you a good story.

Stanley had little tolerance for convention. His one permanent job, at the University of Rochester, came to an abrupt end during a faculty meeting where he spit on the shoes of the University president and walked out. Surely the same personality trait had something to do with his departure from the University of Chicago without a Ph.D., though the paper he wrote there (at age 22) has acquired fame and influence far beyond many of the doctoral theses of his more conventionally successful classmates. I’d like to tell you a little about that paper and what I think it means for the foundations of mathematics.

Continue reading ‘That Does Not Compute’

Humpty Dumpty’s Math Puzzle

humptyGreg Mankiw, with a hat tip to his son Nicholas, asks for a plot of the function xx, where x is a real variable. The answer he points to (provided by Pedagoguery Software) gives this picture/expanation:

Continue reading ‘Humpty Dumpty’s Math Puzzle’

Loose Ends

I’m eager to summarize the (largely excellent) discussion of last week’s nightmares and to talk about what it all means. I’ll surely get to that in the next few days. But meanwhile, we have another loose end to tie up.

I recently asked what comes next in the following series:

The answer, of course, is

Please raise your hand if you found this intuitively obvious.

In case your hand didn’t go up, consider the following sequence:

Continue reading ‘Loose Ends’

Touched by Greatness

Roger Godement, 1970I continue to be bowled over daily by the high quality of the discussion at MathOverflow, and the prominence of many of the frequent participants. But this one was special:

A newbie poster asked for a pointer to a proof of the “de Rham-Weil” theorem. There’s a bit of ambiguity about what theorem this might refer to, but I had a pretty good of what the poster meant, so I responded that the earliest reference I know of is in Grothendieck‘s 1957 Tohoku paper — which led another poster to ask if this meant de Rham and Weil had had nothing to do with it.

This triggered an appearance from the legendary Roger Godement (had he been lurking all this time?), now aged 91 and one of the last survivors of the extraordinary circle of French mathematicians who rewrote the foundations of topology and geometry in the mid-20th century and changed the look, feel and content of mathematics forever. I tend to think of them as gods and demigods. Godement’s indispensable Theorie des Faisceaux was my constant companion in late graduate school. And now he has emerged from retirement for the express purpose of chastising me:

Continue reading ‘Touched by Greatness’

IQ Test

What comes next in the following series?

(Hint: This is a calculus problem.)

Click here for the answer. Explanation forthcoming in a few days.

Click here to comment or read others’ comments.

Uh Oh

How secure is Internet security? A team of researchers recently set out to crack the security of about 6.6 million sites around the Internet that use a supposedly “unbreakable” cryptosystem. The good news is that they succeeded only .2% of the time. The bad — and rather shocking — news — is that .2% of 6.6 million is almost 13,000. That’s 13,000 sites with effectively no security. The interesting part is what went wrong. It’s a gaping security hole that I’d never stopped to consider, but is obvious once it’s pointed out.

Continue reading ‘Uh Oh’

Who Expected THAT?

Suppose you go around taking extremely close-up black-and-white pictures of randomly chosen natural and unnatural objects (rocks, trees, streams, buildings, etc.). What do they look like?

Well, each one looks like a patch of varying shades of gray, of course. But do some patches arise more than others? If each of your close-ups is, say, three pixels by three pixels, Which would you expect to see more of:

This? Or this?

Continue reading ‘Who Expected THAT?’

Rock On

rockI don’t trust rocks. Rocks keep fooling me. They sit there looking all solid until you examine them more carefully and find out they’re mostly empty space, with a smattering of charged particles here and there. Then you look a little deeper and find out those charged particles are nothing like they first appeared. They don’t even have locations. Rocks, and their constituents, are nothing at all like they first present themselves. But at least they’re real. I think.

Now here’s what genuinely baffles me: Apparently there are people in this world (and even, occasionally, in the comments section of this blog) who haven’t the slightest doubt about the existence of rocks, galaxies, squirrels, and the rest of the physical universe, but who suddenly turn into hardcore skeptics re the existence of mathematical objects like the natural numbers. (Many of these people, I suspect, are in fact affecting skepticism because of a badly mistaken belief that it makes them look sophisticated. But that’s speculation on my part, so let’s put it aside and take their positions at face value.) I just don’t get this. Why on earth would, say, a scientist, commit to the belief that there’s a physical universe out there but not a mathematical one, when we know that our perceptions of the physical universe demand constant revision, whereas our perceptions of the mathematical universe are largely eternal. My conception of the natural numbers is very close to Euclid’s; my conception of an atom bears almost no resemblance to Demosthenes’s.

Continue reading ‘Rock On’

The Big Surprise

Back in the 1930′s, Kurt Godel proved two amazing facts about arithmetic: First, there are true statements in arithmetic that can’t be proven. Second, the consistency of arithmetic can’t be proven (at least not without recourse to logical methods that are on shakier ground than arithmetic itself).

Yesterday, I showed you Gregory Chaitin’s remarkably simple proof, of Godel’s first theorem. Today, I’ll show you Shira Kritchman and Ron Raz’s remarkably simple (and very recent) proof of Godel’s second theorem. If you work through this argument, you will, I think, have no trouble seeing how it was inspired by the paradox of the surprise examination.

Continue reading ‘The Big Surprise’

Berry Interesting

confiture and ingredientsToday, I’m going to give you a short, simple proof of Godel’s First Incompleteness Theorem — the one that says there are true statements in arithmetic that can’t be proven. The proof is due to Gregory Chaitin, and it is far far simpler than Godel’s original proof. A bright high-schooler can grasp it instantly. And it’s wonderfully concrete. At the end, we’ll have an infinite list of statements, all easy to understand, and none of them provable — but almost all of them true (though we won’t know which ones).

Continue reading ‘Berry Interesting’

A Tale of Three Paradoxes

This is a tale of three paradoxes and why they matter.

  • First, the ancient Liar Paradox: “This sentence is false”. If this sentence is true, it must be false. If it’s false, it must be true.
  • Next, the century-old Berry Paradox: Call a phrase “short” if it contains fewer than 13 words. The English language contains a finite number of words, and hence a finite number of short phrases. Hence there must be some natural numbers that can’t be described by any short phrase. Among these natural numbers, there must be a smallest. What is that natural number? Why, it’s the smallest natural number that can’t be described by any short phrase, of course. Except that this number is in fact described by the short phrase in boldface.
  • Finally, the more modern Paradox of the Surprise Examination (or the Unexpected Hanging), which we discussed yesterday.

The paradoxes are slippery, because they are stated in the imprecise language of English. But each of them has inspired a precise mathematical counterpart that is central to a brilliant argument in mathematical logic.

Continue reading ‘A Tale of Three Paradoxes’

The Surprise Exam, and More Surprises

surpriseexamIf you’re the sort of person who reads this blog, you’re likely to be familiar with the paradox of the unexpected hanging, which has been floating around since 1943 but achieved popular notoriety around 1969 through the writing of Martin Gardner. But you’re less likely to be aware that the unexpected hanging plays a central role in a wonderful new piece of serious mathematics related to algorithmic complexity, Godel’s theorems, and the gap between truth and provability.

The unexpected hanging might as well be a surprise examination, and that’s the form in which I present this paradox to my students every year: In a class that meets every weekday morning, the professor announces that there will be an exam one day next week, but that students won’t know exactly which day until the exams are handed out.

The students, of course, immediately start trying to guess the day of the exam. One student (call him Bob) observes that the quiz can’t be on Friday — because if it is, the students will know that by Thursday afternoon. After all, if Monday, Tuesday, Wednesday and Thursday mornings have all passed by, only Friday remains. A Friday exam can’t be a surprise exam.

A more thoughtful student (call her Carol) observes that this means the quiz must be on one of Monday, Tuesday, Wednesday or Thursday — and that if it’s on Thursday, they’ll know that by Wednesday night. After all, Friday’s ruled out, so if Monday, Tuesday and Wednesday have passed by, then only Thursday remains. That rules out a surprise exam on Thursday.

Another student (call him Ted) observes that thanks to Bob and Carol, we know the exam must be on one of the first three days of the week — which means that if it’s not on Monday or Tuesday, it must be on Wednesday. Therefore if it’s on Wednesday, they’ll know this by Tuesday night. Scratch Wednesday from the list of possibilities.

Now Ted’s girlfriend Alice points out that the exam can’t be on Tuesday either. Whereupon Bob concludes that the exam must be on Monday. But wait a minute! Carol points out that if they know the exam will be on Monday, it can’t be a surprise. Therefore no surprise exam is possible.

The students, relieved, decide not to study. But they’re awfully surprised when they show up in class the following Tuesday and the professor hands out an exam.

Continue reading ‘The Surprise Exam, and More Surprises’

Beauty, Truth and Symmetry

galoisToday is the 200th birthday of Evariste Galois, who did not live to celebrate his 21st, but found time in his short 20 years to develop a circle of ideas that permeate modern mathematics. We know of these ideas because Galois spent the night of May 30, 1832 scribbling them furiously in a letter to a friend, in advance of the fatal duel he would fight the following morning. According to the great mathematician Hermann Weyl, “This letter, if judged by the novelty and profundity of ideas it contains, is perhaps the most substantial piece of writing in the whole literature of mankind.”

(If this were a less serious post, I might suggest that this famous letter was the first example of a Galois Correspondence.)

Now, two centuries later, every first year graduate student in mathematics spends a semester studying Galois Theory, and many devote their subsequent careers to its extensions and applications. Many of the greatest achievements of modern mathematics (for example, the solution to Fermat’s Last Theorem) are, at their core, elucidations of Galois’s 200-year-old insight.

Continue reading ‘Beauty, Truth and Symmetry’