# FOM: Frege and Dedekind on Numbers

Walter Felscher walter.felscher at uni-tuebingen.de
Thu Apr 2 11:02:57 EST 1998

Dedekind, in the preface to the second edition 1893 of
Was-sind-und-was-sollen-die-Zahlen and referring to the
first edition, writes (and I translate here immediately)

About one year after the appearance of my book, I came to
know the Grundlagen der Arithmetik of G.Frege which had
come out already in 1884 . However different the view,
presented in that work about the nature of number, may be
from the mine, still it contains, beginning with para 79 ,
points of close contact with my book, particularly with my
explanation (44) . Certainly, this agreement is not
easily recognized because of the different terminology;
but already the determination, with which the author
expresses himself about the argumentation from n to n+1
(on p.93 bottom), shows clearly that here he shares the
ground with me.

In this note, I shall observe that Frege and Dedekind do,
actually, present widely parallel lines of mathematical
argument to establish the same fact as their principal
technical result: the construction from a map s of a
relation < such that

(*)  < is an irreflexive linear order for which s(x)
is the immediate successor of x , and x is the
immediate predecessor of s(x) .

The literature I shall refer to is

Frege    79     Begriffsschrift, eine der arithmetischen
nachgebildete Formelsprache des reinen
Denkens . Halle 1879

Frege    84     Die Grundlagen der Arithmetik . Breslau 1884

Dedekind 72/78  Gedanken u"ber die Zahlen.
Manuscript 1872-1878 with several drafts of 88 ,
reprinted as Appendice LVI on pp. 293-309 of
Pierre Dugac: Richard Dedekind et les fondements
des Mathematiques. Paris 1976

Dedekind 88  Was sind und was sollen die Zahlen . Braunschweig 1888

1.   General background

1a.  Dedekind

The purpose of Dedekind's 88 is to derive existence and
properties of both arithmetic operations and order from the
simple, well known axioms for the structures <N,s,o> .
Arithmetical operations are easy to introduce once the
existence of functions defined by simple recursion has been
secured. As Dedekind wants to construct them from below,
i.e. from their germs on intervals [o,n] , he needs to
establish order first; thus he has to pursue as his
intermediary aim the technical result (*) .

Note 1 : The insight, that the existence of recursively
defined functions requires a proof, was so completely new
that it remained unnoticed still in 1929 when the
famous Landau, in his draft of 30 , did not realize that
he had used such existence, an oversight then corrected
by Kalmar. Also the sharp-minded Peano, who in 89 copied
Dedekind's axioms into "Peano's axioms", continued to use
recursively defined functions without justifying their
existence. That existence proofs can also be performed
from above seems first to have been noticed by Paul
Lorenzen 38 .

Peano    89  Arithmetices principia novo methodo exposita. Torino 1889
Landau   30  Grundlagen der Analysis. Leipzig 1930
Lorenzen 38  Die Definition durch vollst"andige Induktion.
Monatshefte Math.Phys. 47 (1938)

Note 2 : Dedekind's book is, from the outset, mathematical:
can understand it as if it were written recently, if only
he translates the termini (Dedekind writes 'system' for
our 'set') and symbols (say for inclusion) into the ones
employed now. That this is so, may be seen as another
success of Dedekind's efforts who, beginning with 71 ,
had used the language of sets to describe algebraic
structures such as fields and modules, as well as the
maps between them.

Dedekind 71  U"ber die Komposition der bina"ren quadratischen
Formen. Supplement X von Dirichlets Vorlesungen
u"ber Zahlentheorie, 2te Auflage. 1871

1b. Frege

The aim of Frege's 84 is a purely conceptual foundation of
the notion of cardinal number, "Anzahl" ; his solution is to
define the cardinal number of a concept F as the extension
of the concept "to be equinumerous with F " , where concepts
F and G are called equinumerous if there is a bijection
between their extensions. The larger part of the 119 pages
of the booklet is devoted to a discussion of the earlier
philosophical literature in so far as it had attempted such
foundation. Only on page 79 Frege's solution is introduced,
and its discussion closes already on page 96 : it contains
a sketch of the introduction of order between finite
cardinals, ending with the formulation of a theorem which,
in today's terminology, says

If n is finite, and if m is the cardinal of all x between o
and n , then m is immediate successor of n .

Again, in the course of this development Frege has to establish
the technical results collected above as (*) .

The 17 pages, devoted to this aim in 84 , contain, if at
all, only indications of proofs.  However, these proofs had
been actually carried out already in section III of Frege's
79 , "Einiges aus einer allgemeinen Reihenlehre".  It was
most unfortunate for their reception that they appear there
in the form of illustrations of Frege's two-dimensional
logical calculus, the newness of which made them quite
inaccessible to his (and maybe be even to our)
contemporaries.

