1 Answers
In mathematics, a proof of impossibility is a proof which demonstrates that a particular problem cannot be solved as described in the claim, or that a particular set of problems cannot be solved in general. They are also known as negative proof, proof of an impossibility theorem, or negative result. Proofs of impossibility often put to rest decades or centuries of work attempting to find a solution. 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.
The irrationality of 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 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 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 that arose 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 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. Gödel's incompleteness theorems are other examples, which uncover some fundamental limitations in the provability of formal systems.