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

Stanford Encyclopedia of Philosophy

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

Frege's Logic, Theorem, and Foundations for Arithmetic

One of the most significant contributions that Frege made to philosophy was his analysis of the theory of natural numbers in terms of his formal language, logic, theory of concepts, and theory of extensions. In this analysis, Frege attempted to derive the theory of natural numbers from what he took to be `purely logical' propositions. Although Frege's project, of showing that number theory is derivable from pure logic, was ultimately unsuccessful, Frege's theoretical accomplishments in pursuit of this goal include several deep insights about the relationship between logic and certain parts of mathematics.

While Frege's second-order logic and theory of concepts in his early work is perfectly consistent, the theory of extensions (or sets) that he added in his later work proved to be inconsistent. The sole axiom of that theory, Basic Law V, foundered on Russell's paradox. Although the addition of this axiom implies a contradiction, there is a significant fragment of Frege's work which remains unaffected by the inconsistency. In this fragment, Frege validly proved the fundamental propositions of arithmetic from a consistent principle that he had derived from the inconsistent Basic Law V. This consistent principle is known as Hume's Principle and it will be thoroughly examined in what follows. If we set aside the invalid derivation of Hume's Principle from Basic Law V and focus on Frege's proofs of the basic propositions of arithmetic, then his remarkable theoretical achievement emerges much more clearly, for he showed that the Dedekind/Peano axioms for number theory are derivable from Hume's Principle in second-order logic. This achievement has now become known as Frege's Theorem. [See Boolos (1990), p. 268.]

Our goals in what follows are: (1) to explain (the logical machinery necessary to understand) the proof of Frege's Theorem, (2) to prepare students of Frege to read his original work (in translation), (3) to prepare the reader to understand a number of excellent articles in the secondary literature on Frege's work, and (4) to frame the most important philosophical questions that arise in connection with Frege's attempt to reduce number theory to logic (for example, "What is the philosophical significance of Frege's Theorem?"). Those readers already familiar with the details of Frege's logic and foundations of arithmetic and the proof of Frege's Theorem, therefore, may wish to skip directly to the discussion of the philosophical questions discussed in the final section.

To accomplish these goals, we presuppose only a familiarity with the first-order predicate calculus. We show how to extend this language and logic to include the most salient features of Frege's second-order 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:

We will refer to these works with boldfaced abbreviations of their German titles: Begr, Gl and Gg, respectively.
[Link to Complete Table of Contents (With Listing of Subsections)]

§1: Frege's Predicate Calculus and Theory of Concepts

In this section, we describe the language and logic of Frege's predicate calculus. We explain his function-argument 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 second-order 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.

The Language

In Begr, Frege invented the predicate calculus. It will soon become clear that the language and logic of his predicate calculus are `second-order'. The language included not only the variables x,y,z, ... , which range over objects, but also included the variables f,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 `f(x)' as the principal operation for forming complex names of objects in his language. The expression `f(x)' denotes the object to which the function f maps the object x. Frege called the object x the `argument' of the function f and called f(x) the `value' of the function. Since Frege also recognized two special objects he called truth-values (The True and The False), he defined a concept to be any function that always maps its arguments to truth-values. For example, whereas `x2 +3' and `father-of(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 truth-values.

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 f is a function of two arguments x and y and f always maps its pair of arguments to a truth value, Frege would say that f 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 greater-than 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 Greek letters as bound variables in names of courses-of-values, and certain other Greek letters as placeholders in the names of functions, then Frege's notation for the logical notions `not', `if-then', `every' and `some' can be described in the following table:

Logical Notion Modern Notation Frege-Style 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 xFx,   i.e.,   xFx
Every F is such that Fa F Fa
Some F is such that Fa FFa,   i.e.,   F Fa
So, for example, whereas a modern logician would formalize the claim `All As are Bs' as:
x(Ax Bx)
Frege would formalize this claim as follows:
However, since Frege's notation is no longer used, we shall instead use the more familiar modern notation in the remainder of this essay. [For an excellent and more faithful introduction to Frege's notation, see Furth (1967).] 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. The statement `f(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 `second-order'.

The Logic

Frege's logic consisted of basic axioms and rules of inference that governed the permissible inferences within his system. His axioms included familiar axioms of propositional logic, second-order predicate logic, 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 were among the basic laws of Frege's system: [Frege's most well-known codification of these laws occurs in Gg I, §47; however, the above laws are first introduced in Gg I, §§18, 20, 25, and 20, respectively.] We shall simplify our discussion in what follows by assuming that the usual axioms of the modern second-order predicate calculus apply to Frege's system. These are essentially the same as the axioms for the first-order predicate calculus, except for the addition of laws for the second-order quantifiers F and F which correspond to the laws governing the first-order quantifiers x and x.

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 Greek letters used as placeholders, certain Gothic and Greek 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 second-order predicate calculus apply to Frege's system. Again, these are essentially the same as the rules for the first-order predicate calculus, except for the addition of new rules for the second-order quantifiers that correspond to the generalization and instantiation rules (i.e., introduction and elimination rules) for the first-order quantifiers.

The Rule of Substitution

There is, however, one distinguished rule of Frege's system that will play an important role in what follows, namely, his Rule of Substitution. For the purposes of this discussion, we may formulate the rule in the following somewhat simplified manner:
Rule of Substitution (Simplified Version):
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... .
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 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).

The Theory of Concepts

The Rule of Substitution has rather powerful consequences. It implies that there exists a concept corresponding to every open formula with a free variable x. To see that this is a consequence of the rule, note that it follows from (A) by existential generalization that:
Gx(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:
Gx(Gx (x)),
where (x) is any formula which has x free and which has no free Gs.
Similarly, from the theorem of logic:
xy(Rxy Rxy)
one can generalize and then use the Rule of Substitution to derive the following Comprehension Principle for Relations:
Comprehension Principle for Relations:
Rxy(Rxy (x,y)),
where (x,y) is any formula with x and y free and which has no free Rs.
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:
Gx(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:
Rxy(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 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 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 2-place 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 insofar as -expressions are taken to be predicates, Frege would not have accepted the idea that these are complete expressions that name concepts. But we shall not discuss Frege's reasons for this in the present essay.

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:
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, the following is an instance of -conversion:
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 right-to-left direction of such biconditionals `-Abstraction'. For example, the inference from
O6  &  6 > 5)
to
[x Ox & x > 5]6
is justified by -Abstraction.

The principle of -Conversion can be generalized, so that it covers relations as well:

zw([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 -expression [x (x)] may be uniformly substituted for the occurrences of the variable F in any theorem of logic containing F free.
(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) p. 171. 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.]

It is important to appreciate that the system we have just described, i.e., Frege's system of second order 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 `R-series' 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.

§2: Frege's Theory of Extensions: Basic Law V

[Note: This section is included to give an historical understanding of Frege's system. It is not required for understanding the proof of Frege's Theorem.]

The principle that undermined Frege's system (Basic Law V) was one that attempted to systematize the notions `extension of a concept' and `course-of-values of a function'. The extension of a concept is something like the set of all objects that fall under the concept. The course-of-values of a function f is something like a set of ordered pairs that records the value f(x) of function f for every argument x. For example, the course-of-values of the function father of x records, among other things, that when Chelsea Clinton is the argument of the function, the value is Bill Clinton. Since concepts are just functions from objects to truth values, the extension of a concept is simply the course-of-values which records which objects that concept maps to The True.

Notation for Courses-of-Values

Frege introduces notation for courses-of-values in Gg I, §9. He switched to the lower case Greek letters and when writing the names of courses-of-values and extensions. He used something like the notation f() to designate the course-of-values of the function f. In the special case where f is the concept F, he used the notation F to designate the extension of the concept F. When (x) is any formula in which the variable x is free, we may write ((/x)) to designate the extension of the concept [x (x)]. Those readers already familiar with the `-calculus' should remember that (()) denotes an object, that [x (x)] denotes a concept, and that Frege rigorously distinguished objects and concepts and supposed them to inhabit mutually exclusive domains.

Here are two pairs of examples of Frege's notation---the first are examples of courses-of-values and the second are examples of extensions. The first pair of examples comes from Gg I, §9. Frege uses the notation:

(2 - )
to denote the course-of-values of the function:
x2 - x
He also uses:
( · ( - 1))
to denote the course-of-values of the function:
x · (x - 1)
Frege then notes that:
x[x2 - x   =   x · (x - 1)]
always has the same truth value as the following:
(2 - )   =   ( · ( - 1))
This equivalence will become embodied in Basic Law V.

Here is a second example, this time involving a pair of concepts. Consider the concept that which when added to 4 equals 5, or using -notation, the following concept:

[x x + 4 = 5]
Frege would use the following notation to denote the extension of this concept:
( + 4 = 5)
Now consider the concept that which when added to 22 equals 5 (i.e., [x x + 22 = 5]). Frege would use the following notation to denote the extension of this concept:
( + 22 = 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.

One subtlety concerning Frege's notation that we have ignored in this last pair of examples is the difference between Frege's notation ( + 4 = 5) and our notation:

([x x + 4 = 5])
However, Frege's notation is equivalent to this latter notation, given that -Conversion allows us to convert
[x x + 4 = 5]
to:
+ 4 = 5
In general, whenever we have a complex formula (x) in which the variable x is free, and (/x) is the result of replacing for x everywhere in (x), we may always rewrite:
([x (x)])
as:
((/x))
Frege doesn't require this `Rewrite Rule', since he doesn't use -notation. But since it is logically more perspicuous to distinguish open formulas from the corresponding names of concepts, it is important to make this rule explicit.

Membership in an Extension

If we remember that the extension of a concept is something like the set of objects that fall under the concept, then we could replace Frege's talk of `extensions' by talk of `sets' and use the following `set notation' to refer to the set of objects that when added to 4 yield 5 and the set of objects that when added to 22 yield 5, respectively:
{x | x + 4 = 5}

{x | x + 22 = 5}

In what follows, we sometimes render Frege's notation in this more modern notation.

Frege took advantage of his second-order language to define what it is for an object to be a member of an extension. Although Frege used the notation xy to designate the membership relation, we shall follow the more usual practice of using x y. Thus, the following captures the main features of Frege's definition of membership in Gg I, §34:

x y =df G(y = G & Gx)
For example, given this definition, one can prove that John is an 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:
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
Some readers may wish to examine a somewhat more complex example, in which the above definition of membership is used to prove that 1 ( + 22 = 5) given the premise that 1 + 22 = 5. (More Complex Example)

Basic Law V

Frege attempted to axiomatize courses-of-values and extensions by formulating 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:
f() = g() x[f(x) = g(x)]
This principle asserts: the course-of-values of the function f is identical to the course-of-values of the function g if and only if f 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.]

Basic Law V has the following special case, when the functions f 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 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:
{x|Fx} = {y|Gy} z(Fz Gz)

The second example discussed in the subsection Notation for Courses of Values can now be seen as an instance of Basic Law V:

( + 4 = 5) = ( + 22 = 5) x(x + 4 = 5 x + 22 = 5)
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 22 yields 5 if and only if all and only the objects that when added to 4 yield 5 are objects that when added to 22 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:
Fx(x F Fx)

(Proof)

Basic Law V also `correctly' implies the Principle of Extensionality. This principle asserts that if two extensions have the same members, they are identical:
Principle of Extensionality:
x = F  &  y = G   [z(z x z y)     x = y]

(Proof)

Despite these `successes' of Basic Law V, the fact is that it is inconsistent. In the following subsections, we shall show how Basic Law V proves to be inconsistent with the rest of Frege's second order logic and theory of concepts. The proofs depend essentially on the second order character of Frege's system and on the second-order 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.

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:
Fx(x = F)
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:
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.

First Derivation of the Contradiction

In the Appendix to Gg II, Frege shows that a contradiction can be derived once we formulate the concept being the extension of a concept which you don't fall under. The following open formula expresses this concept:
F(x = F & Fx)
From 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 and our Rewrite Rule, the extension of this concept exists and can be designated as follows:
[F( = F & F)]
It can now be proved that this extension falls under the concept [x F(x = F & Fx)] if and only if it does not. (Proof.)

Second Derivation of the Contradiction

Frege next (in the Appendix to Gg II) explained how Basic Law V implies the Naive Comprehension Axiom for extensions or sets, which Russell's Paradox shows to be inconsistent. From the Law of Extensions (which was derived from Basic Law V above), one can establish the Naive Comprehension Axiom for extensions in three simple steps. First we instantiate the Law of Extensions to the free variable F, to yield:
x(x F Fx)
Then by generalizing on the extension F, it follows that:
yx(x y Fx)
Now at this point, we may universally generalize on the variable F to get the following second-order 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:
Fyx(x y Fx)
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:
Naive Comprehension Schema for Extensions:
yx(x y (x)), where (x) is any formula in which x is free and which contains no free occurrences of y
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.

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:

yx(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.)

How the Paradox is Engendered

Philosophers have diagnosed the inconsistency in Frege's system in various ways, and it is safe to say that the matter is still somewhat controversial. In this subsection, we discuss only the basic elements of the problem. Most philosophers and logicians agree that the reason Frege's second-order logic and theory of extensions is inconsistent is that they jointly require 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. This impossible situation is strikingly analogous to the impossible situation set up in the proof by reductio of Cantor's Theorem (Cantor's Theorem asserts that if A is any set, and B is the power set of A (i.e., B is the set of all subsets of A), then B has more members than A; the proof by reductio shows that it is impossible for there to be a function from A onto B).

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 right-to-left 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 right-to-left direction of Basic Law V. See, for example, Gg I, §52. However, most 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 = G
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.

However, the left-to-right direction of Basic Law V (i.e., Vb) is more serious. Vb asserts:

Basic Law Vb:
F = G x(Fx Gx)
If we consider the contrapositive of this and remember the identity conditions for concepts, then Vb 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 one-to-one; 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.

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 it 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 though it may seem that this forces the domain of concepts to be larger than the domain of objects, it is a model-theoretic fact that there are models of second-order logic with Comprehension for Concepts (but without Basic Law V) in which the domain of concepts need not be 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 second-order 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.[2] Although attempts have been made to revise Basic Law V, none of the proposed alternatives have been completely successful as a replacement. (However, see Boolos (1986) and (1993), for interesting and reasonably fruitful attempts to revise Basic Law V.)

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 second-order logic with the help of a single additional principle. The principle in question is known as Hume's Principle (to be discussed below). Although both 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 second-order 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.

§3: Frege's Analysis of Cardinal Numbers

Cardinal numbers are the numbers that can be used to answer the question `How many?', and Frege discovered that such numbers bear an interesting relationship to the natural numbers. Frege's insights concerning this relationship trace back to his work in Gl, in which the notion of an extension played very little role. The seminal idea of Gl, §46, was the observation that a statement of number (e.g., "There are nine planets") is an assertion about a concept. To explain this idea, Frege noted that one and the same external phenomenon can be counted in different ways; for example, a certain external phenomenon could be counted as one army, 5 divisions, 25 regiments, 120 companies, 400 platoons, or 4000 people. Each different way of counting this phenomenon corresponds to the manner of its conception. The question "How many are there?" is only properly formulated as the question "How many Fs are there?" where a concept F is supplied. On Frege's view, the statements of number which answer such questions (e.g., "There are n Fs") tell us something about the concept involved. For example, the statement "There are nine planets in the solar system" tells us that the concept planet in the solar system falls under the second-order numerical concept concept under which nine objects fall.

Frege then moves from this realization, in which statements of numbers are analyzed as predicating second-order numerical concepts of first-order concepts, to develop an account of the cardinal and natural numbers as `self-subsistent' 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'. 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 one-to-one correspondence or `equinumerous'. After developing the definition of equinumerosity, we then discuss Frege's implicit and explicit definition of the number of Fs.

Equinumerosity

In order to state the definition of equinumerosity, we shall employ the well-known logical notion `there exists a unique x such that (x)'. To say that there exists a unique x such that (x) is to say: there is some x such that (x) and anything y which is such that (y/x) is identical to x. In what follows, we use the notation `!x(x)' to abbreviate this notion 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 state Frege's definition of equinumerosity 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 object falling under F is R-related 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 R-related 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
  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 two concepts that are equinumerous:

Figure 1
Although there are several different relations R which would demonstrate the equinumerosity of F and G in Figure 1, the particular relation that 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, 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:


Figure 2
In this example, the relation R2 fails the definition of equinumerosity since c is not mapped to a unique object that falls under G.

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 underG. 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:
1. x(Fx Gx) F G
2. F F
3. F G G F
4. F G & G H F H
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.

Contextual Definition of `The Number of Fs':
Hume's Principle

Frege contextually defined `the number of Fs' in terms of the principle now known as Hume's Principle:[3]
Hume's Principle:
The number of Fs is identical to the number of Gs if and only if F and G are equinumerous.
Using our notation `#F' to abbreviate `the number of Fs', we may formalize Hume's Principle as follows:
Hume's Principle:
#F = #G     F G
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.

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 left-side condition) with an equivalence relation on concepts (the right-side 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 one-to-one, Hume's Principle only asserts that the correlation between concepts and numbers is many-to-one. 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 second-order logic. This was shown independently by Burgess (1984) and Hazen (1985).

Explicit Definition of `The Number of Fs'

[Note: The remaining two subsections are not strictly necessary for understanding the proof of Frege's Theorem. They are included here for those who wish to have a more complete understanding of what Frege in fact attempted to do. They presuppose the material in §2.]

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. (Readers interested in just the positive aspects of Frege's accomplishments might wish to skip directly to §4.) The idea behind this attempt was the realization that if given any concept F, the notion of equinumerosity can be used to define the second-order 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 first-order concepts. In that work, he defined informally (§68):

the number of Fs   =df
  the extension of the second-order concept: being a concept equinumerous to F
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 first-order 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 first-order 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 so-called "Frege-Russell 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.

Derivation of Hume's Principle

Frege's derivation of Hume's Principle was invalidated by the fact that it appeals to the inconsistent Basic Law V. Nevertheless, it is instructive to consider why Frege thought the derivation was valid. In Gl, §73, Frege sketches an informal proof of the right-to-left direction of Hume's Principle using the above explicit definition of the number of Fs. The derivation appeals to the fact that a concept G is a member of the extension of the second-order concept concept equinumerous to F if and only if G is equinumerous to F. In other words, the proof relies on a kind of higher-order version of the Law of Extensions (described above), the ordinary version of which we know to be a consequence of Basic Law V.[6] Here is a reconstruction of Frege's proof in Gl, §73, extended so as to cover both directions of Hume's Principle.
Frege's Derivation of Hume's Principle in Gl
However, 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 Gg
As 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.

§4: Frege's Analysis of Predecessor, Ancestrals, and the Natural Numbers

In what follows, we shall suppose that Hume's Principle has replaced Basic Law V in Frege's second-order system. As we have mentioned, Frege made the insightful discovery that the basic laws of number theory could be derived from Hume's Principle alone. This is Frege's Theorem. In this section, we introduce the definitions required for the proof of Frege's Theorem. In the next section, we go through the proof. In the final section, we shall conclude with a discussion of the philosophical questions that arise when we consider Hume's Principle as a replacement for Basic Law V.

The insight behind Frege's analysis of the natural numbers was the realization that one can define a sequence of cardinal numbers in terms of the following sequence of concepts:

C0 = [x   xx]
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 concept Ci has the following property: all and only the numbers of concepts preceding Ci in the sequence fall under Ci. So, for example, the concepts preceding C3 are C0, C1, and C2. Accordingly, all and only the following numbers fall under C3: #C0, #C1, and #C2.

Frege noticed that this sequence of concepts can be used to define the following sequence of cardinal numbers:

0 = #C0
1 = #C1
2 = #C2
etc.
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: 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.

Predecessor

To accomplish these further goals, Frege proceeded by defining the concept x (immediately) precedes y as follows (Gl, §76, and Gg I, §43):
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 w
In formal terms, the definition takes the following form:
Precedes(x,y)   =df
  Fw(Fw   &   y = #F   &   x = #[z Fz & zw])
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 & zr]' 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: If we assemble these truths into a conjunction and apply existential generalization in the appropriate places, the result is the definiens of the definition of predecessor instantiated to the numbers 1 and 2. Thus, if given certain facts about the number of objects falling under the certain concepts, the definition of predecessor correctly predicts that Precedes(1,2).

The Ancestral of Relation R

Frege next defines the relational concept x is an ancestor of y in the R-series. This new relation is called `the ancestral of the relation R' and we henceforth designate this relation as R*. Frege first defined the ancestral of relation R in Begr (Part III, Proposition 76), though the word `ancestral' comes to us from Russell and Whitehead. Frege's term for the ancestral is "x comes before y in the R-series"; alternatively, "y follows x in the R-series". See also Gl, §79 and Gg I, §45.) The intuitive idea is easily grasped if we consider the relation x is the father of y. Suppose that a is the father of b, that b is the father of c, and that c is the father of d. Then `x is an ancestor of y in the fatherhood-series' is defined so that a is an ancestor of b, c, and d, that b is an ancestor of c and d, and that c is an ancestor of d.

Frege's definition of the ancestral of R requires a preliminary definition:

the concept F is hereditary in the R-series if and only if any pair of R-related objects x and y are such that y falls under F whenever x falls under F
In formal terms:
Her(F,R)   =abbr   xy(Rxy & Fx Fy)
Intuitively, the idea is that F is hereditary in the R-series if F is always `passed' from x to y whenever x and y are a pair of R-related 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 R-series   =df   y falls under all those R-hereditary concepts F under which falls every object to which x is R-related
In other words, y follows x in the R-series 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*:

  1. Rxy R*(x,y)
  2. (R*(x,y) Rxy)
  3. xR*(x,y) x Rxy
  4. Rxy & R*(y,z) R*(x,z)
  5. [R*(x,y) & z(Rxz Fz) & Her(F,R)] Fy
  6. [Fx & R*(x,y) & Her(F,R)] Fy
  7. R*(x,y) & R*(y,z) R*(x,z)
The reader should consider what happens when R is taken to be the relation precedes. Appealing to our intuitive grasp of the numbers, we can say that it is an instance of Fact (1) that if 10 precedes 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. An instance of Fact (7) is that precedes* is transitive. When we restrict ourselves to the natural numbers, it is intuitive to think of the difference between precedes and precedes* as the difference between immediately precedes and less-than.

The Weak Ancestral of R

Given the notion of the ancestral of relation R, Frege then defines its weak ancestral, which he termed "y is a member of the R-series beginning with x" (cf. Begr, Part III, Proposition 99; Gl, §81, and Gg I, §46):
y is a member of the R-series beginning with x if and only if either x bears the ancestral of R to y or x = y
In formal terms:
R+(x,y)   =df   R*(x,y) v x=y
We note here that Frege would also read R+(x,y) as: x is a member of the R-series ending with y! Logicians call R+ the `weak-ancestral' 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 less-than-or-equal-to 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+:

  1. Rxy R+(x,y)
  2. R+(x,y) & Ryz R*(x,z)
  3. R(x,y) & R+(y,z) R*(x,z)
  4. R*(x,y) & Ryz R+(x,z)
  5. R*(x,y) z(R+(x,z) & Rzy)
  6. [Fx & R+(x,y) & Her(F,R)] Fy
  7. R*(x,y) & Rzy R+(x,z)
The proofs of these facts are left as exercises.

The Concept Natural Number

Frege's definition of natural number requires one more preliminary definition. It may be recalled that that Frege identified the number 0 as the (cardinal) number of the concept being non-self-identical. That is:
0   =df   #[x xx]
Since the logic of identity guarantees that no object fails to be self-identical, nothing falls under the concept being non-self-identical. 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 second-order logic with identity. It is straightforward to prove the following Lemma Concerning Zero from this definition of 0:
Lemma Concerning Zero:
#F = 0 xFx

(Proof)

Note that the proof appeals to Hume's Principle and facts about equinumerosity.

Frege's definition of the concept natural number can now be stated in terms of the weak-ancestral of Predecessor:

x is a natural number if and only if x is a member of the predecessor-series beginning with 0
This definition appears in Gl, §83, and Gg I, §108 as the definition of `finite number'. Indeed, the natural numbers are precisely the finite cardinals. In formal terms, Frege's definition becomes:
x   =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 Theorem

Frege's Theorem is that the five Dedekind/Peano axioms for number theory can be derived from Hume's Principle in second-order logic. In this section, we reconstruct Frege's proof of this theorem from the definitions and theorems assembled so far. Parts of Frege's proof can be found in Gl. (See the Appendix to Boolos (1990) for a reconstruction.) Our reconstruction follows Frege's Gg proof 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.

Zero is a Number

The following is an immediate consequence of the definition of natural number:
Theorem 1:
0
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.

Zero Isn't the Successor of Any Number

It is also a simple consequence of the foregoing that 0 doesn't succeed any number (cf. Gl, §78, Item (6); Gg I, §109, Theorem 126). This can be represented formally as follows:
Theorem 2:
x(x & Precedes(x,0))
Here is a proof of this theorem. 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.

No Two Numbers Have the Same Successor

The fact that no two numbers have the same successor is somewhat more difficult to prove (cf. Gl, §78, Item (5); Gg I, §95, Theorem 89). We may formulate this theorem as follows, with m, n, and o as restricted variables ranging over the natural numbers:
Theorem 3:
mno[Precedes(m,o) & Precedes(n,o) m = n]
In other words, this theorem asserts that predecessor is a one-to-one relation on the natural numbers. To prove this theorem, it suffices to prove that predecessor is a one-to-one relation full stop. One can prove that predecessor is one-to-one 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:

Figure 3
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.

To help us formalize the Equinumerosity Lemma, let F-x abbreviate the concept [z Fz & zx] and let G-y abbreviate the concept [z Gz & zy]. Then we have:

Equinumerosity Lemma:
F G  &  Fx  &  Gy     F-x G-y

(Proof)

Now we can prove that Predecessor is a one-to-one relation from this Lemma and Hume's Principle (cf. Gg I, §108):
Predecessor is One-to-One:
xyz[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.
So, if Predecessor is a one-to-one relation, it is a one-to-one relation on the natural numbers. Therefore, no two numbers have the same successor.

It is important to mention here that not only is Predecessor a one-to-one relation, it is also a function:

Predecessor is a Function:
xyz[Precedes(x,y) & Precedes(x,z) y = z]
This fact can be proved with the help of a kind of converse to the Equinumerosity Lemma:
Equinumerosity Lemma `Converse':
F-x G-y  &  Fx  &  Gy     F G
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.

The Principle of Mathematical Induction

Let us say that a concept F is hereditary on the natural numbers just in case every `adjacent' pair of numbers n and m (n preceding m) is such that m falls under F whenever n falls under F, i.e.,
HerOn(F,)  =abbr  nm[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:
Principle of Mathematical Induction:
F0 & HerOn(F,) n Fn
Frege actually proves the Principle of Mathematical Induction from a more general principle that governs any R-series 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 R-series beginning with a, then every member of that R-series falls under F. We can formalize the General Principle of Induction with the help of a more strict understanding of `hereditary on the R-series beginning with a'. Here is a definition:
HerOn(F, aR+)  =abbr  xy[R+(a,x) & R+(a,y) & Rxy     (Fx Fy)]
In other words, F is hereditary on the members of the R-series 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:
[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 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, aR+)
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)] Fy
This 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 R-series 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)

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, 0Precedes+)]    x[Precedes+(0,x) Fx]
When we expand the defined notation for HerOn, substitute the notation x and y 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(y ...y...) and x(x ...x...), respectively, the result is the Principle of Mathematical Induction (in which the notation HerOn(F,) has been eliminated in terms of its definiens).

