Editing Logicism (section)

== The unit class, impredicativity, and the vicious circle principle ==
Suppose a librarian wants to index her collection into a single book (call it Ι for "index"). Her index will list all the books and their locations in the library. As it turns out, there are only three books, and these have titles Ά, β, and Γ. To form her index I, she goes out and buys a book of 200 blank pages and labels it "I". Now she has four books: I, Ά, β, and Γ. Her task is not difficult. When completed, the contents of her index I are 4 pages, each with a unique title and unique location (each entry abbreviated as Title.Location<sub>T</sub>):
: I = { I.L<sub>I</sub>, Ά.L<sub>Ά</sub>, β.L<sub>β</sub>, Γ.L<sub>Γ</sub>}.

This sort of definition of I was deemed by [[Henri Poincaré|Poincaré]] to be "[[impredicative]]". He seems to have considered that only predicative definitions can be allowed in mathematics:
:"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".<ref>Zermelo 1908 in van Heijenoort 1967:190. See the discussion of this very quotation in Mancosu 1998:68.</ref>

By Poincaré's definition, the librarian's index book is "impredicative" because the definition of I is dependent upon the definition of the totality I, Ά, β, and Γ. As noted below, some commentators insist that [[impredicativity]] in commonsense versions is harmless, but as the examples show below there are versions which are not harmless. In response to these difficulties, Russell advocated a strong prohibition, his "vicious circle principle":
:"No totality can contain members definable only in terms of this totality, or members involving or presupposing this totality" (vicious circle principle)" (Gödel 1944 appearing in ''Collected Works Vol. II'' 1990:125).<ref>This same definition appears also in Kleene 1952:42.</ref>
To illustrate what a pernicious instance of impredicativity might be, consider the consequence of inputting argument α into the [[Function (mathematics)|function]] f with output ω = 1−α. This may be seen as the equivalent [[Boolean logic|'algebraic-logic']] expression to the 'symbolic-logic' expression ω = [[negation|NOT]]-α, with truth values 1 and 0. When input α = 0, output ω = 1; when input α = 1, output ω = 0.

To make the function "impredicative", identify the input with the output, yielding α = 1−α

Within the algebra of, say, rational numbers the equation is satisfied when α = 0.5. But within, for instance, a Boolean algebra, where only "truth values" 0 and 1 are permitted, then the equality ''cannot'' be satisfied.

Some of the difficulties in the logicist programme may derive from the α = NOT-α paradox<ref> One source for more detail is Fairouz Kamareddine, Twan Laan and Rob Nderpelt, 2004, ''A Modern Perspective on Type Theory, From its Origins Until Today'', Kluwer Academic Publishers, Dordrecht, The Netherlands, ISBN. They give a demonstration of how to create the paradox (pages 1–2), as follows: Define an aggregate/class/set y this way: ∃y∀x[x ε y ↔ Φ(x)]. (This says: There exists a class y such that for ''ANY'' input x, x is an element of set y if and only if x satisfies the given function Φ.) Note that (i) input x is unrestricted as to the "type" of thing that it can be (it can be a thing, or a class), and (ii) function Φ is unrestricted as well. Pick the following tricky function Φ(x) = ¬(x ε x). (This says: Φ(x) is satisfied when x is NOT an element of x)). Because y (a class) is also "unrestricted" we can plug "y" in as input: ∃y[y ε y ↔ ¬(y ε y)]. This says that "there exists a class y that is an element of itself only if it is NOT and element of itself. That is the paradox.</ref> Russell discovered in Frege's 1879 ''Begriffsschrift''<ref>Russell's letter to Frege announcing the "discovery", and Frege's letter back to Russell in sad response, together with commentary, can be found in van Heijenoort 1967:124-128. Zermelo in his 1908 claimed priority to the discovery; cf. footnote 9 on page 191 in van Heijenoort.</ref> that Frege had allowed a function to derive its input "functional" (value of its variable) not only from an object (thing, term), but also from the function's own output.<ref>van Heijenoort 1967:3 and pages 124-128</ref>

