Frege's Logic, Theorem, and Foundations for Arithmetic (Stanford Encyclopedia of Philosophy) Cite this entry Search the SEP • Advanced Search • Tools • RSS FeedTable of Contents• What's New• Archives• Projected ContentsEditorial Information• About the SEP• Editorial Board• How to Cite the SEP• Special CharactersSupport the SEPContact the SEP ©Metaphysics Research Lab,CSLI,Stanford University  Open access to the SEP is made possible by a world-wide funding initiative. Please Read How You Can Help Keep the Encyclopedia FreeFrege's Logic, Theorem, and Foundations for ArithmeticFirst published Wed Jun 10, 1998; substantive revision Sun Apr 6, 2008Frege formulated two distinguished formal systems and used thesesystems in his attempt both to express certain basic concepts ofmathematics precisely and to derive certain mathematical laws from thelaws of logic. In his Begriffsschrift of 1879, he developed asecond-order predicate calculus and used it both to define interestingmathematical concepts and to state and prove mathematically interestingpropositions. However, in his Grundgesetze der Arithmetik of1893/1903, Frege added (as an axiom) what he thought was adistinguished logical proposition (Basic Law V) and tried to derive thefundamental theorems of various mathematical (number) systems from thisproposition. Unfortunately, not only did Basic Law V fail to be alogical proposition, but the resulting system proved to beinconsistent, for it was subject to Russell's Paradox. Although the inconsistency in Frege's Grundgesetze iswidely known, it is not very well known that a deep theoreticalaccomplishment can be extracted from his work. TheGrundgesetze contains all the essential steps of a valid proof(in second-order logic) of the fundamental propositions of arithmeticfrom a single consistent principle. This consistent principle, known inthe literature as "Hume's Principle", asserts that for any conceptsF and G, the number of F-things is equal tothe number G-things if and only if there is a one-to-onecorrespondence between the F-things and the G-things.In the Grundgesetze, Frege used Basic Law V to derive Hume'sPrinciple, but the derivations of the fundamental propositions ofarithmetic from Hume's Principle do not essentially require Basic LawV. So by setting aside the derivation of Hume's Principle from theinconsistent Basic Law V and focusing on Frege's proofs of the basicpropositions of arithmetic, his theoretical accomplishment emerges muchmore clearly, for his work shows us how to prove the Dedekind/Peanoaxioms for number theory from Hume's Principle in second-order logic.This achievement, which involves some remarkably subtle chains ofdefinitions and logical reasoning, has become known as Frege's Theorem.[See Boolos (1990), p. 268.]The principal goals of this essay are: (1) to review in some detailthe essential features of Frege's logical systems, (2) to work throughthe derivations involved in Frege's Theorem, and (3) to frame the mostimportant philosophical questions that arise in connection with thistheorem. In addition, we hope to prepare students of Frege to read hisoriginal work (in translation) and to prepare the reader to understanda number of excellent articles in the secondary literature on Frege'swork.To accomplish these goals, we presuppose only a familiarity with thefirst-order predicate calculus. We show how to extend this language andlogic to include the most salient features of Frege's second-orderpredicate calculus, his theory of concepts, and his theory ofextensions. Our discussion will be largely based upon material drawnfrom Frege's three principal published works:Begriffsschrift, eine der arithmetischen nachgebildeteFormelsprache des reinen Denkens, Halle a. S.: Louis Nebert, 1879;translation by S. Bauer Mengelberg as Concept Notation: A formulalanguage of pure thought, modelled upon that of arithmetic, in J.van Heijenoort, From Frege to Gödel: A Sourcebook inMathematical Logic, 1879-1931, Cambridge, MA: Harvard UniversityPressDie Grundlagen der Arithmetik: eine logisch-mathematischeUntersuchung über den Begriff der Zahl, Breslau: w. Koebner,1884; translated by J. L. Austin as The Foundations of Arithmetic:A Logic-Mathematical Enquiry into the Concept of Number, Oxford:Blackwell, second revised edition, 1974.Grundgesetze der Arithmetik, Band I/II, Jena: VerlagHerman Pohle, 1893/1903; partial translation by M. Furth as TheBasic Laws of Arithmetic, Berkeley: U. California Press, 1964.Volumes I/II)We will refer to these works with boldfaced abbreviations of theirGerman titles: Begr, Gl andGg I/II, respectively. Those readersalready familiar with parts of Frege's texts may wish to skip thediscussion of that material. 1. Frege's Predicate Calculus and Theory of Concepts 1.1 The Language1.2 The Logic1.3 The Rule of Substitution1.4 The Theory of Concepts2. Frege's Theory of Extensions: Basic Law V 2.1 Notation for Courses-of-Values of Functions2.2 Notation for Extensions of Concepts2.3 Membership in an Extension2.4 Basic Law V for Concepts2.5 First Derivation of the Contradiction2.6 Second Derivation of the Contradiction2.7 How the Paradox is Engendered3. Frege's Analysis of Cardinal Numbers 3.1 Equinumerosity3.2 Contextual Definition of ‘The Number of Fs’: Hume's Principle3.3 Explicit Definition of ‘The Number of Fs’3.4 Derivation of Hume's Principle4. Frege's Analysis of Predecessor, Ancestrals, and the Natural Numbers 4.1 Predecessor4.2 The Ancestral of Relation R4.3 The Weak Ancestral of R4.4 The Concept Natural Number5. Frege's Theorem 5.1 Zero is a Number5.2 Zero Isn't the Successor of Any Number5.3 No Two Numbers Have the Same Successor5.4 The Principle of Mathematical Induction5.5 Every Number Has a Successor5.6 Arithmetic6. Philosophical Questions Surrounding Frege's Theorem 6.1 Frege's Goals and Strategy in His Own Words6.2 The Basic Problem for Frege's Strategy6.3 The Existence of Concepts6.4 The Existence of Extensions6.5 The Existence of Numbers and Truth-Values: The Julius Caesar Problem6.6 Final ObservationsBibliographyOther Internet ResourcesRelated Entries1. Frege's Predicate Calculus and Theory of ConceptsIn this section, we describe the language and logic of Frege'spredicate calculus. We explain his function-argument analysis of atomicsentences and his definition of concepts in terms of functions, giveexamples of his ‘concept script’, and discuss the Rule ofSubstitution in his logic. We also show how Frege's Rule ofSubstitution corresponds to a comprehension principle for concepts insecond-order logic, and we introduce and explain λ-notation tohelp us distinguish open formulas and complex names of concepts.Readers who are already familiar with these ideas may wish to skipahead to Section 2.1.1 The LanguageIn Begr, Frege invented the predicate calculus. Itwill soon become clear that the language and logic of his predicatecalculus are ‘second-order’. The language included not onlythe variables x,y,z, … ,which range over objects, but also included the variablesƒ,g,h, … , which range overfunctions. Frege rigidly distinguished objects from functionsand so we may think of these variables as ranging over separate,mutually exclusive domains. Frege took functional application‘ƒ(x)’ as the principal operation for formingcomplex names of objects in his language. The expression‘ƒ(x)’ denotes the object to which thefunction ƒ maps the object x. Frege called the objectx the ‘argument’ of the function ƒ and calledƒ(x) the ‘value’ of the function. Since Fregealso recognized two special objects he called truth-values(The True and The False), he defined a concept to be anyfunction that always maps its arguments to truth-values. For example,whereas ‘x2 +3’ and‘father-of(x)’ denote ordinary functions, theexpressions ‘Happy(x)’ and ‘x >5’ denote concepts. The former denotes a concept which maps anyobject that is happy to The True and all other objects to The False;the latter denotes a concept that maps any object that is greater than5 to The True and all other objects to The False. Given that conceptslike being happy and being greater than 5 map theirarguments to truth values, the atomic sentences of Frege's language,such as ‘Happy(b)’ and ‘4 >5’, become names of truth-values.In what follows, we use the symbolsF,G, … as variables ranging overconcepts and we often write ‘Fx’ (instead of‘F(x)’) to express the claim that conceptF maps x to The True. When this claim is true, Fregewould say that x falls under the conceptF.When ƒ is a function of two arguments x and yand ƒ always maps its pair of arguments to a truth value, Fregewould say that ƒ is a relation. We shall use the expression‘Rxy’ (or sometimes‘R(x,y)’) to assert that therelation R maps x and y (in that order) toThe True. In what follows, we shall sometimes write the symbol thatdenotes a mathematical relation in the usual ‘infix’notation; for example, ‘>’ denotes the greater-thanrelation in the expression ‘x >y’.Now that we have explained Frege's analysis of the atomic statements‘Fx’ and ‘Rxy’ familiar tomodern students of logic, we turn next to the more complex statementsof his language. Frege developed his own graphical notation forasserting complex statements involving negations, conditionals, anduniversal quantification. If we ignore the fact that Frege used Gothicletters as variables of quantification, certain letters as boundvariables in names of courses-of-values, and certain other letters asplaceholders in the names of functions, then Frege's notation for thelogical notions ‘not’, ‘if-then’,‘every’ and ‘some’ can be described in thefollowing table: Logical NotionModern NotationFrege-Style NotationIt is not the case that Fx¬Fx If Fx then GyFx → Gy Every x is such that Fx∀xFx Some x is such that Fx¬∀x¬Fx, i.e., ∃xFx Every F is such that Fa∀F Fa Some F is such that Fa¬∀F¬Fa, i.e., ∃F Fa So, for example, whereas a modern logician would symbolize the claim‘All As are Bs’ as: ∀x(Ax →Bx)Frege would symbolize this claim as follows:  However, since Frege's notation was never adopted as a standard, weshall instead use the more familiar modern notation in the remainder ofthis essay. [See Beaney (1997, Appendix 2), Furth (1967), andReck & Awodey (2004, 26–34) for a moredetailed introduction to Frege's notation.] We shall assume that thereader is familiar with the fact that negations(‘¬φ’) and conditionals(‘φ → ψ’) can be used to define theother molecular formulas such as conjunctions(‘φ & ψ’), disjunctions(‘φ v ψ’), and biconditionals(‘φ ≡ ψ’). Moreover, it isimportant to mention that Frege took identity statements of the form‘x = y’ as primitive in his language.Whereas ‘22 = 4’ names The True,‘22 = 3’ names The False. The statement form‘ƒ(x) = y’ plays an important rolein Frege's axioms and definitions. Note finally that since Fregeallowed quantification over both objects and functions, the language ofhis predicate calculus becomes ‘second-order’. 1.2 The LogicFrege's logic consisted of basic axioms and rules of inference thatgoverned the permissible inferences within his system. His axiomsincluded familiar axioms of propositional logic, second-order predicatelogic, and the logic of identity. For example, where φ and ψare any formulas and ‘a’ is any object term and‘P’ is any concept term, then the following wereamong the basic laws of Frege's system: φ → (ψ → φ)(∀xPx) → Pa(∀F Fa) → Paa = b → ∀F(Fa ≡Fb)[Frege's most well-known codification of these laws occurs inGg I, §47; however, the above laws are firstintroduced in Gg I, §§18, 20, 25, and 20,respectively.] We shall simplify our discussion in what follows byassuming that the usual axioms of the modern second-order predicatecalculus apply to Frege's system. These are essentially the same as theaxioms for the first-order predicate calculus, except for the additionof laws for the second-order quantifiers ∀F and∃F which correspond to the laws governing thefirst-order quantifiers ∀x and ∃x. Although these axioms of Frege's logic are familiar to us, the rulesof inference in Frege's system are not as familiar. The reason is thatthe rules govern not only his graphical notation for molecular andquantified formulas, but also his special purpose symbols, such ascertain lowercase letters used as placeholders, certain Gothic letters andletters used as bound variables, and various other signs of his systemwe have not yet mentioned. Since these will play no role in thediscussion that follows, we shall again simplify our discussion byassuming that the usual rules of the modern second-order predicatecalculus apply to Frege's system. Again, these are essentially the sameas the rules for the first-order predicate calculus, except for theaddition of new rules for the second-order quantifiers that correspondto the generalization and instantiation rules (i.e., introduction andelimination rules) for the first-order quantifiers.1.3 The Rule of SubstitutionThere is, however, one distinguished rule of Frege's system that willplay an important role in what follows, namely, his Rule ofSubstitution. For the purposes of this discussion, we may initiallyformulate the rule in the following somewhat simplified manner: Rule of Substitution (Simplified Version): In any statement of the form …Fx… (in which thevariable F is free) which is derivable as a theorem of logic,we may substitute any open formula φ(x) (with the freevariable x) for all the occurrences of the atomic formulaFx in …Fx… .To see this rule in action, first consider the following theorem of(Frege's) second-order predicate logic: (A) ∀x(Fx ≡Fx).Now Frege's Rule of Substitution not only allows us to substitute theatomic formula ‘Ox’ (which might represent theclaim ‘x is odd’) for the formula Fx toderive the true statement ∀x(Ox ≡Ox), but also allows us to substitute complex formulas with afree variable x for ‘Fx’. So, forexample, we are allowed substitute the formula ‘Ox &x > 5’ (‘x is odd and x isgreater than 5’) for ‘Fx’ in (A) to derivethe following from (A): (B) ∀x(Ox & x > 5≡ Ox & x > 5)Inferences such as this will be valid no matter what complex formulawith x free we substitute for Fx in our universalclaim (A). This is what justifies Frege's Rule of Substitution. In what follows, we will assume that the Rule of Substitution can begeneralized to relations, so that we can uniformly replace the formulaRxy (in a theorem of logic with R free) by a complexformula φ(x,y) (in which both x andy are free).1.4 The Theory of ConceptsThe Rule of Substitution has rather powerful consequences. It impliesthat there exists a concept corresponding to every open formula with afree variable x. To see that this is a consequence of therule, note that it follows from (A) by existential generalization that: ∃G∀x(Gx ≡Fx)Frege's Rule of Substitution now allows us to substitute any formulawith free variable x for Fx. In other words, everyinstance of the following Comprehension Principle for Concepts isderivable in Frege's system: Comprehension Principle for Concepts: ∃G∀x(Gx ≡φ(x)), where φ(x) is any formula which has x free andwhich has no free Gs.Similarly, from the theorem of logic: ∀x∀y(Rxy ≡Rxy)one can generalize and then use the Rule of Substitution to derive thefollowing Comprehension Principle for Relations: Comprehension Principle for Relations: ∃R∀x∀y(Rxy≡ φ(x,y)), where φ(x,y) is any formula with x andy free and which has no free Rs.Although Frege didn't explicitly formulate these ComprehensionPrinciples, they constitute a very important generalization about hissystem that reveals its underlying theory of concepts and relations. Wecan see these principles at work if we return to the example usedabove. The following is an instance of the Comprehension Principle forConcepts and so constitutes a theorem of Frege's system: ∃G∀x(Gx ≡Ox & x > 5)This asserts: there exists a concept G such that for everyobject x, x falls under G if and only ifx is odd and greater than 5. We can see, therefore, thatFrege's Rule of Substitution essentially treats an open formula like‘Ox & x > 5’ as if it were a nameof a complex concept. Similarly, the following is an instance of theComprehension Principle for Relations: ∃R∀x∀y(Rxy≡ Ox & x > y)This asserts the existence of a relation that objects x andy bear to one another just in case the complex conditionOx & x > y holds. Logicians nowadays typically distinguish the open formulaφ(x) from the corresponding name of a concept. They usethe notation [λx Ox & x > 5]as the name of the concept being an object x such that x is odd andx is greater than 5 (or, more naturally, ‘being odd andgreater than 5’). The term-forming operator λx(‘being an x such that’) combines with a formulaφ(x) in which x is free to produce[λx φ(x)]. The λ-expression is aname of the concept expressed by the formula. This notation can beextended for relational concepts. The expression: [λxy Ox & x> y] names the 2-place relation being an x and y such that x is odd andgreater than y. So we will use expressions of the more generalform [λxy φ(x,y)] inwhat follows. [The reader should note, however, that we are takingλ-expressions to be complete expressions that denote concepts.But Frege didn't use this notation. By contrast, he thought thatpredicative expressions such as ‘( ) is happy’ areincomplete expressions and that the concepts they denoted wereunsaturated. We shall not discuss Frege's reasons for this inthis entry; see his essay “Concept and Object”.This λ-notation is governed by the following simple logicalprinciple known as λ-Conversion. Let φ(x) be anyformula in which the variable x is free, and letφ(y/x) be the result of substituting the variabley for x everywhere in φ(x). Then theprinciple of λ-Conversion is: λ-Conversion: ∀y([λx φ(x)]y ≡φ(y/x))This asserts that an object y falls under the concept[λx φ(x)] if and only ifφ(y/x) holds. So, using our example, thefollowing is an instance of λ-conversion: ∀y([λx Ox &x > 5]y ≡ Oy & y >5)This asserts that an object y falls under the conceptbeing odd and greater than 5 if and only if y is oddand greater than 5. Note that when the variable y isinstantiated to some object term, the resulting instance ofλ-Conversion is a biconditional. Some logicians call the rule ofinference derived from the right-to-left direction of suchbiconditionals ‘λ-Abstraction’. For example, theinference from O6 & 6 > 5to [λx Ox & x >5]6is justified by λ-Abstraction. The principle of λ-Conversion can be generalized, so that itcovers relations as well: ∀z∀w([λxyφ(x,y)]zw ≡φ(z/x, w/y))The reader should construct an instance of this principle using ourexample [λxy Ox & x >y]. To reiterate, then, Frege's Rule of Substitution allows us toinstantiate φ(x) for the free variable F intheorems of logic as if φ(x) were a λ-expressionand constituted a name of a concept. In what follows, we shall make useof this λ-notation. Indeed, λ-notation is required if weare to give a more precise formulation of the Rule of Substitution; theprecise formulation of the rule for concepts is: Rule of Substitution: The λ-expression [λx φ(x)] may beuniformly substituted for the occurrences of the variable F inany theorem of logic containing F free.(The formulation for relations is similar.) Moreover, the principle ofλ-Conversion simplifies the strict proof of the equivalence ofFrege's Rule of Substitution and the Comprehension Principle forConcepts. As it turns out, not only does Frege's Rule of Substitutionimply the Comprehension Principle for Concepts, but the converse alsoholds: the Comprehension Principle for Concepts implies the Rule ofSubstitution. [For a proof sketch, see Boolos (1985) pp. 161-162. Notethat instead of [λx φ(x)], Boolos uses thenotation {a: Aa}; elsewhere, in (1987) for example,Boolos uses the notation [x : A(x)] todenote concepts.] It is important to appreciate that the system we have justdescribed, i.e., Frege's system of second-order logic and the theory of(relational) concepts that he developed in Begr, isconsistent. (It is only later in Gg, when Frege addedBasic Law V to this consistent basis, that the resulting system becameinconsistent.) Its underlying comprehension principle for conceptsensures that the domain of concepts is very rich. Each concept has anegation, every pair of concepts has a conjunction, every pair ofconcepts has a disjunction, etc. The reader should be able to writedown instances of the comprehension principle which demonstrate theseclaims. In Part III of Begr, Frege applied his systemto the ‘theory of sequences’ (we call these‘R-series’ below). It is here that Frege presentshis celebrated definition of the ‘ancestral’ of a relationand first proves the generalized analogues of the principle ofmathematical induction, as well as various structural properties of theancestral. We shall postpone further discussion of this work until§§4 and 5, where we reproduce Frege's definition of theancestral of a relation and show how Frege incorporated this definitioninto the proof of mathematical induction, respectively.2. Frege's Theory of Extensions: Basic Law V[Note: This section is included to give an historical understanding ofFrege's system. It is not required for understanding the proof ofFrege's Theorem.] The principle that undermined Frege's system (Basic Law V) was onethat attempted to systematize the notions ‘course-of-values of afunction’ and ‘extension of a concept’. Thecourse-of-values of a function ƒ is something like a set ofordered pairs that records the value ƒ(x) for everyargument x. For example, the course-of-values of the functionfather of x records, among other things, that Bill Clinton isthe value of the function when Chelsea Clinton is the argument. Thecourse-of-values for the function x2 records, amongother things, that the number 4 is the value when the number 2 is theargument, that 9 is the value when 3 is the argument, etc. Theextension of a concept is something like the set of all objects thatfall under the concept. For example, the extension of the concept xis a positive even integer less than 8 is something like the setconsisting of the numbers 2, 4, and 6 (strictly speaking, the extensionof this concept records The True as the value when 2, 4 and 6 aresupplied as argument, and records that The False is the value whenanything else is supplied as argument). Since concepts are justfunctions from objects to truth values, the extension of a concept issimply the course-of-values which records which objects that conceptmaps to The True.2.1 Notation for Courses-of-Values of FunctionsFrege introduces notation for courses-of-values in GgI, §9. He switched to the lower case Greek letters epsilon andalpha when writing the names of courses-of-values and extensions. Heused something like the notation  and  to designate the course-of-values of the functions ƒ andg, respectively. In this notation, the symbols  and  bind the object variables epsilon and alpha, respectively, and theresulting expression denotes a course-of-values. Here is a pair of examples of Frege's notation for courses-of-valuesand the second are examples of extensions. This pair of examples comesfrom Gg I, §9. Frege uses the expression:  to denote the course-of-values of the function represented bythe open formula: x2 − xHe also uses:  to denote the course-of-values of the function representedby the open formula: x · (x − 1)Frege then notes that: ∀x[x2 −x = x · (x −1)]always has the same truth value as the following:  This equivalence will become embodied in Basic Law V. The reader shouldnow be in a position to see how the following formulation of Basic LawV corresponds to Frege's formulation in Gg I,§20: Basic Law V:  This principle asserts: the course-of-values of the function ƒ isidentical to the course-of-values of the function g if andonly if ƒ and g map every object to the same value.[Actually, Frege uses an identity sign instead of the biconditionalsign as the main connective of the principle. The reason he could dothis is that, in his system, when two sentences are materiallyequivalent, they name the same truth value.] We shall soonexplain why this principle is inconsistent. 2.2 Notation for Extensions of ConceptsIn what follows, we shall alter Frege's notation just a bit, to reflectthe fact that we are using a more traditional predicate calculus,rather than a term logic such as Frege's. In the special case whereƒ is the concept F, we use the simple notationεF to designate the extension of the conceptF. Note that λ-expressions[λx φ(x)] can be instances of thevariable F, and soε[λx φ(x)] is well-formed anddesignates the extension of the concept[λx φ(x)]. Thus, we do not useε as an operator which binds object-variables, but rather as afunctional operator on concept terms (i.e., on concept names or conceptvariables). When the operator is prefixed to a concept name, theresulting expression is a name of an object, and in particular, a nameof the extension of the concept denoted. When the operator is prefixedto a concept variable, the resulting expression is a variable rangingover extensions. (Of course, these stipulations will be undermined bythe inconsistency in Basic Law V, but it will do no harm now to assumethat the stipulations are in effect, at least until the inconsistencyin Basic Law V is explained.) Here is an example of our notation involving a pair of complexconcepts. Consider the concept that which when added to 4equals 5, or using λ-notation, the followingconcept: [λx x+4=5]We use the following notation to denote the extension of this concept: ε[λx x+4=5]Now consider the concept that which when added to22 equals 5 (i.e.,[λx x+22=5]). We use thefollowing notation to denote the extension of this concept: ε[λxx+22=5]Note that it seems natural to identify these two extensions wheneverall and only the objects that fall under the first concept fall underthe second. From these examples, it should be clear that when φ(x)is any formula in which the variable x is free, we may writeε[λx φ(x)] to designate theextension of the concept [λx φ(x)].Those readers already familiar with the ‘λ-calculus’should remember thatε[λx φ(x)] denotes an object,that [λx φ(x)] denotes a concept, andthat Frege rigorously distinguished objects and concepts and supposedthem to constitute mutually exclusive domains.2.3 Membership in an ExtensionIf we remember that the extension of a concept is something like theset of objects that fall under the concept, then we could replaceFrege's talk of ‘extensions’ by talk of ‘sets’and use the following ‘set notation’ to refer to the set ofobjects that when added to 4 yield 5 and the set of objects that whenadded to 22 yield 5, respectively: {x |x + 4 = 5} {x |x + 22 = 5}In what follows, we sometimes render Frege's notation in this moremodern notation. Frege took advantage of his second-order language to definewhat it is for an object to be a member of an extension. Although Fregeused the notation x ∩ y to designatethe membership relation, we shall follow the more usual practice ofusing x ∈ y. (Readers should checkthat their web browsers are correctly displaying the difference betweenthe membership sign ∈ and the epsilon operator ε.) Thus,the following captures the main features of Frege's definition ofmembership in Gg I, §34: x ∈ y =df∃G(y=εG & Gx)In other words, x is an element of y just in casex falls under a concept of which y is the extension.For example, given this definition, one can prove that John is a memberof the extension of the concept being happy (formally:j ∈ εH) from the premise that John falls underthe concept being happy (‘Hj’). Here is asimple proof: 1. HjPremise2. εH =εH= Introduction3. εH = εH & Hjfrom 1,2, by & Introduction4. ∃G(εH =εG & Gj)from 3, by Existential Introduction5. j ∈ εHfrom 4, by definition of ∈Some readers may wish to examine a somewhat more complex example, inwhich the above definition of membership is used to prove that 1 ∈ε[λx x+22=5] given thepremise that 1+22=5. (A More Complex Example) 2.4 Basic Law V for ConceptsBasic Law V has the following special case, when the functionsƒ and g are the concepts F and G: Basic Law V (Special Case): εF = εG ≡∀x(Fx ≡ Gx)[Here, again, Frege used an identity sign in place of the biconditionalsigns.] In this special case, Basic Law V asserts: the extension of theconcept F is identical to the extension of the conceptG if and only if all and only the objects that fall underF fall under G (i.e., if and only if the conceptsF and G are materially equivalent). In more modernguise, Frege's Basic Law V asserts that the set of Fs isidentical to the set of Gs if and only if F andG are materially equivalent: {x|Fx} = {y|Gy} ≡∀z(Fz ≡ Gz)The example discussed above can now be seen as an instance of BasicLaw V: ε[λy y+4=5] =ε[λy y+22=5] ≡∀x([λy y+4=5]x≡ [λyy+22=5]x)This simply asserts that the extension of the concept that whichadded to 4 yields 5 is identical to the extension of theconcept that which added to 22 yields 5 ifand only if all and only the objects that when added to 4 yield 5 areobjects that when added to 22 yield 5. Basic Law V has an important corollary, namely, that every concept hasan extension: Corollary to Basic Law V: ∀G∃x(x =εG)To see that this is a consequence of Basic Law V, note that when weinstantiate the variable G to F in Basic Law V, wecan establish: εF = εF ≡∀x(Fx ≡ Fx)Since the right side of this instance of Law V can be derived by logicalone, it follows that εF = εF. But,then, by existential generalization, it follows that: ∃x(x =εF) But now the Corollary follows by universal generalization onthe concept variable F. Basic Law V has other important corollaries as well. These are the Lawof Extensions and the Principle of Extensionality. The Law ofExtensions (cf. Gg I, §55, Theorem 1) assertsthat an object is a member of the extension of a concept if and onlyif it falls under that concept: Law of Extensions: ∀F∀x(x ∈εF ≡ Fx) (Proof of the Law of Extensions) Basic Law V also correctly implies the Principle of Extensionality.This principle asserts that if two extensions have the same members,they are identical. If we define‘Extension(x)’ as‘∃F(x=εF)’ then wemay formally represent and derive the principle of extensionality asfollows: Principle of Extensionality: Extension(x) & Extension(y) → [∀z(z ∈ x≡ z ∈ y) → x =y] (Proof of the Principle of Extensionality)Despite these deceptive successes of Basic Law V, the fact is that itcan't be consistently added to Frege's system. In the followingsubsections, we shall show how Basic Law V proves to be inconsistentwith the rest of Frege's second-order logic and theory of concepts. Theproofs depend essentially on the second-order character of Frege'ssystem and on the second-order definition of the membership relation.Frege was made aware of the inconsistency by Bertrand Russell, who senthim a letter formulating ‘Russell's Paradox’ just as thesecond volume of Gg was going to press. Frege quicklyadded an Appendix to the second volume, describing two distinct ways ofderiving a contradiction from Basic Law V. The first establishes thecontradiction directly, without any special definitions. The seconddeploys the membership relation and more closely follows Russell'sParadox. We will examine both derivations of the contradiction in whatfollows. Both derivations of the contradiction appeal to the Corollaryto Basic Law V. The combination of Frege's Rule of Substitution (whichensures that there is a concept corresponding to every formula withfree variable x) and Basic Law V and its Corollary (whichensure that each concept has an extension that behaves in a certainway), turns out to be a volatile mix.2.5 First Derivation of the ContradictionIn the Appendix to Gg II, Frege shows that acontradiction can be derived once we formulate the concept beingthe extension of a concept which you don't fall under. Thefollowing open formula expresses this concept: ∃F(x=εF &¬Fx)From the Comprehension Principle for Concepts (or Frege's Rule ofSubstitution), we know that there exists a concept corresponding tothis formula and we may use the following λ-expression to nameit: [λx∃F(x=εF &¬Fx)]Now by the Corollary to Basic Law V, the extension of thisconcept exists and can be designated as follows: ε[λx∃F(x=εF &¬Fx)]It can now be proved that this extension falls under the concept[λx ∃F(x=εF& ¬Fx)] if and only if it does not. (First Derivation of the Contradiction.)2.6 Second Derivation of the ContradictionFrege next (in the Appendix to Gg II) explained howBasic Law V implies the Naive Comprehension Axiom for extensions orsets, which Russell's Paradox shows to be inconsistent. From the Law ofExtensions (which was derived from Basic Law V above), one canestablish the Naive Comprehension Axiom for extensions in three simplesteps. First we instantiate the Law of Extensions to the free variableF, to yield: ∀x(x ∈ εF≡ Fx)Then by generalizing on the extension εF, it followsthat: ∃y∀x(x ∈y ≡ Fx)Now at this point, we may universally generalize on the variableF to get the following second-order Naive Comprehension Axiomfor extensions, which asserts that for every concept F, thereis an extension which has as members all and only the objects that fallunder F: Naive Comprehension Axiom for Extensions: ∀F∃y∀x(x∈ y ≡ Fx)Alternatively, instead of generalizing, we could have appealed toFrege's Rule of Substitution to show that all of the instances of thefollowing Naive Comprehension Schema for extensions are derivable inFrege's system: Naive Comprehension Schema for Extensions:∃y∀x(x ∈ y≡ φ(x)), where φ(x) is any formula inwhich x is free and which contains no free occurrences ofyThis asserts that for any formula φ(x) defining acondition on objects, there is an extension which has as members alland only the objects that meet the condition. Both the Naive Comprehension Axiom and the Naive ComprehensionSchema immediately give rise to Russell's Paradox in the context ofFrege's logic. In the case of the axiom, the contradiction follows byinstantiating the quantified variable F to the concept[λz ¬(z ∈ z)]. In the caseof the schema, the contradiction follows by taking φ(x) tobe ¬(x ∈ x), as follows: ∃y∀x(x ∈y ≡ ¬(x ∈ x))In either case, the proof of the contradiction goes through. Thederivation of the contradiction from the above instance of the schemais particularly easy. For suppose the object b is such ay. Then: ∀x(x ∈ b ≡¬(x ∈ x))But we can now instantiate the universal claim to the object bto yield the following contradiction: b ∈ b ≡ ¬(b∈ b)(See the entry on Russell's Paradox.)2.7 How the Paradox is EngenderedPhilosophers have diagnosed the inconsistency in Frege's system invarious ways, and it is safe to say that the matter is still somewhatcontroversial. In this subsection, we discuss only the basic elementsof the problem. Most philosophers and logicians agree that the reasonFrege's second-order logic and theory of extensions is inconsistent isthat they jointly require the impossible situation in which the domainof concepts has to be strictly larger than the domain of extensionswhile at the same time the domain of extensions has to be as large asthe domain of concepts. This impossible situation is strikinglyanalogous to the impossible situation set up in the proof byreductio of Cantor's Theorem (Cantor's Theorem asserts that ifA is any set, and B is the power set of A(i.e., B is the set of all subsets of A), thenB has more members than A; the proof by reductioshows that it is impossible for there to be a function from Aonto B). To analyze the inconsistency in Frege's system in more detail, it isimportant to discuss the conditions under which concepts are to beidentified. Although Frege did not believe that statements of the form‘F = G’ were meaningful, it is evidentfrom the study of Gg that the material equivalence ofconcepts F and G serves as the proxy identityconditions of F and G. So, whenever it isnot the case that all and only the objects that fall underF fall under G, F and G aredistinct concepts.With this in mind, we can see how the paradox is engendered. Recallfirst that the Corollary to Basic Law V reveals that Basic LawV correlates each concept with an extension. Each direction of BasicLaw V requires that this correlation have certain properties. We shallsee, for example, that the right-to-left direction of Basic Law V(i.e., Va) requires that no concept gets correlated with two distinctextensions. [Frege uses the label ‘Va’ to designate theright-to-left direction of Basic Law V. See, for example, GgI, §52. However, many commentators use ‘Va’to designate the left-to-right direction. We shall follow Frege's use,since that will make sense of his Appendix to Gg II,in which he discusses the paradoxes.] Va asserts: Basic Law Va: ∀x(Fx ≡ Gx) →εF = εGIf we think in terms of its contraposition and remember the identityconditions for concepts, Va in effect asserts that whenever extensionsdiffer, the concepts with which they are correlated differ. This meansthat the correlation between concepts and extensions that Basic Law Vsets up must be a function—no concept gets correlated with twodistinct extensions (though for all Va tells us, distinct conceptsmight get correlated with the same extension). Frege noted (in theAppendix to Gg II) that this direction of Basic Law Vdoesn't seem problematic. However, the left-to-right direction of Basic Law V (i.e., Vb) ismore serious. Vb asserts: Basic Law Vb: εF = εG →∀x(Fx ≡ Gx)If we consider the contrapositive of this and remember the identityconditions for concepts, then Vb, in effect, asserts that whenever theconcepts F and G differ, the extensions of Fand G differ. So, the correlation that Basic Law V sets upbetween concepts and extensions will have to be one-to-one; i.e., itcorrelates distinct concepts with distinct extensions. Since everyconcept is correlated with some extension, there have to be at least asmany extensions as there are concepts. But the problem is that Frege's system as a whole requiresthat there be more concepts than extensions. The requirementthat there be more concepts than extensions is imposed jointly by theComprehension Principle for Concepts and the new significancethis principle takes on in the presence of Basic Law V. TheComprehension Principle for Concepts asserts the existence of aconcept for every condition on objects expressible in thelanguage. Now although it may seem that this principle, in and ofitself, forces the domain of concepts to be larger than the domain ofobjects, it is a model-theoretic fact that there are models ofsecond-order logic with the Comprehension Principle for Concepts (butwithout Basic Law V) in which the domain of concepts is notlarger than the domain of objects.[1] However, the ComprehensionPrinciple for Concepts takes on new significance when Basic Law V isadded to Frege's system. The synergism of the Comprehension Principlefor Concepts and Basic Law V force the domain of concepts to be largerthan the domain of objects (and so larger than the domain ofextensions). However, as we saw in the last paragraph, Vb requires thatthere be at least as many extensions as there are concepts.Thus, Frege's second-order logic and theory of extensions togetherrequired the impossible situation in which the domain of concepts hasto be strictly larger than the domain of extensions while at the sametime the domain of extensions has to be as large as the domain ofconcepts.Recently, there has been a lot of interest in discovering ways ofrepairing Frege's system. The traditional view is that one must eitherrestrict Basic Law V or restrict the Comprehension Principle forConcepts. Recently, Boolos (1986, 1993) developed one of the moreinteresting suggestions for revising Basic Law V without abandoningsecond-order logic and its comprehension principle for concepts. Onthe other hand, there have been many suggestions for restricting theComprehension Principle for Concepts. The most severe of these is toabandon second-order logic (and the Comprehension Principle forConcepts) altogether. Schroeder-Heister (1987) conjectured that thefirst-order portion of Frege's system (i.e., the system which resultsby adding Basic Law V to the first-order predicate calculus) wasconsistent and this was proved by T. Parsons (1987) and Burgess (1998).[2] Heck (1996) and Wehmeier (1999) consider less drastic moves. Theyinvestigate systems of second-order logic which have been extended byBasic Law V but in which the Comprehension Principle for Concepts isrestricted in some way. See also Anderson & Zalta (2004) andAntonelli & May (2005) for different approaches to repairingFrege's system. For a good general overview, see Burgess (2005). We will not discuss the above research further in the present entry,for it is not clear which of their alternatives, or others, would havebeen acceptable to Frege. Instead, we focus on the theoreticalaccomplishment revealed by Frege's work in Gg.Despite the failure of Basic Law V, Frege validly proved a ratherdeep fact about the natural numbers, namely, that the Dedekind/Peanoaxioms for number theory could be derived in second-order logic withthe help of a single additional principle. The principle in question isknown as Hume's Principle (discussed below). Although both C. Parsons(1965) and Wright (1983) had recently noted that Hume's Principle waspowerful enough for the derivation of the Dedekind/Peano axioms, Heck(1993) showed that although Frege did use Basic Law V to derive Hume'sprinciple, his (Frege's) subsequent derivations of the Dedekind/Peanoaxioms of number theory from Hume's Principle never made anessential appeal to Basic Law V. Since Hume's Principle justby itself is consistent with second-order logic, this means that Fregevalidly derived the basic laws of number theory. It will be the task ofthe next few sections to explain Frege's accomplishments in thisregard. We will do this in two stages. In §3 we study Frege'sattempt to derive Hume's Principle from Basic Law V by analyzingcardinal numbers as extensions. Then, we put this aside in§§4 and 5 to examine how Frege was able to derive theDedekind/Peano axioms of number theory from Hume's Principle alone.3. Frege's Analysis of Cardinal NumbersCardinal numbers are the numbers that can be used to answer thequestion ‘How many?’, and Frege discovered that suchnumbers bear an interesting relationship to the natural numbers.Frege's insights concerning this relationship trace back to his work inGl, in which the notion of an extension played verylittle role. The seminal idea of Gl, §46, was theobservation that a statement of number (e.g., "There are nine planets")is an assertion about a concept. To explain this idea, Frege noted thatone and the same external phenomenon can be counted in different ways;for example, a certain external phenomenon could be counted as onearmy, 5 divisions, 25 regiments, 120 companies, 400 platoons, or 4000people. Each different way of counting this phenomenon corresponds tothe manner of its conception. The question "How many are there?" isonly properly formulated as the question "How many Fs arethere?" where a concept F is supplied. On Frege's view, thestatements of number which answer such questions (e.g., "There aren Fs") tell us something about the concept involved.For example, the statement "There are nine planets in the solar system"tells us that the ordinary, first-level concept planet inthe solar system falls under the second-level numericalconcept concept under which nine objects fall. Frege then moves from this realization, in which statements of numbersare analyzed as predicating second-level numerical concepts offirst-level concepts, to develop an account of the cardinal andnatural numbers as ‘self-subsistent’ objects. Heintroduces a ‘cardinality operator’ on concepts, namely,‘the number belonging to the concept F’, whichwill designate the cardinal number which numbers the objects fallingunder F. In what follows, we say this more simply as‘the number of Fs’ and use the simple notation‘#F’. (Note that the operator # behaves likeε operator — when it is prefixed to a name of a concept(or prefixed to a concept variable), the resulting expression denotesan object (or ranges over objects).) Frege offers both an implicitand an explicit definition of this operator inGl. Both of these definitions require a preliminarydefinition of when two concepts F and G are inone-to-one correspondence or ‘equinumerous’. Afterdeveloping the definition of equinumerosity, we then discuss Frege'simplicit and explicit definition of the number of Fs.3.1 EquinumerosityIn order to state the definition of equinumerosity, we shall employ thewell-known logical notion ‘there exists a unique x suchthat φ(x)’. To say that there exists a uniquex such that φ(x) is to say: there is somex such that φ(x) and anything y which issuch that φ(y/x) is identical to x. Inwhat follows, we use the notation‘∃!xφ(x)’ to abbreviate thisnotion of unique existence, and we define it formally as follows: ∃!xφ(x) =df ∃x[φ(x) &∀y(φ(y/x) →y=x)]Now, in terms of this logical notion of unique existence, we can stateFrege's definition of equinumerosity (Gl, §71,72) as follows: F and G are equinumerous (or,F and G are in one-to-one correspondence)just in case there is a relation R such that: (1) every objectfalling under F is R-related to a unique objectfalling under G, and (2) every object falling under Gis such that there is a unique object falling under F which isR-related to it.If we let ‘F ≈ G’ stand forequinumerosity, then the definition of this notion can be renderedformally as follows: F ≈ G =df ∃R[∀x(Fx →∃!y(Gy & Rxy)) & ∀x(Gx → ∃!y(Fy& Ryx))]To see that Frege's definition of equinumerosity works correctly,consider the following two examples. In the first example, we have twoconcepts that are equinumerous:  Figure 1Although there are several different relations R which woulddemonstrate the equinumerosity of F and G theparticular relation used in Figure 1 is: R1 = [λxy (x=a& y=f) v (x=b & y=g) v (x=c& y=e)]It is a simple exercise to show that R1, asdefined, is a ‘witness’ to the equinumerosity of Fand G (according to the definition). In the second example, we have two concepts that are notequinumerous:  Figure 2In this example, no relation R can satisfy the definition ofequinumerosity. Clearly, then, the concepts F and G will beequinumerous whenever the number of objects falling under F isidentical to the number of objects falling under G. This factwill be codified by Hume's Principle. Before moving ahead to thediscussion of this principle, the reader should convince him- orherself of the following four facts: (1) that the material equivalenceof two concepts implies their equinumerosity, (2) that equinumerosityis reflexive, (3) that equinumerosity is symmetric, and (4) thatequinumerosity is transitive. In formal terms, the following facts areprovable: Facts About Equinumerosity: 1. ∀x(Fx ≡ Gx) →F ≈ G 2. F ≈ F 3. F ≈ G → G ≈ F 4. F ≈ G & G ≈ H→ F ≈ HThe proofs of these facts, in each case, require the identification ofa relation that is a witness to the relevant equinumerosity claim. Insome cases, it is easy to identify the relation in question. In othercases, the reader should be able to ‘construct’ suchrelations (using λ-notation) by considering the examplesdescribed above. Facts (2) – (4) establish that equinumerosityis an ‘equivalence relation’ which divides up the domainof concepts into ‘equivalence classes’ of equinumerousconcepts. Material equivalence is also an equivalence relation whichdivides up the domain of concepts into equivalence classes ofmaterially equivalent concepts.3.2 Contextual Definition of ‘The Number of Fs’: Hume's PrincipleFrege contextually defined ‘the number of Fs’ interms of the principle now known as Hume's Principle:[3] Hume's Principle: The number of Fs is identical to the number of Gs ifand only if F and G are equinumerous.Using our notation ‘#F’ to abbreviate ‘thenumber of Fs’, we may formalize Hume's Principle asfollows: Hume's Principle: #F = #G ≡ F ≈GThis contextual definition governing cardinal numbers is the basicprinciple upon which Frege forged his development of the theory ofnatural numbers.[4] In Gl, Frege sketched thederivations of the basic laws of number theory from Hume's Principle;these sketches were developed into more rigorous proofs in GgI. We will examine these derivations in the followingsections. Once Frege had a contextual definition of #F, he thendefined a cardinal number as any object which is the number of someconcept: x is a cardinal number =df ∃F(x = #F)This definition appears in Gl, §72. Notice that Hume's Principle bears an obvious formal resemblance toBasic Law V. Both are biconditionals asserting the equivalence of anidentity among singular terms (the left-side condition) with anequivalence relation on concepts (the right-side condition). Indeed,both correlate concepts with certain objects. In the case of Hume'sPrinciple, each concept F is correlated with #F.However, whereas Basic Law V problematically asserts that thecorrelation between concepts and extensions is one-to-one, Hume'sPrinciple only asserts that the correlation between concepts andnumbers is many-to-one. Hume's Principle often correlates distinctconcepts with the same number. For example, the distinct conceptsauthor of Principia Mathematica (‘[λxAxp]’) and number between 1 and 4(‘[λx 1 < x < 4]’) areequinumerous (both both have two objects falling under them). So#[λx Axp] = #[λx 1 <x < 4]. Thus, Hume's Principle, unlike Basic Law V, doesnot require that the domain of numbers be as large as the domain ofconcepts. Indeed, Hume's Principle has recently been proved consistentwith second-order logic. This was shown independently by Burgess(1984) and Hazen (1985).3.3 Explicit Definition of ‘The Number of Fs’[Note: The remaining two subsections are not strictly necessary forunderstanding the proof of Frege's Theorem. They are included here forthose who wish to have a more complete understanding of what Frege infact attempted to do. They presuppose the material in §2. Readersinterested in just the positive aspects of Frege's accomplishmentsshould skip directly to §4.] Before we examine the powerful consequences that Frege derived fromHume's Principle, it is worth digressing to describe his failed attemptto explicitly define ‘#F’ and to derive Hume'sPrinciple from Basic Law V. The idea behind this attempt was therealization that if given any concept F, the notion ofequinumerosity can be used to define the second-level concept beinga concept G that is equinumerous to F (‘G ≈F’). Frege found a way to collect all of the conceptsequinumerous to a given concept F into a single extension. InGl, he informally took this to be an extensionconsisting of first-order concepts. In that work, he defined informally(§68): the number of Fs =df the extension of the second-level concept: being afirst-level concept equinumerous to FIn terms of the example used at the end of the previous subsection,this definition identifies the number of the concept author ofPrincipia Mathematica as the extension consisting of all and onlythose first-level concepts that are equinumerous to this concept; thisextension has both [λx Axp] and[λx 1 < x < 4] as members. Frege in factidentifies the cardinal number 2 with this extension, for it containsall and only those concepts under which two objects fall. Similarly,Frege identifies the cardinal number 0 with the extension consisting ofall those first-level concepts under which no object falls; thisextension would include such concepts as unicorn,centaur, prime number between 3 and 5, etc.Frege's insight here inspired Russell to develop a somewhat similardefinition in his work, and it is now common to see references to theso-called "Frege-Russell definition of the cardinal numbers" as classesof equinumerous concepts or sets.[5] Of course, this explicit definition of ‘thenumber of Fs’ stands or falls with a coherent conceptionof ‘extension’. We know that Basic Law V does not offersuch a coherent conception. 3.4 Derivation of Hume's PrincipleFrege's derivation of Hume's Principle was invalidated by the fact thatit appeals to the inconsistent Basic Law V. Nevertheless, it isinstructive to consider why Frege thought the derivation was valid. InGl, §73, Frege sketches an informal proof of theright-to-left direction of Hume's Principle using the above explicitdefinition of the number of Fs. The derivation appeals to thefact that a concept G is a member of the extension of thesecond-level concept concept equinumerous to F if and only ifG is equinumerous to F. In other words, the proofrelies on a kind of higher-order version of the Law of Extensions(described above), the ordinary version of which we know to be aconsequence of Basic Law V.[6] Here is a reconstruction of Frege's proof inGl, §73, extended so as to cover both directionsof Hume's Principle. Frege's Derivation of Hume's Principle in the GrundlagenHowever, in the development of Gg, Fregean extensionsdo not contain concepts as members but rather objects. SoFrege had to find another way to express the explicit definitiondescribed in the previous subsection. His technique was to letextensions go proxy for their corresponding concepts. Since a fullexplanation of this technique and the proof of Hume's Principle inGg would constitute a digression for the presentexposition, we shall describe the details for interested readers on aseparate page: Frege's ‘Derivation’ of Hume's Principle in the GrundgesetzeAs noted on several occasions, the inconsistency in Basic Law Vinvalidated Frege's derivation of Hume's Principle. But Hume'sPrinciple, in and of itself, is a powerful and consistent principle. 4. Frege's Analysis of Predecessor, Ancestrals, and the Natural NumbersIn what follows, we shall suppose that Hume's Principle has replacedBasic Law V in Frege's second-order system. This requires that wereplace the operator "the course of values of the function f"(and "the extension of concept F") with the primitive operator"the number of Fs". As we have mentioned, Frege made the insightfuldiscovery that the basic laws of number theory could be derived fromHume's Principle alone. This is Frege's Theorem. In this section, weintroduce the definitions required for the proof of Frege's Theorem. Inthe next section, we go through the proof. In the final section, weconclude with a discussion of the philosophical questions that arisewhen we consider Hume's Principle as a replacement for Basic Law V. The insight behind Frege's analysis of the natural numbers was therealization that one can define the finite cardinal numbers in terms ofthe following concepts: C0 = [λx x≠x] C1 = [λx x =#C0] C2 = [λx x = #C0 v x = #C1] C3 = [λx x = #C0 v x = #C1 v x= #C2] etc.Note that starting with C1, each conceptCk has the following property: all and only thenumbers of concepts preceding Ck in the sequencefall under Ck. So, for example, the conceptspreceding C3 are C0, C1, andC2. Accordingly, all and only the following numbers fallunder C3: #C0, #C1, and#C2.Frege noticed that these concepts can be used, respectively, todefine the the finite cardinal numbers, as follows: 0 = #C0 1 = #C1 2 = #C2 etc.This insight, however, was only the first step in Frege's plan. Herealized that though this seems to define a sequence of numbers withwhich we can identify the natural numbers, we have not as yet definedthe concept ‘natural number’ so that it applies to all andonly the cardinal numbers defined in the second sequence. Such aconcept is required if we are to prove as theorems thefollowing axioms of Dedekind/Peano number theory: Dedekind/Peano Axioms for Number Theory: 0 is a natural number.0 is not the successor of any natural number.No two natural numbers have the same successor.If both (a) 0 falls under F, and (b) for any two naturalnumbers n and m such that m is the successorof n, the fact that n falls under F impliesthat m falls under F, then every natural number fallsunder F. (Principle of Induction)Every natural number has a successor.Moreover, Frege recognized the need to employ the Principle ofInduction in the proof that every number has a successor. One cannotprove the claim that every number has a successor simply byproducing the sequence of expressions for cardinal numbers (e.g., thesecond of the two sequences described above). All such a sequencedemonstrates is that for every expression listed in the sequence, onecan define an expression of the appropriate form to follow it in thesequence. This is not the same as proving that everynatural number has a successor. 4.1 PredecessorTo accomplish these further goals, Frege proceeded by defining theconcept x (immediately) precedes y asfollows (Gl, §76, and Gg I,§43): x (immediately) precedesy if and only if there is a concept F and an objectw such that: (a) w falls under F, (b)y is the number of Fs, and (c) x is thenumber of the concept object falling under F other thanwIn formal terms, the definition takes the following form: Precedes(x,y) =df ∃F∃w(Fw & y = #F & x =#[λz Fz &z≠w])Even though we can't as yet assume that we have defined the naturalnumbers 1 and 2, we can use them intuitively to show that thedefinition properly predicts that Precedes(1,2) if givencertain facts about the numbers of certain concepts. Let the expression‘[λz Azp]’ denote the conceptauthor of Principia Mathematica. Only Bertrand Russell(‘r’) and Alfred Whitehead fall under thisconcept. Let the expression ‘[λz Azp& z≠r]’ denote the concept author ofPrincipia Mathematica other than Russell.[7] Then the following may, forthe purposes of this example, be taken as facts: Russell falls under the concept author of PrincipiaMathematica, i.e., [λz Azp]r2 is the number of the concept author of PrincipiaMathematica, i.e., 2 = #[λz Azp]1 is the number of the concept author of Principia Mathematicaother than Russell, i.e., 1 = #[λz Azp &z≠r]If we assemble these truths into a conjunction and apply existentialgeneralization in the appropriate places, the result is the definiensof the definition of predecessor instantiated to the numbers 1 and 2.Thus, if given certain facts about the number of objects falling underthe certain concepts, the definition of predecessor correctly predictsthat Precedes(1,2). 4.2 The Ancestral of Relation RFrege next defines the relational concept x is an ancestor of yin the R-series. This new relation is called ‘the ancestralof the relation R’ and we henceforth designate thisrelation as R*. Frege first defined the ancestral of relationR in Begr (Part III, Proposition 76), thoughthe word ‘ancestral’ comes to us from Russell andWhitehead. Frege's term for the ancestral is "x comes beforey in the R-series"; alternatively, "yfollows x in the R-series". (See alsoGl, §79 and Gg I, §45.) Theintuitive idea is easily grasped if we consider the relation xis the father of y. Suppose that a is the father ofb, that b is the father of c, and thatc is the father of d. Then ‘x is anancestor of y in the fatherhood-series’ is defined sothat a is an ancestor of b, c, andd, that b is an ancestor of c andd, and that c is an ancestor of d.Frege's definition of the ancestral of R requires apreliminary definition: the concept F is hereditary in the R-series if andonly if any pair of R-related objects x andy are such that y falls under F wheneverx falls under FIn formal terms: Her(F,R) =abbr ∀x∀y(Rxy → (Fx→ Fy))Intuitively, the idea is that F is hereditary in theR-series if F is always ‘passed’ fromx to y whenever x and y are a pairof R-related objects. (We warn the reader here that thenotation ‘Her(F,R)’ is merely anabbreviation of a much longer statement. It is not a formulaof our language having the form‘R(x,y)’. In what follows, wesometimes introduce other such abbreviations.) Frege's definition of the ancestral of R can now be statedas follows: x comes before y in the R-series =df y falls under all thoseR-hereditary concepts F under which falls everyobject to which x is R-relatedIn other words, y follows x in the R-serieswhenever y falls under every hereditary concept Fwhich x ‘passes on’ to all of its immediatedescendants. In formal terms: R*(x,y) =df ∀F[∀z(Rxz →Fz) & Her(F,R) → Fy]For example, Clinton's father stands in relation father* of(i.e., forefather) to Chelsea because she falls under everyhereditary concept that Clinton and his brother inherited fromClinton's father. However, Clinton's brother is not one of Chelsea'sforefathers, since he fails to be her father, her grandfather, or anyof the other links in the chain of fathers from which Chelseadescended. It is important to grasp the differences between a relationR and its ancestral R*. Rxy impliesR*(x,y) (e.g., if Clinton is a father ofChelsea, then Clinton is a forefather of Chelsea), but the conversedoesn't hold (Clinton's father is a father* of Chelsea, but he is not afather of Chelsea). Indeed, a grasp of the definition of R*should leave one able to prove the following easy consequences, many ofwhich correspond to theorems in Begr and Gg:[8] Facts About R*: Rxy → R*(x,y)¬∀R∀x∀y(R*(x,y) → Rxy)[R*(x,y) &∀z(Rxz → Fz) &Her(F,R)] → Fy[9]∃xR*(x,y) → ∃x Rxy[Fx & R*(x,y) & Her(F,R)] → FyRxy & R*(y,z) →R*(x,z)R*(x,y) &R*(y,z) →R*(x,z)The reader should consider what happens when R is taken to bethe relation precedes. Appealing to our intuitive grasp of thenumbers, we can say that it is an instance of Fact (1) that if 10precedes 12, then 10 precedes* 12; and that it is an instance of Fact(2) that 10's preceding* 12 does not imply that 10 precedes 12. Aninstance of Fact (7) is that precedes* is transitive. When we restrictourselves to the natural numbers, it is intuitive to think of thedifference between precedes and precedes* as the difference betweenimmediately precedes and less-than. 4.3 The Weak Ancestral of RGiven the notion of the ancestral of relation R, Frege thendefines its weak ancestral, which he termed "y is a member of theR-series beginning with x" (cf. Begr, Part III,Proposition 99; Gl, §81, and GgI, §46): y is a member of the R-series beginning with x ifand only if either x bears the ancestral of R toy or x = yIn formal terms: R+(x,y) =df R*(x,y) vx=yWe note here that Frege would also readR+(x,y) as: x is amember of the R-series ending with y! Logicians callR+ the ‘weak-ancestral’ of Rbecause it is a weakened version of R*. When R isprecedes, we can intuitively regard its weak ancestral,precedes+, as the relationless-than-or-equal-to on the natural numbers. The general definition of the weak ancestral of R yieldsthe following facts, many of which correspond to theorems in Gg:[10] Facts About R+: Rxy →R+(x,y)Rxy &R+(y,z) →R*(x,z)R+(x,y) & Ryz→ R*(x,z)R*(x,y) & Ryz →R+(x,z)R+(x,x) (Reflexivity)R*(x,y) →∃z[R+(x,z) & Rzy] (Proof of Fact 6 Concerning the Weak Ancestral)[Fx & R+(x,y)& Her(F,R)] → FyR*(x,y) & Rzy &R is 1-1 →R+(x,z)[11]The proofs of these facts are left as exercises. 4.4 The Concept Natural NumberFrege's definition of natural number requires one morepreliminary definition. It may be recalled that Frege identifiedthe number 0 as the (cardinal) number of the concept beingnon-self-identical. That is: 0 =df #[λxx≠x]Since the logic of identity guarantees that no object fails to beself-identical, nothing falls under the concept beingnon-self-identical. Had one of Frege's explicit definitions of thecardinal numbers worked as he had intended, the number 0 would, ineffect, be identified with the extension of all (extensions of)concepts under which nothing falls. However, for the present purposes,we may note that 0 is defined in terms of the primitive notion‘the number of Fs’ and a particular complexconcept the existence of which is guaranteed in Frege's theory ofconcepts and second-order logic with identity. It is straightforward toprove the following Lemma Concerning Zero from this definition of 0: Lemma Concerning Zero: #F = 0 ≡ ¬∃xFx (Proof of Lemma Concerning Zero)Note that the proof appeals to Hume's Principle and facts aboutequinumerosity. Frege's definition of the concept natural number can now bestated in terms of the weak-ancestral of Predecessor: x is a natural number if and only if x isa member of the predecessor-series beginning with 0This definition appears in Gl, §83, andGg I, §46 as the definition of ‘finitenumber’. Indeed, the natural numbers are precisely the finitecardinals. In formal terms, Frege's definition becomes: Nx =df Precedes+(0,x)In what follows, we shall sometimes use the variables m,n, and o to range over the natural numbers. 5. Frege's TheoremFrege's Theorem is that the five Dedekind/Peano axioms for numbertheory can be derived from Hume's Principle in second-order logic. Inthis section, we reconstruct the proof of this theorem which can beextracted from Frege's work using the definitions and theoremsassembled so far. Some of the steps in this proof can be found inGl. (See the Appendix to Boolos (1990) for areconstruction.) Our reconstruction follows Frege's Ggin spirit and in most details, but we have tried to simplify thepresentation in several places. For a more strict description ofFrege's Gg proof, the reader is referred to Heck(1993). The following should help prepare the reader for Heck'sexcellent essay.5.1 Zero is a NumberThe following is an immediate consequence of the definition ofnatural number: Theorem 1: N0 Proof: It is a simple consequence of the definition of‘weak ancestral’ that R+ is reflexive(see Fact 4 about R+ in our subsection on the WeakAncestral in §4). So Precedes+(0,0). Hence, bythe definition of number, 0 is a number.It seems that Frege never actually identified this fact explicitly inGl or labeled this fact as a numbered Theorem inGg I. It is possible that he thought it was tooobvious to mention. 5.2 Zero Isn't the Successor of Any NumberIt is also a simple consequence of the foregoing that 0 doesn't succeedany number. This can be represented formally as follows: Theorem 2: ¬∃x(Nx &Precedes(x,0)) Proof: Assume, for reductio, that some object, sayb, is such that Precedes(b,0). Then, by thedefinition of predecessor, it follows that there is a concept, sayQ and an object, say c, such that Qc &0=#Q & b=#[λz Qz & z≠c]. But by the Lemma Concerning Zero (above), 0=#Q implies¬∃xQx, which contradicts the fact thatQc. So nothing precedes 0. Since nothing precedes 0, nonatural number precedes 0. See Gl, §78, Item (6); and Gg I,§109, Theorem 126. 5.3 No Two Numbers Have the Same SuccessorThe fact that no two numbers have the same successor is somewhat moredifficult to prove (cf. Gl, §78, Item (5);Gg I, §95, Theorem 89). We may formulate thistheorem as follows, with m, n, and o asrestricted variables ranging over the natural numbers: Theorem 3: ∀m∀n∀o[Precedes(m,o)& Precedes(n,o) → m =n]In other words, this theorem asserts that predecessor is a one-to-onerelation on the natural numbers. To prove this theorem, it suffices toprove that predecessor is a one-to-one relation full stop. One canprove that predecessor is one-to-one from Hume's Principle, with thehelp of the following Equinumerosity Lemma, the proof of which israther long and involved. The Equinumerosity Lemma asserts that whenF and G are equinumerous, x falls underF, and y falls under G, then the conceptobject falling under F other than x is equinumerous to theconcept object falling under G other than y. The picture issomething like this:  Figure 3In terms of Figure 3, the Equinumerosity Lemma tells us that if thereis a relation R which is a witness to the equinumerosity ofF and G, then there is a relation R′which is a witness to the equinumerosity of the concepts that resultwhen you restrict F and G to the objects other thanx and y, respectively. To help us formalize the Equinumerosity Lemma, letF−x abbreviate the concept[λz Fz & z≠x] and letG−y abbreviate the concept[λz Gz & z≠y]. Thenwe have: Equinumerosity Lemma: F ≈ G & Fx & Gy → F−x ≈G−y (Proof of Equinumerosity Lemma)Now we can prove that Predecessor is a one-to-one relation from thisLemma and Hume's Principle (cf. Gg I, §108): Predecessor is One-to-One: ∀x∀y∀z[Precedes(x,z) & Precedes(y,z)→ x = y] Proof: Assume that both a and b areprecedessors of c. By the definition of predecessor, we knowthat there are concepts and objects P, Q, d,and e, such that:Pd & c = #P & a = #P−dQe & c = #Q & b = #Q−eBut if both c = #P and c = #Q,then #P = #Q. So, by Hume's Principle, P≈ Q. So, by the Equinumerosity Lemma, it follows thatP−d ≈Q−e. If so, then by Hume'sPrinciple, #P−d =#Q−e. But then, a =b.So, if Predecessor is a one-to-one relation, it is a one-to-onerelation on the natural numbers. Therefore, no two numbers have thesame successor. This completes the proof of Theorem 3. It is important to mention here that not only is Predecessor aone-to-one relation, it is also a function: Predecessor is a Function: ∀x∀y∀z[Precedes(x,y) & Precedes(x,z)→ y = z]This fact can be proved with the help of a kind of converse to theEquinumerosity Lemma: Equinumerosity Lemma‘Converse’: F−x ≈G−y & Fx & Gy → F ≈GWe leave the proof of the Equinumerosity Lemma ‘Converse’and the proof that Predecessor is a function as exercises for thereader. The fact that Predecessor is a function will play a part in theproof that every number has a successor. 5.4 The Principle of Mathematical InductionLet us say that a concept F is hereditary on the naturalnumbers just in case every ‘adjacent’ pair of numbersn and m (n preceding m) is suchthat m falls under F whenever n falls underF, i.e., HerOn(F,N) =abbr ∀n∀m[Precedes(n,m)→ (Fn → Fm)]Then we may state the Principle of Mathematical Induction as follows:if (a) 0 falls under F and (b) F is hereditary on thenatural numbers, then every natural number falls under F. Informal terms: Theorem 4: Principle ofMathematical Induction: F0 & HerOn(F,N) →∀n FnFrege actually proves the Principle of Mathematical Induction from amore general principle that governs any R-series whatsoever.We will call the latter the General Principle of Induction. It assertsthat whenever a falls under F, and F ishereditary on the R-series beginning with a, thenevery member of that R-series falls under F. We canformalize the General Principle of Induction with the help of a morestrict understanding of ‘hereditary on the R-seriesbeginning with a’. Here is a definition: HerOn(F,aR+) =abbr ∀x∀y[R+(a,x) & R+(a,y) &Rxy → (Fx →Fy)]In other words, F is hereditary on the members of theR-series beginning with a just in case every adjacentpair x and y in this series (with x bearingR to y) is such that y falls underF whenever x falls under F. Now given thisdefinition, we can reformulate the General Principle of Induction morestrictly as: General Principle of Induction: [Fa & HerOn(F,aR+)] → ∀x[R+(a,x) →Fx]This is a version of Frege's Theorem 152 in Gg I,§117. Frege's proves this claim by making an insightful appeal to his Ruleof Substitution. We may sketch the proof strategy as follows. Assumethat the antecedent of the General Principle of Induction holds for anarbitrarily chosen concept, say P. That is, assume: Pa & HerOn(P,aR+)Now to show∀x(R+(a,x) →Px), pick an arbitrary object, say b, and furtherassume R+(a,b). We then simplyhave to show Pb. Frege does this by using the Rule ofSubstitution on Fact (7) about R+ (in oursubsection on the Weak Ancestral in §4). Recall that Fact (7) is: [Fx &R+(x,y) &Her(F,R)] → FyThis is a theorem of logic containing the free variables x,y, and F. Frege instantiates x andy to a and b, respectively. He then, as wemight put it, instantiates F to the concept[λz R+(a,z) &Pz] and applies λ-Conversion. (This is where Frege usedhis Rule of Substitution.) The concept being instantiated forF is the concept member of the R-series beginning with aand which falls under P. The result of instantiating the freevariables in Fact (7) and then applying λ-Conversion yields arather long conditional, with numerous conjuncts in the antecedent andthe claim that Pb in the consequent. Thus, if the antecedentcan be established, the proof is done. However, for those followingalong with pencil and paper, all of the conjuncts to this conditionalare things we already know, with the exception of the claim that[λz R+(a,z) &Pz] is hereditary on R. However, this claim can beestablished straightforwardly from things we know to be true (and, inparticular, from facts contained in the antecedent of the Principle weare trying to prove, which we assumed as part of our conditionalproof). The reader is encouraged to complete the proof as an exercise.For those who would like to check their work, we give the completeProof of the General Principle of Induction here. Proof of the General Principle of InductionNow to derive Principle of Mathematical Induction from the GeneralPrinciple of Induction, we formulate the instance of the latter inwhich a is 0 and R is Precedes: [F0 & HerOn(F,0Precedes+)] → ∀x[Precedes+(0,x) →Fx]When we expand the defined notation for HerOn, substitute thenotation Nx and Ny forPrecedes+(0,x) andPrecedes+(0,y), respectively, and thenemploy our restricted quantifiers∀n(…n…) and∀m(…m…) for the claims of theform ∀y(Ny →…y…) and ∀x(Nx→ …x…), respectively, the result is thePrinciple of Mathematical Induction (in which the notationHerOn(F,N) has been eliminated in terms ofits definiens). 5.5 Every Number Has a SuccessorFrege uses the Principle of Mathematical Induction to prove that everynumber has a successor in the natural numbers. We may formulate thetheorem as follows: Theorem 5: ∀x[Nx →∃y(Ny &Precedes(x,y))]To understand Frege's strategy for proving this theorem, recall thatthe weak ancestral of the Predecessor relation, i.e.,Precedes+(x,y), can be read as:x is a member of the predecessor-series ending withy. Frege then considers the concept member of thepredecessor-series ending with n, i.e., [λzPrecedes+(z,n)], where nis a natural number. Frege then shows, by induction, that every naturalnumber n precedes the number of the concept member of thepredecessor-series ending with n. That is, Frege proves that everynumber has a successor by proving the following Lemma on Successors byinduction: Lemma on Successors: ∀n Precedes(n, #[λzPrecedes+(z,n)])This asserts that every number n precedes the number ofnumbers in the predecessor series ending with n. Frege canestablish Theorem 5 by proving the Lemma on Successors and by showingthat the successor of a natural number is itself a natural number. To see an intuitive picture of why the Lemma on Successors gives uswhat we want, we may temporarily regard Precedes+ as therelation ≤. (One can prove that Precedes+ has theproperties that ≤ has on the natural numbers.) Although we haven'tyet defined the natural numbers following 0, the following intuitivesequence is driving Frege's strategy: 0 precedes #[λz z≤ 0] 1 precedes #[λz z≤ 1] 2 precedes #[λz z≤ 2] etc.For example, the third member of this sequence is true because thereare 3 natural numbers (0, 1, and 2) that are less than or equal to 2;so the number 2 precedes the number of numbers less than or equal to 2.Frege's strategy is to show that the general claim, that nprecedes the number of numbers less than or equal to n, holdsfor every natural number. So, given this intuitive understanding of theLemma on Successors, Frege has a good strategy for proving that everynumber has a successor. (For the remainder of this subsection, thereader may wish to continue to think of Precedes+ in termsof ≤.) Now to prove the Lemma on Successors by induction, we need toreconfigure this Lemma to a form which can be used as the consequent ofthe Principle of Induction; i.e., we need something of the form∀n Fn. We can get the Lemma on Successors into thisform by ‘abstracting out’ a concept from the Lemma usingthe right-to-left direction of λ-Conversion to produce thefollowing equivalent statement of the Lemma: ∀n [λyPrecedes(y, #[λzPrecedes+(z,y)])]nThe concept ‘abstracted out’ is the following: [λy Precedes(y,#[λzPrecedes+(z,y)])]This is the concept: being an object y which precedes the number ofthe concept: member of the predecessor series ending in y. Let usabbreviate the λ-expression that denotes this concept as‘Q’. Then Frege's strategy is to instantiate thevariable F in the Principle of Induction (using his Rule ofSubstitution) to Q. The result is therefore something that wemay take as having been proved: Q0 & HerOn(Q,N)→ ∀n QnSince the consequent is the Lemma on Successors, Frege can prove thisLemma by proving both that 0 falls under Q (cf. GgI, Theorem 154) and that Q is hereditary on thenatural numbers (cf. Gg I, Theorem 150): Proof that 0 falls under Q Proof that Q is hereditary on the natural numbersGiven this proof of the Lemma on Successors, Theorem 5 is not far away.The Lemma on Successors shows that every number precedes some cardinalnumber of the form #F. We still have to show that suchsuccessor cardinals are natural numbers. That is, it still remains tobe shown that if a number n precedes something y,then y is a natural number: Successors of Natural Numbers are NaturalNumbers: ∀n∀y(Precedes(n,y)→ Ny) Proof: Suppose thatPrecedes(n,a). Then, by definition, sincen is a natural number,Precedes+(0,n). So by Fact (3) aboutR+ (in the subsection on the Weak Ancestral in§4), it follows that Precedes*(0,a), and so bythe definition of Precedes+, it follows thatPrecedes+(0,a); i.e., a is anatural number.Theorem 5 now follows from the Lemma on Successors and the fact thatsuccessors of natural numbers are natural numbers. With the proof ofTheorem 5, we have completed the proof of Frege's Theorem. Before weturn to the last section of this entry, it is worth mentioning themathematical significance of this theorem. 5.6 ArithmeticFrom Frege's Theorem, one can derive arithmetic. It is an immediateconsequence of the functionality of Predecessor that every number has aunique successor. That means we can define the successor function: n′ =df the xsuch that Precedes(n,x)We may then define the sequence of natural numbers succeeding 0 asfollows: 1 = 0′ 2 = 1′ 3 = 2′ etc.Moreover, the recursive definition of addition can now be given: n + 0 = n n + m′ = (n +m)′We may also officially define: n < m =df Precedes*(n,m) n ≤ m =df Precedes+(n,m)These definitions constitute the foundations of arithmetic. Frege hasinsightfully isolated a group of basic laws in which they may begrounded. (Readers interested in how these results are affected whenHume's Principle is combined with predicative second-orderlogic should consult Linnebo (2004).)6. Philosophical Questions Surrounding Frege's TheoremFrege's Theorem is an elegant derivation of the basic laws ofarithmetic which can be carried out independently of the portion ofFrege's system which led to inconsistency. Frege himself neveridentified "Frege's Theorem" as a "result". In Gg, heattempted to derive Hume's Principle and the Dedekind-Peano axioms fromBasic Law V, but once the contradiction became known to him, he neverofficially retreated to the ‘fall-back’ position ofclaiming that the proof of the Dedekind-Peano axioms from Hume'sPrinciple alone constituted an important result. One of several reasonswhy he didn't adopt this fall-back position is that he didn't regardHume's Principle as a sufficiently general principle — he didn'tbelieve it was strong enough, from an epistemological point of view, tohelp us answer the question, "How are numbers given to us?". We discussthe reasons for his attitude, among other things, in what follows. A discussion of the philosophical questions surrounding Frege'sTheorem should begin with some statement of how Frege conceived of hisown project when writing Begr, Gl,and Gg. It seems clear that epistemologicalconsiderations in part motivated Frege's work on the foundations ofmathematics. It is well documented that Frege had the following goal,namely, to explain our knowledge of the basic laws of arithmetic bygiving an answer to the question "How are numbers ‘given’to us?" which makes no appeal to the faculty of intuition. If Fregecould show that the basic laws of number theory are derivable fromanalytic truths of logic, then he could argue that we need only appealto the faculty of understanding (as opposed to some faculty ofintuition) to explain our knowledge of the truths of arithmetic.Frege's goal then stands in contrast to the Kantian view of the exactmathematical sciences, according to which general principles ofreasoning must be supplemented by a faculty of intuition if we are toachieve mathematical knowledge. The Kantian model here is that ofgeometry; Kant thought that our intuitions of figures and constructionsplayed an essential role in the demonstrations of geometrical theorems.(In Frege's own time, the achievements of Frege's contemporaries Pasch,Pieri and Hilbert showed that such intuitions were not essential.)6.1 Frege's Goals and Strategy in His Own WordsFrege's strategy then was to show that no appeal to intuition isrequired for the derivation of the theorems of number theory. This inturn required that he show that the latter are derivable using onlyrules of inference, axioms, and definitions that are purely analyticprinciples of logic. This view has become known as‘Logicism’. Here is what Frege says: [Begr,Preface, p. 5:] To prevent anything intuitive from penetrating here unnoticed, I hadto bend every effort to keep the chain of inferences free of gaps. [from the Bauer-Mengelbergtranslation in van Heijenoort (1967)] [Begr,Part III, §23:] Through the present example, moreover, we see how pure thought,irrespective of any content given by the senses or even by an intuitiona priori, can, solely from the content that results from its ownconstitution, bring forth judgements that at first sight appear to bepossible only on the basis of some intuition. … Thepropositions about sequences [R-series] in what follows farsurpass in generality all those that can be derived from any intuitionof sequences. [from the Bauer-Mengelbergtranslation in van Heijenoort (1967)] [Gl,§62:] How, then, are numbers to be given to us, if we cannot have any ideasor intuitions of them? Since it is only in the context of a propositionthat words have any meaning, our problem becomes this: To define thesense of a proposition in which a number word occurs. [from the Austin translation inFrege (1974)] [Gl,§87:] I hope I may claim in the present work to have made it probable thatthe laws of arithmetic are analytic judgements and consequently apriori. Arithmetic thus becomes simply a development of logic, andevery proposition of arithmetic a law of logic, albeit a derivativeone. [from the Austin translation inFrege (1974)] [Gg I,§0:] In my Grundlagen der Arithmetik, I sought to make itplausible that arithmetic is a branch of logic and need not borrow anyground of proof whatever from either experience or intuition. In thepresent book, this shall be confirmed, by the derivation of thesimplest laws of Numbers by logical means alone. [from the Furth translation inFrege (1967)] [Gg II,Appendix:] The prime problem of arithmetic is the question, In what way are we toconceive logical objects, in particular, numbers? By what means are wejustified in recognizing numbers as objects? Even if this problem isnot solved to the degree I thought it was when I wrote this volume,still I do not doubt that the way to the solution has been found. [from the Furth translation inFrege (1967)]6.2 The Basic Problem for Frege's StrategyThe basic problem for Frege's strategy, however, is that for hislogicist project to succeed, his system must at some point include(either as an axiom or theorem) statements that explicitly assert theexistence of certain kinds of abstract entities and it is not obvioushow to justify the claim that we know such explicit existentialstatements. Given our description of his system, it should be clearthat Frege's logical system includes existence claims for the followingentities: concepts (more generally, functions)extensions (more generally, courses-of-value or value-ranges)truth-valuesnumbersAlthough Frege attempted to reduce the latter two kinds of entities(truth-values and numbers) to extensions, the fact is that theexistence of concepts and extensions are implied by his Rule ofSubstitution and Basic Law V, respectively. Logic, it is often argued,should be free of such existence assumptions. A Kantian might wellcomplain both that explicit existence claims seem to be syntheticrather than analytic (i.e., such claims don't seem to be true in virtueof the meanings of the words involved) and that since the Rule ofSubstitution and Basic Law V imply existence claims, Frege cannot claimthat such principles are purely analytic principles of logic. If so,then some other faculty (such as intuition) might still be needed toaccount for our knowledge of (the existence claims of) arithmetic. 6.3 The Existence of ConceptsBoolos (1985) was the first to note that the Rule of Substitutioncauses a problem of this kind for Frege's program, since it isequivalent to a quite liberal existential claim, namely, theComprehension Principle for Concepts. Boolos suggests a defense forFrege with respect to this particular aspect of his logic, namely, toreinterpret (by paraphrasing) the second-order quantifiers so as toavoid commitment to concepts. (See Boolos (1985) for the details.)Boolos's suggestion, however, is one which would require Frege toabandon his realist theory of concepts. Moreover, although Boolos'suggestion might lead us to an epistemological justification of theComprehension Principle for Concepts, it doesn't do the same for theComprehension Principle for Relations, for his reinterpretation of thequantifiers works only for the ‘monadic’ quantifiers (i.e.,those ranging over concepts having one argument) and thus doesn't offera paraphrase for quantification over relational concepts. Another problem for a strategy of the type suggested by Boolos isthat if the second-order quantifiers are interpreted so that they donot range over a separate domain of entities, then there is nothingappropriate to serve as the denotations of λ-expressions.Although Frege wouldn't quite put it this way, we have seen that hissystem treats open formulas with free object variables as if theydenoted concepts. Although Frege doesn't use λ-notation, the useof such notation seems to be the most logically perspicuous way ofreconstructing his work. The use of such notation faces the sameepistemological puzzles that Frege's Rule of Substitution faces.To see why, note that the Principle of λ-Conversion: ∀y([λxφ(x)]y ≡φ(y/x))seems to be an analytic truth of logic. It says this: An object y exemplifies the complex propertybeing an x such that φ(x) if and only ify is an x such that φOne might argue that this is true in virtue of the very meaning of theλ-expression, the meaning of ≡, and the meaning of thestatement form Fx. However, λ-Conversion also impliesthe Comprehension Principle for Concepts, for the latter follows fromthe former by existential generalization: ∃F∀y(Fy ≡φ(y/x))The point here is that the fact that an existential claim is derivablecasts at least some doubt on the purely analytic status ofλ-Conversion. The question of how we obtain knowledge of suchprinciples is still an open question in philosophy. It is an importantquestion to address, since Frege's most insightful definitions are castusing quantifiers ranging over concepts and relations (e.g., theancestrals of a relation) and it would be useful to have aphilosophical explanation of how such entities and the principles whichgovern them become known to us. In contemporary philosophy, thisquestion is still poignant, since many philosophers do accept thatproperties and relations of various sorts exist.These entities are the contemporary analogues of Frege's concepts. 6.4 The Existence of ExtensionsWe have also seen (§2) that the Corollary to Basic Law V impliesthe existence of extensions. The question for Frege's project, then, iswhy should we accept as a law of logic a statement that implies theexistence of individuals? Frege did conceive of Basic Law V as a law oflogic: [Gg I,Preface, p. 3:] A dispute can arise, so far as I can see, only with regard to my BasicLaw concerning courses-of-values (V)… I hold that it is a law ofpure logic. [from the Furth translation inFrege (1967)]Moreover, he thought that an appeal to extensions would answer one ofthe questions that motivated his work: [Letter toRussell, July 28, 1902:] I myself was long reluctant to recognize ranges of values and henceclasses [sets]; but I saw no other possibility of placing arithmetic ona logical foundation. But the question is, How do we apprehend logicalobjects? And I have found no other answer to it than this, We apprehendthem as extensions of concepts, or more generally, as ranges of valuesof functions. [from the Kaal translation in Frege(1980)]Now it is unclear why Frege thought that he could answer the questionposed here with the reply "We apprehend numbers as extensions ofconcepts". He seems to think we can answer the obvious next question"How do we apprehend extensions?" by saying "by way of Basic Law V".His idea here seems to be that since Basic Law V is supposed to bepurely analytic or true in virtue of the meanings of its terms, weapprehend a pair of extensions whenever we truly judge that conceptsF and G are materially equivalent. Some philosophersargue that Frege would have been correct to argue in just this way (hadBasic Law V been consistent). They argue that Basic Law V (orconsistent principles having the same logical form) justifiesreference to the entities described in the left-side conditionby grounding such reference in the truth of the right-side condition.[12]But this, of course, raises an obvious problem. To justify referenceto extensions, we must first justify the claim that those extensionsexist. It is not clear that the claim that concepts are materiallyequivalent can justify such an existence claim. But given Frege's viewthat Basic Law V is analytic, it seems that he must hold that theright-side condition implies the corresponding left-side condition as amatter of meaning.[13]This view, however, runs up against the following argument. Supposethe right hand condition implies the left-side condition as a matter ofmeaning. That is, suppose that (R) implies (L) as a matter ofmeaning: (R) ∀x(Fx ≡Gx) (L) εF = εGNow note that (L) itself can be analyzed, from a logical point of view.The expression ‘ εF ’ is adefinite description (‘the extension of F’) andso, using Russell's theory of descriptions, (L) can be logicallyanalyzed as the claim: There is an object x and an object y suchthat: (1) x is a unique extension of F, (2) y is a unique extension of G,and (3) x = y.That is, for some defined or primitive notionExtension(x,F) (‘x is anextension of F’), (L) implies the analysis (D) as amatter of meaning: (D) ∃x∃y[Extension(x,F)& ∀z(Extension(z,F)→ z=x) & Extension(y,G) &∀z(Extension(z,G) →z=y) & x =y]But if (R) implies (L) as a matter of meaning, and (L) implies (D) as amatter of meaning, then (R) implies (D) as a matter of meaning. Thisseems doubtful. The material equivalence of F and Gdoes not imply the existence claim (D) as a matter of meaning, whatevernotion of meaning is involved. [This argument attempts to show why Va(i.e., the right-to-left direction of Basic Law V) is not analytic.Below, it will be adapted to show that the right-to-left direction ofHume's Principle is not analytic. See Boolos (1997, 307 - 309), forreasons why Vb and the left-to-right direction of Hume's Principle arenot analytic.] The moral to be drawn here is that the modern Fregean must attemptto explain our knowledge of existence claims for abstract objects suchas extensions head on, and not try to justify them indirectly,by attempting to justify claims that imply such existence claims. Evenif we follow Frege in conceiving of extensions as ‘logicalobjects’, the question remains as to how the very claims thatsuch objects exist can be true on logical or analytic grounds alone. Wemight agree that there must be logical objects of some sort if logic isto have a subject matter, but if Frege is to achieve his goal ofshowing that our knowledge of arithmetic is free of intuition, then thelogical knowledge with which he identifies arithmetical knowledge mustbe either be purely analytic or shown otherwise to be free ofintuition. We'll return to this theme in the final subsection.6.5 The Existence of Numbers and Truth-Values: The Julius Caesar ProblemGiven that the proof of Frege's Theorem makes no appeal to Basic Law V,some philosophers have argued Frege's best strategy for achieving hisgoal is to replace Basic Law V with Hume's Principle and argue thatHume's Principle is an analytic principle of logic.[14] However, we have just seen one reason why such a strategy does notsuffice. The claim that Hume's Principle is an analytic principle oflogic is subject to the same problem just posed for Basic Law V. Theequinumerosity of F and G does not, as a matter ofmeaning, imply (identity claims that entail) the existence ofnumbers. When we analyze "#F = #G" in the same waythat we analyzed "εF = εG" (i.e., byanalyzing away the operator # or definite description "the number ofFs" in terms of existence and uniqueness claims), it becomesclear that the equinumerosity of F and G does not,as a matter of meaning, imply the result of the analysis.Moreover, Frege had his own reasons for not replacing Basic Law Vwith Hume's Principle. One reason was that he thought Hume's Principleoffered no answer to the epistemological question, ‘How do wegrasp or apprehend logical objects, such as the numbers?’. ButFrege had another reason for not substituting Hume's Principle forBasic Law V, namely, that Hume's Principle would be subject to‘the Julius Caesar problem’. Frege first raises thisproblem in connection with an inductive definition of ‘n= #F’ that he tries out in Gl,§55. Concerning this definition, Frege says: [Gl,§55:] … but we can never — to take a crude example— decide by means of our definitions whether any concept has thenumber Julius Caesar belonging to it, or whether that conqueror of Gaulis a number or is not. [from the Austin translation inFrege (1974)]Frege raises this same concern again for a contextual definition thatgives a ‘criterion of identity’ for the objects beingdefined. In Gl §66, Frege considers the followingcontextual definition of ‘the direction of linex’: The direction of line a = the direction of lineb if and only if a is parallel tob.With regard to this definition, Frege says: [Gl,§66:] It will not, for instance, decide for us whether England is the sameas the direction of the Earth's axis— if I may be forgiven anexample which looks nonsensical. Naturally no one is going to confuseEngland with the direction of the Earth's axis; but that is no thanksto our definition of direction. [from the Austin translation inFrege (1974)]Now trouble for Hume's Principle begins to arise when we recognize thatit is a contextual definition that has the same logical form as thisdefinition for directions. It is central to Frege's view that thenumbers are objects, and so he believes that it is incumbentupon him to say which objects they are. But the ‘JuliusCaesar problem’ is that Hume's Principle, if considered as thesole principle offering identity conditions for numbers, doesn'tdescribe the conditions under which an arbitrary object, say JuliusCaesar, is or is not to be identified with the number of planets. Thatis, Hume's Principle doesn't define the condition‘#F=x’, for arbitrary x. It onlyoffers identity conditions when x is an object we know to be acardinal number (for then x=#G, for some G,and Hume's Principle tells us when #F=#G). In Gl, Frege solves the problem by giving hisexplicit definition of numbers in terms of extensions. (We describedthis in §4 above.) Unfortunately, this is only a stopgap measure,for when Frege later systematizes extensions in Gg,Basic Law V has the same logical form as Hume's Principle and the abovecontextual definition of directions. Frege is aware that the JuliusCaesar problem affects Basic Law V, though. In Gg I,§10, Frege appears to raise the Julius Caesar problem forextensions of concepts. With respect to Basic Law V, he says(remembering that for Frege, ε binds object variables and notconcept variables): [Gg I,§10:] …this by no means fixes completely the denotation of a namelike ‘ἐΦ(ε)’. We have only ameans of always recognizing a course-of-values if it is designated by aname like ‘ἐΦ(ε)’, by which it isalready recognizable as a course-of-values. But, we can neither decide,so far, whether an object is a course-of-values that is not given us assuch … [from the Furth translation inFrege (1967)]In other words, Basic Law V does not tell us the conditions under whichan arbitrarily chosen object x may be identified with somegiven extension, such as εF. Until recently, it was thought that Frege solved this problem in§10 by restricting the universal quantifier ∀x ofhis Gg system so that it ranges only over extensions.If Frege could have successfully restricted this quantifier toextensions, then when the question arises, is (arbitrarily chosen)object x is identical with εF, one couldanswer that x has to be the extension of some concept, sayG and that Basic Law V would then tell you the conditionsunder which x is identical to εF. On thisinterpretation of §10, Frege is alleged to have restricted thequantifiers when he identified the two truth values (The True and TheFalse) with the two extensions that contain just these objects asmembers, respectively. By doing this, it was thought that all of theobjects in the range of his quantifier ∀x inGg become extensions which have been identified assuch, for the truth values were the only two objects of his system thathad not been introduced as extensions or courses of value.However, recent work by Wehmeier (1999) suggests that, in §10,Frege was not attempting to restrict the quantifiers of his system toextensions (nor, more generally, to courses-of-values). The extensivefootnote to §10 indicates that Frege considered, but did not holdmuch hope of, identifying every object in the domain with the extensionconsisting of just that object.[15] But, more importantly, Frege later considers cases (inGg, Sections 34 and 35) which seem to presuppose thatthe domain contains objects which aren't extensions. (In thesesections, Frege considers what happens to the definition of‘x is a member of y’ when y isnot an extension.)[16]Even if Frege somehow could have successfully restricted thequantifiers of Gg to avoid the Julius Caesar problem,he would no longer have been able to extend his system to include namesof ordinary non-logical objects. For if he were to attempt to do so,the question, "Under what conditions is εF identicalwith Julius Caesar?", would then be legitimate but have no answer. Thatmeans his logical system could not be used for the analysis of ordinarylanguage. But it was just the analysis of ordinary language that ledFrege to his insight that a statement of number is an assertion about aconcept.6.6 Final ObservationsEven when we replace the inconsistent Basic Law V with the powerfulHume's Principle, Frege's work still leaves two questions unanswered:(1) How do we know that numbers exist?, and (2) How do we preciselyspecify which objects they are? The first question arises becauseHume's Principle doesn't seem to be a purely analytic truth of logic;by what faculty do we come to know (the truth of) the existential claimthat numbers exist if neither Hume's Principle nor this existentialclaim is analytically true? The second question arises because Frege'swork offers no general condition under which we can identify anarbitrarily chosen object x with a given number such as thenumber of planets; how then can Frege claim to have precisely specifiedwhich objects the numbers are within the domain of all logical andnon-logical objects? So questions about the very existence and identityof numbers still plague Frege's work. These two questions arise because of a limitation in the logicalform of these Fregean biconditional principles such as Hume's Principleand Basic Law V. These contextual definitions attempt to do two jobswhich modern logicians now typically accomplish with separateprinciples. A properly reformulated theory of ‘logical’objects should have: (1) a separate non-logical comprehensionprinciple which explicitly asserts the existence of logicalobjects, and (2) a separate identity principle which asserts theconditions under which logical objects are identical. Thelatter should specify identity conditions for logical objects in termsof their most salient characteristic, one which distinguishes them fromother objects. Such an identity principle would then be more specificthan the global identity principle for all objects (Leibniz's Law)which asserts that if objects x and y fall under thesame concepts, they are identical.By way of example, consider modern set theory. Zermelo set theory(Z) has a distinctive non-logical comprehension principle forsets: Subset Axiom of Z: ∀x[Set(x) →∃y[Set(y) &∀z(z ∈ y ≡ z∈ x & φ(z))]], where φ(z) is any formula in which the variablez is free and which has no free variablesyZ has a separate identity principle: Identity Principle for Sets: Set(x) & Set(y) →[∀z(z ∈ x ≡ z∈ y) → x = y]Note that the second principle offers identity conditions in terms ofthe most salient features of sets, namely, the fact that they, unlikeother objects, have members. The identity conditions for objects whicharen't sets, then, can be the standard principle thatidentifies objects whenever they fall under the same concepts. Thisleads us naturally to a very general principle of identity for anyobjects whatever: General Principle of Identity: x = y =df [Set(x) & Set(y) &∀z(z ∈ x ≡ z∈ y)] v [¬Set(x) &¬Set(y) & ∀F(Fx≡ Fy)]Now, if something is given to us as a set and we ask whetherit is identical with an arbitrarily chosen object x, thisspecifies a clear condition that settles the matter. The only questionsthat remain for the theory Z concern its existence principle: Do weknow that the comprehension principle is true, and if so, how? Thequestion of existence is thus laid bare. We do not approach it byattempting to justify a principle that implies the existence of setsvia definite descriptions which we don't yet know to be well-defined. In his classic essays (1987) and (1986), Boolos appears to recommendthis very procedure of using separate existence and identityprinciples. In those essays, he eschews the primitive mathematicalrelation of set membership and suggests that Frege formulate his theoryof numbers (‘Frege Arithmetic’) by using a singlenonlogical comprehension axiom which employs a specialinstantiation relation that holds between a concept G and anobject x whenever, intuitively, x is an extensionconsisting solely of concepts and G is a concept‘in’ x. He calls this nonlogical axiom‘Numbers’ and uses the notation‘Gηx’ to signify that G isin x: Numbers: ∀F∃!x∀G(Gηx ≡ G≈F)[See Boolos (1987), p. 5; and (1986), p. 140.] This principle assertsthat for any concept F, there is a unique object whichcontains in it all and only those concepts G which areequinumerous to F. Boolos then makes two observations: (1)that Frege can then define #F as "the unique object xsuch that for all concepts G, G is in x iffG is equinumerous to F", and (2) that Hume'sPrinciple is derivable from Numbers. [See Boolos (1986), p. 140.] Giventhese observations, we know from our work in §§4 and 5 abovethat Numbers suffices for the derivation of the basic laws ofarithmetic. Since Boolos calls this principle ‘Numbers’, it is nostretch to suppose that he would accept the following explicitreformulation (in which ‘Number(x)’ is anundefined, primitive notion): Numbers: ∀F∃!x[Number(x) &∀G(Gηx ≡G≈F)]Though Boolos doesn't explicitly formulate an identity principle tocomplement Numbers, it seems clear that the following principle wouldoffer identity conditions in terms of the most distinctive feature ofnumbers: Identity Principle for Numbers: Number(x) & Number(y) →[∀G(Gηx ≡Gηy) → x = y]It is then straightforward to formulate a general principle ofidentity, as we did in the case of the set theory Z: General Principle of Identity: x = y =df [Number(x) & Number(y) &∀F(Fηx ≡Fηy)] v [¬Number(x) &¬Number(y) & &foral | |