Every Number Has a Successor

Frege uses the Principle of Mathematical Induction to prove that every number has a successor in the natural numbers. We may formulate the theorem as follows:
Theorem 5:
x[x y(y & Precedes(x,y))]
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 predecessor-series ending with y. Frege then considers the concept member of the predecessor-series 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 predecessor-series ending with n. That is, Frege proves that every number has a successor by proving the following Lemma on Successors by induction:
Lemma on Successors:
n Precedes(n, #[z Precedes+(z,n)])
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.

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]
1 precedes #[z z 1]
2 precedes #[z z 2]
etc.
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 succesor. (For the remainder of this subsection, the reader may wish to continue to think of Precedes+ in terms of .)

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 right-to-left direction of -Conversion to produce the following equivalent statement of the Lemma:

n [y Precedes(y, #[z Precedes+(z,y)])]n
The 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 Qn
Since 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):
Frege's Proof that 0 falls under Q

Frege's Proof that Q is hereditary on the natural numbers

Given 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:
ny(Precedes(n,y) y)
This, however, follows from simple facts about ancestrals. For 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.

Theorem 5 then 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.

Arithmetic

From Frege's Theorem, one can derive arithmetic. It is an immediate consequence of the functionality of Predecessor that every number has a unique successor. That means we can define the successor function:
n  =df  the x such that Precedes(n,x)
We may then define the sequence of natural numbers succeeding 0 as follows:
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 has insightfully isolated a group of basic laws in which they may be grounded.

§6: Philosophical Questions Surrounding Frege's Theorem

Frege's Theorem is an elegant derivation of the basic laws of arithmetic which can be carried out independently of the portion of his system which led to inconsistency. A discussion of the philosophical questions surrounding Frege's Theorem should begin with some statement of how Frege conceived of his own project. It seems clear that epistemological considerations in part motivated Frege's work on the foundations of mathematics. It is well documented that Frege's 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, in which our intuitions of figures and constructions play an essential role in the demonstrations of geometrical theorems.

Frege's Goals and Strategy in His Own Words

Frege's strategy then was to show that no appeal to intuition is required for the derivation of the theorems of number theory. This in turn required that he show that the latter are derivable using only rules of inference, axioms, and definitions that are purely analytic principles 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 had to bend every effort to keep the chain of inferences free of gaps.
          [from the Bauer-Mengelberg 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 [R-series] in what follows far surpass in generality all those that can be derived from any intuition of sequences.
          [from the Bauer-Mengelberg 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)]

The Basic Problem for Frege's Strategy

The basic problem for Frege's strategy, however, is that for his logicist project to succeed, his system must at some point include (either as an axiom or theorem) statements that explicitly assert the existence of certain kinds of abstract entities and it is not obvious how to justify the claim that we know such explicit existential statements. Given our description of his system, it should be clear that Frege's logical system includes existence claims for the following entities: Although Frege attempted to reduce the latter two kinds of entities (truth-values and numbers) to extensions, the fact is that the existence of concepts and extensions are implied by his Rule of Substitution and Basic Law V, respectively. Logic, it is often argued, should be free of such existence assumptions. A Kantian might well complain both that explicit existence claims seem to be synthetic rather than analytic (i.e., such claims don't seem to be true in virtue of the meanings of the words involved) and that since that Rule of Substitution and Basic Law V imply existence claims, Frege cannot claim that such principles are purely analytic principles of logic. If so, then some other faculty (such as intuition) might still be needed to account for our knowledge of (the existence claims of) arithmetic.

The Existence of Concepts

Boolos (1985) was the first to note that the Rule of Substitution causes a problem of this kind for Frege's program, since it is equivalent to a quite liberal existential claim, namely, the Comprehension Principle for Concepts. Boolos suggests a defense for Frege with respect to this particular aspect of his logic, namely, to reinterpret (by paraphrasing) the second-order quantifiers so as to avoid commitment to concepts. (See Boolos (1985) for the details.) Boolos's suggestion, however, is one which would require Frege to abandon his realist theory of concepts. Moreover, although Boolos' suggestion might lead us to an epistemological justification of the Comprehension Principle for Concepts, it doesn't do the same for the Comprehension Principle for Relations, for his reinterpretation of the quantifiers works only for the `monadic' quantifiers (i.e., those ranging over concepts having one argument) and thus doesn't offer a paraphrase for quantification over relational concepts.

Another problem for a strategy of the type suggested by Boolos is that if the second order 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 perspicous 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 satisfies (in Tarski's sense)
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:
Fy(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.

The Existence of Extensions

We have also seen (§2) that the Corollary to Basic Law V implies the existence of extensions. The question for Frege's project, then, is why should we accept as a law of logic a statement that implies the existence of individuals? Frege did conceive of Basic Law V as a law of logic:
          [Gg I, Preface, p. 3:]
A dispute can arise, so far as I can see, only with regard to my Basic Law concerning courses-of-values (V)... I hold that it is a law of pure logic.
          [from the Furth translation in Frege (1967)]
Moreover, he thought that an appeal to extensions would answer one of the questions that motivated his work:
          [Letter to Russell, July 28, 1902:]
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)]
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 left-side condition by grounding such reference in the truth of the right-side condition.[10]

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 right-side condition implies the corresponding left-side condition as a matter of meaning.[11]

This view, however, runs up against the following argument. Suppose the right hand condition implies the left-side condition as a matter of meaning. That is, suppose that (R) implies (L) as a matter of meaning:

(R)   x(Fx Gx)

(L)   F = G

Now note that (L) itself can be analyzed, from a logical point of view. No matter whether we construe as an operator or a kind of definite description, (L) (i.e., "the extension of F = the extension of G") can be analyzed as the claim:
There is an object x and an object y such that:
    (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 notion Extension(x,F) (`x is an extension of F'), (L) implies the analysis (D) as a matter of meaning:
(D)   xy[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 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 right-to-left direction of Basic Law V) is not analytic. Below, it will be adapted to show that the right-to-left direction of Hume's Principle is not analytic. See Boolos (1997, 307 - 309), for reasons why Vb and the left-to-right direction of Hume's Principle are not analytic.]

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.

The Existence of Numbers and Truth-Values:
The Julius Caesar Problem

Given that the proof of Frege's Theorem makes no appeal to Basic Law V, some philosophers have argued Frege's best strategy for achieving his goal is to replace Basic Law V with Hume's Principle and argue that Hume's Principle is an analytic principle of logic.[12] However, we have just seen one reason why such a strategy does not suffice. The claim that Hume's Principle is an analytic principle of logic is subject to the same problem just posed for Basic Law V. The equinumerosity of F and G does not, as a matter of meaning, imply (identity claims that entail) the existence of numbers. When we analyze "#F = #G" in the same way that we analyzed "F = G" (i.e., by analyzing away the operator # or definite description "the number of Fs" in terms of existence and uniqueness claims), it becomes clear 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 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:]
... 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)]
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':
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:]
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)]
Now the problem with Hume's Principle is 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 problem is that Hume's Principle doesn't describe, for an arbitrarily chosen object x, the conditions under which the number of planets, say, may be identified with x. It only offers identity conditions when x is an object we know to be a cardinal number (for then x is the number of some concept G and Hume's Principle tells us when x will be identical to the number of planets).

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 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:

          [Gg I, §10:]
