Impredicativity
In mathematics and logic, impredicativity is the property of a self-referencing definition. More precisely, a definition is said to be impredicative if it invokes (mentions or quantifies over) the set being defined, or (more commonly) another set which contains the thing being defined.
Russell's paradox is a famous example of an impredicative construction, namely the set of all sets which do not contain themselves. The paradox is whether such a set contains itself or not — if it does then by definition it should not, and if it does not then by definition it should.
The vicious circle principle was suggested by Henri Poincaré and Bertrand Russell in the wake of the paradoxes as a requirement on legitimate set specifications. Sets which do not meet the requirement are called impredicative.
The rejection of impredicatively defined mathematical objects (while accepting the natural numbers as classically understood) leads to the position in the philosophy of mathematics known as predicativism, advocated by Henri Poincaré and Hermann Weyl in his Das Kontinuum. Poincaré and Weyl argued that impredicative definitions are problematic only when one or more underlying sets are infinite.
Ramsey argued that "impredicative" definitions can be harmless: for instance, the definition of "Tallest person in the room" is impredicative, since it depends on a set of things of which it is an element, namely the set of all persons in the room. Concerning mathematics, an example of an impredicative definition is the smallest number in a set, which is formally defined as: y = min(X) if and only if for all elements x of X, y is less than or equal to x, and y is in X.
The greatest lower bound of a set X, glb(X), generalizes this concept; y = glb(X) if and only if for all elements x of X, y is less than or equal to x, and any z less than or equal to all elements of X is less than or equal to y. But this definition also quantifies over the set (potentially infinite, depending on the order in question) whose members are the lower bounds of X, one of which being the glb itself. Hence predicativism would reject this definition.
Burgess (2005) discusses predicative and impredicative theories at some length, in the context of Frege's logic, Peano arithmetic, second order arithmetic, and axiomatic set theory.
References
- John Burgess, 2005. Fixing Frege. Princeton Univ. Press.
- Solomon Feferman, 2005, "Predicativity" in The Oxford Handbook of Philosophy of Mathematics and Logic. Oxford University Press: 590–624.
- Stephen C. Kleene 1952 (1971 edition), Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam NY, ISBN 0 7204 2103 9. In particular cf his §11 The Paradoxes (pp. 36–40) and §12 First inferences from the paradoxes IMPREDICATIVE DEFINITON (p. 42). He states that his 6 or so (famous) examples of paradoxes (antinomies) are all examples of impredicative definition, and says that Poincaré (1905*ndash;6, 1908) and Russel (1906, 1910) "enunciated the cause of the paradoxes to lie in these impredicative definitions" (p. 42), however, "parts of mathematics we want to retain, particularly analysis, also contain impredicative definitions." (ibid). Weyl in his 1918 ("Das Kontinuum") attempted to derive as much of analysis as was possible without the use of impredicative definitions, "but not the theorem that an arbitrary non-empty set M of real numbers having an upper bound has a least upper bound (CF. also Weyl 1919)" (p. 43).
- Hans Reichenbach 1947, Elements of Symbolic Logic, Dover Publications, Inc., NY, ISBN 0-486-24004-5. Cf his §40. The antinomies and the theory of types (pp. 218 — wherein he demonstrates how to create antinomies, including the definition of impredicable itself ("Is the definition of "impredicable" impredicable?"). He claims to show methods for eliminating the "paradoxes of syntax" ("logical paradoxes") — by use of the theory of types — and "the paradoxes of semantics" — by the use of metalanguage (his "theory of levels of language"). He attributes the suggestion of this notion to Russell and more concretely to Ramsey.