Impredicativity

From Wikipedia, the free encyclopedia

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 another set, one of whose subsets is 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 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 showed that "impredicative" definitions over finite sets cannot be avoided. For instance, the definition of "Tallest person in the room" is impredicative, since it depends on a set of things of which it is a subset, 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 infinite set 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.

[edit] References

• Burgess, John, 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.