| Part of a series on | ||
| Mathematics | ||
|---|---|---|
| ||
 Mathematics Portal | ||
Inmathematics, animpossibility theorem is atheorem that demonstrates a problem or general set of problems cannot be solved. These are also known asproofs of impossibility,negative proofs, ornegative results. Impossibility theorems often resolve decades or centuries of work spent looking for a solution by proving thereis no solution. Proving that something is impossible is usually much harder than the opposite task, as it is often necessary to develop a proof that works in general, rather than to just show a particular example.[1] Impossibilitytheorems are usually expressible as negative existential propositions oruniversal propositions in logic.
Theirrationality of the square root of 2 is one of the oldest proofs of impossibility. It shows that it is impossible to express the square root of 2 as aratio of twointegers. Another consequential proof of impossibility wasFerdinand von Lindemann's proof in 1882, which showed that the problem ofsquaring the circle cannot be solved[2] because the numberπ istranscendental (i.e., non-algebraic), and that only a subset of thealgebraic numbers can be constructed bycompass and straightedge. Two other classical problems—trisecting the general angle anddoubling the cube—were also proved impossible in the 19th century, and all of these problems gave rise to research into more complicated mathematical structures.
Some of the most important proofs of impossibility found in the 20th century were those related toundecidability, which showed that there are problems that cannot be solved in general by anyalgorithm, with one of the more prominent ones being thehalting problem.Gödel's incompleteness theorems were other examples that uncovered fundamental limitations in the provability of formal systems.[3]
Incomputational complexity theory, techniques like relativization (the addition of anoracle) allow for "weak" proofs of impossibility, in that proofs techniques that are not affected by relativization cannot resolve theP versus NP problem.[4] Another technique is the proof ofcompleteness for acomplexity class, which provides evidence for the difficulty of problems by showing them to be just as hard to solve as any other problem in the class. In particular, a complete problem isintractable if one of the problems in its class is.
One of the widely used types of impossibility proof isproof by contradiction. In this type of proof, it is shown that if a proposition, such as a solution to a particular class of equations, is assumed to hold, then via deduction two mutually contradictory things can be shown to hold, such as a number being both even and odd or both negative and positive. Since the contradiction stems from the original assumption, this means that the assumed premise must be impossible.
In contrast, a non-constructive proof of an impossibility claim would proceed by showing it is logically contradictory forall possible counterexamples to be invalid: at leastone 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 rationalwas disproved, by showing that one of two possible counterexamples must be a valid counterexample, without showing which one it is.
Another type of proof by contradiction is proof by descent, which proceeds first by assuming that something is possible, such as apositive integer[5] solution to a class of equations, and that therefore there must be a smallest solution (by theWell-ordering principle). 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.
The obvious way to disprove an impossibility conjecture is by providing a singlecounterexample. For example,Euler proposed that at leastn differentnth powers were necessary to sum to yet anothernth power. The conjecture was disproved in 1966, with a counterexample involving a count of only four different 5th powers summing to another fifth power:
Proof by counterexample is a form ofconstructive proof, in that an object disproving the claim is exhibited.
Insocial choice theory,Arrow's impossibility theorem shows that it is impossible to devise aranked-choice voting system that is bothnon-dictatorial and satisfies a basic requirement forrational behavior calledindependence of irrelevant alternatives.
Gibbard's theorem shows that anystrategyproofgame form (i.e. one with adominant strategy) with more than two outcomes isdictatorial.
TheGibbard–Satterthwaite theorem is a special case showing that no deterministic voting system can be fully invulnerable tostrategic voting in all circumstances, regardless of how others vote.
Therevelation principle can be seen as an impossibility theorem showing the "opposite" of Gibbard's theorem, in a colloquial sense: anygame or voting system can bemade resistant to strategy by incorporating the strategy into themechanism. Thus, it is impossible to design amechanism with a solution that is better than can be obtained by atruthful mechanism.
The proof byPythagoras about 500 BCE has had a profound effect on mathematics. It shows that thesquare root of 2 cannot be expressed as the ratio of two integers. The proof bifurcated "the numbers" into two non-overlapping collections—therational numbers and theirrational numbers.
There is a famous passage inPlato'sTheaetetus in which it is stated thatTheodorus (Plato's teacher) proved the irrationality of
taking all the separate cases up to the root of 17 square feet ... .[6]
A more general proof shows that themth root of an integerN is irrational, unlessN is themth power of an integern.[7] That is, it is impossible to express themth root of an integerN as the ratioa⁄b of two integersa andb, that share no commonprime factor, except in cases in whichb = 1.
Greek geometry was based on the use of thecompass and a straightedge (though the straightedge is not strictly necessary). The compass allows a geometer to construct points equidistant from each other, which inEuclidean space are equivalent to implicitly calculations ofsquare roots. Four famous questions asked how to construct:
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 mathematically impossible without admitting additional tools other than a compass.[8]
All of these are problems inEuclidean construction, and Euclidean constructions can be done only if they involve onlyEuclidean numbers (by definition of the latter).[9] Irrational numbers can be Euclidean. A good example is the square root of 2 (an irrational number). 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 a straightedge and a 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.
Bothtrisecting the general angle anddoubling the cube require takingcube roots, which are notconstructible numbers.
is not aEuclidean number ... and therefore it is impossible to construct, by Euclidean methods a length equal to the circumference of a circle of unit diameter
Because was proved in 1882 to be atranscendental number, it is not a Euclidean number; Hence the construction of a length from a unit circle is impossible.[10][11]
TheGauss-Wantzel theorem showed in 1837 that constructing an equilateraln-gon is impossible for most values ofn.
Theparallel postulate from Euclid'sElements is equivalent tothe statement that given a straight line and a point not on that line, only one parallel to the line may be drawn through that point. Unlike the other postulates, it was seen as less self-evident. Nagel and Newman argue that this may be because the postulate concerns "infinitely remote" regions of space; in particular, parallel lines are defined as not meeting even "at infinity", in contrast toasymptotes.[12] This perceived lack of self-evidence led to the question of whether it might be proven from the other Euclidean axioms and postulates. It was only in the nineteenth century that the impossibility of deducing the parallel postulate from the others was demonstrated in the works ofGauss,Bolyai,Lobachevsky, andRiemann. These works showed that the parallel postulate can moreover be replaced by alternatives, leading tonon-Euclidean geometries.
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".[12] In particular, they consider its outcome to be "of the greatest intellectual importance," as it showed that "aproof can be given of theimpossibility of proving certain propositions [in this case, the parallel postulate] within a given system [in this case, Euclid's first four postulates]."[13]
Fermat's Last Theorem was conjectured byPierre de Fermat in the 1600s, states the impossibility of finding solutions in positive integers for the equation with.Fermat himself gave a proof for then = 4 case using his technique ofinfinite descent, and other special cases were subsequently proved, but the general case was not proven until 1994 byAndrew Wiles.
The question "Does any arbitrary Diophantine equation have an integer solution?" isundecidable. That is, it is impossible to answer the question for all cases.
Franzén introducesHilbert's tenth problem and theMRDP theorem (Matiyasevich-Robinson-Davis-Putnam theorem) which states that "no algorithm exists which can decide whether or not a Diophantine equation hasany 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".[14]
This profound paradox presented byJules Richard in 1905 informed the work ofKurt Gödel[15] and Alan Turing. A succinct definition is found inPrincipia Mathematica:[16]
Richard's paradox ... is as follows. Consider all decimals that can be defined by means of afinite number ofwords[“words” are symbols; boldface added for emphasis]; letE be the class of such decimals. ThenE has[an infinite number of] terms; hence its members can be ordered as the 1st, 2nd, 3rd, ... LetX be a number defined as follows[Whitehead & Russell now employ the Cantor diagonal method].
If then-th figure in then-th decimal isp, let then-th figure inX bep + 1 (or 0, ifp = 9). ThenX is different from all the members ofE, since, whatever finite valuen may have, then-th figure inX is different from then-th figure in then-th of the decimals composingE, and thereforeX is different from then-th decimal. Nevertheless we have definedX in a finite number of words[i.e. this very definition of “word” above.] and thereforeX ought to be a member ofE. ThusX both is and is not a member of E.— Principia Mathematica, 2nd edition 1927, p. 61
Kurt Gödel considered his proof to be “an analogy” of Richard's paradox, which he called "Richard's antinomy"[17] (seebelow).
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).
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". 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).
Gödel proved, in his own words:
Gödel compared his proof to "Richard's antinomy" (an "antinomy" is a contradiction or a paradox; for more seeRichard's paradox):
A number of similar undecidability proofs appeared soon before and after Turing'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 aTuring machine viewpoint. Chaitin has written a number of books about his endeavors and the subsequent philosophic and mathematical fallout from them.
A string iscalled(algorithmically) random if it cannot be produced from any shorter computer program. Whilemost 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!"[22]
Innatural science, impossibility theorems are derived as mathematical results proven within well-establishedscientific theories. 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 inphysics areperpetual motion machines, which violate the law ofconservation of energy, and exceeding thespeed of light, which violates the implications ofspecial relativity. Another is theuncertainty principle ofquantum mechanics, which asserts the impossibility of simultaneously knowing both the position and the momentum of a particle. There is alsoBell'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 singlecounterexample. Such a counterexample would require that the assumptions underlying the theory that implied the impossibility be re-examined.
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems (list) and paradoxes | |||||||||
| Logics |
| ||||||||
| Set theory |
| ||||||||
| Formal systems (list), language and syntax |
| ||||||||
| Proof theory | |||||||||
| Model theory | |||||||||
| Computability theory | |||||||||
| Related | |||||||||