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:
   he writes about sets and functions, and today's reader
   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
beginning of this article, as well as in letters published
by Dugac, Dedekind writes that he came to know Frege's 79
and 84 only after the publication of 88 .  On the other
hand, not even Dedekind's close collaborator, Heinrich
Weber, knew in 1887 the details of the content of 88 - and
much less so those of 72/78 .


W.F.



More information about the FOM mailing list