...this by no means fixes completely the denotation of a name like `()'. We have only a means of always recognizing a course-of-values if it is designated by a name like `()', by which it is already 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 as such ...
          [from the Furth translation in Frege (1967)]
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.

Again, Frege has a solution, but this time it comes at a price. The first part of the solution is, in essence, to restrict the universal quantifier x of his system so that it ranges only over objects which have been identified as extensions. Given such a restriction, when we ask the question whether an arbitrarily chosen object x is identical with F, we will know that x is the extension of some concept, say G. In such circumstances, then, Basic Law V will tell us, for an arbitrarily chosen object x, the conditions under which x is identical to F. Frege then completes this solution by identifying the two truth values (The True and The False) with the two extensions that contain just these objects as members, respectively. Now all of the objects in the range of his quantifier x are extensions which have been given to us or 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.[13]

The price Frege pays for this solution is that he can no longer extend his system to include names of ordinary non-logical objects. 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 the system can 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.

Final Observations

Even when we replace the inconsistent Basic Law V with the powerful Hume's Principle, Frege's work still leaves two questions unanswered: (1) How do we know that numbers exist?, and (2) How do we precisely specify which objects they are? The first question arises because Hume'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 claim that numbers exist if neither Hume's Principle nor this existential claim is analytically true? The second question arises because Frege's work offers no general condition under which we can identify an arbitrarily chosen object x with a given number such as the number of planets; how then can Frege claim to have precisely specified which objects the numbers are within the domain of all logical and non-logical objects? So questions about the very existence and identity of numbers still plague Frege's work.

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 the non-logical 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 non-logical comprehension principle for sets:

