Axiom of reducibility
Encyclopedia
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
.
'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 Principles of Mathematics. This contradiction
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 Burali-Forti paradox
, 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 his 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 good, 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): "A predicative function of x is one whose values are propositions of the type next above that of x, if x is an individual or a proposition, or that of values of x if x is a function. It may be described as one in which the apparent variables, if any, are all of the same type as x or of lower type; and a variable is of lower type than x if it can significantly occur as argument to x, or as argument to an argument to x, and so forth"
This usage carries over to Alfred North Whitehead
and Russell's 1913 Principia Mathematica
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"
Again, they 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 [to achieve]" and "impossible":
Indeed, the authors even use the word impossible:
) can be expressed by a formally equivalent predicative truth function. It makes its first appearance in Bertrand Russell
'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 [the same] axiom of reducibility.
In his 1903 he proposed how one would go about evaluating such a 2-place function; indeed he compared 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. In other words: 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 are a modern convenience).
In his 1908 Russell makes no mention of this matrix
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
(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 we assert 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.
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:
removes the need for the axiom of reducibility as applied to relations between two variables x, and y e.g. φ(x,y). He does 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 [set] of ordered couples". Indeed van Heijenoort observes that "[b]y 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.
in his 1922 Some remarks on axiomatized 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:
, 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". But is Wittgenstein committing the error of which he accuses Russell? 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; 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:
The goal that he sets for himself then is "adjustments to his theory" of avoiding classes:
Wittgenstein's 5.54ff has more to do with the notion of function
but is worth repeating for context:
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 utter nonsense, because per 5.542 the utterance does not specify anything.
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 [of set theory] are to be formulated in such a way that all the desired theorems of Cantor's set theory follow from them, but not the antinomies. In these axiomatizations, however, we can never be perfectly sure of the latter point. We see only that the known modes of inference leading to the antinomies fail, but who knows whether there are not others?
While he mentions the efforts of David Hilbert
to prove the consistency of his axiomatization 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 [durch 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 axiomatize 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".
's axiomatic system (see more at Hilbert system) 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
, 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.
(1927, page xiv) and in Ramsey's 1926 paper it is stated that certain theorems about real numbers could not be proved using Ramsey's approach. Most later mathematical formalisms (Hilbert's Formalism
or Brower
's Intuitionism
for example) do not use it.
Ramsey showed that you can reformulate the definition of predicative by using the definitions in Wittgenstein'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.
in his 1944 Russell's mathematical logic offers in the words of his commentator Charles Parsons, "[what] might be seen as a defense of these [realist] attitudes 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). But 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 favor 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 . . . [i.e.] the higher types and orders are solely a facon 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:
And 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)
In conclusion Gödel proposed that one should take a "more conservative approach": "make the meaning of the terms "class" and "concept" clearer, and to set up a consistent theory of classes and concepts as objectively existing entities. This is the course which the actual development of amthematical logic has been taking . . . Major among the attempts in this direction . . . are the simple theory of types . . . and axiomatic set theory, both of which have been successful at least to this extent, that they permit the derivation of modern mathematics and at the same time avoid all known paradoxes. Many symptoms show only too clearly, however, that the primitive concepts need further elucidation." (p. 140)
Like Kleene (see below) Quine observes that Ramsey (1926), (1931) 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 damning 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 observes that "to exclude impredicative definitions within a type, the types above type 0 [primary objects or individuals "not subjected to logical analysis"] are further separated into orders. Thus for type 1 [properties 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)".
But Kleene parenthetically observes that "the logicistic definition of natural number now becomes predicative when the [property] P in it is specified to range only over properties of a given order; in [this] 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 [see Kleene’s example at Impredicativity] contains 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:
Kleene references 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".
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...
as part of his ramified theory of types, an attempt to ground mathematics
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...
in first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
.
History: the problem of impredicativity
With Russell's discovery (1901, 1902) that of a paradox (contradiction) in Gottlob FregeGottlob Frege
Friedrich Ludwig Gottlob Frege was a German mathematician, logician and philosopher. He is considered to be one of the founders of modern logic, and made major contributions to the foundations of mathematics. He is generally considered to be the father of analytic philosophy, for his writings on...
'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 Principles of Mathematics. This contradiction
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...
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
Epimenides paradox
The Epimenides paradox is a problem in logic. It is named after the Cretan philosopher Epimenides of Knossos , There is no single statement of the problem; a typical variation is given in the book Gödel, Escher, Bach, by Douglas Hofstadter:...
, 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...
, Richard's paradox
Richard's paradox
In logic, Richard's paradox is a semantical antinomy in set theory and natural language first described by the French mathematician Jules Richard in 1905. Today, the paradox is ordinarily used in order to motivate the importance of carefully distinguishing between mathematics and metamathematics...
) and concluded that "In all the contradictions there is a common characteristic, which we may describe as self-reference or reflexiveness"..
In his 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 good, impredicative functions had to be disallowed:
- "A function whose argument is an individual and whose value is always a first-order proposition will be called a first-order function. A function involving a first-order function or proposition as apparent variable will be called a second-order function, and so on. A function of one variable which is of the order next above that of its argument will be called a predicative function; the same name will be given to a function of several variables [etc] . . .."
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): "A predicative function of x is one whose values are propositions of the type next above that of x, if x is an individual or a proposition, or that of values of x if x is a function. It may be described as one in which the apparent variables, if any, are all of the same type as x or of lower type; and a variable is of lower type than x if it can significantly occur as argument to x, or as argument to an argument to x, and so forth"
This usage carries over to Alfred North Whitehead
Alfred North Whitehead
Alfred North Whitehead, OM FRS was an English mathematician who became a philosopher. He wrote on algebra, logic, foundations of mathematics, philosophy of science, physics, metaphysics, and education...
and Russell's 1913 Principia Mathematica
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by 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"
Again, they 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 [to achieve]" and "impossible":
- "We are thus lead to the conclusion, both from the vicious-circle principle and from direct inspection, that the functions to which a given object a can be an argument are incapable of being arguments to each other, and that they have no term in common with the functions to which they can be arguments. We are thus led to construct a hierarchy".
Indeed, the authors even use the word impossible:
- ". . .if we are not mistaken, that not only is it impossible for a function φz^ to have itself or anything derived from it as argument, but that, if ψz^ is another function such there are arguments a with which both "φa" and "ψa" are significant, then ψz^ and anything derived from it cannot significantly be argument to φz^".
Russell's axiom of reducibility
The axiom of reducibility states that any truth function (i.e. propositional functionPropositional function
A propositional function in logic, is a statement expressed in a way that would assume the value of true or false, except that within the statement is a variable that is not defined or specified, which leaves the statement undetermined...
) can be expressed by a formally equivalent predicative truth function. It makes its first appearance in 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...
's (1908) Mathematical logic as based on the theory of types, but only after some five years of trial and error . In his words:
- "Thus a predicative function of an individual is a first-order function; and for higher types of arguments, predicative functions take the place that first-order functions take in respect of individuals. We assume then, that every function is equivalent, for all its values, to some predicative function of the same argument. This assumption seems to be the essence of the usual assumption of classes [modern sets] . . . we will call this assumption the axiom of classes, or the axiom of reducibility."
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 [the same] axiom of reducibility.
In his 1903 he proposed how one would go about evaluating such a 2-place function; indeed he compared 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. In other words: 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 are a modern convenience).
In his 1908 Russell makes no mention of this matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
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
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by 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 we assert 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:
- A function is said to be predicative when it is a matrix. It will be observed that, in a hierarchy in which all the variables are individuals or matrices, a matrix is the same thing as an elementary function [cf 1913:127, meaning: the function contains no apparent variables]. ¶ "Matrix" or "predicative function" is a primitive idea"
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
Ordered pair
In mathematics, an ordered pair is a pair of mathematical objects. In the ordered pair , the object a is called the first entry, and the object b the second entry of the 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
Intensional
Intensional* in philosophy of language: not extensional. See also intensional definition versus extensional definition.* in philosophy of mind: an intensional state is a state which has a propositional content....
view of relations, and to identify them rather with class-concepts than with classes". As shown below, Norbert Wiener
Norbert Wiener
Norbert Wiener was an American mathematician.A famous child prodigy, Wiener later became an early researcher in stochastic and noise processes, contributing work relevant to electronic engineering, electronic communication, and control systems.Wiener is regarded as the originator of cybernetics, a...
(1914) reduced the notion of relation to class by his definition of an ordered pair.
Zermelo 1908
The outright prohibition implied by Russell's axiom of reducibility was roundly criticised by Ernst ZermeloErnst 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 Investigations in the foundations of set theory I, stung as he was by a demand similar to that of Russell that came from Poincaré
Poincaré
Several members of the French Poincaré family have been successful in public and scientific life:* Henri Poincaré , physicist, mathematician and philosopher of science* Lucien Poincaré , physicist, brother of Raymond and cousin of Henri...
:
- "According to Poincaré (1906, p. 307) 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".
Zermelo countered:
- "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.".
Wiener 1914
In his 1914 A simplification of the logic of relations, Norbert WienerNorbert Wiener
Norbert Wiener was an American mathematician.A famous child prodigy, Wiener later became an early researcher in stochastic and noise processes, contributing work relevant to electronic engineering, electronic communication, and control systems.Wiener is regarded as the originator of cybernetics, a...
removes the need for the axiom of reducibility as applied to relations between two variables x, and y e.g. φ(x,y). He does 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 [set] of ordered couples". Indeed van Heijenoort observes that "[b]y 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.
Skolem 1922
Thoralf SkolemThoralf Skolem
Thoralf Albert Skolem was a Norwegian mathematician known mainly for his work on mathematical logic and set theory.-Life:...
in his 1922 Some remarks on axiomatized set theory took a less than positive attitude toward "Russell and Whitehead" (i.e. their work Principia Mathematica):
- "Until now, so far as I know, only one such system of axioms has found rather general acceptance, namely that constructed by Zermelo (1908). Russell and Whitehead, too, constructed a system of logic that provides a foundation for set theory; if I am not mistaken, however, mathematicians have taken but little interest in it
Skolem then observes the problems of what he called "nonpredicative definition" in the set theory of Zermelo:
- "...the difficulty is that we have to form some sets whose existence depends upon all sets . . . Poincaré called this kind of definition and regarded it as the real logical weakness of set theory"
While Skolem is mainly addressing a problem with Zermelo's set theory, he does make this observation about the axiom of reducibility:
- ". . . they [Russell and Whitehead], too, simply content themselves with circumventing the difficulty by introducing a stipulation, the axiom of reducibility. Actually, this axiom decrees that the nonpredicative stipulations will be satisfied. There is no proof of that; besides, so far as I can see, such a proof must be impossible from Russell and Whitehead's point of view as well as from Zermelo's"
Wittgenstein 1918 - (1922 English translation)
Ludwig WittgensteinLudwig Wittgenstein
Ludwig Josef Johann Wittgenstein was an Austrian philosopher who worked primarily in logic, the philosophy of mathematics, the philosophy of mind, and the philosophy of language. He was professor in philosophy at the University of Cambridge from 1939 until 1947...
, while imprisoned in a prison camp, finished his Tractatus Logico-Philosophicus
Tractatus Logico-Philosophicus
The Tractatus Logico-Philosophicus is the only book-length philosophical work published by the Austrian philosopher Ludwig Wittgenstein in his lifetime. It was an ambitious project: to identify the relationship between language and reality and to define the limits of science...
. 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:
- 3.33
- In logical syntax the meaning of a sign ought never to play a role; it must admit of being established without mention being thereby made of the meaning of a sign; it ought to presuppose only the description of the expressions.
- 3.331
- From this observation we get a further view -- into Russell's Theory of Types. Russell's error is shown by the fact that in drawing up his symbolic rules he has to speak of the meaning of the signs.
- 3.332
- No proposition can say anything about itself, because the proposition sign cannot be contained in itself (that is the "whole theory of types").
- 3.333
- A function cannot be its own argument, because the functional sign already contains the prototype of its own argument and it cannot contain itself . . .. Herewith Russell's paradox vanishes..
This appears to support the same argument Russell uses to erase his "paradox". But is Wittgenstein committing the error of which he accuses Russell? This "using the signs" to "speak of the signs" Russell criticises in his introduction that preceded the original English translation:
-
- "What causes hesitation is the fact that, after all, Mr Wittgenstein manages to say a good deal about what cannot be said, thus suggesting to the sceptical reader that possibly there may be some loophole through a hierarchy of languages, or by some other exit."
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; Russell has asserted (inserted into the theory) a "further law of logic" when all the laws (e.g. the unbounded Sheffer stroke
Sheffer stroke
In Boolean functions and propositional calculus, the Sheffer stroke, named after Henry M. Sheffer, written "|" , "Dpq", or "↑", denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both"...
adopted by Wittgenstein) have already been asserted:
- 6.123
- It is clear that the laws of logic cannot themselves obey further logical laws. (There is not, as Russell supposed, for every "type" a special law of contradiction; but one is sufficient, since it is not applied to itself.)
- 6.1231
- The mark of logical propositions is not their general validity. To be general is only to be accidentally valid for all things. An ungeneralised proposition can be tautologous just as well as a generalised one.
- 6.1232
- Logical general validity, we could call essential as opposed to accidental general validity, e.g., of the proposition "all men are mortal". Propositions like Russell's "axiom of reducibility" are not logical propositions, and this explains our feeling that, if true, they can only be true by a happy chance.
- 6.1233
- We can imagine a world in which the axiom of reducibility is not valid. But it is clear that logic has nothing to do with the question of whether our world is really of this kind or not.
Russell 1919
Russell 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, [etc]". So what he does next 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:- "I do not see any reason to believe that the axiom of reducibility is logically necessary, which is what would be meant by saying that it is true in all possible worlds. The admission of this axiom into a system of logic is therefore a defect . . . a dubious assumption." (p. 155)
The goal that he sets for himself then is "adjustments to his theory" of avoiding classes:
- "uts reduction of propositions nominally about classes to propositions about their defining functions. The avoidance of classes as entities by this method must, it would be seem, be sound in principle, however the detail may still require adjustment . . ." (p. 155).
Russell 1927
In his 1927 Introduction to the second edition of Principia Mathematica Russell criticises his own axiom:- "One point in regard to which improvement is obviously desirable is the axiom of reducibility (*12.1.11). This axiom has a purely pragmatic justification: it leads to the desired results, and to no others. But clearly it is not the sort of axiom with which we can rest content. On this subject, however, it cannot be said that a satisfactory solution is as yet obtainable. . . . There is another course recommended by Wittgenstein† [† Tractatus Logico-Philosophicus, *5.54ff] for philosophical reasons. This is to assume that functions of propositions are always truth-functions, and that a function can only occur as in a proposition through its values. There are difficulties . . . It involves the consequence that all functions of functions are extensional. . . . [But the consequences of his logic are that] the theory of infinite Dedekindian and well-ordering collapses, so that irrationals, and real numbers generally, can no longer be adequately dealt with. Also Cantor's proof that 2n > n breaks down unless n is finite Perhaps some further axiom, less objectionable than the axiom of reducibility, might give these results, but we have not succeeded in finding such an axiom.
Wittgenstein's 5.54ff has more to do with the notion of function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
but is worth repeating for context:
- 5.54
- In the general propositional form, propositions occur in a proposition only as bases of the truth-operations.
- 5.541
- At first sight it appears as if there were also a different way in which one proposition could occur in another. ¶ Especially in certain propositional forms of psychology, like "A thinks, that p is the case," or "A thinks p," etc. ¶ Here it appears superficially as if the proposition p stood to the object A in a kind of relation. ¶ (And in modern epistemology [Russell, Moore, etc.] those propositions have been conceived in this way.)
- 5.542
- But it is clear that "A believes that p, "A thinks p", "A says p", are of the form " ' p ' thinks p "; and here we have no coordination of a fact and an object, but a coordination of facts by means of a coordination of their objects.
- 5.5421 [etc: "A composite soul would not be a soul any longer."]
- 5.5422
- The correct explanation of the form of the proposition "A judges p" must show that it is impossible to judge a nonsense. (Russell's theory does not satisfy this condition).
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 utter nonsense, because per 5.542 the utterance does not specify anything.
von Neumann 1925
John von Neumann in his 1925 An axiomatization of set theory wrestled with the same issues as did Russell, Zermelo, Skolem, and Fraenkel. He summarily rejected the effort of Russell:- "Here Russell, J. Konig, Weyl, and Brouwer must be mentioned. They arrived at entirely different results [from the set theorists], but the over-all effect of their activity seems to me outright devastating. In Russell, all of mathematics and set theory seems to rest upon the highly problematic "axiom of reducibility", while Weyl and Brouwer systematically reject the larger part of mathematics and set theory as completely meaningless"
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 [of set theory] are to be formulated in such a way that all the desired theorems of Cantor's set theory follow from them, but not the antinomies. In these axiomatizations, however, we can never be perfectly sure of the latter point. We see only that the known modes of inference leading to the antinomies fail, but who knows whether there are not others?
While he mentions the efforts of David Hilbert
David Hilbert
David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
to prove the consistency of his axiomatization 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 [durch 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 axiomatize 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 HilbertDavid Hilbert
David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
's axiomatic system (see more at Hilbert system) 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
Peano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are a set of axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano...
in 4 axioms including mathematical induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
, 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
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
rests.
Ramsey 1925
In 1925 Frank Plumpton Ramsey argued that it is not needed . However in the second edition of Principia MathematicaPrincipia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by 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 could not be proved using Ramsey's approach. Most later mathematical formalisms (Hilbert's Formalism
Formalism (mathematics)
In foundations of mathematics, philosophy of mathematics, and philosophy of logic, formalism is a theory that holds that statements of mathematics and logic can be thought of as statements about the consequences of certain string manipulation rules....
or Brower
Brower
Brower is a surname, and may refer to:* Brittany Brower* Charles H. Brower American advertising executive, copywriter, and author.* Charles N. Brower American judge* David R...
's Intuitionism
Intuitionism
In the philosophy of mathematics, intuitionism, or neointuitionism , is an approach to mathematics as the constructive mental activity of humans. That is, mathematics does not consist of analytic activities wherein deep properties of existence are revealed and applied...
for example) do not use it.
Ramsey showed that you can reformulate the definition of predicative by using the definitions in Wittgenstein's Tractatus Logico-Philosophicus
Tractatus Logico-Philosophicus
The Tractatus Logico-Philosophicus is the only book-length philosophical work published by the Austrian philosopher Ludwig Wittgenstein in his lifetime. It was an ambitious project: to identify the relationship between language and reality and to define the limits of science...
. 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ödelKurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
in his 1944 Russell's mathematical logic offers in the words of his commentator Charles Parsons, "[what] might be seen as a defense of these [realist] attitudes 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). But 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 favor 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 . . . [i.e.] the higher types and orders are solely a facon 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 = a1 V x = a2 V . . . V x = ak" [example on page 134]
And 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:
- "Even the theory of integers is non-analytic, provided that one requires of the rules of elmination that they allow one actually to carry out the elmination in a finite number of steps in each case.44. (44Because this would imply the existence of a decision procedure for all arithmetical propositions. Cf. Turing 1937.) . . . [Thus] the whole of mathematics as applied to sentences of infinite length has to be presupposed in order to prove [the] analyticity [of the theory of integers], e.g., the axiom of choice can be proved to be analytic only if is assumed to be true." (p. 139)
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)
In conclusion Gödel proposed that one should take a "more conservative approach": "make the meaning of the terms "class" and "concept" clearer, and to set up a consistent theory of classes and concepts as objectively existing entities. This is the course which the actual development of amthematical logic has been taking . . . Major among the attempts in this direction . . . are the simple theory of types . . . and axiomatic set theory, both of which have been successful at least to this extent, that they permit the derivation of modern mathematics and at the same time avoid all known paradoxes. Many symptoms show only too clearly, however, that the primitive concepts need further elucidation." (p. 140)
W. V. Quine in van Heijenoort 1967
In a damning critique that also discusses the pros and cons of Ramsey (1931) Quine calls Russell's formulation of "types" to be "troublesome . . . the confusion persists as he attempts to define "nth order propositions". . . the method is indeed oddly devious . . . the axiom of reducibility is self-effacing", etc..Like Kleene (see below) Quine observes that Ramsey (1926), (1931) 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 damning 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".
Stephen Kleene 1952
In his section §12. First inferences from the paradoxes, subchapter "LOGICISM" Kleene 1952 traces the development of Russell's theory of types:- "To adapt the logicistic [sic] construction of mathematics to the situation arising from the discovery of the paradoxes, Russell excluded impredicative definitions by his ramified theory of types (1908, 1910)".
Kleene observes that "to exclude impredicative definitions within a type, the types above type 0 [primary objects or individuals "not subjected to logical analysis"] are further separated into orders. Thus for type 1 [properties of individuals, i.e. logical results of the propositional calculus
Propositional calculus
In mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...
], 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)".
But Kleene parenthetically observes that "the logicistic definition of natural number now becomes predicative when the [property] P in it is specified to range only over properties of a given order; in [this] 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 [see Kleene’s example at Impredicativity] contains 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 quoting from Whitehead and Russell's introduction to their 1927 2nd edition of Principia Mathematica.
Kleene references 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".