## Friday, March 13, 2009

### You Can't Handle the Lack of Falsehood!

Short Round is at it again, calling me out to challenge me to a good old-fashioned Math-Off.* He's laid down his best moves, throwing out verbal accusations about his old grandpappy and comparing me to Joaquin Phoenix (?), and now it's time for me to step up and put him in his place. The subject at hand was the word "autological":

Q. What does autological mean?
A. Huh, that's sort of a random question. A word is autological if it has the property it denotes. For example, polysyllabic, being itself polysyllabic, is autological because it can be used to describe itself. Other examples include, unhyphenated, pronounceable, abstract, nonpalindromic, and adjectival. The opposite is heterological: the word monosyllabic is polysyllabic and therefore not autological, but/therefore it is heterological. (Most words are going to be heterological: like hairy and well-dressed.) Got it?
Q. Yeah, actually I knew that.
A. What, are you testing me?
Q. No, I have a question about the word and wanted to sort of, you know, set it up first.
A. Is the question whether autological is autological?
Q. Why, yes! That's exactly what I was going to ask.
A. Well, let's take a look. First let's see whether heterological is heterological. That question is basically a restatement of Russell's Paradox and therefore maybe more the domain of Dr. Math, but as my old grandpappy used to say, "F__k Dr. Math!"

So, Shorty, you're right about the connection to Russell's Paradox. In fact, it's this very kind of question that almost brought all of math tumbling down in the early part of the 20th century, although it seems to have mostly recovered now. The real issue at stake here is the idea of sets, and what possible sets you're allowed to construct. When you get down to it, math is really built on a foundation of sets; numbers themselves are just sets in disguise--for example, 0 is actually the empty set, 1 is the set containing the empty set as an element, and so on. But the word "set" is never formally defined, and can't be. If you think about it, this is the only possible way to avoid any circular logic; if "set" were defined in terms of some other words, then those words would themselves need definitions, etc., until we eventually either had an infinite number of words or something was defined in terms of "sets" again. In English this is OK, because we can eventually just point to things and say "I mean that!" but in math we don't have that luxury. You just try pointing to a set sometime.

Many people used to take the point of view that you could always construct a set by specifying the properties of its elements. So, for example, I could say, "Let A be the set of all whole numbers between 1 and 10," or "Let B be the set of all people with moustaches," and those sets would make sense. However, the problem occurs when you start trying to construct sets with self-referential properties; for example, you might like the set itself to be a member of itself. Some sets, like the sets A and B above, are clearly not members of themselves (a set can't grow a moustache), but maybe there are sets that could be, like the "set of all things that aren't made of glass." Unless sets are made of glass (which they aren't), that set would be a member of itself. So far, there's no real paradox, just some weird-looking sets. However, if you now construct "the set of all sets that are not members of themselves," we have an honest-to-Gödel paradox on our hands: Suppose the set exists, and call the set S. The question is, Is S is a member of itself? If it is, then it cannot be, because it fails the test for membership; therefore, it's not, so it is. And it goes on like this, ad infinitum.

If all of this seems like abstract nonsense to you (you're probably right, but) consider the following alternate formulations of the paradox and similar paradoxes:

--Imagine that all the librarians in the country are asked to compile lists of the books in their respective libraries. Since these lists are written in book-form and are kept in the library, some librarians include the catalogue among their lists of books; others don't. Now, imagine that all the librarians send the catalogues to a central library in Washington, where the head librarian makes a master catalogue of all those catalogues which don't include themselves. Should the master catalogue include itself?
--For each number, we can write out statements describing the number and find the statement that uses the fewest syllables. Now, let n be the number described by the statement, "the least number not describable using fewer than twenty syllables." Since this description only contains 19 syllables, n is describable by fewer than twenty syllables, and thus can't be equal to n.
--The barber of Seville, who is a man and is shaven, shaves all men in town who do not shave themselves, and only those men. Who shaves the barber? It can't be someone else, because then he wouldn't shave himself, so he would have to shave himself, but it can't be him, either.
--Groucho Marx once said he wouldn't want to join any club that would have him as a member. Fine. But what if he joined every club that wouldn't have him? Would he be a member of Texarkana Country Club? If yes, then no; if no, then yes.
--Your question about whether the word "heterological" is heterological, meaning not possessing the quality it denotes, can be rephrased in terms of sets as follows: Let W be the set of all words which do not possess the quality they denote; a word is heterological if it is a member of W. So the question is, then, does W contain the word meaning "is a member of W"? If so, then that word doesn't belong in W, therefore it does belong, etc.

In any event, "Uh-oh" is the correct answer.

A related paradox is the so-called "liar's paradox," also called the Epimenides paradox, after the famous stand-up comedian who popularized it around 600 B.C. The joke goes like this: A Cretan walks into a bar and says "All Cretans are liars!" Rim-shot. If the guy's telling the truth, then he's lying, and vice versa. A fun variant that I like to use at parties (courtesy of Raymond Smullyan) is this: Put a dollar bill in one of two envelopes. On the first envelope, write

1) "The sentences on both envelopes are false."

On the second envelope, write

2) "The dollar bill is in the other envelope."

