Proof of impossibility
In mathematics, an impossibility theorem is a theorem that demonstrates a problem or general set of problems cannot be solved. These are also known as proofs of impossibility, negative proofs, or negative results. Impossibility theorems often resolve decades or centuries of work spent looking for a solution by proving there is 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] Impossibility theorems are usually expressible as negative existential propositions or universal propositions in logic.
The irrationality 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 a ratio of two integers. Another consequential proof of impossibility was Ferdinand von Lindemann's proof in 1882, which showed that the problem of squaring the circle cannot be solved[2] because the number π is transcendental (i.e., non-algebraic), and that 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, 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 to undecidability, which showed that there are problems that cannot be solved in general by any algorithm, with one of the more prominent ones being the halting problem. Gödel's incompleteness theorems were other examples that uncovered fundamental limitations in the provability of formal systems.[3]
In computational complexity theory, techniques like relativization (the addition of an oracle) allow for "weak" proofs of impossibility, in that proofs techniques that are not affected by relativization cannot resolve the P versus NP problem.[4] Another technique is the proof of completeness for a complexity 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 is intractable if one of the problems in its class is.
Economics[edit]
Arrow's theorem: Rational ranked-choice voting[edit]
In social choice theory, Arrow's impossibility theorem shows that it is impossible to devise a ranked-choice voting system that is both non-dictatorial and satisfies a basic requirement for rational behavior called independence of irrelevant alternatives.
Gibbard's theorem: Non-dictatorial strategyproof games[edit]
Gibbard's theorem shows that any strategyproof game form (i.e. one with a dominant strategy) with more than two outcomes is dictatorial.
The Gibbard–Satterthwaite theorem is a special case showing that no deterministic voting system can be fully invulnerable to strategic voting in all circumstances, regardless of how others vote.
Revelation principle: Non-honest solutions[edit]
The revelation principle can be seen as an impossibility theorem showing the "opposite" of Gibbard's theorem, in a colloquial sense: any game or voting system can be made resistant to strategy by incorporating the strategy into the mechanism. Thus, it is impossible to design a mechanism with a solution that is better than can be obtained by a truthful mechanism.
Geometry[edit]
Expressing mth roots rationally[edit]
The proof by Pythagoras 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. The proof bifurcated "the numbers" into two non-overlapping collections—the rational numbers and the irrational numbers.