Archive for the 'Logic' Category

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’


Hard and Harder

If you failed to solve Wednesday’s problem on Knights, Knaves and Crazies, take comfort from the fact that this has circulated among philosophers under the title “The Hardest Logic Problem Ever”. MIT philosopher George Boolos discussed it in the Harvard Review of Philosophy back in 1996. In that version, Crazies are never silent. But Oxford philosopher Gabriel Uzquiano soon observed that this can’t be the hardest logic problem ever, because it gets harder if the Crazies can be silent. Uzquiano’s new “hardest logic problem ever” was solved by the philosophers Gregory Wheeler and Pedro Barahona — and then solved again, substantially more elegantly, I think, in Wednesday’s comments section right here.

A few more thoughts, on the problem, its solution, and how to make it harder:

Continue reading ‘Hard and Harder’

Knights, Knaves and Crazies

SmullyanThe best dozen or so puzzle books ever written are, without a doubt, the works of Raymond Smullyan. If you’ve never encountered these, stop right now and order yourself a copy of What is the Name of This Book?, which is brilliant on multiple levels. On the surface, it’s a book of particularly amusing little brain teasers. One level down, those brain teasers contain a proof of Godel’s Incompleteness Theorem — solve all the riddles and you’ll have painlessly understood the proof!

Smullyan’s books are heavily populated by Knights who always tell the truth, Knaves who always lie, and bewildered travelers trying to distinguish one from the other via their cryptic utterances. Today’s puzzle is Smullyan-like in its set-up but considerably more difficult than most. It’s been proposed and discussed in philosophy journals, but I’m suppressing the sources (and rewording the problem) to make it a little harder to Google. I’ll of course pay appropriate homage to the authors when I post solutions in the near future. Meanwhile, if you’ve seen this before, or if you’ve found the answer on line, please restrain yourself from posting spoilers. But do post whatever you manage to come up with on your own.

And now to the puzzle:

Continue reading ‘Knights, Knaves and Crazies’

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 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’

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’

Big News

Last week, the highly distinguished Princeton Professor Ed Nelson announced a proof that the Peano axioms for arithmetic are inconsistent — and hence so is arithmetic itself. If true, this would be much bigger news than faster-than-light neutrinos. It would be bigger news than a discovery that the South had won the American Civil War. It would be far, far bigger news than a discovery that all life on Earth was intelligently designed.

There are, after all, multiple proofs that Peano Arithmetic (that is, the fragment of arithmetic described by the Peano axioms) is consistent. Among those, the simplest and most convincing (to the overwhelming majority of mathematicians) is this: The axioms of Peano Arithmetic, and therefore the theorems of Peano Arithmetic, are all true statements about the natural numbers — and a set of true statements cannot contradict itself.

Ed Nelson rejects that argument because (exempting himself from that overwhelming majority) he doesn’t believe in the set of natural numbers — or perhaps even in individual numbers when those numbers are very large. (How do you know that 810000 exists? Have you ever counted to it?)

Continue reading ‘Big News’

Friday Humor

Three logicians walk into a bar.

The bartender says: “Would any of you guys like a drink?”

The first logician says: “I don’t know.”

The second logician says: “I don’t know.”

The third logician says: “No.”

Hat tip to Adam Merberg, who isn’t sure of the source.

Click here to comment or read others’ comments.


voevodsky-80thVladimir Voevodsky, one of the world’s best and most influential mathematicians, has stirred up a bit of a hornet’s nest with a video lecture suggesting the possibility that the Peano Axioms — the standard axioms for arithmetic — might be inconsistent.

Since the Peano Axioms are known to be consistent, it’s tempting to dismiss the whole lecture as either a prank or a shocking display of ignorance. The latter temptation is buttressed somewhat by Voevodsky’s bold misstatement of Godel’s Incompleteness Theorem, which plays a central role in the lecture. On the other hand, Voevodsky is smarter than almost anyone else on earth, which earns him the benefit of the doubt — maybe what he’s saying is subtler than it seems. On the other hand, some of those in the “shocking display of ignorance” camp are among the few people in the world who might be as smart as Voevodsky.

To believe that the Peano Axioms are inconsistent, Voevodsky must reject all of the known proofs that they are consistent. In particular, he must reject the simplest and most convincing of all those proofs, which goes like this:

  1. The Peano Axioms, and therefore all of their logical consequences, are true statements about the natural numbers,
  2. A collection of true statements cannot contradict itself.
  3. QED.

Continue reading ‘Inconsistency’

Lord Russell’s Nightmare

bertieBertrand Russell, that most rational of men, was nonetheless plagued by intermittent depression and the occasional nightmare. Including this one, as reported by Russell’s confidante, the mathematician G.H. Hardy:

[Russell] was in the top floor of the University Library, about A.D. 2100. A library assistant was going round the shelves carrying an enormous bucket, taking down books, glancing at them, restoring them to the shelves or dumping them into the bucket. At last he came to three large volumes which Russell could recognize as the last surviving copy of Principia Mathematica. He took down one of the volumes, turned over a few pages, seemed puzzled for a moment by the curious symbolism, closed the volume, balanced it in his hand and hesitated….

Principia Mathematica, to which Russell had devoted ten years of his life, was his (and co-author Alfred North Whitehead‘s) audacious and ultimately futile attempt to reduce all of mathematics to pure logic. It is a failure that enabled some of the great successes of 20th century mathematics. And — the first volume having been published in December, 1910 — this is its 100th birthday.

Continue reading ‘Lord Russell’s Nightmare’

Eighty Years of Incompleteness

godelThis weekend marked the 80th anniversary of the most significant event in the history of logic since the days of Aristotle. On October 23, 1930, the 24-year-old Kurt Godel presented his incompleteness theorems to the Vienna Academy of Sciences.

The first incompleteness theorem says this: No matter what axioms you start with, there will always be statements in arithmetic that you can neither prove nor disprove. (I am glossing over some technicalities here, but in this context they are not important.) Some of those statements take the form “Such-and-such an equation has (or does not have) any solutions”. You tell me your axioms, and I’ll produce an equation that you can neither prove solvable nor prove insolvable.

Continue reading ‘Eighty Years of Incompleteness’

Basic Arithmetic, Part III: The Map is Not the Territory

Today let’s talk about consistency.

Suppose I show you a map of Nebraska, with as-the-crow-flies distances marked between the major cities. Omaha to Lincoln, 100 miles. Lincoln to Grand Island, 100 miles. Omaha to Grand Island, 400 miles.

You are entitled to say “Hey, wait a minute! This map is inconsistent. The numbers don’t add up. If it’s 400 miles straight from Omaha to Grand Island, then there can’t be a 200 mile route that goes through Lincoln!”

So a map can be inconsistent. (It can also be consistent but wrong.) Nebraska itself, however, can no more be inconsistent than the color red can be made of terrycloth. (Red things can be made of terrycloth, but the color red certainly can’t.)

With that in mind, suppose I give you a theory of the natural numbers — that is, a list of axioms about them. You might examine my axioms and say “Hey! These axioms are inconsistent. I can use them to prove that 0 equals 1 and I can also use them to prove that 0 does not equal 1!” And, depending on the theory I gave you, you might be right. So a theory can be inconsistent. But the intended model of that theory — the natural numbers themselves — can no more be inconsistent than Nebraska can. Inconsistency in this context applies to theories, like the Peano axioms for arithmetic, not to structures, like the natural numbers themselves.

Continue reading ‘Basic Arithmetic, Part III: The Map is Not the Territory’

Basic Arithmetic, Part II

Today’s mini-lesson in the foundations of mathematics is about the key distinction between theories and models.

The first thing to keep in mind is that mathematics is not economics, and therefore the vocabulary is not the same. In economics, a “model” is some sort of an approximation to reality. In mathematics, the word model refers to the reality itself, whereas a theory is a sort of approximation to that reality.

A theory is a list of axioms. (I am slightly oversimplifying, but not in any way that will be important here.) Let’s take an example. I have a theory with two axioms. The first axiom is “Socrates is a man” and the second is “All men are mortal”. From these axioms I can deduce some theorems, like “Socrates is mortal”.

That’s the theory. My intended model for this theory is the real world, where “man” means man, “Socrates” means that ancient Greek guy named Socrates, and “mortal” means “bound to die”.

But this theory also has models I never intended. Another model is the universe of Disney cartoons, where we interpret “man” to mean “mouse”, we interpret “Socrates” to mean “Mickey” and we interpret “mortal” to mean “large-eared”. Under that interpretation, my axioms are still true — all mice are large-eared, and Mickey is a mouse — so my theorem “Socrates is mortal” (which now means “Mickey is large-eared”) is also true.

Continue reading ‘Basic Arithmetic, Part II’

Godel, Fermat, Hercules

HerculesAndHydraYesterday I answered one of Coupon Clipper‘s questions about Godel’s Theorem. Today I’ll tackle the other: Does Godel’s Theorem matter on a day-to-day basis to practicing mathematicians?

And the answer is: Of course not. Mathematicians care about what’s true, not about what’s provable from some arbitrary set of axioms. (Of course this is an overgeneralization; some mathematicians have built distinguished careers on worrying about what’s provable from various sets of axioms. But they are a small minority.) Godel’s Theorem says that not all true things are provable. But for the most part, we’re happy just to know they’re true.