Subset Axiom of (Z):
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
(Z) 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 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:
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 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 well-defined.

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 `Gx' to signify that G is in x:

Numbers:
F!xG(Gx GF)
[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 obsevations: (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.

Since Boolos calls this principle `Numbers', it is no stretch to suppose that he would accept the following explicit reformulation:

Numbers:
F!x[Number(x) & G(Gx GF)]
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:
Identity Principle for Numbers:
Number(x) & Number(y) [G(Gx Gy) x = y]
It is then straightforward to formulate a general principle of identity, as we did in the case of the set theory (Z):
General Principle of Identity:
x = y   =df   [Number(x) & Number(y) & F(Fx Fy)]   v
                    [Number(x) & Number(y) & F(Fx Fy)]
This formulation of Frege Arithmetic, in terms of Numbers and the General Principle of Identity, avoids the Julius Caesar problem. It openly faces the epistemological questions head-on: 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 instantiation relation , see Zalta (forthcoming).]

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.

Bibliography

Other Internet Resources

Related Entries

Frege, Gottlob | Principia Mathematica | Russell, Bertrand | Russell's Paradox

Acknowledgements: I am indebted to William Demopoulos, whose short essay "Gottlob Frege" for the forthcoming Garland Encyclopedia 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.

Copyright © 1998 by
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

Table of Contents

First published: June 10, 1998
Content last modified: December 10, 1998