Proofs of impossibility

kenewbie

Amateur question ahead, be warned.

I really dislike proofs that something cannot be done. My first gripe is that they limit the areas we are "allowed to think about", so to speak. But more importantly, I have this feeling that any proof of impossibility is unavoidably flawed because it cannot account for any openings which may be found in systems other than we are using today.

As a theoretical example, an ancient greek could could easily prove that there are no solutions to x^2 = -1. However today we can easily give solution to that in the complex numbers. Although we are working in a different system, we have meaningful answers to what was proved impossible.

The emphasis on meaningful answer is important. Although we did not technically break the greeks proof, we sort of rewrote the rules, and was able to use what the greek said was impossible to do meaningful calculations, which can help find solutions to problems.

The fallacy of our hypothetical greek was of course that he did not specify that he was talking about real solutions. But that is sort if my point. They had no concept of imaginary numbers yet, so every number was real.

Which is the exact position that anyone today is in, when they prove that something is impossible. Although they can trivially avoid the exact problem the greek had by specifying a domain, who knows in what directions our system of mathematics will expand in the future.

Is it not presumptuous to assume that we can disprove anything for anything other than the system which we currently have? Since this system is constantly evolving, any proof of impossibility would be valid only for a finite time, until the system changes, and as such it is not a proof at all.

"Positive" proofs, on the other hand, does not have this limitation. If you prove that something is possible, you helping expanding the current system. Assuming there is no fundamental axiomatic failure in math or in your positive proof itself, it cannot be undone by future expansions of the system.

So, is there really any meaning to a proof that squaring the circle is impossible? It may be impossible with any system we currently have, but who knows what tomorrow might bring.

Are there good examples of proofs of impossibility that was commonly accepted and then found to be wrong?

Did I stumble off into crackpot-land here?

k

TheOogy

To my opinion, you are correct.

CRGreathouse

I'm going to take a strong contrary position.

I love impossibility proofs. For me, they map out the contours of what can and cannot be done, and this is useful.

Let's take the example of the square root of -1. Why create a new system with it, except because it couldn't otherwise be done? It was the impossibility of finding a square root of -1 that led to the complex numbers -- it didn't prevent their finding.

For a rather different example, consider Arrow's (1951) theorem: there are no monotonic voting system that respect independence of irrelevant alternatives* and are not restricted (anyone can vote for any candidate), imposed (more than one candidate can win, say if they get all votes), or dictatorial (one voter makes all the decisions).**

So if you want to design a voting rule that meets all those conditions, you know that it can't fall under Arrow's definition of a voting system. Alternately, if you want to make an Arrovian voting system, you know that you need to break at least one of these criteria (most violate IIA).

* If A would win an election, but then B joins in the race, either A or B will win -- B's entry won't case C to win.
** There have been literally hundreds of published improvements to this theorem; see Arrow 1963, Wilson 1972, Pattanaik & Peleg 1986, Tanaka 2003, etc.

AUMathTutor

Proofs always make reference to certain basic assumptions. Clearly, if you change the assumptions, perhaps some things which were impossible before will become possible (and maybe things that were possible become impossible).

Impossibility proofs are useful because they make people sit down and think of how to change the assumptions so that everything else remains possible and the impossible becomes possible, i.e. the complex numbers, irrational numbers, etc.

CRGreathouse

Like trisecting an angle, it's impossible with a compass and an unmarked straightedge. But how is that bad? It is because the problem is known to be impossible with compass and straightedge that interested people can focus on finding a system that can do it, rather than follow Hippocrates' attempts to do it only with those tools. (He *was* able to square a lune with just compass and straightedge, so the quest didn't seem hopeless.)

For problems like doubling the cube and trisecting angles, other tools have been found that allow this: linkages and origami, for example. But again, I think the impossibility proofs focused effort rather than making mathematicians give up.

robert Ihnot

One trouble with trisecting an angle is the common attitude I encountered about it. When I went to school a girl told me, she had been told in high school it was an impossible construction so she spent three years attempting to find one. In fact, many students took an interest in this problem in high school after hearing it was "impossible."

The trouble here is that using a straight edge and compass is a very restrictive way to approach the problem, and I don't think most of the individuals, and that includes the high school teachers, actually understood that a ruler is not the same as a straight edge, since they normally used a ruler for a straight edge anyway! So they did not understand there is a difference between placing a mark on a straight edge and having no mark on it.

If one uses, as Heinrich Dorrie tells us, "100 Great Problems of Elementary Mathematics," a paper strip that we can place a mark on, it is perfectly possible to trisect an angle. In fact, Archimedes is credited with this solution.

This would seem to be at least as important as "It is impossible to trisect an angle," but, as I say most of the individuals involved in this in high school had no idea what the restrictions were. Again, because of this, many students devoted large amounts of time to finding a solution--or where there is smoke--they suspected there might be real fire!

As for doubling the cube as an alter, well that could be easily obtained by weighing the amount of material going into the cube--or at least it seems so to me. So that this was probably never any kind of problem the Greeks had to worry about.

CRGreathouse

I take it you're not familiar with the backstory?

Methods for doubling a cube were known around the time of the question's original posing, and not even resorting to approximate methods. But because of the sacral nature of the issue at hand, it was decided that a 'pure' solution (that is, compass and straightedge only) was needed.

robert Ihnot

I take it you're not familiar with the backstory?

Not entirely. I take it as a literal request. It is one thing to use a geometric method on an angle. But, if the actual problem was to double a cube used as an alter, how do you expect to do this by extending the sides by an irrational number? That may interest the mathematician, but the builder might see it differently.

kenewbie

I see what you are saying, I just look at it slightly different I guess. I don't believe it was any proof that it could not be done which lead to the complex numbers, it was right there in their faces and they just worked until they found a way around it.

A better example might be Gödel's incompleteness theorems. As far as I know they pretty much put a stop to all work on proving arithmetic consistent (Hilbert's second problem). I just feel like Gödel is in no position to know what the future brings. Perhaps it is possible to do a slight redefinition of arithmetic and suddenly it can be done. If this is true, then he is still technically correct (he was talking about a different arithmetic) but he useless.

As for the circle squaring example; Proving that pi is transcendental is awesome, but I would leave it at that. I don't see the value in going further and claiming that squaring is impossible.

Ok, that sounds true. There are only so many was you can assure "independence of irrelevant alternatives", and I guess all of them are listed. I assume voting is defined so that a system where are the votes are discarded fall outside the definition, otherwise such a system seems to disagree with the theorem; it is monotonic, iia, not restricted, imposed or dictatorial.

Anyway, as much as I might agree with what he is saying, I'm not sure i see the value of making a theorem of it. Suffice to say that "under so and so conditions, I don't see how this can be done". Maybe that is how most people read proof and that is where my trouble is.

k

kenewbie

Aye, that is pretty clear. The thing is that since our assumptions about mathematics are ever changing, a proof of impossibility is only valid under the assumptions which it is given, and as such is not really valid at all.

A positive proof on the other hand, becomes part of the system and as such carries over into the new assumptions (we throw away any brewing new assumptions that disagree with the old ones, we only keep the ones that are complementary).

k

CRGreathouse

I think my "proof" is your "in their faces". They knew it couldn't be done, so they invented a way around.

Inventing a way around for something you can already do (say, finding a square root of 0) is less common: how often do you see the dual numbers compared to the complex numbers? Both are logical extensions of the reals; both can be defined by simple algebraic manipulations and axioms or by 2x2 matrices.

I certainly don't agree here. If you want to prove the consistency (in some sense) of arithmetic (in some sense), you really need to understand Gödel's theorem. For example, if you want to prove consistency in exactly Gödel's sense, you need to prove it from a system that is either weak (in the sense of being unable to model Peano arithmetic) or one that cannot model your system.

If you want to prove a system to be consistent from itself, you either need to use a different meaning of consistent than Gödel's or you need to use a weak system.

There's a five-lane highway with exits on the left and right. You see the roadblock and complain that Gödel blocked the road -- I see the flashing "left" and "right" arrows as preventing us from going down the dead end he charted!

You would have just ignored that problem, then? Or, like the Pythagoreans (so the story goes, though about root(2) rather than pi), covered it up?