The flashiest example I can give you—and one I’ve used on this blog before—is Fermat’s Last Theorem, which says that no equation of the form xn + yn = zn has any solutions, as long as n is at least 3 and x, y and z are non-zero. Proving this was the was most famous unsolved problem in mathematics for 350 years until it was solved (to much public fanfare) by Frey, Serre, Ribet and Wiles in the 1980′s and 1990′s.

We know from that work that Fermat’s Last Theorem is true. However, we still don’t know whether Fermat’s Last Theorem follows from the standard axioms for arithmetic. And—this is the point—very few mathematicians care very much, at least by comparison to how much they care about the theorem itself. (Here is one of my favorite papers on the subject. Tellingly, the author is a philosopher.)

Continue reading ‘Godel, Fermat, Hercules’

First Things and Second Things

The occasional commenter who goes by the name Coupon Clipper has emailed me some interesting questions about Godel’s Theorem. I think I’ll answer them here.

The first question is about first-order versus second-order logic, so let me explain the distinction. When we reason formally about arithmetic, we need to clearly specify the ground rules. This means, among other things, specifying the language and grammar we’re allowed to use. A very simple language might allow us to say things like “2 + 3 = 5″ or “8 is an even number”. With a language like that, you could talk about a lot of sixth grade arithmetic, but you wouldn’t be able to say anything very interesting beyond that. To talk about the questions mathematicians care about, you need a language that contains words like “every”, as in Every number can be factored into primes or Every number can be written as a sum of four squares or Every choice of positiive numbers x, y, and z will yield a non-solution to the equation x3+y3=z3 . That language is called first-order logic.

With first order logic we can specify a set of axioms, and then follow a prescribed set of rules to deduce consequences. For example, if you’ve already established that every number is a sum of four squares, then you’re allowed to conclude that 1,245,783 is a sum of four squares. (The general rule is that if you’ve proved that every number has some particular property, then you’re allowed to conclude that any particular number has that property.)

Continue reading ‘First Things and Second Things’

Just the Facts

jackwebbDuring our brief intermission last week, commenters chose to revisit the question of whether arithmetic is invented or discovered—a topic we’d discussed here and here. This reminded me that I’ve been meaning to highlight an elementary error that comes up a lot in this kind of discussion.

It is frequently asserted that the facts of arithmetic are either “tautologous” or “true by definition” or “logical consequences of the axioms”. Those are three different assertions, and all of them are false. (This is not a controversial statement.)

The arguments made to support these assertions are not subtly flawed; they are overtly ludicrous. Almost always, they consist of “proof by example”, as in “1+1=2 is true by definition; therefore all the facts of arithmetic are true by definition”. Of course one expects to stumble across this sort of “reasoning” on the Internet, but it’s always jarring to see it coming from people who profess an interest in mathematical logic. (I will refrain from naming the worst offenders.)

So let’s consider a few facts of arithmetic:

Continue reading ‘Just the Facts’

The Self-Referential Test

This quiz amused the hell out of me. I hope it does the same for you.

Edited to add: In comments, Mike H points me (and you) to this even better quiz, which seems to have been the model for the one I linked to. Enjoy your day.

Non-Simple Arithmetic

complexThe Intelligent Design folk tell you that complexity requires a designer.

The Richard Dawkins crowd tell you that complexity must evolve from simplicity.

I claim they’re both wrong, because the natural numbers, together with the operations of arithmetic, are fantastically complex, but were neither created nor evolved.

I’ve made this argument multiple times, in The Big Questions, on this blog, and elsewhere. Today, I aim to explain a little more deeply why I say that the natural numbers are fantastically complex.

Continue reading ‘Non-Simple Arithmetic’

Trading Up

A reader has just emailed me a link to a Washington Post story about North Carolina workers losing their jobs to foreign competition. Presumably he believes there’s a larger moral here, because his subject line is “Wrong again, Steve”. Here is a slightly edited version of my emailed response:

It would be dishonest for me or anyone else to defend free trade by pointing to its advantages while ignoring its disadvantages.

It is equally dishonest to oppose free trade by pointing to its disadvantages while ignoring its advantages.

What you need is a framework that accounts for all the advantages and disadvantages, together with enough of a logical structure to instill confidence that nothing imporant has been overlooked. Thats what economic theory supplies. You can find that theory in the economics textbooks. You can also find (I think) a pretty good summary of it in The Big Questions.

My correspondent wrote back with a pointer to a website with fifty years of what he calls “extrapolatable stats” that he thinks supply the necessary framework. This misses the point entirely. There is no way a hodgepodge of numbers can settle the question of whether something’s been left out. For that you need a theory.

Continue reading ‘Trading Up’