This is a file in the archives of the Stanford Encyclopedia of Philosophy. 
version history

Stanford Encyclopedia of PhilosophyA  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z

last substantive content change

Although the inconsistency in Frege's Grundgesetze is widely known, it is not very well known that a deep theoretical accomplishment can be extracted from his work. The Grundgesetze contains all the essential steps of a valid proof (in secondorder logic) of the fundamental propositions of arithmetic from a single consistent principle. This consistent principle, known in the literature as "Hume's Principle", asserts that for any concepts F and G, the number of Fthings is equal to the number Gthings if and only if there is a onetoone correspondence between the Fthings and the Gthings. In the Grundgesetze, Frege used Basic Law V to derive Hume's Principle, but the derivations of the fundamental propositions of arithmetic from Hume's Principle do not essentially require Basic Law V. So by setting aside the derivation of Hume's Principle from the inconsistent Basic Law V and focusing on Frege's proofs of the basic propositions of arithmetic, his theoretical accomplishment emerges much more clearly, for his work shows us how to prove the Dedekind/Peano axioms for number theory from Hume's Principle in secondorder logic. This achievement, which involves some remarkably subtle chains of definitions 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 detail the essential features of Frege's logical systems, (2) to work through the derivations involved in Frege's Theorem, and (3) to frame the most important philosophical questions that arise in connection with this theorem. In addition, we hope to prepare students of Frege to read his original work (in translation) and to prepare the reader to understand a number of excellent articles in the secondary literature on Frege's work.
To accomplish these goals, we presuppose only a familiarity with the firstorder predicate calculus. We show how to extend this language and logic to include the most salient features of Frege's secondorder predicate calculus, his theory of concepts, and his theory of extensions. Our discussion will be largely based upon material drawn from Frege's three principal published works:
In this section, we describe the language and logic of Frege's predicate calculus. We explain his functionargument analysis of atomic sentences and his definition of concepts in terms of functions, give examples of his ‘concept script’, and discuss the Rule of Substitution in his logic. We also show how Frege's Rule of Substitution corresponds to a comprehension principle for concepts in secondorder logic, and we introduce and explain λnotation to help us distinguish open formulas and complex names of concepts. Readers who are already familiar with these ideas may wish to skip ahead to Section 2.
In Begr, Frege invented the predicate calculus. It will soon become clear that the language and logic of his predicate calculus are ‘secondorder’. The language included not only the variables x,y,z, … , which range over objects, but also included the variables ƒ,g,h, … , which range over functions. Frege rigidly distinguished objects from functions and so we may think of these variables as ranging over separate, mutually exclusive domains. Frege took functional application ‘ƒ(x)’ as the principal operation for forming complex names of objects in his language. The expression ‘ƒ(x)’ denotes the object to which the function ƒ maps the object x. Frege called the object x the ‘argument’ of the function ƒ and called ƒ(x) the ‘value’ of the function. Since Frege also recognized two special objects he called truthvalues (The True and The False), he defined a concept to be any function that always maps its arguments to truthvalues. For example, whereas ‘x^{2} +3’ and ‘fatherof(x)’ denote ordinary functions, the expressions ‘Happy(x)’ and ‘x > 5’ denote concepts. The former denotes a concept which maps any object 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 than 5 to The True and all other objects to The False. Given that concepts like being happy and being greater than 5 map their arguments to truth values, the atomic sentences of Frege's language, such as ‘Happy(b)’ and ‘4 > 5’, become names of truthvalues.
In what follows, we use the symbols F,G, … as variables ranging over concepts and we often write ‘Fx’ (instead of ‘F(x)’) to express the claim that concept F maps x to The True. When this claim is true, Frege would say that x falls under the concept F.
When ƒ is a function of two arguments x and y and ƒ always maps its pair of arguments to a truth value, Frege would say that ƒ is a relation. We shall use the expression ‘Rxy’ (or sometimes ‘R(x,y)’) to assert that the relation R maps x and y (in that order) to The True. In what follows, we shall sometimes write the symbol that denotes a mathematical relation in the usual ‘infix’ notation; for example, ‘>’ denotes the greaterthan relation in the expression ‘x > y’.
Now that we have explained Frege's analysis of the atomic statements ‘Fx’ and ‘Rxy’ familiar to modern students of logic, we turn next to the more complex statements of his language. Frege developed his own graphical notation for asserting complex statements involving negations, conditionals, and universal quantification. If we ignore the fact that Frege used Gothic letters as variables of quantification, certain letters as bound variables in names of coursesofvalues, and certain other letters as placeholders in the names of functions, then Frege's notation for the logical notions ‘not’, ‘ifthen’, ‘every’ and ‘some’ can be described in the following table:
So, for example, whereas a modern logician would symbolize the claim ‘All As are Bs’ as:
Logical Notion Modern Notation FregeStyle Notation It is not the case that Fx ¬Fx If Fx then Gy Fx → 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
∀x(Ax → Bx)Frege would symbolize this claim as follows:
However, since Frege's notation was never adopted as a standard, we shall instead use the more familiar modern notation in the remainder of this essay. [See Beaney (1997, Appendix 2), Furth (1967), and Reck & Awodey (2004, 26–34) for a more detailed introduction to Frege's notation.] We shall assume that the reader is familiar with the fact that negations (‘¬φ’) and conditionals (‘φ → ψ’) can be used to define the other molecular formulas such as conjunctions (‘φ & ψ’), disjunctions (‘φ v ψ’), and biconditionals (‘φ ≡ ψ’). Moreover, it is important to mention that Frege took identity statements of the form ‘x = y’ as primitive in his language. Whereas ‘2^{2} = 4’ names The True, ‘2^{2} = 3’ names The False. The statement form ‘ƒ(x) = y’ plays an important role in Frege's axioms and definitions. Note finally that since Frege allowed quantification over both objects and functions, the language of his predicate calculus becomes ‘secondorder’.
Although these axioms of Frege's logic are familiar to us, the rules of inference in Frege's system are not as familiar. The reason is that the rules govern not only his graphical notation for molecular and quantified formulas, but also his special purpose symbols, such as certain lowercase letters used as placeholders, certain Gothic letters and letters used as bound variables, and various other signs of his system we have not yet mentioned. Since these will play no role in the discussion that follows, we shall again simplify our discussion by assuming that the usual rules of the modern secondorder predicate calculus apply to Frege's system. Again, these are essentially the same as the rules for the firstorder predicate calculus, except for the addition of new rules for the secondorder quantifiers that correspond to the generalization and instantiation rules (i.e., introduction and elimination rules) for the firstorder quantifiers.
Rule of Substitution (Simplified Version):To see this rule in action, first consider the following theorem of (Frege's) secondorder predicate logic:
In any statement of the form …Fx… (in which the variable F is free) which is derivable as a theorem of logic, we may substitute any open formula φ(x) (with the free variable x) for all the occurrences of the atomic formula Fx in …Fx… .
(A) ∀x(Fx ≡ Fx).Now Frege's Rule of Substitution not only allows us to substitute the atomic formula ‘Ox’ (which might represent the claim ‘x is odd’) for the formula Fx to derive the true statement ∀x(Ox ≡ Ox), but also allows us to substitute complex formulas with a free variable x for ‘Fx’. So, for example, we are allowed substitute the formula ‘Ox & x > 5’ (‘x is odd and x is greater than 5’) for ‘Fx’ in (A) to derive the following from (A):
(B) ∀x(Ox & x > 5 ≡ Ox & x > 5)Inferences such as this will be valid no matter what complex formula with x free we substitute for Fx in our universal claim (A). This is what justifies Frege's Rule of Substitution.
In what follows, we will assume that the Rule of Substitution can be generalized to relations, so that we can uniformly replace the formula Rxy (in a theorem of logic with R free) by a complex formula φ(x,y) (in which both x and y are free).
∃G∀x(Gx ≡ Fx)Frege's Rule of Substitution now allows us to substitute any formula with free variable x for Fx. In other words, every instance of the following Comprehension Principle for Concepts is derivable in Frege's system:
Comprehension Principle for Concepts:Similarly, from the theorem of logic:
∃G∀x(Gx ≡ φ(x)),
where φ(x) is any formula which has x free and which has no free Gs.
∀x∀y(Rxy ≡ Rxy)one can generalize and then use the Rule of Substitution to derive the following Comprehension Principle for Relations:
Comprehension Principle for Relations:Although Frege didn't explicitly formulate these Comprehension Principles, they constitute a very important generalization about his system that reveals its underlying theory of concepts and relations. We can see these principles at work if we return to the example used above. The following is an instance of the Comprehension Principle for Concepts and so constitutes a theorem of Frege's system:
∃R∀x∀y(Rxy ≡ φ(x,y)),
where φ(x,y) is any formula with x and y free and which has no free Rs.
∃G∀x(Gx ≡ Ox & x > 5)This asserts: there exists a concept G such that for every object x, x falls under G if and only if x is odd and greater than 5. We can see, therefore, that Frege's Rule of Substitution essentially treats an open formula like ‘Ox & x > 5’ as if it were a name of a complex concept. Similarly, the following is an instance of the Comprehension Principle for Relations:
∃R∀x∀y(Rxy ≡ Ox & x > y)This asserts the existence of a relation that objects x and y bear to one another just in case the complex condition Ox & x > y holds.
Logicians nowadays typically distinguish the open formula φ(x) from the corresponding name of a concept. They use the notation [λx Ox & x > 5] as the name of the concept being an object x such that x is odd and x is greater than 5 (or, more naturally, ‘being odd and greater than 5’). The termforming operator λx (‘being an x such that’) combines with a formula φ(x) in which x is free to produce [λx φ(x)]. The λexpression is a name of the concept expressed by the formula. This notation can be extended for relational concepts. The expression:
[λxy Ox & x > y]names the 2place relation being an x and y such that x is odd and greater than y. So we will use expressions of the more general form [λxy φ(x,y)] in what 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 that predicative expressions such as ‘( ) is happy’ are incomplete expressions and that the concepts they denoted were unsaturated. We shall not discuss Frege's reasons for this in this entry; see his essay “Concept and Object”.
This λnotation is governed by the following simple logical principle known as λConversion. Let φ(x) be any formula in which the variable x is free, and let φ(y/x) be the result of substituting the variable y for x everywhere in φ(x). Then the principle of λConversion is:
λConversion:This asserts that an object y falls under the concept [λx φ(x)] if and only if φ(y/x) holds. So, using our example, the following is an instance of λconversion:
∀y([λx φ(x)]y ≡ φ(y/x))
∀y([λx Ox & x > 5]y ≡ Oy & y > 5)This asserts that an object y falls under the concept being odd and greater than 5 if and only if y is odd and greater than 5. Note that when the variable y is instantiated to some object term, the resulting instance of λConversion is a biconditional. Some logicians call the rule of inference derived from the righttoleft direction of such biconditionals ‘λAbstraction’. For example, the inference from
O6 & 6 > 5to
[λx Ox & x > 5]6is justified by λAbstraction.
The principle of λConversion can be generalized, so that it covers relations as well:
∀z∀w([λxy φ(x,y)]zw ≡ φ(z/x, w/y))The reader should construct an instance of this principle using our example [λxy Ox & x > y].
To reiterate, then, Frege's Rule of Substitution allows us to instantiate φ(x) for the free variable F in theorems of logic as if φ(x) were a λexpression and constituted a name of a concept. In what follows, we shall make use of this λnotation. Indeed, λnotation is required if we are to give a more precise formulation of the Rule of Substitution; the precise formulation of the rule for concepts is:
Rule of Substitution:(The formulation for relations is similar.) Moreover, the principle of λConversion simplifies the strict proof of the equivalence of Frege's Rule of Substitution and the Comprehension Principle for Concepts. As it turns out, not only does Frege's Rule of Substitution imply the Comprehension Principle for Concepts, but the converse also holds: the Comprehension Principle for Concepts implies the Rule of Substitution. [For a proof sketch, see Boolos (1985) pp. 161162. Note that instead of [λx φ(x)], Boolos uses the notation {a: Aa}; elsewhere, in (1987) for example, Boolos uses the notation [x : A(x)] to denote concepts.]
The λexpression [λx φ(x)] may be uniformly substituted for the occurrences of the variable F in any theorem of logic containing F free.
It is important to appreciate that the system we have just described, i.e., Frege's system of secondorder logic and the theory of (relational) concepts that he developed in Begr, is consistent. (It is only later in Gg, when Frege added Basic Law V to this consistent basis, that the resulting system became inconsistent.) Its underlying comprehension principle for concepts ensures that the domain of concepts is very rich. Each concept has a negation, every pair of concepts has a conjunction, every pair of concepts has a disjunction, etc. The reader should be able to write down instances of the comprehension principle which demonstrate these claims. In Part III of Begr, Frege applied his system to the ‘theory of sequences’ (we call these ‘Rseries’ below). It is here that Frege presents his celebrated definition of the ‘ancestral’ of a relation and first proves the generalized analogues of the principle of mathematical induction, as well as various structural properties of the ancestral. We shall postpone further discussion of this work until §§4 and 5, where we reproduce Frege's definition of the ancestral of a relation and show how Frege incorporated this definition into the proof of mathematical induction, respectively.
The principle that undermined Frege's system (Basic Law V) was one that attempted to systematize the notions ‘courseofvalues of a function’ and ‘extension of a concept’. The courseofvalues of a function ƒ is something like a set of ordered pairs that records the value ƒ(x) for every argument x. For example, the courseofvalues of the function father of x records, among other things, that Bill Clinton is the value of the function when Chelsea Clinton is the argument. The courseofvalues for the function x^{2} records, among other things, that the number 4 is the value when the number 2 is the argument, that 9 is the value when 3 is the argument, etc. The extension of a concept is something like the set of all objects that fall under the concept. For example, the extension of the concept x is a positive even integer less than 8 is something like the set consisting of the numbers 2, 4,and 6 (strictly speaking, the extension of this concept records The True as the value when 2, 4 and 6 are supplied as argument, and records that The False is the value when anything else is supplied as argument). Since concepts are just functions from objects to truth values, the extension of a concept is simply the courseofvalues which records which objects that concept maps to The True.
and
to designate the courseofvalues of the functions ƒ and g, respectively. In this notation, the symbols and bind the object variables epsilon and alpha, respectively, and the resulting expression denotes a courseofvalues.
Here is a pair of examples of Frege's notation for coursesofvalues and the second are examples of extensions. This pair of examples comes from Gg I, §9. Frege writes:
to denote the courseofvalues of the function:
x^{2} − xHe also uses:
to denote the courseofvalues of the function:
x · (x − 1)Frege then notes that:
∀x[x^{2} − x = x · (x − 1)]always has the same truth value as the following:
This equivalence will become embodied in Basic Law V. The reader should now be in a position to see how the following formulation of Basic Law V corresponds to Frege's formulation in Gg I, §20:
Basic Law V:This principle asserts: the courseofvalues of the function ƒ is identical to the courseofvalues of the function g if and only if ƒ and g map every object to the same value. [Actually, Frege uses an identity sign instead of the biconditional sign as the main connective of the principle. The reason he could do this is that, in his system, when two sentences are materially equivalent, they name the same truth value.] We shall soon explain why this principle is inconsistent.
Here is an example of our notation involving a pair of complex concepts. Consider the concept that which when added to 4 equals 5, or using λnotation, the following concept:
[λ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 to 2^{2} equals 5 (i.e., [λx x+2^{2}=5]). We use the following notation to denote the extension of this concept:
ε[λx x+2^{2}=5]Note that it seems natural to identify these two extensions whenever all and only the objects that fall under the first concept fall under the 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 the extension 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, and that Frege rigorously distinguished objects and concepts and supposed them to constitute mutually exclusive domains.
{x  x + 4 = 5}In what follows, we sometimes render Frege's notation in this more modern notation.{x  x + 2^{2} = 5}
Frege took advantage of his secondorder language to define what it is for an object to be a member of an extension. Although Frege used the notation x ∩ y to designate the membership relation, we shall follow the more usual practice of using x ∈ y. (Readers should check that their web browsers are correctly displaying the difference between the membership sign ∈ and the epsilon operator ε.) Thus, the following captures the main features of Frege's definition of membership in Gg I, §34:
x ∈ y =_{df} ∃G(y=εG & Gx)In other words, x is an element of y just in case x falls under a concept of which y is the extension. For example, given this definition, one can prove that John is a member of the extension of the concept being happy (formally: j ∈ εH) from the premise that John falls under the concept being happy (‘Hj’). Here is a simple proof:
Some readers may wish to examine a somewhat more complex example, in which the above definition of membership is used to prove that 1 ∈ ε[λx x+2^{2}=5] given the premise that 1+2^{2}=5. (A More Complex Example)
1. Hj Premise 2. εH = εH = Introduction 3. εH = εH & Hj from 1,2, by & Introduction 4. ∃G(εH = εG & Gj) from 3, by Existential Introduction 5. j ∈ εH from 4, by definition of ∈
Basic Law V has the following special case, when the functions ƒ and g are the concepts F and G:
Basic Law V (Special Case):[Here, again, Frege used an identity sign in place of the biconditional signs.] In this special case, Basic Law V asserts: the extension of the concept F is identical to the extension of the concept G if and only if all and only the objects that fall under F fall under G (i.e., if and only if the concepts F and G are materially equivalent). In more modern guise, Frege's Basic Law V asserts that the set of Fs is identical to the set of Gs if and only if F and G are materially equivalent:
εF = εG ≡ ∀x(Fx ≡ Gx)
{xFx} = {yGy} ≡ ∀z(Fz ≡ Gz)
The example discussed above can now be seen as an instance of Basic Law V:
ε[λy y+4=5] = ε[λy y+2^{2}=5] ≡ ∀x([λy y+4=5]x ≡ [λy y+2^{2}=5]x)This simply asserts that the extension of the concept that which added to 4 yields 5 is identical to the extension of the concept that which added to 2^{2} yields 5 if and only if all and only the objects that when added to 4 yield 5 are objects that when added to 2^{2} yield 5.
Basic Law V looks like it asserts a very general truth. In fact, it does correctly imply the Law of Extensions and the Principle of Extensionality. The Law of Extensions (cf. Gg I, §55, Theorem 1) asserts that an object is a member of the extension of a concept if and only if it falls under that concept:
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 we may formally represent and derive the principle of extensionality as follows:
∀F∀x(x ∈ εF ≡ Fx)
Principle of Extensionality:Despite these deceptive successes of Basic Law V, the fact is that it can't be consistently added to Frege's system. In the following subsections, we shall show how Basic Law V proves to be inconsistent with the rest of Frege's secondorder logic and theory of concepts. The proofs depend essentially on the secondorder character of Frege's system and on the secondorder definition of the membership relation. Frege was made aware of the inconsistency by Bertrand Russell, who sent him a letter formulating ‘Russell's Paradox’ just as the second volume of Gg was going to press. Frege quickly added an Appendix to the second volume, describing two distinct ways of deriving a contradiction from Basic Law V. The first establishes the contradiction directly, without any special definitions. The second deploys the membership relation and more closely follows Russell's Paradox. We will examine both derivations of the contradiction in what follows.
Extension(x) & Extension(y) → [∀z(z ∈ x ≡ z ∈ y) → x = y]
Both derivations of the contradiction turn on an important corollary to Basic Law V, namely, that every concept has an extension:
Corollary to Basic Law V:To see that this is a consequence of Basic Law V, note that when we instantiate the variable G to F in Basic Law V, we can establish:
∀G∃x(x = εG)
εF = εF ≡ ∀x(Fx ≡ Fx)Since the right side of this instance of Law V can be derived by logic alone, it follows that εF = εF. But, then, by existential generalization, it follows that:
∃x(x = εF)But now our Corollary follows by universal generalization on the concept variable F. However, the combination of Frege's Rule of Substitution (which ensures that there is a concept corresponding to every formula with free variable x) and Basic Law V (which ensures that each concept has an extension that behaves in a certain way), turns out to be a volatile mix.
∃F(x=εF & ¬Fx)From the Comprehension Principle for Concepts (or Frege's Rule of Substitution), we know that there exists a concept corresponding to this formula and we may use the following λexpression to name it:
[λx ∃F(x=εF & ¬Fx)]Now by the Corollary to Basic Law V, the extension of this concept 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.)
∀x(x ∈ εF ≡ Fx)Then by generalizing on the extension εF, it follows that:
∃y∀x(x ∈ y ≡ Fx)Now at this point, we may universally generalize on the variable F to get the following secondorder Naive Comprehension Axiom for extensions, which asserts that for every concept F, there is an extension which has as members all and only the objects that fall under F:
Naive Comprehension Axiom for Extensions:Alternatively, instead of generalizing, we could have appealed to Frege's Rule of Substitution to show that all of the instances of the following Naive Comprehension Schema for extensions are derivable in Frege's system:
∀F∃y∀x(x ∈ y ≡ Fx)
Naive Comprehension Schema for Extensions:This asserts that for any formula φ(x) defining a condition on objects, there is an extension which has as members all and only the objects that meet the condition.
∃y∀x(x ∈ y ≡ φ(x)), where φ(x) is any formula in which x is free and which contains no free occurrences of y
Both the Naive Comprehension Axiom and the Naive Comprehension Schema immediately give rise to Russell's Paradox in the context of Frege's logic. In the case of the axiom, the contradiction follows by instantiating the quantified variable F to the concept [λz ¬(z ∈ z)]. In the case of the schema, the contradiction follows by taking φ(x) to be ¬(x ∈ x), as follows:
∃y∀x(x ∈ y ≡ ¬(x ∈ x))In either case, the proof of the contradiction goes through. The derivation of the contradiction from the above instance of the schema is particularly easy. For suppose the object b is such a y. Then:
∀x(x ∈ b ≡ ¬(x ∈ x))But we can now instantiate the universal claim to the object b to yield the following contradiction:
b ∈ b ≡ ¬(b ∈ b)(See the entry on Russell's Paradox.)
To analyze the inconsistency in Frege's system in more detail, it is important to discuss the conditions under which concepts are to be identified. Although Frege did not believe that statements of the form ‘F = G’ were meaningful, it is evident from the study of Gg that the material equivalence of concepts F and G serves as the proxy identity conditions of F and G. So, whenever it is not the case that all and only the objects that fall under F fall under G, F and G are distinct concepts.
With this in mind, we can see how the paradox is engendered. Recall first that the Corollary to Basic Law V reveals that Basic Law V correlates each concept with an extension. Each direction of Basic Law V requires that this correlation have certain properties. We shall see, for example, that the righttoleft direction of Basic Law V (i.e., Va) requires that no concept gets correlated with two distinct extensions. [Frege uses the label ‘Va’ to designate the righttoleft direction of Basic Law V. See, for example, Gg I, §52. However, many commentators use ‘Va’ to designate the lefttoright 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:If we think in terms of its contraposition and remember the identity conditions for concepts, Va in effect asserts that whenever extensions differ, the concepts with which they are correlated differ. This means that the correlation between concepts and extensions that Basic Law V sets up must be a function—no concept gets correlated with two distinct extensions (though for all Va tells us, distinct concepts might get correlated with the same extension). Frege noted (in the Appendix to Gg II) that this direction of Basic Law V doesn't seem problematic.
∀x(Fx ≡ Gx) → εF = εG
However, the lefttoright direction of Basic Law V (i.e., Vb) is more serious. Vb asserts:
Basic Law Vb:If we consider the contrapositive of this and remember the identity conditions for concepts, then Vb, in effect, asserts that whenever the concepts F and G differ, the extensions of F and G differ. So, the correlation that Basic Law V sets up between concepts and extensions will have to be onetoone; i.e., it correlates distinct concepts with distinct extensions. Since every concept is correlated with some extension, there have to be at least as many extensions as there are concepts.
εF = εG → ∀x(Fx ≡ Gx)
But the problem is that Frege's system as a whole requires that there be more concepts than extensions. The requirement that there be more concepts than extensions is imposed jointly by the Comprehension Principle for Concepts and the new significance this principle takes on in the presence of Basic Law V. The Comprehension Principle for Concepts asserts the existence of a concept for every condition on objects expressible in the language. Now although it may seem that this principle, in and of itself, forces the domain of concepts to be larger than the domain of objects, it is a modeltheoretic fact that there are models of secondorder logic with the Comprehension Principle for Concepts (but without Basic Law V) in which the domain of concepts is not larger than the domain of objects.^{[1]} However, the Comprehension Principle for Concepts takes on new significance when Basic Law V is added to Frege's system. The synergism of the Comprehension Principle for Concepts and Basic Law V force the domain of concepts to be larger than the domain of objects (and so larger than the domain of extensions). However, as we saw in the last paragraph, Vb requires that there be at least as many extensions as there are concepts.
Thus, Frege's secondorder logic and theory of extensions together required the impossible situation in which the domain of concepts has to be strictly larger than the domain of extensions while at the same time the domain of extensions has to be as large as the domain of concepts.
Recently, there has been a lot of interest in discovering ways of repairing Frege's system. The traditional view is that one must either restrict Basic Law V or restrict the Comprehension Principle for Concepts. Recently, Boolos (1986, 1993) developed one of the more interesting suggestions for revising Basic Law V without abandoning secondorder logic and its comprehension principle for concepts. On the other hand, there have been many suggestions for restricting the Comprehension Principle for Concepts. The most severe of these is to abandon secondorder logic (and the Comprehension Principle for Concepts) altogether. SchroederHeister (1987) conjectured that the firstorder portion of Frege's system (i.e., the system which results by adding Basic Law V to the firstorder predicate calculus) was consistent and this was proved by T. Parsons (1987) and Burgess (1998).^{[2]} Heck (1996) and Wehmeier (1999) consider less drastic moves. They investigate systems of secondorder logic which have been extended by Basic Law V but in which the Comprehension Principle for Concepts is restricted in some way. See also Anderson & Zalta (2004) and Antonelli & May (2005) for different approaches to repairing Frege's system.
We will not discuss the above research further in the present entry, for it is not clear which of their alternatives, or others, would have been acceptable to Frege. Instead, we focus on the theoretical accomplishment revealed by Frege's work in Gg.
Despite the failure of Basic Law V, Frege validly proved a rather deep fact about the natural numbers, namely, that the Dedekind/Peano axioms for number theory could be derived in secondorder logic with the help of a single additional principle. The principle in question is known as Hume's Principle (discussed below). Although both C. Parsons (1965) and Wright (1983) had recently noted that Hume's Principle was powerful enough for the derivation of the Dedekind/Peano axioms, Heck (1993) showed that although Frege did use Basic Law V to derive Hume's principle, his (Frege's) subsequent derivations of the Dedekind/Peano axioms of number theory from Hume's Principle never made an essential appeal to Basic Law V. Since Hume's Principle just by itself is consistent with secondorder logic, this means that Frege validly derived the basic laws of number theory. It will be the task of the next few sections to explain Frege's accomplishments in this regard. We will do this in two stages. In §3 we study Frege's attempt to derive Hume's Principle from Basic Law V by analyzing cardinal numbers as extensions. Then, we put this aside in §§4 and 5 to examine how Frege was able to derive the Dedekind/Peano axioms of number theory from Hume's Principle alone.
Frege then moves from this realization, in which statements of numbers are analyzed as predicating secondlevel numerical concepts of firstlevel concepts, to develop an account of the cardinal and natural numbers as ‘selfsubsistent’ objects. He introduces a ‘cardinality operator’ on concepts, namely, ‘the number belonging to the concept F’, which will designate the cardinal number which numbers the objects falling under 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 denotes an object (or ranges over objects).) Frege offers both an implicit and an explicit definition of this operator in Gl. Both of these definitions require a preliminary definition of when two concepts F and G are in onetoone correspondence or ‘equinumerous’. After developing the definition of equinumerosity, we then discuss Frege's implicit and explicit definition of the number of Fs.
∃!xφ(x) =_{df} ∃x[φ(x) & ∀y(φ(y/x) → y=x)]Now, in terms of this logical notion of unique existence, we can state Frege's definition of equinumerosity (Gl, §71, 72) as follows:
F and G are equinumerous (or, F and G are in onetoone correspondence) just in case there is a relation R such that: (1) every object falling under F is Rrelated to a unique object falling under G, and (2) every object falling under G is such that there is a unique object falling under F which is Rrelated to it.If we let ‘F ≈ G’ stand for equinumerosity, then the definition of this notion can be rendered formally as follows:
F ≈ G =_{df}To see that Frege's definition of equinumerosity works correctly, consider the following two examples. In the first example, we have two concepts that are equinumerous:
∃R[∀x(Fx → ∃!y(Gy & Rxy)) & ∀x(Gx → ∃!y(Fy & Ryx))]
Although there are several different relations R which would demonstrate the equinumerosity of F and G the particular relation used in Figure 1 is:
Figure 1
R_{1} = [λxy (x=a & y=f) v (x=b & y=g) v (x=c & y=e)]It is a simple exercise to show that R_{1}, as defined, is a ‘witness’ to the equinumerosity of F and G (according to the definition).
In the second example, we have two concepts that are not equinumerous:
In this example, no relation R can satisfy the definition of equinumerosity.
Figure 2
Clearly, then, the concepts F and G will be equinumerous whenever the number of objects falling under F is identical to the number of objects falling under G. This fact will be codified by Hume's Principle. Before moving ahead to the discussion of this principle, the reader should convince him or herself of the following four facts: (1) that the material equivalence of two concepts implies their equinumerosity, (2) that equinumerosity is reflexive, (3) that equinumerosity is symmetric, and (4) that equinumerosity is transitive. In formal terms, the following facts are provable:
Facts About Equinumerosity:The proofs of these facts, in each case, require the identification of a relation that is a witness to the relevant equinumerosity claim. In some cases, it is easy to identify the relation in question. In other cases, the reader should be able to ‘construct’ such relations (using λnotation) by considering the examples described above. Facts (2)  (4) establish that equinumerosity is an ‘equivalence relation’ which divides up the domain of concepts into ‘equivalence classes’ of equinumerous concepts. Material equivalence is also an equivalence relation which divides up the domain of concepts into equivalence classes of materially equivalent concepts.
1. ∀x(Fx ≡ Gx) → F ≈ G
2. F ≈ F
3. F ≈ G → G ≈ F
4. F ≈ G & G ≈ H → F ≈ H
Hume's Principle:Using our notation ‘#F’ to abbreviate ‘the number of Fs’, we may formalize Hume's Principle as follows:
The number of Fs is identical to the number of Gs if and only if F and G are equinumerous.
Hume's Principle:This contextual definition governing cardinal numbers is the basic principle upon which Frege forged his development of the theory of natural numbers.^{[4]} In Gl, Frege sketched the derivations of the basic laws of number theory from Hume's Principle; these sketches were developed into more rigorous proofs in Gg I. We will examine these derivations in the following sections.
#F = #G ≡ F ≈ G
Once Frege had a contextual definition of #F, he then defined a cardinal number as any object which is the number of some concept:
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 to Basic Law V. Both are biconditionals asserting the equivalence of an identity among singular terms (the leftside condition) with an equivalence relation on concepts (the rightside condition). Indeed, both correlate concepts with certain objects. In the case of Hume's Principle, each concept F is correlated with #F. However, whereas Basic Law V problematically asserts that the correlation between concepts and extensions is onetoone, Hume's Principle only asserts that the correlation between concepts and numbers is manytoone. Hume's Principle often correlates distinct concepts with the same number. For example, the distinct concepts author of Principia Mathematica (‘[λx Axp]’) and number between 1 and 4 (‘[λx 1 < x < 4]’) are equinumerous (both both have two objects falling under them). So #[λx Axp] = #[λx 1 < x < 4]. Thus, Hume's Principle, unlike Basic Law V, does not require that the domain of numbers be as large as the domain of concepts. Indeed, Hume's Principle has recently been proved consistent with secondorder logic. This was shown independently by Burgess (1984) and Hazen (1985).
Before we examine the powerful consequences that Frege derived from Hume's Principle, it is worth digressing to describe his failed attempt to explicitly define ‘#F’ and to derive Hume's Principle from Basic Law V. The idea behind this attempt was the realization that if given any concept F, the notion of equinumerosity can be used to define the secondlevel concept being a concept G that is equinumerous to F (‘G ≈ F’). Frege found a way to collect all of the concepts equinumerous to a given concept F into a single extension. In Gl, he informally took this to be an extension consisting of firstorder concepts. In that work, he defined informally (§68):
the number of Fs =_{df}In terms of the example used at the end of the previous subsection, this definition identifies the number of the concept author of Principia Mathematica as the extension consisting of all and only those firstlevel concepts that are equinumerous to this concept; this extension has both [λx Axp] and [λx 1 < x < 4] as members. Frege in fact identifies the cardinal number 2 with this extension, for it contains all and only those concepts under which two objects fall. Similarly, Frege identifies the cardinal number 0 with the extension consisting of all those firstlevel concepts under which no object falls; this extension would include such concepts as unicorn, centaur, prime number between 3 and 5, etc. Frege's insight here inspired Russell to develop a somewhat similar definition in his work, and it is now common to see references to the socalled "FregeRussell definition of the cardinal numbers" as classes of equinumerous concepts or sets.^{[5]} Of course, this explicit definition of ‘the number of Fs’ stands or falls with a coherent conception of ‘extension’. We know that Basic Law V does not offer such a coherent conception.
the extension of the secondlevel concept: being a firstlevel concept equinumerous to F
Frege's Derivation of Hume's Principle in the GrundlagenHowever, in the development of Gg, Fregean extensions do not contain concepts as members but rather objects. So Frege had to find another way to express the explicit definition described in the previous subsection. His technique was to let extensions go proxy for their corresponding concepts. Since a full explanation of this technique and the proof of Hume's Principle in Gg would constitute a digression for the present exposition, we shall describe the details for interested readers on a separate page:
Frege's ‘Derivation’ of Hume's Principle in the GrundgesetzeAs noted on several occasions, the inconsistency in Basic Law V invalidated Frege's derivation of Hume's Principle. But Hume's Principle, in and of itself, is a powerful and consistent principle.
The insight behind Frege's analysis of the natural numbers was the realization that one can define the finite cardinal numbers in terms of the following concepts:
C_{0} = [λx x≠x]Note that starting with C_{1}, each concept C_{k} has the following property: all and only the numbers of concepts preceding C_{k} in the sequence fall under C_{k}. So, for example, the concepts preceding C_{3} are C_{0}, C_{1}, and C_{2}. Accordingly, all and only the following numbers fall under C_{3}: #C_{0}, #C_{1}, and #C_{2}.
C_{1} = [λx x = #C_{0}]
C_{2} = [λx x = #C_{0} v x = #C_{1}]
C_{3} = [λx x = #C_{0} v x = #C_{1} v x = #C_{2}]
etc.
Frege noticed that these concepts can be used, respectively, to define the the finite cardinal numbers, as follows:
0 = #C_{0}This insight, however, was only the first step in Frege's plan. He realized that though this seems to define a sequence of numbers with which we can identify the natural numbers, we have not as yet defined the concept ‘natural number’ so that it applies to all and only the cardinal numbers defined in the second sequence. Such a concept is required if we are to prove as theorems the following axioms of Dedekind/Peano number theory:
1 = #C_{1}
2 = #C_{2}
etc.
Dedekind/Peano Axioms for Number Theory:Moreover, Frege recognized the need to employ the Principle of Induction in the proof that every number has a successor. One cannot prove the claim that every number has a successor simply by producing the sequence of expressions for cardinal numbers (e.g., the second of the two sequences described above). All such a sequence demonstrates is that for every expression listed in the sequence, one can define an expression of the appropriate form to follow it in the sequence. This is not the same as proving that every natural number has a successor.
 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 natural numbers n and m such that m is the successor of n, the fact that n falls under F implies that m falls under F, then every natural number falls under F. (Principle of Induction)
 Every natural number has a successor.
x (immediately) precedes y if and only if there is a concept F and an object w such that: (a) w falls under F, (b) y is the number of Fs, and (c) x is the number of the concept object falling under F other than wIn formal terms, the definition takes the following form:
Precedes(x,y) =_{df}Even though we can't as yet assume that we have defined the natural numbers 1 and 2, we can use them intuitively to show that the definition properly predicts that Precedes(1,2) if given certain facts about the numbers of certain concepts. Let the expression ‘[λz Azp]’ denote the concept author of Principia Mathematica. Only Bertrand Russell (‘r’) and Alfred Whitehead fall under this concept. Let the expression ‘[λz Azp & z≠r]’ denote the concept author of Principia Mathematica other than Russell.^{[7]} Then the following may, for the purposes of this example, be taken as facts:
∃F∃w(Fw & y = #F & x = #[λz Fz & z≠w])
Frege's definition of the ancestral of R requires a preliminary definition:
the concept F is hereditary in the Rseries if and only if any pair of Rrelated objects x and y are such that y falls under F whenever x falls under FIn formal terms:
Her(F,R) =_{abbr} ∀x∀y(Rxy & Fx → Fy)Intuitively, the idea is that F is hereditary in the Rseries if F is always ‘passed’ from x to y whenever x and y are a pair of Rrelated objects. (We warn the reader here that the notation ‘Her(F,R)’ is merely an abbreviation of a much longer statement. It is not a formula of our language having the form ‘R(x,y)’. In what follows, we sometimes introduce other such abbreviations.)
Frege's definition of the ancestral of R can now be stated as follows:
x comes before y in the Rseries =_{df} y falls under all those Rhereditary concepts F under which falls every object to which x is RrelatedIn other words, y follows x in the Rseries whenever y falls under every hereditary concept F which x ‘passes on’ to all of its immediate descendants. 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 every hereditary concept that Clinton and his brother inherited from Clinton's father. However, Clinton's brother is not one of Chelsea's forefathers, since he fails to be her father, her grandfather, or any of the other links in the chain of fathers from which Chelsea descended.
It is important to grasp the differences between a relation R and its ancestral R*. Rxy implies R*(x,y) (e.g., if Clinton is a father of Chelsea, then Clinton is a forefather of Chelsea), but the converse doesn't hold (Clinton's father is a father* of Chelsea, but he is not a father of Chelsea). Indeed, a grasp of the definition of R* should leave one able to prove the following easy consequences, many of which correspond to theorems in Begr and Gg:^{[8]}
Facts About R*:
y is a member of the Rseries beginning with x if and only if either x bears the ancestral of R to y or x = yIn formal terms:
R^{+}(x,y) =_{df} R*(x,y) v x=yWe note here that Frege would also read R^{+}(x,y) as: x is a member of the Rseries ending with y! Logicians call R^{+} the ‘weakancestral’ of R because it is a weakened version of R*. When R is precedes, we can intuitively regard its weak ancestral, precedes^{+}, as the relation lessthanorequalto on the natural numbers.
The general definition of the weak ancestral of R yields the following facts, many of which correspond to theorems in Gg:^{[9]}
Facts About R^{+}:
0 =_{df} #[λx x≠x]Since the logic of identity guarantees that no object fails to be selfidentical, nothing falls under the concept being nonselfidentical. Had one of Frege's explicit definitions of the cardinal numbers worked as he had intended, the number 0 would, in effect, 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 complex concept the existence of which is guaranteed in Frege's theory of concepts and secondorder logic with identity. It is straightforward to prove the following Lemma Concerning Zero from this definition of 0:
Lemma Concerning Zero:Note that the proof appeals to Hume's Principle and facts about equinumerosity.
#F = 0 ≡ ¬∃xFx
Frege's definition of the concept natural number can now be stated in terms of the weakancestral of Predecessor:
x is a natural number if and only if x is a member of the predecessorseries beginning with 0This definition appears in Gl, §83, and Gg I, §46 as the definition of ‘finite number’. Indeed, the natural numbers are precisely the finite cardinals. 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.
Frege's Theorem is that the five Dedekind/Peano axioms for number theory can be derived from Hume's Principle in secondorder logic. In this section, we reconstruct the proof of this theorem which can be extracted from Frege's work using the definitions and theorems assembled so far. Some of the steps in this proof can be found in Gl. (See the Appendix to Boolos (1990) for a reconstruction.) Our reconstruction follows Frege's Gg in spirit and in most details, but we have tried to simplify the presentation in several places. For a more strict description of Frege's Gg proof, the reader is referred to Heck (1993). The following should help prepare the reader for Heck's excellent essay.
Theorem 1:It seems that Frege never actually identified this fact explicitly in Gl or labeled this fact as a numbered Theorem in Gg I. It is possible that he thought it was too obvious to mention.
N0Proof: It is a simple consequence of the definition of ‘weak ancestral’ that R^{+} is reflexive (see Fact 8 about R^{+} in our subsection on the Weak Ancestral in §4). So Precedes^{+}(0,0). Hence, by the definition of number, 0 is a number.
Theorem 2:See Gl, §78, Item (6); and Gg I, §109, Theorem 126.
¬∃x(Nx & Precedes(x,0))Proof: Assume, for reductio, that some object, say b, does precede 0. Then, by the definition of predecessor, it follows that there is a concept, say Q and an object falling under Q, say c, such that 0 is #Q. But this contradicts the Lemma Concerning Zero (above). Since nothing precedes 0, no natural number precedes 0.
Theorem 3:In other words, this theorem asserts that predecessor is a onetoone relation on the natural numbers. To prove this theorem, it suffices to prove that predecessor is a onetoone relation full stop. One can prove that predecessor is onetoone from Hume's Principle, with the help of the following Equinumerosity Lemma, the proof of which is rather long and involved. The Equinumerosity Lemma asserts that when F and G are equinumerous, x falls under F, and y falls under G, then the concept object falling under F other than x is equinumerous to the concept object falling under G other than y. The picture is something like this:
∀m∀n∀o[Precedes(m,o) & Precedes(n,o) → m = n]
In terms of Figure 3, the Equinumerosity Lemma tells us that if there is a relation R which is a witness to the equinumerosity of F and G, then there is a relation R′ which is a witness to the equinumerosity of the concepts that result when you restrict F and G to the objects other than x and y, respectively.
Figure 3
To help us formalize the Equinumerosity Lemma, let F^{−x} abbreviate the concept [λz Fz & z≠x] and let G^{−y} abbreviate the concept [λz Gz & z≠y]. Then we have:
Equinumerosity Lemma:Now we can prove that Predecessor is a onetoone relation from this Lemma and Hume's Principle (cf. Gg I, §108):
F ≈ G & Fx & Gy → F^{−x} ≈ G^{−y}
Predecessor is OnetoOne:So, if Predecessor is a onetoone relation, it is a onetoone relation on the natural numbers. Therefore, no two numbers have the same successor.
∀x∀y∀z[Precedes( x,z) & Precedes(y,z) → x = y]Proof: Assume that both a and b are precedessors of c. By the definition of predecessor, we know that there are concepts and objects P, Q, d, and e, such that:
But if both c = #P and c = #Q, then #P = #Q. So, by Hume's Principle, P ≈ Q. So, by the Equinumerosity Lemma, it follows that P^{−d} ≈ Q^{−e}. If so, then by Hume's Principle, #P^{−d} = #Q^{−e}. But then, a = b.
 Pd & c = #P & a = #P^{−d}
 Qe & c = #Q & b = #Q^{−e}
It is important to mention here that not only is Predecessor a onetoone relation, it is also a function:
Predecessor is a Function:This fact can be proved with the help of a kind of converse to the Equinumerosity Lemma:
∀x∀y∀z[Precedes(x,y) & Precedes(x,z) → y = z]
Equinumerosity Lemma ‘Converse’:We leave the proof of the Equinumerosity Lemma ‘Converse’ and the proof that Predecessor is a function as exercises for the reader. The fact that Predecessor is a function will play a part in the proof that every number has a successor.
F^{−x} ≈ G^{−y} & Fx & Gy → F ≈ G
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 the natural numbers, then every natural number falls under F. In formal terms:
Theorem 4: Principle of Mathematical Induction:Frege actually proves the Principle of Mathematical Induction from a more general principle that governs any Rseries whatsoever. We will call the latter the General Principle of Induction. It asserts that whenever a falls under F, and F is hereditary on the Rseries beginning with a, then every member of that Rseries falls under F. We can formalize the General Principle of Induction with the help of a more strict understanding of ‘hereditary on the Rseries beginning with a’. Here is a definition:
F0 & HerOn(F,N) → ∀n Fn
HerOn(F, ^{a}R^{+}) =_{abbr} ∀x∀y[R^{+}(a, x) & R^{+}(a,y) & Rxy → (Fx → Fy)]In other words, F is hereditary on the members of the Rseries beginning with a just in case every adjacent pair x and y in this series (with x bearing R to y) is such that y falls under F whenever x falls under F. Now given this definition, we can reformulate the General Principle of Induction more strictly as:
General Principle of Induction:This is a version of Frege's Theorem 152 in Gg I, §117.
[Fa & HerOn(F, ^{a}R^{+})] → ∀x[R^{+}(a,x) → Fx]
Frege's proves this claim by making an insightful appeal to his Rule of Substitution. We may sketch the proof strategy as follows. Assume that the antecedent of the General Principle of Induction holds for an arbitrarily chosen concept, say P. That is, assume:
Pa & HerOn(P, ^{a}R^{+})Now to show ∀x(R^{+}(a,x) → Fx), pick an arbitrary object, say b, and further assume R^{+}(a,b). We then simply have to show Pb. Frege does this by using the Rule of Substitution on Fact (6) about R^{+} (in our subsection on the Weak Ancestral in §4). Recall that Fact (6) 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 and y to a and b, respectively. He then, as we might put it, instantiates F to the concept [λz R^{+}(a,z) & Pz] and applies λConversion. (This is where Frege used his Rule of Substitution.) The concept being instantiated for F is the concept member of the Rseries beginning with a and which falls under P. The result of instantiating all the free variables in Fact (6) and then applying λConversion yields a rather long conditional, with numerous conjuncts in the antecedent and the claim that Pb in the consequent. Thus, if the antecedent can be established, the proof is done. However, for those following along with pencil and paper, all of the conjuncts to this conditional are things we already know, with the exception of the claim that [λz R^{+}(a,z) & Pz] is hereditary on R. However, this claim can be established straightforwardly from things we know to be true (and, in particular, from facts contained in the antecedent of the Principle we are trying to prove, which we assumed as part of our conditional proof). The reader is encouraged to complete the proof as an exercise. For those who would like to check their work, we give the complete Proof of the General Principle of Induction here.
Proof of the General Principle of Induction
Now to derive Principle of Mathematical Induction from the General Principle of Induction, we formulate the instance of the latter in which a is 0 and R is Precedes:
[F0 & HerOn(F, ^{0}Precedes^{+})] → ∀x[Precedes^{+}(0,x) → Fx]When we expand the defined notation for HerOn, substitute the notation Nx and Ny for Precedes^{+}(0,x) and Precedes^{+}(0,y), respectively, and then employ our restricted quantifiers ∀n(…n…) and ∀m(…m…) for the claims of the form ∀y(Ny → …y…) and ∀x(Nx → …x…), respectively, the result is the Principle of Mathematical Induction (in which the notation HerOn(F,N) has been eliminated in terms of its definiens).
Theorem 5:To understand Frege's strategy for proving this theorem, recall that the weak ancestral of the Predecessor relation, i.e., Precedes^{+}(x,y), can be read as: x is a member of the predecessorseries ending with y. Frege then considers the concept member of the predecessorseries ending with n, i.e., [λz Precedes^{+}(z,n)], where n is a natural number. Frege then shows, by induction, that every natural number n precedes the number of the concept member of the predecessorseries ending with n. That is, Frege proves that every number has a successor by proving the following Lemma on Successors by induction:
∀x[Nx → ∃y(Ny & Precedes(x,y))]
Lemma on Successors:This asserts that every number n precedes the number of numbers in the predecessor series ending with n. Frege can establish Theorem 5 by proving the Lemma on Successors and by showing that the successor of a natural number is itself a natural number.
∀n Precedes(n, #[λz Precedes^{+}(z,n)])
To see an intuitive picture of why the Lemma on Successors gives us what we want, we may temporarily regard Precedes^{+} as the relation ≤. (One can prove that Precedes^{+} has the properties that ≤ has on the natural numbers.) Although we haven't yet defined the natural numbers following 0, the following intuitive sequence is driving Frege's strategy:
0 precedes #[λz z≤ 0]For example, the third member of this sequence is true because there are 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 n precedes the number of numbers less than or equal to n, holds for every natural number. So, given this intuitive understanding of the Lemma on Successors, Frege has a good strategy for proving that every number has a successor. (For the remainder of this subsection, the reader may wish to continue to think of Precedes^{+} in terms of ≤.)
1 precedes #[λz z≤ 1]
2 precedes #[λz z≤ 2]
etc.
Now to prove the Lemma on Successors by induction, we need to reconfigure this Lemma to a form which can be used as the consequent of the Principle of Induction; i.e., we need something of the form ∀n Fn. We can get the Lemma on Successors into this form by ‘abstracting out’ a concept from the Lemma using the righttoleft direction of λConversion to produce the following equivalent statement of the Lemma:
∀n [λy Precedes(y, #[λz Precedes^{+}(z,y)])]nThe concept ‘abstracted out’ is the following:
[λy Precedes(y, #[λz Precedes^{+}(z,y)])]This is the concept: being an object y which precedes the number of the concept: member of the predecessor series ending in y. Let us abbreviate the λexpression that denotes this concept as ‘Q’. Then Frege's strategy is to instantiate the variable F in the Principle of Induction (using his Rule of Substitution) to Q. The result is therefore something that we may take as having been proved:
Q0 & HerOn(Q,N) → ∀n QnSince the consequent is the Lemma on Successors, Frege can prove this Lemma by proving both that 0 falls under Q (cf. Gg I, Theorem 154) and that Q is hereditary on the natural numbers (cf. Gg I, Theorem 150):
Proof that 0 falls under QGiven this proof of the Lemma on Successors, Theorem 5 is not far away. The Lemma on Successors shows that every number precedes some cardinal number of the form #F. We still have to show that such successor cardinals are natural numbers. That is, it still remains to be shown that if a number n precedes something y, then y is a natural number:
Successors of Natural Numbers are Natural Numbers:Theorem 5 now follows from the Lemma on Successors and the fact that successors of natural numbers are natural numbers. With the proof of Theorem 5, we have completed the proof of Frege's Theorem. Before we turn to the last section of this entry, it is worth mentioning the mathematical significance of this theorem.
∀n∀y(Precedes(n,y) → Ny)Proof: Suppose that Precedes(n,a). Then, by definition, since n is a natural number, Precedes^{+}(0,n). So by Fact (2) about R^{+} (in the subsection on the Weak Ancestral in §4), it follows that Precedes*(0,a), and so by the definition of Precedes^{+}, it follows that Precedes^{+}(0,a); i.e., a is a natural number.
n′ =_{df} the x such that Precedes(n,x)We may then define the sequence of natural numbers succeeding 0 as follows:
1 = 0′Moreover, the recursive definition of addition can now be given:
2 = 1′
3 = 2′
etc.
n + 0 = nWe may also officially define:
n + m′ = (n + m)′
n < m =_{df} Precedes*(n,m)These definitions constitute the foundations of arithmetic. Frege has insightfully isolated a group of basic laws in which they may be grounded. (Readers interested in how these results are affected when Hume's Principle is combined with predicative secondorder logic should consult Linnebo (2004).)
n ≤ m =_{df} Precedes^{+}(n,m)
A discussion of the philosophical questions surrounding Frege's Theorem should begin with some statement of how Frege conceived of his own project when writing Begr, Gl, and Gg. It seems clear that epistemological considerations in part motivated Frege's work on the foundations of mathematics. It is well documented that Frege had the following goal, namely, to explain our knowledge of the basic laws of arithmetic by giving an answer to the question "How are numbers ‘given’ to us?" which makes no appeal to the faculty of intuition. If Frege could show that the basic laws of number theory are derivable from analytic truths of logic, then he could argue that we need only appeal to the faculty of understanding (as opposed to some faculty of intuition) to explain our knowledge of the truths of arithmetic. Frege's goal then stands in contrast to the Kantian view of the exact mathematical sciences, according to which general principles of reasoning must be supplemented by a faculty of intuition if we are to achieve mathematical knowledge. The Kantian model here is that of geometry; Kant thought that our intuitions of figures and constructions played 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.)
[Begr, Preface, p. 5:]
To prevent anything intuitive from penetrating here unnoticed, I had to bend every effort to keep the chain of inferences free of gaps.
[from the BauerMengelberg translation 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 intuition a priori, can, solely from the content that results from its own constitution, bring forth judgements that at first sight appear to be possible only on the basis of some intuition. … The propositions about sequences [Rseries] in what follows far surpass in generality all those that can be derived from any intuition of sequences.
[from the BauerMengelberg translation in van Heijenoort (1967)]
[Gl, §62:]
How, then, are numbers to be given to us, if we cannot have any ideas or intuitions of them? Since it is only in the context of a proposition that words have any meaning, our problem becomes this: To define the sense of a proposition in which a number word occurs.
[from the Austin translation in Frege (1974)]
[Gl, §87:]
I hope I may claim in the present work to have made it probable that the laws of arithmetic are analytic judgements and consequently a priori. Arithmetic thus becomes simply a development of logic, and every proposition of arithmetic a law of logic, albeit a derivative one.
[from the Austin translation in Frege (1974)]
[Gg I, §0:]
In my Grundlagen der Arithmetik, I sought to make it plausible that arithmetic is a branch of logic and need not borrow any ground of proof whatever from either experience or intuition. In the present book, this shall be confirmed, by the derivation of the simplest laws of Numbers by logical means alone.
[from the Furth translation in Frege (1967)]
[Gg II, Appendix:]
The prime problem of arithmetic is the question, In what way are we to conceive logical objects, in particular, numbers? By what means are we justified in recognizing numbers as objects? Even if this problem is not 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 in Frege (1967)]
Another problem for a strategy of the type suggested by Boolos is that if the secondorder quantifiers are interpreted so that they do not range over a separate domain of entities, then there is nothing appropriate to serve as the denotations of λexpressions. Although Frege wouldn't quite put it this way, we have seen that his system treats open formulas with free object variables as if they denoted concepts. Although Frege doesn't use λnotation, the use of such notation seems to be the most logically perspicuous way of reconstructing his work. The use of such notation faces the same epistemological 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 property being an x such that φ(x) if and only if y 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 the statement form Fx. However, λConversion also implies the Comprehension Principle for Concepts, for the latter follows from the former by existential generalization:
∃F∀y(Fy ≡ φ(y/x))The point here is that the fact that an existential claim is derivable casts at least some doubt on the purely analytic status of λConversion. The question of how we obtain knowledge of such principles is still an open question in philosophy. It is an important question to address, since Frege's most insightful definitions are cast using quantifiers ranging over concepts and relations (e.g., the ancestrals of a relation) and it would be useful to have a philosophical explanation of how such entities and the principles which govern them become known to us. In contemporary philosophy, this question is still poignant, since many philosophers do accept that properties and relations of various sorts exist. These entities are the contemporary analogues of Frege's concepts.
[Gg I, Preface, p. 3:]Moreover, he thought that an appeal to extensions would answer one of the questions that motivated his work:
A dispute can arise, so far as I can see, only with regard to my Basic Law concerning coursesofvalues (V)… I hold that it is a law of pure logic.
[from the Furth translation in Frege (1967)]
[Letter to Russell, July 28, 1902:]Now it is unclear why Frege thought that he could answer the question posed here with the reply "We apprehend numbers as extensions of concepts". 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 be purely analytic or true in virtue of the meanings of its terms, we apprehend a pair of extensions whenever we truly judge that concepts F and G are materially equivalent. Some philosophers argue that Frege would have been correct to argue in just this way (had Basic Law V been consistent). They argue that Basic Law V (or consistent principles having the same logical form) justifies reference to the entities described in the leftside condition by grounding such reference in the truth of the rightside condition.^{[11]}
I myself was long reluctant to recognize ranges of values and hence classes [sets]; but I saw no other possibility of placing arithmetic on a logical foundation. But the question is, How do we apprehend logical objects? And I have found no other answer to it than this, We apprehend them as extensions of concepts, or more generally, as ranges of values of functions.
[from the Kaal translation in Frege (1980)]
But this, of course, raises an obvious problem. To justify reference to extensions, we must first justify the claim that those extensions exist. It is not clear that the claim that concepts are materially equivalent can justify such an existence claim. But given Frege's view that Basic Law V is analytic, it seems that he must hold that the rightside condition implies the corresponding leftside condition as a matter of meaning.^{[12]}
This view, however, runs up against the following argument. Suppose the right hand condition implies the leftside condition as a matter of meaning. That is, suppose that (R) implies (L) as a matter of meaning:
(R) ∀x(Fx ≡ Gx)Now note that (L) itself can be analyzed, from a logical point of view. The expression ‘ εF ’ is a definite description (‘the extension of F’) and so, using Russell's theory of descriptions, (L) can be logically analyzed as the claim:(L) εF = εG
There is an object x and an object y such that:That is, for some defined or primitive notion Extension(x,F) (‘x is an extension of F’), (L) implies the analysis (D) as a matter of meaning:
(1) x is a unique extension of F,
(2) y is a unique extension of G, and
(3) x = y.
(D) ∃x∃y[Extension(x,F) & ∀z(Extension(z,F) → z=x) &But if (R) implies (L) as a matter of meaning, and (L) implies (D) as a matter of meaning, then (R) implies (D) as a matter of meaning. This seems doubtful. The material equivalence of F and G does not imply the existence claim (D) as a matter of meaning, whatever notion of meaning is involved. [This argument attempts to show why Va (i.e., the righttoleft direction of Basic Law V) is not analytic. Below, it will be adapted to show that the righttoleft direction of Hume's Principle is not analytic. See Boolos (1997, 307  309), for reasons why Vb and the lefttoright direction of Hume's Principle are not analytic.]
Extension(y,G) & ∀z(Extension(z,G) → z=y) &
x = y]
The moral to be drawn here is that the modern Fregean must attempt to explain our knowledge of existence claims for abstract objects such as extensions head on, and not try to justify them indirectly, by attempting to justify claims that imply such existence claims. Even if we follow Frege in conceiving of extensions as ‘logical objects’, the question remains as to how the very claims that such objects exist can be true on logical or analytic grounds alone. We might agree that there must be logical objects of some sort if logic is to have a subject matter, but if Frege is to achieve his goal of showing that our knowledge of arithmetic is free of intuition, then the logical knowledge with which he identifies arithmetical knowledge must be either be purely analytic or shown otherwise to be free of intuition. We'll return to this theme in the final subsection.
Moreover, Frege had his own reasons for not replacing Basic Law V with Hume's Principle. One reason was that he thought Hume's Principle offered no answer to the epistemological question, ‘How do we grasp or apprehend logical objects, such as the numbers?’. But Frege had another reason for not substituting Hume's Principle for Basic Law V, namely, that Hume's Principle would be subject to ‘the Julius Caesar problem’. Frege first raises this problem in connection with an inductive definition of ‘n = #F’ that he tries out in Gl, §55. Concerning this definition, Frege says:
[Gl, §55:]Frege raises this same concern again for a contextual definition that gives a ‘criterion of identity’ for the objects being defined. In Gl §66, Frege considers the following contextual definition of ‘the direction of line x’:
… but we can never — to take a crude example — decide by means of our definitions whether any concept has the number Julius Caesar belonging to it, or whether that conqueror of Gaul is a number or is not.
[from the Austin translation in Frege (1974)]
The direction of line a = the direction of line b if and only if a is parallel to b.With regard to this definition, Frege says:
[Gl, §66:]Now trouble for Hume's Principle begins to arise when we recognize that it is a contextual definition that has the same logical form as this definition for directions. It is central to Frege's view that the numbers are objects, and so he believes that it is incumbent upon him to say which objects they are. But the ‘Julius Caesar problem’ is that Hume's Principle, if considered as the sole principle offering identity conditions for numbers, doesn't describe the conditions under which an arbitrary object, say Julius Caesar, is or is not to be identified with the number of planets. That is, Hume's Principle doesn't define the condition ‘#F=x’, for arbitrary x. It only offers identity conditions when x is an object we know to be a cardinal number (for then x=#G, for some G, and Hume's Principle tells us when #F=#G).
It will not, for instance, decide for us whether England is the same as the direction of the Earth's axis— if I may be forgiven an example which looks nonsensical. Naturally no one is going to confuse England with the direction of the Earth's axis; but that is no thanks to our definition of direction.
[from the Austin translation in Frege (1974)]
In Gl, Frege solves the problem by giving his explicit definition of numbers in terms of extensions. (We described this 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 above contextual definition of directions. Frege is aware that the Julius Caesar problem affects Basic Law V, though. In Gg I, §10, Frege appears to raise the Julius Caesar problem for extensions of concepts. With respect to Basic Law V, he says (remembering that for Frege, ε binds object variables and not concept variables):
[Gg I, §10:]In other words, Basic Law V does not tell us the conditions under which an arbitrarily chosen object x may be identified with some given extension, such as εF.
…this by no means fixes completely the denotation of a name like ‘ἐΦ(ε)’. We have only a means of always recognizing a courseofvalues if it is designated by a name like ‘ἐΦ(ε)’, by which it is already recognizable as a courseofvalues. But, we can neither decide, so far, whether an object is a courseofvalues that is not given us as such …
[from the Furth translation in Frege (1967)]
Until recently, it was thought that Frege solved this problem in §10 by restricting the universal quantifier ∀x of his Gg system so that it ranges only over extensions. If Frege could have successfully restricted this quantifier to extensions, then when the question arises, is (arbitrarily chosen) object x is identical with εF, one could answer that x has to be the extension of some concept, say G and that Basic Law V would then tell you the conditions under which x is identical to εF. On this interpretation of §10, Frege is alleged to have restricted the quantifiers when he identified the two truth values (The True and The False) with the two extensions that contain just these objects as members, respectively. By doing this, it was thought that all of the objects in the range of his quantifier ∀x in Gg become extensions which have been identified as such, for the truth values were the only two objects of his system that had 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 to extensions (nor, more generally, to coursesofvalues). The extensive footnote to §10 indicates that Frege considered, but did not hold much hope of, identifying every object in the domain with the extension consisting of just that object.^{[14]} But, more importantly, Frege later considers cases (in Gg, Sections 34 and 35) which seem to presuppose that the domain contains objects which aren't extensions. (In these sections, Frege considers what happens to the definition of ‘x is a member of y’ when y is not an extension.)^{[15]}
Even if Frege somehow could have successfully restricted the quantifiers of Gg to avoid the Julius Caesar problem, he would no longer have been able to extend his system to include names of ordinary nonlogical objects. For if he were to attempt to do so, the question, "Under what conditions is εF identical with Julius Caesar?", would then be legitimate but have no answer. That means his logical system could not be used for the analysis of ordinary language. But it was just the analysis of ordinary language that led Frege to his insight that a statement of number is an assertion about a concept.
These two questions arise because of a limitation in the logical form of these Fregean biconditional principles such as Hume's Principle and Basic Law V. These contextual definitions attempt to do two jobs which modern logicians now typically accomplish with separate principles. A properly reformulated theory of ‘logical’ objects should have: (1) a separate nonlogical comprehension principle which explicitly asserts the existence of logical objects, and (2) a separate identity principle which asserts the conditions under which logical objects are identical. The latter should specify identity conditions for logical objects in terms of their most salient characteristic, one which distinguishes them from other objects. Such an identity principle would then be more specific than the global identity principle for all objects (Leibniz's Law) which asserts that if objects x and y fall under the same concepts, they are identical.
By way of example, consider modern set theory. Zermelo set theory (Z) has a distinctive nonlogical comprehension principle for sets:
Subset Axiom of Z:Z has a separate identity principle:
∀x[Set(x) → ∃y[Set(y) & ∀z(z ∈ y ≡ z ∈ x & φ(z))]],
where φ(z) is any formula in which the variable z is free and which has no free variables y
Identity Principle for Sets:Note that the second principle offers identity conditions in terms of the most salient features of sets, namely, the fact that they, unlike other objects, have members. The identity conditions for objects which aren't sets, then, can be the standard principle that identifies objects whenever they fall under the same concepts. This leads us naturally to a very general principle of identity for any objects whatever:
Set(x) & Set(y) → [∀z(z ∈ x ≡ z ∈ y) → x = y]
General Principle of Identity:Now, if something is given to us as a set and we ask whether it is identical with an arbitrarily chosen object x, this specifies a clear condition that settles the matter. The only questions that remain for the theory Z concern its existence principle: Do we know that the comprehension principle is true, and if so, how? The question of existence is thus laid bare. We do not approach it by attempting to justify a principle that implies the existence of sets via definite descriptions which we don't yet know to be welldefined.
x = y =_{df} [Set(x) & Set(y) & ∀z(z ∈ x ≡ z ∈ y)] v
[¬Set(x) & ¬Set(y) & ∀F(Fx ≡ Fy)]
In his classic essays (1987) and (1986), Boolos appears to recommend this very procedure of using separate existence and identity principles. In those essays, he eschews the primitive mathematical relation of set membership and suggests that Frege formulate his theory of numbers (‘Frege Arithmetic’) by using a single nonlogical comprehension axiom which employs a special instantiation relation that holds between a concept G and an object x whenever, intuitively, x is an extension consisting 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 is in x:
Numbers:[See Boolos (1987), p. 5; and (1986), p. 140.] This principle asserts that for any concept F, there is a unique object which contains in it all and only those concepts G which are equinumerous to F. Boolos then makes two observations: (1) that Frege can then define #F as "the unique object x such that for all concepts G, G is in x iff G is equinumerous to F", and (2) that Hume's Principle is derivable from Numbers. [See Boolos (1986), p. 140.] Given these observations, we know from our work in §§4 and 5 above that Numbers suffices for the derivation of the basic laws of arithmetic.
∀F∃!x∀G(Gη x ≡ G≈F)
Since Boolos calls this principle ‘Numbers’, it is no stretch to suppose that he would accept the following explicit reformulation (in which ‘Number(x)’ is an undefined, primitive notion):
Numbers:Though Boolos doesn't explicitly formulate an identity principle to complement Numbers, it seems clear that the following principle would offer identity conditions in terms of the most distinctive feature of numbers:
∀F∃!x[Number(x) & ∀G(Gηx ≡ G≈F)]
Identity Principle for Numbers:It is then straightforward to formulate a general principle of identity, as we did in the case of the set theory Z:
Number(x) & Number(y) → [∀G(Gηx ≡ Gηy) → x = y]
General Principle of Identity:This formulation of Frege Arithmetic, in terms of Numbers and the General Principle of Identity, puts the Julius Caesar problem (described above) into better perspective; the condition ‘#F=x’ is defined for arbitrary concepts F and objects x. It openly faces the epistemological questions headon: Do we know that Numbers is true, and if so, how? This is where philosophers need to concentrate their energies. [For a reconstruction of Frege Arithmetic with a more general version of the special instantiation relation η, see Zalta (1999).]
x = y =_{df} [Number(x) & Number(y) & ∀F(Fηx ≡ Fηy)] v
[¬Number(x) & ¬Number(y) & ∀F(Fx ≡ Fy)]
By replacing Fregean biconditionals such as Hume's Principle with explicit existence and identity principles, we reduce two problems to one and and isolate the real problem for Fregean foundations of arithmetic, namely, the problem of giving an epistemological justification of existence claims (e.g., Numbers) for abstract objects of a certain kind. For anything like Frege's program to succeed, it must at some point explicitly assert (as an axiom or theorem) the existence of (logical) objects of some kind. Those explicit existence claims should be the focus of attention, for they are the point at which logic and metaphysics dovetail. The theory of logical objects, if carried out without any mathematical primitives, should simply be acknowledged as a nonlogical metaphysical theory, not a piece of logic. A proper epistemology for such a theory should offer some epistemological justification of the explicit existence claims that serve as the basic axioms of the theory. That is the moral to be drawn from Frege's work.
An early version of William Demopoulos' forthcoming essay "The Logicism of Frege, Dedekind, and Russell" motivated me to write the present entry. Demopoulos has kindly allowed me to quote certain passages from that essay in the footnotes to the present entry. I am also indebted to Roberto Torretti, who carefully read this piece and identified numerous infelicities; to Franz Fritsche, who noticed a quantifier transposition error in Fact 2 about the strong ancestral, to Seyed N. Mousavian, who noticed some typographical errors in some formulas; to Xu Mingming, who noticed that Fact 7 about the Weak Ancestral (Section 4, subsection "The Weak Ancestral of R") was missing an important condition (namely, that R must be 11); and to Paul Pietroski, who noticed an infelicity in the first statement of the principle of induction in Section 4. Finally, I am indebted to Kai Wehmeier, who reminded me that, strictly speaking, the result of replacing Basic Law V by Hume's Principle in Frege's system does not result in a subsystem of the original until we replace the primitive notion "the course of values of the function ƒ" with the primitive notion "the number of Fs".
Edward N. Zalta zalta@stanford.edu 
A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z