Saturday 26 March 2011

History

1900 - 1927

Origin of Russell's Theory of Types: In a letter to Gottlob Frege (1902) Russell announced his discovery of the paradox in Frege's Begriffsschrift[8]. Frege promptly responded, acknowledging the problem and proposing a solution in a technical discussion of "levels". To quote Frege: "Incidentally, it seems to me that the expression "a predicate is predicated of itself" is not exact. A predicate is as a rule a first-level function, and this function requires an object as argument and cannot have itself as argument (subject). Therefore I would prefer to say "a concept is predicated of its own extension"[9]. He goes about showing how this might work but seems to pull back from it. (In a footnote, van Heijenoort notes that in Frege 1893 Frege had used a symbol (horseshoe) "for reducing second-level functions to first-level functions"[10]). As a consequence of what has become known as Russell's paradox both Frege and Russell had to quickly emend works that they had at the printers. In an Appendix B that Russell tacked on to his 1903 Principles of Mathematics one finds his "tentative" "theory of types"[11].

The matter plagued Russell for about five years (1903–1908). Willard Quine in his preface to Russell's (1908a) Mathematical logic as based on the theory of types[12] presents a historical synopsis of the origin of the theory of types and the "ramified" theory of types: Russell proposed in turn a number of alternatives: (i) abandoning the theory of types (1905) followed by three theories in 1905: (ii.1) the zigzag theory, (ii.2) theory of limitation of size, (ii.3) the no-class theory (1905–1906), then (iii) readopting the theory of types (1908ff)".

Quine observes that Russell's introduction of the notion of "apparent variable" had the following result: "the distinction between 'all' and 'any': 'all' is expressed by the bound ('apparent') variable of universal quantification, which ranges over a type, and 'any' is expressed by the free ('real') variable which refers schematically to any unspecified thing irrespective of type". Quine dismisses this notion of "bound variable" as "pointless apart from a certain aspect of the theory of types"[13].
The 1908 "ramified" theory of types

Quine explains the ramified theory as follows: "It has been so called because the type of a function depends both on the types of its arguments and on the types of the apparent variables contained in it (or in its expresion), in case these exceed the types of the arguments"[14]. Stephen Kleene in his 1952 Introduction to Metamathematics describes the ramified theory of types this way:

    The primary objects or individuals (i.e. the given things not being subjected to logical analysis) are assigned to one type (say type 0), the properties of individuals to type 1, properties of properties of individuals to type 2, etc.; and no properties are admitted which do not fall into one of these logical types (e.g. this puts the properties 'predicable' and 'impredicable' ... outside the pale of logic). A more detailed account would describe the admitted types for other objects as relations and classes. Then to exclude impredicative definitions within a type, the types above type 0 are further separated into orders. Thus for type 1, properties defined without mentioning any totality belong to order 0, and properties defined using the totality of properties of a given order belong to the next higher order. ... But this separation into orders makes it impossible to construct the familiar analysis, which we saw above contains impredicative definitions. To escape this outcome, Russell postulated his axiom of reducibility, which asserts that to any property belonging to an order above the lowest, there is a coextensive property (i.e. one possessed by exactly the same objects) of order 0. If only definable properties are considered to exist, then the axiom means that to every impredicative definition within a given type there is an equivalent predicative one (Kleene 1952:44-45).

The axiom of reducibility and the notion of "matrix"

But because the stipulations of the ramified theory would prove (to quote Quine) "onerous", Russell in his 1908 Mathematical logic as based on the theory of types[15] also would propose his axiom of reducibility. By 1910 Whitehead and Russell in their Principia Mathematica would further augment this axiom with the notion of a matrix -- a fully-extensional specification of a function. From its matrix a function could be derived by the process of "generalization" and vice versa, i.e. the two processes are reversible -- (i) generalization from a matrix to a function ( by use apparent variables ) and (ii) the reverse process of reduction of type by courses-of-values substitution of arguments for the apparent variable. By this method impredicativity could be avoided[16].
Truth tables

Eventually Emil Post (1921) would lay waste to Russell's "cumbersome"[17] Theory of Types with his "truth functions" and their truth tables. In his "Introduction" to his 1921 Post places the blame on Russell's notion of apparent variable: "Whereas the complete theory [of Whitehead and Russell (1910, 1912, 1913)] requires for the enunciation of its propositions real and apparent variables, which represent both individuals and propositional functions of different kinds, and as a result necessitates the cumbersome theory of types, this subtheory uses only real variables, and these real variables represent but one kind of entity, which the authors have chosen to call elementary propositions".

At about the same time Ludwig Wittgenstein made short work of the theory of types in his 1922 work Tractatus Logico-Philosophicus in which he points out the following in parts 3.331–3.333:

    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 meanings of his signs.

    3.332 No proposition can say anything about itself, because the propositional 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...

Wittgenstein proposed the truth-table method as well. In his 4.3 through 5.101, Wittgenstein adopts an unbounded Sheffer stroke as his fundamental logical entity and then lists all 16 functions of two variables (5.101).

The notion of matrix-as-truth-table appears as late as the 1940-1950's in the work of Tarski, e.g. his 1946 indexes "Matrix, see: Truth table"[18]
Russell's doubts

Russell in his 1920 Introduction to Mathematical Philosophy devotes an entire chapter to "The axiom of Infinity and logical types" wherein he states his concerns: "Now the theory of types emphatically does not belong to the finished and certain part of our subject: much of this theory is still inchoate, confused, and obscure. But the need of some doctrine of types is less doubtful than the precise form the doctrine should take; and in connection with the axiom of infinity it is particularly easy to see the necessity of some such doctrine"[19].

Russell abandons the axiom of reducibility: In the second edition of Principia Mathematica (1927) he acknowledges Wittgenstein's argument[20]. At the outset of his Introduction he declares "there can be no doubt ... that there is no need of the distinction between real and apparent variables..."[21]. Now he fully embraces the matrix notion and declares "A function can only appear in a matrix through its values" (but demurs in a footnote: "It takes the place (not quite adequately) of the axiom of reducibility"[22]). Furthermore, he introduces a new (abbreviated, generalized) notion of "matrix", that of a "logical matrix . . . one that contains no constants. Thus p|q is a logical matrix"[23]. Thus Russell has virtually abandoned the axiom of reducibility[24], but in his last paragraphs he states that from "our present primitive propositions" he cannot derive "Dedekindian relations and well-ordered relations" and observes that if there is a new axiom to replace the axiom of reducibility "it remains to be discovered"

No comments:

Post a Comment