Lesson 6

In continuous mathematics, there are also many proofs that can be classified as non-constructive.

Theorem (Bolzano — Cauchy, 1821). If a function continuous on a segment takes values of different signs at the ends of this segment, then at some point within the segment it equals zero.

The Bolzano — Cauchy theorem is somewhat similar to the pigeonhole principle: it provides certain conditions under which the desired object (a hole with more than one pigeon or a point where the function equals zero) must exist. These two statements are non-constructive because they do not specify which object has the desired property.

Theorem (Borsuk — Ulam, 1933). For any continuous mapping of an \(n\)-dimensional sphere into \(n\)-dimensional Euclidean space, there exist two diametrically opposite points on the sphere that have the same value.

From this theorem, the following (discrete!) result can be derived.

Theorem. Let \(G\) be an undirected graph on \(3n\) vertices, which is the union of a Hamiltonian cycle and \(n\) disjoint triangles. Then, \(G\) has an independent set of size \(n\).

In 1888, Hilbert proved that there exist nonnegative polynomials (with real coefficients) that cannot be represented as a sum of squares of polynomials. The first explicit example of such a polynomial was constructed by Theodor Motzkin only in 1967: \[P(x,y)=1+x^{4}y^{2}+x^{2}y^{4}-3x^{2}y^{2}.\] In 1900, David Hilbert formulated a list of twenty-three open problems, the seventeenth of which asked: can any nonnegative polynomial be represented as a sum of squares of rational functions? A positive non-constructive answer to this question was given by Emil Artin in 1927, and a constructive one by Charles Delzell in 1984.