No, such a system is imposed. (A technical consideration which I omitted is that random results are not allowed. If you're actually interested, the Pattanaik & Peleg 1986 paper I mentioned above generalized Arrow's theorem to cover the case where randomness is allowed.)

I very much agree with your last statement. The real problem, in my view, is that some people misinterpret impossibility theorems. This is especially harmful in the case of Arrow's theorem, where the usual gloss is "no good voting system is possible". What a terrible conclusion to draw! Arrow himself is largely to blame for that one.

CRGreathouse

Not really valid at all? The conditions are the whole point! Consider these rewritings of Arrow's theorem:

• Any voting system that respects IIA and is not restricted, imposed, or dictatorial is nonmonotonic.
• Any monotone voting system that is not restricted, imposed, or dictatorial is not independent of irrelevant alternatives.
• Any monotone voting system that respects IIA and is not imposed, or dictatorial is restricted.
• Any monotone voting system that respects IIA and is not restricted or dictatorial is imposed.
• Any monotone voting system that respects IIA and is not restricted or imposed is dictatorial.

The assumptions become the conclusions.

Dragonfall

But we know that the hypothetical greek meant the real numbers. His proof is not any less valid because we have the new concept of complex numbers. [tex]\sqrt{-1}[/tex] is no more of a real number today than it was 2000 years ago

Similarly, any proof of impossibility done today will still be valid, even if we can come up with new concepts under which whatever we proved to be impossible becomes possible.

kenewbie

Yeah, I'm coming around to your point of view. I've just been looking at this whole thing with a preconception that does not really reflect reality.

k

CRGreathouse

I'll try to pull you all the way over with more examples.

Abel's theorem says there's no solution in addition, subtraction, multiplication, division, and radicals to fifth or higher degree equations in general. This theorem led to the development of Galois theory. A general solution for fifth-degree equations has been found, but no effort was wasted trying to make one with just radicals: hypergeometrics (or Bring radicals, etc.) are needed.

The Modigliani-Miller theorem says that it is impossible to change the value of a company by issuing debt instead of selling stock (or vice-versa) if taxes, transaction costs, and bankruptcy costs are zero and the market is efficient (no asymmetric information, etc). Companies clearly care about which they offer (there are even stockholder lawsuits over this sort of thing!), so any change in value can be traced to a violation of one of the conditions. All other things are necessarily irrelevant! What as powerful theorem.

arildno

Hi, ken!

I see you are coming around, but I'd like to give you an analogy:

In games, some rules are arbitrarily chosen, but are held as valid WITHIN that game.

In poker, for example, we have chosen that a legitimate hand shall have 5, and only 5, cards (at least in the poker variants I'm familiar with!)

Now, suppose we make the following query:
"Is 3 aces and 3 kings" a possible poker hand?

Now, we may PROVE that this is impossible, since it violates the 5-card limit a hand has been decreed to have!

In precisely the same manner, impossibility proofs in maths elucidates how the proposed conjecture violates one of more of the arbitrarily chosen axioms in the math variant we are playing at the moment.

In no way does this entail that we cannot play other types of math games, or that those other math games can't be useful.



Secondly:
It is not due to mysticism that the Greeks required of geometry that only a unmarked straight-edge (and compass) should be used.

Rather, it is crucial to have this requirement if you want to prove, for example, that it is possible to CONSTRUCT a MARKED straight-edge (under the lesser assumption, of course, that straight-edges do exist..)

JungleJesus

I guess I'm walking into a firestorm of a discussion, so I won't take up too much of your time. The way I see it is quite simple. Think of everything we know about mathematics today as its own separate universe. Any proof that coincides with the laws of this universe (be it a proof of possibility or impossibility) is valid because it makes sense compared to all of the established knowledge. If new knowledge is discovered, the proof in question may not hold true given the new conditions, but that doesn't make the proof any less correct because the proof was established in a time when those new conditions didn't exist. If anything, the proof in question would merely have to be updated with some fancy language to preserve its functional domain.

As it has already been stated, we know that i² = -1 has no real solutions. The hypothetical Greeks had no need to explain what a real solution is because all numbers were real for them. However, today we must update and refine theorems established in the past so that they fit into our ever-changing world. These proofs are by no means useless and are not a waste of time to develop.