foundations of mathematics Impredicative constructions

A number of 19th-century mathematicians found fault with the program of reducing mathematics to arithmetic and set theory as suggested by the work of Cantor and Frege. In particular, the French mathematician Henri Poincaré (1854–1912) objected to impredicative constructions, which construct an entity of a certain type in terms of entities of the same or higher type—i.e., self-referencing constructions and definitions. For example, when proving that every bounded nonempty set X of real numbers has a least upper bound a, one proceeds as follows. (For this purpose, it will be convenient to think of a real number, following Dedekind, as a set of rationals that contains all the rationals less than any element of the set.) One lets x ∊ a if and only if x ∊ y for some y ∊ X; but here y is of the same type as a.

It would seem that to do ordinary analysis one requires impredicative constructions. Russell and Whitehead tried unsuccessfully to base mathematics on a predicative type theory; but, though reluctant, they had to introduce an additional axiom, the axiom of reducibility, which rendered their enterprise impredicative after all. More recently, the Swedish logician Per Martin-Löf presented a new predicative type theory, but no one claims that this is adequate for all of classical analysis. However, the German-American mathematician Hermann Weyl (1885–1955) and the American mathematician Solomon Feferman have shown that impredicative arguments such as the above can often be circumvented and are not needed for most, if not all, of analysis. On the other hand, as was pointed out by the Italian computer scientist Giuseppe Longo (b. 1929), impredicative constructions are extremely useful in computer science—namely, for producing fixpoints (entities that remain unchanged under a given process).