Transcription
Introduction to Mathematical ThinkingRenzo CavalieriNotes for Students of Math 235Fort Collins, Spring 2020Department of Mathematics, Colorado State University, FortCollins, CO, 80523-1874, USA. Email: renzo@math.colostate.edu
ContentsIntroductionWhere do we start?What does it mean to write a “complete” proof?555Unit1.2.3.1. Examples of proofsKey IdeasGroupworkHomework771114Unit1.2.3.2. SetsKey IdeasGroupworkHomework15151819Unit1.2.3.3. Definitions, Quantifiers, ImplicationsKey IdeasGroupworkHomework21212325Unit1.2.3.4. Bijections and InfinitiesKey IdeasGroupworkHomework29293133Unit1.2.3.5. Combinatorics and Newton’s theoremKey IdeasGroupworkHomework35353639Unit1.2.3.6. Functions: part IKey IdeasGroupworkHomework41414345Unit1.2.3.7. Functions: part 2Key IdeasGroupworkHomework47474950Unit1.2.3.8. Equivalence relations and quotient setsKey IdeasGroupworkHomework515153553
4Unit1.2.3.CONTENTS9. Quotients and OperationsKey IdeasGroupworkHomework57575961
IntroductionWhere do we start?In no human activity we ever start at the beginning. For example, if youwant to play a videogame, you don’t program it, if you want to program acomputer you don’t build it, if you want to build a computer you don’t buildthe parts, if you want to build the parts you don’t process the metals andplastic from raw materials, and if you want to process the raw materials youdon’t extract them. If you wanted to play a videogame that you built fromscratch you may end up investing your whole life into that goal, and maybestill not achieve it.Math seems different. To many of us, one of the appeals of math isthat it seems like you don’t have to take anything off the shelf. You makesome definitions, maybe choose some axioms (“rules of the game”), and thenconstruct your theory via logical steps. This has (and is still) been a centralgoal of modern mathematics, but alas, even in mathematics, we don’t startall the way at the beginning. For a very simple reason, which is that startingat the very beginning is very difficult, and one can only get there after theyhave substantially trained their skills.In this class, we will ASSUME as given the following:(1) the notion of numbers (natural, integer, rational and real), and theoperations of addition and multiplication;(2) the notion of set (roughly speaking a collection of “things” calledelements).We all “know” (or think we do) what these things are, but if you try andthink of precise definitions you will find it very hard. What happened isthat we got “used” to using these concepts instead of really understandingwhat they are. just like driving a car instead of building it. For a firstclass in mathematical thinking, I think it is best to start driving, and thenwhomever may be interested in the future may look under the hood.What does it mean to write a “complete” proof ?A proof establishes the truth of a mathematical statement. A mathematical statement consists of a bunch of hypotheses, which are the thingsthat you assume to be true, and of a statement called thesis that you wantto deduce from the hypotheses. Note that sometimes the hypothesis arehidden.For example, in the mathematical statement:For every natural number n, the sum 1 3 5 . (2n 1) n25
6INTRODUCTIONwe have written the thesis. The hypotheses are that we know what naturalnumbers are, and how addition works. Often, hypotheses that are part ofthe framework of mathematics are omitted from the statement.Proving that statement means writing a string of sentences that establishthe validity of the above formula. There are many different ways to writea complete and correct proof, and no algorithm that will efficiently work inevery case. This makes the task more difficult, but in a sense also more fun,because we are often led to looking for not just “a” proof, but a “nice” proof,where nice could mean many things: elegant, slick, efficient, or illuminating,for example.The string of sentences must take us from the hypothesis to the thesis bya sequence of logical implications. There is a big difference between writing aproof for a computer or for a human being. in this class we are not learningto write “proofs that a computer can understand”, but “proofs that a humancan understand”. and here there is some unavoidable ambiguity in whatit means to write a complete proof. the way that I would write a prooffor you is certainly different from the way I would write the same proof foranother mathematical researcher, where I can assume that they have muchmore background and I am allowed to not have to say everything. Since youare beginners, try to err on the safe side. If in doubt, give extra motivationat each step. At the same time, be careful that you are not just repeatingyourself without adding any content.Let me give a silly and not very mathematical example. Suppose youwant to provide an argument for the sentence:If it rains, then it is a good idea to have an umbrella.This is not an argument:If it rains, it rains. Which means it is raining. Then itis a good idea to have an umbrella. Because you know, itrains. So it is a good idea to have an umbrella. Because itis a good idea.A much more complete argument is the shorter:If it rains, then it is a good idea to have an umbrella, sincethat prevents you from getting wet.
UNIT 1Examples of proofs1. Key IdeasProving a mathematical statement means to give a sequence of implications that show how the thesis (what is stated to be true) follows from thehypothesis (what is assumed to be true). There are many different waysto write a proof, and trying to constrain proof writing to an algorithm willsooner or later be limiting. Also, it is often useful to “translate” a mathematical statement into an equivalent statement where we have better toolsto show its validity. Rather than continuing with a general but abstract discussion, let us illustrate this with one example. Consider the mathematicalstatement:(S): The sum of the first n odd natural numbers is equal to n2 .We can rewrite this statement symbolically as follows:1 3 5 . . . (2n 1) n2 ,(1)or if we want to be even more slick,n2 (2i 1) n .(2)i 1Before we proceed any further, let us pause for a second to becomeaware of some hidden things to which we will pay a lot of attention duringthis semester:hypotheses: In the statement above there seem to be no hypothesis,but in fact we have just hidden what we consider common knowledge: that we agree on what a natural number is, on what an oddnumber is, that we agree on how the operations of addition andmultiplication work and that the symbol n2 means n n. These arethe hidden hypotheses of this mathematical statement.quantifier: In order for statement (S) to be true, formula (2) musthold for every possible choice of a natural number n. So, ifone wanted to be absolutely complete, one should rewrite it asFor every natural number n, the sum of the first n oddnatural numbers is equal to n2 .clear pattern: In equation (1) we take advantage of the fact that weare communicating among humans and not to a computer. Writing1 3 5 establishes a pattern which is easily recognizable by justabout anyone. That is why it is acceptable to put “. . .” to indicatethat one should continue with the same pattern until the number(2n 1).7
81. EXAMPLES OF PROOFSNow let us get to work and prove statement (S). OK, hold on. beforewe actually start the proof, there is one more important thing to do. beingskeptical! We are going to test the statement for a few values of n. This isuseful for two reasons:(1) It provides a check that there was not a typo, or that you weregiven as a task to try and prove a false statement (never trust yourteachers).(2) Testing a statement often allows you to understand the statementbetter, and often suggests how to prove it.So let us test our statement for n up to 5:n 1:1 12 ,n 2:1 3 4 22 ,n 3:1 3 5 9 32 ,n 4:1 3 5 7 16 42 ,n 5:1 3 5 7 9 25 52 .Allright, it looks like I was not trying to fool you. But here is an interestingobservation that one can make by looking at the above list of checks. Ateach line, you have a summation which is equal to the previous line plus onemore term. Which in practice means that if you have already checked that1 3 5 7 16 in the fourth line, in the fifth line you could save yourselfsome energy by computing directly 16 9 as opposed to going back to doingall over 1 3 5 7 9. This idea is at the basis of a proof technique calledinduction. Let us first show the proof of statement (S) using this technique,and then make some general comments about induction.1.1. Proof by induction.We first establish the base case. Statement (S) is true for n 1: thesum of the first odd natural number is 1, which is equal to 12 .We now assume statement (S) to be true for n equal to a particular butunspecified value n N . This becomes a hypothesis (called the inductivehypothesis), which means that we can use it as a true fact, in order toestablish the validity of statement (S) for n N 1. (this is called theinductive step).Let us be very explicit: to perform the inductive step we assume that(H) 1 3 5 . . . (2N 1) N 2is true, and we show that it follows that(T ) 1 3 5 . . . (2N 1) (2N 1) (N 1)2must also be true.
1. KEY IDEAS9It is often convenient to start from what you have to show to be true.We are going to start from the left hand side of (T ), and use a sequence ofalgebraic manipluations together with the use of (H) to show that it equalsthe right hand side of (T ).Start from the left hand side of (T ). By associativity of addition wehave:1 3 5 . . . (2N 1) (2N 1) [1 3 5 . . . (2N 1)] (2N 1)In the square parentheses (and in blue if you have colors) we have the lefthand side of (H). Since we are assuming (H) to be a true statement, wecan replace the square parenthesis with the right hand side of (H):[1 3 5 . . . (2N 1)] (2N 1) N 2 (2N 1).Now by foiling we haveN 2 (2N 1) (N 1)2 ,which is the right hand side of (T ). This concludes the proof by inductionof statement (S).Induction. What just happened? How did we just prove statement(S)? There is a perfect analogy between a proof by induction and the gameof domino: you should imagine that statement (S) is in fact an infinitenumber of statements, one for each value of n (in the test above we saw thefirst 5). Imagine each of these statements is the tile of a domino game, putone after the other. A statement being true corresponds to a tile falling.When we show the inductive step, we are saying that if any one tile falls,then it knocks down the next one. Establishing the base case amounts toshowing that the first tile falls. These two together show that every tile isgonna fall, because the first knocks down the second, the second the third,and so on forever.Here is a formal description of the technique of proof by induction. Givena collection of mathematical statements S(n), indexed by natural numbersn. A proof by induction consists in establishing the following two steps:base case: show that S(1) is true.inductive step: assume that S(N ) is true for some unspecified number N , and show that it must be the case that S(N 1) is also true.By applying the inductive step for N 1, ( you have shown S(1) to be truein the base case), you obtain that S(2) is true. But now you can apply theinductive step for N 2 (which you just learned was true), to obtain thatS(3) is true, and so on and so forth.1.2. Proof by translation to a geometric problem.We now prove statement (S) by translating it to a geometric statementwhich we then show to be true.Consider a collection of beads arranged on the plane on all points (x, y)such that x, y are integers, and 1 x n, 1 y n, as illustrated in Figure1.1. Since each row contains n beads, and there are n rows, there are exactly
101. EXAMPLES OF PROOFSn2 beads in this arrangement. Now count the beads as shown by the redlines in the drawing: for every integer i, you group together the beads withcoordinates i x y and those with coordinates i y x. There are 2i 1beads in this group. Since the total number of beads in the grid is equal tothe sum of the beads in the various red groups, we have shown thatnn2 (2i 1)i 1Figure 1.1. A figure that illustrates the argument of thegeometric proof of statement (S) for n 5. Remember: afigure is not a proof, but a figure helps understanding a proofby clarifying and establishing a geometric pattern which weare using in the proof of our argument.1.3. Summing integers and counting handshakes. We define twointegers that depend on n.H(n): the number of handshakes that happen if, in a group of npersons, everyone shakes hands with everyone else exactly once.G(m): the sum of the first m natural numbers. In symbols,mG(m) i.i 1Now we state some theorems (mathematical statements whose truth we willwork to establish).Theorem 1.1. For every natural number n,H(n) G(n 1).Theorem 1.2. For every natural number n,1H(n) n (n 1).2
2. GROUPWORK11Theorem 1.3. For every natural number m,1G(m) m (m 1).2First off, let us observe that Theorem 1.2 gives a formula for H(n), Theorem 1.3 gives a formula for G(m) and Theorem 1.1 expresses a relationshipbetween H and G. Theorem 1.1 is a translation between two problems:a combinatorial problem of counting handshakes is related to an algebraicproblem of adding a sequence of natural numbers.We observe the following logical implications:(1) Theorem 1.1 Theorem 1.2 Ô Theorem 1.3;(2) Theorem 1.1 Theorem 1.3 Ô Theorem 1.2;(3) Theorem 1.2 Theorem 1.3 Ô Theorem 1.1.In other words, if any two of those three theorems are true, then thethird one is also true. Another way to think of the logical relationshipbetween these three statements is that if one of them is true, then theremaining two become equivalent. We will revisit this fact and use i
Introduction to Mathematical Thinking Renzo Cavalieri NotesforStudentsof Math 235 FortCollins,Spring2020 Department of Mathematics, Colorado State University, Fort Collins, CO, 80523-1874, USA. Email: renzo@math.colostate.edu. Contents Introduction 5 Wheredowestart? 5 Whatdoesitmeantowritea“complete” proof? 5 Unit1. Examplesofproofs 7 1. KeyIdeas 7 2. Groupwork
