academia | advice | alcohol | American Indians | architecture | art | artificial intelligence | Barnard | best | biography | bitcoin | blogging | broken umbrellas | candide | censorship | children's books | Columbia | comics | consciousness | cooking | crime | criticism | dance | data analysis | design | dishonesty | economics | education | energy | epistemology | error correction | essays | family | fashion | finance | food | foreign policy | futurism | games | gender | Georgia | health | history | inspiration | intellectual property | Israel | journalism | Judaism | labor | language | law | leadership | letters | literature | management | marketing | memoir | movies | music | mystery | mythology | New Mexico | New York | parenting | philosophy | photography | podcast | poetry | politics | prediction | product | productivity | programming | psychology | public transportation | publishing | puzzles | race | reading | recommendation | religion | reputation | review | RSI | Russia | sci-fi | science | sex | short stories | social justice | social media | sports | startups | statistics | teaching | technology | Texas | theater | translation | travel | trivia | tv | typography | unreliable narrators | video | video games | violence | war | weather | wordplay | writing

Tuesday, February 07, 2006

Infinite ladders, indescribable numbers

The University of Toronto has a great page of 5 mathematical proofs that lead to false conclusions. The idea is that these are logic puzzles where the goal is to find the error in the logic, which can be subtle.

One is the famous, brilliant proof that 1=2, which was the single most effective teaching tool I ever found for engaging high-school kids in math. I'd step through the proof, conclude that 1=2, and watch as kids fell out of their seats, angry and amazed, begging me to repeat the proof, and competing to find the error. (Any time you get high school students to exclaim in unison, you're doing something right. No amount of "naw, son!" exclamations about math is too many.)

But the page also contains two proofs whose falsehood I disagree with. That is, I think they are, in fact, correct, not incorrect as the site's authors insist.