2.   Mathematical analysis

I shall outline, in today's mathematical terminology, the
mathematical methods used by Dedekind and Frege in order
to prove (*) .

Let E be a set, and let X, Y , ...  range over subsets of E .
Writing in ASCII , I denote membership by e and inclusion
by c .

Let S be 2-ary relation relation on E , and let S(x) be the
set of all y such that xSy . Let s be a map from E into E ,
let s(x) be the image of x under s , and let s(X) be the set
of all s(x) for x e X .

2a.  Dedekind.

Statements # n are numbered in 88 . The line of argument
proceeds as follows.

# 37 : Define X to be s-closed [Dedekind: Kette ]
if x e X implies s(x) e X .

# 44 : Define K(Y) to be the intersection [Dedekind: Gemeinheit ]
of all s-closed X with Y c X .

# 43, 47 : K(Y) is the smallest s-closed set containing Y .

# 53 : X c K(Y)  iff  K(X) c K(Y) .

# 58 : K(Y) is the union of Y and K(s(Y)) .

# 59, 60 : Mathematical induction:
If Y c Z and
if ( x e Z and x e K(Y) implies s(x) e Z )
then  K(Y) c Z .

>From now on, let E, s, o be such that s is injective,
o is in E - s(E) , and E = K({o}) ( for short: <E,s,o>
is a Dedekind triple ). Write K(x) for K({x}) .

# 74 : y e K(x) iff  K(y) c K(x) . [by # 53 ]

# 77 : K(x) is the union of {x} and K(s(x)) . [by # 58 ]

# 78 : E is the union of {o} and s(E) .

# 79 : If o e X and X is s-closed then X = E .

# 81 : not x = s(x) .                    [induction]

# 82 : Not y e s(K(y) .                [induction]

# 83 : The inclusion K(s(x)) c K(x) is proper .

# 84 : If K(x) = K(y)  then  x = y

