Proof of impossibility

A proof of impossibility, also known as negative proof, proof of an impossibility theorem, or negative result, is a proof demonstrating that a particular problem cannot be solved as described in the claim, or that a particular set of problems cannot be solved in general. Proofs of impossibility often put decades or centuries of work attempting to find a solution to rest. To prove that something is impossible is usually much harder than the opposite task; as it is often necessary to develop a theory. Impossibility theorems are usually expressible as negative existential propositions, or universal propositions in logic (see universal quantification for more).
Perhaps one of the oldest proofs of impossibility is that of the irrationality of square root of 2, which shows that it is impossible to express the square root of 2 as a ratio of integers. Another famous proof of impossibility was the 1882 proof of Ferdinand von Lindemann, showing that the ancient problem of squaring the circle cannot be solved, because the number is transcendental (i.e., non-algebraic) and only a subset of the algebraic numbers can be constructed by compass and straightedge. Two other classical problems—trisecting the general angle and doubling the cube—were also proved impossible in the 19th century.
A problem arising in the 16th century was that of creating a general formula using radicals expressing the solution of any polynomial equation of fixed degree "k", where "k" ≥ 5. In the 1820s, the Abel–Ruffini theorem (also known as Abel's impossibility theorem) showed this to be impossible, using concepts such as solvable groups from Galois theory—a new subfield of abstract algebra.
Among the most important proofs of impossibility of the 20th century were those related to undecidability, which showed that there are problems that cannot be solved in general by any algorithm at all, with the most famous one being the halting problem. Other similarly-related findings are those of the Gödel's incompleteness theorems, which uncovers some fundamental limitations in the provability of formal systems.
In computational complexity theory, techniques like relativization (see oracle machine) provide "weak" proofs of impossibility excluding certain proof techniques. Other techniques, such as proofs of completeness for a complexity class, provide evidence for the difficulty of problems, by showing them to be just as hard to solve as other known problems that have proved intractable.
Types of impossibility proof.
Proof by contradiction.
One widely used type of impossibility proof is proof by contradiction. In this type of proof, it is shown that if something, such as a solution to a particular class of equations, were possible, then two mutually contradictory things would be true, such as a number being both even and odd. The contradiction implies that the original premise is impossible.
Proof by descent.
One type of proof by contradiction is proof by descent, which proceeds first by assuming that something is possible, such as a positive integer solution to a class of equations, and that therefore there must be a smallest solution. From the alleged smallest solution, it is then shown that a smaller solution can be found, contradicting the premise that the former solution was the smallest one possible—thereby showing that the original premise (that a solution exists) must be false.
Types of disproof of impossibility conjectures.
There are two alternative methods of disproving a conjecture that something is impossible: by counterexample (constructive proof) and by logical contradiction (non-constructive proof).
The obvious way to disprove an impossibility conjecture by providing a single counterexample. For example, Euler proposed that at least "n" different "n"th powers were necessary to sum to yet another "n"th power. The conjecture was disproved in 1966, with a counterexample involving a count of only four different 5th powers summing to another fifth power:
A proof by counterexample is a constructive proof, in that an object disproving the claim is exhibited. In contrast, a non-constructive proof of an impossibility claim would proceed by showing it is logically contradictory for "all" possible counterexamples to be invalid: At least "one" of the items on a list of possible counterexamples must actually be a valid counterexample to the impossibility conjecture. For example, a conjecture that it is impossible for an irrational power raised to an irrational power to be rational was disproved, by showing that one of two possible counterexamples must be a valid counterexample, without showing which one it is.
The existence of irrational numbers: The Pythagoreans' proof.
The proof by Pythagoras (or more likely one of his students) about 500 BCE has had a profound effect on mathematics. It shows that the square root of 2 cannot be expressed as the ratio of two integers (counting numbers). The proof bifurcated "the numbers" into two non-overlapping collections—the rational numbers and the irrational numbers. This bifurcation was used by Cantor in his diagonal method, which in turn was used by Turing in his proof that the "Entscheidungsproblem", the decision problem of Hilbert, is undecidable.
Proofs followed for various square roots of the primes up to 17.
There is a famous passage in Plato's "Theaetetus" in which it is stated that Teodorus (Plato's teacher) proved the irrationality of
taking all the separate cases up to the root of 17 square feet ... .
A more general proof now exists that:
That is, it is impossible to express the "m"th root of an integer "N" as the ratio of two integers "a" and "b", that share no common prime factor except in cases in which "b" = 1.
Impossible constructions sought by the ancient Greeks.
Three famous questions of Greek geometry were how:
For more than 2,000 years unsuccessful attempts were made to solve these problems; at last, in the 19th century it was proved that the desired constructions are logically impossible.
A fourth problem of the ancient Greeks was to construct an equilateral polygon with a specified number "n" of sides, beyond the basic cases "n" = 3, 4, 5 that they knew how to construct.
All of these are problems in Euclidean construction, and Euclidean constructions can be done only if they involve only Euclidean numbers (by definition of the latter) (Hardy and Wright p. 159). Irrational numbers can be Euclidean. A good example is the irrational number the square root of 2. It is simply the length of the hypotenuse of a right triangle with legs both one unit in length, and it can be constructed with straightedge and compass. But it was proved centuries after Euclid that Euclidean numbers cannot involve any operations other than addition, subtraction, multiplication, division, and the extraction of square roots.
Angle trisection and doubling the cube.
Both trisecting the general angle and doubling the cube require taking cube roots, which are not constructible numbers by compass and straightedge.
Squaring the circle.
formula_2 is not a Euclidean number ... and therefore it is impossible to construct, by Euclidean methods a length equal to the circumference of a circle of unit diameter
A proof exists to demonstrate that any Euclidean number is an algebraic number—a number that is the solution to some polynomial equation. Therefore, because formula_2 was proved in 1882 to be a transcendental number and thus by definition not an algebraic number, it is not a Euclidean number. Hence the construction of a length formula_2 from a unit circle is impossible, and the circle cannot be squared.
Constructing an equilateral "n"-gon.
The Gauss-Wantzel theorem showed in 1837 that constructing an equilateral "n"-gon is impossible for most values of "n".
Euclid's parallel axiom.
Nagel and Newman consider the question raised by the parallel postulate to be "...perhaps the most significant development in its long-range effects upon subsequent mathematical history" (p. 9).
The question is: can the axiom that two parallel lines "...will not meet even 'at infinity'" (footnote, ibid) be derived from the other axioms of Euclid's geometry? It was not until work in the nineteenth century by "... Gauss, Bolyai, Lobachevsky, and Riemann, that the impossibility of deducing the parallel axiom from the others was demonstrated. This outcome was of the greatest intellectual importance. ...a "proof" can be given of the "impossibility of proving" certain propositions [in this case, the parallel postlate] within a given system [in this case, Euclid's first four postulates]". (p. 10)
Fermat's Last Theorem.
Fermat's Last Theorem was conjectured by Pierre de Fermat in the 1600s, states the impossibility of finding solutions in positive integers for the equation formula_5 with formula_6. Fermat himself gave a proof for the "n" = 4 case using his technique of infinite descent, and other special cases were subsequently proved, but the general case was not proved until 1994 by Andrew Wiles.
Richard's paradox.
This profound paradox presented by Jules Richard in 1905 informed the work of Kurt Gödel (cf Nagel and Newman p. 60ff) and Alan Turing. A succinct definition is found in "Principia Mathematica":
Kurt Gödel considered his proof to be “an analogy” of Richard's paradox, which he called “"Richard's antinomy"”. See more below about Gödel's proof.
Alan Turing constructed this paradox with a machine and proved that this machine could not answer a simple question: will this machine be able to determine if any machine (including itself) will become trapped in an unproductive ‘infinite loop’ (i.e. it fails to continue its computation of the diagonal number).
Can this theorem be proved from these axioms? Gödel's proof.
To quote Nagel and Newman (p. 68), "Gödel's paper is difficult. Forty-six preliminary definitions, together with several important preliminary theorems, must be mastered before the main results are reached" (p. 68). In fact, Nagel and Newman required a 67-page introduction to their exposition of the proof. But if the reader feels strong enough to tackle the paper, Martin Davis observes that "This remarkable paper is not only an intellectual landmark, but is written with a clarity and vigor that makes it a pleasure to read" (Davis in Undecidable, p. 4). It is recommended that most readers see Nagel and Newman first.
So what did Gödel prove? In his own words:
Gödel compared his proof to "Richard's antinomy" (an "antinomy" is a contradiction or a paradox; for more see Richard's paradox):
Will this computing machine lock in a "circle"? Turing's first proof.
A number of similar undecidability proofs appeared soon before and after Turing's proof:
Can this string be compressed? Chaitin's proof.
For an exposition suitable for non-specialists see Beltrami p. 108ff. Also see Franzen Chapter 8 pp. 137–148, and Davis pp. 263–266. Franzén's discussion is significantly more complicated than Beltrami's and delves into Ω—Gregory Chaitin's so-called "halting probability". Davis's older treatment approaches the question from a Turing machine viewpoint. Chaitin has written a number of books about his endeavors and the subsequent philosophic and mathematical fallout from them.
A string is called "(algorithmically) random" if it cannot be produced from any shorter computer program. While most strings are random, no particular one can be proved so, except for finitely many short ones:
Beltrami observes that "Chaitin's proof is related to a paradox posed by Oxford librarian G. Berry early in the twentieth century that asks for 'the smallest positive integer that cannot be defined by an English sentence with fewer than 1000 characters.' Evidently, the shortest definition of this number must have at least 1000 characters. However, the sentence within quotation marks, which is itself a definition of the alleged number is less than 1000 characters in length!" (Beltrami, p. 108)
Does this Diophantine equation have an integer solution? Hilbert's tenth problem.
The question "Does any arbitrary "Diophantine equation" have an integer solution?" is undecidable.That is, it is impossible to answer the question for all cases.
Franzén introduces Hilbert's tenth problem and the MRDP theorem (Matiyasevich-Robinson-Davis-Putnam theorem) which states that "no algorithm exists which can decide whether or not a Diophantine equation has "any" solution at all". MRDP uses the undecidability proof of Turing: "... the set of solvable Diophantine equations is an example of a computably enumerable but not decidable set, and the set of unsolvable Diophantine equations is not computably enumerable" (p. 71).
In social science.
In political science, Arrow's impossibility theorem states that it is impossible to devise a voting system that satisfies a set of five specific axioms. This theorem is proved by showing that four of the axioms together imply the opposite of the fifth.
In economics, Holmström's theorem is an impossibility theorem proving that no incentive system for a team of agents can satisfy all of three desirable criteria.
In natural science.
In natural science, impossibility assertions (like other assertions) come to be widely accepted as overwhelmingly probable rather than considered proved to the point of being unchallengeable. The basis for this strong acceptance is a combination of extensive evidence of something not occurring, combined with an underlying theory, very successful in making predictions, whose assumptions lead logically to the conclusion that something is impossible.
Two examples of widely accepted impossibilities in physics are perpetual motion machines, which violate the law of conservation of energy, and exceeding the speed of light, which violates the implications of special relativity. Another is the uncertainty principle of quantum mechanics, which asserts the impossibility of simultaneously knowing both the position and the momentum of a particle. Also Bell's theorem: no physical theory of local hidden variables can ever reproduce all of the predictions of quantum mechanics.
While an impossibility assertion in natural science can never be absolutely proved, it could be refuted by the observation of a single counterexample. Such a counterexample would require that the assumptions underlying the theory that implied the impossibility be re-examined.