As described above, Both Frege's and Russell's constructions of the natural numbers begin with the formation of equinumerous classes of classes ("bundles"), followed by an assignment of a unique "numeral" to each bundle, and then by the placing of the bundles into an order via a relation ''S'' that is asymmetric: ''x S y'' ≠ ''y S x''. But Frege, unlike Russell, allowed the class of unit classes to be identified as a unit itself:

But, since the class with numeral 1 is a single object or unit in its own right, it too must be included in the class of unit classes. This inclusion results in an [[infinite regress]] of increasing type and increasing content.

Russell avoided this problem by declaring a class to be more or a "fiction". By this he meant that a class could designate only those elements that satisfied its propositional function and nothing else. As a "fiction" a class cannot be considered to be a thing: an entity, a "term", a singularity, a "unit". It is an ''assemblage'' but is not in Russell's view "worthy of thing-hood":
:"The class as many . . . is unobjectionable, but is many and not one. We may, if we choose, represent this by a single symbol: thus ''x'' ε ''u'' will mean "''x'' is one of the ''u''{{'}}s." This must not be taken as a relation of two terms, ''x'' and ''u'', because ''u'' as the numerical conjunction is not a single term . . . Thus a class of classes will be many many's; its constituents will each be only many, and cannot therefore in any sense, one might suppose, be single constituents.[etc]" (1903:516).

This supposes that "at the bottom" every single solitary "term" can be listed (specified by a "predicative" predicate) for any class, for any class of classes, for class of classes of classes, etc, but it introduces a new problem—a hierarchy of "types" of classes.

===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).

===Gödel's criticism and suggestions===
Gödel, in his 1944 work, identifies the place where he considers Russell's logicism to fail and offers suggestions to rectify the problems. He submits the "vicious circle principle" to re-examination, splitting it into three parts "definable only in terms of", "involving" and "presupposing". It is the first part that "makes impredicative definitions impossible and thereby destroys the derivation of mathematics from logic, effected by Dedekind and Frege, and a good deal of mathematics itself". Since, he argues, mathematics sees to rely on its inherent impredicativities (e.g. "real numbers defined by reference to all real numbers"), he concludes that what he has offered is "a proof that the vicious circle principle is false [rather] than that classical mathematics is false" (all quotes Gödel 1944:127).

'''Russell's no-class theory is the root of the problem''': Gödel believes that impredicativity is not "absurd", as it appears throughout mathematics. Russell's problem derives from his "constructivistic (or nominalistic"<ref>Perry observes that Plato and Russell are "enthusiastic" about "universals", then in the next sentence writes: " 'Nominalists' think that all that particulars really have in common are the words we apply to them" (Perry in his 1997 Introduction to Russell 1912:xi). Perry adds that while your sweatshirt and mine are different objects generalized by the word "sweatshirt", you have a relation to yours and I have a relation to mine. And Russell "treated relations on par with other universals" (p. xii). But Gödel is saying that Russell's "no-class" theory denies the numbers the status of "universals".</ref>) standpoint toward the objects of logic and mathematics, in particular toward propositions, classes, and notions . . . a notion being a symbol . . . so that a separate object denoted by the symbol appears as a mere fiction" (p.&nbsp;128).

Indeed, Russell's "no class" theory, Gödel concludes:
:"is of great interest as one of the few examples, carried out in detail, of the tendency to eliminate assumptions about the existence of objects outside the "data" and to replace them by constructions on the basis of these data<sup>33</sup>. The "data" are to understand in a relative sense here; i.e. in our case as logic without the assumption of the existence of classes and concepts]. The result has been in this case essentially negative; i.e. the classes and concepts introduced in this way do not have all the properties required from their use in mathematics. . . . All this is only a verification of the view defended above that logic and mathematics (just as physics) are built up on axioms with a real content which cannot be explained away" (p. 132)

He concludes his essay with the following suggestions and observations:
:"One should take a more conservative course, such as would consist in trying to make the meaning of 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 mathematical logic has been taking and which Russell himself has been forced to enter upon in the more constructive parts of his work. Major among the attempts in this direction . . . are the simple [[type theory|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 . . . ¶ It seems reasonable to suspect that it is this incomplete understanding of the foundations which is responsible for the fact that mathematical logic has up to now remained so far behind the high expectations of Peano and others . . .." (p. 140)