Proof of impossibility
Part of a series on | ||
Mathematics | ||
---|---|---|
|
||
Mathematics Portal | ||
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
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
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
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
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
Geometry
Expressing mth roots rationally
The proof by
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.
Euclidean constructions
- a pair of lines trisecting a given angle;
- a cube with a volume twice the volume of a given cube;
- a square equal in area to that of a given circle;
- 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
Both
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
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 .
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
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 of words [“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] ( ).
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).
Gödel proved, in his own words:
- "It is reasonable... to make the conjecture that ...[the] axioms [from 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 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
- The Entscheidungsproblem, the decision problem, was first answered by Church in April 1935 and preceded Turing by over a year, as Turing's paper was received for publication in May 1936.[18]
- Turing's proof is made difficult by number of definitions required and its subtle nature. See Turing machine and Turing's proof for details.
- Turing's first proof (of three) follows the schema of Richard's paradox: Turing's computing machine is an algorithm represented by a string of seven letters in a "computing machine". Its "computation" is to test all computing machines (including itself) for "circles", and form a diagonal number from the computations of the non-circular or "successful" computing machines. It does this, starting in sequence from 1, by converting the numbers (base 8) into strings of seven letters to test. When it arrives at its own number, it creates its own letter-string. It decides it is the letter-string of a successful machine, but when it tries to do this machine's (its own) computation it locks in a circle and can't continue. Thus, we have arrived at Richard's paradox. (If you are bewildered see Turing's proof for more).
A number of similar undecidability proofs appeared soon before and after Turing's proof:
- 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))
- 1946: Post correspondence problem (cf Hopcroft and Ullman[19] p. 193ff, p. 407 for the reference)
- 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 Thueproposed this problem in a paper of 1914 (cf References to Post's paper in Undecidable, p. 303)).
- Rice's theorem: a generalized formulation of Turing's second theorem (cf Hopcroft and Ullman[19] p. 185ff)[20]
- 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.)
- 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
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
- List of unsolved problems in mathematics – Solutions of these problems are still being searched for. In contrast, the above problems are known to have no solution.
- Paradoxes of set theory
Notes and references
- ^ Pudlák, pp. 255–256.
- ^ Weisstein, Eric W. "Circle Squaring". mathworld.wolfram.com. Retrieved 2019-12-13.
- ^ 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
- doi:10.1137/0204037. Retrieved 2022-12-11.
- well-ordered set.
- ^ Hardy and Wright, p. 42
- ^ Hardy and Wright, p. 40
- ^ Nagel and Newman p. 8
- ^ Hardy and Wright p. 159
- ^ Hardy and Wright p. 176
- ^ Hardy and Wright p. 159 referenced by E. Hecke. (1923). Vorlesungen über die Theorie der algebraischen Zahlen. Leipzig: Akademische Verlagsgesellschaft
- ^ a b Nagel and Newman, p. 9
- ^ Nagel and Newman, p. 10
- ^ Franzén p.71
- OCLC 1057623639.
- ^ Principia Mathematica, 2nd edition 1927, p. 61, 64 in Principia Mathematica online, Vol.1 at University of Michigan Historical Math Collection
- ^ a b Gödel in Undecidable, p. 9
- ^ 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).
- ^ ISBN 0-201-02988-X.
- ^ "...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.
- ^ Beltrami p. 109
- ^ Beltrami, p. 108
Bibliography
- G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Clarendon Press, Oxford England, 1979, reprinted 2000 with General Index (first edition: 1938). The proofs that e and pi are transcendental are not trivial, but a mathematically adept reader will be able to wade through them.
- Alfred North Whitehead and Bertrand Russell, Principia Mathematica to *56, Cambridge at the University Press, 1962, reprint of 2nd edition 1927, first edition 1913. Chap. 2.I. "The Vicious-Circle Principle" p. 37ff, and Chap. 2.VIII. "The Contradictions" p. 60ff.
- Turing, A.M. (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2, vol. 42, no. 1 (published 1937), pp. 230–65, doi:10.1112/plms/s2-43.6.544). online version This is the epochal paper where Turing defines Turing machines and shows that it (as well as the Entscheidungsproblem) is unsolvable.
- Martin Davis, The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
- Martin Davis's chapter "What is a Computation" in Lynn Arthur Steen's Mathematics Today, 1978, Vintage Books Edition, New York, 1980. His chapter describes Turing machines in the terms of the simpler Post–Turing machine, then proceeds onward with descriptions of Turing's first proof and Chaitin's contributions.
- Andrew Hodges, Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
- Hans Reichenbach, Elements of Symbolic Logic, Dover Publications Inc., New York, 1947. A reference often cited by other authors.
- Ernest Nagel and James Newman, Gödel's Proof, New York University Press, 1958.
- Edward Beltrami, What is Random? Chance and Order in Mathematics and Life, Springer-Verlag New York, Inc., 1999.
- Torkel Franzén, Godel's Theorem, An Incomplete Guide to Its Use and Abuse, A.K. Peters, Wellesley Mass, 2005. A recent take on Gödel's Theorems and the abuses thereof. Not so simple a read as the author believes it is. Franzén's (blurry) discussion of Turing's 3rd proof is useful because of his attempts to clarify terminology. Offers discussions of Freeman Dyson's, Stephen Hawking's, Roger Penrose's and Gregory Chaitin's arguments (among others) that use Gödel's theorems, and useful criticism of some philosophic and metaphysical Gödel-inspired dreck that he's found on the web.
- Pavel Pudlák, Logical Foundations of Mathematics and Computational Complexity. A Gentle Introduction, Springer 2013. (See Chapter 4 "Proofs of impossibility".)