Impredicativity

Last updated

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

Contents

The opposite of impredicativity is predicativity, which essentially entails building stratified (or ramified) theories where quantification over a type at one 'level' results in types at a new, higher, level. A prototypical example is intuitionistic type theory, which retains ramification (without the explicit levels) so as to discard impredicativity. The 'levels' here correspond to the number of layers of dependency in a term definition.

Russell's paradox is a famous example of an impredicative construction—namely the set of all sets that do not contain themselves. The paradox 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 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. This definition 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

Norms (containing one variable) which do not define classes I propose to call non-predicative; those which do define classes I shall call predicative.

(Russell 1907, p.34) (Russell used "norm" to mean a proposition: roughly something that can take the values "true" or "false".)

The terms "predicative" and "impredicative" were introduced by Russell (1907), though the meaning has changed a little since then.

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 that 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. Georg 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 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. Therefore 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 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 ...". [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"[ full citation needed ] 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...". [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

Related Research Articles

In mathematics, the axiom of regularity is an axiom of Zermelo–Fraenkel set theory that states that every non-empty set A contains an element that is disjoint from A. In first-order logic, the axiom reads:

Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language. It describes the aspects of mathematical sets familiar in discrete mathematics, and suffices for the everyday use of set theory concepts in contemporary mathematics.

In logic, the law of excluded middle states that for every proposition, either this proposition or its negation is true. It is one of the so-called three laws of thought, along with the law of noncontradiction, and the law of identity. However, no system of logic is built on just these laws, and none of these laws provides inference rules, such as modus ponens or De Morgan's laws.

In the philosophy of mathematics, intuitionism, or neointuitionism, is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of fundamental principles claimed to exist in an objective reality. That is, logic and mathematics are not considered analytic activities wherein deep properties of objective reality are revealed and applied, but are instead considered the application of internally consistent methods used to realize more complex mental constructs, regardless of their possible independent existence in an objective reality.

Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics.

<i>Principia Mathematica</i> Book on the foundations of mathematics (1910–13, 1925–27)

The Principia Mathematica is a three-volume work on the foundations of mathematics written by mathematician–philosophers Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913. In 1925–1927, it appeared in a second edition with an important Introduction to the Second Edition, an Appendix A that replaced ✱9 and all-new Appendix B and Appendix C. PM was conceived as a sequel to Russell's 1903 The Principles of Mathematics, but as PM states, this became an unworkable suggestion for practical and philosophical reasons: "The present work was originally intended by us to be comprised in a second volume of Principles of Mathematics... But as we advanced, it became increasingly evident that the subject is a very much larger one than we had supposed; moreover on many fundamental questions which had been left obscure and doubtful in the former work, we have now arrived at what we believe to be satisfactory solutions."

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 nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete.

<span class="mw-page-title-main">Set theory</span> Branch of mathematics that studies sets

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 concerned with those that are relevant to mathematics as a whole.

<span class="mw-page-title-main">Russell's paradox</span> Paradox in set theory

In mathematical logic, Russell's paradox is a set-theoretic paradox published by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains an unrestricted comprehension principle leads to contradictions. The paradox had already been discovered independently in 1899 by the German mathematician Ernst Zermelo. However, Zermelo did not publish the idea, which remained known only to David Hilbert, Edmund Husserl, and other academics at the University of Göttingen. At the end of the 1890s, Georg Cantor – considered the founder of modern set theory – had already realized that his theory would lead to a contradiction, as he told Hilbert and Richard Dedekind by letter.

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 Cesare Burali-Forti, who, in 1897, published a paper proving a theorem which, unknown to him, contradicted a previously proved result by Cantor. Bertrand Russell subsequently noticed the contradiction, and when he published it in his 1903 book Principles of Mathematics, he stated that it had been suggested to him by Burali-Forti's paper, with the result that it came to be known by Burali-Forti's name.

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 between mathematics and metamathematics.

<span class="mw-page-title-main">Metamathematics</span> Study of mathematics itself

Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories. Emphasis on metamathematics owes itself to David Hilbert's attempt to secure the foundations of mathematics in the early part of the 20th century. Metamathematics provides "a rigorous mathematical technique for investigating a great variety of foundation problems for mathematics and logic". An important feature of metamathematics is its emphasis on differentiating between reasoning from inside a system and from outside a system. An informal illustration of this is categorizing the proposition "2+2=4" as belonging to mathematics while categorizing the proposition "'2+2=4' is valid" as belonging to metamathematics.

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 of mathematics may be modelled in logic. Bertrand Russell and Alfred North Whitehead championed this programme, initiated by Gottlob Frege and subsequently developed by Richard Dedekind and Giuseppe Peano.

The laws of thought are fundamental axiomatic rules upon which rational discourse itself is often considered to be based. The formulation and clarification of such rules have a long tradition in the history of philosophy and logic. Generally they are taken as laws that guide and underlie everyone's thinking, thoughts, expressions, discussions, etc. However, such classical ideas are often questioned or rejected in more recent developments, such as intuitionistic logic, dialetheism and fuzzy logic.

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 of set theory.

The history of the Church–Turing thesis ("thesis") involves the history of the development of the study of the nature of functions whose values are effectively calculable; or, in more modern terms, functions whose values are algorithmically computable. It is an important topic in modern mathematical theory and computer science, particularly associated with the work of Alonzo Church and Alan Turing.

<span class="mw-page-title-main">Brouwer–Hilbert controversy</span>

In a controversy over the foundations of mathematics, in twentieth-century mathematics, L. E. J. Brouwer, a proponent of the constructivist school of intuitionism, opposed David Hilbert, a proponent of formalism. The debate concerned fundamental questions about the consistency of axioms and the role of semantics and syntax in mathematics. Much of the controversy took place while both were involved with Mathematische Annalen, the leading mathematical journal of the time, with Hilbert as editor-in-chief and Brouwer as a member of its editorial board. In 1920, Hilbert succeeded in having Brouwer, whom he considered a threat to mathematics, removed from the editorial board of Mathematische Annalen.

The mathematical concept of a function dates from the 17th century in connection with the development of the calculus; for example, the slope of a graph at a point was regarded as a function of the x-coordinate of the point. Functions were not explicitly considered in antiquity, but some precursors of the concept can perhaps be seen in the work of medieval philosophers and mathematicians such as Oresme.

The type theory was initially created to avoid paradoxes in a variety of formal logics and rewrite systems. Later, type theory referred to a class of formal systems, some of which can serve as alternatives to naive set theory as a foundation for all mathematics.

Class logic is a logic in its broad sense, whose objects are called classes. In a narrower sense, one speaks of a class logic only if classes are described by a property of their elements. This class logic is thus a generalization of set theory, which allows only a limited consideration of classes.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.