The first claim can't be true, by the same reasoning as the liar's paradox (if it were true, then it would be false, etc.). So therefore, it must be false, right? That means that one of the two statements is true, but, again, it can't be the first one, so it must be the second. Thus, the dollar bill is in the first envelope. Imagine your guests' surprise when they open the first envelope and find it empty (because you put the money in the other envelope!)! Oh, they laugh and laugh.

Another related paradox is called "Newcomb's paradox," which goes like this: Suppose you're going on a gameshow, and you'll be presented with 2 boxes, box A and box B. Your choices are:

1) take box A and box B
2) take box B only

You are told that box A contains \$1000, and that box B either contains \$0 or \$1 million. Seems like an obvious choice, right? Either way, you stand to gain by taking both boxes. Here's the catch, though: the host tells you that somehow (either by clairvoyance, psychological observation, or computer simulation) the producers of the show knew ahead of time what decision you were going to make, and changed the contents of box B as a result. If you were going to just take B, they put the million inside; if you were going to take A and B, they put nothing inside B, so you'll just get \$1000. So, now what? Assuming you believe their claim, how do you act?

Now, I wouldn't be writing all this if there weren't a way out of this mess. I'm not ready to give up on math just yet. Just to warn you, though, the resolution can be scarier than the paradoxes. Ready, then? Here goes: the essential answer to all of these puzzles is "You CAN'T!"

That is, the mathematical wisdom that we now hold to, according to the hallowed Zermelo-Fraenkel axioms (sort of the owner's manual of math), is that there are some sets you just can't construct. So, for example, the set of all sets which don't contain themselves just isn't a set. It's nothing. Even though it's described in language reminiscent of sets, it does not exist. The librarian can't make a list of all catalogues not referencing themselves; there's no such thing as the least number not describable in fewer than twenty syllables; the barber can't shave everyone who doesn't shave himself; Groucho can't join every club that won't allow him; and it's impossible to consider all words which don't refer to themselves. The producers of The Newcomb's Paradox Show can't (reliably) claim to have predicted your actions, because whatever simulation they had of your brain could not have included the fact that you knew that they had simulated it! Or if it did, then it didn't include the fact that you knew that it knew that you knew... Again, to put things in the language of set theory, the set of things they claim to know about you cannot contain itself.

A consequence of all of this is that there are some logical statements that are neither true nor false. For example, the statement "the word 'heterological' is heterological" is neither true nor false, because assigning it either truth value (True or False) would be inconsistent. Similarly, the statement "the word 'autological' is autological" is neither true nor false, because either truth value would make it consistent with the axioms. If it were true, then it would be true; if it were false, then it would be false. Starting from the axioms of set theory, we could never hope to prove either statement. So in any logical sense, they are meaningless. And this, by the way, resolves the envelope problem as well, since the flaw in our deduction above was the assumption that statement 1 had to be either true or false.

This seems to fly in the face of everything we've been taught about truth and falsehood--namely, that statements are always either true or false. But consider for a moment, What if that statement is neither true nor false? Whoa.

In fact, we're not out of the woods yet, because, as Gödel showed in 1931, the consistency of the axioms themselves is not provable from the axioms. So it might happen that two perfectly logical deductions could lead to inconsistent conclusions--we can't prove that it's impossible. Later, he died of starvation because he was convinced that someone was trying to poison him. So, perhaps the best advice I can give is just not to think about these things too much.

As Tom Cruise said in A Few Good Men, "It doesn't matter what I believe [to be consistent with the Zermelo-Fraenkel axioms], it only matters what I can prove [as a consequence of the Zermelo-Fraenkel axioms]!"

-DrM

*A tradition dating back to ancient Greece, when Plato used to take on all challengers with his legendary taunt, "αγεωμετρητος μηδεις εισιτω."

**Listen, what happened between me and your grandfather (and grandmother) happened a long time ago and is really none of your business.

Travis said...

I'll post what I consider to be a painfully obvious link, to save others from the wracking internal debate over whether to do it:

http://xkcd.com/468/

Also, have you considered pitching this game show as an actual game show? Get an imposing panel of psychics, psychologists, and supercomputers together, and a charming Canadian to host the thing, maybe draw the thing out by putting the contestant through a series of "tests" to determine how they think... To make it work, you'd probably need to have a bunch of plants amongst the initial contestants. That way, you could show a number of contestants making the crazy-seeming choice to take only box B and being rewarded for it, which might help sell the plausibility of such a course of action to future actual contestants.

drmath said...

Travis, I should keep you on staff. I imagine there's an xkcd comic to match every post I've ever written. Someone care to prove me right?

The slogan for The Newcomb's Paradox Show could be, "The one game show we already know you're going to watch this fall!"

Travis said...

The panel could be called the Fortune Tellers.

Simon said...

Fuzzy logic tells you the answer to all these questions is 0.5

Deep thought would probably just take billions of years to interpolate that value and arive at 0.42

quine said...

A consequence of all of this is that there are some logical statements that are neither true nor false.

This is not right, or at the very least, it's contentious. The conclusion is susceptible to the strengthened liar. Instead of the statement 'this statement is false', consider the statement 'this statement is not true'. Now you are also barred from concluding that the statement is neither true nor false.

Matt said...

{0} is NOT the empty set.

{0} is the set that contains "the additive identity for real numbers." 0 is not equitable to the null set.

{ } is the empty set.