In
mathematics, a proof of impossibility is a
proof that 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. Such a case is also known as a negative proof, proof of an impossibility theorem, or negative result. Because they show that something cannot be done, proofs of impossibility can be the resolutions to decades or centuries of work attempting to find a 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. Impossibility
theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of t ...
s 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
In mathematics, a ratio shows how many times one number contains another. For example, if there are eight oranges and six lemons in a bowl of fruit, then the ratio of oranges to lemons is eight to six (that is, 8:6, which is equivalent to the ...
of two
integers
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
. Another consequential proof of impossibility was the 1882 proof by
Ferdinand von Lindemann
Carl Louis Ferdinand von Lindemann (12 April 1852 – 6 March 1939) was a German mathematician, noted for his proof, published in 1882, that (pi) is a transcendental number, meaning it is not a root of any polynomial with rational coefficien ...
, which showed that the problem of
squaring the circle cannot be solved because the number is
transcendental (i.e., non-algebraic), and that only a subset of the
algebraic numbers
An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the po ...
can be constructed by
compass and straightedge. Two other classical problems—
trisecting the general angle and
doubling the cube
Doubling the cube, also known as the Delian problem, is an ancient geometric problem. Given the edge of a cube, the problem requires the construction of the edge of a second cube whose volume is double that of the first. As with the related probl ...
—were also proved impossible in the 19th century, and all of these problems gave rise to research into more complicated mathematical structures.
A problem that arose in the 16th century was that of creating a general formula using radicals expressing the solution of any
polynomial equation
In mathematics, an algebraic equation or polynomial equation is an equation of the form
:P = 0
where ''P'' is a polynomial with coefficients in some field (mathematics), field, often the field of the rational numbers. For many authors, the term '' ...
of fixed
degree ''k'', where ''k'' ≥ 5. In the 1820s, the
Abel–Ruffini theorem
In mathematics, the Abel–Ruffini theorem (also known as Abel's impossibility theorem) states that there is no solution in radicals to general polynomial equations of degree five or higher with arbitrary coefficients. Here, ''general'' means th ...
(also known as ''Abel's impossibility theorem'') showed this to be impossible, using concepts such as
solvable group
In mathematics, more specifically in the field of group theory, a solvable group or soluble group is a group that can be constructed from abelian groups using extensions. Equivalently, a solvable group is a group whose derived series terminate ...
s from
Galois theory
In mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems in field theory to ...
—a new subfield of
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathematics), fields, module (mathe ...
.
Among 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
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
, with the most famous one being the
halting problem
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. Alan Turing proved in 1936 that a ...
.
Gödel's incompleteness theorems were other examples that uncovered fundamental limitations in the provability of formal systems.
In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, 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
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used above ...
. Another technique is the proof of
completeness for a
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...
, 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.
Types of proof
By contradiction
One widely used type of impossibility proof is
proof by contradiction
In logic and mathematics, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Proof by contradiction is also known ...
. 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. Since the contradiction stems from the original assumption, this means that the assumed premise must be impossible.
By descent
One type of proof by contradiction is proof by descent, which proceeds first by assuming that something is possible, such as a
positive integer solution to a class of equations, and that therefore there must be a smallest solution (by the
Well-ordering principle
In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which x precedes y i ...
). 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.
Types of disproof
There are two alternative methods of disproving a conjecture that something is impossible: by
counterexample
A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "John Smith is not a lazy student" is a ...
(
constructive proof
In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof (also known as an existenc ...
) and by logical contradiction (
non-constructive proof).
The obvious way to disprove an impossibility conjecture is by providing a single counterexample. For example,
Euler proposed that at least ''n'' different ''n''
th powers were necessary to sum to yet another ''n''
th power. The conjecture was disproved in 1966, with a counterexample involving a count of only four different 5th powers summing to another fifth power:
:27
5 + 84
5 + 110
5 + 133
5 = 144
5.
Proof by counterexample is a
constructive proof
In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof (also known as an existenc ...
, in that an object disproving the claim is exhibited. 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.
Pythagorean proof of the existence of irrational numbers
The proof by
Pythagoras
Pythagoras of Samos ( grc, Πυθαγόρας ὁ Σάμιος, Pythagóras ho Sámios, Pythagoras the Samian, or simply ; in Ionian Greek; ) was an ancient Ionian Greek philosopher and the eponymous founder of Pythagoreanism. His politi ...
(or more likely one of his students) about 500
BCE
Common Era (CE) and Before the Common Era (BCE) are year notations for the Gregorian calendar (and its predecessor, the Julian calendar), the world's most widely used calendar era. Common Era and Before the Common Era are alternatives to the or ...
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
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
and the
irrational numbers
In mathematics, the irrational numbers (from in- prefix assimilated to ir- (negative prefix, privative) + rational) are all the real numbers that are not rational numbers. That is, irrational numbers cannot be expressed as the ratio of two inte ...
. This bifurcation was used by
Cantor
A cantor or chanter is a person who leads people in singing or sometimes in prayer. In formal Jewish worship, a cantor is a person who sings solo verses or passages to which the choir or congregation responds.
In Judaism, a cantor sings and lead ...
in his
diagonal method
The diagonal method (DM) is a rule of thumb in photography, painting and drawing. Dutch photographer and lecturer Edwin Westhoff discovered the method when, after having long taught the rule of thirds in photography courses, he conducted visual e ...
, which in turn was used by Turing in his proof that the ''
Entscheidungsproblem
In mathematics and computer science, the ' (, ) 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 state ...
'', the
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
of
Hilbert
David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician, one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many ...
, is undecidable.
Proofs followed for various square roots of the primes up to 17.
There is a famous passage in Plato
Plato ( ; grc-gre, Πλάτων ; 428/427 or 424/423 – 348/347 BC) was a Greek philosopher born in Athens during the Classical period in Ancient Greece. He founded the Platonist school of thought and the Academy, the first institution ...
'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 ... .
A more general proof now exists that:
:The ''m''th root of an integer ''N'' is irrational, unless ''N'' is the ''m''th power of an integer ''n''".
That is, it is impossible to express the ''m''th root of an integer ''N'' as the ratio of two integers ''a'' and ''b'', that share no common
prime factor except in cases in which ''b'' = 1.
Impossible constructions sought by the ancient Greeks
Three famous questions of
Greek geometry were how:
# to
trisect any angle using
a compass and a straightedge,
# to construct a cube with a volume
twice the volume of a given cube,
# to construct a square
equal in area to that of a given circle.
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 logically impossible.
[Nagel and Newman p. 8]
A fourth problem of the ancient Greeks was to construct an
equilateral polygon
In geometry, an equilateral polygon is a polygon which has all sides of the same length. Except in the triangle case, an equilateral polygon does not need to also be equiangular (have all angles equal), but if it does then it is a regular polygon ...
with a specified number ''n'' of sides, beyond the basic cases ''n'' = 3, 4, 5, 6 that they knew how to construct.
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). 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.
Angle trisection and doubling the cube
Both
trisecting the general angle and
doubling the cube
Doubling the cube, also known as the Delian problem, is an ancient geometric problem. Given the edge of a cube, the problem requires the construction of the edge of a second cube whose volume is double that of the first. As with the related probl ...
require taking
cube roots, which are not
constructible numbers
In geometry and algebra, a real number r is constructible if and only if, given a line segment of unit length, a line segment of length , r, can be constructed with compass and straightedge in a finite number of steps. Equivalently, r is con ...
by compass and straightedge.
Squaring the circle
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
A proof exists to demonstrate that any Euclidean number is an
algebraic number—a number that is the solution to some
polynomial equation
In mathematics, an algebraic equation or polynomial equation is an equation of the form
:P = 0
where ''P'' is a polynomial with coefficients in some field (mathematics), field, often the field of the rational numbers. For many authors, the term '' ...
. Therefore, because
was proved in 1882 to be a
transcendental number
In mathematics, a transcendental number is a number that is not algebraic—that is, not the root of a non-zero polynomial of finite degree with rational coefficients. The best known transcendental numbers are and .
Though only a few classes ...
and thus by definition not an algebraic number, it is not a Euclidean number. Hence the construction of a length
from a unit circle is impossible, and the circle cannot be squared.
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''.
Euclid's parallel postulate
The
parallel postulate
In geometry, the parallel postulate, also called Euclid's fifth postulate because it is the fifth postulate in Euclid's ''Elements'', is a distinctive axiom in Euclidean geometry. It states that, in two-dimensional geometry:
''If a line segmen ...
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.
[Nagel and Newman, p. 9] 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
Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
,
Bolyai,
Lobachevsky
Nikolai Ivanovich Lobachevsky ( rus, Никола́й Ива́нович Лобаче́вский, p=nʲikɐˈlaj ɪˈvanəvʲɪtɕ ləbɐˈtɕɛfskʲɪj, a=Ru-Nikolai_Ivanovich_Lobachevsky.ogg; – ) was a Russian mathematician and geometer, kn ...
, and
Riemann
Georg Friedrich Bernhard Riemann (; 17 September 1826 – 20 July 1866) was a German mathematician who made contributions to analysis, number theory, and differential geometry. In the field of real analysis, he is mostly known for the first rig ...
. These works showed that the parallel postulate can moreover be replaced by alternatives, leading to
non-Euclidean geometries
In mathematics, non-Euclidean geometry consists of two geometries based on axioms closely related to those that specify Euclidean geometry. As Euclidean geometry lies at the intersection of metric geometry and affine geometry, non-Euclidean ge ...
.
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".
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
n this case, the parallel postulatewithin a given system
n this case, Euclid's first four postulates"
Fermat's Last Theorem
Fermat's Last Theorem
In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers , , and satisfy the equation for any integer value of greater than 2. The cases and have been ...
was conjectured by
Pierre de Fermat
Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he ...
in the 1600s, states the impossibility of finding solutions in positive integers for the equation
with
.
Fermat
Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he is ...
himself gave a proof for the ''n'' = 4 case using his technique of
infinite descent In mathematics, a proof by infinite descent, also known as Fermat's method of descent, is a particular kind of proof by contradiction used to show that a statement cannot possibly hold for any number, by showing that if the statement were to hold f ...
, and other special cases were subsequently proved, but the general case was not proven until 1994 by
Andrew Wiles
Sir Andrew John Wiles (born 11 April 1953) is an English mathematician and a Royal Society Research Professor at the University of Oxford, specializing in number theory. He is best known for proving Fermat's Last Theorem, for which he was awa ...
.
Richard's paradox
This profound paradox presented by
Jules Richard in 1905 informed the work of
Kurt Gödel and Alan Turing. A succinct definition is found in ''
Principia Mathematica
The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. ...
'':
Kurt Gödel considered his proof to be “an analogy” of Richard's paradox, which he called “''Richard's antinomy''”
[Gödel in ''Undecidable'', p. 9] .
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical co ...
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
In computer programming, an infinite loop (or endless loop) is a sequence of instructions that, as written, will continue endlessly, unless an external intervention occurs ("pull the plug"). It may be intentional.
Overview
This differs from:
* ...
’ (i.e. it fails to continue its computation of the diagonal number).
Incompleteness of axiomatic systems: Gödel's proof
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 that most readers see Nagel and Newman first.
Gödel proved, in his own words:
: "It is reasonable... to make the conjecture that ...
heaxioms [from
Principia Mathematica
The ''Principia Mathematica'' (often abbreviated ''PM'') is a three-volume work on the foundations of mathematics written by mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. ...
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
In logic, Richard's paradox is a semantical antinomy of set theory and natural language first described by the French mathematician Jules Richard in 1905. The paradox is ordinarily used to motivate the importance of distinguishing carefully betwee ...
):
: "The analogy of this result with Richard's antinomy is immediately evident; there is also a close relationship
4with the
Liar Paradox
In philosophy and logic, the classical liar paradox or liar's paradox or antinomy of the liar is the statement of a liar that they are lying: for instance, declaring that "I am lying". If the liar is indeed lying, then the liar is telling the truth ...
(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
5 (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)".
Halting problem: Turing's first proof
* The ''
Entscheidungsproblem
In mathematics and computer science, the ' (, ) 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 state ...
'', the
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
, 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.
* Turing's proof is made difficult by number of definitions required and its subtle nature. See
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
and
Turing's proof
Turing's proof is a proof by Alan Turing, first published in January 1937 with the title "On Computable Numbers, with an Application to the ". It was the second proof (after Church's theorem) of the negation of Hilbert's ; that is, the conjecture ...
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
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer scien ...
("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
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the ''Entscheidungsproblem'' it is often used in proofs of undecidability.
Definiti ...
(cf Hopcroft and Ullman
p. 193ff, p. 407 for the reference)
# April 1947: Proof of
Emil Post
Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.
Life
Post was born in Augustów, Suwałki Gove ...
(''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
Axel Thue (; 19 February 1863 – 7 March 1922) was a Norwegian mathematician, known for his original work in diophantine approximation and combinatorics.
Work
Thue published his first important paper in 1909.
He stated in 1914 the so-calle ...
proposed this problem in a paper of 1914 (cf References to Post's paper in Undecidable, p. 303)).
#
Rice's theorem
In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a synta ...
: a generalized formulation of Turing's second theorem (cf Hopcroft and Ullman
p. 185ff)
#
Greibach's theorem In theoretical computer science, in particular in formal language theory, Greibach's theorem states that certain properties of formal language classes are undecidable. It is named after the computer scientist Sheila Greibach, who first proved it in ...
: undecidability in language theory (cf Hopcroft and Ullman
p. 205ff and reference on p. 401 ibid:
Greibach 963
Year 963 ( CMLXIII) was a common year starting on Thursday (link will display the full calendar) of the Julian calendar.
Events
By place
Byzantine Empire
* March 15 – Emperor Romanos II dies at age 25, probably of poison admini ...
"The undecidability of the ambiguity problem for minimal lineal grammars," ''Information and Control'' 6:2, 117–125, also reference on p. 402 ibid: Greibach
968
Year 968 ( CMLXVIII) was a leap year starting on Wednesday (link will display the full calendar) of the Julian calendar.
Events
By place Byzantine Empire
* Emperor Nikephoros II receives a Bulgarian embassy led by Prince Boris (th ...
"A note on undecidable properties of formal languages", Math Systems Theory 2:1, 1–6.)
#
Penrose tiling
A Penrose tiling is an example of an aperiodic tiling. Here, a ''tiling'' is a covering of the plane by non-overlapping polygons or other shapes, and ''aperiodic'' means that shifting any tiling with these shapes by any finite distance, without ...
questions
# Question of solutions for
Diophantine equations
In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
and the resultant answer in the MRDP Theorem; see entry below.
String compressibility: Chaitin'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
Gregory John Chaitin ( ; born 25 June 1947) is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-t ...
's so-called "halting probability". Davis's older treatment approaches the question from a
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
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..."
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!".
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
Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm which, for any given Diophantine equation (a polynomial equa ...
and the
MRDP theorem
In mathematics, a Diophantine equation is an equation of the form ''P''(''x''1, ..., ''x'j'', ''y''1, ..., ''y'k'') = 0 (usually abbreviated ''P''(', ') = 0) where ''P''(', ') is a polynomial with integer coefficients, where ''x''1, ..., '' ...
(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".
[Franzén p.71]
In social science
In
political science
Political science is the scientific study of politics. It is a social science dealing with systems of governance and power, and the analysis of political activities, political thought, political behavior, and associated constitutions and la ...
,
Arrow's impossibility theorem
Arrow's impossibility theorem, the general possibility theorem or Arrow's paradox is an impossibility theorem in social choice theory that states that when voters have three or more distinct alternatives (options), no ranked voting electoral syst ...
states that it is impossible to devise a
voting system
An electoral system or voting system is a set of rules that determine how elections and referendums are conducted and how their results are determined. Electoral systems are used in politics to elect governments, while non-political elections m ...
that satisfies a set of five specific axioms. This theorem is proved by showing that four of the axioms together imply the opposite of the fifth.
In
economics
Economics () is the social science that studies the production, distribution, and consumption of goods and services.
Economics focuses on the behaviour and interactions of economic agents and how economies work. Microeconomics analyzes ...
,
Holmström's theorem is an impossibility theorem proving that no incentive system for a team of agents can satisfy all of three desirable criteria.
In natural science
In
natural science, impossibility assertions (like other assertions) come to be widely accepted as overwhelmingly probable rather than considered proved to the point of being unchallengeable. 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
Physics is the natural science that studies matter, its fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge which r ...
are
perpetual motion machine
Perpetual motion is the motion of bodies that continues forever in an unperturbed system. A perpetual motion machine is a hypothetical machine that can do work infinitely without an external energy source. This kind of machine is impossible, a ...
s, which violate the law of
conservation of energy, and exceeding the
speed of light
The speed of light in vacuum, commonly denoted , is a universal physical constant that is important in many areas of physics. The speed of light is exactly equal to ). According to the special theory of relativity, is the upper limit ...
, which violates the implications of
special relativity
In physics, the special theory of relativity, or special relativity for short, is a scientific theory regarding the relationship between space and time. In Albert Einstein's original treatment, the theory is based on two postulates:
# The laws ...
. Another is the
uncertainty principle
In quantum mechanics, the uncertainty principle (also known as Heisenberg's uncertainty principle) is any of a variety of mathematical inequalities asserting a fundamental limit to the accuracy with which the values for certain pairs of physic ...
of
quantum mechanics
Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistr ...
, 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
A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "John Smith is not a lazy student" is a ...
. 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
Many mathematical problems have been stated but not yet solved. These problems come from many areas of mathematics, such as theoretical physics, computer science, algebra, analysis, combinatorics, algebraic, differential, discrete and Eucli ...
Solutions of these problems are still being searched for. In contrast, the above problems are ''known'' to have no solution.
*
Notes and references
Bibliography
*
G. H. Hardy
Godfrey Harold Hardy (7 February 1877 – 1 December 1947) was an English mathematician, known for his achievements in number theory and mathematical analysis. In biology, he is known for the Hardy–Weinberg principle, a basic principle of pop ...
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
Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ...
, ''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.
* (and )
online versionThis is the epochal paper where Turing defines
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
s and shows that it (as well as the
Entscheidungsproblem
In mathematics and computer science, the ' (, ) 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 state ...
) 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
A Post–Turing machineRajendra Kumar, ''Theory of Automata'', Tata McGraw-Hill Education, 2010, p. 343. is a "program formulation" of a type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation. Post's mode ...
, then proceeds onward with descriptions of Turing's first proof and Chaitin's contributions.
*
Andrew Hodges
Andrew Philip Hodges (; born 1949) is a British mathematician, author and emeritus senior research fellow at Wadham College, Oxford.
Education
Hodges was born in London in 1949 and educated at Birkbeck, University of London where he was award ...
, ''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 Lo''gic, Dover Publications Inc., New York, 1947. A reference often cited by other authors.
*
Ernest Nagel
Ernest Nagel (November 16, 1901 – September 20, 1985) was an American philosopher of science. Suppes, Patrick (1999)Biographical memoir of Ernest Nagel In '' American National Biograph''y (Vol. 16, pp. 216-218). New York: Oxford University Pr ...
and
James Newman''Gödel's Proof'' New York University Press, 1958.
*
Edward Beltrami
Edward is an English given name. It is derived from the Anglo-Saxon name ''Ēadweard'', composed of the elements '' ēad'' "wealth, fortune; prosperous" and '' weard'' "guardian, protector”.
History
The name Edward was very popular in Anglo-Sax ...
, ''What is Random? Chance and Order in Mathematics and Life'', Springer-Verlag New York, Inc., 1999.
*
Torkel Franzén
Torkel Franzén (1 April 1950, Norrbotten County – 19 April 2006, Stockholm) was a Swedish academic.
Biography
Franzén worked at the Department of Computer Science and Electrical Engineering at Luleå University of Technology, Sweden, in the f ...
, ''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".)
{{DEFAULTSORT:Proof Of Impossibility
Mathematical logic
Mathematical proofs
Methods of proof
Possibility