Impredicative
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 (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 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.
was suggested by Henri Poincaré
(1905-6, 1908) 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 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 with his reading of Frege's treatise of mathematical logic, his 1879 Begriffsschrift
; the offending sentence in Frege is the following:
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:
Frege promptly wrote back to Russell acknowledging the problem:
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...". Russell, after 6 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". But this "axiom" was met with resistance from all quarters.
The rejection of impredicatively defined mathematical objects (while accepting the natural number
s 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". 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". 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".
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.)"
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
, impredicativity is the property of a self-referencing definition
Definition
A definition is a passage that explains the meaning of a term , or a type of thing. The term to be defined is the definiendum. A term may have many different senses or meanings...
. 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
Russell's paradox
In the foundations of mathematics, Russell's paradox , discovered by Bertrand Russell in 1901, showed that the naive set theory created by Georg Cantor leads to a contradiction...
is a famous example of an impredicative construction, namely the set of all sets which do not contain themselves. The paradox
Paradox
Similar to Circular reasoning, A paradox is a seemingly true statement or group of statements that lead to a contradiction or a situation which seems to defy logic or intuition...
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.
History
The vicious circle principleVicious circle principle
The vicious circle principle is a principle that was endorsed by many predicativist mathematicians in the early 20th century to prevent contradictions. The principle states that no object or property may be introduced by a definition that depends on that object or property itself...
was suggested by Henri Poincaré
Henri Poincaré
Jules Henri Poincaré was a French mathematician, theoretical physicist, engineer, and a philosopher of science...
(1905-6, 1908) and Bertrand Russell
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
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
Cesare Burali-Forti
Cesare Burali-Forti was an Italian mathematician.He was born in Arezzo, and was an assistant of Giuseppe Peano in Turin from 1894 to 1896, during which time he discovered what came to be called the Burali-Forti paradox of Cantorian set theory. He died in Turin.-Books by C. Burali-Forti:* with R....
's 1897 A question on transfinite numbers and would become known as the Burali-Forti paradox
Burali-Forti paradox
In set theory, a field of mathematics, the Burali-Forti paradox demonstrates that naively constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction...
. Cantor had apparently discovered the same paradox in his (Cantor's) "naive" set theory and this become known as Cantor's paradox
Cantor's paradox
In set theory, Cantor's paradox is derivable from the theorem that there is no greatest cardinal number, so that the collection of "infinite sizes" is itself infinite...
. Russell's awareness of the problem originated in June 1901 with his reading of Frege's treatise of mathematical logic, his 1879 Begriffsschrift
Begriffsschrift
Begriffsschrift is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book...
; 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".
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".
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".
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...". Russell, after 6 years of false starts, would eventually answer the matter with his 1908 theory of types by "propounding his axiom of reducibility
Axiom of reducibility
The axiom of reducibility was introduced by Bertrand Russell as part of his ramified theory of types, an attempt to ground mathematics in first-order logic.- History: the problem of impredicativity :...
. 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". But this "axiom" was met with resistance from all quarters.
The rejection of impredicatively defined mathematical objects (while accepting the natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s as classically understood) leads to the position in the philosophy of mathematics
Philosophy of mathematics
The philosophy of mathematics is the branch of philosophy that studies the philosophical assumptions, foundations, and implications of mathematics. The aim of the philosophy of mathematics is to provide an account of the nature and methodology of mathematics and to understand the place of...
known as predicativism, advocated by Henri Poincaré
Henri Poincaré
Jules Henri Poincaré was a French mathematician, theoretical physicist, engineer, and a philosopher of science...
and Hermann Weyl
Hermann Weyl
Hermann Klaus Hugo Weyl was a German mathematician and theoretical physicist. Although much of his working life was spent in Zürich, Switzerland and then Princeton, he is associated with the University of Göttingen tradition of mathematics, represented by David Hilbert and Hermann Minkowski.His...
in his Das Kontinuum. Poincaré and Weyl argued that impredicative definitions are problematic only when one or more underlying sets are infinite.
Ernst Zermelo
Ernst Zermelo
Ernst Friedrich Ferdinand Zermelo was a German mathematician, whose work has major implications for the foundations of mathematics and hence on philosophy. He is known for his role in developing Zermelo–Fraenkel axiomatic set theory and his proof of the well-ordering theorem.-Life:He graduated...
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". 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". 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".
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.)"
Ramsey
Frank P. Ramsey
Frank Plumpton Ramsey was a British mathematician who, in addition to mathematics, made significant and precocious contributions in philosophy and economics before his death at the age of 26...
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.