Editing Logicism (section)

===A solution to impredicativity: a hierarchy of types===
Gödel 1944:131 observes that "Russell adduces two reasons against the extensional view of classes, namely the existence of (1) the null class, which cannot very well be a collection, and (2) the unit classes, which would have to be identical with their single elements." He suggests that Russell should have regarded these as fictitious, but not derive the further conclusion that ''all'' classes (such as the class-of-classes that define the numbers 2, 3, etc) are fictions.

But Russell did not do this. After a detailed analysis in Appendix A: ''The Logical and Arithmetical Doctrines of Frege'' in his 1903, Russell concludes:
:"The logical doctrine which is thus forced upon us is this: The subject of a proposition may be not a single term, but essentially many terms; this is the case with all propositions asserting numbers other than 0 and 1" (1903:516).

In the following notice the wording "the class as many"—a class is an aggregate of those terms (things) that satisfy the propositional function, but a class is not a [[thing-in-itself]]:
:"Thus the final conclusion is, that the correct theory of classes is even more extensional than that of Chapter VI; that the class as many is the only object always defined by a propositional function, and that this is adequate for formal purposes" (1903:518).

It is as if a rancher were to round up all his livestock (sheep, cows and horses) into three fictitious corrals (one for the sheep, one for the cows, and one for the horses) that are located in his fictitious ranch. What actually exist are the sheep, the cows and the horses (the extensions), but not the fictitious "concepts" corrals and ranch.{{or|date=May 2019}}

When Russell proclaimed ''all'' classes are useful fictions he solved the problem of the "unit" class, but the ''overall'' problem did not go away; rather, it arrived in a new form: "It will now be necessary to distinguish (1) terms, (2) classes, (3) classes of classes, and so on ''ad infinitum''; we shall have to hold that no member of one set is a member of any other set, and that ''x'' ε ''u'' requires that ''x'' should be of a set of a degree lower by one than the set to which ''u'' belongs. Thus ''x'' ε ''x''  will become a meaningless proposition; and in this way the contradiction is avoided" (1903:517).

This is Russell's "doctrine of types". To guarantee that impredicative expressions such as ''x'' ε ''x'' can be treated in his logic, Russell proposed, as a kind of working hypothesis, that all such impredicative definitions have predicative definitions. This supposition requires the notions of function-"orders" and argument-"types". First, functions (and their classes-as-extensions, i.e. "matrices") are to be classified by their "order", where functions of individuals are of order 1, functions of functions (classes of classes) are of order 2, and so forth. Next, he defines the "type" of a function's arguments (the function's "inputs") to be their "range of significance", i.e. what are those inputs ''α'' (individuals? classes? classes-of-classes? etc.) that, when plugged into ''f''(''x''), yield a meaningful output ω. Note that this means that a "type" can be of mixed order, as the following example shows:
:"Joe DiMaggio and the Yankees won the 1947 World Series".
This sentence can be decomposed into two clauses: "''x'' won the 1947 World Series" + "''y'' won the 1947 World Series". The first sentence takes for ''x'' an individual "Joe DiMaggio" as its input, the other takes for ''y'' an aggregate "Yankees" as its input. Thus the composite-sentence has a (mixed) type of 2, mixed as to order (1 and 2).

By "predicative", Russell meant that the function must be of an order higher than the "type" of its variable(s). Thus a function (of order 2) that creates a class of classes can only entertain arguments for its variable(s) that are classes (type 1) and individuals (type 0), as these are lower types. Type 3 can only entertain types 2, 1 or 0, and so forth. But these types can be mixed (for example, for this sentence to be (sort of) true: "''z'' won the 1947 World Series" could accept the individual (type 0) "Joe DiMaggio" and/or the names of his other teammates, ''and'' it could accept the class (type 1) of individual players "The Yankees".

The ''[[axiom of reducibility]]'' is the hypothesis that ''any'' function of ''any'' order can be reduced to (or replaced by) an equivalent ''predicative'' function of the appropriate order.<ref>"The axiom of reducibility is the assumption that, given any function φẑ, there is a formally equivalent, ''predicative'' function, i.e. there is a predicative function which is true when φz is true and false when φz is false. In symbols, the axiom is: ⊦ :(∃ψ) : φz. ≡<sub>z</sub> .ψ!z." (''PM'' 1913/1962 edition:56, the original uses x with a circumflex). Here φẑ indicates the function with variable ẑ, i.e. φ(x) where x is argument "z"; φz indicates the value of the function given argument "z"; ≡<sub>z</sub> indicates "equivalence for all z"; ψ!z indicates a predicative function, i.e. one with no variables except individuals.</ref> A careful reading of the first edition indicates that an ''n''th order predicative function need not be expressed "all the way down" as a huge "matrix" or aggregate of individual atomic propositions. "For in practice only the ''relative'' types of variables are relevant; thus the lowest type occurring in a given context may be called that of individuals" (p. 161). But the axiom of reducibility proposes that ''in theory'' a reduction "all the way down" is possible.

By the 2nd edition of ''PM'' of 1927, though, Russell had given up on the axiom of reducibility and concluded he would indeed force any order of function "all the way down" to its elementary propositions, linked together with logical operators:
:"All propositions, of whatever order, are derived from a matrix composed of elementary propositions combined by means of the stroke" (''PM'' 1927 Appendix A, p. 385)
(The "stroke" is ''[[Sheffer's stroke]]'' – adopted for the 2nd edition of PM – a single two argument logical function from which all other logical functions may be defined.)

The net result, though, was a collapse of his theory. Russell arrived at this disheartening conclusion: that "the theory of ordinals and cardinals survives . . . but [[irrational number|irrationals]], and real numbers generally, can no longer be adequately dealt with. . . . 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" (''PM'' 1927:xiv).

Gödel 1944 agrees that Russell's logicist project was stymied; he seems to disagree that even the integers survived:
:"[In the second edition] The axiom of reducibility is dropped, and it is stated explicitly that all primitive predicates belong to the lowest type and that the only purpose of variables (and evidently also of constants) of higher orders and types is to make it possible to assert more complicated truth-functions of atomic propositions" (Gödel 1944 in ''Collected Works'':134).

Gödel asserts, however, that this procedure seems to presuppose arithmetic in some form or other (p.&nbsp;134). He deduces that "one obtains integers of different orders" (p.&nbsp;134-135); the proof in Russell 1927 ''PM'' Appendix B that "the integers of any order higher than 5 are the same as those of order 5" is "not conclusive" and "the question whether (or to what extent) the theory of integers can be obtained on the basis of the ramified hierarchy [classes plus types] must be considered as unsolved at the present time". Gödel concluded that it wouldn't matter anyway because propositional functions of order ''n'' (any ''n'') must be described by finite combinations of symbols (all quotes and content derived from page 135).