# 85 : Is  X is s-closed and not y e X  then  X c K(s(x)) .
[ induction, # 78 , # 77 ]

# 88 : If not x = y  then either K(x) c K(s(y)) or K(y) c K(s(x)) .
[ by # 83 , # 84 , # 85 ]

# 89 : Define x < y  if  K(y) c K(s(x))  [ iff  y e K(s(x)) ] .

# 90 : Either x = y  or either  x < y  or  y < x ;
in particular  not x < x .
[ by # 84 , # 88 ]
# 91 : x < s(x)

Define x <= y  as  x < y or x=y .

# 93 : x <=y  iff  x < s(y)  iff  K(y) c K(x) .

# 94 : s(x) <= y  iff  s(x) < s(y)  iff  x < y

It follows that < is a irreflexive linear order (# 90 ) and
that s(x) is the immediate successor of x (# 94) and y is
the immediate predecessor of s(y) (# 93) .

# 96 : If X is not empty then it contains a smallest element .

2b.  Frege

Statement Anm is the statement denoted as " (nm. " in 79 .
Statement Bnm is taken from para nm of 84 .
Statements C are immediate corollaries not stated by Frege

The statements quoted here from 79 are not presented with
Frege's proofs which employ the Begriffsschrift; if not
obvious, their proofs here are stated in informal mathematical
manner. The line of argument proceeds as follows :

A69  : Define X to be S-closed if x e X implies S(x) c X .
[ "X vererbt sich in der S-Reihe" ]

A76  : Define x < y  if for every S-closed X : S(x) c X implies y e X
B79                 [ "y folgt in der S-Reihe auf x" ]

C1   : If y e S(x) then x < y  .

A81  : If X is S-closed and if x e X and x < y  then y e X .
[A, p.64 : "Hierauf beruht die Bernoullische Induction"]

A98  :  <  is transitive

A99  : Define [x,-) to consist of all z such that x = z or x < z .
B81              [ "die mit x anfangende S-Reihe" ]
Write x <= z for these z .

A109 : [x,-) is S-closed

C2   : [x,-) is the smallest S-closed set containing x . By At81 .

>From now, A para 31 , on let S be a map denoted as s .

A110 : If s(y) e [x,-) and y < z  then  z e [x,-)

Proof: [x,-) is an S-closed set X . Thus y < z implies
(if S(y) c X then z e X ). Also, s(y) e [x,-)
by assumption. Thus z e X by definition in A76 .

A124 : If y < z  then  z e [s(y),-)

Proof: Take x to be s(y) in A110 .

C3   : [s(x),-) is the set of all z such that x < z .

C4   : [x,-) is [s(x),-) joined with {x} .

A131 : For every z , the set of y with  y e [z,-) or y < z is s-closed .

Proof: If z <= y  then  z <= s(y) . If y < z then s(y) <= z ,
hence either s(y) = z , z <= s(y) , or s(y) < z , y < z .

A133 : If x <= y and x <= z  then  y e [z,-) or y < z .

Proof: (Frege assumed  x < y and x < z ) Given z , let
Y be the set defined in A131 . Then Y is also the set
of all y with  y e [z,-) or y <= z . Let Y' be the
common part of [x,-) and Y ; then also Y' is s-closed.
Also, z <= x implies that x is in Y and Y'. Thus [x,-)
is contained in Y'.

C5   : If x <= y and x <= z  then  z <= y or s(y) <= z .

Proof: By A133 and A124 .

Frege's 79 ends with A133 . In 84 the Begriffsschrift is not
employed; the basic definitions A69 , A76 , A99 are repeated
in words, and A81 is mentioned. Frege there considers a particular
situation with a special E and special s , and also with a
particular element o of E, with which he restricts E to be [o,-) ;
this is equivalent to the assumption that

E is the only s-closed set containing o .

In B83 Frege observes that now, in his particular situation,
the relation < can be shown to be irreflexive; the proof is
said to proceed by induction and is left to the reader. Indeed,
the particular situation has the effect that

s is injective  and
o is not of the form s(y) ,

such that now the axioms for a Dedekind triple have become
available. Hence I obtain irreflexivity as follows :

C6   : For every x : not  x = s(x)  .

Proof: Not o = s(o) as o is no image, and not x = s(x)
implies not s(x) = s(s(x)) by injectiveness of s .

C7   : Not  o < o  .

Proof: Let X arise from the s-closed set [o,-) be removing
o . As o is no image under s , the set X remains s-closed,
and as not o = s(o) , it contains s(o) . Thus not  o < o
by definition.

C8   : If  not x < x  then  not s(x) < s(x) .

Proof: Not x < x implies not s(x) <= x . Let X arise from
the s-closed [s(x),-) by removing s(x) . Would X not be
s-closed then s(x) = s(z) for z in X , s(x) <= z , but
x = z by injectiveness, hence s(x) <= x , and this again
would imply  x < x . Hence X remains s-closed, and by C6
it still contains s(s(o)). Thus not s(x) < s(x) .

C9   : For every x : not  x < x  .

C10  : If z < s(y)   then  z <= y  .

Proof: By C5 there holds  z <= y or s(y) <= z . In the latter
case, z < s(y) <= z  would give  z < z  .

It follows that < is an irreflexive, linear (by A133) order
for which s(x) is the immediate successor of x (by A124) and
x is the immediate predecessor of s(x) (by C10).

Note : The particular situation studied by Frege, as
alluded to above, is concerned with the introduction of
finite cardinals ("Anzahlen"). Frege defines in 84

B68 : The cardinal of a concept C is the class of
all sets equivalent to the extension of C

B75 : o is the cardinal of the concept "different from itself"

B76 : The cardinal n is immediate successor of the cardinal m
if there is a concept C with cardinal n and
there is an object a belonging to C  and
the concept "x belongs to C and is different from a"
has the cardinal m .

B83 : The cardinal n is finite if  o <= n

Restricting the study to finite cardinals then amounts to
making the hypothesis  E = [o,-) .

2c.  Comparition

The similarities between Dedekind's and Frege's approaches to
the result (*) are obvious; I shall restrict myself to point
out some differences.

Dedekind introduces the relation < much later than Frege,
preceding this introduction with a more general framework about
chains.

Dedekind uses elementary set language, in particular the
formation of intersections already in # 44 , whereas Frege
forms sets only by collecting with respect to a property:
A99 and B81 .  This availability of sets leads Dedekind to
also state auxiliary observations (such as irrflexivity # 82 )
at a considerably earlier stage than Frege.

Dedekind's sets K(x) are the same as Frege's [x,-) ; Dedekind
can define them generally, while Frege needs to have <
available already. Consequently, while Frege needs the
family _F(s(x)) of all s-closed sets containing s(x) for his
definition

x < y  if for every X in _F(s(x)): if s(x) e X  then  y e X  ,

Dedekind's definition

x < y  if  y e K(s(x))

requires only the one member K(s(x)) = [s(x), - ) of that
family, although this, in turn, did need for its definition
the reference to the entire family _F(s(x)) .

As for the questions of priority, we can with, with high
probability, say that Frege and Dedekind invented their
methods independently. In the preface quoted in the