HOME

TheInfoList



OR:

The axiom of reducibility was introduced by
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, ar ...
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.


History

With Russell's discovery (1901, 1902) of a
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 ...
in Gottlob Frege's 1879 ''Begriffsschrift'' and Frege's acknowledgment of the same (1902), Russell tentatively introduced his solution as "Appendix B: Doctrine of Types" in his 1903 ''The Principles of Mathematics''. This
contradiction In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...
can be stated as "the class of all classes that do not contain themselves as elements". At the end of this appendix Russell asserts that his "doctrine" would solve the immediate problem posed by Frege, but "there is at least one closely analogous contradiction which is probably not soluble by this doctrine. The totality of all logical objects, or of all propositions, involves, it would seem a fundamental logical difficulty. What the complete solution of the difficulty may be, I have not succeeded in discovering; but as it affects the very foundations of reasoning..." By the time of his 1908 ''Mathematical logic as based on the theory of types'' Russell had studied "the contradictions" (among them the
Epimenides paradox The Epimenides paradox reveals a problem with self-reference in logic. It is named after the Cretan philosopher Epimenides of Knossos (alive circa 600 BC) who is credited with the original statement. A typical description of the problem is given ...
, 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 ...
, and Richard's paradox) and concluded that "In all the contradictions there is a common characteristic, which we may describe as self-reference or reflexiveness". In 1903, Russell defined ''predicative'' functions as those whose order is one more than the highest-order function occurring in the expression of the function. While these were fine for the situation, ''impredicative'' functions had to be disallowed: He repeats this definition in a slightly different way later in the paper (together with a subtle prohibition that they would express more clearly in 1913): This usage carries over to
Alfred North Whitehead Alfred North Whitehead (15 February 1861 – 30 December 1947) was an English mathematician and philosopher. He is best known as the defining figure of the philosophical school known as process philosophy, which today has found applicat ...
and Russell's 1913 ''
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') 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. ...
'' wherein the authors devote an entire subsection of their Chapter II: "The Theory of Logical Types" to subchapter I. ''The Vicious-Circle Principle'': "We will define a function of one variable as ''predicative'' when it is of the next order above that of its argument, i.e. of the lowest order compatible with its having that argument. . . A function of several arguments is predicative if there is one of its arguments such that, when the other arguments have values assigned to them, we obtain a predicative function of the one undetermined argument." They again propose the definition of a ''predicative function'' as one that does not violate The Theory of Logical Types. Indeed the authors assert such violations are "incapable o achieve and "impossible": The authors stress the word ''impossible'':


Russell's axiom of reducibility

The axiom of reducibility states that any truth function (i.e.
propositional function In propositional calculus, a propositional function or a predicate is a sentence expressed in a way that would assume the value of true or false, except that within the sentence there is a variable (''x'') that is not defined or specified (thus be ...
) can be expressed by a formally equivalent ''predicative'' truth function. It made its first appearance in
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, ar ...
's (1908) ''Mathematical logic as based on the theory of types'', but only after some five years of trial and error. In his words: For relations (functions of two variables such as "For all x and for all y, those values for which f(x,y) is true" i.e. ∀x∀y: f(x,y)), Russell assumed an ''axiom of relations'', or he same''axiom of reducibility''. In 1903, he proposed a possible process of evaluating such a 2-place function by comparing the process to double integration: One after another, plug into ''x'' definite values ''am'' (i.e. the particular ''aj'' is "a constant" or a parameter held constant), then evaluate f(''am'',''yn'') across all the ''n'' instances of possible ''yn''. For all ''yn'' evaluate f(a1, ''yn''), then for all ''yn'' evaluate f(''a2'', ''yn''), etc until all the ''x'' = ''am'' are exhausted). This would create an ''m'' by ''n'' matrix of values: TRUE or UNKNOWN. (In this exposition, the use of indices is a modern convenience.) In 1908, Russell made no mention of this
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...
of ''x'', ''y'' values that render a two-place function (e.g. relation) TRUE, but by 1913 he has introduced a matrix-like concept into "function". In *12 of
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') 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. ...
(1913) he defines "a matrix" as "any function, of however many variables, which does not involve any apparent variables. Then any possible function other than a matrix is derived from a matrix by means of generalisation, i.e. by considering the proposition which asserts that the function in question is true with all possible values or with some values of one of the arguments, the other argument or arguments remaining undetermined". For example, if one asserts that "∀y: f(x, y) is true", then ''x'' is the apparent variable because it is unspecified. Russell now defines a matrix of "individuals" as a ''first-order'' matrix, and he follows a similar process to define a ''second-order matrix'', etc. Finally, he introduces the definition of a ''predicative function'': From this reasoning, he then uses the same wording to propose the same ''axioms of reducibility'' as he did in his 1908. As an aside, Russell in his 1903 considered, and then rejected, "a temptation to regard a relation as definable in extension as a class of couples", i.e. the modern set-theoretic notion of ordered pair. An intuitive version of this notion appeared in Frege's (1879) ''Begriffsschrift'' (translated in van Heijenoort 1967:23); Russell's 1903 followed closely the work of Frege (cf. Russell 1903:505ff). Russell worried that "it is necessary to give sense to the couple, to distinguish the referent from the relatum: thus a couple becomes essentially distinct from a class of two terms, and must itself be introduced as a primitive idea. It would seem, viewing the idea philosophically, that sense can only be derived from some relational proposition . . . it seems therefore more correct to take an intensional view of relations, and to identify them rather with class-concepts than with classes". As shown below, Norbert Wiener (1914) reduced the notion of relation to class by his definition of an ordered pair.


Criticism


Zermelo 1908

The outright prohibition implied by Russell's ''axiom of reducibility'' was roundly criticised by
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 ''Investigations in the foundations of set theory I'', stung as he was by a demand similar to that of Russell that came from Poincaré: Zermelo countered:


Wiener 1914

In his 1914 ''A simplification of the logic of relations'', Norbert Wiener removed the need for the axiom of reducibility as applied to relations between two variables ''x'', and ''y'' e.g. φ(''x'',''y''). He did this by introducing a way to express a relation as a set of ordered pairs: "It will be seen that what we have done is practically to revert to Schröder's treatment of a relation as a class etof ordered couples". Van Heijenoort observes that " giving a definition of the ordered pair of two-elements in terms of class operations, the note reduced the theory of relations to that of classes." But Wiener opined that while he had dispatched Russell and Whitehead's two-variable version of the axiom *12.11, the single-variable version of the axiom of reducibility for (axiom *12.1 in ''Principia Mathematica'') was still necessary.


Wittgenstein 1918

Ludwig Wittgenstein, while imprisoned in a prison camp, finished his '' Tractatus Logico-Philosophicus''. His introduction credits "the great works of Frege and the writings of my friend Bertrand Russell". Not a self-effacing intellectual, he pronounced that "the ''truth'' of the thoughts communicated here seems to me unassailable and definitive. I am, therefore, of the opinion that the problems have in essentials been finally solved." So given such an attitude, it is no surprise that Russell's theory of types comes under criticism: This appears to support the same argument Russell uses to erase his "paradox". This "using the signs" to "speak of the signs" Russell criticises in his introduction that preceded the original English translation: This problem appears later when Wittgenstein arrives at this gentle disavowal of the axiom of reducibility—one interpretation of the following is that Wittgenstein is saying that Russell has made (what is known today as) a
category error A category mistake, or category error, or categorical mistake, or mistake of category, is a semantic or ontological error in which things belonging to a particular category are presented as if they belong to a different category, or, alternativel ...
; Russell has asserted (inserted into the theory) a "further law of logic" when ''all'' the laws (e.g. the unbounded Sheffer stroke adopted by Wittgenstein) have ''already'' been asserted:


Russell 1919

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, ar ...
in his 1919 '' Introduction to Mathematical Philosophy'', a non-mathematical companion to his first edition of ''PM'', discusses his Axiom of Reducibility in Chapter 17 ''Classes'' (pp. 146ff). He concludes that "we cannot accept "class" as a primitive idea; the symbols for classes are "mere conveniences" and classes are "logical fictions, or (as we say) 'incomplete symbols' ... classes cannot be regarded as part of the ultimate furniture of the world" (p. 146). The reason for this is because of the problem of impredicativity: "classes cannot be regarded as a species of individuals, on account of the contradiction about classes which are not members of themselves ... and because we can prove that the number of classes is greater than the number of individuals, tc. What he then does is propose 5 obligations that must be satisfied with respect to a theory of classes, and the result is his axiom of reducibility. He states that this axiom is "a generalised form of Leibniz's identity of indiscernibles" (p. 155). But he concludes Leibniz's assumption is not necessarily true for all possible predicates in all possible worlds, so he concludes that: The goal that he sets for himself then is "adjustments to his theory" of avoiding classes:


Skolem 1922

Thoralf Skolem in his 1922 ''Some remarks on axiomatised set theory'' took a less than positive attitude toward "Russell and Whitehead" (i.e. their work ''Principia Mathematica''): Skolem then observes the problems of what he called "nonpredicative definition" in the set theory of Zermelo: While Skolem is mainly addressing a problem with Zermelo's set theory, he does make this observation about the ''axiom of reducibility'':


Russell 1927

In his 1927 "Introduction" to the second edition of ''
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') 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. ...
'', Russell criticises his own axiom: Wittgenstein's 5.54ff is more centred on the notion of
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...
: A possible interpretation of Wittgenstein's stance is that the thinker A i.e. ''p'' ''is identically'' the thought ''p'', in this way the "soul" remains a unit and not a composite. So to utter "the thought thinks the thought" is nonsense, because per 5.542 the utterance does not specify anything.


von Neumann 1925

John von Neumann in his 1925 "An axiomatisation of set theory" wrestled with the same issues as did Russell, Zermelo, Skolem, and Fraenkel. He summarily rejected the effort of Russell: He then notes the work of the set theorists Zermelo, Fraenkel and Schoenflies, in which "one understands by "set" nothing but an object of which one knows no more and wants to know no more than what follows about it from the postulates. The postulates f set theoryare to be formulated in such a way that all the desired theorems of Cantor's set theory follow from them, but not the antinomies. While he mentions the efforts of David Hilbert to prove the consistency of his axiomatisation of mathematics von Neumann placed him in the same group as Russell. Rather, von Neumann considered his proposal to be "in the spirit of the second group ... We must, however, avoid forming sets by collecting or separating elements urch Zusammenfassung oder Aussonderung von Elementen and so on, as well as eschew the unclear principle of 'definiteness' that can still be found in Zermelo. ..We prefer, however, to axiomatise not 'set' but 'function'." Van Heijenoort observes that ultimately this axiomatic system of von Neumann's, "was simplified, revised, and expanded ... and it come to be known as the von Neumann-Bernays-Gödel set theory."


David Hilbert 1927

David Hilbert's
axiomatic system In mathematics and logic, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A theory is a consistent, relatively-self-contained body of knowledge which usually contai ...
that he presents in his 1925 ''The Foundations of Mathematics'' is the mature expression of a task he set about in the early 1900s but let lapse for a while (cf. his 1904 ''On the foundations of logic and arithmetic''). His system is neither set theoretic nor derived directly from Russell and Whitehead. Rather, it invokes 13 axioms of logic—four axioms of Implication, six axioms of logical AND and logical OR, 2 axioms of logical negation, and 1 ε-axiom ("existence" axiom)-- plus a version of the Peano axioms in 4 axioms including
mathematical induction Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ...  all hold. Informal metaphors help ...
, some definitions that "have the character of axioms, and certain ''recursion axioms'' that result from a general recursion schema" plus some formation rules that "govern the use of the axioms". Hilbert states that, with regard to this system, i.e. "Russell and Whitehead's theory of foundations ... the foundation that it provides for mathematics rests, first, upon the axiom of infinity and, then upon what is called the axiom of reducibility, and both of these axioms are genuine contentual assumptions that are not supported by a consistency proof; they are assumptions whose validity in fact remains dubious and that, in any case, my theory does not require ... reducibility is not presupposed in my theory ... the execution of the reduction would be required only in case a proof of a contradiction were given, and then, according to my proof theory, this reduction would always be bound to succeed." It is upon this foundation that modern recursion theory rests.


Ramsey 1925

In 1925,
Frank Plumpton Ramsey Frank Plumpton Ramsey (; 22 February 1903 – 19 January 1930) was a British philosopher, mathematician, and economist who made major contributions to all three fields before his death at the age of 26. He was a close friend of Ludwig Wittgenste ...
argued that it is not needed. However in the second edition of
Principia Mathematica The ''Principia Mathematica'' (often abbreviated ''PM'') 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. ...
(1927, page xiv) and in Ramsey's 1926 paper it is stated that certain theorems about
real numbers 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 ...
could not be proved using Ramsey's approach. Most later mathematical formalisms (Hilbert's
Formalism Formalism may refer to: * Form (disambiguation) * Formal (disambiguation) * Legal formalism, legal positivist view that the substantive justice of a law is a question for the legislature rather than the judiciary * Formalism (linguistics) * Scien ...
or Brower's
Intuitionism In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of f ...
for example) do not use it. Ramsey showed that it is possible to reformulate the definition of ''predicative'' by using the definitions in
Wittgenstein Ludwig Josef Johann Wittgenstein ( ; ; 26 April 1889 – 29 April 1951) was an Austrian-British philosopher who worked primarily in logic, the philosophy of mathematics, the philosophy of mind, and the philosophy of language. He is consider ...
's Tractatus Logico-Philosophicus. As a result, all functions of a given order are ''predicative'', irrespective of how they are expressed. He goes on to show that his formulation still avoids the paradoxes. However, the "Tractatus" theory did not appear strong enough to prove some mathematical results.


Gödel 1944

Kurt Gödel in his 1944 ''Russell's mathematical logic'' offers in the words of his commentator Charles Parsons, "
hat A hat is a head covering which is worn for various reasons, including protection against weather conditions, ceremonial reasons such as university graduation, religious reasons, safety, or as a fashion accessory. Hats which incorporate mecha ...
might be seen as a defense of these ealistattitudes of Russell against the reductionism prominent in his philosophy and implicit in much of his actual logical work. It was perhaps the most robust defense of realism about mathematics and its objects since the paradoxes and come to the consciousness of the mathematical world after 1900". In general, Gödel is sympathetic to the notion that a propositional function can be reduced to (identified with) the ''real objects'' that satisfy it, but this causes problems with respect to the theory of real numbers, and even integers (p. 134). He observes that the first edition of ''PM'' "abandoned" the realist (constructivistic) "attitude" with his proposal of the axiom of reducibility (p. 133). However, within the introduction to the second edition of ''PM'' (1927) Gödel asserts "the constructivistic attitude is resumed again" (p. 133) when Russell "dropped" of the axiom of reducibility in favour of the matrix (truth-functional) theory; Russell "stated explicitly that all primitive predicates belong to the lowest type and that the only purpose of variables (and evidently also of constants) is to make it possible to assert more complicated truth-functions of atomic propositions ... .e.the higher types and orders are solely a '' façon de parler''" (p. 134). But this only works when the number of individuals and primitive predicates is finite, for one can construct finite strings of symbols such as: :x = a_1 \vee x = a_2 \vee \dots \vee x = a_k xample on page 134And from such strings one can form strings of strings to obtain the equivalent of classes of classes, with a mixture of types possible. However, from such finite strings the whole of mathematics cannot be constructed because they cannot be "analyzed", i.e. reducible to the law of identity or disprovable by a negations of the law: But he observes that "this procedure seems to presuppose arithmetic in some form or other" (p. 134), and he states in the next paragraph that "the question of whether (or to what extent) the theory of integers can be obtained on the basis of the ramified hierarchy must be considered as unsolved." (p. 135) Gödel proposed that one should take a "more conservative approach":


Quine 1967

In a critique that also discusses the pros and cons of Ramsey (1931)
W. V. O. Quine W. may refer to: * SoHo (Australian TV channel) (previously W.), an Australian pay television channel * ''W.'' (film), a 2008 American biographical drama film based on the life of George W. Bush * "W.", the fifth track from Codeine's 1992 EP ''Bar ...
calls Russell's formulation of "types" to be "troublesome ... the confusion persists as he attempts to define ''n''th order propositions'... the method is indeed oddly devious ... the axiom of reducibility is self-effacing", etc. Like Stephen Kleene, Quine observes that Ramsey (1926) divided the various paradoxes into two varieties (i) "those of pure set theory" and (ii) those derived from "semantic concepts such as falsity and specifiability", and Ramsey believed that the second variety should have been left out of Russell's solution. Quine ends with the opinion that "because of the confusion of propositions with sentences, and of attributes with their expressions, Russell's purported solution of the semantic paradoxes was enigmatic anyway."


Kleene 1952

In his section "§12. First inferences from the paradoxes" (subchapter "LOGICISM"), Stephen Kleene (1952) traces the development of Russell's theory of types: Kleene observes that "to exclude impredicative definitions within a type, the types above type 0 rimary objects or individuals "not subjected to logical analysis"are further separated into orders. Thus for type 1 roperties of individuals, i.e. logical results of the propositional calculus ], properties defined without mentioning any totality belong to ''order'' 0, and properties defined using the totality of properties of a given order below to the next higher order)". Kleene, however, parenthetically observes that "the logicistic definition of natural number now becomes predicative when the ropertyP in it is specified to range only over properties of a given order; in
his His or HIS may refer to: Computing * Hightech Information System, a Hong Kong graphics card company * Honeywell Information Systems * Hybrid intelligent system * Microsoft Host Integration Server Education * Hangzhou International School, ...
case the property of being a natural number is of the next higher order". But this separation into orders makes it impossible to construct the familiar analysis, which ee_Kleene's_example_at_Impredicativity.html" ;"title="Impredicativity.html" ;"title="ee Kleene's example at Impredicativity">ee Kleene's example at Impredicativity">Impredicativity.html" ;"title="ee Kleene's example at Impredicativity">ee Kleene's example at Impredicativitycontains impredicative definitions. To escape this outcome, Russell postulated his ''axiom of reducibility''. But, Kleene wonders, "on what grounds should we believe in the axiom of reducibility?" He observes that, whereas ''Principia Mathematica'' is presented as derived from ''intuitively''-derived axioms that "were intended to be believed about the world, or at least to be accepted as plausible hypotheses concerning the world ... if properties are to be constructed, the matter should be settled on the basis of constructions, not by an axiom." Indeed, he quotes Whitehead and Russell (1927) questioning their own axiom: "clearly it is not the sort of axiom with which we can rest content". Kleene references the work of Ramsey 1926, but notes that "neither Whitehead and Russell nor Ramsey succeeded in attaining the logicistic goal constructively" and "an interesting proposal ... by Langford 1927 and Carnap 1931-2, is also not free of difficulties." Kleene ends this discussion with quotes from Weyl (1946) that "the system of ''Principia Mathematica'' ... [is founded on] a sort of logician's paradise" and anyone "who is ready to believe in this 'transcendental world' could also accept the system of axiomatic set theory (Zermelo, Fraenkel, etc), which, for the deduction of mathematics, has the advantage of being simpler in structure."Kleene 1952:45


Notes


References

* van Heijenoort, Jean (1967, 3rd printing 1976), ''From Frege to Godel: A Source Book in Mathematical Logic, 1879–1931'', Harvard University Press, Cambridge, MA, (pbk) * Russell, Bertrand (1903) ''The Principles of Mathematics: Vol. 1'', Cambridge at the University Press, Cambridge, UK, republished as a googlebook. * Whitehead, Alfred North and Russell, Bertrand (1910–1913, 2nd edition 1927, reprinted 1962 edition), ''Principia Mathematica to *56'', Cambridge at the University Press, London UK, no ISBN or US card catalogue number. * Mario Livio (2009), ''Is God a Mathematician?'', Simon and Schuster, New York, NY, .


External links

* {{DEFAULTSORT:Axiom Of Reducibility Foundations of mathematics Bertrand Russell Type theory Concepts in logic