(Stop reading now if you're not obsessed with math.)

The first is a proof that a ladder will fall infinitely fast when pulled. The proof itself is not remarkable, and they admit it is actually mathematically correct (unlike the other spurious proofs). It also makes logical sense: when the base of the ladder, which is leaning against the wall, is slowly pulled until it is almost horizontal, the next tiny bit of pulling it away from the wall means a long drop at its point of contact with the wall. And tiny change on one axis resulting in a large change on another is exactly the kind of ratio that approaches infinity.

Of course, this ratio approaches division by zero, but that is kosher because the denominator never actually reaches zero, just approaches it. In calculus these kind of trends have limits of infinity (or negative infinity) all the time.

So if the math isn't the problem in their view, what is? They claim that as you pull the ladder away from the wall, it loses contact with the wall, and therefore the whole situation, with its pure mathematical variables and basis in the pythagorean theorem, is incorrect.

This is like the answer "roosters don't lay eggs" (to the riddle, "If a rooster lays an egg on the exact middle of a barn roof, which side does it roll down?"--which is sort of clever but doesn't work logically because the riddle begins with the assumption that in this case, a rooster has laid an egg. (My math students in Brooklyn had no patience for smugness of this sort.)

But the rooster riddle is bullshit (it's obviously a rare, egg-laying rooster, just one of the majority of animal species that are still unclassified and unknown to science) and so is the supposed hole in the logic of the ladder proof. If you classify some non-zero molecular distance between the wall's molecules and the ladder's as being "touching", and the ladder is within this distance at rest, it's obviously possible to pull the ladder at a speed so slow that it never exceeds this distance.

Besides, in the proof, we are dealing with a mathematical ladder, not a real one. After all, a real ladder is not a line but a rough box; it encounters friction on the wall and in the air; "pulling" involves not a change in distance but a change in force which ripples through an object, temporarily altering its length; etc. If you accept the proposition that we are dealing with a mathematical ladder, i.e. a line that is kept in contact with the wall and the floor by a frictionless force, and whose base point is moved at a continuous speed, then the proof holds.

The other spuriously spurious proof is more subtle. It is a proof that "Every Natural Number can be Unambiguously Described in Fourteen Words or Less." (A natural number is just a positive integer.)

Here's the proof in a nutshell:

To prove: every natural number can be unambiguously described in fourteen words or less.
  1. Assume that not every natural number can be unambiguously described in fourteen words or less.
  2. Then there must be some smallest number n which cannot be unambiguously described in fourteen words or less.
  3. n can thus be described as "the smallest number which cannot be unambiguously described in fourteen words or less".
  4. But this is such a description, so there is a contradiction.
  5. Therefore, the initial assumption is false, and every natural number can be unambiguously described in fourteen words or less.
What's the problem, in the editors' opinion? That the description of "the smallest number which cannot be unambiguously described in fourteen words or less" is invalid, because, like "I am lying" (which is neither true nor false), it is self-referential.

Self-referentiality is a famous bugaboo in math; Bertrand Russell spent much of his life trying desperately to figure out a way around it (and thus to successfully order all mathematical knowledge), but it proved impossible.

However, there is a fundamental difference between statements that are self-referential and descriptions that are self-referential. A statement's self-reference, in the worst case, can make it invalid--not evaluable as either true or false. But what about a description? The general self-referential case is a description like "something that does not exist." But this isn't so bad--you can simply agree that the thing in question does not exist. Unlike statements, which carry the fundamental assumed nature of being either true or false, descriptions do not require the thing they describe to exist to be valid. The only thing they require--which then you can play with by claiming was not provided--is that they are themselves a description, a sentence, a label: that the description, itself, does exist. Statements deal with truth, while descriptions deal with existence; and falsehood doubles back on itself in a way that nonexistence does not.

So the worst-case scenario is actually a description like "something that is never described" or the equivalent "something that cannot be described".

Here is the natural number proof, reconfigured to its more general case:

To prove: everything can be described.
  1. Assume that not everything can be described.
  2. Thus there is at least one thing t that cannot be described.
  3. Thus t can be described as "something that cannot be described".
  4. But this means t can be described, a contradiction.
  5. Therefore the assumption was wrong, and everything can be described.
What exactly is wrong with this proof? The end result is the assertion that everything can be described, which is not just correct, but also happens to be a stable, consistent state--the logical equivalent of a Nash equilibrium. (Recall the moment in A Beautiful Mind when he stops his buddies from pursuing the hottest woman in the room, because her girlfriends will feel slighted and the whole effort will collapse into the stable state of no one scoring; but if they all agree to ignore her and pursue her girlfriends, a stable state of everyone scoring--except the hottie--will be achieved.)

As for natural numbers, why exactly can't we agree with the proof's conclusion that every natural number can be unambiguously described in fourteen words or less? The fallacy website's editors assert, amazingly, that "There is such a number n, and n is the smallest natural number that cannot be unambiguously described in fourteen words or less". So, um, what's the problem? They continue:

[but] the phrase "the smallest natural number that cannot be unambiguously described in fourteen words or less" is not a description of [n] (in the sense that is being used in the proof), because it is a phrase that cannot be self-consistently asserted about any number.
First of all, didn't they just assert that there is such a number, which thus would carry the "self-consistent" description forever? Well, if there is such a number, it seems correct that its status would be unstable, and it would immediately cease to satisfy the requirement of being indescribable.

(And, at its heart, their refutation is cheap: the "self-consistently" thing is a shameless switcheroo. If they had stipulated at the start that such a description wasn't kosher, we could have found a different way of describing any number n--as, say, "seventeen less than the eighty-fifth prime multiplied by forty-seven", or "Alice's favorite number", or by writing it on a napkin and agreeing to describe it as "that one" until the end of time.)

So if a number is indescribable, then it's not indescribable--a contradiction, to be sure. But they make the mistake of thinking that the proof overlooks this contradiction. The reason that the assumption is found to lead to a contradiction is precisely because the description is self-inconsistent, pointing to one number at one moment of the proof, and another at the next. Asserting that the description is self-consistent would be incorrect, but merely including it in your proof is not. If you are trying to prove a statement, and you find that its inverse is untenable, that helps your cause.

The editors' misunderstanding of this concept is made clear when they discuss Russell's Paradox (the sets-of-sets problem that stymied his effort to fit all knowledge in a hierarchy):

This is also related to Russell's Paradox in set theory: there is no such thing as the "set of all sets" (if there were, you could look at "the set of all sets that do not contain themselves". Let S be this set. Does S contain itself, or not? Either way leads to a contradiction).
First of all, they have the paradox wrong. It's not about whether there can be a "set of all sets", but just about set S, the "set of all sets that do not contain themselves". S's contradictions have nothing to do with whether or not there is a "set of all sets" because S's contradictions merely mean that S is not a set, so the set of all sets is neither bothered by having to accomodate it nor punished for excluding it.

like most paradoxes, Russell's is not a paradox at all if you step back and frame it in a larger context. Here it is in proof form:

To prove: There is no set of all sets that do not contain themselves.
  1. Assume there is such a thing as the set of all sets that do not contain themselves, which we will call S.
  2. Either S is a member of S, or it is not.
  3. Assume that S is a member of S. Then S contains a set that does contain itself, a contradiction.
  4. Therefore, S is not a member of S.
  5. Since S is not a member of S, it does not contain all sets that do not contain themselves, a contradiction.
  6. Therefore, the assumption leads to a contradiction, and there is indeed no set of all sets that do not contain themselves.
Again, where's the problem? The paradox only exists if you first accept the proof's assumption as true. As soon as you realize that the assumption was false, the paradox vanishes--you reach a stable logical state.

The editors at Toronto would make the mistake of crying foul because the description of a "set of all sets that do not contain themselves" used in line 1 is self-inconsistent. But that's ridiculous--the function of the proof is to demonstrate this self-inconsistency. If merely inclusing a self-inconsistent description invalidated a proof, it would be logically impossible to prove self-inconsistency!