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

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

10.4 Carrying: Cinderella of arithmetic 115

move it back later” (eg .36 × .25 = 36 × 25 × .0001) confused me

because I was never quite s ure how many places to move it over.

It was only later that I actually realized that what I was doing

was multiplying everything by a power of ten and then dividing

again later. In the problem above, for example, I would have been

tempted to only move the decimal place b ack two places because

that was how far I had moved it over. I was home-schooled, so I

usually just looked in the back of the book for the right answer

and eventually ﬁgured out the correct pattern, but didn’t under-

stand it till much later.

10.4.2 A few formal deﬁnitions

Let G be a group and A an abelian group with an action of G on A:

G × A → A

(g, a) 7→ g · a.

A 2-co cycle is a map

f : G × G → A

such that

g · f(h, k) + f (g, hk) = f(gh, k) + f(g, h)

Let E be an extension of A by G,

1 −→ A −→ E −→ G −→ 1,

S a system of coset representative of A in E,

s : G → E

a coset map.

Then

f : G × G → A

deﬁned by

s(gh) = f(g, h)s(g)s(h)

is a 2-cocycle. It measures the extent to which the collection of coset

representatives fails to be closed under multiplication.

A 2-coboundary for the action of G on A is a function

f : G × G → A

such that there e xists a functio n

φ : G → A

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

 ALEXANDRE V. BOROVIK

116 10 Ca rrying: Cinderella of Arithmetic

such that:

f(g, h) = g · φ(h) − φ(gh) + φ(g).

Two 2-cocycles for the same extension E dif fer by a 2-coboundary.

Therefore the extensions are described by the second cohomology

group

(G, A) = Z

(G, A)/B

(G, A),

where Z

(G, A) is the group of 2-cocy cles with respect to natural

pointwise addition and B

(G, A) is the gr oup o f cobou ndaries.

I leave it to the reader as an exerc ise to show that “carry” is a

2-cocycle.

10.4.3 Limits and series

Carry has another interesting property: it con tains a seed of a con-

cept of limit le ading to immensely rich p -adic an alysis.

In this context, it is interesting to analyze how p-adic analysis

arises from the purely algebraic concept of carry and co mpletely

avoids all alleged psychological traps which imperil the study of

real analysis.

Very frequ ently, when we deal with a mathematical object and

wish to modify it and make it “inﬁnite” in some se nse, we have

several different ways for doing so. For example, the usual deci-

mal nu mbers can be extended to inﬁnite decimal expansions to the

right:

π = 3.1415926 . . .

and to the left:

. . . 987654321

In the second case, the operations of multiplication and addition on

“inﬁnite to the left” decimals ( called 10-adic integers) are deﬁned in

the usual way, with the excess carried to the next position on the

left. Carries march on and on, uninterruptedly, and this steadine ss

of their pace is the psychological basis of a very intuitive concept of

limit.

10-adics are not frequently used in mathematics, but p-adic in-

tegers for prime values of the base p, deﬁned in a similar way by

expanding integers written to base p to the left, are quite useful

and ver y popular.

10-adic integers are n ot so good as p-adic for prime p because

they contain zero divisors, non-z ero numbers x and y such that

xy = 0. The following elementary example was provided by Hovik

Khudaverdyan and Gábor Me gyesi an d nicely illustrates the con-

cept of 10-adic limit. If you look at the sequ ence of iterated squares

5, 5

= 25, 25

= 625, 625

= 390625, 390625

= 152587890625 . . .

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

 ALEXANDRE V. BOROVIK

10.4 Carrying: Cinderella of arithmetic 117

you notice that consecutive numbers have in common an increas-

ingly long sequenc es of the rightmost digits, that is,

n+1

≡ 5

mod 10

the fact which could be easily proven by induction. This freezing

of righ tmost digits means that the sequence converges to a 10-adic

integer

x = . . . 92256259918212890625.

One can e asily see that x has the property that

= x

and hen c e

x(x − 1) = 0.

Therefore x and x − 1 are desired zero divisor s.

It can be shown that zero divisors app ear in the ring of 10-adic

integers because 10 is not a prime number. An exerc ise for the

reader: prove that the ring of 2-adic integers has no zero div isor s.

Properties of 10-adic and p-adic integers are quite differ ent from

those of real numbers: to give one example, y ou cannot order 10-

adic integer s in a way compatible with addition and multiplication

(so that the usual rules of manipulating inequalities would hold).

This can be seen already from one of the simplest instances of ad-

dition:

. . . 99999 + 1 = . . . 00000 = 0.

For lack of space, I will me ntion only one other pro perty of p-adic

integers made self-explanatory by application of simplest rules of

operating with carries.

10.4.4 Euler’s sum

Notice that a paradoxical summation of the inﬁnite series

1 + 2 + 4 + ··· = −1,

due to Euler, makes sense and is completely correct if one uses 2-

adic integers written by base 2 expansions. Indeed, it becomes an

easy-to-check arithmetic calculation:

1 + 2 + 4 + 8 + ··· = 1 + 10 + 100 + 1000 + ···

= ···111111111

But

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

 ALEXANDRE V. BOROVIK

118 10 Ca rrying: Cinderella of Arithmetic

···111111111

+ 1

= ···000000000

Hence in 2-adic arithmetic

1 + 2 + 4 + 8 + ··· = −1.

It is worth noting that Euler was most likely to know binary

numbers. A ﬁ rst clear description of them in mo dern notation was

published in 1703 by Gottfried Leibniz in his p aper Explication de

l’Arithmétique Binaire [208], see Figure 10.1:

0 = 0

1 = 1

2 = 10

3 = 11

4 = 100

5 = 101

6 = 110

7 = 111

= 10 ···0 ( n zeroes)

As Anton Glaser exp lains in [187], Leibniz was not the ﬁrst to

come up with binary numerals; Glaser ﬁnds the origins of binary

numerals in unpublished manu scripts of the English mathemati-

cian and astronomer Thomas Harriot (c. 1560-1621) and in work of

Bishop Juan Caramuel y Lobkowitz (1606-1682).

10.5 Unary number system

I do not remember when I was ﬁrst shown this unsophisticated

party trick: you ask someone to write down, in secret, a one digit

number. As a r ule, lay persons write down 7. Also, as a rule, math-

ematicians write down 1. It is a part of a general tendency to look

at simplest and/o r most degenerate cases.

And now listen to Alexey Muranov

AM is male, Russian, has a PhD in mathematics, works in a French

university.

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

 ALEXANDRE V. BOROVIK

10.5 Unary number system 119

I remember that I could understand the algorithms for adding and

multiplying numbers, but the algorithm of long di vision was much

harder, I might have ended up just memorizing it. This must have

been my 2nd or 3 rd grade.

Later it was a revelation to me, probably in 7th or 8th grade,

that numbers are not strings of digits.

This happened wh en I realized that the base-n number system

has all the same rights to name numbers as the base-10 number

system, and h ence the number itself was not what I thought it was

before, it existed independently of the number system, and if any

number system had to be the preferred one, that should have been

probably the unary number system (where

1 = “1”, 2 = “11”, 3 = “111” . . .

but I do not remember if I h ad this idea myself, or learned it some-

where later).

Exercises

Exercise 10.1 If you still believe that real nu mb ers are the best of all

worlds, try to ﬁnd, with out a calcul ator, the ﬁrst three digi ts of the ratio

0.12345 ···484950

0.5152 ···99100

In princip le, the ﬁrst few digits of the numerator and the denominator

should sufﬁce for the computation. But how many of them do you need?

Exercise 10.2 Check the 2-cocycle property of carries.

Exercise 10.3 Compute

(Z, Z/10Z)

for the trivial action of Z/10Z on Z.

Exercise 10.4 Prove by induction on n that, for all natural numbers n,

n+1

≡ 5

mod 10

Exercise 10.5 [651] The list of nu mbers

49, 4489, 444889, 44448889, 4444488889, . . .

goes on for ever. What is the next number on the list? The ﬁrst number

49 is a perfect square. Is the second number 4489 a perfect square? Is the

tenth number on the list a perfect squa re? Which other numbers in the list

are perfect squares?

Exercise 10.6 Prove that a 10-adic integer has an inverse if a nd only if

its last digit is 1, 3, 7 or 9.

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

 ALEXANDRE V. BOROVIK

120 10 Ca rrying: Cinderella of Arithmetic

Hint. If the last digit of x is 1, we can write it as x = 1 + 10y and

(1 + 10y)

−1

= 1 − 10y + 100y

− 100y

+ ··· ,

with the expression on the right making sense because in the inﬁ nite sum

in every position we sum up only ﬁnitely many digits.

Exercise 10.7 Prove that a 2-adic integer has an inverse if and only if its

last digit is 1.

Exercise 10.8 Prove th at every 2-adic integer can be written in the form

· x, where k is an (ordinary) non-negative integer and x is an invertible

2-adic integer.

Exercise 10.9 Prove that the rin g Z

of 2-adic integers is a domain, that

is, it has no zero divisors.

Exercise 10.10 [86] Prove that the p -adic i nteger

···0100000000000000000100011 =

∞

k=1

is transcendental, that is, it is not a root of any polynomial with integer

coefﬁcients.

Exercise 10.11 Study the arithmetic properties of the ring Z[[x]] of formal

power series over integers; here, formal power series are expressions

+ a

x + a

+ ··· + a

+ ···

with all coefﬁcients a

∈ Z, with the usual operati ons of addition a nd mul-

tiplicati on.

• Is Z[[x]] a domain? (Domain is a commutative ring which has no zero

divisors.)

• Which elements of Z[[x]] are invertible? An invertible element in a do-

main R, that is, an element r ∈ R such that rs = 1 for some s ∈ R is

also called an unit.

• Take a page from DW’s book and ﬁnd in Z[[x]] the inverse of

1 + 2x + 3x

+ 4x

+ 5x

+ ··· .

• Does Z[[x]] have unique factorization?

See [6] for answers.

Exercise 10.12 Try column (long) multiplication of unary nu mbers, say,

111 × 11. And what about long division?

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

 ALEXANDRE V. BOROVIK

Fig. 10.1. A page from Leibnitz’s paper about binary system [208].

Pedagogical Intermission:

Nomination and Deﬁnition

We all know the old story abo ut the rustic

who said he wasn’t surprised that

savants with all thei r i nstruments

could ﬁgu r e out the size of stars and

their course—what bafﬂed him was

how they fou nd out their names.

L. S. Vygotsky [404]

The conver sation with DW raises an interesting issue—children

need names for the conc epts, objects, and structures they meet

with in their ﬁrst encounters with arithmetic. Moreover, they need

names for basic discriminating objects in the world, and naming is

an integral part of infan t’s cognitive strategy, starting with their

ﬁrst words [419].

Many my correspondents report the importance of availability

of names for their understanding of mathematics: ¸SUE had intu-

itive understanding of the concept of a prime number, but did not

know the name. Elizabeth Kimber told me that her troubles would

have been instantly resolv ed if her teacher had mentioned to h er

that addition is co mmutative. She suffered more from he r inability

to communicate her difﬁculties to adults than from the difﬁculties

as such.

And, of course, inventing names is a natural part of a child’s

games. Here is a testimony from Jü r gen Wolfart

Probably I was four years old when my mother still forced me to go

to bed after lunch for a while and have a little sleep (children don’t

need this rest a f ter lunch, but parents need child ren’s sleep). Quite

often, I couldn’t sleep and made some calculations with small inte-

gers to entertain myself, and afterwards I presented the results to

my mother. Soon, I d id not restrict myself to addition (“und”) and

invented by myself other arithmetic operations—unfortun ately I

JW is male, German, a professor of mathematics.

123

124 11 Pedagogical Intermission:Nomination and Deﬁnition

don’t remember which, probably “minus”—but I invented also a

name for it, of course not the usual one. I don’t remember which

name, but I remember that my mother reconstructed from my re-

sults what operation I had in mind and told me wha t I did in ofﬁ-

cial terminology. So I f orgot my own words for it, but I had a new

toy for the siesta time.

Mathematics is a p lethora of names, and even memor izin g them

all could already be a challenging intellectual task for a child. Not

surprisingly, the following observ ation belongs to a poet; it is taken

from Cahiers (Notebooks) Paul Valéry:

Vu Estaumier, nommé Directeur de l’Ecole Supérieure des PTT. Me

dit que, enfant, à 6 ans il avait a ppris à compter jusqu’à 6 – en 2

jours. Il comprit alors qu’il y avait 7, et ainsi d e suite, et il p rit peur

qu’il fallû t apprendre une i nﬁnité de noms. Cet inﬁni l’épouvanta

au point de refuser de continuer à a pprendre les a utres nombres.

[842, Tome II, p. 798]

Notice that a child was frightened not by inﬁnity of numbers,

but by inﬁnity of nam e s; he was afraid that the sequence of rando m

words lacking any pattern or logic:

un, deux, trois, quatre, cinq, six, . . .

will drag on and on for ever. I agree—it is a scary thought. But

mathematics can bring safety back by providing means for a sys-

tematic production of the inﬁnity of names, as evidenced by Roy

Stewart Roberts:

At some point [. . . ] I had discovered that you can continue count-

ing forever, using the usual representation of numbers if one ran

out of names.

An enforced siesta—or other forms of conﬁnement in a bed—f eature

prominently in childhood stories. What follows is a testimony from

Mikhail Belolipetsky:

I have fragmented memories of searching for various paths on a

carpet that was hanging on the wall above my bed (that is, cycles

in a graph). I was about four or ﬁve years old.

MB is male, Russian, has a PhD in mathematics, he is a lecturer in

mathematics in a British university.

Seen Estaumier, appointed Manager of the S chool of PTT [this is the

French Postal and Communication Service]. Tells me that, as a child of

6, he had learnt h ow to count up to 6—took him 2 days. He then under-

stood that there was 7, and so on, and he was scared that he would ha ve

to learn an inﬁnity of names. This inﬁnity frightened him to the point

that he refused to keep on learning the other numbers. Translation is by

Adrien Deloro. The quote i s kindly provided by Donald Preece.

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

 ALEXANDRE V. BOROVIK