Borovik A. Shadows of the Truth: Metamathematics of Elementary Mathematics

Подождите немного. Документ загружается.

Counting Shee p

7.1 Numbers in computer science

An anonymous contributor to my blog

, a profe ssional com puter

scientist, once left the following comm ent:

I would caution everyone . . . not to confuse “mathematical

thinking" with “The thinking done by computer scientists and pro-

grammers".

Unfortunately, most people who are not computer scientists be-

lieve these two modes of thinking to be the same.

The purposes, nature, frequency and levels of abstraction com-

monly used in programming are very dif f erent from those in math-

ematics.

This statement may appear to be extreme, but let u s not to jump

to conclusions and loo k ﬁrst at a very simple example.

I suggest to have a loo k at MATLAB, an industry standard soft-

ware package for mathematical (mo stly numerical) computations.

The follo wing fragment of text is a screen dump of me playing with

natural numbers in MATLAB .

>> t= 2

t = 2

>> 1/t

ans = 0.5000

Mathematics under the Microscope, http://micromath.wordpress.com/.

I apologize to my computer scientist colleagues who on a number of oc-

casions explained to me that MATLAB is nothing more but a gloriﬁed

calculator. I choose MATLAB because, for a lay p erson, it provides an

easy, even if limited, insight into what is going on in computer realiza-

tions of natural numbers.

76 7 Counting Sheep

What yo u see her e is a basic calculation which uses ﬂoating

point arithmetic for computations with rounding; lines starting

with the prompt » are my in put; unmarked lines are MATLAB ’s

response.

Next, let us make the same calculation with a different kind of

integers:

>> s=sym(’2’)

s = 2

>> 1/s

ans = 1/2

Here w e use “symbolic integers”, designed for use as coefﬁcients

in symbolic ex pressions. You can see that in the ﬁrst example 1/2

was rounded as 0.5000, in the second case 1/2 is written as it is, as

a fraction.

Since MATLAB keeps in its memory the values of the variables

s and t, we may force it to combine the two kinds of intege rs in a

single calculation:

>> 1/(s+t)

ans = 1/4

We observe that the sum s + t of a ﬂoating point number t and a

symbolic intege r s is treated by MATLAB a symbolic integer.

Examples involving analytic functions are even more striking:

>> sqrt(t)

ans = 1.4142

>> sqrt(s)

ans = 2^(1/2)

>> sqrt(t)

sqrt(s)

ans = 2

We see that MATLAB can handle two absolutely different represen -

tations of in tegers, re membering, however, the intimate relation

between them.

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

7.2 Counting sheep 77

MATLAB is written in C

. When represented in C

, even the

simplest mathematical objects and structures appear in the form

of (a potentially inﬁnite variety of) classes linked by mechanisms of

inheritance and polymorphism. This is a manifestation of one of the

paradigms of the c omputer science: if mathematicians instinctively

seek to build their discipline around a small number of “canoni-

cal” structures, computer scientists frequently prefer to wo rk with

a host of similarly looking structures, each one adapted for a spe-

ciﬁc purpose. We shall look in the next chapters at how they

keep control of this bestiary. For the time being, we h ave only

to take note that we h ave to be prepared to look at many different

number systems satisfying the Dedekind-Peano axioms.

7.2 C ounting sheep

Fig. 7.1 . The shortening winter’s day is near a close. Joseph Farq uharson,

1846–1935. Source: Wikimedia Commons. Public domain.

The observation that concluded the previou s section is noth-

ing new if we turn our attention from computer languages to the

natural human lore: we already dealt with “named” number s. But

“named” numbers can come in a much more extreme form, as nu-

merals used for co unting speciﬁc types of obje c ts (most likely, they

historically precede the emergen ce of the universal number system

as we know it). In England, a popular slander about Yorkshiremen

is that they u se special numerals for counting sheep. Judging by

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

78 7 Counting Sheep

the Lakeland Dialect Society website [838], local people proud ly

admit to sticking to the old ways. In Wen sleydale, for example, the

ﬁrst ten shee p numerals are said to be

yan, tean, tither, mither, pi p, teaser, leaser, catra, horna, dick.

If we turn to more modern times, it is entertaining to compare

sheep numer als with Richard Feynman’s joke [19]:

You see, the chemists have a complicated way of counting: instead

of saying “one, two, three, four, ﬁve protons”, they say, “hydrogen,

helium, lithium, beryllium, boron.”

This a joke but we have to learn some lessons from it.

One lesson is that we have to distinguish betwe en ordinal nu-

merals, which ex press relative order of objects,

ﬁrst, second, third, . . .

and cardinal numerals which expr ess the cardinality of a set, the

number of elements:

one, two, three, . . .

To my eye, in Feynman’s joke the words

hydrogen, helium, lithium,. . .

look more like o rdinal numer als.

In languages around the world, there is a remarkable diversity

of systems of numerals, both ordinal and cardin al. We have already

discussed in Chap ter 1 a special class of distributive numerals in

the Turkish language.

The Japanese language provides one of mo re striking exam-

ples of diversity of numerals. Here, diffe rent numerals are used for

counting, for example, ﬂat objects (like sheets of paper) and long

slender objec ts (like p encils). I give a table of some of them:

regular simple ﬂat long

numbers objects things slender

things

1 ichi hitotsu ichimai ippo

2 ni futatsu nimai nihon

3 san mittsu sanmai sanbon

4 shi or yon yottsu yonmai yohon

5 go itsutsu gomai gohon

6 roku muttsu rokumai ro ppon

7 shichi or nana nanatsu nanamai nanahon

8 hachi yatsu hachimai h appon

9 ku or ky u kokonotsu kyumai kyuhon

10 ju or jyu tou jumai jyuppon

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

7.3 Abstract nonsense 79

7.3 Abstract nonsense:

universal algebra and category theory

7.3.1 Exi stence and un iqueness

It is time to pause and ask a natural question: why is the proof of

consistency of the inductive deﬁ nition of addition so difﬁcult? We

shall soon see that this is because, as frequently happens in math-

ematics, existence of nice additional structures on a mathematical

object is closely related to the uniqueness o f this obje ct.

Indeed , we had seen in Sections 7.1 and 7.2 that there exists

a bewildering variety of systems of n umerals and computer imple-

mentations of natural numbe rs. In the same time, we for some r ea-

son believe that they all are the same object: a unique canon ical

object which we call the system of natural numbers and denote by

letter N.

In his paper [73] David Pierce summarised difﬁculties demon-

strated in Section 5.6 and Theorem 4:

A set with an initial element and a successor-operation may admit

proof by induction without admitting inductive or rather recursive

deﬁnition of functions.

Historically, this observation was made explicit by Dedekind

[15, II.130] but overlooked by Peano [72]. Edmund Landau himself

[53, Preface for the Teacher] confesses to c ommitting an error—

detected by his teaching assistant—in the ﬁrst version of his lec-

tures. In a m ore algebraic language, the issue is clariﬁed by Henkin

in [34].

In this section I shall present some slightly modiﬁed theor ems

from Henkin’s pap er.

7.3.2 Unary algebras

We shall need some algebraic ter minology o f a very general nature;

similar terms are app lied, for example, to groups and rings.

A unary algebra is an algebraic structure

A = hA; 1, Si

consisting of a groun d set A togethe r with a distinguished element

1 and a unary function S : A −→ A. Notice that every unary algebra

automatically satisﬁes Axioms 1 and 2.

Theorem 8. A unary algebra A sati s ﬁes the Axiom of Induction

(Axiom 5) if and only if A is generated by 1;

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

80 7 Counting Sheep

Landau implicitly (and Henkin explicitly) shows that addition

can be deﬁned by ind uction alo ne. But, as we have just seen, the

argument takes some work.

Notice that it follows from Landau’s proof that addition is d e-

ﬁned and commutative on any 1-generated unary algebra, in par-

ticular, on the algebra show n on Figure 7.2:

1 2 3

···

n + 1

Fig. 7.2. A unary algebra with commutative a nd associative addition (with

thanks to David Pierce).

And would not the reader agree that little Elizabeth Kimber

and little AB had good reasons to be confused?

7.3.3 Proofs

If a u nary algebra hA; 1, Si satisﬁes the Induction Axiom (Axiom 5),

we shall call it an in duction algebra.

If, in add ition, an induction alge bra satisﬁes Axioms 3 and 4, we

shall call it a Peano algebra.

Theorem 9. Let A = hA; 1

, Si be an arbitrary Peano algebra. If

B = hB; 1

, Si is a unary algebra then there ex ists a unique hom o-

morphism

α : A −→ B.

Proof. to be included



7.4 Induction on systems other than N

David Pierce brought my attention to a beautiful example of the

use of indu c tio n on a unary algebra other than N.

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

7.4 Induction on systems other than N 81

Fig. 7.3. Sheep in the Snow. Joseph Farquharson 1846–1935. Source: Wiki-

media Commons. Public domain .

Theorem 10 (Fermat’s Little Theorem). Let p be a prim e. Then

− a = 0

for all a ∈ Z/pZ.

The following proof belongs to Leonard Euler [180]. It had been

