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

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

5.7 Induction and recursi on 55

and by Lagrang e’s Theore m (known in this special case as Euler’s

Theorem,

φ(n)

= 1

for every a ∈ (Z/nZ)

∗

, hence raising a to powers from Z/φ(n)Z make

sense. This modular exponentiation is widely used in cryptography;

we shall re tur n to it later in the book.

Notice that modular exponentiation is not a function

Z/nZ × Z/nZ → Z/nZ.

When we state Fermat’s Theorem

≡ a mod p

the exponent p is not to be under stood mod ulo p.

I share David Pierce’s indignation at the state of affairs [73]:

Yet the confusion continues to be made, even in textbooks intended

for students of mathematics and computer science wh o ought to be

able to understand the distinction. Textbooks also perpetuate re-

lated confusions, such as suggestions that induction and ‘strong’

induction (or else the ‘well-ordering principle’) are logically equiv-

alent, and that either one is sufﬁcient to axiomatize the natural

numbers. [. . . ]

This is one example to suggest that getting things straight may

make a pedagogical difference.

But I have to admit that I shared the widespread ignorance un -

til David Pierce brought m y attention to the issue—despite the fact

that, in a calculus course that I took in the ﬁrst year of my univer-

sity studies, the lecturer (Gleb Pavlovich Akilov ) explicitly proved

the existence of a function of natural argument deﬁne d by a recur-

sive scheme [1].

To save our theory from collapse, we shall prove the existence of

addition after a brie f ped agogical digr ession.

5.7 Induction and recursion

From a pedagogical point of view, recursion is simpler than induction—

because it goes back, to smaller numbers and simpler cases.

This is supported by another childhood story, from BB

I would like to point out that the stories are provided by the peo-

ple who happen to stumble on this blog. I am sure that the read-

ership of this blog is atypical in terms of mathematical thinking

BB was 11 or 12 years old a t the time of the story. He is male, Russian,

currently a PhD student in pure mathematics.

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

 ALEXANDRE V. BOROVIK

56 5 Adding One by One

Fig. 5.4. A cyclic Gray code discussed by BB in his story is a cyclic path on

edges of the n-cube passing exactly once through each vertex of the cube.

In this picture, n = 3.

and l earning. Most people who have responded have not only gone

to deal with unusually abstract concepts in their ca reer, bu t actu -

ally do mathematics. So, the examples here might represent not

so much the major difﬁculties that need to be overcome before an

understanding can b e reached (as in ﬁnding the correct way of

thinking of division of apples by apples ), but the signs that un-

derstanding has already been reached, and that the difﬁculty is

purely semantic, i.e. how to express it.

My own story: In our math circle we covered indu ction (domino

analogy, proofs of summation formulae such as

1 + ··· + n =

n + 1

and varied other examples). I did passably well on the problems,

but still I did not understand what induction was really for, un-

til the end-of-year competition. I failed to solve a single problem:

arrange all binary strin gs of length 10 around the circle so that

two adjacent strings diff er in precisely one position (it is known

as a cyclic Gray code of s ize 10). It was when I was told the solu-

tion that I felt that I ﬁnally u nderstood the ind uction. The missing

element was probably the fact that I did not realize that the state-

ment proved by induction is an honest mathematical statement

that pertains to concrete nu mbers like 10, and not only to x, y, n,

m and 1996, among which only the latter is a number, but so big

and arbitrary tha t i t could as well be denoted by n.

And another story, from RTC:

I do remember that when I was about 12 or 13 at school we were

taught mathematical induction for the ﬁrst time. Despite the fact

RTC is male, B ritish, a professor of mathematics in a British u niversity.

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

 ALEXANDRE V. BOROVIK

5.8 Digression into inﬁnite descent 57

Fig. 5.5. BB in his story reminds us that induction is frequently used to

prove s ome statement not for al l natu ral numbers, b ut just for some par-

ticular na tural number. In the famous domino tipping Guinness advert

(Tipping Point, director Nicolai Fuglsig, 2007) the sequence of tipping ob-

jects was ﬁnite ( 6,000 dominoes, 10,000 books, 400 tyres, 75 mirrors, 50

fridges, 45 wardrobes and six cars) and culminated in this tower of books.

that I was supposed to be the maths whizz who would catch on

to any new concept very quickly, I distinctly remember feeli ng

cheated by induction. At tha t age we had onl y ever proved things

directly, and with in duction we seemed to be s ide-stepping the is-

sue and not proving anything.

5.8 Digression into inﬁnite descent

Let us have a look at the historic predecessor of induction, princi-

ple of inﬁnite decent. Its use can be traced to Proposition XIII.6 of

Euclid’s Elements

The quickest p r oof by inﬁnite descent is perhaps proof of irra-

tionality o f the Golden Ratio (I found it in a beautiful little book by

Tim Gowers [122, p. 44]).

Theorem 5. The Gold en Ratio is irrational.

Proof. By deﬁ nition, the rectangle ABCD is a golden rectangle, if

after cutting off the square BBCC, the remaining rectangle ADCB

is similar to the original one, ABCD. The ratio of lengths of sides

of a golden rectangle is called the golden ratio.

http://www.claymath.org/library/historical/euclid/

files/elem.13.6.html.

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

 ALEXANDRE V. BOROVIK

58 5 Adding One by One

Fig. 5.6 . Inﬁnite descent. This poster gave birth to the term Droste effect.

Source: WIKIMEDIA COMMONS. Public domain.

Günter Törner writes about a similar image:

At the age of 7 I get aware of some advertising of a brandy (gin)

showing the bottle placed into a nice landscape. And on the la bel on the

bottle there was the same drawing, however smaller (and on this picture

on the bottle was a sma ller bottle etc.). Ad inﬁnitum—I thought and I was

fascinated by the idea.

If the golden r atio were r ational, a “golden rectangle” could be

drawn on square grid paper; see Figure 5.7. After cutting a square

from it we get a smaller “golden rectangle ” drawn on square grid

paper. By principle of inﬁnite descent, this is impossible—hen ce the

golden ratio is irrational.

Hmm, we did not even care about the numeric value of the

golden ratio . . . 

And, to co nclude this section, I give one more e xample of an

argument by inﬁnite descent: proof of irrationality of

√

Theorem 6.

√

2 is not rational.

Proof. We shall prove an equ ivalent, but a stranger looking state-

ment: if

√

2 is rational the n it is an integer. Set

√

2 =

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

 ALEXANDRE V. BOROVIK

5.9 Landau’s proof of the existence of addition 59

Fig. 5. 7 . Golden Rectangle.

where p and q are natural numbers; select such repr esentation for

√

2 with the smallest possible q. Our aim is to prove that q = 1; if

this is not the case the n observe that

q < p < 2q

and

2q − p

p − q

(check this identity!) is a representation with a smaller d enomina-

tor. A contradiction. 

5.9 Landau’s proof of the existence of addition

I decided to borrow verbatim a proof of the existence of addition

from Edmun d Landau’s famous book Grundlagen der Analysi s [53].

It is from his book that I picked up the notation

S(n) = n

′

which I had already used in my proofs. Although this is not empha-

sized by Landau, the proo f of consistency of addition does not use

Axioms 3 and 4. Are these axioms of any use at all? We shall return

to this question later.

Theorem 7. [53, Theorem 4] To every pair of numbers x, y, we may

assign in ex actly one way a natural number, called x + y, such that

(1) x + 1 = x

′

for every x,

(2) x + y

′

= (x + y)

′

for every x and every y.

Proof. (A) First we will show that for each ﬁxe d x there is at most

one possibility of deﬁning x + y for all y in such a way that

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

 ALEXANDRE V. BOROVIK

60 5 Adding One by One

x + 1 = x

′

and

x + y

′

= (x + y)

′

for ever y y.

Let a

and b

be deﬁned for all y an d be such that

= x

′

, b

= x

′

, a

′

= (a

)

′

, b

′

= (b

)

′

for ever y y.

Let M be the set o f all y for which

= b

(I) a

= x

′

= b

; hence 1 belongs to M.

(II) If y belongs to M, then a

= b

, hence by Ax iom 2,

)

′

= (b

)

′

therefore

′

= (a

)

′

= (b

)

′

= b

′

so that y

′

belongs to M.

Hence M is the set of all natural n umbers; i.e. for every y we have

= b

(B) No w we will show that for each x it is actually possible to

deﬁne x + y for all y in such a way that

x + 1 = x

′

and x + y

′

= (x + y)

′

for ever y y.

Let M be the set of all x for which this is possible (in exactly

one way, by (A)).

(I) For x = 1, the number x + y = y

′

is as required, since

x + 1 = 1

′

= x

′

x + y

′

= (y

′

)

′

= (x + y)

′

Hence 1 belongs to M.

(II) Let x belong to M, so that there exists an x + y for all y.

Then the number x

′

+ y = (x + y)

′

is the required number for x

′

since

′

+ 1 = (x + 1)

′

= (x

′

)

′

and

′

+ y

′

= (x + y

′

)

′

= ((x + y)

′

)

′

= (x

′

+ y)

′

Hence x

′

belongs to M. Therefor e M contains all x. 

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

 ALEXANDRE V. BOROVIK

5.9 Landau’s proof of the existence of addition 61

Landau’s book is characterized by a speciﬁc austere beauty

of entirely formal axiomatic de velopme nt, dry, cut to the bone,

streamlined. Not surprisingly, it is claimed that logical austerity

and precision w ere Landau’s characteristic personal traits.

Grundlagen der Analysis opens with two pref aces, one inte nded

for the student and the other for the teacher; we shall return to

Preface for the Teacher in Section 7.3.1, it is a remarkable pedagog-

ical document. The preface for the stude nt is very short and begins

thus:

1. Please don’t read the preface for the teacher.

2. I will ask of you only the ability to read Engli sh and to think

logically-no high school mathematics, and certainly no hi gher

mathematics. [. . . ]

3. Please forget everything you have learned in school; for you

