Unsolvability

The impossibility of solving a given problem exactly by prescribed means. Below the most important examples of unsolvability in mathematics are considered.

Algorithmic unsolvability. In various domains of mathematics there arise problems in which it is required to find a single mathematical procedure (an algorithm) by means of which one would be able to solve any problem from a given infinite class of problems of equal type. These are called decidability problems. An example is Hilbert's 10th problem, which requires the construction of an algorithm that would allow one to recognize whether any given polynomial with integer coefficients has integer values of the variables that make the polynomial vanish. Many decidability problems did not yield a solution for a long time: subsequently it turned out that the difficulty of solving them is of fundamental nature. This could be established only after in the 1930's in mathematical logic the concept of an algorithm was worked out accurately, and for some decidability problems it was proved that the required algorithm does not exist. Such decidability problems are called unsolvable or algorithmically unsolvable. Many other algorithmic problems from various branches of mathematics turned out to be unsolvable; in particular, Hilbert's 10th problem (see also Algorithmic problem).

Once the algorithmic unsolvability of a given decidability problem has been established, the solution of every concrete problem in the class in question requires its own specific method, so that there is no uniform method for solving all these problems.

Undecidable propositions. One of the tools for constructing a mathematical theory is the axiomatic method. In the axiomatic construction of a theory, a number of its propositions are taken as initial, as axioms, and the others are obtained as consequences of them. In works by D. Hilbert and his school the concept of an axiomatic theory was made more precise as a formal system. Hilbert's planned program of founding mathematics stipulated, in particular, the formalization of the basic branches of mathematics: arithmetic, analysis, set theory, that is, the construction of a formal system from the axioms of which one could deduce practically all mathematical theorems. However, in 1931 K. Gödel proved that every formal system of arithmetic is incomplete in the sense that one can state a proposition that cannot be proved nor disproved (i.e. prove its negation) within the system. Such propositions are called undecidable or formally undecidable in the given system. In particular, for every consistent formal system containing a sufficiently rich part of arithmetic the assertion that this system is consistent turns out to be undecidable in it (see Gödel incompleteness theorem).

The undecidability of a proposition in a given formal system indicates that it is impossible to verify its truth or falsity on the basis of only those ideas about the object of study that can be expressed in terms of the axioms and derivation rules. Often it proves possible to extend the formal system by new axioms such that certain specific undecidable propositions can be proved or disproved in the extended system. The discovery of undecidable propositions in an axiomatic theory has had an important significance for the development of this theory in that it stimulates the search for new fundamental statements that could be added as axioms.

Examples of unsolvability in elementary mathematics are geometric construction problems such as the trisection of an angle and the quadrature of the circle by means of ruler and compasses.

References

[1]	D. Hilbert, P. Bernays, "Grundlagen der Mathematik" , 1–2 , Springer (1968–1970)

Comments

Many of the issues raised in the main article above are discussed in greater detail and depth in Undecidability; in particular, how to establish unsolvability, the border line between solvability and unsolvability, as well as the existence of undecidable propositions independently of the axiomatization.