Proof of impossibility

Last updated

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.

Contents

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.

Proof techniques

Contradiction

One of the widely used types of impossibility proof is proof 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 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.

By descent

Another type of proof by contradiction is proof by descent, which proceeds first by assuming that something is possible, such as a positive integer [5] solution to a class of equations, and that therefore there must be a smallest solution (by the Well-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.

Counterexample

The obvious way to disprove an impossibility conjecture is by providing a single counterexample. For example, Euler proposed that at least n different nth powers were necessary to sum to yet another nth power. The conjecture was disproved in 1966, with a counterexample involving a count of only four different 5th powers summing to another fifth power:

275 + 845 + 1105 + 1335 = 1445.

Proof by counterexample is a form of constructive proof, in that an object disproving the claim is exhibited.

Economics

Arrow's theorem: Rational ranked-choice voting

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

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

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

Expressing mth roots rationally

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.

There is a famous passage in Plato's Theaetetus in which it is stated that Theodorus (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 the mth root of an integer N is irrational, unless N is the mth power of an integer n. [7] That is, it is impossible to express the mth root of an integer N as the ratio ab of two integers a and b, that share no common prime factor, except in cases in which b = 1.

Euclidean constructions

Greek geometry was based on the use of the compass and a straightedge (though the straightedge is not strictly necessary). The compass allows a geometer to construct points equidistant from each other, which in Euclidean space are equivalent to implicitly calculations of square roots. Four famous questions asked how to construct:

  1. a pair of lines trisecting a given angle;
  2. a cube with a volume twice the volume of a given cube;
  3. a square equal in area to that of a given circle;
  4. an equilateral polygon with an arbitrary number of sides.

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 in Euclidean construction, and Euclidean constructions can be done only if they involve only Euclidean 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.

Both trisecting the general angle and doubling the cube require taking cube roots, which are not constructible numbers.

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

Because was proved in 1882 to be a transcendental number, it is not a Euclidean number; Hence the construction of a length from a unit circle is impossible. [10] [11]

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.

Deducing Euclid's parallel postulate

The parallel postulate from Euclid's Elements is equivalent to the 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 to asymptotes. [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 of Gauss, Bolyai, Lobachevsky, and Riemann. These works showed that the parallel postulate can moreover be replaced by alternatives, leading to non-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 "a proof can be given of the impossibility of proving certain propositions [in this case, the parallel postulate] within a given system [in this case, Euclid's first four postulates]." [13]

Number theory

Impossibility of Fermat triples

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 with . 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 proven until 1994 by Andrew Wiles.

Integer solutions of Diophantine equations: 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". [14]

Decidability

Richard's paradox

This profound paradox presented by Jules Richard in 1905 informed the work of Kurt Gödel [15] and Alan Turing. A succinct definition is found in Principia Mathematica : [16]

Richard's paradox ... is as follows. Consider all decimals that can be defined by means of a finite number ofwords[“words” are symbols; boldface added for emphasis]; let E be the class of such decimals. Then E has [an infinite number of] terms; hence its members can be ordered as the 1st, 2nd, 3rd, ... Let X be a number defined as follows [Whitehead & Russell now employ the Cantor diagonal method].
If the n-th figure in the n-th decimal is p, let the n-th figure in X be p + 1 (or 0, if p = 9). Then X is different from all the members of E, since, whatever finite value n may have, the n-th figure in X is different from the n-th figure in the n-th of the decimals composing E, and therefore X is different from the n-th decimal. Nevertheless we have defined X in a finite number of words [i.e. this very definition of “word” above.] and therefore X ought to be a member of E. Thus X 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] (see below).

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).

Complete and consistent axiomatic system

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). It is recommended[ by whom? ] that most readers see Nagel and Newman first.

Gödel proved, in his own words:

"It is reasonable... to make the conjecture that ...[the] axioms [from Principia Mathematica and Peano] are ... sufficient to decide all mathematical questions which can be formally expressed in the given systems. In what follows it will be shown that this is not the case, but rather that ... there exist relatively simple problems of the theory of ordinary whole numbers which cannot be decided on the basis of the axioms" (Gödel in Undecidable, p. 4).

Gödel compared his proof to "Richard's antinomy" (an "antinomy" is a contradiction or a paradox; for more see Richard's paradox):

"The analogy of this result with Richard's antinomy is immediately evident; there is also a close relationship [14] with the Liar Paradox (Gödel's footnote 14: Every epistemological antinomy can be used for a similar proof of undecidability) ... Thus, we have a proposition before us which asserts its own unprovability [15]. (His footnote 15: Contrary to appearances, such a proposition is not circular, for, to begin with, it asserts the unprovability of a quite definite formula)". [17]

Proof of halting

A number of similar undecidability proofs appeared soon before and after Turing's proof:

  1. April 1935: Proof of Alonzo Church ("An Unsolvable Problem of Elementary Number Theory"). His proof was to "...propose a definition of effective calculability ... and to show, by means of an example, that not every problem of this class is solvable" (Undecidable p. 90))
  2. 1946: Post correspondence problem (cf Hopcroft and Ullman [19] p. 193ff, p. 407 for the reference)
  3. April 1947: Proof of Emil Post (Recursive Unsolvability of a Problem of Thue) (Undecidable p. 293). This has since become known as "The Word problem of Thue" or "Thue's Word Problem" (Axel Thue proposed this problem in a paper of 1914 (cf References to Post's paper in Undecidable, p. 303)).
  4. Rice's theorem: a generalized formulation of Turing's second theorem (cf Hopcroft and Ullman [19] p. 185ff) [20]
  5. Greibach's theorem: undecidability in language theory (cf Hopcroft and Ullman [19] p. 205ff and reference on p. 401 ibid: Greibach [1963] "The undecidability of the ambiguity problem for minimal lineal grammars," Information and Control 6:2, 117–125, also reference on p. 402 ibid: Greibach [1968] "A note on undecidable properties of formal languages", Math Systems Theory 2:1, 1–6.)
  6. Penrose tiling questions.

Information theory

Compression of random strings

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:

"A paraphrase of Chaitin's result is that there can be no formal proof that a sufficiently long string is random..." [21]

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]

Natural sciences

In natural science, impossibility theorems are derived as mathematical results proven within well-established scientific 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 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. There is 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.

See also

Notes and references

  1. Pudlák, pp. 255–256.
  2. Weisstein, Eric W. "Circle Squaring". mathworld.wolfram.com. Retrieved 2019-12-13.
  3. Raatikainen, Panu (2018), "Gödel's Incompleteness Theorems", in Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (Fall 2018 ed.), Metaphysics Research Lab, Stanford University, retrieved 2019-12-13
  4. Baker, Theodore; Gill, John; Solovay, Robert (1975). "Relativizations of the P=?NP Question" . SIAM Journal on Computing. 4 (4): 431–442. doi:10.1137/0204037 . Retrieved 2022-12-11.
  5. More generally, proof by infinite descent is applicable to any well-ordered set.
  6. Hardy and Wright, p. 42
  7. Hardy and Wright, p. 40
  8. Nagel and Newman p. 8
  9. Hardy and Wright p. 159
  10. Hardy and Wright p. 176
  11. Hardy and Wright p. 159 referenced by E. Hecke. (1923). Vorlesungen über die Theorie der algebraischen Zahlen. Leipzig: Akademische Verlagsgesellschaft
  12. 1 2 Nagel and Newman, p. 9
  13. Nagel and Newman, p. 10
  14. Franzén p.71
  15. Nagel, Ernest; Newman, James R. (1958). Gödel's proof. pp. 60 ff. ISBN   0-359-07926-1. OCLC   1057623639.
  16. Principia Mathematica, 2nd edition 1927, p. 61, 64 in Principia Mathematica online, Vol.1 at University of Michigan Historical Math Collection
  17. 1 2 Gödel in Undecidable, p. 9
  18. Also received for publication in 1936 (in October, later than Turing) was a short paper by Emil Post that discussed the reduction of an algorithm to a simple machine-like "method" very similar to Turing's computing machine model (see Post–Turing machine for details).
  19. 1 2 3 John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation . Addison-Wesley. ISBN   0-201-02988-X.
  20. "...there can be no machine E which ... will determine whether M [an arbitrary machine] ever prints a given symbol (0 say)" (Undecidable p. 134). Turing makes an odd assertion at the end of this proof that sounds remarkably like Rice's Theorem:
    "...each of these "general process" problems can be expressed as a problem concerning a general process for determining whether a given integer n has a property G(n)... and this is equivalent to computing a number whose nth figure is 1 if G(n) is true and 0 if it is false" (Undecidable p 134). Unfortunately he doesn't clarify the point further, and the reader is left confused.
  21. Beltrami p. 109
  22. Beltrami, p. 108

Bibliography

Related Research Articles

The Berry paradox is a self-referential paradox arising from an expression like "The smallest positive integer not definable in under sixty letters".

The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In the computer science subfield of algorithmic information theory, a Chaitin constant or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will halt. These numbers are formed from a construction due to Gregory Chaitin.

In mathematics and computer science, the Entscheidungsproblem is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. The problem asks for an algorithm that considers, as input, a statement and answers "yes" or "no" according to whether the statement is universally valid, i.e., valid in every structure.

Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics.

Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of provability in formal axiomatic theories. These results, published by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics. The theorems are widely, but not universally, interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all mathematics is impossible.

<span class="mw-page-title-main">Mathematical proof</span> Reasoning for mathematical statements

A mathematical proof is a deductive argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proof can, in principle, be constructed using only certain basic or original assumptions known as axioms, along with the accepted rules of inference. Proofs are examples of exhaustive deductive reasoning which establish logical certainty, to be distinguished from empirical arguments or non-exhaustive inductive reasoning which establish "reasonable expectation". Presenting many cases in which the statement holds is not enough for a proof, which must demonstrate that the statement is true in all possible cases. A proposition that has not been proved but is believed to be true is known as a conjecture, or a hypothesis if frequently used as an assumption for further mathematical work.

Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory.

Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theories concerning the nature of mathematics. In this latter sense, the distinction between foundations of mathematics and philosophy of mathematics turns out to be vague. Foundations of mathematics can be conceived as the study of the basic mathematical concepts and how they form hierarchies of more complex structures and concepts, especially the fundamentally important structures that form the language of mathematics also called metamathematical concepts, with an eye to the philosophical aspects and the unity of mathematics. The search for foundations of mathematics is a central question of the philosophy of mathematics; the abstract nature of mathematical objects presents special philosophical challenges.

<span class="mw-page-title-main">Metamathematics</span> Study of mathematics itself

Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories. Emphasis on metamathematics owes itself to David Hilbert's attempt to secure the foundations of mathematics in the early part of the 20th century. Metamathematics provides "a rigorous mathematical technique for investigating a great variety of foundation problems for mathematics and logic". An important feature of metamathematics is its emphasis on differentiating between reasoning from inside a system and from outside a system. An informal illustration of this is categorizing the proposition "2+2=4" as belonging to mathematics while categorizing the proposition "'2+2=4' is valid" as belonging to metamathematics.

In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was developed by Kurt Gödel for the proof of his incompleteness theorems.

<span class="mw-page-title-main">Fallibilism</span> Philosophical principle

Originally, fallibilism is the philosophical principle that propositions can be accepted even though they cannot be conclusively proven or justified, or that neither knowledge nor belief is certain. The term was coined in the late nineteenth century by the American philosopher Charles Sanders Peirce, as a response to foundationalism. Theorists, following Austrian-British philosopher Karl Popper, may also refer to fallibilism as the notion that knowledge might turn out to be false. Furthermore, fallibilism is said to imply corrigibilism, the principle that propositions are open to revision. Fallibilism is often juxtaposed with infallibilism.

Turing's proof is a proof by Alan Turing, first published in November 1936 with the title "On Computable Numbers, with an Application to the Entscheidungsproblem". It was the second proof of the negation of Hilbert's Entscheidungsproblem; that is, the conjecture that some purely mathematical yes–no questions can never be answered by computation; more technically, that some decision problems are "undecidable" in the sense that there is no single algorithm that infallibly gives a correct "yes" or "no" answer to each instance of the problem. In Turing's own words: "what I shall prove is quite different from the well-known results of Gödel ... I shall now show that there is no general method which tells whether a given formula U is provable in K [Principia Mathematica]".

Francisco Antônio de Moraes Accioli Dória is a Brazilian mathematician, philosopher, and genealogist. Francisco Antônio Dória received his B.S. in Chemical Engineering from the Federal University of Rio de Janeiro (UFRJ), Brazil, in 1968 and then got his doctorate from the Brazilian Center for Research in Physics (CBPF), advised by Leopoldo Nachbin in 1977. Dória worked for a while at the Physics Institute of UFRJ, and then left to become a Professor of the Foundations of Communications at the School of Communications, also at UFRJ. Dória held visiting positions at the University of Rochester (NY), Stanford University (CA), and the University of São Paulo (USP). His most prolific period spawned from his collaboration with Newton da Costa, a Brazilian logician and one of the founders of paraconsistent logic, which began in 1985. He is currently Professor of Communications, Emeritus, at UFRJ and a member of the Brazilian Academy of Philosophy.

The history of the Church–Turing thesis ("thesis") involves the history of the development of the study of the nature of functions whose values are effectively calculable; or, in more modern terms, functions whose values are algorithmically computable. It is an important topic in modern mathematical theory and computer science, particularly associated with the work of Alonzo Church and Alan Turing.

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.

<span class="mw-page-title-main">Brouwer–Hilbert controversy</span>

The Brouwer–Hilbert controversy was a debate in twentieth-century mathematics over fundamental questions about the consistency of axioms and the role of semantics and syntax in mathematics. L. E. J. Brouwer, a proponent of the constructivist school of intuitionism, opposed David Hilbert, a proponent of formalism. Much of the controversy took place while both were involved with Mathematische Annalen, the leading mathematical journal of the time, with Hilbert as editor-in-chief and Brouwer as a member of its editorial board. In 1920 Hilbert had Brouwer removed from the editorial board of Mathematische Annalen.

A timeline of mathematical logic; see also history of logic.

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs.