Impredicativity

In mathematics and logic, a self-referencing definition is called impredicative. 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.

The opposite of impredicativity is predicativity, which essentially entails building stratified (or ramified) theories where quantification over lower levels results in variables of some new type, distinguished from the lower types that the variable ranges over. A prototypical example is intuitionistic type theory, which retains ramification but discards impredicativity.

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 greatest lower bound of a set X, glb(X), also has an impredicative definition: 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.[1]

History

Solomon Feferman provides a historical review of predicativity, connecting it to current outstanding research problems.[2]

The vicious circle principle was suggested by Henri Poincaré (1905-6, 1908)[3] 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 first modern paradox appeared with Cesare Burali-Forti's 1897 A question on transfinite numbers[4] and would become known as the Burali-Forti paradox. Cantor had apparently discovered the same paradox in his (Cantor's) "naive" set theory and this become known as Cantor's paradox. Russell's awareness of the problem originated in June 1901[5] with his reading of Frege's treatise of mathematical logic, his 1879 Begriffsschrift; the offending sentence in Frege is the following:

On the other hand, it may be also be that the argument is determinate and the function indeterminate.[6]

In other words, given f(a) the function f is the variable and a is the invariant part. So why not substitute the value f(a) for f itself? Russell promptly wrote Frege a letter pointing out that:

You state ... that a function too, can act as the indeterminate element. This I formerly believed, but now this view seems doubtful to me because of the following contradiction. Let w be the predicate: to be a predicate that cannot be predicated of itself. Can w be predicated of itself? From each answer its opposite follows. There we must conclude that w is not a predicate. Likewise there is no class (as a totality) of those classes which each taken as a totality, do not belong to themselves. From this I conclude that under certain circumstances a definable collection does not form a totality.[7]

Frege promptly wrote back to Russell acknowledging the problem:

Your discovery of the contradiction caused me the greatest surprise and, I would almost say, consternation, since it has shaken the basis on which I intended to build arithmetic.[8]

While the problem had adverse personal consequences for both men (both had works at the printers that had to be emended), van Heijenoort observes that "The paradox shook the logicians' world, and the rumbles are still felt today. ... Russell's paradox, which makes use of the bare notions of set and element, falls squarely in the field of logic. The paradox was first published by Russell in The principles of mathematics (1903) and is discussed there in great detail ...".[9] Russell, after six years of false starts, would eventually answer the matter with his 1908 theory of types by "propounding his axiom of reducibility. It says that any function is coextensive with what he calls a predicative function: a function in which the types of apparent variables run no higher than the types of the arguments".[10] But this "axiom" was met with resistance from all quarters.

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.

Ernst Zermelo in his 1908 "A new proof of the possibility of a well-ordering" presents an entire section "b. Objection concerning nonpredicative definition" where he argued against "Poincaré (1906, p. 307) [who states that] a definition is 'predicative' and logically admissible only if it excludes all objects that are dependent upon the notion defined, that is, that can in any way be determined by it".[11] He gives two examples of impredicative definitions – (i) the notion of Dedekind chains and (ii) "in analysis wherever the maximum or minimum of a previously defined "completed" set of numbers Z is used for further inferences. This happens, for example, in the well-known Cauchy proof of the fundamental theorem of algebra, and up to now it has not occurred to anyone to regard this as something illogical".[12] He ends his section with the following observation: "A definition may very well rely upon notions that are equivalent to the one being defined; indeed, in every definition definiens and definiendum are equivalent notions, and the strict observance of Poincaré's demand would make every definition, hence all of science, impossible".[13]

Zermelo's example of minimum and maximum of a previously defined "completed" set of numbers reappears in Kleene 1952:42-42 where Kleene uses the example of Least upper bound in his discussion of impredicative definitions; Kleene does not resolve this problem. In the next paragraphs he discusses Weyl's attempt in his 1918 Das Kontinuum (The Continuum) to eliminate impredicative definitions and his failure to retain 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)".[14]

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.

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.

See also

Notes

  1. ↑ Kleene 1952:42-43
  2. ↑ Solomon Feferman, "Predicativity" (2002)
  3. ↑ dates derived from Kleene 1952:42
  4. ↑ van Heijenoort's commentary before Burali-Forti's (1897) A question on transfinite numbers in van Heijenoort 1967:104; see also his commentary before Georg Cantor's (1899) Letter to Dedekind in van Heijenoort 1967:113
  5. ↑ Commentary by van Heijenoort before Bertrand Russell's Lettern to Frege in van Heijenoort 1967:124
  6. ↑ Gottlob Frege (1879) Begriffsschrift in van Heijenoort 1967:23
  7. ↑ Bertrand Russell's 1902 Letter to Frege in van Heijenoort 1967:124-125
  8. ↑ Gottlob Frege's (1902) Letter to Russell in van Hiejenoort 1967:127
  9. ↑ Van Heijenoort's commentary before Bertrand Russell's (1902) Letter to Frege 1967:124
  10. ↑ Willard V. Quine's commentary before Bertrand Russell's 1908 Mathematical logic as based on the theory of types
  11. ↑ van Heijenoort 1967:190
  12. ↑ van Heijenoort 1967:190-191
  13. ↑ van Heijenoort 1967:191
  14. ↑ Kleene 1952:43

References

This article is issued from Wikipedia - version of the 10/2/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.