### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Fund Concpts Of Math MATH 300

UMass

GPA 3.55

### View Full Document

## 13

## 0

## Popular in Course

## Popular in Mathematics (M)

This 72 page Class Notes was uploaded by Reuben Hudson DDS on Friday October 30, 2015. The Class Notes belongs to MATH 300 at University of Massachusetts taught by Farshid Hajir in Fall. Since its upload, it has received 13 views. For similar materials see /class/232221/math-300-university-of-massachusetts in Mathematics (M) at University of Massachusetts.

## Reviews for Fund Concpts Of Math

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/30/15

UMASS AMHERST MATH 300 NOTES FOR FALL 05 FARSHID HAJIR CONTENTS Part 1 Problem Solving Inductive vs Deductive Reasoning An introduction to Proofs 1 Introductory Notes 11 Propositions 12 Deductive Reasoning 13 Inductive Reasoning Part 2 Logic and Sets 2 Elementary Logic 3 Sets Part 3 Sets and Maps 4 Partitions of Sets 5 Maps between sets 6 Composites and inverses of maps Part 4 Counting Principles and Finite Sets 7 Three Counting Principles 71 The Well Ordering Principle 72 The Pigeon Hole Principle 73 The multiplication counting principle 8 Finite sets Part 5 Equivalence Relations and Partitions 9 Relations 10 The set of rational numbers Part 6 Induction 11 Remembrances of Things Past 12 Mathematical Induction Part 7 Number Theory 13 A little number theory 14 Some more number theory Part 8 Counting and Uncountability 15 The classi cation of sets according to size 1 CHAgtOOOOOO I 16 16 17 19 22 22 22 23 24 28 33 34 34 38 46 49 49 2 FARSHID HAJIR Part 9 Complex Numbers 60 16 In the beginning 60 17 A constructive existence theorem 64 18 The geometry of C 67 Dear Reader Hi I am the slightly edited and rearranged notes Farshid typed up for his students in Math 300 Introduction to Fundamental Concepts of Mathematics starting with the Spring term of 2005 Since you7ve read this far it appears you7re taking Math 300 this semester so you might be spending a fair bit of time with me Allow me therefore to tell you a bit about myself I am rough as in unpolished there are typos sprinkled throughout and even errors some of them are actually intentional see the note at the end of Part 1 not to mention uncon ventional words and even made up words like Shazzam and anyhoo I am also uneven at times you7ll nd I7m quite conversational and quirky there are little one act plays in most chapters and at other times quite formal and stodgy like a regular mathematics book for 2 300 level classes I am after all supposed to help prepare you for the rather formal structures you will be studying as you continue your mathematically oriented learning ex periences I7m also a bit wordy and long winded explaining the same thing over and over again in only slightly different formulations saying it this way then that way putting it in di ferent words nding aIternate expressions for it in short repeating myself repeating myself I guarantee Farshid will admonish you to be cogent correct and concise But just between us nding it rather dif cult to be the latter himself he likes to pretend that repetition is a key hallmark of any educational process Having just listed some of my obvious faults allow me a certain measure of complacecy in hoping that you will nd these faults to be counterbalanced by my being a little less boring than other texts that cover the same material such as the textbook used for Math 300 this term Gilbert and Vanstone7s Not to say that the latter text is boring its quite good apparently but I7m willing to bet it doesnt have any one act pIays starring actual students from the class Nor will you nd Mr Noodle mentioned anywhere within its pages and key ideas in the proof will not be highlighted by SHAZZAM As it is I think Farshid will be making you pay through the nose to buy the book because he thinks its valuable to have a real published well organized example laden textbook alongside yours truly that explains the same material in a different way The contrasts as well as the similarities he says will enhance the students7 ability to learn You be the judge I think you can guess where I stand on this issue As the semester progresses I suspect Farshid will attempt to polish me up and make cross references add examples diagrams all that jazzy stuff which is alright I suppose but I sure hope he doesnt try to change my informal character I dont want to be prim and proper and pompous like most mathematics texts That would be a pity Although I have to admit grudgingly that I wouldnt mind having a real cover one day Anyhoo dont bother printing out all my gazillion pages yet as I7m bound to undergo quite a few changes MATH 300 NOTES FALL 05 3 Maybe every week you can print out the part that you happen to be studying then Also watch Farshid7s web site for update notes Well I hope you enjoy Math 300 If you have suggestions for improving me send them to Farshid unfortunately the tyrant auteur has complete nal cut on my contents Your humble servant and guide Math 300 Notes September 8th 2005 Edition Part 1 Problem Solving Inductive vs Deductive Reasoning An introduction to Proofs 1 INTRODUCTORY NOTES 11 Propositions Much of mathematics is about solving problems The process of doing mathematics is however far more complex than simply solving problems For one thing you have to create the problems in the rst place One of the things I would like to show you in this course is how mathematician create ma 1 objects and tools in order to solve speci c problems In the process of doing so the objects and tools created bring forth new questions and new problems from which new objects and tools blossom But for now to whet your appetite in this rst week of class let us start with the more familiar territory of problems Do keep in mind that there will be plenty of theory building coming later Think of the problems below as puzzles for that is what they are Have fun with them Examine their different components and how they t together make observations jot down notes locate and investigate patterns try easier versions of the problem relate the given problem to others you may have worked on act the problem out see the problem as a movie in your head draw doodle sketch pictures make graphs and tables and charts You will probably nd it helpful to keep in mind the 4 steps George Polya advocates in approaching a problem i Read and Understand the Problem ii Dream up a plan to solve the problem iii Carry out the plan iv Look back returning to i if necessary In some of the problems below and throughout the semester heck throughout your life you will be asked to provide a proof of some Proposition Let us de ne how we will use these terms A Proposition is a common name for a mathematical statement in which all concepts that appear have been given a valid de nition A Proposition may be true or false A Proof of a Proposition is an argument which establishes the truth of the Proposition Here is an alternative description a proof of P is a convincing argument which removes any doubt concerning the truth of P If a Proposition is true we say that it holds If a Proposition is false we say that it does not hold Here are some examples of Propositions P1 The sum of two even integers is even 4 FARSHID HAJIR What is meant here is shorthand for the following more precise version Let us de ne our terms rst the integers are the elements of the familiar set Z 7372710123 on which we are given the usual operations of addition and multiplication An integer a is even if there exists an integer m such that a 2m Now here nally is the meaning of our statement If a is an arbitrary even integer and b is an arbitrary even integer then a b is an even integer ls P1 true Can you construct a proof of P1 for yourself P2 Every triangle is isosceles Although this is a very good example of a patently false proposition assuming the notion of distance between two points is the usual one there is a very important class of distance measurements called p adic distance where p is a prime for which the statement is true If you campaign long and hard say one second then I will be glad to tell you more about p adic metrics P3 If a and b are integers and b 31 0 then there exists exactly one ordered pair of integers qr such that a bq r and 0 S r S lbl 7 1 See if you can gure out what commonly grasped mathematical process can convince you of the truth of this abstract sounding statementl P4 Every dog will have his day The status of the statement P4 as a Proposition is dubious unless we give precise def initions to all the terms involved In any case the establishment of such a Proposition is outside the scope of mathematics 12 Deductive Reasoning Suppose you somehow establish the following facts 0 A Every cat named Tom is grey o B Garret has a cat named Tom I am reasonably certain you have already established in your mind a third fact that follows from these two namely that Garret has a grey cat We say that the general statement A and the particular statement B together imply o G Garret has a grey cat This an example of Deductive Reasoning That is to say if you believe Statement A and if you believe Statement B then you must necessarily believe Statement G Note that whether or not you actually believe Statement A or Statement B is irrelevant to this discussion The key idea being illustrated here is the validity of implication arrow A B i 0 not the validity of either A or B or G on its own What we are establishing is that you cannot logically believe statements A and B to be true without also believing G to be true The notation P i Q is read P implies Q or Q follows logically from P or If P then Q meaning If P holds then Q holds or Q is an implication of P Okay that7s enough In Mathematics we begin with am39oms statements which we accept as true We also give precise de nitions for a variety of mathematical objects which through much experience we have decided recur often and deserve a name of their own and worthy of study Our job is then to seek out true statements which follow logically from ie are implied by the axioms and the de nitions we have given How to choose these axioms and de nitions is dictated in a natural way by the historical evolution of mathematics itself And whether a given true statement about these objects is interesting or useful is also historically judged You can be sure that the objects axioms concepts and theorems you encounter as a student of mathematics have paid their dues through hundreds and thousands of years of selective pressure if they are still around it means they are interesting and important MATH 300 NOTES FALL 05 5 Let me repeat Our jobs as mathematicians is to seek out interesting statements which follow logically from ie are implied by the axioms and the de nitions we have given The statements that we establish to be logical consequences of the axioms are usually called Propositions the more important ones get dubbed Theorems When a Theorem has interesting consequences which follow without much dif culty from the theorem we call the resulting propositions a Corollary of the theorem When we need an intermediary or auxiliary result on the way toward proving a Proposition we call that a Lemma Certain Lemmas become so indispensable they become the mathematical equivalent of a screwdriver the tool not the drink where is your mind Its great to prove a theorem that becomes famous and gets your name attached to it but many mathematicians secretly pine for having a Lemma of theirs that becomes famous You can decide for yourself would you rather be known as the inventor of the screwdriver the tool not the drink or the inventor of the HydroMagneticDestabiliZingMultiChannelTransmogri er On an even more basic level when we are plodding along trying to solve a problem having to do with one set of objects over many years and much trial and error a collection of properties and ideas may coallesce together and inspire us to de ne a new mathematical object Sometimes these objects then are so fascinating on their own that they become the thing many people want to study How satisfying do you think that might be 13 Inductive Reasoning Before I say anything about lnductive Reasoning itself let me say that later in the course we will discuss a very important Deductive Reasoning Tool known as Mathematical Induction and that Mathematical Induction and lnductive Reasoning are NOT to be confused with each other lnductive Reasoning produces a statement that may or may or not be true Mathematical lnduction is a useful method for proving certain kinds of statements The term inductive reasoning refers to generalization based on observed patterns It represents an educated guess It is used in all the sciences as well as in everyday life Here are some examples 1 12 is a perfect square 1 3 4 22 is a square 1 3 5 32 is a square 1 3 5 7 42 is a square 1 3 5 7 9 52 is a perfect squarel Wow here comes the observation when we take a small bunch of odd numbers in order starting with 1 and add them up we get a perfect square Dude maybe here comes the generalization no matter how many odd numbers you take starting with 1 and going in order and add them up you always get a perfect squarel This is inductive reasoning The next step in the inductive reasoning process is to test a few more cases to see if the pattern continues to hold 1 3 5 7 9 11 is just 1 3 5 7 9 11 ie the previous number plus 11 ie 25 11 36 If we add the next odd prime we get 36 13 49 which is the next squarel If we add 49 15 64 its the next square Dude this seems like no accident There has got to be a reason behind this If you feel that way too you are thinking like a mathematician already Later in the course we will discuss how Mathematical lnduction can be used to prove the following more precise version of our observation Proposition For any integer n 2 1 the sum of the rst n odd numbers is n2 NOTE ON HOMEWORK PROBLEMS AND BEING ON YOUR TOES lN CLASS There number of problems given will be typically smaller than you expect from a mathematics class but the problems will have several parts or will require quite a bit of thinking So get started on the homework right away because it will take you a long time to come up 6 FARSHID HAJIR with the solutions and write them up carefully One of the goals of this course is to help you express your arguments cogently concisely and correctly the three c075 This is much harder than it sounds A certain number of points for the assignment go toward each of the c075 Expect to suck at the three co7s for a while but if you keep working at it and study the style of the arguments you encounter throughout this course you will improve steadily By the way as I am lecturing feel free to rate my proofs on the three co7s You might have already guessed that I suck at concisely7 Let me be totally up front about this sometimes in class I will present proofs that suck on purpose even in correctness Your job is to catch those instances Why do I do this Sometimes it helps to see someone else fall into a ditch in order to learn how to avoid one yourself MATH 300 NOTES FALL 05 7 Part 2 Logic and Sets 2 ELEMENTARY LOGIC ln mathematics we are concerned with statements which are either True T or False This is called the truth value or validity of the statement If a statement is true we say it holds if false we say that it does not hold Most the time the statements we encounter will depend on speci c values taken by variables contained within them For example the statement 51 z 1 3 may be true or false depending on the situation The same goes for 2 z 7 1 1 The same goes for Sg y 18 But whereas for 1 and 3 there are four possible truth value combinations namely 5153 is T T or T F or F T or F F since we have been given no relationship between z and y it is easy to see that 51 can be derived from 2 and vice versa In other words the only truth value combinations for 8152 are T T and F If you want you can imagine that there is some kind of logical glue binding 51 and 2 together Determining whether two given statements are held together by a logical glue or not is in some sense a large part of doing mathematics The basic relationship that can exist between two statements is that of implication mean ing if the validity of one statement P always guarantees the validity of another one Q then we write P i Q to be read P implies Q or Q follows from P In P i Q we call P the premise or hypothesis and Q is the conclusion Let us review this if P and Q are statements then we can make a new statement R P i Q out of them The individual validity of P or Q by itself does not affect the validity of R P i Q Rather for R to be true all one needs is that WHENEVER P HAPPENS TO BE TRUE Q HAPPENS TO BE TRUE ALSO So R is false only we can establish some instance of P being TRUE and simultaneously Q being FALSE In other words P i Q is TRUE if and only if P is true and Q is false is impossible Let us introduce some more notation Here are some more ways to create new statements from given ones First there is the negation 7P of a statement P This is a statement which is TRUE whenever P is FALSE and is FALSE whenever P is TRUE In other words the negation of P has the opposite truth value of P Note that 77P P If PQ are statements then P Q read P AND Q is true if and only if BOTH P and Q are true On the other hand PV Q read P OR Q is true if at least one of the two statements PQ is true Note the symmetries P Q Q P and P V Q Q V P We have already seen that given P and Q we can creat the statement P i Q The converse of P i Q is Q i P A statement which always has truth value T is called a tautology and one which always has truth value F is called a contradiction The contrapositive of P i Q is 7Q i P Two statements are called equivalent if the truth value of one is always equal to the truth value of the other They have coinciding truth tables ConsiderPx2andQx2 4 WehaveiPx7 2and7Qz2gt4 The implication P i Q is true but its converse Q i P is false because there are many values of z other than 2 such that x2 S 4 such as x 72 The implication 7Q i 7P however ie the contrapositive of P i Q is true for if x2 gt 4 then gt 2 so z 31 2 Let us show that the contrapositive of P i Q is always equivalent to it Well P i Q is true if and only if P 7Q is a contradiction On the other hand 7Q i 7P is true if and only if 7Q 77P is a contradiction But clearly 7Q 77P P 7Q so we are done In the homework you will recheck the equivalence of an implication and its contrapositive by examining their truth tables and showing that they coincide 8 FARSHID HAJIR Since we know that an implication and its contrapositive are equivalent sometimes instead of proving a statement directly we can prove its contrapositive instead and be done more quickly Here is an example PROBLEM Prove that if n is an integer and n2 is odd then 71 is odd SOLUTION We will prove the contrapositive which will suf ce for establising the theo rem The contrapositive is If n is an integer and n is not odd then 712 is not odd Recall that an integer not being odd means it is even so we must prove If n is an even integer then 712 is an even integer This is easy If n is an even integer then 71 2m for some m E Z by de nition Then 712 47712 22m2 so 712 is even This completes the proof 3 SETS At some early point in your childhood you learned about binary phenomena Binary phenomena are those that involve two possible outcomes77 or states7 YesiNo OniO 071 Have you ever seen a child delight in repeatedly switching lights on and off in a room Anyway even if not chances are good you were such a child at some point The source of this delight is the control they exert on the state of this binary phenomenon I think it is also one of the reasons why very young children like Books of Opposites A very important concept in mathematics is that of a set and at the heart of the concept of set is a binary phenomenon namely that of belongsidoes not belong77 This deserves some explanation What is a set Basically a set is a collection of objects What a set does is to divide the world into two parts the part that belongs to the set and the part that doesn7t If you introduce any object to the set it will admit that object to be a member of the set or not to be a member of the set according to some de nite immovable solid criterion The binary phenomenon at the heart of the de nition of a set is belong 7 not belong To be a little more precise De nition 31 A set X is a well de ned rule for determining whether any given object belongs or does not belong to X Those objects that belong to X are called elements of X or the members of X Here well de ned means that the rule for belonging is very precisely described that no ambiguity enters into checking whether an object belongs or does not belong to X it does not depend for instance on who the person checking the condition is or at what time of day the checking takes place Below I will give some examples of poorly de ned77 rules of belonging to give you a better idea of well de ned means One simple way of describing the rule which distinguishes between the objects that belong to the set or not is simply to give a list of the elements of the set To list the elements we put them inside curly brackets and separate them by commas For instance here are some sets de ned in this way X abcY 72 24 0 74 Z Aaron Anna Laura Garret These sets are all nite meaning they have a nite number of elements We will talk much more about sizes of sets in a moment Let us see if we can give some alternative ways of de ning the sets we de ned above Farshz39d Can you describe the set X verbally without listing its elements explicitly MATH 300 NOTES FALL 05 9 Jaclyn I got one X is the set consisting of the rst three letters of the alphabet Emily That7s pretty good7 but I have a minor objection I dont think this is precise enough yet When you say rst three somebody might list the letters of the alphabet in some other crazy way say backwards and then for them the rst three would be 2xy not 17 b7 0 like we want Jaclyn Hmm7 that7s easy to x I revise my de nition thus X is the set consisting of the rst three in forward alphabetic order letters of the alphabet Alby I thought Emily was going to say that its not precise enough because we should specify they are all lowercase Jaclyn Point well taken7 just add lowercase to my de nition Nicolai Dudes7 you are forgetting there are more alphabets in the world than are yet dreamt of in your philosophies 1 For instance7 if an Iranian sees this de nition7 she might list the elements of X as aleph beh7 peh 2 Jaclyn Touchee I should add English to my de ntion also7 so now I have X is the set consisting of the rst three in forward alphabetic order lowercase letters in the English Alphabet Farshz39d I think its reasonable to say that this is a precise de nition of the set X It has three elements7 namely 17 be Good work I hope this little play helps describe what I mean by well de ned Here are some other examples of not well enough de ned sets You7re probably too old to be familiar with Elmo7s World but who knows7 you7re awfully young Perhaps you know Mr Noodle In case you dont know him7 it suf ces to know that at the start of each Elmo7s World episode7 Elmo asks Mr Noodle to do someting related to what Elmo is thinking about Mr Noodle then proceeds to make a real hash of it which toddlers simply LOVE because they love feeling superior to Mr Noodle and they all shout out advice to Mr Noodle Anyway7 you get the idea Let7s ask Mr Noodle to give us a set M7quot Noodle Let B be the set of beautiful people in the world John Objection Dude7 that is7 like SO not well de ned M7quot Noodle Oh yeah Let C be the set of Farshid7s favorite numbers Steve I can7t even begin to register the depth of my objections Would that be the set of Farshid7s favorite numbers when he was 3 years old7 or at this very moment right now7 or 7 Besides7 how are we supposed to know which numbers are his favorite Try to rely on a more universally understood concept7 Mr Noodle M7quot Noodle Okay7 you7re right Let D be the set of positive numbers Jennifer That7s better7 Mr Noodle7 but what kind of numbers do you mean whole numbers7 fractions7 real numbers M7quot Noodle Oh7 sorry7 you7re right This business of elements of sets is so hard Let E be the set with no elments Whoa You might think Mr Noodle is off his rocker7 but actually he has just managed to give us a well de ned and7 I might add7 very important7 set7 namely the empty set The empty set is the set with no elements There are two standard notations for the empty set7 namely either or Q I think you will agree that the rule nothing belongs to the empty 1Apparently Nicolai is taking a course on Shakespeare 2He is also taking a course on Elementary Farsi 10 FARSHID HAJIR set77 is a very solid7 impeccably well de ned rule There is absolutely no ambiguity about that rule the bouncer guarding the gate of the empty set has a very simple job7 namely don7t let anyone into the club7 because nobody belongs You might be uncomfortable with it at rst shouldn7t all sets have at least one element The answer is no7 its very convenient and useful to accept the empty set as a well de ned set you7ll see in a moment why Here are some more standard examples of sets of numbers you will encounter yet and again in this course as well as during the rest of your mathematical career The bold letter N is reserved for the set of natural numbers The elements of N are the counting numbers7 namely 17 27 37 4 57 67 7 Remark In some textbooks7 0 is also considered a natural number Because of this ambiguity7 I usually avoid using the notation N and specify more directly what I mean for instance7 I will write Zgt0 for the set of positive integers7 Z20 for the set of non negative integers7 etc The bold letter Z is reserved for the set of integers7 positive7 negative and 0 Namely Z 7gt727 710123 Leopold Kronecker7 a very in uential and important 19th century number theorist once said something to the effect that Z is at the heart of all mathematics Being a number theorist myself7 I agree with him Another set of great importance is the set R of all real numbers We will discuss the de nition of this set in a bit more detail later on7 but for now7 think of a number line extending in two in nite directions7 with the integers marked on it at regular intervals The real numbers are exactly the distances from 0 along this line to any point on the line it is positive if the point is to the right of 0 and negative if the point is to the left of 0 A real number 7 can be speci ed by giving a decimal expansion77 for it7 ie by an integer followed by a decimal point followed by an in nite sequence of digits 0 9 Later7 we will also discuss the complex numbers C these are all the numbers of the form a bxjl where a b are real numbers Now7 more notation We write x E X read z is in X7 or z belongs to X to mean that z is an element of X and z Z X to mean that z is not an element of X If X and Y are sets7 we write Y Q X or sometimes Y C X if every element of Y is an element of X In this case7 we say that Y is a subset of X Another7 sometimes useful7 way of saying this is that no element of Y fails to be in X Let7s think about this a little What does a set Y have to do in order for it NOT to be a subset of X It would have to have an element y E Y which is not in X In other words7 it would have to have an element y E Y which fails to be in X Therefore7 if Y has no elements that fail to be in X7 then Y is a subset of X If you think back to the de nition of a set7 you will see that two sets X and Y are equal written X Y if and only if Y Q X and X Q Y In other words7 two sets are the same exactly when their membership lists coincide By the way7 recall that any given object z either belongs to a set X or not7 there is no concept of half beloning or not7 or belonging twice For instance7 if X abc and Y abccccc then X Y lt7s as if the guy 0 keeps losing his membership card7 so we had to issue multiple club membership cards for him7 which does not change in any way the fundamental fact that he is a member of Club X Recall from our class discussion that in mathematics7 the truth or falsity of any given statement is not as important as the implicationsthat truth or falsity has on other statements in other words7 a mathematician is an investigator of the logical links between statements In the same way7 what is interesting to us is not so much sets of mathematical interest as the MATH 300 NOTES FALL 05 11 relationships between sets These relationships are mediated by functions between sets I think it would be hard to refute that the single most important concept in all of mathematics is that of a function between sets De nition 32 A map or a function f from a set X to a set Y is a precise rule which assigns7 to each element x 6 X7 a well determined element fx 6 Y We write f X a Y to denote a function with source X and target Y You have encountered many functions usually from R to R in Calculus7 so they are somewhat familiar You probably expect a function to be given by an explicit formula but there are many acceptable ways of de ning a function that do not involve a formula What is needed is precision7 so that there is no ambiguity in how to assign a value f E Y to a given z E X For example7 if we de ne f R a R by f is the nearest integer to s then it is easy to that f174 17 for example7 and f17 f169 177 but what is f1757l This number is equally close to 17 or 18 As de ned7 fis not a function If we de ne f is the greatest integer not exceeding s then f is well de ned and 175 17 Here is another example Let a be the set whose elements are the 26 lowercase English letters7 and B the set of 26 uppercase English letters The map sending a lowercase letter to its corresponding uppercase letter is a well de ned map from a to 6 De nition 33 Let XY be sets Then X Y ala E Xa E Y is called the intersection of X and Y7 and X U Y ala E X V a E Y is the union of X and Y We say that X and Y are disjoint if X H Y is empty We de ne the set exclusion X Y7 sometimes denoted X 7 Y as follows XYX7Y ij Y In other words7 X Y consists of all those members of X which are not also members of Y Little Warmup Exercises A The President of Costless meets the President of Price Chopped and brags If C denotes the set of members of Costless and P denotes the set of members of PriceChopped7 then P C is empty The President of PriceChopped retorts You dont say Consider this I am not just the President of PriceChopped7 I am also one of its members however7 I am not7 nor have I ever been7 a member of Costless The President of Costless then leaves in a huff Explain why B Suppose XY7 Z are sets and let A XY7 B YX First show that A and B are disjoint Suppose A A B7 Z is a partition of X U Y See below for what partition means What can you say about X Y Explain 3 It is clearly desirable that intersection be an operation that takes as input two sets and gives as output another set Since many pairs of sets have no element in common7 whose intersection is then void7 it is a matter of tremendous convenience to de ne the empty set to be the set with no elements Try this experiment locate a kid aged at least 3 years 7 the optimal age for this experiment is probably 5 or 6 if the kid is a teenager7 the experiment will probably fail miserably as it will be dif cult as the reaction will probably consist of little more than Whatever you7re weird Anyway7 nd a kid and then say Hey Kid7 listen to this 12734765777879710 Chances are the kid will go ballistic Kid Nooooo That7s not how it goes You What7s 3free advice draw some blobs and call them X7 Y etc then shade in different regions for A7 B etcl 12 FARSHID HAJIR wrong with it Kid You just can7t do that Its against the rules You But if you put ten pennies in front of me and ask me to count them l7ll get the right anser my way Kid l don7t care you just can7t say 6 before 5 don7t you get it l7m still waiting for the kid who would say Yeah but ifl put 5 or 6 pennies in front of you you7ll mess up What this experiment demonstrates l have tried it quite often myself is that early in life people become familiar with the notion that the set Z is endowed with an ordering in other words the integers come in a speci c order To a child its very hard in fact to separate the concept of number from that of counting and of course counting requires that the numbers be recited in a speci c order The notation that we use for ordering the integers is 3 How is this ordering de ned As usual there are multiple perspectives If you list the integers on the number line in the usual way with 0 in the middle and travelling to the right to 1 then 2 etc and starting at 0 and going left to 1 then 2 etc then for my 6 Z x S y means that y is on top of or to the right of x The same procedure serves to de ne an ordering of the real numbers Another perspective is that Z is divided into two subsets Z4r 1234 Z 7172 7374 and 0 Then x S y means that y 7 z E Z4r U The notion that the integers are ordered according to their size brings up at some early age the question of the largest and smallest numbers Surprisingly early children can decide on their own that there is no largest integer This is a fundamental and rst rate mathematical theorem Once they become familiar with negative numbers children also accept fairly quickly that there is no smallest integer However if one restricts attention to positive integers N or non negative integers Z20 then there is of course a smallest integer namely 1 respectively 0 A slightly more fancy version of this observation has a fancy name since it is often invoked as a useful and fundamental fact of arithmetic But rst lets have a de nition De nition 34 Suppose S is a subset of R We say that l E S is a least element of S if for all s E S we have l S s We say that g E S is a greatest element of S if for all s E S we have s S g The WellOrdering Principle Given any subset S Q Zgt0 of the set of positive integers there exists a least element of S WARNING l have purposely inserted an error in the above statement This error is of a standard type called forgetting to include one of the hypotheses Can you nd the missing hypothesis If not read on you7ll nd it later What is responsible for the Well ordering Principle is the fact is that the integers are a discrete set lts elements don7t get bunched up together so to speak they maintain a respectful distance from each other NON EXAMPLES For instance the open interval I 01 x 6 MO lt z lt 1 has no least element and no greatest element Let us begin to give a proof of this fact Let us prove that I has no largest element the other half is left to the reader that means YOU 4 There are two kinds of mathematicians those who can count and those who cant 7 John Conway 5You no doubt know the important maxim that whenever you learn a new word its a good idea to construct a simple sentence containing that word Well in learning mathematics we have something along these lines Whenver you are presented with a new de nition you need to do two things rst create for yourself an example of the object just de ned then create several examples of objects which just miss tting the de nition you have just encountered Chances are you will learn as much or perhaps more from the nonexamples as from the genuine bona fide examplei MATH 300 NOTES FALL 05 13 Interlude on Proof by Contradiction We must show that I does NOT have a greatest element One way to do this is to use the proof technique known as Contradiction The idea behind this method is simple you wish to prove that some premise P implies some conclusion Q Recall that P i Q simply means that P 7Q is impossible ie is a contradiction ie its truth table has constant value FALSE So the idea behind proving P i Q via contradiction is to place yourself inside a universe where P is true and 7Q is true ie P is true and Q is false Our job is to show that this is impossible so we look around this world we are imagining and look for cracks in its foundation once we nd a statement that is logically untenable and which must follow from the assumptions P 7Q then we will conclude that this world cannot exist so P 7Q must be impossible so whenver P is true Q must also be true ie P 7 Q Back to the statement we wish to prove namely I 01 does not have a greatest element Proof By Contradiction Let us suppose I 01 does in fact admit a greatest element x By de nition z E I and if y E I then x S y Let y z 17 This is the de nitive step we have looked around in this weird universe where z is a greatest element and noticed that since there is quite a gap between z and 1 we can slip in the number y in 01 and check that y x this contradicts the fact that z is a greatest element of I In other words on the one hand y 12 z 7 2 1 x2 lt 1 12 since z lt1 thanks to z E I so y lt 1 and on the other hand y 7m 17 x2 gt 0 1e y gt x But then x lt y lt 1 so y E I so z is NOT the greatest element of I This is a contradiction Thus the hypothesis that I has a greatest element leads to an absurdity it must therefore be false We conclude that I has no greatest element l have made the argument quite repetitive here because I want to hammer home all the different components Now prove that I has no least element and give your argument cogently concisely and correctly De nition 35 A set is called nite if it has a nite number of distinct elements To be more formal a set X is nite if there exists a non negative integer n such that for all sequences x0x1z2 zn of elements of X there exist integers 0 S i lt j S n such that m xi If X is nite then we can de ne the order of X also called its cardinality and denoted by X as follows X is the least non negative integer n with the property that for all sequences x0z1x2 an of elements of X there exist integers 0 S i lt j S n such that x xj Why does such an integer it exist By the assumption that X is nite we know that there exists at least one such non negative integer it now by the Well Ordering Principle 6 there must be a least such integer n 2 0 In less formal language the maximal number of distinct elements in X is called the size of X or the cardinality of X and is denoted by X or sometimes X A set which is not nite is called in nite Equivalently a set X is in nite if and only if for every positive integer it there exists a sequence of n pairwise distinct elements of X In this case we write X 00 As we will see later this statement is slightly misleading as there are in fact multiple gradations of in nity7 For example let us look at the nite set X acbccb for this set we have the sequence acb with no repetitions of length 3 but in any sequence of length 4 or more 6NOTE that the missing hypothesis in the statement of the WellOrdering Principle was that S ll 7Say Whatm stay tuned 14 FARSHID HAJIR coming from this set one of these letters at least must be repeated so le 3 On the other hand the set I 01 is in nite because for instance given any positive integer n the sequence of length n 341213 1n consists of n pairwise distinct elements of I Of course in real life this is not how we count how many things are in a set Again imagine interviewing a child Put a bunch of dots on a page say two or three times the kids age and ask her to count how many dots there are The child will probably point to each dot and count in sequence 123 etc An attempt will be made to make sure of two things a each dot is included in the count and b no dot is counted more than once In other words she will try to cover each dot exactly once What is the child7s method She attempts to set up a one to one correspondence between the dots on the page and a set of type 1 234 n 71n Then the child will know that there are n dots The important principle behind her method is that whenever two sets are in one to one correspondence then they must have the same cardinality or size De nition 36 A map f X a Y is called onto or surjective if for all y E Y there exists z E X such that fz y A map f X a Y is called one to one or injective if whenever 12 E X and p1 31 2 then fz1 31 zz A map f X a Y is called bijective or a set equivalence or most commonly a one to one correspondence if it is injective and surjective We say that two sets X and Y are equivalent if there exists a bijective map f X a Y Example 37 The sets X ab cd e f g and Y A B C D E F G are equivalent For instance the map that sends a lower case letter to the corresponding upper case letter is clearly one to one and onto The sets A 123 and B 90 are not equivalent because any map f A a B is not injective How to prove this Lemma 38 Suppose f X a Y is an injective map of a set X into some set Y IfX has n distinct elements then Y has at least n distinct elements Proof Let 1zn be n distinct elements of X Since f is injective and z 7 pj for 1 S i ltj S n we have 31 y for the same ij Hence the elements fz1 fpn are n distinct elements of Y So Y has at least n distinct elements D The moral is that you cannot shove a set of size 3 into a set of size 2 in a one to one fashion If X is a set then the power set of X is the set 73X consisting of all subsets of X In other words the elements of 73X are subsets of X and every subset of X is in fact a member of 73X Now lets get one thing straight If X is any set any set at all then the empty set is a subset of X Let7s check why in two ways First the direct way is to check that every member of the empty set is in X You might say that since the empty set has no elements then we cannot do this but I say since the empty set has not elements what we have to check is an empty condition so it holds by at so to speak There is nothing to check so the fact is true If you wish think that a statement is true unless proven false Now here is the second way perhaps you will nd it more convincing In order for the empty set to fail to be a subset of X we have to produce an element of which does not belong to X Since we can nd no such suspect the empty set must be a subset of X MATH 300 NOTES FALL 05 15 Example 39 List all subsets of X abc Well there is only one subset of size 3 namely X itself There are three ways to leave out an element so there are three subsets of size 2 namely ab ac bc Similarly there are three ways to pick one element to leave in so there are three subsets of size one ab Finally there is one subset of size 0 namely Altogether there are 13 3 1 8 subsets of X Thus 73X has size 8 De nition 310 A partition A of a set X is a subset A Q 73X of the power set of X with the following two properties i if Y1Y2 E A then Y1 Yg and ii the union of all elements of A is X In other words a partition of X a collection of pairwise disjoint subsets of X whose collective union is X In a future unit we will explore the importance of partitions in more depth when we talk about equivalence classes Example 311 A Let X 1234 Then A 1234 is a partition of X At the two extremes we can partition X via the largest possible subdivision namely A 1 2 3 4 or the smallest one A B If S is the set of students at an elementary school then two natural partitions are the class partition and the grade partition Which one of these do you think is potentially ner Now a caveat regarding our treatment of sets for the sake of honesty I have given a relatively informal de nition of what it means for a rule de ning a set to be well de ned but in truth this concept is actually an extremely deep and subtle one For practical purpose we may and we will almost entirely avoid all the depth and all the weird subtleties to begin exploring them if you wish consult some books on logic or Godel Escher Bach by D Hofstadter For most mathematicians the particular sets we use in everyday work are of a simple standard type which do not exhibit any pathological behavior So far we have de ned sets by listing all the elements This is not always the most convenient method Sets are often described in terms of the conditions satis ed by elements of a larger set For instance N z 6 Hz 2 18 This should be read as the set of natural numbers consists of all z in the set of integers that satisfy z 2 1 Some more examples z E Rz2 1 should be read as the set of all real numbers whose square is equal to 1 Thus the elements of this set are 1 and 71 z 6 Zn gt 0 z is odd is the set of positive odd integers whereas z E Zh gt 0 z is odd is the union z 6 Zn gt 0 U 2k 1k E Z Finally let us note the use of the dummy variable 9 namely z E Rz2 1 C 6 KW 1 De nition 312 Suppose X1 Xn are sets The direct product of X1 Xn denoted by X1 gtlt X2 gtlt gtlt X is the set of all ordered n tuples z1z2 zn where z E X for z12n For examples R gtlt R is the set of all ordered pairs zy where zy E R In other words R gtlt R can be thought of as the set of coordinates of points in the usual zy plane 8The little vertical line should be read as such that sometimes instead one uses the colon instead of 9the poor variables get no respect 16 FARSHID HAJIR Part 3 Sets and Maps 4 PARTITIONS OF SETS If X is a set7 then the power set of X is the set 73X consisting of all subsets of X In other words7 the elements of 73X are subsets of X7 and every subset of X is in fact a member of 73X Recall that two sets Y and Z are called disjoint or sometimes non overlapping if Y Z Instead of saying Y intersect Z is empty sometimes I might say Y and Z do not meet7 or Y and Z have no one in common or Y and Z have no intersection You shouldn7t take the latter phrase too literally7 of course7 because Y and Z do have an intersection even when they are disjoint7 its just that their intersection happens to be a set devoid of elements7 ie is the empty set If X7 Y7 Z are three sets7 we say that X7 Y7 Z are disjoint if X Y Z Lets be very precise about what we mean by the intersection of a bunch of sets so far we only de ned the intersection of two sets Say we have a collection of sets and we want to take their intersection First of all7 how do we list this collection of sets One way is to index them in other words7 we have some auxiliary set A which we will use to index our sets7 meaning for each or 6 A7 we have one set Xa in our collection We can then say that we have a collection C Xaloz E A of sets Their intersection is de ned as aEAXo E Xa for all or E A If this intersection is the empty set7 we say that the collection of sets is disjoint There is a much stronger condition7 namely that of the collection of sets being pairwise disjoint This means that for every pair 046 6 A7 Xa X For instance7 the collection 127 237 34 is disjoint nobody is in all three sets simultaneously but not pairwise disjoint It happens often that we want to divide up a set into smaller pieces For example7 consider the set of students in Math 300 this semester We may break them up or classify them in quite a few natural ways 1 according to the students major 2 according to the students registration status fresh7 soph7 jr7 sr7 other 3 according to the students TA Pick any one of these schemes for breaking up the set of Math 300 students into smaller subsets and check that it enjoys the following property every student belongs to exactly one subset This means that the subsets do not overlap7 and that the union of all the subsets is in fact the whole class We say that each of these schemes for breaking up the class is a partition of it De nition 41 BOGUS ALERTlo A partition A of a set X is a subset A Q 73X of the power set of X with the following two properties i Given YZ E A with Y 31 Z7 then Y Z 7 and ii the union of all elements of A is X In other words7 a partition of X is a collection of pairwise disjoint subsets of X whose collective union is X 10Recall that occasionally in class and in these notes7 I will make bogus7 slightly wrong7 statements Okay7 lets be frank about it7 I will just lie on purpose The goal is to show you how doing mathematics is a progressive process7 full of false starts and second attempts We learn a lot everytime we crash the plane Sometimes when I want you to be on the lookout for my lies7 I will give you the BOGUS ALERT signal7 and sometimes I wont In this particular case7 I want you to be on the lookout for a missing assumption which would make the definition more elegant MATH 300 NOTES FALL 05 17 In the near future we will explore the importance of partitions in more depth when we talk about equivalence classes Example 42 A Let X 1234 Then A 1234 is a partition of X At the two extremes we can partition X via the largest possible subdivision namely A 1 2 3 4 or the smallest one A How many partitions does the empty set have C If X is a non empty set then A X is a partition indeed it is the coarsest possible partition of X At the other extreme if A consists of all singleton subsets of X ie A E X then A is the nest partition of X D If S is the set of students at an elementary school then two natural partitions are the class partition and the grade partition Which one of these do you think is potentially ner E Consider the partition X It is a partition according to our de nition because X and X U X But is it not a slightly annoying partition Why do I nd it annoying l7ll tell you why Suppose X is a set and A is a partition of X where none of the chosen subsets is empty So A speci es a certain scheme for how to divide up A into teams Now suppose we add to A the empty set Has the scheme for dividing up the teams changed at all No But the partition has Putting the empty set in the partition doesn7t really add or subtract anything from how the set is actually broken up it doesn7t serve any useful purpose It just dirties the waters so to speak So it would be more clean more tight more elegant if we don7t allow the empty set to be one of the subsets allowed in the partition This is the source of the BOGUS ALERT I gave you earlier Accordingly below is BOGUS ALERT FREE de nition of partitions De nition 43 If X is a set and A Q PX is a collection of subsets of X then A is a partition of X if i for all Y E A Y 31 ii for all Y Z 6 A with Y 31 Z Y Z and iii UyEAY XM In other words a partition of X is a collection of non empty pairwise disjoint ie non overlapping subsets of X whose union is X Now how many partitions does the empty set have I think it is probably intuitively clear what I meant by coarser and ner partions in the above examples Here is a new kind of exercise or problem you may not have tried before try your hand at making up a formal de nition by completing the following De nition 44 Let X be a set and suppose A and A are two distinct partitions of X We say that A is ner than A if We say that A is coarser than A if A is ner than A 5 MAPS BETWEEN SETS One of the maxims of modern mathematics is that objects are not as important as the relationships between objects The meaning of this maxim will perhaps become clearer as the course goes on and l don7t want to dwell on it here except to point out how in a way we have already encountered one instance of this when studying implications Recall that in pondering an implication statement P i Q the truth of P or that of Q in any given situation is not so important what is important for P i Q is whether there is some logical 11The notation UyEAY means the union of all Y as Y runs over all elements of A 18 FARSHID HAJIR glue which rules out Q being false whenever P happens to be true whether that logical glue exists or not is what determines the truth or falsity of P i Q so its the relationship between P and Q that is of import when we ponder P i Q l have said that sets are the primal words in the language of mathematics Combining this with the maxim stressing the importance of relationships between objects we conclude that a central role in mathematics must be played by the gadgets that measure relationships between sets The most common such gadgets as we alreay mentioned are called functions or maps A more general more exible but less frequently encountered notion for expressing relationships between sets is that of a relation which we will talk about a little later For now let us concentrate on functions and begin by recalling its de nition De nition 51 A map or a function f from a set X to a set Y is a precise rule which assigns to each element x E X a well determined element fx 6 Y We write f X a Y to denote a function with source X and target Y You have encountered many functions usually from R to R in Calculus so they are somewhat familiar You probably expect a function to be given by an explicit formula but there are many acceptable ways of de ning a function What is needed for a de nition to be valid is simply a high degree of precision so that there is no ambiguity in how to assign one single value fx 6 Y to any given z E X For example if we de ne f R a R by fx is the nearest integer to x then it is easy to that f174 17 for example and f17 f169 17 but what is f1757l This number is equally close to 17 or 18 As de ned f is not a function If we de ne fx is the greatest integer not exceeding x then f is well de ned and f17 175 17 In calculus one often speci es a function in shorthand by alluding to part of a formula or symbol de ning it viz the sine function or the exponential function or 1z with utter disregard for the speci cation of its source and target Therefore you must retrain yourself in two ways rst think of functions as having three components I a source set ll a target set III a rule describing how to assign one single element in the target set to each element in the source Second be more exible about what kinds of sets can be sources and targets for maps and also about how the rule for assigning elements of the target to the source elements is described Every map f X a Y from a set X to a set Y establishes a connection a relationship between these two sets Sometimes this connection is very tight setting up a correspon dence between the two sets showing them to be similar and sometimes not There are two important ways to measure how tightly a function binds two sets Consider for example the case of P being the players on the current UMass Amherst Hockey Team and N being the set of whole numbers between 0 and 99 inclusive There is a map f P a N which assigns to each player his jersey number This relationship is tight in one way namely no two players are assigned the same number for obvious reasons so that the map can be used to identify players uniquely based on their jersey number But there is another way in which this map is not tight namely there are gaps so to speak between the numbers that have been assigned to the players Not every number in the range 0799 actually corresponds to a player for instance Zech Klann is no 39 but no one wears the no 38 jersey As another example ifX is the set of TAs for Math 300 this term and Y undergrad grad then l7m sure you7ll agree there is a naturally de ned map f X a Y which assigns to each TA hisher degree program status Now for this map there are no missed values because MATH 300 NOTES FALL 05 19 for instance7 Molly is a graduate TA7 and Aaron is an undergraduate TA7 so the map is tight as far as hitting every possible value is concerned But now there are four undergraduate TAs7 so you cannot necessarily determine the identity of a TA based soleley on hisher degree program status On the other hand7 say Y is the set consisting of the 26 lowercase English letters and X n E le S n S 26 The map f X a Y sending n to the nth letter of the alphabet in the standard order does not miss any letters and no two distinct n go to the same letter In other words7 each number corresponds to exactly one letter and vice versa In this case7 the map is as tight as possible we call it a set equivalence or sometimes a one to one correspondence7712 Let us formalize these concepts De nition 52 A map f X a Y is called onto or surjeetive if for all y 6 Y7 there exists z E X such that fz y A map f X a Y is called one to one or injective if whenever 172 E X and 1 31 2 then fz1 31 fz2 A map f X a Y is called bijeetive or a set equivalence if it is injective and surjective We say that two sets X and Y are equivalent if there exists a bijective map f X a Y Example 53 The sets X mo7 cd7 e7 f7 9 and Y A B7 0 D7 E7 F7 G are equivalent For instance7 the map that sends a lower case letter to the corresponding upper case letter is clearly one to one and onto The sets A 123 and B 90 are not equivalent7 because any map f A a B is not injective How to prove this Lemma 54 Suppose f X a Y is an injective map of a set X into some set Y IfX has n distinct elements then Y has at least n distinct elements Proof Let 17zn be n distinct elements of X Since f is injective7 and zl 31 z for 1 S i ltj S n7 we have 31 y for the same i7j Hence the elements fz1 7fzn are n distinct elements of Y So7 Y has at least n distinct elements D The moral is that you cannot shove a set of size 3 into a set of size 2 in a one to one fashion 6 COMPOSITES AND INVERSES OF MAPS Lets say you want to y from Columbus Ohio to London England Chances are there are no direct ights So7 what do you do You y from Columbus to Chicago say7 then catch a ight from Chicago to London You concatenate the two ights to create a path from Columbus to London You can do a similar thing with maps of sets Suppose f X a Y is a map and g Y a Z is a map Then7 can we de ne a map from X to Z by concatenating77 the two maps to get a map h X a Z How do we specify a map We take an arbitrary z E X and we have to describe how to attach an element of Z to it Well7 how about hz gfz7 In other words7 rst we send z to fz 6 Y7 then7 having safely arrived at fz7 since fz is in Y7 we can send fz to Z via 9 giving us The picture is X a Y a Z x H me e we 1ZMake sure you note that there is a big differnce between a map being oneto one and a map being a oneto one correspondence the former just means injective but the latter means injective AND surjectivei This is one of the reasons I prefer the terms injectivesurjective over oneto one and onto 20 FARSHID HAJIR Note that in the picture the map f comes before 9 but in the algebra 9 comes before to the left of f This can be a little disorienting at rst but you7ll get used to it with practice We write that h g o f This means that the source of h is the source of f and the target of h is the target of g and that for an arbitrary z in the source of f h We say that the map h is the composite of the maps f and 9 You have seen composition of functions before when you studied the chain rule in calculus for example Thus the function h sinz2 a function from R to R for example is a composite of two maps namely if f R a R is the map given by f 2 and g R a R is given by 9y siny then 9 o f h You should check this If X and Y are sets we let MapsX Y be the set consisting of all maps from X to Y Now let us study maps from a set X to itself These are sometimes called self maps of X Among all maps from X to itself there is one very special one called the identity map and usually denoted idX it is a very neutral map as it is de ned simply by idX z for all z E X Recall that a bijective map f X a Y sets up a one to one correspondence between X and Y so that if at any point we nd ourselves at some point in Y we know exactly one point in X to which it corresponds and if we are at a particular point in X we know exactly which single point in Y it is linked with For example if there are four students in a section say Emily Braley Amy Jackson Mike Malloy and John McColgan then we have a map F a L where F Emily Amy MikeJohn and L Braley Jackson Malloy McColgan which links each students7 rst name with his or her last name Note that this link is injective and surjective so that we can go back and forth77 from one list to the other without any ambiguity More generally if f X a Y is a map then we may ask Under what conditions will there may be a map 9 in the reverse direction 9 Y a X such that the maps f and 9 undo each other ie gfx x for all z E X and fgy y for all y E Y We can rephrase this as follows Given a map f X a Y when is there a map 9 Y a X such that gof idX and f o g idy If such a map exists we call it an inverse function for f and denote it by f l IMPORTANT EXAMPLE It is very signi cant that for an inverse function we insist not only that g undoes f but that in turn f undoes 9 As an example to illustrate that this does make a difference let X 1 and let Y 711 Consider the map f X a Y de ned by f1 1 Since X has only one element a moments thought will convince you that there is only one map from Y to X namely 9 Y a X which sends everyone to 1 ie 91 971 1 Now it is clear that g undoes f ie g o f idX But note that fog 31 idyl lndeed f og1 1 and f og71 1 so f does not undo g If you think about it you will see that since X and Y do not have the same cardinality no map from X to Y could ever undo a map from Y to X De nition 61 We say that a map f X a Y admits an inverse if there is a map 9 Y a X such that gfz z for all z E X and fgy y for all y E Y In other words 9 is an inverse of f if g o f idX and f 09 idy Now we can give a very satisfying answer to our question about which maps admit inverses The following is a very important and useful theorem You should study its statement and proof carefully Theorem 62 A map f X a Y admits an inverse if and only iff is bijeetive MATH 300 NOTES FALL 05 21 Proof Let us suppose f is bijective As we saw in class this means that for each y E Y there is a unique x such that fx y Now de ne g Y a X as follows for each y E Y since there is one and only one x E X such that f y then by putting 9y x g is well de ned We also clearly have gfz 9y x so 9 o z for all z E X so 9 o f idX similarly for y E Y fgy f y Thus we have shown that if f is bijective then it admits an inverse Let us now prove the converse Suppose g is an inverse for f Let us show that f is injective Suppose Lz E X and f fx Then gfz gfx But gfz and gfz x by the fact that g is an inverse to f hence x x We have shown that the only way for on E X to have the same image f fz under f is for z to be equal to x Thus f maps distinct elements of X to distinct elements of Y ie f is injective Now welll show that f is surjective Given y E Y we must nd z E X such that f y that7s easy let x Then f fgy and fgy y by the de nition of inverse function77 E NOTE Often an easy way to show that a function is bijective is to nd an inverse for it as in the following example Example 63 Consider the map f 01 a 711 given by f 4x 7 for z 6 01 Show that f is bijective lt suf ces to note that ify 4x7 then we can uniquely solve for and get z ye 4 Thus if we de ne the map 9 711 a 01 by 9y y 7 74 then gfz z for all z 6 01 and fgy y for all y 6 711 Proposition 64 a If a map f X a Y admits an inverse map 9 then the inverse map 9 is unique and we will denote it by f l b In this case the map f 1 Y a X is invertible also andits inverse is f ie f lil f Proof a Suppose 99 Y a X are both maps from Y to X that are inverses to f Thus 90 9 f96 M01 all 96 E X and f9y f9 y y for all y E Y Since f admits an inverse by the above Theorem f is bijective What is our task We must show that the functions 9 Y a X and g Y a X are really the same function That means we have to show for each y E Y gy g y Well given y E Y since f is surjective we can nd z E X such that f y Then 9y gfz z g fx g y This completes the proof that g g b Now suppose g f l By the de nition of inverse function we have that gfx z for all z E X and fgy y for all y E Y hence f is an inverse for 9 By the uniqueness of the inverse we must have 9 1 f or f lil which is what we wished to prove D Finally we recall here a de nition from the previous homework De nition 65 Suppose X1 Xn are sets The direct product or Cartesian product of X1 Xn denoted by X1 gtlt X2 gtlt gtlt X is the set of all ordered n tuples 1 2 xn where d E X for i 12n For examples R gtlt R is the set of all ordered pairs my where Ly E R In other words R gtlt R can be thought of as the set of coordinates of points in the usual zy plane and R gtlt R gtlt R can be thought of as the set of all points in three dimensional space 22 FARSHID HAJIR Part 4 Counting Principles and Finite Sets 7 THREE COUNTING PRINCIPLES 71 The WellOrdering Principle The notion that the integers are ordered according to their size brings up7 at some early age7 the question of the largest and smallest numbers Surprisingly early7 children can decide on their own that there is no largest integer This is a fundamental and rst rate mathematical theorem Once they become familiar with negative numbers7 children also accept fairly quickly that there is no smallest integer by symmetry However7 if one restricts attention to positive integers N or non negative integers Z20 then there is of course a smallest integer7 namely 1 respectively 0 The same is true of any subset of N or of Z20 This simple but extremely handy observation has a fancy name since it is often invoked as a useful and fundamental fact of arithmetic But rst7 lets have a de nition De nition 71 Suppose S is a subset of R We say that l E S is a least element of S sometimes minimal element if for all s 6 S7 we have l S s We say that g E S is a greatest element of S or mammal if for all s 6 S7 we have s S g The WellOrdering Principle Given any nonempty subset S Q Z20 of the set of positive integers7 there exists a least element or minimal element of S WARNING In the above statement7 if you forget to say that S is non empty7 then the statement becomes false The empty set has no least element7 because it has no elements whatsoever What is responsible for the Well ordering Principle is the fact that the integers are a discrete set lts elements dont get bunched up together7 so to speak they maintain a respectful distance from each other This is a topological property of the integers as a subset of the real numbers NonExample 72 For instance7 the open interval I 01 x 6 MO lt z lt 1 has no least element and no greatest element A proof of this using the the proof by contradiction method was given earlier in these series of notes Perhaps you dimly remember skipping that Well7 now go back and read it7 or better yet7 try to give a proof for yourself Example 73 Let S be the set of positive integers that when added to themselves are divisible by 127 ie SxEZgt0andx12y for somey 6 Its not too hard to see that the least element of S is 6 72 The PigeonHole Principle Lets say you have a bunch of pigeons and a bunch of pigeon holes If all the pigeons must be placed in the pigeon holes7 and you have more pigeons than pigeonholes7 then at least two pigeons will have to share a pigeon hole That7s the Pigeon hole Principle ln Germany7 they call this the Shoebox principle13 with shoes playing the role of pigeons and boxes you get the idea Here is a game you should play pick your own favorite imagery for objects pigeons7 shoes7 ducks7 pencils7 as well 13or the much more amusing Schubfachschluss Priazip on this topic you should read Act I of Oscar Wilde s The lmportance of Being Earnest MATH 300 NOTES FALL 05 23 as places to put them holes boxes slots to get your own principle such as The Pencil box principle or the Ducks in row principle Then translate your phrase into some abstruse language to get a really cool Principle of Your Very Own You might think this is a colossally silly thing to make into a principle77 but you would be wrong it is very useful and important Sometimes a slightly fancier version is handy The Pigeonhole Principle Suppose k 2 1 is a positive integer If N pigeons are to be placed in H pigeon holes and N gt kH then there will be at least one pigeon hole housing more than k pigeons It might sound fancy but its very simple Let7s use the proof by contradiction way of looking at it If there are no pigeon holes housing more than k pigeons then every pigeon hole houses at most k pigeons so then the number of pigeons is at most kH but kH lt N So N the number of pigeons lt N This is rather embarrassing so there must be at least one pigeon hole housing more than k pigeons 73 The multiplication counting principle Lets say your breakfast every weekday morning consists of one bagel and one cup of coffee at the Marcus Cafe There are the following choices for the bagel plain poppy seed sesame onion cinnamon raisin salt and everything nine choices in all Your coffee choices are small regular small decaf large regular and large decaf Now how many different possible breakfasts can you have You could list them all in a systematic way for example by saying there are four breakfasts where the bagel is plain indexed by the four different coffee choices there are four breakfasts where the bagel is poppy seed etc In fact there are four breakfasts for each type of bagel and there are 9 types of bagels so the total number of breakfasts is 444444444 36 Of course you could also say its 9 4 36 Or if you say there are 9 breakfasts where the cofee is regular etc you7d get 4 9 36 breakfasts Now then you say aha but I can get the bagel toasted or not so now how many breakfasts are there Well since toastednot toasted is two choices it just doubles the number of breakfasts to 72 Oh I forgot I can also choose No topping Cream Cheese topping or butter that7s three choices tripling the number of breakfasts to 216 Oh I forgot that for the coffee I might choose sugar or not sugar doubling the number of choices again to 432 Then I might opt for Regular Milk Lowfat Milk Skim Milk Cream HalfHalf or No Gosh Darn Cold Liquid ln my Cosh Darn Co ee Thank You Very Much sextupling the number of choices to a mere 2592 possible breakfasts No wonder I never vary my breakfastl14 We have just seen an example of the Multiplication Counting Principle77 The total number of possible outcomes of a compound event is the product of the number of possible outcomes for each of the constituent events Again this is a simple and extremely nimble principle Why is it true Well say you have two nite sets X1 and X2 and you take their Cartesian product X1 gtlt X2 Recall that this is the set of all ordered pairs of type 12 where 1 6 X1 and x2 6 X2 There are ngl elements of the Cartesian product whose rst coordinate is 1 an equal number whose rst coordinate is 2 etc giving us a total of ngl added to itself lel times which is just 14PoppySeed Bagel with no topping untoasted unsugared coffee and NoGoshDarn Cold Liquid ln my GoshDarnCoffee Thank You VeryMuchi 24 FARSHID HAJIR lel ngl In other words7 le gtlt Xgl lel gtlt ng It takes little more effort to prove the more general rule that if X17X27 Xn are n 2 2 nite sets7 then lX1gtltX2gtltgtltanlX1lgtltgtltan For instance7 in a short while7 well give a proof of this using Mathematical Induction 8 FINITE SETS We have been studying sets and maps between sets Suppose two sets X and Y meet at a party and want to nd out about each other What would be the rst question one set would ask another7 do you think Perhaps the most fundamental question is Are you the empty set There is a profound difference7 after all7 between the empty set and all other sets If the set you have met is ernpty7 then you know exactly who she is But if the set you have met is non ernpty7 then what question would you ask next I think a perfect sensible question is How many elements do you have In particular7 to size up the set you have just rnet7 what you are really curious about is whether she is in nite or nite What does this mean Oh Oh7 I think another one act play is about to start In nite sets Starring Farshid as Professor Dude7 and lntroducing Jererniah Ashley7 Shaohan7 Nicolai7 Jererny Eric7 Kwylan7 Ben7 Bert7 Matthew7 Arny7 Emily and Alby Farshz39d Class7 what does it mean for a set X to be in nite Jeremiah An in nite set is one that has in nitely many elements Farshz39d Sorry I don7t understand7 what does it mean to have in nitely many elements Ashley Don7t play stupid7 you know what that means Farshz39d No7 really7 I want a rigorous7 solid7 de nition of what it means for a set to be in nite So far7 it has been put forward that a set is in nite if and only if it has in nitely many elements That is possibly a good de nition7 but only if someone can then de ne rigorously what it means for a set to have in ntely many elements For instance7 for the set 1237 here are in nitely many elements 111111111 but 123 is clearly not what you would call an in nite set The point is You have to give a rigorous de nition of what it means to give in nitely many elements of the set I submit that when it comes to in nity7 nothing is obvious or to be taken for granted In this course7 one thing you will hopefully learn is that ln nity is a big tough guy on the block you don7t mess around with it So7 I must insist7 please de ne either a what it means for a set to be in nite7 andor b what it means for a set to have in nitely many elements Shaohtm I cannot answer your question irnrnediately7 but I would like to say that in nite is the opposite of nite Nicolai That7s a good point Dude7 if you can de ne what it means for a set to be nite7 then l7ll give you a de nition of what it means to be in nite7 namely a set is called in nite if it is not nite Farshz39d That is perfectly acceptable7 in theory7 assuming you can give a good de nition of what it means for a set to be nite Julie Well7 a set is nite if you can count how many elements it has That7s easy Jeremy I think Professor Hajir is looking for something more formal than that Julie Who7s Professor Hajir Oh7 you mean that Farshid guy Okay7 no problem A set is nite if you can list all its elements in a nite amount of time MATH 300 NOTES FALL 05 25 Farshz39d You are on to something7 Julie However7 do you think that this is really a workable de nition Will you ever be able to prove that a set is NOT nite using that de nition Let me suggest that you should try to take time out of your de nition You said a minute ago that a set is nite if you can count how many elements it has Imagine you are 4 years old and I give you a bag of apples How would you count the number of apples in the bag Eric Dude7 like7 l7ll handle that one You take one apple out and you go 177 you take out another apple and you go 277 and so on7 and so forth7 until you have taken out all the apples If the last number that you said is7 n then the number of apples is n7 Bert Wait7 you know what you are doing when you7re doing that You are setting up a one to one correspondence between the bag of apples and the set 1727771 7 171 Each apple gets labelled with exactly one integer between 1 and 717 so the map you are creating is a bijection Eric Well7 I never thought of it that way7 but I agree with what you say Amy Okay7 how about this A set X is nite if there exists an integer n 2 0 such that the set X is equivalent to the set 1237 7n7 ie there is a bijection f X a 172 771 Matthew Why 71 2 0 Why not 71 2 1 Kwylan Don7t forget the empty set dudesl Matthew Gotcha Hey7 you know the n77 in Amy7s de nition is how many elements the set has7 we should call it the size of the set Farshz39d Good point This is great7 but I still want to know what it means to be an in nite set Emily Um7 like7 haven7t you been paying attention We already de ned what it means for a set to be nite7 and now we say that a set is in nite it is NOT nite Farshz39d You7re right7 17m just trying to catch up here Let me see if I can summarize for myself what conclusions you have reached First of all7 your strategy for checking whether a given set is nite or not and if it is nite to know its size7 is to compare it to a standard family of counting sets77 To facilitate the summary7 lets give a name to these special counting sets for each integer n 2 07 let Znz Zl1 x n Bert Hey7 there7s that n 0 again I still don7t like that Your de nition doesn7t make sense if n 0 because you get Z0 x E Z11 S x S 0llll That7s not well de ned because there are no such zlll Ben I see what you don7t like 1 S x S 0 is stupid Shaohtm It is not so much stupid as false In other words7 since 1 S x S 0 simply does not hold for any s it is a contradiction ie a false statement Farshz39d Let7s look at Z0 You are abosolutely right7 Bert7 when you say that Z0 consists of all integers x such that z is bigger than 1 and less than 0 Of course7 there are no such integers But that doesn7t mean that we have to ush everything down the toilet and say its not well de ned For a set to be well de ned7 the bouncer should be completely sure about who to let in and who to bounce out For the set Z07 the instructions to the bouncer are there are no x that pass the test for getting into Z07 so bounce the heck out of every single x that comes along This is not an ambiguous rule7 it7s pefectly well de ned7 it7s perhaps the 26 FARSHID HAJIR most well de ned rule for any bouncerl Its just that Z0 is the set with no elments ie Z0 is the empty set that7s all Bert Oh okay sorry man that was bothering me I see now FursLid No problem Now Z0 is the empty set It has size 0 Z1 1 it has size 1 Z2 1 2 it has size 2 and so on For an integer n 21Zn Zn1Un 123 n and lan n Finally here is the summary of our discussion GIVEN A SET X IF THERE EXISTS A NON NEGATIVE INTEGER n SUCH THAT X IS EQUIVALENT To THE SET 123n THEN THE SET X IS nite AND WE SAY THAT ITS size IS n IF THERE IS NO SUCH n THEN WE SAY THAT X IS INFINITE Alby sotto U006 Leave it to this guy to take something so simple as counting and making it sound complicated FursLid What was that Alby Oh nothing I was just saying how much I like this class FursLid Well l7ll be damned De nition 81 A set is called nite if it has a limited number of distinct elements To be more formal a set X is nite if there exists a non negative integer n such that for all sequences z0z1z2 zn of elements of X there exist integers 0 S i lt j S n such that z zj In other words a set is nite if for some n 2 0 every list of n 1 elements of the set must have a repetition If X is nite then we can de ne the order of X also called its cardinality and denoted by le as follows le is the least non negative integer n with the property that for all sequences z0z1z2 zn of elements of X there exist integers 0 S i lt j S n such that z zj Why does such an integer n exist By the assumption that X is nite we know that there exists at least one such non negative integer n now by the Well Ordering Principle there is a unique smallest such integer n 2 0 and this n is the cardinality or size of the set In less formal language the maximal number of distinct elements in X is called the size of X or the cardinality of X and is denoted by le or sometimes X A set which is not nite is called in nite Equivalently a set X is in nite if and only if for every positive integer ii there exists a sequence of n pairwise distinct elements of X In this case we write le 00 As we will see later this statement is slightly misleading as there are in fact multiple gradations of in nity l5 For example let us look at the nite set X acbccb for this set we have the sequence acb with no repetitions of length 3 but in any sequence of length 4 or more coming from this set one of these letters at least must be repeated so le 3 On the other hand the set I 01 is in nite because for instance given any positive integer n the sequence of length n 12 23 34 n 7 1n 1 consists of n pairwise distinct elements of I Thus there exist arbitrarily long sequences of pairwise distinct elements in I so I must be in nite Of course in real life this is not how we count how many things are in a set Again imagine interviewing a child Put a bunch of dots on a page say two or three times the kids age and ask her to count how many dots there are The child will probably point to each dot and count in sequence 123 etc An attempt will be made to make sure of two things a each dot is included in the count and b no dot is counted more than once ln 15We will see that the set of real numbers for example is a lot more infinite77 than the set of integersl MATH 300 NOTES FALL 05 27 other words she will try to cover each dot exactly once What is the child7s method She attempts to set up a one to one correspondence between the dots on the page and a set of type 1 234 n 7171 Then the child will know that there are n dots The important principle behind her method is that whenever two sets are in one to one correspondence then they must have the same cardinality or size Lemma 82 Suppose f X a Y is an injective map of a set X into some set Y a For any integer n 2 2 ifX has n pairwise distinct elements then Y has at least n pairwise distinct elements b IfY is nite then X is nite also and moreover le S Proof First we prove a Let p1 pn be n pairwise distinct elements of X Since f is injective and x 7 pj for 1 S i ltj S n we have 31 y for the same ij Hence the elements fp1 x are n pairwise distinct elements of Y So Y has at least n distinct elements Now to prove We assume that Y is nite Let n We claim that X cannot have n 1 pairwise distinct elements For if it did then by part a Y would would have n 1 pairwise distinct elements which would contradict n Since X cannot have n 1 pairwise distinct elements we must have le S n In particular X is nite and W s m Now we are ready to prove the theorem we have been after GIVEN A SET X IF THERE EXISTS A NON NEGATIVE INTEGER n SUCH THAT X IS EQUIVALENT To THE SET 123n THEN THE SET X IS nite AND WE SAY THAT ITS size IS n IF THERE IS NO SUCH n THEN WE SAY THAT X IS INFINITE Got it Theorem 83 IfX and Y are equivalent sets and if one of them is nite then the other is nite also and le Proof Suppose Y is nite Since X and Y are equivalent sets there exists a bijective map f X a Y Since f is injective by Lemma 82 X is also nite and le S Now we have the map f 1 Y a X which is also bijective why so again by the same Lemma lYl S Since le S lYl and lYl S le we have le If we start with the assumption that X is nite instead of Y then we repeat the argument starting with a bijection g Y a X D 28 FARSHID HAJIR Part 5 Equivalence Relations and Partitions 9 RELATIONS Recall the concept of a function f from a source set X to a target set Y It is a rule for mapping each element x of the source to a single7 well de ned7 element of the target7 which we call A function from X to Y gives a very neat relationship between these two sets Not all relationships between two sets are so neat and we will now consider a more general notion7 that of a relation between X and Y De nition 91 Suppose X and Y are sets and R Q X gtlt Y is an arbitrary subset of the Cartesian product of X and Y We say that R determines a relation from X to Y in the following way If x E X and y E Y we say that z is related to y and write x NR 1 if my 6 R7 and we say that z is not related to y z 743 y if Ly R If R is a relation from X to Y7 and z 6 X7 we say that the ber above z is the set Rm y E Y my 6 R Similarly7 for y E Y R x E X my 6 R is the ber below y The Graph of the relation R is simply the set R itself If X and Y are subsets of R with XY lying along the x axis7 y axis as usual7 then RE is simply the intersection of the vertical line passing through z with the graph of R and R is the intersection of the horizontal line through y with this graph The relation R determines a function X a Y determines a function if and only if for each x 6 X7 the ber above it7 R1 is a singleton7 ie contains a single element7 which is then the value of the function at x Thus7 a relation can be thought of as a function when its graph passes the vertical line test7 Here is an informal summary of the above formal de nition First7 informally speaking7 a relation R between X and Y is a rule which7 given z E X and y E Y determines whether z is related77 to y or not If x is related to y we write x NR y and otherwise we write x 743 y The graph of R is de ned by E X X Y z NR If for each x 6 X7 there is a unique y E Y such that z NR y then R is a special kind of relation called a function in that case7 we write y is the value of this function at x if z NR y Let us consider some examples Example 92 Let X Y R and let R E R2 x2y2 1 In other words7 z is related to y if and only if my is a point on the unit circle The graph of the relation is just the unit circle For instance7 1 NR 0 because 1202 1 and 05 743 05 because 052 052 05 31 1 Now lets talk about bers We have R0 17 71 because 02 y2 1 has two solutions y i1 On the other hand7 the ber below 1 has only one element7 because R1 x E X f x2 1 1 By looking at the picture7 one can see immediately that the ber above x has 01 or 2 elements depending on whether is greater than 17 equal to 17 or less than one7 respectively In particular7 this relation is not a function Example 93 Let X 02 and Y 012 Let R E R2 f y 7 3x2 0 The graph of this relation is a piece of the parabola y 3x2 Since there is exactly one y Value in Y for each x value in X7 this relation actually determines a function X a Y7 namely 3H MATH 300 NOTES FALL 05 29 Example 94 A relation can also be determined by just listing which elements of X are related to which of Y For example let X abcd and Y 01 Then we de ne a relation R by de ning the related pairs to be are a N 0 b N 1 b N 0 c N 1 This means that these are ALL the related pairs In other words the subset R of X gtlt Y is simply R a0b1 b0c This relation is not a function here are two reasons the ber above b is too big it is 01 and the ber above d is too little it7s emptyl Example 95 Let X Y 711 and de ne z NR y if and only if xy 2 0 Thus R 6 01 gtlt 01 xy 2 0 What does the graph of this relation look like Think about it on your own for a minute No Peekie until one minutes worth of thinking has occurred What did you get The union ofthe unit squares in the rst and third quadrants including the axes I hope Verify that Rm 01 if z gt 0 and that Rm 710 if z lt 0 What is R0 In some of the examples above the sets X and Y were the same so the relation from X to Y can be called a self relation on X we call this a relation on X77 for short Certain relations on X those which satisfy three very nice properties we7ll describe in a moment are alled equivalence relations they play a very important role in mathematics We now de ne them De nition 96 A relation N from a set X to itself is called an equivalence relation if it is re exive ie z N z for all z E X symmetric ie for all my 6 X z N y i y N z and transitive ie for all yz E X x N y y N z i z N These three conditions can be stated as follows for each x E X z is always in the ber above itself re exive for each my 6 X if z is in the ber above y then y is in the ber above z symmetric and nally for yz E X ify is in the ber above z and z is in the ber above y then 2 is in the ber above z transitive Given our philosophy of the importance of non examples let us start with two relations which are not equivalence relations NonExample 97 Let us look at the rst example of a relation we gave namely X Y R and z N y if and only if 2 y2 1 This relation fails two of the three tests needed for being an equivalence relation First it is not re exive for z E X we do not always have z N x For starters for an equivalence relation there are no empty bers why but this relation has plenty of empty bers just consider numbers of absolute value greater than 1 In fact there are just 2 real numbers x such that z w x1 What are they This relation also fails transitivity Give an example This relation is however symmetric Example 98 Let X Y Z with the divisibility relation ie My if and only if the equation y da has a unique solution d E Z Note that this is an asymmetric relation My does not imply But y and yz implies xz and Ma of course We see that this relation is re exive and transitive but not symmetric It plays a very important role in the study of the algebraic properties of the set Z NonExample 99 Now consider X Y 711 with z N y if and only if zy 2 0 We have xRx because 2 2 0 for all z E X If xy 2 0 then clearly ya 2 0 also But this relation fails the last property of transitivity for example 1 0 and 0 71 are true but 1 71 is false 3O FARSHID HAJIR Example 910 We can tweak the previous relation just a little bit and make it into an equivalence relation Namely if we take X0 710 U 01 ie X0 711 0 and de ne z N y if and only if xy 2 0 then de nes an equivalence relation on X0 Or if we keep X 711 as before but now de ne z N y to mean that either xy gt 0 or z y 0 You should check that in either of these cases we get an equivalence relation Many relations from a set X to itself that occur naturally are equivalence relations When that happens it is a signal to us that the property de ning the relation is a useful way of understanding the set For example if you consider the set of students at some elementary school and consider the relation N1 of being in the same grade then YOU CAN EASILY CONVINCE YOURSELF This is a shorthand way of saying It7s very important for you to do this exercisel that this is an equivalence relation What that means is that breaking up the students according to their grade is a meaningful and interesting way to organize the set of elementary school students Another relation NZ of being in the same class is also an equivalence relation They are not necessarily the same relation because a school might have so many students that it has three different Kindergarten classes for example Another relation might be the classify the students according to age Now let us consider the bers of an equivalence relation R on X For x E X since Rm R we write simply R1 for either of these sets This may appear an innocent de nition but the reader is hereby alreted to the fact that the bers of an equivalence relation play a tremendously important role in all of mathematics Often we annotate an equivalence relation with just a N instead of giving a name such as R to its graph so its useful to have some other kind of notation for these bers6 Consequently we make the following very important de nition De nition 911 If N is an equivalence relation on a set X with graph R E X gtlt X z N y then for each x E X the N equivalenee class of m or simply the equivalence class ofz is the ber above x namely Rwclx i yEX zwy It is the set of all elements of X equivalent to x The set of all equivalence classes ie the set X i z E X is called X modulo N and sometimes denoted by X N and called a quotient of X Note that X Q 73X since its elements are subsets of X The surjective map X 7 X de ned by z gt gt clz E is called the quotient map or the natural map from X to Example 912 Consider the set Z of all integers If a E Z we say that the parity of a is even if a 2b for some b E Z and that its parity is odd otherwise Let us write a N b whenever a and b have the same parity In other words a N b means that a and b are both odd or both even Another way to say this is that a 7 b is even Let us check that this de nes an equivalence relation on Z rst a 7 a is always 0 2 0 hence always even If a 7 b is even then b 7 a 7a 7 b is also even If a 7 b and b 7 c are even then a 7 c is even because a 7 c a 7 b b 7 c is the sum of two evens Thus parity de nes an equivalence relation on Z with two equivalence classes the odds O and the evens The quotient of Z by this equivalence relation is the set 0 16In general whenever a mathematical concept is given multiple names or multiple notations this should serve as a clear indication to the student that a concept of great import has just been encountered MATH 300 NOTES FALL 05 31 Part of the Fundamental Theorem of Equivalence Relations says the following Suppose X is a set and N is an equivalence relation on X then X is a partition ofX ie partitions the set into non overlapping non empty subsets that cover the whole set You might say it polarizes the set into non overlapping clans of equivalent elements It might help you to think of equivalent elements ie those which are related to each other by the given equivalence relation as relatives and the set of all relatives of a given element E is the clan of E a less technical term for equivalence class of E The fact that clan and class both start with cla is linguistically useful is that an accident To justify the remarks of the previous paragraph let us make some important observations about clE E where E is an arbitrary element of X relative to a xed equivalence relation on X o clE E is never empty because E E clEl Every clan has at least one member 0 For the same reason every element of X belongs to some clan HE E X then E E clE o On the other hand if E and z and two elements of X then their equivalence classes clE and clz are either identical or disjoint recall that two sets are called disjoint if their intersection is the empty set 0 In other words if Ey E X then either E i or E 7 Q The proof of this is left as an important homework exercise Now let us recall the de nition of a partition of a set De nition 913 Suppose X is a set A is another set an auxiliary or indexing set and A Xaloz E A is a collection of subsets of X We say that X0 is a partition of X with indeEing set A if 1 for all 04 E A X0 31 0 2 for all 046 6 A X0 X Q 2 UQEAXD X In other words a partition of X is a collection of non empty pairwise disjoint non overlapping subsets of X whose collective union is X the subests X0 are non overlapping and together entirely cover X Remark As you will show in one of your homework problems a collection Xaloz E A of non empty subsets of X is a partition of X with indexing set A if and only if for every E E X there exists a unique 04 E A such that E 6 X0 Remark If A Xa l 04 E A is a partition of X with indexing set A then the map A a A de ned by a gt gt X0 is a one to one correspondence from A to A Thus the point of the indexing set A is just to have a convenient way to refer to the elements of A Example 914 let X Z let A 01 let X0 bet the set of even integers and let X1 be the set of odd integers Then X0X1 is a partition of Z because every integer is either odd or even and no integer is both odd and even You may note that this partition is mandated by the parity equivalence relation we discussed earlier If we impose the parity relation on the integers and then order all the integers to band together into the corresponding clans we will have exactly two clans the evens and the odds ie X0 and X1 The partition A X0X1 is the set of clans under the parity equivalence relation Thus if X is a set and N is an equivalence relation on X then X breaks up is partitioned into non overlapping spanning equivalence classes The set of these equivalence classes ie X or X N called X modulo N is also called the partition ofX associated to N The elements of X are on the one hand subsets of X on the other hand they should be thought of as the clans which together make up X Thus ifE E X is a point in X then clE E does double duty as clE C X it is a subset of X and as E it is a point in the set 32 FARSHID HAJIR For example for Z under the parity equivalance the set Z N is the set X0 X1 consisting of two elements Note that the elements of Z N are themselves sets X0 is the set of even integers and X1 is the set of odd integers but as elements of the set Z N we just think of them as the even equivalence class77 and the the odd equivalence class77 One psychological technique is to say that the equivalence relation gloms all odds together into one object and all the evens together into another object it forgets77 or erases the distinguishing features of the integers and remembers only their parity Any single member of an equivalence class is then a representative of that class just as any member of a clan is a representative of his or her clan The main fact that one should understand about partitions also happens to be the main fact one should understand about equivalence relations namely that To specify a partition of X is the same as77 speci ying an equivalence relation on X and Vice versa The process of going back and forth between the two concepts the rst half of which we have already outlined above is as follows From an equivalence relation to a partition If X N is a set together with an equiv alence relation on it then the set X clx l p E X of the clans of X also called X N read X modulo 77 is a partition of X From a partition to an equivalence relation On the other hand if X A is a set together with a partition of it then this partition induces an equivalence relation on X via the rule z N y if and only if there exists S E A such that z E S and y E S ie if and only if z and y belong to the same piece of the partition Note that the equivalence relation we have attached to A is the unique equivalence relation under which the partition formed by the equivalence classes is just the partition we started with Likewise the reader should check that if you start with X N then pass to X A and then attach an equivalence relation to A then you get back the original N Theorem 915 The Fundamental Theorem of Equivalence Relations Suppose X is a set a If is an equivalence relation on X then the set ofN equiualence classes X X N is a partition of X b IfA is a partition of X then A induces an equivalence relation NA by the rule z N y if and only ifz E S andy E S for some S E A c IfA is a partition ofX then X NA A and ifA X then NA The point of the above theorem is that equivalence relations and partitions are two ways of looking at the same thing Sometimes it is more convenient to use the partition language and other times it is more useful to think in terms of relations It is a frequent theme in a mathematician7s experience that two objects that had been under separate study are revealed to offer different perspectives on the same underlying idea Whenever this happens the co habitation by the two seemingly di erent concepts of the same idea landscape77 serves to illuminate both concepts and to elevate the latter to a higher category of importance in the MATH 300 NOTES FALL 05 33 consciousness of the mathematician On this issue consult the wonderful book l7 by Barry Mazur one of the most distinguished not to mention eloquent mathematicians of our times 10 THE SET OF RATIONAL NUMBERS Earlier we introduced the set of rational numbers in a practical way by de ning Q E l m 6 Zn 6 Zgcdmn 1 n The problem if you want to call it that with this de nition is that as written 714 is not a rational number We have to make the added stipulation that 714 71 by putting the fraction in reduced form The problem here is to be able to forget77 the fact that the fraction 7 determine by the ordered pair of numbers 2 and 74 looks di ferent from the fraction 712 Our machinery of equivalence classes gives a neat solution to this little dilemma Namely to construct the set of rational numbers let Z0 Z 0 be the set of non zero integers We start with the set X Z gtlt Z0 On this set we de ne the equivalence relation ab E cd if and only if adibc 018 Don7t take my word for it you must actually check that this really is an equivalence relationl Then we de ne the set Q of rational numbers to be Q X N In other words a rational number is really an equivalence class of in nitely many ordered pairs of integers the second of which is non zero For instance 717271 1 n E Z0 376 2741 72712724 736 is a rational number You might object that this is a horrendously cumbersome way of dealing77 with what is after all a pretty basic object and you would be right But you cannot argue witht the fact that our construction is very rigorous and correct77 somehow If we are ever in doubt about the truth of some subtle point about rational numbers we can fall back on this very rigorous understanding On some level our mind keeps track of the fact that rational numbers can be represented in in nitely many different ways For instance in wishing to add 12 to 13 we prefer to think of these as 36 and 26 respectively What allowed us to give a de nition of Q without all this fuss was that we are able to give in each equivalence class in X a well chosen representative namely the one with positive second coordinate whose rst coordinate is least in absolute value This is a different way of saying ab where b gt 0 and gcdab 1 By the way we have a natural injection Z gt Q given by a gt gt cla 1 which you should think of as a gt gt a1 Now we will express our previous proof that Q is a countable set in a slightly different way Recall that a set S is countable if its elements can be listed with or without repetition as 51 52 In other words S is countable if and only if there exists asurjection N a S Thus if S is a countable set and N is an equivalence relation on S then S is also countable see the homework exercises Since N and Z0 are countable and since the direct product of two countable sets is countable we have N gtlt Z0 is countable hence so is Q N gtlt Z0 where this is the quotient under the equivalence relation 1 b N c d gt ad 7 b0 0 17Barry Mazur Imagining Numbers especially the square root of minus fteen FSG 2002 18Where else have you seend that expression ad 7 be beforel 34 FARSHID HAJIR Part 6 Induction 11 REMEMBRANCES OF THINGS PAST Lets take a moment to recall some material which will hopefully be familiar to you from your study of in nite series and matrices etc A nite sum 11 a2 can can be expressed compactly as 22 17 Note that it could also be written as szass1 aumass If 11 a2 is an in nite sequence of real numbers then for the in nite sum 11 a2 we write 00 71 a lim Za Z a W w j1 7391 1e the sum of the series is de ned to be the limit of the partial sums should this limit exist If it does not we say that the series diverges A product of terms 1102 an is written as 112 17 You have probably encountered the factorial notation when you studied the Taylor series of em for example for an integer n 2 0 we de ne n Hy j Note that 0 1 because by de nition 0 is an empty product an empty product should be interpreted as 1 always just as an empty sum should be interpreted as 0 A very useful fact is that n e n 0395 this rather good approximation for large n is known as Stirling s formula If A Z Z and B 6 z are two matrices with real coef cients then the product of the two matrices AB is de ned to be the matrix 7 aebg afbh ABicedg cfdh 39 Matrices represent linear transformations of a plane equipped with a basis and the matrix product de ned above represents the composite of the two linear transformations correspond ing to A and B respectively under a xed basis The determinant of the matrix A is de ned to be ad 7 be one can check directly that detAB detA detB ie the determinant map is multiplicative For a more conceptual explanation you should have attended an Undergraduate Colloquium on March 24 2005 notes on my web page might pop up one day 12 MATHEMATICAL INDUCTION One of the most powerful methods for proving certain kinds of propositions is mathemat ical induction Keep in mind that inductive reasoning is quite distinct from mathematical induction from now on I will just say induction for short Induction is based on the well ordering principle There are several di erent avors of induction we will talk about three ordinary induction complete induction and two variable induction The basic idea is as follows Imagine a typical guy Let7s call him Larry Larry is a snacker His favorite snack is Potato Chips Larry has a peculiar habit If he eats a chip from a bag then he simply must eat another chip from that bag as long as another chip exists in the bag So what can we conclude from this That if you give Larry a bag of chips and he eats a rst chip then he will completely eat the whole bag no matter how many chips are in the bag That7s it that7s Mathematical Induction Note the main engine of MATH 300 NOTES FALL 05 35 the conclusion we reached about Larry is the inductive step that each consummed chip necessarily will entail the consumption of another chip The other necessary hypothesis for Larry to eat the whole bag is of course is that he take that rst plunge and actually eat the rst chip the base case Here is another analogy Imagine you set up a bunch of dominoes in your room and you space them so closely that you know for sure that should any domino ever topple forward then its succeeding neighbor will also fall forward Then if any domino along the chain falls forward all of the succeeding ones will as well Okay now you are psychologically prepared for a more formal statement of the Principle of Mathematical lnduction Theorem 121 The Ordinary Principle of Mathematical lnduction Suppose for each integer n 2 1 Pn is a statement Assume moreover that o P1 is true and 0 Whenever Pk happens to be true for some h 2 1 then Ph 1 is also true ie Pk Pk 1 for all k 21 Then Pn is true for all n 2 1 Proof We will give a proof by contradiction Suppose it is not the cae that Pn holds for all n ie the set S n 2 1 l Pn is false is non empty By the well ordering principle S has a least element let us call it in We know that m gt 1 since P1 is true by assumption Since in is the smallest element of S we know that m 71 S By de nition of S therefore Pm 71 is true Since Ph Ph 1 for all h 2 1 we conclude that Pm is true but in E S so Pm is false This is a contradiction So S must be empty after all ie Pn holds for all n 2 1 D Remark Problem 5 on HW5 was just a different way of stating the above Principle We will now use mathematical induction to prove some formulas that we guessed using inductive reasoning but have not yet veri ed as well as some other kinds of statements Example 122 For each integer n 2 1 prove that Pn 1 2 n nn 12 This is crying out for proof by induction We rst check P1 1 1112 CHECK Now we check the induction step ie Ph Ph 1 for h 2 1 So suppose Ph holds for some h 2 1 Then 1 2 h hh 12 We have to show that this implies Ph 1 Okay lets try to calculate 1 2 k k 1 using what we have been allowed to assume namely that the sum of the rst h integers has a nifty closed form formula Okay 12kk1 12kk1 kk12 h 1 k 11 h2 k 1h 22 Hey we just showed that for h 2 1 Ph 1 follows if Ph is true That completes the induction step So by the principle of mathematical induction Pn is true for all n 2 1 Example 123 Show that if we order the odd positive integers in increasing size as usual for n 2 1 the nth one is 2n 7 1 In other words Pn if 0 is the nth odd integer then 0 27171 Let7s check the base case n 1 01 1 and 21 71 1 so it checks out okay 36 FARSHID HAJIR Now lets do the inductive step If for some k 2 1 0k 2k 71 then since OML 0k 2 we have OML 2k 7 1 2 2k 1 We might scratch our heads here a little and say Urn like are we done now77 or What the heck are we trying to do here77 The answers are Not quite dude77 and Like you have to show Pk Pk 1 dude77 respectively Lets just work backwards just a tiny bit what is Pk 1 It says that OML 2k 1 7 1 So far we have OML 2k 1 Oh but wait 2k1 2k 2 71 2k 1 71 so we got it Just to be totally clear let7s now re give the induction step We suppose that k 2 1 is some integer and that Pn happens to hold for n k then try to derive that Pn would follow for n k 1 So we assume 0k 2k 71 then compute OML 2k 712 2k1 2k2712k171soPk Pk1 Example 124 Prove that for n 2 1 the sum of the rst 71 odd positive integers is 712 So let us de ne Tn to be the sum of the rst 71 odd integers ie Tn 1 3 5 2n 71 since we gured out that 271 7 1 is the nth odd number Let7s check the base case Always do that rst In fact it pays to do just a few more cases after the base case So for n 1 Tn T1 1 and n2 12 1 so they agree We also check T2 13 22 T3 135 9 and that7s good too Okay let7s move to the heart of the matter then inductive step We must show that Pk implies Pk 1 for all k 2 1 Thus if Pk holds then Tk k2 which implies that Tk1Tk2k1k22k1k12 so Pk 1 holds just as easy as that The equality Tn n2 has now been proved for all n 2 1 by the principle of mathematical induction Example 125 Show that for n 2 5 2 gt 712 So we have Pn 2 gt 712 You mean out statement77 is not an equality its an inequality And we don7t start with n 1 Dude can we still apply induction Of course we can Dude Base Case and lnductive Step that7s what its all about Base Case n 5 25 32 gt 25 52 no sweat lnductive Step must show for k 2 5 that 2k gt k2 implies 21 1 gt k 12 So suppose for some integer k 2 5 2k gt k2 Then 2111 l 2 2k gt 2k2 Looking ahead or working backwards it sure would be nice if 2k2 would be gracious enough to dominate k 12 for k 2 5 So we boldly claim 2k2 gt k 12 for k 2 5 which solves the problem assuming we can prove our claim Now we write down 2k2 k 12 on a Blue Wall napkin and expand and bring stuff from one side to the other until we see the following argument work itself out in reverse order of how we will now present it lL9 Since k 2 5 we have k gt k 7 2 gt 1 so kk 7 2 gt1 so k2 7 2k gt1 sok2gt2k1so2k2k2k2gtk22k1so2k2gtk12 Example 126 Prove by induction that n3n13 n23 is a multiple of 9 for all n 2 1 The base case n 1 1 8 27 36 4 gtk 9 CHECK Now we must show Pk Pk 1 for all k 2 1 So we assume the lnduction Hypothesis k3 k 13 k 23 9t for some integer t We must SHOW k 13 k 23 k 33 95 for some integer s We recognize the rst two terms of this sum as the last two terms of the sum in the induction 19One problem with reading mathematics is that the little scratchwork is never kept even off in the margins the proofs are all presented neat and crisp 17m not saying this should change but if that stuff isnlt there in the text you are reading then you need to be supplying it as you readl MATH 300 NOTES FALL 05 37 hypothesis7 so we calculate k13k23k33 9tk337k3 9tk39k227k277k3 9t9k227k27 95 stk23k3 Z By the Principle of Mathematical lnduction7 we have proved that the sum of three consecutive integer cubes is divisible by 9 38 FARSHID HAJIR Part 7 Number Theory 13 A LITTLE NUMBER THEORY The set Z is really much more marvelous than you think We have already discussed its rst marvelous quality its in nitude What makes it even more marvelous are the two binary operations and gtlt What is a binary operation7 you ask Good question De nition 131 Let X be a set A binary operation on a set is a map M X gtlt X 7 X Thus7 an operation is a rule7 which7 given an ordered pair Lz of elements of a produces an element x Man of X in a well determined way An alternative notation is often more convenient7 namely if 0 stands for some kind of operational symbol7 then instead of writing La7 we write more compactly z ox An operation 0 on X is called commutative ifaob boa for all ab 6 X It is called associative if for all abc 6 X7 aoboc aoboc NonExample 132 If N is the set of natural numbers7 ordinary addition de nes a commutative operation on N However7 subtraction 7 does not de ne an operation on N because for ab 6 N7 it is not always the case that a 7 b E N Example 133 The operations gtlt7 7 on Z are familiar to you addition and multiplication are associative and commutative7 but subtraction is neither Why did I leave out 7 Well7 7 does not actually de ne an operation on Z because given ab 6 Z7 it is not always that case that a 7 b is in Z Let us de ne an operation on Z as follows given ab 6 Z7 we put a o b la2 7 bzl Then 0 is a well de ned operation on Z It is clearly commutative ls it associative Going back to what I started with7 the set Z is really marvelous because it has two com patible operations gtlt de ned on it What this means is that the two operations respect each other namely7 if abc E Z7 then a gtlt b c a gtlt b a gtlt c We say that gtlt distributes over Moreover7 these operations satisfy a whole host of other properties20 Of the two basic operations 1L7 gtlt on Z7 the more subtle of the two is multiplication How numbers are put together additively is not too mysterious each integer n decomposes additively into a sum of 71 17s it 1 1 1 As we traverse the number line7 this decomposition grows in a regular fashion7 picking up one more 1 as it goes But how numbers decompose multiplicatively is much less predictable as we traverse the number line21This comment hopefully serves to explain a little the claim that multiplication is more subtle than addition The most subtle and interesting concept then7 for the algebraic structure of Z7 is that of divisibility Divisibility is a relation on Z which is transitive and re exive but not symmetric thus it is not an equivalence relation lts importance is re ected in the multiplicity excuse the pun of names for this concept De nition 134 If n and d are integers7 we write dln if and only if the equation dx n has a unique solution x E Z The following phrases are all equivalent 0 dln o d divides ii7 ZOAS your study of algebra continues these properties will collectively come to be known as ring proper ties by the way7 algebra is the study of sets equipped with certain kinds of operations ZlFor instance7 17 is indecomposable7 18 2 3 37 19 is indecomposable20 2 2 57 21 3 7 etc MATH 300 NOTES FALL 05 39 o n is a multiple of d7 0 n is is divisible by d7 0 d is a factor of ii7 o d is a divisor of ii7 0 there exists a unique z E Z such that n dx in shorthand7 we write this as nd E Z Example 135 For any integer d E Z 07 we have le7 as the equation dx 0 has a unique solution x 0 On the other hand7 the statement Oln is false for every n E Z7 because the equation 0x n has no solutions if n 31 0 and in nitely many solutions if n 0 ln summary7 0 doesn7t divide anybody but 0 is divisible by everybody other than itself De nition 136 For any integer n 31 07 let Divn d E Z l dln be the set of divisors of n We let Divn d E Z l d gt 07dln be the set of positive divisors of n and put 0071 lDivnl Since d E Divn ldl S lnl Divn is a nite set7 and in fact7 we have the very crude bounds lDivnl 3 2n and lDivnl S n The set Z 0 is equipped with the involution multiplication by 71 This involution reduces many issues having to do with multiplicative properties of integers to essentially the same question on the set N of positive integers In other words7 for every positive divisor of ii there is exacly one negative divisor of ii7 so it suf ces to work with Divn and this is often more convenient Now7 suppose it E N Every d E Divn7 can be graphically represented by a d gtlt e grid of n de dots arranged in d rows and e columns We note that lDivnl is never empty since lln and nln7 corresponding to the 1 gtlt n and n gtlt 1 arrangements of n points Now7 for certain integers n 2 27 no other rectangular arrangement is possible these it are called primes De nition 137 A positive integer n is prime if lDivnl 2 In other words7 n is prime if and only if it has exactly two positive divisors7 namely 1 and n An integer n is called composite if lDivnl 2 3 Thus7 every integer gt 1 is either prime or composite NonExample 138 Note that 1 has but a single positive divisor hence 1 is not a prime according to our de nition It is not a composite either It is clear that it plays a very special role in multiplication7 since 1 divides every integer A number which divides every element of Z is called uriit The only units in Z are i1 The number 1 is further distinguished by its role as the identity for multiplication7 namely 1 a a for all a E Z Example 139 The primes less than 50 are 2357 77 1113171923729731737741743747 The importance of primes for arithmetic is that every integer can be decomposed into a product of primes7 and that7 up to reordering of the factors7 this prime decomposition is unique this is a very important fact7 known as The Fundamental Theorem of Arithmetic Here is an analogy In this sense7 the primes are to arithmetic what the elements77 are to chemistry we understand molecules in terms of the elements which constitute them For now7 let us show that every integer is a product of primes Theorem 1310 Ifn gt 1 is m iriteger theri n is a product of primes 4O FARSHID HAJIR Proof We will give a proof by complete mathematical induction So for n 2 2 we de ne the statement Pn as follows Pn n is a product of primes which is shorthand for the following more precise statement there exist primes p1 p and positive integerrs a1a such that n p fl pffi Note that n is a product of primes thus encompasses the possibility that n is a prime itself Let us check the validity of the base case ie 132 2 is a prime so 2 is a product of primes We will now proceed to the induction step of complete induction so we have to establish Given an arbitrary h 2 2 if Pj holds for 2 S j S k then Ph 1 holds The statement can be restated as P2 P3 Ph Ph 1 So we assume for 2 S m S k m is a product of primes and seek to show that h 1 is a product of primes If h 1 is a prime itself then it is a product of primes and we would be done The other possibility is that h 1 is not a product of primes ie h 1 is composite since h 1 gt 1 Thus there exist integers 1 lt d S e lt h 1 such that de h 1 But by the induction hypothesis since de are integers in the range 2k each of them is a product of primes hence so is h 1 de This establish We have thus established Pn for all n 2 2 by complete induction on n D Secorid Proof of Theorem 1310 Let us now give a proof by contradiction which relies on the Well ordering principle The strategy is to use the following lemma Lemma 1311 If ari iriteger m 2 2 is riot a product of primes theri there edists ari iriteger 1 lt h lt m such that h is riot a product of primes Proof Since it is not a product of primes 71 itself is not a prime Since it 2 2 Divn 2 2 and since it is not prime Divn 31 2 hence Divn gt 2 Therefore there exists d E Divn with 1 lt d lt n which implies that n de with 1 lt e lt it also Since it is not a product of primes at least one of d e must not be a product of primes since both d and e are in the range 271 7 1 this proves the existence of an integer k 1 lt h lt n such that h is not a product of primes D It should be clear how to prove the theorem using the Lemma Suppose the theorem is false Thus there exists an integer n 2 2 such that n is not a product of primes Applying the lemma to this n we get an integer 1 lt k1 lt 71 Applying the lemma to kl now we get an integer 1 lt k2 lt k1 lt n It is clear that if we repeat this procedure we obtain in nitely many integers in the range 271 7 1 which is a contradiction To be even more precise repeating this procedure it 7 1 times we obtain 1 lt hwl lt knq lt lt k2 lt k1 lt n ie we have n 7 1 distinct integers in the range 2 n 7 1 which is impossible This contradiction proves that every integer is a product of primes We can rephrase the endgame of this proof a little more ef ciently by using the well ordering principle If we assume the theorem is false ie that the set 71 2 2 n is not a product of primes is non empty then by the well ordering principle there exists a least element in 2 2 which is not the product of primes By the Lemma there exists 1 lt h lt m such that h is not a product of primes contradicting the minimality of m D MATH 300 NOTES FALL 05 41 The following theorem and proof going back at least to Euclid is a classic Theorem 1312 There are in nitely many primes Proof How do we show that a set X is in nite One way to do so would be to show that if F Q X is any non empty nite subset of X then X F is non empty So let P be the set of all primes and let F be a nite set of primes Since F is nite it has a maximal element say Z Now de ne N 1 Hpqp ie N is one more than the product of all the primes up to and including Z Since N gt 1 it is a product of primes by the previous theorem so there exists at least one prime q which divides N We claim that q F This is because qlN so Nq is an integer but for p E F Np z 11 for some integer x In other words for any p E F when N is divided by p the remainder is 1 but when N is divided by q the remainder is 0 Hence q F We have shown that for every nite subset F of P PF 31 0 hence P is in nite D Recall that for an integer n 31 0 Divn is a nite set If m is another non zero integer then Divn Divm is clearly a nite set and is non empty since it contains 1 hence it has a unique largest element which we denote by gcdmn gcdnm and of course call the greatest common divisor of m and n Apparently the greatest common factor77 is much more a la mode in schools these days In the reverse direction for an integer n we let nZ nm l m E Z h l h is divisible by n be the set of integer multiples of ii If m and n are non zero integers then It is clear that 71 mZ N is not empty since it contains Thus this set must have a least element by the Well ordering principle which we call lcmmn lcmnm the least common multiple of m and n Calculating the greatest common divisor and least common multiple of pairs of integers is an important computational task in many situtations so fortunately there is a very ef cient procedure for calculating them It is based on the Division algorithm which is simply what we usually call Long Division Theorem 1313 The Division or Euclidean Algorithm Given integers nh E N there erists a unique pair qr where q E N and r E 0 1 23 h 71 such that n qh r We call q the quotient and r Remln 7 k the remainder ofn 7 k Proof First let us prove uniqueness of the pair qr Suppose for pairs qr and q r where qq E N and rr E 0123 k71 we have n qkr q kr By switching the pairs if necessary we may assume that q 2 1 Then q 7 q k r 7 r We claim that q q and prove this by contradiction If not then q 7 q gt 0 and h 2 1 together imply that r 7 r q 7 q k 2 h which in turn implies that r 2 h since r 2 0 but r lt h by assumption giving the desired contradiction Thus q q and since r 7 r q 7 q k we get r r also This proves uniqueness of the speci ed pair qr Now let us establish the existence of this pair Since h 31 0 by assumption the set S x E N l zk S n is nite It therefore has a largest element we put q maxS for this maximal element and let r n 7 qh It remains toshowthat0 Sr 3 71 Sincqu Sqk gnsorn7qk 2 0 Toshowthatr 3 71 let us use proof by contradiction If r 2 k then nqhrqhhr7kq1kr7k which since r 7 h 2 0 would show that q 1 E S contradicting the fact that q max S Thus0 r k71 D 42 FARSHID HAJIR The division algorithm can be used to calculate the greatest common divisor of two given positive integers ef ciently Let us examine the key idea Given 711712 2 1 we rearrange them if necessary to have n1 2 n2 lf n1 n2 then we rejoice because then gcdn1 n2 n2 without any further ado The strategy is to replace the pair 711712 by a smaller pair 712713 with the same gcdl So where do we get 713 from Easy we take 713 to be the remainder when n1 is divided by n2 Thus we need to prove a little lemma Lemma 1314 Ifn 2 h 21 and n qh r with q E N then gcdn k gcdkr Proof Recall that gcdnk is by de nition the largest element of Divn Divh thus it suf ces to prove that Divn Divh Divh Divr To prove the above equality of sets we well show that each set is contained in the other So suppose dln and dlk Then dlqh so dln 7 qk ie dlr So now dlh and dlr showing that Divn Divh Q Divk Divr On the other hand if dlr and dlk then dlqh so dlqhr ie dln showing the reverse inclusion This completes the proof of the lemma D The strategy for computing gcdn1n2 should now be clear Let n3 RemlnjL 7 n2 and indeed for each i 2 3 successively de ne n Remlniq 7 ill1 Then n2 gt 713 gt gives a strictly decreasing sequence of remainders which are automatically non negativel ie n2 gt 713 gt 2 0 thus this sequence must eventually hit 0 Let s 2 2 be the least integer such that nS 0 Thus we have ngn17 712 ngU LZ 713 39 39 39 ngns727ns71 ngns71707 71971 7 0 Since 7151 31 0 gcdns10 7151 Another perspective is that since nS Remns2 7 7151 0 we have n51ln52 and hence gcdn52ns1 7151 Either way we nd gcdn1n2 7151 is the penultimate remainder just before getting remainder 0 Example 1315 Let us use the above algorithm to compute gcd43260 So n1 432 n2 60 We get 432 76012 so 713 12 and 60 512 so 714 0 Thus gcd432 60 n3 12 Lets do one more What is gcd89557 Letting n1 89 n2 55 we have 713 34714 21 n5 13 n6 8717 5 n6 3 n7 2 n8 1 n9 0 Phew gcd8955 n8 1 De nition 1316 If m n are integers we say that m and n are coprime or relatively prime to each other if gcdmn 1 Theorem 1317 Bezout7s Theorem Suppose ab are integers and d gcdab Then there eccist integers Ly such that ap by d In particular ifa and b are relatively prime then some integer linear combination of a and b is 1 Indeed for m E Z the equation aX bY m is solvable with XY E Z if and only ifdlm Sketch of Proof The integers Ly can in fact be found via the repeated application of the Euclidean algorithm we described for computing gcda b Recall that we put n1 maXa b n2 minab and de ne recursively nj1 to be the remainder of 7771 divided by 71 for j 2 2 viz 7771 anj iii1 Then gcdab 7151 where nS 0 with 5 minimal for this property Erom 7153 157271572 7151 we climb one level higher to 7151 7153 7 1547154 7153 7 q52n54 7 n53q53 and so on until we obtain an expression 7151 znl yng for some integers Ly Once we have my 6 Z with aa by d where MATH 300 NOTES FALL 05 43 d gcdab then for any multiple m of d say m kd we have aX 191 m for X kx and Y ky On the other hand suppose aX 191 m with integers XY We want to show that then m is a multiple of d so let us divide and see we have m qdr for integers 1 where 0 S r lt d By multiplying ax by d by q we nd azq byq m 7 r We subtract this from aX 191 m to nd aX 7 zq MY yq 7quot Since dla and dlb we conclude that dlr which when combined with the inequality 0 S d lt 7 gives 7 0 ie dlm as desired Remark We should note the following important interpretation of the theorem The set of Z linear combinations of a and b is exactly the set of Z multiples of their greatest common divisor ie we have an equality of sets aX7bY l XY Zkd l kEZ Even more brie y one can write 1 19 dZ where d gcda b Later when you study rings in Math 412 you will come to interpret this statement as The ideal generated by a and b is principal generated by gcdab77 Example 1318 Determine gcd200126 and express it as a linear combination of these integers We write 200 12674 71374 126 7452 n452 74 5222 n522 52 2228 7168 22 2 8 6 n7 6 8 6 2 n8 2 6 32 7190 Thus n8 2 gcd200126 Reversing the steps we have 2 876 8722728 72238 7223527222 3527722 3527774752 77741052 77 74 10126 7 74 1012671774 10126 717200 7126 27 126 717200 There is a nice method advocated by WA Blankinship Amer Math Monthly 1963 for keeping track of the straightforward but somewhat messy book keeping of the above algorithm It produces gcdn1n2 and the Bezout numbers77 Ly such that 711 yng gcdn1n2 all in one shot Namely to nd gcdn1n2 we write them in a column next to 44 FARSHID HAJIR the 2 gtlt 2 identity matrix then we do the usual operations for nding 713714 but apply each operation to the whole row We stop when we reach a row that begins with 0 The penultimate row will then be dzy where d gcdn1n2 and d 711 yngl Instead of giving a formal algorithm and proving that it does what we say we will be satis ed with reworking the above example with Blankinship as our guide Example 1319 To nd gcd200126 we follow the same steps as before but carry the algebra to the entire row each time 200 1 0 126 0 1 74 1 71 52 71 2 22 2 73 8 75 8 6 12 719 2 717 27 0 63 7100 We read off that 717 200 27 126 2 We also can read off 6 12 200 719126 etc in case we wanted to Note that 0 63200 7100126 in other words the sixty third multiple of 200 is also the hundredth multiple of 126 and so this number 63200 100 126 12600 is a common multiple of 200 and 126 Are you thinking what l7m thinking This must be the least common multiple of 200 and 126 Yes that is true Remark If you are familiar with row operations on matrices you will note that the sequence of moves in the Blankinship algorithm is nothing more than that I leave it as a challenge to the interested reader to investigate and prove if true whether the last row of the Blankinship algorithm will always display 0 r s where lrnll lsngl lcmn1n2 The Bezout theorem has a bunch of important and useful consequences Theorem 1320 pr is a prime arid plab where ab E Z theripla or plb Proof Let us write ab pk for some h E Z If a and b are both divisible by p then we are done So let us assume one of them is not divisible by p say h Then by Bezout7s theorem there exist my 6 Z such that bx py 1 Multiplying this last equation by b we nd abz apy a or pk ay a so pla D Corollary 1321 Ifn 2 1 arid m1 mn E Z are n iritegers whose product is divisibe by p theri at least one of these iritegers is divisible by p ie plml mn implies that theri there epists 1 Sj S n such thatplmj Proof The proof is by induction on n and is left as an exercise D Corollary 1322 For abc E Z if albc arid gcdab 1 theri ale Proof We use Bezout to write ax by 1 with my 6 Z We multiply this by c to get axe boy c then note that alapc and albcy so alapc boy c D Another consequence of the Bezout theorem is the following Let7s give it a fanciful name in the hope that you will remember its statement It will be extremely useful to you when you study group theory MATH 300 NOTES FALL 05 45 Theorem 1323 The Supremacy of gcd and lcm Suppose ab E Z Every common multiple ofa and b is a multiple of their least common multiple lcmab and every common divisor ofa and b is a divisor of their greatest common divisor gcda b In other words alcblc gt lcmablc dladlb gt dlgcdab Proof Let Z lcma b and g gcdab First let7s show that alcblc llc We may write c as and c bt for integers st We want to show that c divided by l gives remainder 0 so lets divide and see We have c lq r for some integer q and some r satisfying 0 S r lt Z We have c at lqr so r ate lq Since l is a multiple of a we then have alr Similarly c bu lq r so r bu 7 lg is a multiple of b Thus r is a common multiple of a and b But 0 S r lt l and l is the least positive common multiple of a and b so r cannot be positive Thus r 0 ie l divides c Now lets show that dladlb dlg We may write a de and b df with ef E Z by assumption and g ax by for my 6 Z by Bezout Assembling all of this together we get 9 dex dfy dex fy hence dlg D Now let us state and prove the Fundamental Theorem of Arithmetic It says that except for the way the prime factors are ordered how a number breaks up into prime factors is unique Theorem 1324 The Fundamental Theorem of Arithmetic Ifn E N then there is a unique function en P a Z20 from the set of all primes P to the set of non negative integers such that n H 1357007 pEP The function en vanishes on all but nitely many primes Proof We have already shown in Theorem 1310 that every integer gt 1 is a product of primes and 1 is an empty product of primes ie the function e0 is just the function that takes the value 0 at every prime To show uniqueness let us proceed by contradiction hoping to use the well ordering principle once again So we suppose that there exist positive integers n gt 1 that admit at least two distinct factorizations By the well ordering principle there exists a least such integer let us call it in Thus there exist two factorizations m 10110239 Pr qquqs where the phqj are all primes not necessarily distinct ordered so that pl 3 pg 3 S p and Q1 3 qz S S qs By assumption the lists p1 p 11qS are not identical We can assume without loss of generality22 that pl 3 Q1 By Corollary 1321 pllqi for some 1 S i S 5 Since q and p1 are both primes we then have p1 1 307101 S Q1 S Qi p1 so 191 Q1 Letting 771 7711017 We have m p2pr qzqs Now these two factorizations must be distinct since the two distinct factorizations of m are gotten by including the equal prime factors p1 and Q1 at the beginning of each one Thus 0 lt m lt m and 771 has two distinct factorizations contradicting the fact that m is the 22This oftquoted phrase warns the reader that the author is about to make an assumption but that this assumption is not central to the validity of the proof Without the assumption a simple and obvious modification or repetition of the argument can be made to account for all possible cases For instance in this case if it happens that ql S p1 then we simply repeat the argument replacing all the 4 s by pls and Vice versai 46 FARSHID HAJIR least positive integer admitting two distinct factorizations This contradiction completes the proof To compute lcmm7 n7 one can compute gcdmn and then use part c of the following fact Theorem 1325 Suppose mm 2 1 and m Hpmmy n Hpmp PEP pEP Then a gcdmn Hpn nemp equotp pEP b lcmmn Hpm5mp equotp pEP e Ifmm 21 thehlcmmngcdmn mn Proof We leave the proof to the interested reader D 14 SOME MORE NUMBER THEORY One of the biggest mysteries in number theory is the following problem Major Problem Explain the distribution of prime numbers on the number line If we list the primes in order7 then it becomes apparent fairly quickly that they start to thin out77 In other words7 if you take an interval of length N for a large but xed N7 then look at N consecutive positive integers7 starting with a 17 then the chances that this interval a La N contains a prime goes to zero as 1 goes to in nity Here is a movie77 of this phenomenon If you take a window of xed width and shift it to the right7 the chances that you catch a prime for any given frame goes to zero as you shift to the right In a sense7 you should expect that the primes are outmuscled77 by the composites7 because everytime you have a bunch of primes7 you can combine them in many ways in order to make composites7 but there is only one way to make a prime ln particular7 in one of the homework problems7 you will show that no matter how large N is7 as you shift to the right7 you are bound to hit a frame with no primes in it Here is another way in which composites outmuscle77 the primes Example 141 A sequence 0 1 2 in Z is called arithmetic if there exists an integer 1 called the addeth such that xn 7 xn a for all n 2 1 Equivalently7 xn 0 no Show that any arithmetic sequence in Z with non zero addend contains in nitely many composites Here is a proof Suppose mango is an arithmetic sequence with addend a If all the xn are composite7 we are certainly done If not7 let p x0 ma be prime for some m 2 0 We claim that if n m hp7 where h 2 17 then xn is composite Once we prove the claim7 we are done7 of course To prove the claim7 note rst that xn is divisible by p because xnz0anz0amkpx0amahppakpp1ah MATH 300 NOTES FALL 05 47 Note that xn p1 ah gt p for h 2 1 hence xn is divisible by p and greater than p hence it is composite proving the claim On the other hand primes are persistent in some ways For instance as we proved there are in nitely many of them A much more subtle and powerful theorem rst formulated by Lagrange and nally proved by Peter Gustav Lejeune Dirichlet in 1837 says that in any arithmetic progression that has the potential of having in nitely many primes does have in nitely many primes Theorem 142 Dirichlet7s Theorem on Primes in Arithmetic Progressions If x0a E N and gcda x0 1 then the arithmetic sequence zone a 0 2a po an contains in nitely many primes Note that the assumption gcdx0a 1 is needed because otherwise all the elements in the sequence are divisible by d gt 1 where d gcdz0a Dirichlet7s ideas for proving this theorem consitute the foundations of an entire branch of modern mathematics known as analytic number theory Another prime persistence theorem due to Chebyshev is known as Bertrand7s Pos tulate It says that for n 2 1 the interval 71271 contains at least one prime Here is an unsolved problem Question 143 ls it true that for all large enough n say n 2 117 the interval 71 n contains a prime It is believed that the answer is yes but no proof or counterexample is known at present A spectacular and recent prime persistence theorem is the following Theorem 144 Peter Green and Terence Tao 2004 Given N 2 1 there epists integers x0a E N such that 0 awe 2a zo Na are all primes In other words there are arbitrarily long arithmetic progressions of primes See httparxivorgabsmathNTO404188 for their paper You may not understand much but you7ll get a glimpse of what a mathematical preprint an article in pre published form looks like One of the most exciting aspects of their proof is that it uses techniques of ergodic theory a branch of analysis calculus The fact that the study of smooth functions R a R should say anything about arithmetic properties of whole numbers might be surprising at rst but this tradition actually goes way back to Leonhard Euler at least who gave a proof of the in nitude of primes based on the fact that the harmonic series 1 1 1 5 g divergesl Euler7s observation led Georg Bernhard Riemann to the study of the function 1 1 1 1 i i Cz 213m nm which Euler had introduced but which we now call the Riemann Zeta Function Riemann observed that the analytic properties of this function reveal some deep arithmetic facts about the distribution of primes on the number line The connection between them is sealed by the Euler Product Formula 48 FARSHID HAJIR which in turn holds because of the Fundamental Theorem of Arithmetic ln 18597 Riemann outlined a program7 completed by de la Valle e Poussin and Hadamard independently in 18967 for proving a conjecture of Gauss which we now call the Prime Number Theorem To state it7 let us de ne the Prime Counting Function 7Tx Hp E P l p S which counts the number of primes in the interval 17 Up close7 this function is quite choppy7 as it jumps by 1 everytime it encounters a prime But if you look at its graph on a very large interval7 it looks remarkably smooth So the question is ls there a nice simple continuous function whose graph approaches the graph of 7Tx as x tends to in nity The answer is Yes and one function which ts the bill is z ln Theorem 145 The Prime Number Theorem We have hm mace z ln The theorem says that HQ and zlnx are about the same size For example7 in 19597 Derrick Lehmer my mathematical grandfather calculated on his super duper computer that M1010 455052511ie is about 455 million Let us compare that to 1010ln1010 434294482 or about 434 million I wonder whether you are impressed by this or not On the one hand7 we are off by about 21 million primes On the other hand7 calculating 1010 ln1010 takes just a second whereas counting how many primes there are up to 10L0 is serious business In retrospect7 21 million primes out of 455 million is only about a 45 error Not too bad at all Nonetheless7 one would like to understand how much the error Ms 7 slnz is7 or at least put a cap on this error Riemann7s method does give us a bound on this error7 but the bound is MUCH bigger than the actual errors we observe Riemann has an explanation for that too He thinks it is highly likely that the roots of his function not just for z in R for complex numbers m all lie on a certain line To nd out whether this is true or not is one of the hottest problems in Mathematics It is known as The Riemann Hypothesis7 the subject of various recent popular books MATH 300 NOTES FALL 05 49 Part 8 Counting and Uncountability 15 THE CLASSIFICATION OF SETS ACCORDING TO SIZE Let us begin by reviewing some facts about nite sets Two main facts are as follows Lemma 151 Main Lemma of Finite Sets Suppose f X gt Y is an lnjeetlue map of sets Then a Ifz17zn is a non repeating sequence of length n 2 1 in X then fz17 7fzn is a non repeating sequence of length n in Y b IfY is nite then so is X and IX 3 Theorem 152 Main Theorem of Finite Sets Suppose X and Y are nite sets Then X N Y lfand only lle Proof IfX Y7 then there exists a bijective map f X a Y Since f is injective7 IX 3 lY by the Main Lemma of Finite Sets Since f is bijective7 we also have f l Y a X which is bijective hence injective7 so we also get lY S Since IX 3 lY S le we must have IX The other direction is also easy7 it is left as a homework problem A set X is in nite if and only if there exists an injective map f N gt X For7 if such a map exists7 then f17 f27 f37 is a non repeating in nite sequence in X7 and in the other direction7 if zlz2 is an in nite non repeating sequence in X7 then by putting fn zn for n 2 17 we see immediately that f gives an injection N gt X How should we measure the size of in nite sets Our rst thought might be as it was for a period lasting at least 4000 years that all in nite sets are of the same size It was only in the 19th century that Georg Cantor cured us of this nai39vete singlehandedly Here is an analogy Suppose in all your life7 you have never seen or heard of a car The fastest method of travel you know about is riding a horse Then one day you discover cars In the beginning of your discovery7 you will not be able to tell the difference between a Yugo and a Ferrari To you7 these new machine horses are so extraordinarily fast and superior to your prior experiences that the relative di ferences between them are irrelevant But after driving in a Yugo for a while7 then moving on to a Chevrolet and a Mercedes and a Ferrari7 you come to distinguish and understand the di ferences between them Then one day you see a Cessna plane cruising down a runway and you think well7 here is another machine horse7 and then you see it take off and y7 and you realize Whoa Now that thing belongs to a whole higher class of machine horses by itself So it was for our mathematical understanding of in nity At rst7 you are familiar with nite sets You realize early on that some nite sets are alike they have the same size and are in that sense equivalent Then one ne day7 you realize Hey there is NO largest counting number ie Whoa the set of counting numbers which 7classify7 nite sets is not a nite set itself In other words7 you have just discovered the existence of in nite sets This is such a monumental discovery7 in nity is such a remote concept7 that to you just assume that all in nite sets are of the same size This relative homogeneity of in nite sets is expressed in your language you have a name for sets of size 17 size 27 size 37 etc but you have only one name for sets which are not nite in nite reinforcing the notion that all in nites sets are of the same size Let us look more closely to see whether all in nite sets really are of the same size Well7 what does it mean for two sets to be of the same size For nite sets7 it means that there 50 FARSHID HAJIR is a one to one correspondence between the two sets we can line up the elements of one set against the elements of the other set in an exact match up Cantor had the important insight that this de nition should be used for in nite sets as well Recall that we write X N Y if there is a bijection X a Y De nition 153 For any pair of arbitrary sets X and Y we say that X and Y have the same size and write le lYl if and only if X N Y Having accepted this de nition we now must dare ask with Cantor a fundamental ques tion Let7s imagine a conversation Cantor could have had with a ctitious colleague and a very old friend who has just come for a visit from out of town let us call him Professor Groeg Rotnac as they stroll along on Ulmestrasse one summer evening in the early 1870s PROFESSORS CANTOR AND ROTNAC TAKE A WALK Prof Romac What work is occupying you these days esteemed colleague Prof Cantor l have been fascinated and considerably puzzled by a fundamental question which on the surface appears quite simple but whose complexities in my opinion run very deep This question has been troubling me for years and only recently have I been able to make any progress Given the simplicity of the question I hesitate to mention it even to such a dear and old friend as yourself Prof Romac Come now we have known each other practically from infanthoodl We have no need of reticencel Please I am curious I will treat your question with respect Prof Cantor Very well I would expect no less from you You would agree that two sets be they nite or in nite should be said to be of the same size if there is a one to one correspondence ie a bijection between them Prof Romac On that we are in complete agreement You might say on that there is a correspondence between our thoughts Ha Ha Ha Prof Cantor Yes that is very witty of you Very good Now here is my innocent sounding question If XY are two in nite sets are they necessarily of the same size In other words if XY are in nite sets then is there necessarily a bijection from X to Y Prof Romac MIT VERLAUB with all due respect I believe you are teasing me Prof Cantor Need I remind you that you promised you would take my question at face value Here is my question again please treat it seriously If X and Y are in nite sets can one always nd a bijection from X to Y Prof Romac JAWOHL NATURLICH of course one can my dear Georg DAS IST EIN KINDERSPIEL It is child7s play not worthy of a Herr Doctor Professor of your standingl Prof Cantor lndulge me and present your KINDER proof bitte Prof Ramos Very well list the elments of X and Y as zlz2zg and y1y2y3 respectively Then map z to y for each 239 2 1 Prof Cantor Your proof rests on the notion that if X is any in nite set then one can simply list all its elements in a single in nite list ie that there is a bijection from the 397 MATH 300 NOTES FALL 05 51 natural numbers N23 to X Then since there is a bijection from X to N and another from N to Y composing them one gets a bijection from X to Y ls that about it Prof Ramos You have expressed my thoughts perfectly as you always do Prof Cantor Yes but this brings us to the crux of the matter I nd your claim that one can always list all the elements of an arbitrary in nite set in a single in nite list LASTIG troubling at best indeed downright false as we shall hopefully see in a moment Pray discuss how you would justify your claim that if X is any in nite set then its elements can be listed in one in nite list Prof Romac Well simply choose one element at random call it zl then a different one call it 2 then an 33 different form 1 and x2 and so on Since the set is in nite one will never run out of elements to choose and one will eventually list every single element Prof Cantor I am afraid that will not work Prof Romac Of course it will Prof Cantor NEIN Prof Romac I see that you are quite sure of yourself Very well why not pray Prof Cantor The trouble with your procedure is your claim that that one will eventually list every single element77 Let me illustrate with a very simple example Suppose we attempt to use your procedure to list all the elements of the set N You said I can choose the elements as I please Suppose I happen to choose 2 then 4 then 6 then 8 and so on always skipping the odd numbers In this way I will never stop and will never list all the elements since I miss every odd number Prof Romac Very well the procedure does not work if you apply it in a deliberately obtuse manner but surely there must be a way of listing the elements correctly so that none gets left out I grudgingly admit that l have not yet given you a correct procedure that will always list all the elements of a given in nite list but I do not give up on the claim that such a procedure exists For instance of course one can list all the elements of N simply ask a child to do it and she will do it in the right order Prof Cantor For the set N yes of course but recall that we are asking if the elements of an arbitrary in nite set X can always be given in one in nite list let us call that simply listing the elements77 and a set for which we can list the elements in one in nite list I will call listable So far I was simply showing you that your procedure is not guaranteed to work Let us continue our investigation for various in nite sets and attempt to nd the means of listing the elements which you so adamantly maintain must exist Prof Romac Very well how about Herr Dr Professor Kronecker7s favored set Z Prof Cantor With barely disguised disgust BITTE do not speak of that distinguished yet pompous gentleman Prof Romac Please forgive me I did not know that mentioning his name would upset you so But do let us take up the case of the set of all integers Z positive negative and 0 This is a good test case to start with because it is usually thought of as a two sided in nite list and you would like a one sided in nite list Hmm just a moment I have it We start at 0 then go to 1 then circle around to 71 then circle around to 2 then circle around to 72 and so on getting 0 1 71 2 72 3 73 4 74 Every element is now listed in one in nite list 23For the sake of convenience we allow several anachronisms such as the use of words like bijection in this discourse Another anachronism is the nuse of N to stand for the set of natural numbers The notation N Z Q R and so on was not standardized until many years later when Bourbaki came along 52 FARSHID HAJIR Prof Cantor Excellent work MEINE FREUNDI You have discovered a method I call interleaving7 Here is what I mean Given two sets X and Y which are listable say as 12 and y1y2 then X U Y is also listable by interleaving the two sets as follows x1y1x2y2x3y3 just as you interleaved the positives and negatives Moreover suppose given a nite collection of sets X1 X2 Xn each of which is listable then you can imagine Prof Rotnac Tut tut just a moment I know what you are about to say by listing the rst element of the rst the rst element of the second etc up the the rst element of the last set then going to the second element of the rst set and so on this shows that X1 U U Xn is listablel Prof Cantor Sharp as the axe of the rnightiest lurnberjack of the Black Forest is your mind Herr Dr Professor Prof Rotnac Very funny Well that takes care of quite a few in nite sets alreadyl Prof Cantor Yes you can well imagine the next step what if one has an in nite list of listable sets is their union listable Again there is a simple way to show that this is so I should say its simple after one sees how to do it but I can confess to my esteerned colleage because he is also an intimate friend that it took me many months to come up with this answerl Narnely let us write 11 12 13 for the rst list then 21 22 23 for the second list and so on So that xi is the jth element in the 2th list Do you see the lists in your minds eye Prof Rotnac Yes yes you have put them there beautifully I see them as a 2 dirnensional grid with the rst list at the bottom going off to the right the second list just above it and so on Prof Cantor You atter me but its true that you imagine them just as I do Well now let us say that the element xi has weight j The lightest elernent so to speak is 11 and it has weight 2 the next two lightest are 12 and 21 of weight 3 then next three lightest are of weight 4 they are zglz22x13 The next four lightest are of weight 5 they are x14233241 And then Prof Romac lCH HABE DEIN SPIEL DURCHSCHAUT I can see your game You list the elements by increasing weight and since there are only nitely elements of each weight you simply order those nitely many elements however you please as you go along In fact I think you have been Zigzagging thernl Prof Cantor Exactly l have always admired your quick uptake of ideas Prof Rotnac Well as I said before it appears you are well on your way to proving that every in nite set is listablel Prof Cantor That is what I thought as well Notably with the ltering by weight77 idea I have just described one sees that the set of rational numbers Q is listable But alas my success stalled there for quite some time for l have been utterly unsuccessful in listing all the elements of the set of real numbers R So much so that I now believe that this set is not listablel Prof Romca Now now do not be hasty I understand why you are discouraged but do not give up hope No one has yet found the holy grail but that does not prove that it does not exist Patience I am sure your fertile mind will soon devise a method for listing all the real numbers as well After all each real number can be expressed as in nite list of nitely many digits Will not some re nement of your Zigzagging on diagonals provide the answer MATH 300 NOTES FALL 05 53 Prof Cantor Ah7 l have indeed come to the conclusion that it does provide the answer7 but the answer is NOT the one that you expect my dear colleague Prof Romac You mean to say that you have found a proof that the real numbers are not listable Prof Cantor Precisely Prof Romac Unbelieving7 but excited all the same Corne now7 be serious How can such a monstrous thing be true You have piqued my curiosity I am sure you are rnistaken7 however Corne7 let us have your so called proof7 and if it is not overly elaborate7 within minutes we will have found a shortcorning in your argument or my name is not Groeg Rotnac Prof Cantor Very well7 I must admit I would be relieved to nd an error in the argurnent7 which is indeed quite short7 but I am afraid there is none In fact we will prove that the set of real numbers bounded by 0 and 17 the so called unit interval7 already has so many elements that they cannot all be given in one in nite list We will proceed by Widerspruch7 contradiction So7 suppose you offer me a list 172737 of real numbers between 0 and 1 and claim that all real numbers between 0 and 1 gure among your list I will now show you that7 with all due respect7 you cannot have done so Narnely7 I will produce a real number between 0 and 1 which cannot be on your list You see what I wish to do Prof Rotnac Yes7 I see what you wish to do7 but cannot see how you will possibly achieve it Prof Cantor Neither could I for a long time You will agree7 readily7 l believe7 that by de nition7 each real number larger than 0 but smaller than 1 can be represented in a unique way with an in nite decirnal expansion 010203 where the digits cl belong to the set 0172374576777879 Let us say we write the rst number on your list as 1 0a11a12a13 the second number on your list as 2 0a21a22a23 so that the jth digit of the 2th number on the list is aij Here of course the digits aij belong to the set 0172374576777879 Are you with me Prof Romac Yes7 I am Go on7 please Prof Cantor Recall that my goal is to show you that some number in the unit interval must have been left out of the list Here is how to do it I will construct such a number y b1b2b3 by making sure that y differs from each number in the list for at least one digit ln fact7 I will choose it one digit at a time so that for each j 2 17 bj is different from 177 For instance7 if an is not 57 I will choose b1 to be 57 whereas if an is 5 then I will choose b1 to be some other digit7 say 6 for the sake of de niteness lf 122 is not 57 I will choose b2 to be 5 and otherwise I will choose it to be 6 And so on Thus7 y cannot be 1 because they differ in the rst digit7 and y cannot be 2 because they differ in the second digit and so on For anyj 2 17 y cannot be sj because their jth digits do not match Thus7 y which will be some real number in the interval 05555 7 06666 59769l does not appear on the list 1727 no matter how this list was constructed This proves that the real numbers bounded by 0 and 1 are already too numerous to be put into one single list Prof Rotnac I am stunnedl You have just shown that the set of real numbers is more in nite sornehow than the set of natural numbers You have opened my mind to a universe whose existence I did not even suspectl ln nite sets come in different sizes ln nite sets come in different sizes Prof Cantor You believe the proof then Prof Romac Indeed I do You are travelling down the diagonal modifying the digits as you go along This diagonal argument77 of yours is sirnplicity itself I congratulate you 54 FARSHID HAJIR Have you found any other sets that are not listable Have you found sets that are even bigger than the set of real numbers Prof Cantor Actually yes to both questions Let 73N be the set of all subset of N If you begin to list its elements you will see that they are quite numerous Other than the empty set and the complete set N itself there is one in nite list of subsets of size 1 a 2 dimensinonal in nite grid of subsets of size 2 a 3 dimensional in nite grid of subsets of size 3 and so on I have found a rather roundabout way of showing that 73N is not listable on the one hand and also of showing that 73N is of the same size as the set of real numbers on the other Let me rst explain why 73N is not listable the term I prefer incidentally is countable77 in which category I also include the nite sets So here is why 73N is not countable lf if were then there would be a bijection which is in particular a surjection form N to 73N But I claim that for any set X and any map f X a 73X f is not surjective Prof Romac Let me see now you are saying that if f X a 73X is any map then there is some subset Y of X such that Y 31 fz for all z E X Prof Cantor Admirably put yes Here is a set Y which is always missed by f so to speak Consider the subset Yf of X which consists of those elements z E X such that z does not belong to Prof Romac That is confusing Let me see to each x in X we have an associated subset fz of X and you are saying that you admit z to the set Yf if and only if z itself does not belong to the subset fz associated to it by f Yes I see your de nition of Yf is rather bizarre but gives a pefectly valid subset of X Prof Cantor Very good Now I claim that Yf is not in the image of f ie is not of the form fy with y E X Why you ask Recall that for any given z E X z belongs to Yf if and only if z does not belong to Recall that y belongs to Yf if and only if y does not belong to So if we had fy Yf then this last statement would become y belongs to Yf if and only if y does not belong to Yff7 This is absurd Thus for all y E X fy 31 Yf and so f is not surjective Prof Romac Just when I think you have ceased surprising me you astound me with an even more devious proof That is brilliant Moreover with this new proof not only do you have two in nite sets of different size but you can make as many in nite sets of different size as you want Prof Cantor I can How can I Prof Romac Well say you start with N then 73N is more numerous then 7373N is more numerous still 737373N is more numerous still and so on Prof Cantor Yes of course that is truly marvelousl Thank you my friend for that wonderful observation Prof Romac You had already thought of that yourself hadn7t you Prof Cantor To be truthful yes but after much thinking Whereas you made the leap immediately and I wanted to share in the excitement of your discovery Prof Romac One thing puzzles me still How does 73N compare with the set of real numbers Which one is bigger Prof Cantor Actually they are both of the same size Prof Romac ls that so Ah yes you already said that they were But I don7t see why MATH 300 NOTES FALL 05 55 Prof Cantor Well rst of all there is a natural one to one correspondence between 73N and MapsN01 that is to say the set of all maps from N to the binary set 0 1 Here is how to Prof Romac Just a moment forgive me for interrupting but I beg you do not tell me I want to gure this out on my own Lets see now You are saying that to give a subset of N is the same as giving a map from N to 01 eh to give a subset X of N means to admit certain natural numbers to X and exclude others And to give a map from N to 01 means that certain natural numbers will be assigned the number 1 and others will be assigned the number 0 l have got it Being assigned a 177 can mean admit to X and being assigned a 077 means you are to be excluded from X To be perfectly formal here is a bijective map F 73N a MapsN01 If X Q N we have to describe a map FX E MapsN01 We de ne FX N a 01 by putting 1 if n E X and FX 0 if n Z X The map F is bijective because for example it has an inverse G MapsN01 de ned in a simple way Given a map f N a 01 we let Gf n E N fn 1 Then FGf is clearly the map f and GFX is just the set X Prof Cantor Masterfully done I am sure So as l was saying 73N is in one to one correspondence with MapsN01 and the set of maps from N to 0 1 is in one to one correspondence with the interval 01 Prof Romac There you go confusing me again just fresh from my triumph Give me a moment to thinkYou have a string of 07s and 17s and you wish to assign to it a number between 0 and 1 in such a way that every real number is covered once If you had a string of digits between 0 and 9 then I would just say write out the decimal expansion and that would do the trick but you are giving me only 07s and 17s Prof Cantor Pray remind me what is the decimal expansion Prof Romac I assume you are playing dumb for my bene t Very well I will play along If 11 a2a3 is a sequence of digits from the set 0 1 9 then we get a corresponding decimal expansion 0a1a2a3 which is de ned to be the real number 1110 12100 131000 and this converges to a number in the interval 01 Every number in 01 can be represented as a decimal expansion in exactly one way with 0 0000000 and 1 099999 Prof Cantor Excellent You are nearly there meine Kollege I am only giving you two symbols instead of ten so instead of representing numbers in base ten decimal expansion you should represent them Prof Romac ln Base Two natiirlichl That7s it Allow me describe it in complete detail There is a bijective map 04 from MapsN01 to 01 de ned as follows Given a map f N a 01 we associate a number 04f 6 01 to it by putting 04f f12 f24 f38 fn2 This series converges to a number in 01 Note that the smallest possible 04f occurs for the function f0 with constant value 0 giving 0 0 and the greatest possible value occurs for the function f1 with constant value 1 giving afl 1214 1 To show that every real number in between 0 and 1 is in the image of oz ie has a binary expansion we must construct a map 6 01 a MapsN0 which just gives the binary instead of the decimal expansion of a real number Namely if z 6 01 we de ne a map 61 N a 0 1 as follows We know that 0 S x S 1 so we try to determine which half of this range contains x Namely if z lt 12 we put 1 0 and if z 2 12 we put 1 1 Now we have 0 S x 7 x12 S 12 so we ask which half of this interval z 7 x12 belongs to ie 56 FARSHID HAJIR if z 7 z12 lt 14 we put zg 0 otherwise we put zg 1 Then if z 7 z12 7 z24 lt 18 we put zg 0 otherwise zg 1 In general having found z for 1 S i S n we de ne zn by putting zn 0 if z 7 z12 7 z24 7 7 zn2 lt12 1 and zn 1 otherwise It is easy to see that z 7 z12 7 z24 7 7 zn2 12 and 12 goes to 0 of course as n becomes large hence the series z12 z24 converges to x by construction If we de ne f N 7 01 by Mn 7 then x f12 f24 f38 fn2 so that with 6z fw we have 6 is the inverse of oz and so 04 is bijective Prof Cantor Dotting the is and crossing the t7s perfectly as usual So now we see that 73N is in one to one correspondence with the closed interval 01 of real numbers Now that we have seen in nite sets come in different sizes I have begun to give names to sizes which in nite sets can take I call these sizes cardinal numbers77 or cardinalities7 Sets which are in one to one correspondence with N I call of size N0 Those which are in one to one correspondence with 73N I call of size N1 Those which are in one to one correspondence with 7373N I call of size N2 and so on Prof Rotnac So the set of real numbers is of which cardinality Prof Cantor Of cardinality N1 For it is easy to see that the set of all real numbers is in one to one correspondence with those in the interval 0 1 and the latter is in one to one correspondence with 01 l have two different proofs that 01 is more numerous than N one via what you call the diagonal argument and the other based on the fact that 01 is equivalent to 73N and no surjective map N 7 73N can exist The two proofs are in fact related in a simple way Prof Rotnac Which one is your favorite Prof Cantor You might imagine that I am more fond of the second because it allows me to see that there is a whole in nite sequence of in nite cardinals but the diagonal argument allowed me for the rst time to show that in nite sets come in different sizes so it is particularly dear to me Prof Rotnac My dear friend you have uncovered eine grundsatzliche Wahrheit a funda mental truth of nature which has eluded our science for thousands of years This is heady stuff Georg Have you written to our friend Richard about your ndings Prof Cantor I am so pleased that you are in agreement with my results and methods I have written to Herr Dedekind some of my discoveries but now that l have your reassurance I will write to him an expanded version of my results Speaking of heady stuff here we are in front of our favorite pub Wirsthaus Mozart Shall we go in for a celebratory pint of something cold Prof Rotnac We shall do more than that meine freundl We will go on a Bierreise machen a pub crawl to celebrate your results And I will pay De nition 154 A set X is called countable if it is either nite or equivalent to N A set is called uncountable if it is not countable An in nite countable set ie one which is equivalent to N is also sometimes called countably in nite and is said to have size 040 read aleph nought77 or aleph null7 A set which is equivalent to 73N is said to have size N1 Lemma 155 A set X is countable if there ewists a single in nite list with 07quot without repetition which contains all the elements of X MATH 300 NOTES FALL 05 57 Proof First suppose X is countable If it is nite then certainly its elements can be listed If it is in nite then by de nition there is a bijection f N a X hence f1f2 is a single in nite list containing all the elements of X with no repetition in fact In the other direction suppose z1z2z3 is an in nite list possibly with repetition with the property that for all z E X there exists n E N such that z x If X is nite then it is certainly countable Now suppose X is in nite From the list z1z2 we easily produce a list without repetition that contains all the elements of X Namely let n1 1 and put yl zl Let yg pm where n2 minn gt nllzn Let yg pm where 713 minn gt nglzn y1y2 Similarly having de ned n1n2nk and yk as above we de ne nk1 minn gt nklzn y1y2yk and put yk1 znk Then the map f N a X de ned by fm pm is a bijection so X is countable Theorem 156 a IfX1 XN is a nite collection of countable sets then X1 U UXN is countable b IfX1X2 is a t y in nite t39 of t L sets then Uf Xn is count able The two parts can be summarized by saying that quota countable union of countable sets is countable Proof The proof of both assertions was given in the discussion between Cantor and his friend above In practice mathematicians encounter nite sets countable sets and sets of size N1 on an everyday basis Sometimes when we want to compare two in nite sets to see if there could be some kind of relationship between them its a good rst question to ask if they are both countable Recall that for in nite sets we have given a meaning to the equality le lYl namely this means that X N Y ie there is a bijection from X to Y We will also de ne a partial ordering on the size of sets as follows De nition 157 If X and Y are sets we write le S lYl if there exists an injective map X gt Y We write le lt lYl if there exists an injective map X gt Y but no bijective map X g Y exists Note that the partial ordering we have de ned on sizes of sets is transitive Namely suppose le S lYl and lYl S Then does it follows that le S lZl Yes for suppose f X gt Y and g Y gt Z are injections Then 9 o f injects X into Z But now suppose le S lYl and lYl S We would expect in this case that le In other words if X injects into Y and Y injects into X then there is a bijection from X to Y Cantor was not able to show this but in 1898 Schroeder and Bernstein succeeded in demonstrating this property Here is their theorem Theorem 158 Schroeder Bernstein a Suppose B Q A and there is an injection f A a B Then there is a bijection h A S B b Suppose there is an injectiue map f X gt Y and an injectiue map 9 Y gt X Then there is a bijection h X g Y c Suppose le S lYl and lYl S Then le Proof The proof that follows was adapted from httpplanetmathorg 58 FARSHID HAJIR a Inductively de ne a sequence On of subsets of A by CO A B and On fCn Then the On are pairwise disjoint We will prove this by contradiction Suppose the countable collection of sets 000102 is not pairwise disjoint Let Zj20le Ck7 forsornekgtj We have assumed that Z is not empty and are seeking a contradiction By the Well Ordering Principle7 since Z is non ernpty7 it has a least elernent7 call it m Let k gt m be the least integer larger than m such that Cm Ck 31 0 it exists because m E Z Since CO is disjoint with any following On7 we have 0 lt m and thus that Cm fCm1 and Ck fCk1 But this implies that fCm1 Cm1 31 Q and so Cm1 0k1 cannot be ernpty7 hence mil 6 Z7 contradicting the rninirnality of m This contradiction shows that the collection 0001 is pairwise disjoint Now let C UZO Ck and de ne h A a B by h2 162 g lf 2 6 C7 then hz fz E B But if z C7 then 2 6 B7 and so hz E B Hence h is well de ned h is injective by construction Let b E B If b C7 then hb b Otherwise7 b E Ck fCk1 for some k 2 07 and so there is some a E Ck1 such that ha fa b Thus b is bijective in particular7 if B A7 then h is simply the identity map on A Now b is a simple consequence of a Suppose f X a Y and g Y a X are injective Then the composition 9 o f X a gY is also injective By the lernrna7 there is a bijection h X a gY The injectivity of 9 implies that 9 1 gY a Y exists and is bijective De ne h X a Y by hz 9 1 o h z this map is a bijection For c7 we simply apply b to conclude that if X injects into Y and Y injects into X7 then X and Y have the same cardinality D Note that ifX is an in nite set7 then N injects into X7 hence for all in nite sets7 lNl S The picture that emerged from Cantor7s research is the following schematic of sets classi ed according to their size l 1 l 172 l 1273 l H N WW l7373Nl 0 1 2 3 HNO N1 N2 Cantor had established that N7Z7Q are of size N0 and that 73NR and 01 are of size N1 Cantor believed that there were no sets of size strictly between N0 and N1 in other words7 he believed that if X is an uncountable subset satisfying lNl lt le 3 HM then X is equivalent to R Equivalently7 he believed that every uncountable subset of R is equivalent to R This statement became known as the Continuum Hypothesis Following fundarnental work of Curt Godel in 1940 and that of Paul Cohen in 19627 the Continuurn Hypothesis was found to be in a most rnysterious class of problerns7 those which are undecidable7 What this means in practice7 is that believing the Continuurn Hypothesis to be true does not lead to any contradictions within the totality of all logical consequences of the standard axioms of set theory7 and the same can be said of believing the Continuurn Hypothesis to be false In other words7 there are two perfectly consistent paradigms in which to do set theory one in which we accept the standard axioms of set theory plus the Continuurn Hypothesis and another in which we accept the standard axioms of set theory plus the negation of the MATH 300 NOTES FALL 05 59 Continuum Hypothesisl In practice most problems that mathematicians work on are not affected one way or another by which of these these two set theoretical paradigms we work in because the sets we usually deal with are so to speak too small However in the eld of mathematical logic one of the objects of study to consider rami cations of adopting one set of logic axioms versus another Please note with my apologiesl that l grossly misrepresented the status of knowledge concerning the Continuum Hypothesis in class although I stated the Hypothesis itself correctly 6O FARSHID HAJIR Part 9 Complex Numbers 16 IN THE BEGINNING In the beginning there is the number 1 Then 1 1 makes 2 1 2 makes 3 and the rest is history We get all the positive whole numbers After a while we ponder the reverse of this adding 1 process and discover the take away 1 process which gives us 3 7 1 is 2 2 7 1 is 1 1 7 1 makes a new and wondrous number namely 0 Moreover 0 7 1 makes 71 71 minus 1 makes 72 and so on giving us the negative numbers The new system of numbers Z7271012 has many wonderful qualities and internal relationships For instance 72 is de ned to be 71 7 1 but it is also 71 71 There are quite a few popular books which discuss the history of 0 and negative numbers According to an ancient tradition of mathematics which lasted through the fteenth and sixteenth centuries in European mathematicaI circIes 1 negative solutions of simple equations were not accepted as proper weII behaved solutions and were discarded at the end of the solving process These days of course any accountant knows that negative numbers cannot be simply discarded or do they Can you say Enron How about WorIdcom Once one chooses to accept the system Z of integers as a legitimate collection of numbers it is dif cult to avoid noting its charms There they are the integers marching off to in nity at perfectIy reguIar discrete intervals in two directions with a neutral point 0 smack in the middle perfectIy baIancing out the positive and negative integers As we discussed earlier there are two basic simply fantasmagoric luscious binary operations de ned on Z namer and gtlt What this implies is that for any xed integer k E Z we can attach two actions 77 and 6 corresponding to addition by k and multiplication by k We use 77 to stand for translation by k and 6 for diIation by k in order to emphasize the geometric meaning of these operators 77 shifts all the integers k places to the right if signk 1 and to the left if signk 71 and 6 diIates everything streches Z by a factor of k if signk 71 the there is a stretch by the factor followed by a 180 degree rotation of the line To give a precise aIgebraic de nition for each k E Z we have two seIf maps 77 6 of Z namer 77Z7Zde ned by 77nknfor aIInEZ 61Z 7 Z de ned by 671 kn for all n E Z Note that 77 is a bijection for all k E Z But 6 is a bijection for only very few integers k Which ones Well the map 6 is injective as long as k 31 0 prove it But the image of 6 is what we have been calling kZ namely the set of all multiples of k The latter is all of Z if and only if k i1 Note that i1 are the only integers which have no prime divisors they are units They are also the only ones whose muItipIicative reciprocaI belongs to Z Any aIgebraic manipuIation with integers can be reinterpreted in terms of the geometry of the maps 739 Z 7 MapsZZ and 6 Z 7 MapsZZ For instance why were we motivated to create the negative numbers in the rst place Because the translation map 7391 or rather its restriction to N24 naturaIIy wants to have an inverse map Now 73911N doesn7t 24Whenever f z X 7 Y is a map and S is a subset of X we get a map S 7 Y in a simple way namely by restricting the domain to S In other words we de ne the restriction of f to S denoted f s by f SZS7YSgt gtf8 forallsE S MATH 300 NOTES FALL 05 61 quite have an inverse because 1 is not in its image Thus we are led to creating a symbol 0 which serves as 7141 One then proves that To is the identity map ie 0 n 0 for all 71 By the same process 71 71710 and now one proves that 711 Tfll Note that for any integer k 7k is the compositum of k copies of 7391 resp 71 if k is positive resp negative Recalling how the lack of surjectivity of Tk led to the creation of negative numbers we recall that the maps 6 Z a Z are injective for k 74 0 but they turn out not to be surjective for gt 1 So for gt 1 and n E Z we want an element 61171 which is in general not in Z So we create a new set Q which is the smallest set which lls in the missing numbers Namely we create a set Q by de ning on the set Z gtlt Z025 the equivalence relation ab cd if and only if ad 7 be 0 then we put Q Z gtlt Z0 for the set of equivalence classes We think of the equivalence class ab as the fraction ab We have a natural injection Z gt Q given by n gt gt n 1 In this way we think of Z as a subset of Q On Q we know how to de ne addition and multiplication by the think of them as fractions yoga namely ab cd ad bcbd ab gtlt cd acbd Now the maps 451 Q a Q is easy to de ne just as before as addition and multiplication by k maps with the advantage now that 7k is a bijection of Q to itself for all k and 6 is a bijection of Q to itself for all k 74 0 The fact that we cannot make 7390 into a bijection by extending its eld of de nition is due to its being so horri cally is that a word non injectivel We discussed earlier in the semester that the Greeks were quite happy with their system of numbers Q until they discovered that the equation 2 7 2 0 does not have a solution in this number system The Greeks knew however that the quantity can be approximated as well as one wishes by a sequence of rational numbers eg 1 14141 1414 What is amiss is that this sequence does not have a limit in the set Q itself Thus what is needed is to have a number system in which all sequences of rational numbers which should tend to an acutal number do have a limit Thus another extension of their number system was required The eventual solution was to write rational numbers in decimal expansion and then note that there are lots of decimal expansions that do not express rational numbers because the decimal expansion of a rational number always ends in a repeating nite pattern Thus the set of all real numbers R is de ned to be the set of numbers expressible as a decimal expansion One then shows that any sequence of real numbers which should have a limit does indeed have a limit The concept of should have a limit which I am leaving vague here can be made precise of course and goes under the name of Cauchy sequence for the fabulous mathematician Auguste Louis Cauchy You will learn more about this in Math 523 Thus the set of real numbers R is complete it has all the properties that one would want Translation by a real number is invertible Multiplication by a real number other than 0 is invertible The real numbers have no wholes meaning any sequence of reals that are getting closer and closer together actually converge to a real number Moreover Newton showed how to nd real solutions of cubic fth degree and higher odd degree polynomial equations by an iteration procedure But the seeming perfection of the real number 25Recall that Z0 Z 0 62 FARSHID HAJIR system is tarnished by only one minor defect7 namely7 the simple equation 22 1 0 does not have any rootsl Thi story goes back thousands of years from ancient times7 we have known that there is a simple quadratic formula for solving all quadratic equations7 namely7 if a22bxc0 abc Ral 07 then we put 7b xA 7b 7 xK 7 z2 7 2a 2a and then 122 bx c az 7 21z 7 22 so that 21 22 are the roots of the equation Great The only trouble is how to interpret the symbol xA when A is a negative real number In other words7 how does one solve the equation 22 7 A 0 when A lt 0 If y is a real quantity7 then 22 2 0 so 22 simply cannot equal A lt 0 The easy answer is to say7 Dude7 you just proved these equations don7t have solutions7 so just let it rest manl However7 if you7ve followed the arc of the story so far7 you will have noticed that almost every time that a certain solution did not seem to exist to a simple problem7 there was a way to create a larger set within which a solution does exist and this new set is a bigger and better place to do mathematics So the ambitious answer would be Dude7 you have shown there are no real numbers y that satisfy the equation 22 A when A lt 07 so are there some nonreal numbers that do satisfy the equation Historically what happened is that people came to realize that if they sometimes allowed the use of symbols such as xjl in their calculations7 as long as these symbols were handled with care7 then they could be manipulated in the usual way and this next bit was very important historically they could use these manipulations to nd real solutions of other equations This was a great advantage to those who braved the new world of imaginary numbers as they came to be called There is a fascinating story here for which I highly recommend the book lmagining Numbers by Professor Barry Mazur as summer reading for all of you7 but lets move on to describing the set C of complex numbers7 a place where all polynomial equations have solutionsl Where to start We want to solve yz A where A is negative7 so how about we try 22 71 for starters We know that y cannot be a real quantity7 so we just invent a symbol traditionally the symbol used is 2 and we will stick with that and stipulate that this symbol designates a xed object with the property that 2392 71 We will then want this 2 to interact with real numbers in reasonable ways7 so for example7 we should be able to add 5 to 2 to get an object 2 5 Also we should be able to multiply by real numbers7 say 52397 7239 should be admitted to our system of numbers We will want some standard commutativeassociative rules7 so that7 for example7 2 2 2 239 2 27 2 3239 6239 etc In short7 we want to de ne a new system of numbers to be all those that are generated by the real numbers R and this one new symbol239 but keeping the usual nice rules of addition and multiplication So7 we put Cab239 l aJJER7 and call this the set of complex numbers Note that we can inject R into C via a gt gt a 0239 In this way7 we think of R as a subset of C So7 a complex number 2 is nothing other than a pair cab of real numbers Whats the big deal about that Well7 as a set7 maybe7 that7s what C is but on this set we now de ne some cool operations Namely7 given 220 6 C7 we write 2 a b2 and w c d2397 then we de ne z w a c b d2397 ie we add two complex numbers coordinate wise7 that7s easy Multiplication is a much niftier operation7 so Ab274acxl MATH 300 NOTES FALL 05 63 lets be careful here How should we de ne 2w a bic di Recalling that i2 71 is its de ning quality its raison d etre its mantra its enough already and that we want to maintain the usual algebraic rules we compute a bi c di ac adi bic bidi ac ad bci 7 bd ac 7 bd ad bci So that7s what we do on the set C we de ne a bi c di a c b di a bi c di ac 7 bd ad bci One then checks that all the usual algebraic rules do in fact holdl Now in this new wonderful set C what can we then say about the equation yz 71 Well naturally i is a solution of it But even more than that 7i is also a solution Just plug it in and see 42 4X4 11 i2 1 So we have y 7i y i y2 7i2 y2 1 ie y21 now factors completely and has exacly two roots in C namely i 7i How do we know Because if 2w 0 where zw E C then either 2 0 or w 0 We say that C has no zero divisors The observant reader might now be thinking Dude like we had to do like all this just to solve um yz 7171 And now we have to go through all these hoops again to solve like yz 72 and y2 73 etc77 No Dude we dont Watch if i2 71 and A 7r for some real number r gt 0 then we know we have a positive real number so we observe that ii are two solutions of y2 A As before these are the only solutions in C Consequently we have the following theorem Theorem 161 Ifabc E R with A b274ac 7r lt 0 then the equation a22bzc 0 has emaclty two solutions in C namely 7b i ii7 7 2a 39 Much more is in fact true It turns that if we consider any polynomial equation with coef cients of any degree n 2 1 in C then it will always factor completely into linear factors over C This is known as the fundamental theorem of algebra although it is an analytic factl and the rst proof of it was given by Gauss in 1799 Keep in mind Gauss was born in 1777 Moroever the eld C does not have any holes meaning it is complete meaning any sequence in C which ought to converge does in fact do so Thus the set of complex numbers is some kind of heavenly place to work with numbers 2i Theorem 162 Fundamental Theorem of Algebra Suppose fx and an1 1 alz a0z where ak E C for h 1 n and an 31 0 Then there ecoist integers r s 2 0 with r 25 n real numbers 041 a and non real complew numbers 61 such that xan7a17m96761x7 s967E967E The numbers r s as well as the unordered sequences 041 a and 61 are uniquely determined by f You will probably study a proof of this wonderful theorem in Math 421 using the concept of di erentiablity for a function f C 7 C Just to give a very simple example suppose w E C and w 31 0 Then the equation 22 7 w has two roots Namely if we write w rem with r gt 0 then with 2i i eiQZ we have 22 7 w z 7 2z 7 2 64 FARSHID HAJIR 17 A CONSTRUCTIVE EXISTENCE THEOREM Some of you might feel lulled into a sense of complacency by the previous section7 culmi nating in Theorem 161 Others might be feeling somewhat unsatis ed or unconvinced on the point of the reality of the solution there proposed Oh Oh7 here comes another one of those amp amp plays The reality of imaginary numbers Javier Hey7 professor Dude So you7re saying you can solve an equation like 22 71 by inventing a symbol 239 and calling that the solution What kind of a cop out is that I thought this course was supposed to be about provingjustifying everthing that we do logically How can you just say Oh happy me7 let me just invent a solution7 la di dal and expect us to accept that What would you do if I just invented answers and gave them names to whatever equation you gave me on an exam Kristen Way harsh Farshz39d No7 no7 Javier has a valid point here The point is ne7 maybe wonderful things will happen if I just invent a solution to some equation7 but until I prove that a solution does exist7 it is a valid question to ask how I know that the equation 22 71 has a solution This issue was actually the subject of bitter controversy in the 17th and 18th centuries Gauss7 for instance7 was very critical of how his predecessors just posited philosophers love that word the existence of solutions and went merrily along playing with these posited invented out of thin air solutions Gauss was the rst person to put the complex numbers on rm ground and prove what we now call The Fundamental Theorem of Algebra more on that later Matt T 39 So you7re saying that complex numbers don7t really exist Farshz39d Oh not at all7 l7m just saying I haven7t yet proved that they exist I will do so now Alby No way7 dude7 there is no way you can do it Farshz39d Let me try and the class7 including you7 can be the judge of that Before I start7 let7s agree on what it is l7m setting out to do We all agree that the equation 22 71 has no solution with z E R What I want to construct is a set7 let me call it C for now7 which contains R but also contains a special element 239 such that 2392 71 Actually what I will do is slightly different I will construct a set C which does not contain R strictly speaking7 but an exact copy R of the set of real numbers written in a slightly unusual way To explain what I mean7 recall when we constructed the rational numbers as Z gtlt ZO ie as equivalence classes cab of pairs cab of integers with b 31 0 with Lab 07d if and only if ad be Well the set Z is not strictly speaking a subset of Q Z gtlt ZO now7 is it But we have a natural injection Z gt Q by sending a gt gt 11 In the same way7 we we will have a very natural injective map R gt C whose image R we will think of as a copy of the real numbers Brent 1 think7 with that explanation7 you7ve confused the heck out of half the class and put the other half to sleep MATH 300 NOTES FALL 05 65 Farshz39d You7re right sorry let me just spit it out Alright here we go You remember matrices right Let7s look at the set M of all 2 gtlt 2 matrices with real entries M 23 labcd R I want to look at those matrices that satisfy a d and b 70 Matt L39 Why That seems like a whacko idea Farshz39d You7ll see So let me de ne C to be the matrices that have repeating diagonal entries and whose anti diagonal entries are negatives of each other ie C EM l 07bda 3172 lavb E If we de ne a map m R2 a M by ab gt gt mm where mill 11 g 7 then C is simply the image of the map m You will admit I hope that the existence of the set C is not in question Class Grudingly Granted Get to the point Dude Farshz39d Thank you Next I want to show you that the real numbers live very happily inside C can you guess how Kate Kate I guess the real numbers correspond to matrices with zeros in the b and 7b position Farshz39d Brilliant yesl How did you come up with that guess Kate Well I went with the coincidence of notation theory In other words I Farshz39d interrupting Wait what was that Whats the coincidence of notation the ory77 Kate What I mean is that the set C you have de ned is supposed to be like the complex numbers right Farshz39d Yeah so Kate And you said the elements of C what you talked about before are a in with real numbers ab But now the elements of C are matrices fl Notice how the same letters are used Coincidence I personally don7t think so I think in some twisted way a in the complex number is associated with El the matrix So to answer your question about which of these matrices corresponds to a real number I went back to ask the same about the a in and its pretty obvious which of those are real numbers the ones with b 0 So then going back the matrices I guess the real ones77 are the ones with b 0 ie with zeros on the anti diagonals Farshz39d Wow that is great detective work and perfectly correct in its ndings although I suspect the coincidence of notation theory can lead you down the road of confusion and false turns too But in this case I gotta hand it to you you nailed it We do de ne R to be the set of matrices R fbgleclb0 33 WEIR ln other words R is the image of the clearly injective map R gt C de ned by a gt gt 3 Julie Will this discussion ever come back to the equation 22 71 66 FARSHID HAJIR Farshz39d Yes very soon Good point So how do we express the usual number 71 in this weird matrixy world Julie Julie I guess as 01 31 Farshz39d Yes so we look for a matrix Z of the right type ie with negative antidiagonals and equal entries on the diagonal such that when you multiply it matrix multiplication by itself you get the matrix Julie just said Can anyone see such a matrix Class Silence Farshz39d Okay if I gave you ten minutes even ve even three to work together and you really went at it l7m sure you7d nd it by experimentation but that would be too obvious and boring a way to get the answer Any other ideas for how to proceed Jonah Oh come on man For Pete7s sake you know the matrix just tell us what it is Farshz39d Okay you7re right its lzgifig Would you mind just squaring that matrix and verifying that it gives 01 31 Jonah Annoyed gets to work nonetheless Farshz39d While Jonah is working on that Shaohtm l have an idea which in principle will work To ease the notation recall that the matrix Eb has the name mm Then we want to nd a b such that mil 77119 Farshz39d Hiding his glee Yes go on Shaohtm The equation mil 77110 will give us 4 equations one for each of the entries We can try to solve those four equations to nd the a and the b Farshz39d Excellent you and Ashley and Jing work on that and see what you get Jonah hows it going Jonah Still working on it thanks to you jabbering away Farshz39d Not sorry at all Sorry keep working Mike Jen and I think we7ve gured out the answer Farshz39d Did you just experiment trial and errori cally That would be too dull Mike Well not exactly I really liked Kate7s theory so we went with that to try to guess the anwer its more like steal and check as opposed to trial and error Anyway remember how Kate said she thinks ma is secretly the number a in Farshz39d I believe she used the phrase in a twisted way77 Mike Yes well that7s not the point is it Anyhoo if ma is a M and we7re looking for what matrix represents 239 right Then we should Jen 0 Look at the matrix moL because 239 a in with a 0 and b 1 Ashley Okay we followed Shaohan7s method and we got the matrix 9 01 which is the matrix m01 as one solution Farshz39d Jonah any luck Jonah Dude I multiplied the whole darn thing out three times and I got the same answer three times and it doesn7t give what you saidll Farshz39d Feigning sorrow Oh sorry my man my bad But don7t worry we seem to be getting the right answer some other way Let7s note that moL imo j so if one of them squared is 77119 then so is the other one Alright let7s check moL then m3191591531317 just as we wanted Hurray Notice that in the set C we have two solutions of 22 71 namely moL and m01 So let us de ne I mm This is very nice because then ma abI MATH 300 NOTES FALL 05 67 with the usual operations of matrix addition and multiplying a matrix by a scalar We have therefore settled the existence of a set C which contains a copy of the real numbers and in which the equation 22 71 has a solution Moreover the usual algbraic operations on R extends to C In practice we could continue to work with these matrices but having now rigorously shown the existence of complex numbers in a rather concrete way in fact we can now return with an easy conscience to the paradise of C a bi l ab E R should we ever have any doubts we can travel back to C to make sure our intuition is based on a rm foundation 18 THE GEOMETRY OF C We have seen that geometrically speaking the set C is just the plane R2 ab l ab E R Namely we have a very nice bijective map R2 a C given by ab gt gt a bi Moreover on this set there is a vector space77 rule for adding elements geometrically it is the familiar parallelogram rule which is just gotten by adding coordinate wise which is the usual way adding numbers in R2 On the set C however we have de ned a very cool multiplication rule which one probably would not have thought of if the point 01 had not been given the interpretation as the quantity i This multiplication rule is commutative associative and distributes over addition ie 2w wz zow 2ow and 21 w 21 2w for all 21 w E C The map R2 a C allows us to think of complex numbers as vectors in the plane Contin uing with the vector metaphor lf 2 a bi with ab E R the real part of z is de ned to be a and the imaginary part of z is de ned to be b In other words these are respectively the 10 and 01 components of a b We always have 2 We de ne the modulus or length of z a bi to be lzl Ez2 xa2 b2 By de nition the modulus of z is a non negative real number measuring its distance in the usual sense from the origin The complex numbers with xed real part lie on a vertical line those with xed imaginary part lie on a horizontal line and those with xed modulus lie on a circle centred at the origin We have already encountered a symmetry of the complex numbers the one where i and 7i are interchanged We de ne for z a bi its complea conjugate to be 3 a 7 bi We have Note that lle 23 You might recall that an alternate method for locating points in the plane is called polar coordinates lt speci es a point z in the plane by giving a pair r where 736 are real numbers Here M is the modulus of 2 we allow 7 to be negative in which case we move backwards along the ray indicated by 9 and 6 is an angle measured in radians with 6 0 being the angle subtended by the a axis and positive angles indicating a counterclockwise motion In some text when we want to indicate a complex number 2 whose polar coordinates are r and 9 one writes z rcis0 A little recollection of trigonometry suf ces for noting that 68 FARSHID HAJIR rcis6 rcos6 z sin 6 lf 2 lzlcos6 z sin 67 then the angle 6 is called the argument of z sometimes denoted argz Note that if z 31 07 argz is determined only up to an integer multiple of 27f7 and arg0 is not well de ned at all For instance7 Brian might say that the argument ofz39 is 7T27 and Rick might say that 239 has argument 737T2 They would both be right Here is a wonderful and useful theorem Theorem 181 For a eompler number 2 rcos6z sin 6 with r7 6 E R we have 2 rem Euler s Proof For this proof7 I will assume that you are familiar with Taylor series from calculus Recall the following lusciously and everywhere converging power series representa tions 00 k 52 Z l k0 k 7 47222quot COSZ i Z j0 7 0 71k22m1 SIHZ 7 7 It turns out that these power series converge and are valid even if the argument is a complex number Before we plug in7 lets take a peek ahead and notice that the ex pression z39k will appear in the formulas this is a periodic function of period four7 giving 172397717723971723977177239717 so we will split our sum into the even k7s giving alternating 17 71 and the odd k7s giving alternating 239 7239 So7 we plug in z 26 into the rst one and compute 00 39k k 619 z 6 kl k0 7 239ka 239ka k k keven kodd Z2 62 Z2m162m1 ZW7 2m1l j0 47021 Amazm1 2 0 2m1l cos6z sin6 Presto D Now lets pull a few rabbits out of our hat with this fabulous result First of all7 lets say 21 22 are points on the unit circle7 say 2 em1 and w e192 Remembering rules for how to multiply exponentials7 we have 2w ei9192 In other words7 multiplying two points on the unit circle keeps them on the unit circle but adds their arguments If n E Z clearly z 9 ems7 or z cos 716 z sin 7167 which seems to indicate that if you multiply 2 by itself 71 times7 then that just makes it go 71 times further along the circle MATH 300 NOTES FALL 05 69 Note that if t E R then leitl V cos2t sinzt 1 Let us solve the equation 2 1 where n E N Rewriting z T619 with r 2 07 we have ame 1 giving 7quot 1 Since 7 2 07 we conclude that r 1 Moreover7 arg1 argem97 so we have 710 0 27Tk with k E Z In other words7 6 can take 71 values 27Tkn l k 0127 77171 which are distinct modulo 27TZ These give 71 equally spaced points on the unit circle7 1 being one of them To see what multiplication of complex numbers means geometrically7 for each w E C let7s de ne 6w C a C by z gt gt wz ie 6wz wz This is just an extension of the maps 6k we de ned for integers k to all of C What does the map 65 do Let7s see7 if z a in then 52 5a 5M so it multiplies the imaginary and real parts by 5 The point 2 will move along the line from 0 to z and travel to a point 5 times as far from 0 as it was So 65 is a radial expansion by 5 map You can see that for all s 6 RN that 65 is an expansion by 5 map If 0 lt s lt 17 then its more of a dilation7 isn7t it You should verify that L1 is rotation by 180 degrees around 0 More generally7 if s E R is negative7 then the map 65 is expansion by 151 followed by a 180 degree rotation around 0 Of course7 60 is the killer map that sends everybody and her cousin to 0 Now7 what about 61 We calculate that z a in at 7 b 7b at so multiplying by 239 sends the Euclidean point 11 to the point 497a This represents a vector which is perpendicular to the vector 11 and has moved counterclockwise In other words7 a in has moved 90 degrees counterclockwise7 with unchanged modulus Aha7 so 61 has a nice geometric meaning7 it is rotation by 7T2 radians counterclockwise ln retrospect7 we could have seen that coming7 because 239 emZ so if z T619 then 22 rei97 2 In other words7 16121 and arg6iz argz 7r2 lf that7s not rotation counterclockwise by 7r2 then l7m Mr Noodle What 6w is geometrically for an arbitrary w should now be clear7 for instance by thinking of it as a composite map MATH 300 FUNDAMENTAL CONCEPTS OF MATHEMATICS SYLLABUS Credits 3 Credits Note Math 300 students are required to register also for the l credit co seminar Math 391A which is taught by an undergraduate TA Students will be assigned a seminar time during the rst week of class Prerequisites Math 131 and 132i Co requisite Math 2335 Suggested Texts 0 Class notes by Professor Hajir available upon request 0 Class notes by Professor Meeks available upon request 0 The Mathematical Method A Transition to Advanced Mathematics by Mi Eisenberg Prentice Hall 1996 o How to Read and Do Proofs by D Solow Fourth Edition Wiley 2005 An Introduction to Mathematical Thinking by W Gilbert and Si Vanstone Pearson PrenticeHall 2005 General Course Description Math 300 is designed to help students make the transition from calculus courses to the more theoretical juniorsenior level mathematics courses The goal of this course is to help students learn the language of rigorous mathematics as structured by de nitions axioms and theorems Students will be trained in how to read understand devise and communicate proofs of mathematical statements A number of proof techniques contrapositive contradiction and induction will be emphasized The material includes set theory Cantor7s notion of size for sets and gradations of in nity maps between sets equivalence relations partitions of sets and basic logic truth tables negation quanti ers The material also includes discussion of the integers rational numbers real numbers and complex numbers One or two topics chosen from number theory group theory and pointset topology will also be included according to the interests of the instructor I Basic Set Theory and Logic Required De nitions 1 Given sets A B de ne A N B A UB A X B 2 De ne what it means for f A A B to be a 11 function injective or an onto function surjective or a bijective function 3 De ne the image of a function f z A A B 4 For a function f A gt B and C C B de ne the inverse image f 1C 5 lnverse map f li 6 Equivalence relation on a set 7 Countable set 8 Uncountable set 9 Partition of a set 10 The power set 73A of a set A 11 Q R C Statements 1 lnverse map f 1 exists and is unique ltgt f is bijective 2 Well ordering principle 3 Principle of mathematical inductioni 4 Cantor7s theorem 5 Fundamental theorem of equivalence relations 6 Binomial Theorem recommended Representative problems to solve and proofs of theorems l The composition of injective functions is injective 2 The composition of surjective functions is surjective 3 Write down the truth table for p q gt p 4 Prove 221 k Mnlrl using the principle of mathematical induction 5 What is the power set of 123 6 Cantor7s theorem there is no surjection f z A A 73A 7 Q is a countable set 8 R is an uncountable set 9 Suppose 27 R A R What is the image of f What is f 1 717 4 10 If A B7 C are countable in nite sets7 then A U B U C is a countable set 11 Find the multiplicative inverse of the complex number 5 7239 II Basic Number Theory De nitions 1 Congruence modulo m 2 Construction of Zm 3 Greatest common divisor 4 Prime numbers Statements 1 Division Algorithm 2 Euclidean Algorithm 3 Factorization of integers into primes Representative problems to solve and proofs of theorems 1 Find the remainder of 3100 When dividing by 4 2 Calculate the gcd of 484 and 451 and Write it as a linear combination of 484 and 451 3 Show that 5 is not rational 4 How many positive divisors does 180 have 5 When does a fraction have a terminating decimal expansion in R III Basic Group Theory De nitions 1 A group G 2 A subgroup H C G 3 Order of an element 4 Abelian and cyclic groups A generator of a group 5 Group homomorphism 6 Center of a group 7 Kernel of a group homomorphism 8 Isomorphism Statements 1 A nite cyclic group is isomorphic to Zm for one choice of positive integer m Representative problems to solve and proofs of theorems l Cancellation laW in a group 2 Uniqueness of identity in a group 3 Uniqueness of inverses in a group 4 List the generators of Z3 or Z2 gtlt Z3 5 The intersection of subgroups is a subgroup 6 The center of a group is a subgroup 7 The image of a group homomorphism is a subgroup 8 The kernel of a group homomorphism is a subgroup 9 A group homomorphism is injective if and only if its kernel contains only the identity element 10 The composition of group homomorphisms is a group homomorphism IV Basic Topology De nitions 1 Metric 39space 2 The ball Brp in a metric space 3 Open set in a metric space 4 Topological space 5 Closed set in a topological space 6 Limit point of a subset of a topological space 7 The closure of a subset in a topological space 8 Connected topological space 9 Compact topological space 10 Finite intersection property for a collection of sets 11 Subspace topology 12 Continuous function between topological spaces Stat ement s 1 De Morgan7s Laws 2 Leastupper bound property of R 3 HeineBorel theorem Representative problems to solve and proofs of theorems I In a metric space an open ball is an open set 2 In a metric space the nite intersection of open sets is an open set 3 In a metric space the union of any collection of open sets is an open set 4 A subset of a topological space is closed if and only if it contains all of its limit points 5 The intersection of a collection of closed sets is a closed set 6 A closed subset of a compact space is compact in the subspace topology 7 The composition of continuous functions is continuous 8 The continuous image of a connected space is connected in the subspace topology 9 The continuous image of a compact space is compact in the subspace topology

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.