haven’t learned it.

Please keep in mi nd at all times the corresponding portions

of your school curriculum; for you haven’t actually forgotten

them.

4. The multiplication table wi ll not occur in this book, not even

the theorem,

2 × 2 = 4,

but I would recommend, as an exercise for Ch ap. I, section 4,

that you deﬁne

2 = 1 + 1,

4 = (((1 + 1) + 1) + 1),

and then prove the theorem.

Our discussion of natural numbers continu es in Chapter 7.

Exercises

Exercise 5.1 Prove Theorem 4 for prime values of n. You may wish to use

Fermat’s Theorem:

If p is a prime integer and 0 < a < p th en

≡ a mod p.

Exercise 5.2 Then try to prove Theorem 4 in full generality.

Exercise 5.3 Follow Edmund Landau’s advice and prove from the Dedekind-

Peano axioms that

2 × 2 = 4.

Asked for a testimony to the effect that Emmy Noether was a great

woman mathematician, L andau famously said: “I can testify that she is

a great mathematician, but that s he is a woman, I cannot swear.”

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

 ALEXANDRE V. BOROVIK

62 5 Adding One by One

Exercise 5.4 Assuming the existence of multiplication on N, prove the

existence and uniqueness of the exponentiation

N × N → N,

(n, k) 7→ n

satisfyi ng the recursive relations

= 1,

k+1

= n

· n.

Exercise 5.5 Make an inﬁnite descent proof of irrationality of

√

2 ba sed

on this diagram:

Exercise 5.6 Modify the proof of Theorem 6 to prove irrationality of

√

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

 ALEXANDRE V. BOROVIK

What is a Minus Sign Anyway?

6.1 Fuzziness of the rules

After our study of associativity of addition (Chapter 5, Theorem 1),

we can turn our attention to subtraction.

The question “What is a minus sign anyway?” was posed by

John Baldwin in a paper under this name placed on the Internet.

He asks a seemingly naive question: in school mathematics te ach-

ing, how do we justify manipulations like

(40 + 20) − (12 + 5) = (40 − 12) + (20 − 5)?

John Baldwin writes:

The associative law can only work on two applications of the plus

sign. We generalize it to say we can regroup any sequences of addi-

tions. It is quite plausible that this is a disti nction one should not

make for teachers or at least the question should be at wha t level

you want them to be aware of it. The second problem is that when

minus signs are interspersed this gets more complicated. Since as-

sociativity fails for subtraction some further rules are requi red.

Indeed , notice that

(3 − 2) − 1

is not the same as

3 − (2 − 1).

Subtraction is not associative!

This is a classical example of a “fuzziness” in mathematics

teaching, a phenom enon especially noticeable at earlier stages of

school education. Very frequently, children are placed in a position

where they have to ﬁgure out ru les which have not been made ex-

plicit. Of course, children learn the grammar of their mother tongue

exactly that way, by absorptio n. Unfortunately, by the time they are

64 6 What is a Minus Sign Anyway?

taught mathematics, the ir natural ability to extract grammar rules

from adult’s speech is already signiﬁcantly suppressed.

Striking the right balance of rigor and co mputational ﬂuency

is a hard task. Still, what struck me in John Baldwin’s paper was

his reluctance to bring this subtle distinction between the un ary

operation of negation and the binary operation of subtraction to

the attention of (American) teachers:

It is quite plausible that this is a distinction one should not make

for teachers or at leas t the question should be at what level you

want them to be aware of it.

John Baldwin comm ented further in my blog:

You are well to wonder when I question whether or maybe better

how teachers should be taught this. One of the faults of a prelim-

inary version is that certain facts understood by the writer an d

immediate audience are not spelled out. Thus we were talking in

the seminar for whom that was written about future elementary

school teachers. And the issue that I was alluding to was at what

stage you can make such students self-aware of subtle matters.

One can’t just tell them that one operation i s binary and the other

unary.

Because they have never heard either word.

One of the members of the audience had been extremely s uc-

cessful in teaching this group of students without making such for-

mal distinction but by givin g them lots of opportunity by operating

on lattices of numbers to develop the understan d ing —analogously

to, as you mentioned, children learning their n ative tongue.

In fact, I haven’t really resolved this issue in my own mind

and recently have been working with high s chool teachers where

the more explicit understanding is essential (and with some effort)

communicable.

6.2 A formal treatment of s ubtraction

My f r iend and colleague Tuna Altınel

learnt “new math” style

mathematics in a Turkish school where scien ces had been taught in

French and in accordance with French curricula

. He surprised m e

by telling me that his teachers and textbooks mad e a clear distinc-

tion between “minus” as a binary symbol for subtraction and minus

as an unary symbol for taking the opposite. Actually, the opp osite

TA is male, Turkish, has a PhD in mathematics from an American uni-

versity and teaches in a French university.

Galatasaray Lis esi, http://www.gsl.gsu.edu.tr/html_tr; a page

in English: http://www.gsl.gsu.edu.tr/html_eng/000/000.

html.

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

 ALEXANDRE V. BOROVIK