Fundamental Impossibilities

impossibilities

An Understanding of our fundamental limitations is among the most important contributions of science and of mathematics. There are quite a few cases where things that seemed possible and had been pursued for centuries in fact turned out to be fundamentally impossible. Ancient geometers thought that any two geometric lengths are commensurable, namely, measurable by the same common unit. However, for a right triangle with equal legs, the leg and the hypotenuse are incommensurable. In modern language (based on the Pythagorean theorem), this is the assertion that the square root of two is not a rational number. This was a big surprise in 600 BCE in ancient Greece (the story is that this discovery, attributed to a Pythagorean named Hippasus, perplexed Pythagoras to such an extent that he let Hippasus drown). Two centuries later, Euclid devoted the tenth book of his work The Elements to irrational quantities. The irrationality of the square root of 2 is an important landmark in mathematics. Similarly, the starting point of modern algebra can be traced back to another impossibility result. Algebraists found formulas for solving equations of degrees two, three, and four. Abel and Galois proved that no such formula is possible for general equations of degree five and above. This theory also led to a solution of a problem that remained unsolved from the ancient Greek era: finding a method of trisecting a general angle with a compass and a ruler. Galois’ theory demonstrated that no such method exists.

There are other important impossibility results. We have already mentioned Gödel’s impossibility result, asserting that it is not possible to prove (nor even to state) the consistency of mathematics from within mathematics. It is believed that there are inherent impossibilities for computers (and for any computational devices). This is the famous conjecture that P is different from NP. An impossibility theorem of Gibbard and Sattherthwaite asserts that for an election with more than two candidates and at least two voters, there does not exist a voting method; that is, there is no method for choosing a winner, based on the voters’ preferences, which is immune to manipulation. Impossibility insights outside mathematics, like the impossibility of building a perpetuum mobile, of turning iron into gold, and (most likely) of traveling in time, are related to profound scientific understanding.  And, of course, the impossibility of traveling quicker than the speed of light is one of the famous and mind-boggling insights of science.

Here is a post on related things by Dick Lipton,

About these ads
This entry was posted in Philosophy, What is Mathematics and tagged . Bookmark the permalink.

7 Responses to Fundamental Impossibilities

  1. Pingback: Impossible « EH

  2. Abu Alon says:

    Can you comment on our interest and joy of leraning about fundamental possibilities vs. fundamental impossibilities, the later indeed more exciting?

  3. Gil Kalai says:

    Dear Abu Alon,

    I am not sure which is more exciting and often the most exciting aspects are new understandings and possibilities derived from the impossibility results. For example, I suppose that before Cook and Levin people thought that some problems are not feasible because they require “complete enumeration” (so this was an even stronger belief than “no polynomial time algorithm exists”), while perhaps other people believed (or implicitely assumed) that “in principle” computers can solve any problem we can ask them to solve. The exciting thing was that Cook, Levin, and Karp put the issue on formal grounds and introduced the class “NP” and understood polynomial reductions, and this have led to the much more complete picture we have today on the limmitation of computation. (Anyway, excitement is a subtle thing. What is really more exciting building or destroying?) So what do you think? What do you find more exciting? Exploring imposibilities, exploring possibilities, or perhaps it is all really quite the same.

  4. Ori says:

    >it is not possible to prove (nor even to state) the consistency of mathematics from within mathematics.

    In what sense is it not possible to state it? you can write a sentence A which means “ZFC is consistent” in ZFC.
    However, it is true that Con(ZFC) implies Con(ZFC+(-A)), which is somewhat counterintuitive.

  5. rjlipton says:

    I disagree a bit here.

    One must be very careful what impossible means. For example, iron into gold I thought is possible in principle thru nuclear methods. The lack of a proof of consistency of ZF is fundamental, but seems to have no impact on practicing mathematicians.

    Even a perpetual motion machine, while impossible, one must be very careful. I can imagine a century ago a proof that no 10 pounds of any substance on earth could create more than X amount of energy. That X would be way insufficient to, for example, blow up a whole battleship. The proof would have been “correct”. Except that it was wrong. In those days nuclear energy was unknown. So would that “proof” had been correct?

  6. Gil Kalai says:

    Dear Dick, thanks for the comment.

    Chemistry, that largley grew out from the attempts to turn iron into gold, described the principles for why this is impossible (at least in the context that this was raised) to the extent that once these principles were understood the question of turning iron into gold lost its interest.

    The consistency of mathematics and the reasons for why the “foundational crisis” was eased and why Godel’s result is of no impact on practicing mathematics is discussed in this post. (Two different views are mentioned.)

    A follow up post to this one on amazing possiblities gives several examples for why indeed one must be very careful with impossibility claims.

  7. Pingback: Amazing Possibilities « Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s