presented by Euler to the St. Petersburg Academy of Sciences on 2

August 1936 [196, p. 164]. Gauss repr oduced it in his Disquis itiones

Arithmeticae [185, art. 50]. Both Euler and Gauss were running

induction in Z, but we can do the same in Z/pZ.

We start by observation that the binomial coefﬁcients





k!(p − k)!

for k = 1, 2, . . . , p−1 have denominators not divisible by p and there-

fore are divisible by p. Now it follows from the Binomial Theorem

that

(a + b)

k=0





p−k

≡ a

+ b

mod p.

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

82 7 Counting Sheep

Now we are proving theorem by induction on a. The basis of indu c-

tion is obvious: 1

= 1. Assume now that a

− a = 0 in Z/pZ and

compute

(a + 1)

− (a + 1) = a

+ 1

− a − 1

= a

− 1

= 0,

which proves the inductive step.

7.5 C ategories

I am in general leery of a remark like

“Here’s what the axioms really mean”

when it prefaces a category-theoretic discussion.

David Pierce

A categor y C consists of

• a class ob(C) of objects:

• a class hom(C) of morphisms, or arrows between the objects.

Each morphism f h as a unique source object a and target ob-

ject b where a and b are in ob(C). We write f : a −→ b, and we

say “f is a morphism (or arrow) from a to b”. We write hom(a, b)

to denote the class of all morphisms from a to b.

• for every three objects a, b and c, a binary operation

hom(a, b) × hom(b, c) −→ hom(a, c)

called composition of morphisms; the composition of

f : a −→ b and g : b −→ c

is written as g ◦ f or gf

such that the following axioms hold:

• (associativity) if f : a −→ b, g : b −→ c and h : c −→ d then

h ◦ (g ◦ f) = (h ◦ g) ◦ f,

and

• (identity) for every object x, there exists a morphism

: x −→ x

called the identity morphism for x, such that for every mor-

phism

f : a −→ b,

we have

◦ f = f = f ◦ Id

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

7.6 Digression:N atural numbers in Ancient Greece 83

An initial object o f a category C is an obje c t i in C such that for

every object a in C, there exists prec isely one morphism i −→ a.

Now we can reformulate Theorem 9 in the language of cate-

gories.

Theorem 11. Any Pea no algebra is an initial object in the category

of unary algebras. In particular, any two Peano algebras are isomor-

phic.

7.6 Digression:

Natural numbers in Ancient Greece

A commentary to Plato’s dialogue Char mides by an unknown scholar

describes a clear distinction between ideal natural numbe r s and

numbers used for mundane everyday counting:

Logistic is the science that treats of numbered objects, not of num-

bers; it does not consider number in the true sense, but it works

with 1 as unit an d the numbered object a s number, e.g. i t regards

3 as a triad and 10 as a decad, and a pplies the theorems of arith-

metic to such cases. It is, then, logistic which treats on the one

hand the problem called by Archimedes the cattle-problem, and

on the other hand melite and phialite numbers, the latter apper-

taining to bowls, the former to ﬂocks; in other types of problem

too it has regard to the number of s ensible bodies, treating them

as absolute. Its subject-matter is everything that is nu mbered; its

branches include the so-called Greek and Egyptian methods in

multiplica tions and divis ions, as well as the addition and split-

ting up of fractions, whereby it explores the secrets lurking in the

subject-matter of the problems by means of the theory of triangu-

lar and polygonal numbers. Its aim is to provide a common ground

in the relations of lif e and to be useful in making contracts, but it

appears to regard sens ible objects as though they were absolute.

(Quoted from [227, pp. 17–19], with thanks to David Pierce who

brought this quotation to my attention.)

Exercises

Exercise 7.1 For which values of n does the unary algebra of Figure 7.2

allow the same recursive deﬁniti on of addition and multiplication as i n

Dedekind-Peano arithmetic? If the deﬁn itions are consistent, are the cor-

responding binary operations commutative? associative? Will the di stribu-

tive law of multiplication with respect to addition hold?

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

84 7 Counting Sheep

Exercise 7.2 Prove that if a unary algebra hA; 1, Si satisﬁes the Induction

Axiom (Axiom 5) then it satisﬁes one of the Axioms 3 and 4.

Exercise 7.3 For an inexperienced learner of mathematics, it is sometime

difﬁcult to accept that any two empty sets are equal. Indeed, how can we

claim that the set of all ﬂying pi gs equals the set of all mermaids? There is

nothing in common between pigs and mermaids.

Prove that any two empty sets are equal by considering a category with

sets as objects and appropriately deﬁned morphisms, a nd such th at empty

sets are initial objects in th at category.

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK