WIXLIB

8CONTENTS.4474554564574667 Functions and Cardinality7.1 Introduction . . . . . . . . . . . . . . . . . .7.1.1 Objectives . . . . . . . . . . . . . . .7.1.2 Segue from previous chapter . . . . .7.1.3 Motivation . . . . . . . . . . . . . .7.1.4 Goals and Warnings for the Reader .7.2 Definition and Examples . . . . . . . . . . .7.2.1 Definition . . . . . . . . . . . . . . .7.2.2 Examples . . . . . . . . . . . . . . .7.2.3 Equality of Functions . . . . . . . .7.2.4 Schematics . . . . . . . . . . . . . .7.2.5 Questions & Exercises . . . . . . . .7.3 Images and Pre-images . . . . . . . . . . . .7.3.1 Image: Definition and Examples . .7.3.2 Proofs about Images . . . . . . . . .7.3.3 Pre-Image: Definition and Examples7.3.4 Proofs about Pre-Images . . . . . . .7.3.5 Questions & Exercises . . . . . . . .7.4 Properties of Functions . . . . . . . . . . .7.4.1 Surjective (Onto) Functions . . . . .7.4.2 Injective (1-to-1) Functions . . . . .7.4.3 Proof Techniques for Jections . . . .7.4.4 Bijections . . . . . . . . . . . . . . .7.4.5 Questions & Exercises . . . . . . . .7.5 Compositions and Inverses . . . . . . . . . .7.5.1 Composition of Functions . . . . . .7.5.2 Inverses . . . . . . . . . . . . . . . .7.5.3 Bijective Invertible . . . . . . .7.5.4 Questions & Exercises . . . . . . . .7.6 Cardinality . . . . . . . . . . . . . . . . . .7.6.1 Motivation and Definition . . . . . .7.6.2 Finite Sets . . . . . . . . . . . . . .7.6.3 Countably Infinite Sets . . . . . . .7.6.4 Uncountable Sets . . . . . . . . . . .7.6.5 Questions & Exercises . . . . . . . .7.7 Summary . . . . . . . . . . . . . . . . . . .7.8 Chapter Exercises . . . . . . . . . . . . . .7.9 Lookahead . . . . . . . . . . . . . . . . . . 5495555575585666.66.76.86.5.4 Some Helpful Theorems6.5.5 Questions & Exercises .Summary . . . . . . . . . . . .Chapter Exercises . . . . . . .Lookahead . . . . . . . . . . . .

9CONTENTS8 Combinatorics8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . .8.1.1 Objectives . . . . . . . . . . . . . . . . . . . .8.1.2 Segue from previous chapter . . . . . . . . . .8.1.3 Motivation . . . . . . . . . . . . . . . . . . .8.1.4 Goals and Warnings for the Reader . . . . . .8.2 Basic Counting Principles . . . . . . . . . . . . . . .8.2.1 The Rule of Sum . . . . . . . . . . . . . . . .8.2.2 The Rule of Product . . . . . . . . . . . . . .8.2.3 Fundamental Counting Objects and Formulas8.2.4 Questions & Exercises . . . . . . . . . . . . .8.3 Counting Arguments . . . . . . . . . . . . . . . . . .8.3.1 Poker Hands . . . . . . . . . . . . . . . . . .8.3.2 Other Card-Counting Examples . . . . . . . .8.3.3 Other Counting Objects . . . . . . . . . . . .8.3.4 Questions & Exercises . . . . . . . . . . . . .8.4 Counting in Two Ways . . . . . . . . . . . . . . . . .8.4.1 Method Summary . . . . . . . . . . . . . . .8.4.2 Examples . . . . . . . . . . . . . . . . . . . .8.4.3 Standard Counting Objects . . . . . . . . . .8.4.4 Binomial Theorem . . . . . . . . . . . . . . .8.4.5 Questions & Exercises . . . . . . . . . . . . .8.5 Selections with Repetition . . . . . . . . . . . . . . .8.5.1 Motivation . . . . . . . . . . . . . . . . . . .8.5.2 Formula . . . . . . . . . . . . . . . . . . . . .8.5.3 Equivalent Forms . . . . . . . . . . . . . . . .8.5.4 Examples . . . . . . . . . . . . . . . . . . . .8.5.5 Questions & Exercises . . . . . . . . . . . . .8.6 Pigeonhole Principle . . . . . . . . . . . . . . . . . .8.6.1 Motivation . . . . . . . . . . . . . . . . . . .8.6.2 Statement and Proof . . . . . . . . . . . . . .8.6.3 Examples . . . . . . . . . . . . . . . . . . . .8.6.4 Questions & Exercises . . . . . . . . . . . . .8.7 Inclusion/Exclusion . . . . . . . . . . . . . . . . . . .8.7.1 Motivation . . . . . . . . . . . . . . . . . . .8.7.2 Statement and Proof . . . . . . . . . . . . . .8.7.3 Examples . . . . . . . . . . . . . . . . . . . .8.7.4 Questions & Exercises . . . . . . . . . . . . .8.8 Summary . . . . . . . . . . . . . . . . . . . . . . . .8.9 Chapter Exercises . . . . . . . . . . . . . . . . . . .8.10 Lookahead . . . . . . . . . . . . . . . . . . . . . . . 657657658659662662663669

10A Definitions and TheoremsA.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . .A.1.1 Standard Sets . . . . . . . . . . . . . . . . . .A.1.2 Set-Builder Notation . . . . . . . . . . . . . .A.1.3 Elements and Subsets . . . . . . . . . . . . .A.1.4 Power Set . . . . . . . . . . . . . . . . . . . .A.1.5 Set Equality . . . . . . . . . . . . . . . . . . .A.1.6 Set Operations . . . . . . . . . . . . . . . . .A.1.7 Indexed Set Operations . . . . . . . . . . . .A.1.8 Partition . . . . . . . . . . . . . . . . . . . .A.2 Logic . . . . . . . . . . . . . . . . . . . . . . . . . . .A.2.1 Statements and Propositions . . . . . . . . .A.2.2 Quantifiers . . . . . . . . . . . . . . . . . . .A.2.3 Connectives . . . . . . . . . . . . . . . . . . .A.2.4 Logical Negation . . . . . . . . . . . . . . . .A.2.5 Proof Strategies . . . . . . . . . . . . . . . .A.3 Induction . . . . . . . . . . . . . . . . . . . . . . . .A.3.1 Principle of Specific Mathematical InductionA.3.2 Principle of Strong Mathematical Induction .A.3.3 “Minimal Criminal” Argument . . . . . . . .A.4 Relations . . . . . . . . . . . . . . . . . . . . . . . .A.4.1 Properties of Relations . . . . . . . . . . . . .A.4.2 Equivalence Relations . . . . . . . . . . . . .A.4.3 Modular Arithmetic . . . . . . . . . . . . . .A.5 Functions . . . . . . . . . . . . . . . . . . . . . . . .A.5.1 Images and Pre-Images . . . . . . . . . . . .A.5.2 Jections . . . . . . . . . . . . . . . . . . . . .A.5.3 Composition of Functions . . . . . . . . . . .A.5.4 Inverses . . . . . . . . . . . . . . . . . . . . .A.5.5 Proof Techniques for Functions . . . . . . . .A.6 Cardinality . . . . . . . . . . . . . . . . . . . . . . .A.6.1 Definitions . . . . . . . . . . . . . . . . . . .A.6.2 Results . . . . . . . . . . . . . . . . . . . . .A.6.3 Standard Catalog of Cardinalities . . . . . . .A.7 Combinatorics . . . . . . . . . . . . . . . . . . . . .A.7.1 Definitions . . . . . . . . . . . . . . . . . . .A.7.2 Counting Principles . . . . . . . . . . . . . .A.7.3 Formulas . . . . . . . . . . . . . . . . . . . .A.7.4 Standard Counting Objects . . . . . . . . . .A.7.5 Counting In Two Ways . . . . . . . . . . . .A.7.6 Results . . . . . . . . . . . . . . . . . . . . .A.7.7 Inclusion/Exclusion . . . . . . . . . . . . . .A.7.8 Pigeonhole Principle . . . . . . . . . . . . . .A.8 Acronyms . . . . . . . . . . . . . . . . . . . . . . . .A.8.1 General Phrases . . . . . . . . . . . . . . . .A.8.2 Induction . . . . . . . . . . . . . . . . . . . 692692692694695695695695696696696697697698698698

Part ILearning to ThinkMathematically11

Chapter 1What Is Mathematics?1.1Truths and ProofsHow do you know whether something is true or not? Surely, you’ve been toldthat the angles of a triangle add to 180 , for example, but how do you know forsure? What if you met an alien who had never studied basic geometry? Howcould you convince him/her/it that this fact is true? In a way, this is whatmathematics is all about: devising new statements, deciding somehow whetherthey are true or false, and explaining these findings to other people (or aliens,as the case may be). Unfortunately, it seems like many people think mathematicians spend their days multiplying large numbers together; in actuality,though, mathematics is a far more creative and writing-based discipline thanits widely-perceived role as ever-more-complicated arithmetic. One aim of thisbook is to convince you of this fact, but that’s merely a bonus. This book’smain goals are to show you what mathematical thinking, problem-solving, andproof-writing are really all about, to show you how to do those things, and toshow you how much fun they really are!As a side note, you might even wonder “What does it mean for somethingto be true?” A full discussion of this question would delve into philosophy,psychology, and maybe linguistics, and we don’t really want to get into that.The main idea in the context of mathematics, though, is that something istrue only if we can show it to be true always. We know 1 1 2always and forever. It doesn’t matter if it’s midnight or noon, we can restassured that equation will hold true. (Have you ever thought about how to showsuch a fact, though? It’s actually quite difficult! A book called the PrincipiaMathematica does this from “first principles” and it takes the authors many,many pages to even get to 1 1 2!) This is quite different from, perhaps,other sciences. If we conduct a physical experiment 10 times and the same resultoccurs, do we know that this will always happen? What if we do the experimenta million times? A billion? At what point have we actually proven anything? Inmathematics, repeated experimentation is not a viable proof! We would need to13

14CHAPTER 1. WHAT IS MATHEMATICS?find an argument that shows why such a phenomenon would always occur. Asan example, there is a famous open problem in mathematics called the GoldbachConjecture. It is unknown, as of now, whether it is true or not, even thoughit has been verified by computer simulations up until a value of roughly 1018 .That’s a huge number, but it is still not enough to know whether the conjectureis True or False. Do you see the difference? We mathematicians like to provefacts, and checking a bunch of values but not all of them does not constitute aproof.1.1.1Triangle TangleWe’ve introduced the idea of a proof by talking about what we hope proofs toaccomplish, and why we would care so much about them. You might wonder,then, how one can define a proof. This is actually a difficult idea to address!To approach this idea, we are going to present several different mathematicalarguments. We want you to read along with them, and think about whetherthey are convincing. Do they prove something? Are they correct? Are theyunderstandable? How do they make you feel? Think about them on your ownand develop some opinions, and then read along with our discussion.The mathematical arguments we will present here are all about triangles.Specifically, they concern the Pythagorean Theorem.Theorem 1.1.1 (The Pythagorean Theorem). If a right triangle has baselengths a, b and hypotenuse length c, then these values satisfy a2 b2 c2 .How do we know this? It’s a very useful fact, one that you’ve probably usedmany times in your mathematics classes (and in life, without even realizing).

151.1. TRUTHS AND PROOFSHave you ever wondered why it’s true? How would you explain it to a skepticalfriend? This is what a mathematical proof attempts to accomplish: a clearand concise explanation of a fact. The reasoning behind requiring a proof makesa lot of sense, too, and is twofold: it’s a relief to know that what we thought wastrue is, indeed, true and it’s nice to not have to go through the explanation ofthe fact every time we’d like to use it. After proving the Pythagorean Theorem(satisfactorily), we merely need to refer to the theorem by name whenever arelevant situation arises; we’ve already done the proof, so there’s no need toprove it again.Now, what exactly constitutes a proof? How do we know that an explanationis sufficiently clear and concise? Answering this question is, in general, ratherdifficult and is part of the reason why mathematics can be viewed as an art asmuch as it is a science. We deal with cold, hard facts, yes, but being able toreason with these facts and satisfactorily explain them to others is an art formin itself.Examples of “Proofs”Let’s look at some sample “proofs” and see whether they work well enough.(We say “proof” for now until we come up with a more precise definition for it,later on.) Here’s the first one:“Proof ” 1. Draw a square with side length a b. Inside this square, draw fourcopies of the right triangle, forming a square with side length c inside the largersquare.The area of the larger square can be computed in two ways: by applying thearea formula to the larger square or by adding the area of the smaller square tothe area of the four triangles. Thus, it must be true that(a b)2 c2 4 ·ab c2 2ab2

16CHAPTER 1. WHAT IS MATHEMATICS?Expanding the expression on the left and canceling a common term on bothsides yields b2 c2 a2 2ab2abTherefore, a2 b2 c2 is true.Are you convinced? Did each step make sense? Maybe you’re not sure yet,so let’s look at another “proof” of the theorem.“Proof ” 2. Suppose the Pythagorean Theorem is true and draw the right triangle with the altitude from the vertex corresponding to the right angle. Labelthe points and lengths as in the diagram below:Since the Pythagorean Theorem is true, we can apply it to all three of theright triangles in the diagram, namely ABC, BCD, ACD. This tells us (defininge c d)a2 d2 f 2b2 f 2 e2c2 a2 b2Adding the first two equations together and replacing this sum in the thirdequation, we getc2 d2 e2 2f 2Notice that angles ABC and ACD are equal, because they are both complementary to angle CAB, so we know triangles 4CDB and 4ADC are similartriangles. (We are now assuming some familiarity with plane geometry.) Thistells us fe fd , and thus f 2 ed. We can use this to replace f 2 in the lineabove and factor, as follows:c2 d2 e2 2de (d e)2

1.1. TRUTHS AND PROOFS17Taking the square root of both sides (and knowing c, d, e are all positive numbers) tells us c d e, which is true by the definition of the lengths d and e.Therefore, our assumption that the Pythagorean Theorem is true was valid.What about this proof? Was it convincing? Was it clear? Let’s examine onemore “proof” before we decide what a constitutes a “correct” or “good” proof.“Proof ” 3. Observe thatsoac b c baand thus a2 b2 c2 .Did that make any sense to you? Finally, here’s one last “proof” to consider.“Proof ” 4. The Pythagorean Theorem must be true, otherwise my teachershave been lying to me.DiscussionBefore reading on, we encourage you to think about these four “proofs” and evendiscuss them with another student or a friend. What do you think constitutesa “correct” proof? Is clarity and ease of reading important? Does it affect the“correctness” of a proof?From a historical perspective, mathematical proof-writing has evolved overthe years and there is a good, general consensus as to what constitutes a “correct” proof: It is important that every step in the proof, every logical inference andclaim, is valid, mathematically speaking. It is also important that the proof-writer makes (reasonably) clear why astatement follows from the previous work or from outside knowledge.

18CHAPTER 1. WHAT IS MATHEMATICS?What’s nice about the truth requirement is that mathematics has been built upso that we can read through an argument and verify each claim as True or False.What’s difficult to define is clear writing. In a way, it is much like SupremeCourt Justice Potter Stewart’s famous definition of obscenity: “I know it whenI see it”.Given these four arguments for comparison, let’s assess them for clarity andcorrectness:Clarity: “Proofs” 1 and 2 are fairly well explained. There are clear statementsabout what the writer is doing and why. They indicate where any equations come from, and even include some pictures to illustrate their ideasfor the rea

Everything You Always Wanted To Know About Mathematics* (*But didn’t even know to ask) A Guided Journey Into the World of Abstract Mathematics and the Writing of Proofs Brendan W. Sullivan bwsulliv@andrew.cmu.edu with Professor John Mackey Department of Mathematical Scienc