HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
,
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from prem ...
and
philosophy of mathematics The philosophy of mathematics is the branch of philosophy that studies the assumptions, foundations, and implications of mathematics. It aims to understand the nature and methods of mathematics, and find out the place of mathematics in people' ...
, something that is impredicative is a self-referencing
definition A definition is a statement of the meaning of a term (a word, phrase, or other set of symbols). Definitions can be classified into two large categories: intensional definitions (which try to give the sense of a term), and extensional definiti ...
. Roughly speaking, a definition is impredicative if it invokes (mentions or quantifies over) the set being defined, or (more commonly) another set that contains the thing being defined. There is no generally accepted precise definition of what it means to be predicative or impredicative. Authors have given different but related definitions. The opposite of impredicativity is predicativity, which essentially entails building
stratified Stratification may refer to: Mathematics * Stratification (mathematics), any consistent assignment of numbers to predicate symbols * Data stratification in statistics Earth sciences * Stable and unstable stratification * Stratification, or st ...
(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 so as to discard impredicativity.
Russell's paradox In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains ...
is a famous example of an impredicative construction—namely the
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
of all sets that do not contain themselves. The
paradox A paradox is a logically self-contradictory statement or a statement that runs contrary to one's expectation. It is a statement that, despite apparently valid reasoning from true premises, leads to a seemingly self-contradictory or a logically u ...
is that such a set cannot exist: If it would exist, the question could be asked whether it 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 In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest ...
of a set , , also has an impredicative definition: if and only if for all elements of , is less than or equal to , and any less than or equal to all elements of is less than or equal to . This definition quantifies over the set (potentially infinite, depending on the
order Order, ORDER or Orders may refer to: * Categorization, the process in which ideas and objects are recognized, differentiated, and understood * Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of ...
in question) whose members are the lower bounds of , one of which being the glb itself. Hence predicativism would reject this definition.


History

The terms "predicative" and "impredicative" were introduced by , though the meaning has changed a little since then.
Solomon Feferman Solomon Feferman (December 13, 1928 – July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic. Life Solomon Feferman was born in The Bronx in New York City to working-class parents who had immigrated to th ...
provides a historical review of predicativity, connecting it to current outstanding research problems. The
vicious 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 depen ...
was suggested by
Henri Poincaré Jules Henri Poincaré ( S: stress final syllable ; 29 April 1854 – 17 July 1912) was a French mathematician, theoretical physicist, engineer, and philosopher of science. He is often described as a polymath, and in mathematics as "Th ...
(1905-6, 1908) and
Bertrand Russell Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, a ...
in the wake of the paradoxes as a requirement on legitimate set specifications. Sets that do not meet the requirement are called ''impredicative''. The first modern paradox appeared with
Cesare Burali-Forti Cesare Burali-Forti (13 August 1861 – 21 January 1931) was an Italian mathematician, after whom the Burali-Forti paradox is named. Biography Burali-Forti was born in Arezzo, and was an assistant of Giuseppe Peano in Turin from 1894 to 1 ...
's 1897 ''A question on transfinite numbers'' and would become known as the
Burali-Forti paradox In set theory, a field of mathematics, the Burali-Forti paradox demonstrates that constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction. It is named after C ...
. Cantor had apparently discovered the same paradox in his (Cantor's) "naive" set theory and this become known as
Cantor's paradox In set theory, Cantor's paradox states that there is no set of all cardinalities. This is derived from the theorem that there is no greatest cardinal number. In informal terms, the paradox is that the collection of all possible "infinite sizes" is ...
. Russell's awareness of the problem originated in June 1901 with his reading of
Frege Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic p ...
's treatise of mathematical logic, his 1879 ''
Begriffsschrift ''Begriffsschrift'' (German for, roughly, "concept-script") is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book. ''Begriffsschrift'' is usually translated as ''concept writing'' or ''concept nota ...
''; the offending sentence in Frege is the following: In other words, given the function is the variable and is the invariant part. So why not substitute the value for 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 uses 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 six years of false starts, would eventually answer the matter with his 1908 theory of types by "propounding his ''
axiom of reducibility The axiom of reducibility was introduced by Bertrand Russell in the early 20th century as part of his ramified theory of types. Russell devised and introduced the axiom in an attempt to manage the contradictions he had discovered in his analysis ...
''. 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 In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
s as classically understood) leads to the position in the
philosophy of mathematics The philosophy of mathematics is the branch of philosophy that studies the assumptions, foundations, and implications of mathematics. It aims to understand the nature and methods of mathematics, and find out the place of mathematics in people' ...
known as predicativism, advocated by
Henri Poincaré Jules Henri Poincaré ( S: stress final syllable ; 29 April 1854 – 17 July 1912) was a French mathematician, theoretical physicist, engineer, and philosopher of science. He is often described as a polymath, and in mathematics as "Th ...
and
Hermann Weyl Hermann Klaus Hugo Weyl, (; 9 November 1885 – 8 December 1955) was a German mathematician, theoretical physicist and philosopher. Although much of his working life was spent in Zürich, Switzerland, and then Princeton, New Jersey, he is asso ...
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 Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic ...
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) ho states thata 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 is used for further inferences. This happens, for example, in the well-known Cauchy proof...". 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 of
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s having an upper bound has a least upper bound (cf. also Weyl 1919)".Kleene 1952:43 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: if and only if for all elements of , is less than or equal to , and is in . Burgess (2005) discusses predicative and impredicative theories at some length, in the context of
Frege Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic p ...
's logic,
Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearl ...
,
second-order arithmetic In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. A precur ...
, and
axiomatic set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
.


See also

* ''
Gödel, Escher, Bach ''Gödel, Escher, Bach: an Eternal Golden Braid'', also known as ''GEB'', is a 1979 book by Douglas Hofstadter. By exploring common themes in the lives and works of logician Kurt Gödel, artist M. C. Escher, and composer Johann Sebastian Bach, t ...
'' * Impredicative polymorphism *
Logicism In the philosophy of mathematics, logicism is a programme comprising one or more of the theses that — for some coherent meaning of 'logic' — mathematics is an extension of logic, some or all of mathematics is reducible to logic, or some or all ...
*
Richard's paradox In logic, Richard's paradox is a semantical antinomy of set theory and natural language first described by the French mathematician Jules Richard in 1905. The paradox is ordinarily used to motivate the importance of distinguishing carefully betwee ...


Notes


References

*
PlanetMath article on predicativism
* John Burgess, 2005. ''Fixing Frege''. Princeton Univ. Press. *
Solomon Feferman Solomon Feferman (December 13, 1928 – July 26, 2016) was an American philosopher and mathematician who worked in mathematical logic. Life Solomon Feferman was born in The Bronx in New York City to working-class parents who had immigrated to th ...
, 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, . In particular cf. his ''§11 The Paradoxes'' (pp. 36–40) and ''§12 First inferences from the paradoxes'' IMPREDICATIVE DEFINITION (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 Russell (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 Hans Reichenbach (September 26, 1891 – April 9, 1953) was a leading philosopher of science, educator, and proponent of logical empiricism. He was influential in the areas of science, education, and of logical empiricism. He founded the ''Ges ...
1947, ''Elements of Symbolic Logic'', Dover Publications, Inc., NY, . 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. * Jean van Heijenoort 1967, third printing 1976, ''From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931'', Harvard University Press, Cambridge MA, {{ISBN, 0-674-32449-8 (pbk.) Mathematical logic Philosophy of mathematics Self-reference Concepts in logic Recursion