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.
History With Russell's discovery (1901, 1902)According to van Heijenoort 1967:124, Russell discovered the paradox in June 1901. van Heijenoort in turn references Bertrand Russell (1944) "My mental development" in The philosophy of Bertrand Russell, edited by Paul Arthur Schilpp (Tudor, New York), page 13. But Russell did not report it to Frege until his letter to Frege dated 16 June 1902. Livio 2009:186 reports the same date. Livio 2009:191 writes that Zermelo discovered the paradox as early as 1900, but does not give his source for this (Ewald 1996?). Indeed, Zermelo makes this claim in a footnote 9 to his 1908 A new proof of the possibility of a well-ordering in van Heijenoort 1967:191. of a paradox in Gottlob Frege's 1893 Grundgesetze der Arithmetik 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.Cf. Introductory remarks by W. V. O. Quine preceding Bertrand Russell (1908a) reprinted in van Heijenoort 1967:150. This contradiction can be stated as "the class of all classes that do not contain themselves as elements".Cf. Introductory remarks by W. V. O. Quine preceding Bertrand Russell (1908a) reprinted in van Heijenoort 1967:150. 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..."Russell 1903:528
By the time of his 1908 Mathematical logic as based on the theory of typesreprinted in van Heijenoort 150–182 Russell had studied "the contradictions" (among them the Epimenides paradox, the Burali-Forti paradox, 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".Russell 1908:154. The exact wording appears in Whitehead and Russell 1913 reprinted to *53 1962:60
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 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."Whitehead and Russell 1913 reprinted to *53 1962:53
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 [to 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) can be expressed by a formally equivalent predicative truth function. It made 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.Cf. commentary by W. V. O. Quine in van Heijenoort 1967:150–152 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 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 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".Whitehead and Russell 1913:162 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",Russell 1903:99 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".Russell 1903:99 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 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 [set] of ordered couples".Wiener 1914 in van Heijenoort 1967:226 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."Wiener in van Heijenoort 1967:224 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.Wiener 1914 in van Heijenoort 1967:224
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."Wittgenstein 1922 in HarperCollins 2009:4 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; 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 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]". 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:Zermelo stipulates that there exist "a domain B of objects, among which are the sets." But by a theorem Zermelo proves that this domain B cannot be a set itself "and this disposes of the Russell antinomy so far as we are concerned." (Cf. Zermelo 1908 in van Heijenoort 1967:203.) The ultimate problem (to be answered by Skolem and Fraenkel ) is a precise definition of Zermelo's notion of definite property which, via Zermelo's Axiom of separation (Axiom der Aussonderung), when applied via a propositional function to a set M, separates from M a subset e.g. M1 (Skolem 1922 in van Heijenoort 1967:292).
While Skolem is mainly addressing a problem with Zermelo's set theory, he does make this observation about the axiom of reducibility:
Russell 1927