Impredicativity


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 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 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 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, " [http://math.stanford.edu/~feferman/papers/predicativity.pdf 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-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.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Impredicativity — Imprédicativité L imprédicativité est un terme du domaine des mathématiques, de la logique, de la théorie des ensembles et de la théorie des types. Sommaire 1 Définitions 2 Bibliographie 3 Voir aussi …   Wikipédia en Français

  • Logicism — is one of the schools of thought in the philosophy of mathematics, putting forth the theory that mathematics is an extension of logic and therefore some or all mathematics is reducible to logic.[1] Bertrand Russell and Alfred North Whitehead… …   Wikipedia

  • Edmund Husserl — Infobox Philosopher region = Western Philosophy era = 20th century philosophy color = #B0C4DE image caption = Edmund Husserl name = Edmund Gustav Albrecht Husserl birth = April 8, 1859 (Prostějov, Moravia) | death = death date and… …   Wikipedia

  • Self-reference — The Treachery Of Images (1928 29) by René Magritte depicts a pipe along with text stating This is not a pipe. Note: This image is an illustration of a self reference case only if the demonstrative pronoun ceci ( this ) refers not to the idea of a …   Wikipedia

  • New Foundations — In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled New Foundations for …   Wikipedia

  • Predicative — may mean:* Predicative (adjectival or nominal) * Predicative (verb) * Lacking impredicativity …   Wikipedia

  • List of mathematics articles (I) — NOTOC Ia IA automorphism ICER Icosagon Icosahedral 120 cell Icosahedral prism Icosahedral symmetry Icosahedron Icosian Calculus Icosian game Icosidodecadodecahedron Icosidodecahedron Icositetrachoric honeycomb Icositruncated dodecadodecahedron… …   Wikipedia

  • Constructive set theory — is an approach to mathematical constructivism following the program of axiomatic set theory. That is, it uses the usual first order language of classical set theory, and although of course the logic is constructive, there is no explicit use of… …   Wikipedia

  • Alexander George — ist ein US amerikanischer Philosoph mit Forschungsschwerpunkten vor allem in der Philosophie der Mathematik und Sprachphilosophie. Außerdem ist er Schachkomponist. Inhaltsverzeichnis 1 Philosophie 2 Schachkomposition 3 Werke (Auswahl) …   Deutsch Wikipedia

  • Imprédicativité — L imprédicativité est un terme du domaine des mathématiques, de la logique, de la théorie des ensembles et de la théorie des types. Sommaire 1 Définitions 2 Aspect calculatoire de l imprédicativité 3 Bibliographie …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.