[PDF] Proofs and Mathematical Reasoning

View - Download Proofs and Mathematical Reasoning

Previous PDF

Next PDF

Proofs and Mathematical Reasoning

University of Birmingham

Author:

AgataStefanowiczSupervisors:

JoeKyle

MichaelGrove

September 2014c

University of Birmingham 2014

Contents

1 Introduction6

2 Mathematical language and symbols 6

2.1 Mathematics is a language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2 Greek alphabet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.3 Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.4 Words in mathematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3 What is a proof?9

3.1 Writer versus reader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2 Methods of proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.3 Implications and if and only if statements . . . . . . . . . . . . . . . . . . . . . . . . . .

10

4 Direct proof11

4.1 Description of method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

4.2 Hard parts? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

4.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

4.4 Fallacious \proofs" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

4.5 Counterexamples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

5 Proof by cases17

5.1 Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

5.2 Hard parts? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

5.3 Examples of proof by cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

6 Mathematical Induction 19

6.1 Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

6.2 Versions of induction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

6.3 Hard parts? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

6.4 Examples of mathematical induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

7 Contradiction26

7.1 Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

7.2 Hard parts? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

7.3 Examples of proof by contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

8 Contrapositive29

8.1 Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

8.2 Hard parts? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

8.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

9 Tips31

9.1 What common mistakes do students make when trying to present the proofs? . . . . .

31

9.2 What are the reasons for mistakes? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

9.3 Advice to students for writing good proofs . . . . . . . . . . . . . . . . . . . . . . . . . .

32

9.4 Friendly reminder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32 c

University of Birmingham 2014

10 Sets34

10.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

10.2 Subsets and power sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

10.3 Cardinality and equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

10.4 Common sets of numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

10.5 How to describe a set? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

10.6 More on cardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

10.7 Operations on sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

10.8 Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

11 Functions41

11.1 Image and preimage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

11.2 Composition of the functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

11.3 Special functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

11.4 Injectivity, surjectivity, bijectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

11.5 Inverse function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

11.6 Even and odd functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

11.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

12 Appendix47c

University of Birmingham 2014

Foreword

Talk to any group of lecturers about how their students handle proof and reasoning when presenting mathematics and you will soon hear a long list of `improvements' they would wish for. And yet, if no one has ever explained clearly, in simple but rigorous terms, what is expected it is hardly a surprise that this is a regular comment. The project that Agata Stefanowicz worked on at the University of Birmingham over the summer of 2014 had as its aim, clarifying and codifying views of sta on these matters and then using these as the basis of an introduction to the basic methods of proof and reasoning in a single document that might help new (and indeed continuing) students to gain a deeper understanding of how we write good proofs and present clear and logical mathematics. Through a judicious selection of examples and techniques, students are presented with instructive examples and straightforward advice on how to improve the way they produce and present good mathematics. An added feature that further enhances the written text is the use of linked videos les that oer the reader the experience of `live' mathematics developed by an expert. And Chapter 9, that looks at common mistakes that are made when students present proofs, should be compulsory reading for every student of mathematics. We are condent that, regardless of ability, all students will nd something to improve their study of mathematics within the pages that follow. But this will be doubly true if they engage with the problems by trying them as they go through this guide.

Michael Grove & Joe Kyle

September 2014c

University of Birmingham 2014

Acknowledgements

I would like to say a big thank you to the Mathematics Support Centre team for the opportunity to work on an interesting project and for the help and advice from the very rst day. Special gratitude goes to Dr Joe Kyle for his detailed comments on my work and tips on creating the document. Thank you also to Michael Grove for his cheerful supervision, fruitful brainstorming conversations and many ideas on improving the document. I cannot forget to mention Dr Simon Goodwin and Dr Corneliu Homan; thank you for your time and friendly advice. The document would not be the same without help from the lecturers at the University of Birmingham who took part in my survey - thank you all. Finally, thank you to my fellow interns, Heather Collis, Allan Cunningham, Mano Sivanthara- jah and Rory Whelan for making the internship an excellent experience.c

University of Birmingham 2014

1 Introduction

From the rst day at university you will hear mention of writing Mathematics in a good style and using \proper English". You will probably start wondering what is the whole deal withwords, when you just wanted to work withnumbers.If, on top of this scary welcome talk, you get a number of denitions and theorems thrown at you in your rst week, where most of them include strange notions that you cannot completely make sense of - do not worry! It is important to notice how big dierence

there is between mathematics at school and at the university. Before the start of the course, many of

us visualise really hard dierential equations, long calculations andx-long digit numbers. Most of us will be struck seeing theorems like \a0 = 0". Now, while it isobviousto everybody, mathematicians are the ones who will not take things for granted and would like to see theproof.

This booklet is intended to give the gist of mathematics at university, present the language used and

the methods of proofs. A number of examples will be given, which should be a good resource for further

study and an extra exercise in constructing your own arguments. We will start with introducing the mathematical language and symbols before moving onto the serious matter of writing the mathematical

proofs. Each theorem is followed by the \notes", which are the thoughts on the topic, intended to give

a deeper idea of the statement. You will nd that some proofs are missing the steps and the purple

notes will hopefully guide you to complete the proof yourself. If stuck, you can watch the videos which

should explain the argument step by step. Most of the theorems presented, some easier and others more complicated, are discussed in rst year of the mathematics course. The last two chapters give the basics of sets and functions as well as present plenty of examples for the reader's practice.

2 Mathematical language and symbols

2.1 Mathematics is a language

Mathematics at school gives us good basics; in a country where mathematical language is spoken,

after GCSEs and A-Levels we would be able to introduce ourselves, buy a train ticket or order a pizza.

To have a

uent conversation, however, a lot of work still needs to be done. Mathematics at university is going to surprise you. First, you will need to learn thelanguageto be able to communicate clearly with others. This section will provide the \grammar notes", i.e. the commonly used symbols and notation, so that you can start writing your mathematical statements in a good style. And like with any other foreign language, \practice makes perfect", so take advantage of any extra exercises, which over time will make you uent in a mathematical world.

2.2 Greek alphabet

Greek alphabet - upper and lower cases and the names of the letters.

2.3 Symbols

Writing proofs is much more ecient if you get used to the simple symbols that save us writing long

sentences (very useful during fast paced lectures!). Below you will nd the basic list, with the symbols

on the left and their meaning on the right hand side, which should be a good start to exploring further

mathematics. Note that these are useful shorthands when you need to note the ideas down quickly. In general though, when writing your own proofs, your lecturers will advise you to usewordsinstead of

the fancy notation - especially at the beginning until you are totally comfortable with the statements

\if..., then...". When reading mathematical books you will notice that the word \implies" appears more often than the symbol =).c

University of Birmingham 20147

Aalpha

Bbeta gamma delta

Eepsilon

Zzeta H eta theta Iiota

Kkappa

lambda

MmuNnu

xi

O omicron

pi Prho sigma Ttau

Yupsilon

phi Xchi psi !omega

Table 1: Greek letters

Quantiers

8(universal quantier)

9(existential quantier)for all

there exists

Symbols in set theory

;(or& union intersection subset proper subset composition of functions Common symbols used when writing proofs and denitions : orj

Eororimplies

if and only if is dened as is equivalent to such that therefore contradiction end of proof

2.4 Words in mathematics

Many symbols presented above are useful tools in writing mathematical statements but nothing more than a convenient shorthand. You must always remember that a good proof should also include words. As mentioned at the beginning of the paper, \correct English" (or any other language in which you are literate) is as important as the symbols and numbers when writing mathematics. Since it is important to present proofs clearly, it is good to add the explanation of what is happening at each step using full sentences. The whole page with just numbers and symbols, without a single word, will nearly always be an example of a bad proof! Tea or coee?Mathematical language, though using mentioned earlier \correct English", diers slightly from our everyday communication. The classic example is a joke about a mathematician,c

University of Birmingham 20148

who asked whether they would like a tea or coee, answers simply \yes". This is because \or" in mathematics is inclusive, soAorBis a set of things where each of them must be either inAor inB. In another words, elements ofAorBare both those inAandthose inB. On the other hand, when considering a setAandB, then each of its elements must be both inAandB. Exercise 2.1.Question: There are 3 spoons, 4 forks and 4 knives on the table. What fraction of the utensils are forks OR knives? Answer: \Forks or knives" means that we consider both of these sets. We have 4 of each, so there are 8 together. Therefore we have that forks or knives constitute to 811
of all the utensils. If we were asked what fraction of the utensils are \forks and knives", then the answer would be 0, since no utensil is both fork and knive. Please refer to section 10, where the operations on sets are explained in detail. The notions \or" and \and" are illustrated on the Venn diagrams, which should help to understand them better.c

University of Birmingham 20149

3 What is a proof?

\The search for a mathematical proof is the search for a knowledge which is more absolute than the knowledge accu- mulated by any other discipline."

Simon Singh

A proof is a sequence of logical statements, one implying another, which gives an explanation of why a given statement is true. Previously established theorems may be used to deduce the new ones; one may also refer to axioms, which are the starting points, \rules" accepted by everyone. Mathematical proof isabsolute, which means that once a theorem is proved, it is proved for ever. Until proven though, the statement is never accepted as a true one. Writing proofs is the essence of mathematics studies. You will notice very quickly that from day one at university, lecturers will be very thorough with their explanations. Every word will bedened, notations clearly presented and each theoremproved. We learn how to construct logical arguments and

what a good proof looks like. It is not easy though and requires practice, therefore it is always tempting

for students to learn theorems and apply them, leaving proofs behind. This is a really bad habit (and

does not pay o during nal examinations!); instead, go through the proofs given in lectures and textbooks, understand them and ask for help whenever you are stuck. There are a number of methods which can be used to prove statements, some of which will be presented in the next sections. Hard and tiring at the beginning, constructing proofs gives a lot of satisfaction when the end is reached successfully.

3.1 Writer versus reader

Kevin Houston in his book[2] gives an idea to think of a proof like a small \battle" between the

reader and the writer. At the beginning of mathematics studies you will often be the reader, learning

the proofs given by your lecturers or found in textbooks. You should then take theactive attitude, which means working through the given proof with pen and paper. Reading proofs is not easy and may

get boring if you just try to read it like a novel, comfortable on your sofa with the half-concentration

level. Probably the most important part is toquestioneverything, what the writer is telling you. Treat it as the argument between yourself and the author of the proof and ask them \why?" at each step of their reasoning. When it comes to writing your own proof, the nal version should be clear and have no gaps in understanding. Here, a good idea is to think about someone else as the person who would question each of the steps you present. The argument should ow and have enough explanations, so that the reader will nd the answer to every \why?" they might ask.

3.2 Methods of proofs

There are many techniques that can be used to prove the statements. It is often not obvious at the beginning which one to use, although with a bit of practice, we may be able to give an \educated

guess" and hopefully reach the required conclusion. It is important to notice that there is no one ideal

proof - a theorem can be established using dierent techniques and none of them will be better or worse (as long as they are all valid). For example, in \Proofs from the book", we may ndsixdierent proofs of the innity of primes (one of which is presented in section 7). Go ahead and master the techniques - you might discover the passion for pure mathematics!c

University of Birmingham 201410

We can divide the techniques presented in this document into two groups; direct proofs and indirect proofs. Direct proof assumes a given hypothesis, or any other known statement, and then logically deduces a conclusion. Indirect proof, also called proof by contradiction, assumes the hypothesis (if given) together with a negation of a conclusion to reach the contradictory statement. It is often equivalent to proof by contrapositive, though it is subtly dierent (see the examples). Both direct and indirect proofs may

also include additional tools to reach the required conclusions, namely proof by cases or mathematical

induction.

3.3 Implications and if and only if statements

\If our hypothesis is about anything and everything and not about one or more particular things, then our deductions constitute mathematics. Thus mathematics may be dened as the subject in which we never know what we are talking about, nor whether what we are saying is true".

Bertrand Russell

The formulaA=)Bmeans \AimpliesB" or \ifAthenB", whereAandBare two statements. SayingA=)Bindicates that wheneverAis accepted, then we also must acceptB. The important point is that thedirection of the implication should not be mixed! WhenA=)B, then the argument goesfromAtoB, so ifAholds, thenBdoes too (we cannot haveAwithoutB). On the other hand, when we have thatBis accepted, then it doesnothave to happen thatAis also accepted (so we can haveBwithoutA). This can be illustrated by the following example: it is raining =)it is cloudy:

Now, if the rst statement is true (so it is raining), then we automatically accept that it is also cloudy.

However, it does not work the other way round; the fact that it is cloudy doesnotimply the rain. Notice further, thataccepteddoes not meantrue! We have that if it is raining, then it is cloudy and we accept both statements, but we do not know whether they are actuallytrue(we might have a nice sunny day!). Also, genuineness of the second statement does not give any information whether the rst statement is true or not. It may happen that the false statement will lead to the truth via a number of implications! \If and only if", often abbreviated \i", is expressed mathematicallyA()Band means that ifA holds, thenBalso holdsand vice versa.To prove the theorems of such form, we must show the implications in both directions, so the proof splits into two parts - showing that \A)B" and that \B)A". The proof of the statement it is raining,it is cloudy; requires from us showing that whenever it is raining, then it is cloudyandshowing that whenever it is cloudy, it is always raining.

Necessary and sucient.

A)Bmeans thatAissucientforB;

A(Bmeans thatAisnecessaryforB;

A,Bmeans thatAisbothnecessary and sucient forB:c

University of Birmingham 201411

4 Direct proof

4.1 Description of method

Direct proof is probably the easiest approach to establish the theorems, as it does not require

knowledge of any special techniques. The argument is constructed using a series of simple statements,

where each one should follow directly from the previous one. It is important not to miss out any steps

as this may lead to a gap in reasoning. To prove the hypothesis, one may use axioms, as well as the previously established statements of dierent theorems. Propositions of the form A=)B are shown to be valid bystarting atAby writing down what the hypothesis means and consequently approachingBusing correct implications.

4.2 Hard parts?

it is tempting to skip simple steps, but in mathematics nothing is \obvious" - all steps of reasoning

must be included; not enough explanations; \I know what I mean" is no good - the reader must know what you mean to be able to follow your argument; it is hard to nd a starting point to the proof of theorems, which seem \obvious" - we often forget about the axioms.

4.3 Examples

Below you will nd the theorems from various areas of mathematics. Some of them will be new and techniques used not previously seen by the reader. To help with an understanding, the proofs are preceded by the \rough notes" which should give a little introduction to the reasoning and show the thought process.Theorem 4.1.Letnandmbe integers. Then i. if nandmare both even, thenn+mis even, ii. if nandmare both odd, thenn+mis even, iii. if one of nandmis even and the other is odd, thenn+mis odd. Rough notes.This is a warm-up theorem to make us comfortable with writing mathe- matical arguments. Start with the hypothesis, which tells you that bothnandmare even integers (for parti.). Use your knowledge about the even and odd numbers, writing them in forms2kor2k+ 1for some integerk. Proof.i.If nandmare even, then there exist integerskandjsuch thatn= 2kandm= 2j. Then n+m= 2k+ 2j= 2(k+j):

And sincek;j2Z;(k+j)2Z.)n+mis even.

ii. and iii. are left for a reader as an exercise. c

University of Birmingham 201412

Theorem 4.2.Letn2N;n >1:Suppose thatnis not prime=)2n1is not a prime. Rough notes.Notice that this statement gives us a starting point; we know what it means to be a prime, so it is reasonable to begin by writingnas a product of two natural numbersn=ab. To nd the next step, we have to \play" with the numbers so we receive the expression of the required form. We are looking at2ab1and we want to factorise this. We know the identity t m1 = (t1)(1 +t+t2++tm1):

Apply this identity witht= 2bandm=ato obtain

2 ab1 = (2b1)(1 + 2b+ 22b++ 2(a1)b): Always keep in mind where you are trying to get to - it is a useful advice here! Proof.Sincenisnota prime,9a;b2Nsuch thatn=ab;1< a;b < n. Letx= 2b1 and y= 1 + 2b+ 22b++ 2(a1)b. Then xy= (2b1)(1 + 2b+ 22b++ 2(a1)b)(substituting forxandy) = 2 b+ 22b+ 23b++ 2ab

12b22b23b 2(a1)b(multiplying out the brackets)

= 2 ab1(taking away the similar items) = 2 n1:(asn=ab) Now notice that since 1< b < n, we have that 1<2b1<2n1, so 1< x <2n1:Therefore,

xis a positive factor, hence 2n1 isnotprime number.Note: It isnottrue that:n2N, ifnis prime =)2n1 is prime; see the counterexample of this

statement in section 4.5.Proposition 4.3.Letx;y;z2Z:Ifx+y=x+z, theny=z: Rough notes.The proof of this proposition is an example of anaxiomatic proof, i.e. the proof that refers explicitly to the axioms. To prove the statements of the simplest form like the one above, we need to nd a starting point. Referring to axioms is often a good idea.

Proof.

x+y=x+z =)(x) + (x+y) = (x) + (x+z)(by the existence of additive inverse) =)((x) +x) +y= ((x) +x) +z(by the associativity of addition) =)(x+ (x)) +y= (x+ (x)) +z(by the commutativity of addition) =)0 +y= 0 +z(by existence of additive inverse) =)y=z:c

University of Birmingham 201413

Proposition 4.4.8x2Z;0x=x0 = 0

Rough notes.Striking theorem seen in the second year lecture! We all know it since ourquotesdbs_dbs47.pdfusesText_47

[PDF] maths exercice 1ère S

[PDF] maths exercice 1ère s , tableau de variations de fonctions

[PDF] MATHS Exercice 2nde

[PDF] MATHS EXERCICE 3EME

[PDF] maths exercice d'équation

[PDF] Maths exercice Devoir Maison

[PDF] Maths exercice droite graduée

[PDF] Maths exercice eee

[PDF] Maths exercice éoliennes

[PDF] Maths exercice équation de droites

[PDF] Maths Exercice factorisation

[PDF] Maths exercice fonction polynôme

[PDF] maths exercice maths phare

[PDF] Maths exercice seconde

[PDF] maths exercice sur moyenne et ecart types