New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Millie Johnston


Millie Johnston
GPA 3.99


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Mathematics (M)

This 62 page Class Notes was uploaded by Millie Johnston on Friday September 18, 2015. The Class Notes belongs to MAS 4105 at University of Florida taught by Staff in Fall. Since its upload, it has received 6 views. For similar materials see /class/206954/mas-4105-university-of-florida in Mathematics (M) at University of Florida.

Similar to MAS 4105 at UF

Popular in Mathematics (M)


Reviews for LINEAR ALGEBRA 1


Report this Material


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: 09/18/15
Notes by David Groisser7 Copyright 1998 What is a proof When asked to show or prove something7 you are being asked to supply an airtight logical argument leading from the hypothesis to the conclusion A written proof is a one way conversation between the writer and the reader This conversation takes place in English To save space and time7 mathematical symbols may be used to stand for words7 but each mathematical symbol has a xed7 conventional word or a small set of words that it is allowed to substitute for you are not free to make up your own unless you explicitly state what you are de ning your symbols For example7 stands for equals 7 which equals 7 or is equal to it does not stand for Doing the next step in this problem7 I arrive at the expression l7m writing to the right of the equals sign Your written work should have the property that7 when the conventional meanings of your symbols are substituted for the symbols themselves7 the result is a collection of sentences7 with correct grammar and punctuation7 detailing the logical ow of the argument Some useful mathematical abbreviations are the following 0 V stands for for all 7 for every 7 or for each 0 3 stands for there exists or there exist 0 i stands for implies or which implies 0 stands for which is implied by this can also be read implies 7 if you read from right to left or from the bottom of a page up 0 ltgt stands for if and only if or which is equivalent to When you see someone else7s nal proof7 it may appear that he or she has pulled something out of thin air This is a common misunderstanding of whats being asked in show and prove problems Your approach to any such problem involves some thought process which you hope will lead you to an answer ie a proof As far as the thought process goes7 anything is validiyou can work backwards7 make leaps of faith7 make mistakes7 etc This is all okay because at this stage you are not claiming to have an answer All you are doing is trying to collect facts and ideas that you will later assemble into an answer This thought process is not what you are being asked to write down you are only being asked to write down the nal proof When you write this down correctly7 you are showing two things that you recognize what a valid proof is7 and ii in all likelihood7 you came upon your proof by an intelligent thought process7 because the chance that you stumbled onto a correct proof by pure luck is very small There is no single method guaranteed always to lead you to a proof7 but here are a few methods that work well in certain problems o If you7re instructed Show that this thing here is a widget 7 usually what you have to do is write down the de nition of widget and check that this thing here meets all the criteria of the de nition If the problem reads Show that this thing here is not a widget 7 you have to exhibit a property of widgets that this thing here lacks 0 In many instances7 proof by contradiction works The logic is as follows You are asked to prove If P is true7 then Q is true77 Start by assuming that P is true but Q is false lf7 after a series of logical deductions7 you reach a contradiction7 then the assumption that Q is false must be wrong7 and hence Q must be true For an example7 see Example 2 below the part labeled valid proof Sometimes proof by induction works This potentially applies when you are trying to prove something that can be expressed that a collection of statements Sn is true for every natural number n The natural numbers are the positive integers 1237 Proof by induction proceeds by rst showing that 1 is true7 and then showing that whenever n is such that Sn is true called the inductive hypothesis 7 then Sn is true This proves what7s wanted7 because then 51 true i SQ true i Sg true i S4 true i Example Prove that for all n 2 17 the sum of the rst 71 natural numbers is nn 12 Proof Let Sn be the statement that the sum of the rst 71 natural numbers is nn 12 Sl asserts that 111127 which is true Suppose that n is such that Sn is true Then the sum of the rst 71 1 natural numbers is n 1 n 1 n 12 n 1n 227 so Sn is true Example Let V fR R the vector space of real valued functions on the real line7 let n 2 17 and let T17Tn be distinct real numbers zle n 7 rj ifz39 31 j De ne elements fl 6 V7 1 S 239 S 717 by fit em Prove that the set of functions f1L7 fn is linearly independent Proof We proceed by induction on 71 First let 711 Let r1 6 R and suppose c is a scalar for which cfl 0V7 te cent 0 Vt E R Multiplying by e m7 we obtain 0 0 Hence fl is a linearly independent set Now suppose that n is such that whenever r1 Tn are distinct7 the set f17 7fn is linearly independent Let T17rn11 be distinct real numbers without loss of generality we may assume they are listed in increasing order 11 gt Tn gt 1 gt gt 71 Suppose 017cn11 are scalars for which 01f1 cnfncn1fn1 0V Then for all t E R7016 anew cn1em1t 0 Multiplying both sides by e mtl 7 we obtain cle71 fquot1t cne7quot 7quot1tcn1 0 Vt E R But new lt 0 for 1 S 239 S 717 so taking the limit as t a 00 in the preceding equation7 we have 0 0cn1 07 so on 07 and therefore 0V 01f1 cnfncn1fn1 clfl Cnfn By the inductive hypothesis7 f1L7 fn is linearly independent7 true so cl 0 for 1 S i S n We7ve already shown that Cn1 0 Thus whenever clfl cnfn Cn1fn1 0V7 all the scalars cl are zero Hence f1 fn1 is linearly independent Other times7 to nd proofs you have to struggle to understand why something is Experience and thorough knowledge of examples are your best friends here Another approach is to try to look for a counterexample of what you7re being asked to prove You should be able to nd a reason why each of your attempted counterexamples fails For students in MAS 4105 who want to see examples of correctly written proofs7 look at the proofs of Theorems7 Propositions7 etc7 in your textbook for example Propositions 11 and 127 and Theorem 13 Also look at the examples in sections 12 and 13 In each case7 the argument showing that something is a vector space or a subspace is a proof7 despite not being labeled as such 1 E0 Some pitfalls to avoid when doing proofs Here are a few common methods of non proof that are often mistaken for proofs Proof by lack of contradiction not to be confused with the valid method proof by contradiction In this method7 you start by assuming what was supposed to be your conclusion as your hypothesis7 and then say that you7re nished when you reach no contradiction Here is an example Example 1 Given that the total number of points scored in a certain Gator football game was 807 prove that the Gators scored 73 and their opponents scored 7 Proof 73 7 80 That we reached no contradiction shows only that the conclusion is consistent with the hypothesis7 not that it follows from the hypothesis In fact7 what the argument actually proves is exactly the converse of what we were supposed to prove it proves that ifthe Gators scored 73 and their opponents 77 then the total number of points scored was 807 not the other way around This brings us to the next pitfall Proving the converse of what you are supposed to prove The converse of a statement if P then Q is the statement if Q then P Students sometimes fall into this trap because of the way they were taught to prove trigono metric identities in high school For example7 suppose that you were asked to prove 9 7 9 CT the trigonometric identity sec2 z tan2 z 17 knowing that sin2 z cos2 x 1 The most natural thing in the world for a thought process is to start with the conclusion and work backwards write down the equation sec2 z tan2 z 1 on the next line rewrite sec2 as 1cos27 and tan2 as sin2 cos2 on the next line multiply through by cos2 to obtain 1 cos2 sin27 and then stop because you7ve reached an identity you know to be true If you were to write this down as a logical sequence of operations7 detailing what followed from what in your mind7 you7d write seczz tanzx 17 1 sin2 z 2 2 t 17 cos x cos x i 1 sin2 z cos2 x But this is hot what you were told to prove You were told to prove that seczz tan2 z 17 assuming sin2 cos2 x 1 what you did instead is to prove that sin2 z coszx 17 assuming seczz tanzx 1 The actual argument you want reads from the bottom of what you wrote to the top7 not the other way around But any human being looking at what you wrote is going to read from the top down7 not bottom up So for the proof you were asked for you should rewrite the three lines above in the other order Alternatively7 you could have noticed that in the three lines above7 the implications are still valid as if and only if statements each line is logically equivalent to the line before or after7 which would not have been true if your rst line had been7 say7 m 57 and your second line7 say7 x2 25 Then you could have gotten around the need to rewrite the argument7 by simply replacing the i symbols by ltgt symbols Starting a proof with an unconditional assertion of what you are supposed to be proving This is a common mistake when you are asked to prove two things are equal See Proving the converse of what you are supposed to prove above Proof by example Suppose you are given the problem Show that every even positive integer greater than two is the sum of two prime numbers You observe that 422 633 835 1037 1257 1477 165117 185137 207137 etc You list example after example That still doesnt mean there isnt some even number you havent listed that isn t the sum of two primes Here7s another example Prove that if n is prime7 then 2 71 is prime You start checking 22 71 3 is prime7 23 71 7 is prime7 25 71 31 is prime7 27 7112 is prime You might now think the statement is true But 211 7 1 2047 2389 is not prime The statement you were told to prove is actually falsel Proof by notation For example7 you cant prove that addition of matrices is com mutative by saying that since a sign is used7 the operation must be commutative Proof by lack of imagination I dont see how the theorem can possibly be false7 so it must be true Alternatively7 I dont know a counterexample7 so the theorem must be true 7 00 p 0 H E0 Proofs using math symbols for objects that do not exist This is also related to proof by gibberish Example 2 Prove that there does not exist a real number x such that 0x 1 lnvalid Proof If there were such a number7 it would have to be 107 which is unde ned The main reason this is invalid is that it relies on an unde ned term The secondary reason is that the argument makes the nonsensical assertion that something has to equal this unde ned object There is a big difference between reaching a contradic tion7 such as 1 27 and thinking you7ve reached a contradiction just because you don7t know how to make sense of what you7ve writtenl Valid Proof Assume there is such a number x Then 0 0x 17 a contradiction Hence no such z exists Proof by inapplicability of what you know This is sometimes related to proof by lack of imagination The invalid proof above in which something had to be 10 is an example Writing all the correct steps for a proof7 but writing them in an invalid order This is sometimes how people end up proving the converse of what they were supposed to prove Proof by gibberish There are two ways this generally happens Remember that your proof should be readable as ordinary7 grammatical English once the conven tional word substitutions are made for mathematical abbreviations So you can go wrong two places the English you actually write can be ambiguous or in extreme cases incomprehensible7 or the English you get after making word substitutions for the math symbols can have the same problem See the handout Mathematical Grammar and Correct Use of Terminology Assuming the reader can read your mind even if what you wrote does not make sense in English or means something wrong This is related to proof by gibberish Proofs based on assuming an empty set is nonempty For an example7 see Example 1 of the handout called One to one7 Onto7 and What you are really doing when you solve equations Numbers and Polynomials Notes for a course Third edition Kermit Sigmon Department of Mathematics University of Florida7 Gainesville Copyright 19907 1996 by Kermit Sigmon 1999 by Department of Mathematics Department of Mathematics 0 University of Florida 0 Gainesville7 FL 32611 revised June 20017 corrections Nov 2005 Preface to Second Edition The mathematics you will learn in this course is part of what every mathematically mature person should know The course is designed neither for learning computational skills nor for learning many facts about number systems and polynomials over these number systems It is rather to provide you with the opportunity to examine the structure77 of these systems and to learn the art of careful mathematical reasoning It is expected that this experience will help you in the linear algebra MAS 4105 and abstract algebra MAS 4301 courses which most of you will subsequently take You are expected to work through the notes proving the theorems and working the ex ercises Collaboration between class members in this regard is ne indeed encouraged but keep in mind that independent work builds self con dence You should work ahead to the extent that you have worked through the material prior to its discussion in class In this way you can compare your work with that discussed in class and develop a con dence that you can independently attack a question This is a do it yourself course in which you are expected to take your turn presenting your work to the class and to actively participate in class discussion To give you this opportunity for independent discovery the notes contain neither proofs of the theorems nor solutions to the exercises It is important therefore for you to keep a carefully organized record of such obtained from your work as modi ed after class discussion a ring binder is suggested for this The process of carefully rewriting your notes after class discussion is an important part of the learning process in the course Answers to exercises marked with an asterisk 77 are at the end of the notes Enjoy yourself Kermit Sigmon Department of Mathematics University of Florida 5 96 0Thanks go to all the instructors of the course whose many suggestions which have improved these notes 0These notes were typeset using Thanks go to Jean Larson for creating the gures in Chapter 6 with 0These notes were revised in 1999 iii Introduction We adopt the viewpoint that the real number system is known More speci cally we will assume the existence of a set R the real numbers equipped with two binary operations 77 and 77 satisfying certain axioms and an order relation lt 77 satisfying further axioms You are to deduce prove properties of the real numbers from these axioms 7 and these axioms alone The natural numbers integers rational numbers and irrational numbers will be de ned as certain distinguished subsets of the real numbers Their properties will be deduced therefore from properties of the real numbers The complex numbers will be constructed from the real numbers and their properties deduced from properties of the real numbers Finally the notion of a polynomial over a number system will be built on properties of the number system Thus all truth about these number systems and polynomials over them ultimately has its source in the algebraic and order axioms for the real numbers which we will assume An alternate approach to the development ofthese number systems which we do not adopt is to rst assume the existence of the natural numbers or even more primitively the Peano axioms One then constructs successively the integers rational numbers real numbers and complex numbers This route presents considerable technical dif culty especially in building the reals from the rationals We choose the rst approach because it permits one to focus on the central properties of the number systems with a minimum of distractions Contents H Algebraic Properties of the Real Numbers 2 The Natural Numbers Induction 3 Elementary Number Theory l ldeals7 gcd7s and the Euclidean Algorithm ll Prime and Composite Numbers a Rational and Irrational Numbers l Algebraic lrrationals ll More order properties of real numbers lllDecimal Expansions of Real Numbers 5 Countable and Uncountable Sets 6 Fields and Sub elds l Sub elds7 Surd Fields7 and Ordered Fields ll Modular Arithmetic 7 Complex Numbers 8 Polynomials 9 Answers to selected exercises 27 31 31 32 35 39 45 Vi CONTENTS 1 Algebraic Properties of the Real Numbers 11 Axioms Algebraic Axioms for the Real Numbers Field Axioms We assume that the real numbers consists of a set R equipped with two binary operations 77 and 77 satisfying the following axioms AC Commutativity of Addition abbafor all a7bER AA Associativity of Addition abc abcfor all a7b7c R AID Existence of Additive ldentity There is a number 0 E R satisfying a0a0afor allaER AIV Existence of Additive lnverses Corresponding to each a E R7 there is a unique number 7a E R satisfying 1 7a 0 7a a MC Commutativity of Multiplication ab ba for all a7b E R MA Associativity of Multiplication abc abc for all a7b7c E R MID Existence of Multiplicative ldentity There is a number 1 different from 0 in R satisfying 1aaa1 for allaER MIV Existence of Multiplicative lnverses Corresponding to each 1 except 0 in R7 there is a unique number cf1 6 R satisfying aa 1 1 a la D Distributivity abc abac and abc acbc for all a7b7c E R 12 Remark Some other basic facts will be used in proofs without being formally stated here and without citation except as needed to clarify the exposition These can be divided into two categories 2 1 Algebraic Properties of the Real Numbers 1 Laws of logic 2 Laws of equality First we have three basic axioms For all ab and e we have i a a ii if a b then b a and iii if a b and b c then a e In addition there is a general principle which we may call substitution of equals stating that if a b then we may freely substitute the symbol b for a in any expression Thus if a b and e d then a e b d and ae bd The principle here is that a b means that the symbols a and b are names for the same object All of the properties with which we are concerned are properties of the underlying object not of the name and hence are unaffected by the name we happen to use for the object 13 De nitionRemark A binary operation on a set S is a function that assigns to every ordered pair of elements of S a unique element of S Familiar examples of binary operations on R are ordinary addition subtraction and multiplication In particular if we write ab e we are assigning the real number 0 the answer to the ordered pair a b of real numbers One immediate consequence of this de nition is the familiar equals added to equals are equal In other words if a b and e d then a e b d The justi cation for this is that our binary operation of addition assigns to the ordered pair a 0 some real number e lets say But since a b and e d the ordered pair bd is the same ordered pair as a e and since the operation of addition assigns a unique number e to this ordered pair we must have b d e But since a e e we have a e b d In summary we can say that the de nition of binary operation justi es the implication that if a b and e d then a e b d Similar considerations apply to subtraction multiplication and division We will use the familiar rule that multiplication takes precidence over addition so that ab ed means ab ed 14 Theorem Suppose abed E R Then a Ifaebe thenab b The additive identity is unique Thatis ifeER andaeaeafor allaER thene0 e Ifaebe andeyi 0 thenab d The multiplicative identity is unique Thatis ifeER andaeaeaforalla R thene1 e a b c d a c b d and abed mad f a0 0 0a g fab0 thena0 orb0 h 71a 7a 239 77a a and 7ab 7a 7b Warning You cannot use the identity 7171 177 in the proof of clause i since you will not have proved it until clause j a7b 7ab ia and 7a7b ab fa 31 0 then a 1 31 0 l fa 31 0 then a lf1 a also ifa 31 0 and b 31 0 then ab 1L a lb l 15 Theorem Suppose ab 6 R a The equation b z a has one and only one solution b Ifb 31 0 then the equation bx a has one and only one solution 16 De nition We de ne subtraction and division as follows a For ab 6 R a 7 b denotes that number x such that b z a b For ab 6 R with b 31 07 denotes that number x such that bx a 17 Theorem Suppose a7b707d E R a a 7 b a 7b also ifb 31 0 then ab l b abie abiae and7aib bia 1 e fa 31 0 then is the multiplicative inverse ofa a d a also ifa 31 0 then 2 1 a 7a a a a a eIfb7 0 thenT7 b7lt3gt and big f Ifby O andd7 0 then 9fb7 0c7 0andd7 0 then d E C a e adbe hIfb7 0andd7 0thenzEi bd 18 Exercise Limitations on de nitions7 axioms a a Explain Why7 in De nition 167 was not given meaning when l 0 b Explain why7 in MID7 one would wish to require that 1 31 0 by showing that7 if not7 then R c Explain Why7 in MIV7 one would not wish to require that 0 have a multiplicative inverse 19 Exercise Redundancy of axioms 4 1 Algebraic Properties of the Real Numbers Show that Axiom AC is redundant ie7 it can be proved from the other axioms Hint Expand 1 1a b in two ways D C7 V Show that the uniqueness of the additive inverse in Axiom AIV is redundant ie7 show from the other axioms that a E R has at most one additive inverse Show that the uniqueness of the multiplicative inverse in Axiom MIV is redundant 1 e7 show from the other axioms that a non zero a E R has at most one multiplicative inverse O 110 Exercise Show that for abcd E B one has a a bc d ac ad be bd b a b2 a22abb2 and 12in aibab a2 aa b2 bl7 2ab abab 111 Notation A B means that the new symbol A77 is de ned by B 112 Remark This illustrates how one deduces a few of the familiar algebraic properties of R from the axioms You may henceforth use any other valid ones as long as you can verify them upon demand In view of the commutative and associative properties you may also omit parenthesis eg7 a2 2ab b2 a2 2ab bz7 etc 113 Axioms Order Axioms for the Real Numbers We assume that there is a binary relation lt 77 on R satisfying the following axioms OTC Trichotomy For any a7b E R7 exactly one of a lt b7 1 b7 and b lt 1 holds OTR Transitivity lfaltbandbltc7thenalto OA Compatibility with Addition lfa ltb7 then acltbc OM Compatibility with Multiplication lfaltband0ltc7thenacltbo The axioms above7 together with those in 117 assert that the reals are an example of what is known as an ordered eld One more axiom will be presented later as Axiom 47 With this axiom7 the least upper bourid axiom LUB7 the reals are a complete ordered eld 114 Notation a gt b77 means b lt 1777 a S b77 means a lt b or a b 7 etc 115 Theorem Suppose a7b7c E R Theri a Ifagt0 aridbgt0 theriabgt0 Ifaltb theri iagt 7b Ifaltb aridclt0 theriacgtbc agt07bgt0implyabgt0agt07blt0 implyablt0dridalt0blt0 implyabgt0 abgt 0 implies that eitheragt 0 aridbgt0 or elsea lt0 aridblt 0 0lt1 a71ltalta1 1 Supposea7 0 Thehagt0i ggt0 Supposeb7 0 Therigt0 i eitheragt0 aridbgt0 oralt0 aridblt0 1 Suppose a arid b are either both positive or both negative Theri a lt b i gt b a Ifa2ltb2 duda7b20 therialtb 116 Exercise Prove or disprove each of the following a b VV lfaltbandcltd7thenacltbd lfaltbandcltd7thenacltbd Formulate true versions of the statements you disproved 6 1 Algebraic Properties of the Real Numbers 117 Theorem Suppose ab E R Then a Ifaz b2 and ab 2 0 then a b b fa3 b3 then a b a3 121 118 Exercise Suppose ab E R and 2 1 1 Show that b a lt b Arithmetic mean a lfa lt b then a lt b If 0 lt a lt b then a lt M lt b Geometric mean You may assume 416 lt b Harmonic mean 2 clf0ltaltbthenalt1 1 33 119 De nition The absolute value of a number a in R is a ifaZO W i 7a 1falt0 Geometrically we can think of the absolute value lal as giving the length of the line segment of the number line whose ends are a and 0 The de nition by cases given above enables us to use algebra eg l 71 771 by de nition and hence l 71 1 by 14i 120 Theorem Suppose that abe E R Then a lal 2 0 b lial lal and lbial laibl e lalz a2 2 0 d ilal S a 3 lol e ForeZO lal Se z iegage f labl laHbl and ifb 31 0 then Hint Consider using clause g la bl S lal lbl Triangle inequality h laibl 2 Hal W 239 laiel S laibllbiel The importance ofthe notion of absolute value lies in the fact that laibl gives the distance between points a and b on the real number line independent of their order 121 Exercise Solve the following inequalities using ordinary arithmetic on real numbers a lz1l gt6 b Him 13 C 2x 7 9 S 1 d 2z1z74 ez27z76gt0 71 x1 1 Algebraic Properties of the Real Numbers 2 The Natural Numbers Induction 21 Notation We use the notation a E B to mean that B is a set7 and a is a member of that set We write A C B to mean that A is a subset of B7 that is7 Vp x E A gt z E B Thus if A and B are two sets then A B if and only if A C B and B C A 22 De nition We introduce a new symbol N lntuitively7 N will be the set of natural numbers7 N 071727 As we all know7 every natural number is also a real number7 that is7 N is a subset of the real numbers We will introduce three new axioms for the natural numbers 1 Every member of N is a member of R 2 a 0 E N b n 1 6 N for all numbers n E N c n71ENforallnENsuchthatny O 3 The well ordering Principle WO Every nonempty subset of N has a least member That is7 if A is a set with at least one member7 such that every member of A is in N7 then there is some number n E A such that m A for all m lt n 23 Theorem 1 Ifn is any member ofN then n 2 0 Hint N is a nonempty subset of N and hence has a least member by W0 2 Ifn is any member ofN anda E R satis es n lt a lt n 1 then a N 24 Exercise Suppose that N is a subset of the real numbers which also satis es the axioms for N Show that N N Hint Show that every member of N is in N by assuming the contrary and applying acc iom W0 to A N N n n E N and n N to get a contradiction Then use the same argument applying W0 for N to show that every member of N is in N 25 De nition The set of integers Z is de ned by Z N U in l n E N lntuitively Z 77377277170717273 26 Theorem Connections between N and Z a A numbern is in N if and only ifn E Z andn 2 0 b Ifz E Z then E N 10 2 The Natural Numbers Induction Since N C R all of the operations de ned on members of R are automatically de ned on members of N However they are not all de ned as operations on N since the result of the operation may not be in N Thus for example 1 7 2 N even though 1 and 2 are in N and 12 is not even in Z Hence some of the Field Axioms77 from 11 are not true in N for example MIV is not true in N since there is no number 2 1 in N such that 2 2 1 1 On the other hand many of the Field axioms automatically hold in N because they hold in R for example AC is true because if n and m are any two members of N then de nition 221 implies that n and m are also members of R Since we have already assumed that AC holds for R it follows that n m m n The following theorem states which operations and which axioms can be transfered from R to N and to Z 27 Theorem Field and order accioms a N is closed under addition and multiplication that is ifn and m are any two members ofN thennm EN andnm EN Hint Assume by way of contradiction that there are nm E N such that n m N Then the set A r E N n r N C N is nonempty since in E A It follows by WO that A has a least member Call this least member re and reach a contradiction by showing that re cannot satisfy axiom 222c Q 4 Each of the quotField Apioms see 11 holds in N ecccept AIV and MIV and each of the quotOrder Axioms OTC OTR OA and OM see 113 holds in N Hintx They hold in R so they hold in N as long as the relevant quantities are in N m 4 Z is closed under addition and multiplication In addition Z is closed under additive inverse and subtraction Hintx We know the desired sums and products epist in R Use De nition 25 a case analysis 25a and algebra to show that they must also be in Z d Each of the quotField Apioms holds in Z ecccept MIV and each of the quotOrder Axioms OTC OTR OA and OM see 113 holds in Z The following proposition lists a few more of the familiar algebraic properties of N and Z You may want to prove some of them as intermediate results in the course of proving clauses c and d of theorem 27 28 Theorem 1 IfaEZthena71EZ 2fab Zthena7b Z 3 IszZaER andzltaltz1 thena Z 4 The following holds in each ofN and Z39 ab 0 implies a 0 or b 0 Thus neither N nor Z has quotdivisors of zero You may henceforth use any other of the familiar valid algebraic properties of N and Z as long as you can verify them upon demand using algebra and order properties learned in the previous chapter 11 Mathematical induction You may have noticed that almost all proofs using the ax iom WO are proofs by contradiction Mathematical induction can be viewed as a positive way of giving essentially the same proof 29 Lemma Suppose that a E N and that B is a subset ofN which satis es the following two properties a a E B and bh1 B wheneverhEB antha Then z E B for all natural numbers z 2 a Hint Try indirect proof ie7 proof by contradiction using WO 210 Theorem First Principle of Mathematical Induction M11 Suppose that a E N and that for each natural number n 2 a lt13 is a statement associated with n Suppose further that the statements lt13 satisfy the following two properties a lt13 is true b Ifh is any natural number with h 2 a and lt1gtk is true then lt1gtk1 is also true Then lt13 holds for each natural number n 2 a 211 Theorem Second Principle of Mathematical Induction M12 Suppose for each natural number n lt13 is a statement associated with n and the statements lt13 have the following property a If lt1gtk is true whenever lt1gtj holds for all natural numbersj lt h then lt13 holds for all natural numbers n Hint One way to prove this is to let 1k be the statement that lt1gt is true for all j lt 777 and apply M11 to the statements 1k Notice that7 although M12 does not have an explicit base case7 it does have an implicit one which will oftenibut not alwaysineed to be treated as a special case If h 0 then the condition lt1gt holds for all natural numbers j lt h is true for the trivial reason that there are no natural numbers j lt h Hence proving clause 211a for given statements lt13 will always require proving 1307 without any nontrivial assumptions Sample proofs using M11 212 Theorem Ifz is any real number greater than 71 andn is any natural number greater than 0 then 1 x 21 nz Proof Fix an arbitrary real number x gt 71 Let lt1gtk be the statement 1 zk 2 1 hp lt1gtk We use M11 with a 1 to prove by induction on k that lt1gtk holds for all h E N with h 2 1 12 2 The Natural Numbers Induction 1 For k 1 we have 1k1x1km so 1xk 21kx Hence lt1gt1 holds 2 Suppose that lt1gtk is true Then 1 zk1 1 x1 But 1 z gt 0 since z gt 71 and 1 zk 21 kx by lt1gtk Thus by OM we have 1 zk1 1 x1 zk 2 11kz 1k1zk2 But kzz gt 0 since k gt 0 andz gt 0 so 1 zk1 2 1 k 1 This is just lt1gtk1 so we have shown that lt1gtk implies 111 By M11 1 and 2 implies that lt1gtk holds for all natural numbers k gt 0 What about the following proof by mathematical induction 213 Theorem All horses have the same color Proof Let lt1gtk for k 2 1 a natural number be the statement that in any herd H of exactly k horses every horse in H has the same color We will apply M11 with a 1 to show that lt1gtk holds for all k 2 1 1 If a herd H has only one horse then H cant have horses of different colors Thus lt1gt1 holds 2 Suppose lt1gtk holds Since k 1 2 2 we can choose two horses hl and hg from H Consider the two herds H1 obtained by removing hg from H and H2 obtained by removing hl from H Each of these herds has k members so by the induction hypothesis lt1gtk any two horses both from H1 or both from H2 have the same color Thus any two horses in H with the possible exception of the pair h1h2 have the same color Thus we will have nished the induction step if we can show that hl and hg have the same color To this end pick any horse in the herd other than hl and hg Call this horse Misty Then Misty has the same color as hl because both hl and Misty are members of H1 Similarly Misty has the same color as hg because they are both members of H2 But then hl and hg both have the same color as Misty Since H was arbitrary we have shown that lt1gtk implies 111 By 1 2 and M11 we conclude that lt1gtk holds for all natural numbers k 2 1 Hence all horses have the same color1 d 214 Exercise Use mathematical induction to show that for each positive integer n a If 0 S a lt b then a lt b 1 b123n c1352n71n2 1Here is the rest of the story THEOREM All horses have an in nite number of legs Proof by intimidation Everyone would agree that all horses have an even number of legs It is also wellknown that horses have forelegs in front and two legs in back But 4 2 6 legs is certainly an odd number of legs for a horse to havel Now the only number that is both even and odd is in nity therefore all horses have an in nite number of legs However suppose that there is a horse somewhere that does not have an in nite number of legs Well that would be a horse of a different color and by the Lemma it doesnlt exist QED d e f g 215 3 C7 V O nn12n 1 6 7 n2n12 4 a 1223nn1nn1n23 b 123234nn1n2 nn1n2n34 c Find and prove the next statement in the series above d Find and prove the kth statement in the series above7 for any natural number k 1 ym 1yymm ifn247then2nltnl n1 123n Exercise 1 Let F017F117F211 27F31 2 37 in general7 let Fn1 Fn1 F This sequence lists the Fibonacci numbers Show that for all natural numbers n7 Fn S 2 De ne by recursion a sequence bn as follows be 0 b1 bn 7bn1 7 10bn2 for n gt 1 n Use M12 to prove that for all natural numbers n7 bn 5 7 2 Exercise Use mathematical induction to show that7 for each natural number n7 n S 1 or n has a prime factor You may use the following facts which will be proved later a natural numbern gt 1 is prime i it has no factors other that itself and Z ifd is any factor ofn other than 1 or n then d lt n and if d is a factor of d and d is afactor of n then d is afactor of n n has a binary expansion7 00 i nE aZ27 i0 where each al is either 0 or 1 and al 0 for all but nitely many i E N Hint One way to do this is by MI2 ifn is odd then you can get an eccpansion ofn from an eccpansion ofn 71 while ifn is even you can get an empansion ofn from that of 712 You may assume without proof that every natural number n is either even or odd n has a ternary expansion7 00 n E aZZ yl7 i0 where each al is either 07 1 or 27 and al 0 for all but nitely manyi E N 14 2 The Natural Numbers Induction 17T1r17 177m139 Recall that r0 1 e the nth partial sum of the geometric series is n I a17 Tn1gt Sn 3 Zar 39 i0 17 7 3 Elementary Number Theory 31 De nition For ab 6 Z7 we say a divides b in symbols alb if there exists a c E Z such that b ac In this case7 we say that a is a divisor of b7 that a is a factor of b and that b is a multiple of a 32 Theorem Suppose a7b7c E Z a lla and alO for all a E Z b Ifalb then aclbc e Ifalb and ale then alb c d Ifalb then albc e Ifalb and ale then almb no for all m7n E Z f Ifalb and blc then ale 9 fa 31 0 then all if and only if a lb E Z h Ifalb andb 31 0 then al 3 33 Theorem Division Algorithm For ab 6 N with b gt 0 there exist unique natural numbers q and r satisfying a bq r and 0 S r lt b Hint Set R s E N Sq E N such that a qb s7 show R 31 0 and apply WO to get a least element 7 I Ideals god s and the Euclidean Algorithm 34 De nition A non empty subset J of Z is called an ideal of Z if it satis es i z E J7y E J implies xy 6 J7 and ii z E J7n E Z implies in E J What is the smallest possible ideal The largest 35 Lemma IfJ is an ideal of Z then a z E J implies in E J b 0 E J and e for allx E Z x E J if and only E J 15 16 3 Elementary Number Theory 36 Theorem For any a E N de ne the set J by J ha 1 h E Z a For any a E N the set J is an ideal of Z b J0 0 and J1 Z c Suppose J is an ideal on and a E J N Then Ja Q J d Suppose J is an ideal of Z Then there eccists some b E N such that J Jb Hint for d For J 31 07 let A d E J l x gt 0 Show A Q N and A 31 0 apply WO to get h Then for z 6 J7 use the Division Algorithm to show E J17 and use this claim to show J Q Jb 37 De nition lf ab 6 N7 then an integer c is called a common divisor of a and b if cla and clb lf d is a common divisor of a and b such that d 2 c for every common divisor of a and b7 then d is called the greatest common divisor of a and b7 and one writes d gcda7 b 38 Theorem Suppose ab 6 N with not both a and b zero Then there is a unique integer d such that d is the greatest common divisor ofa and b Hint Set A ac c E N7cla and clb Show that A C N and A 31 07 and then apply WO to A 39 Exercise a Show that gcd07 0 does not exist b Show that gcd07a lal for all a 31 0 c Show that if c gcda7b7 then gcd e 1 310 Theorem Suppose ab 6 N not both zero and set Jul kalblk e Z1 6 Z a Jag is an ideal of Z and b Jag Jd where d gcda7b Hint for b We know Jag J5 he 1h 6 Z for some e E N by Theorem 36d Show ed 311 Corollary If a7b E N not both zero and d gcda7b then there eccist integers z and y such that or by d 312 Exercise Prove or disprove a albc implies all or alc b ale and blc imply able 313 De nition Natural numbers a and b are called relatively prime if gcda7b 1 l ldeals god s and the Euclidean Algorithm 17 314 Theorem Suppose abe E N a a arid b are relatively prime i there exist iritegers z arid y such that or by 1 b lfaibe arid a arid b are relatively prime theri aie e lfa arid b are relatively prime arid aie arid hie theri abie d If each ofa arid b is relatively prime to e theri so is ab e lfeia arid eib theri e1 gcdab f lfedqr E N d 31 0 satisfy 0 dq r theri gcded gcddr 315 Exercise Reduction to lowest terms Prove that every fraction whose numerator and denominator are positive integers can be reduced to lowest terms That is suppose m and n are positive integers Prove that there are positive integers h and Z so that h and Z are relatively prime and T 71 Z 316 Theorem Euclidean Algorithm Suppose ab E N with b gt 0 Theri gcdab is the last riori zero remairider rk obtairiedfrom the following applieatioris of the divisiori algorithm uriless bia iri which case gcdab b Hiritx 314f abq1r1 0 r1ltb br1q2r2 0 r2ltr1 T17 2J37 3 0 T3ltT2 W72 Mimi 7 0 S M lt W71 W71 mm wjm 82301 71s this clearer7 Consider the following algorithm which de nes a function GCD GCDab a if b 039 GCDbr 1f a bq r w1th 0 S r lt Thus for example GCD55 15 GCD15 10 since 55 3 45 10 GCD105 since 15 110 5 GCD50 since 10250 5 since b 0 Show that this algorithm computes gcdab That is show that if ab are any two members of N with a 31 0 then the computation of GCDab will eventually stop and that the value of GCDab so obtained is gcda b 18 3 Elementary Number Theory 317 Exercise Use the Euclidean algorithm to compute the gcd of the following pairs of numbers a 10017 1815 b 3917 403 c 49607 9200 d 83167 26208 e If you have access to a microcomputer or programmable calculator7 construct a program to compute gcdab for any positive integers a and l f Extend the algorithm GCD above to obtain a function XGCD such that whenever a7b are in N and a 31 0 then XGCDa7b p7y7d where d gcdab and d za by II Prime and Composite Numbers 318 De nition A natural number greater than 1 is called i prime if its only positive divisors are 1 and itself ii composite if it is not prime 319 Theorem Suppose ab 6 N Then a pr is prime and plab then pla or plb b pr7 114127 7qk are prime and plq1q2 qk thenp qi for some i 320 De nition For a natural number n gt 17 a product of primes plpg pk is a prime factorization of n if i np1p2pk and 10121 3222 pk 321 Example 21377 252223377 10422213 One often groups equal primes 252 22 32 77 104 23 13 So n qlequz quot111517 where ql lt qz lt lt q with el 2 0 322 Theorem Fundamental Theorem of Arithmetic Every natural number greater than 1 has eccactly one prime factorization 323 Corollary Every natural number greater than 1 has a prime factor 324 Theorem Primes and perfect squares a If a7b7 and n are positive integers with n ab then either a2 S n or b2 S n H Prime and Composite Numbers 19 b A natural number n gt 1 is prime i it has no prime diuisorp with p2 S n 325 Exercise Prime factorizations and lists of primes a Determine the prime factorization of the following natural numbers 391 403 1815 8316 26208 997 b Describe a method for nding all prime numbers up to a xed natural number k Apply your method for h 150 h 500 Sieve of Eratosthenes 326 Theorem Distribution of primes a There are arbitrarily large gaps in the primes That is for any natural number k gt 1 there eccist h consecutive composite integers Hintx 6 2 6 3 6 4 6 5 6 6 are each composite b There are in nitely many prime numbers Hintx Suppose not consider N plpg pk 1 327 Theorem Leta pflpf2 pkek andb plflpgf2 pkfk where p1 pk are distinct primes and ef E N for 1 S i S h Allowing e 0 or f 0 permits the use of the same p s for each ofa and b Then a alb i e S f for each i b gcdab plmlpgm2 pkmk where m minef c lcmab pl Ilng2 pkMk where M maxe f In Clause c lcmab is the least positive common multiple of a and b 328 Exercise Use the method of Theorem 327 to compute the gcd and lcm of the pairs of integers in Exercise 317 The results from Exercise 325 may help 329 Remark Although there is no known local pattern to the occurrence of the primes it is known that they become rarer among large integers as one would expect since more prime is a global model for the distribution divisors become available In fact the function 1 n n n of the primes as the following theorem shows we will not prove it 330 Theorem The Prime Number Theorem For a positive integer n let Pn denote the number of primes not greater than n Then lim naoo 20 3 Elementary Number Theory 4 Rational and Irrational Numbers 41 De nition a The set of rational numbers is the set Q l m7n 6 Zn 31 0 b A real number which is not rational is called irrational 42 Theorem The rational numbers Q are closed under addition and multiplication and satisfy all the quotField Axioms See 11 and the order apioms given in 113 I Algebraic Irrationals In 43 through 4177 we assume temporarily that for each positive integer n and each a E R with a 2 07 there is exactly one b 2 0 such that b a this b is denoted by 5 This fact rests on the axiom LUB 47 and is proved for the case n 2 in 416 43 Theorem Irrational square roots a is irrational Hint Suppose not7 and apply Exercise 315 b V12 is irrational e W is irrational d 7S is irrational e Suppose that 0 lt n7 h E N and that W is rational Then there is some in E N so that k n m f and g are irrational 44 Exercise Suppose a7 b E R a Suppose that a 31 0 is rational and b is irrational Can you tell whether ab is rational or irrational What about ab b Suppose that a and b are both irrational Can you tell whether a b is rational or irrational What about ab 45 Theorem a There are no a7b E Q such that W axE b b Ifa3 2b3 c0 with a7b706Q thenabc0 21 22 4 Rational and Irrational Numbers II More order properties of real numbers 46 De nition A number b E R is an upper bound for a subset A of R if b 2 z for all z E A A lower bound for A is de ned analogously Note that b is not an upper bound for A iff there is some z E A with b lt x We now supply the missing order axiom for R which was promised in 113 47 Axiom Least Upper Bound Axiom LUB Each non empty subset A of R which has an upper bound has a least upper bound u Notation u lub A 48 Example The least upper bound of a set may be an element of that set but it need not be for example lub01 lub01 lub1 7 1n 1 23 1 Here is the property for the natural numbers corresponding to LUB 49 Theorem DWO the Order Dual of W0 lfa non empty subset A Q N has an upper boundi E N then it has a greatest element t t E A and a S t for all a E A Hint apply WO to U u E N u is an upper bound of A to nd t We note that the LUB axiom does not hold in Q See 417 Warning Do not confuse LUB and DWO While they may at rst glance appear similar LUB is quite different from the DWO The DWO is based on the W0 and addresses the ordering of N It implies among other things that the ordering of of N is discrete that is for each natural number ii there must be a next greatest one namely the least element of h 6 N1 h gt n whose existence is guaranteed by WO The LUB on the other hand addresses the ordering of R and implies as noted below in 418 that there are no gaps not even in nitely small ones in the ordering of R Hence LUB assures that the ordering of R is a continuum just the opposite of the discrete ordering of N assured by WO 410 Theorem For every real number b there is some n E N so that b lt n Indeed for every real number b 2 0 there is a natural number k so that h S b lt h 1 Hint For the rst sentence assume the sentence is false and apply LUB to the set N C R 411 Corollary Archimedian Property For each ab E R with a gt 0 there epists an integer n such that no gt b 412 Theorem Order Dual of LUB Each non empty subset A ofR which has a lower bound has a greatest lower bound 1 Notation39 i glbA Hint Let B be the set of lower bounds of A apply LUB to B 413 Exercise Show that a limnHOOT ll 0 ie for each 6 gt 0 there is an integer M such that if n 2 M then 0 lt i lt 6 See a calculus book for a de nition of limit of a sequence II More order properties of real numbers 23 b If 0 lt a lt 17 then limiH00 a 0 Hint for b Write 1 x gt 0 and use 212 414 Theorem Between any two distinct real numbers there is both a rational number and an irrational number 7 and hence in nitely many of each type Hint Consider multiples of 7 and g for suitable n Assume though it has not yet been proven that 2 exists 415 Exercise Use the technique of the proof of 414 to exhibit a rational number and an irrational number between a x and 4 5 and c 3 and v11 Finally we show that 2 exists 416 Theorem For each a E R a 2 0 there erists eccactly one b 2 0 such that b2 a This b is denoted by Hint Set u lubA7 where A x 6 R10 3 x2 S a7 and show u2 a7 using an indirect proof If u2 lt a7 exhibit E gt 0 such that u 62 lt a7 etc 417 Theorem The LUB acciom does not hold in Q Hint Consider the set A Q for a 2 from theorem 416 418 Remark The set A from the hint for Theorem 4177 paired with B y E Q y 2 0 and y2 gt 27 gives one example of a Dedekind cut With Dedekind cuts one can more clearly see the role of LUB and how the rational and irrational numbers intermix Suppose A and B are disjoint subsets of Q whose union is Q and for which z lt y for each x E A and y E B Such a pair A7 B of sets is called a Dedekind cut Each such pair corresponds to a real number if either A has a greatest element r or B has a least element r7 the pair A7 B corresponds to the rational number r a pair in which A has no greatest element and B has no least element corresponds to an irrational number The irrational numbers can7 therefore7 be Viewed as those numbers created to plug the holes between pairs of sets in Dedekind cuts of the second type Note that LUB asserts the existence of numbers to plug all such holes This is what we meant earlier when we said that LUB asserted that there are no gaps in the ordering of R 24 4 Rational and Irrational Numbers III Decimal Expansions of Real Numbers 419 Remark In 420 through 432 we explore the decimal expansion of a non negative real number less than one 7 in particular the form of the expansion for a positive rational number that can be represented as a proper fraction Since by Corollary 410 every non negative real number can be expressed as the sum of a natural number and a non negative real number less than one this exploration yields a lot of information about the entire set of real numbers In this section formal proofs of the theorems are not expected One should however be able to illustrate why Theorems 426 427 429 and 431 hold through an analysis of general examples 420 Theorem If lrl lt 1 then the geometric series aar ar2 or converges to 7 Recall that cl 02 03 converges to b77 means limHcocL 02 on b in this case we write b cl 02 03 You may wish to consult a calculus book for the de nition of the sequence of partial sums and the de nition of convergence of a series 421 De nition A decimal expansion of a non negative real number b lt 1 is a series 11 12 1k 10102 10 which converges to b where a E 0 l 2 8 9 for each i and not all as are 9 from some point on One usually writes b 0a1a2a3 l 422 Example By 420 0333 since 1 30 converges to 10 g 10 025000 is a decimal expansion for i but 024999 is not 423 Theorem Convergence existence and uniqueness of decimal eicpansions a Each series i as described in 421 must converge to some non negative real number less than one That is each decimal erpansion represents a non negative real number less than one 7 9 9 Hint Compare with 1 i E W Comparison Theorem 39 see a calculus book for a suitable H Oils b Conversely each non negative real number less than one has a decimal eppansion c The decimal erpansion of a non negative real number less than one is unique Hint for c Suppose r 0a1a2a3 0b1b2b3 Multiply by 10 to obtain 10r a1a2a3 b1b2b3 Use Theorem 410 to argue that al b1 Note that 0203 10r 7 a1 10r 7 b1 b2b3 Continue by induction We now explore the decimal expansion of a positive rational number which can be repre sented by a proper fraction III Decimal Expansions of Real Numbers 25 424 Exercise Compute via long division the decimal representations of 5 5 13 201 3 5 5 7 7 7 7 7 7 and 39 8 11 88 444 7 7 13 Examine the form of these decimal expansions length of repeating blocks and delay before such begins Do you see any connection between this form and the denominators of the rational numbers 425 De nition A decimal expansion 0a1a2a3 is a Periodic if after some point a block of digits repeats itself inde nitely 0a1a2 asaHL a51ta511 aHt In this case we write 0a1a2a5a51a5t For example 2 72 03181818 03K The smallest such 5 is called the pre period and the smallest such t the period of the expansion b Terminating if all a from some point on are zero 0a1a2 a5000 Observe that every terminating decimal expansion is periodic of period 1 426 Theorem Normal forms of decimal eccpansions of rationals a The decimal edpansion of each positive rational number q lt 1 is periodic b Conversely each non zero periodic decimal edpansion of a non negative real number b lt 1 represents a positive rational number Hint for a What are the possible remainders in each step of performing the long division nlm Hint for b Generalize this computation b 0123 implies 103b 123 and 105b 12245 Hence 105 710 12345 i 123 so that 12222 7 12222 7 1358 105 7103 99000 T 11000 Call a fraction a proper reduced rational number if m lt n are positive integers with gcdmn 1 Recall that in Exercise 315 we showed fractions could be reduced 427 Theorem The decimal eccpansion of the proper reduced rational number is termi nating emactly when n 205 for some LLB 2 0 In this case the length of the terminating decimal eccpansion is maxoz 11 i 11 Hint Ei o2m 428 Exercise Express as a reduced quotient of integers 26 4 Rational and Irrational Numbers a0 m 413 21 044 3 2 C7 c 034612 d Exhibit explicitly a decimal expansion of an irrational number 429 Theorem Assume is proper and reduced with no 2 or 5 in the prime factorization of n Then the pre period of its decimal eccpansion is zero and the period is the smallest integer t so that 71110 71 ie t is the number of digits in the smallest of97 997 9997 99997 which n divides Hint b 9 implies 103i 393 Then 103 71 393 so that 7 393 7 393 7 131 7103717 999 7 33339 430 Remark It can be shown that for any such n7 a t exists such that 71110 7 1 431 Theorem Suppose is proper and reduced and n 20 5 n where n has no 2 or 5 in its prime factorization Then the pre period of the decimal eppansion of g is maxoz and the period is the smallestt such that n l10t 7 1 432 Exercise Determine7 without dividing out7 the form of the decimal expansion of the following 27 7 7 154 7 111 a b c 56 13 1680 148 5 Countable and Uncountable Sets We now explore brie y how many77 natural numbers7 integers7 rational numbers7 irrational numbers7 and real numbers there are 51 De nition 1 If A and B are sets7 then afunctz39zm f from A to B is an object which speci es7 for each element a 6 A7 an element fa E B We use the notation f A a B to say that f is a function from A to B We will not attempt here to say what sort of an object a function is7 or precisely what we mean by the word speci es D A function f A a B is onto B if for each b E B there is at least one a E A such that b fa A function f A a B is me to zme frequently written 171 if for each b E B there is at most one a E A such that b fa 00 Note that this de nition can be equivalently stated as f A a B is 171 if for every a7a E A such that a 31 1 we have fa 31 fa 77 For an example of a function7 consider a shepherd who has made a list of the names of the sheep in his herd Assuming that no two sheep have the same name7 the shepherd has de ned a function S which assigns to each name 71 on the list the sheep Sn having that name The function is one to one provided that no sheep has more than one name if the list includes nicknames along with the of cial names7 then it would not be one to one It is onto if every sheep has a name during lambing season the function would not be onto until all of the newborn lambs had been given names We say that there is a one to one correspondence between two sets A and B if there if is a one to one function from A onto B In the case of the sheep there is assuming no nicknames a one to one correspondence between the set of names on the list and the set of named sheep Clearly7 this correspondence shows assuming no nicknames that there are at least as many sheep as names If every sheep has a name then it shows that the sets have the same size7 but if this is lambing season then the set of named sheep may be a proper subset of the set of all sheep7 so we could conclude that there are fewer names than there are sheep 52 De nition a Two sets A and B have the same cardinal number7 written A E E7 if there is a one to one correspondence between A and B Example The one to one correspondence n lt gt 271 shows that the set of all natural numbers has the same cardinal number as the set of even natural numbers 27 28 5 Countable and Uncountable Sets b We say that A has at most as many members as B written A 5 B if there is a one to one correspondence between A and a subset of B Example the identity function de ned by idn n for each n E N shows that N j N N 5 Q and N j R The function f N a Q de ned by fn 1n 1 is another map showing that N 5 Q c A has fewer elements than B written A 4 B if A 5 B but A E B d A set is countable if it is either nite or has the same cardinal number as N the set of natural numbers Otherwise it is said to be uncountable e A set is countably in nite if it is countable but not in nite 53 Remark Notice that the function Dn 2n of clause a is a 171 function from N to the set of even numbers which is a proper subset of N This is an important difference between nite and in nite sets The set of sheep is presumably nite so if there are sheep without names then the set of named sheep must be strictly smaller than the set of all sheep In the case of the in nite set N however the function D shows that the set of even numbers has the same size as the full set N 54 Remark Mathematicians often write lAl for the cardinal number ofA the number of elements of A Thus A 5 B could be written lAl S However you should not use the concept of the cardinal number of A77 in the proofs below In the rst place we really have no idea what the cardinal number77 of an in nite set would be clearly the cardinal number of the set Buttercup Silvy Misty is the natural number 3 but what sort of an object is lRl the cardinal number of the set of reals In the second place Remark 53 shows that in at least one important aspect the cardinal numbers of in nite sets behave quite differently from nite numbers It seems that we should be careful not to trust the analogy too far until we have a better understanding of the properties of the cardinal numbers 55 Theorem The relation A E B is an equivalence relation That is for all sets A B and C a Re exivity A E A b Symmetry IfA E B then B E A c Transitivity IfA E B and B E C then A E C 56 Theorem N E 1357 E Z E Q That is each ofN 135 Z and Q is countably in nite 57 Theorem N 4 R That is R is uncountable Hint Let A x E R 0 lt z lt 1 and show N 4 A indirectly Suppose to the contrary N E A with a one to one correspondence between N and A given by 0 lt gt 0a00a01 a0 a0 a04 1 lt gt 0a10a11a12a13a14 2 lt gt 0a20a21 122023014 29 where 0ak0ak1 a is the decimal expansion of the real number rk corresponding to the natural number k Nowletb0b0b1b2b3wherebi la 7g 2 1M To what natural number can b correspond This argument is called the Cantor Diagonalization Process 58 Theorem a The union of two disjoint countably in nite sets is countably in nite b There are uncountably many irrational numbers 59 Theorem For any set A A 4 73A where 73A denotes the set of all subsets of A called the power set of A Hint lndirect proof Suppose to the contrary that f A a 73A is a one to one correspon dence between A and 73A and consider the set E x E A z Then B E PA so it must correspond to some element b E A ls l E B 510 Exercise Give examples of in nitely many in nite sets no two of which have the same cardinal number Theorem 55 stating that E is like an equivalence relation suggests asking the question whether the relation 5 is an order relation In fact it is as the following theorem asserts We will not prove parts b and 511 Theorem a For all sets A B and C ifA 5 B andB j C then A j C b For all setsA and B ifA 5 B andB j A thenAE B c For all sets A and B eitherA 5 B or B j A The proof of the rst clause is essentially the same as clause c of theorem 55 The proof of the second which is known as the Cantor Bernstein theorem is somewhat more challenging The proof of the third requires a new axiom the Axiom of Choice To get a start on the theory of arithmetic for in nite cardinal numbers notice that if 0 is the set of odd natural numbers and E is the set of even natural numbers then N OUE and hence we must have lNl 0 But 0 lNl so it follows that lNl lNl In fact one can prove using the axiom of choice that for any in nite cardinal number n we havennnandnnn 30 5 Countable and Uncountable Sets 6 Fields and Sub elds 61 De nition A eld is a set F equipped with binary operations and satisfying the eld axioms77 given in 11 AC7 AA7 AID7 AIV7 MC7 MA7 MID7 MIV7 and D A subset K of a eld F is a sub eld of F if K itself forms a eld under the operations de ned on F Recall that the closure of a set under an operation follows from the meaning of a binary operation on the set see 13 62 Example Revisiting R and Q a We began by assuming that the real numbers R form a eld b The rational numbers Q form a eld see 427 and Q is a sub eld of R I Sub elds Surd Fields and Ordered Fields 63 Theorem Suppose that F is a eld If a subset K ofF satis es the hypotheses i K is closed uhdeiquot addition and multiplication ii 01 e K iii a E K implies 7a E K and iv 0 31 a E K implies a 1 E K then K is a sub eld of F 64 Exercise Sample surd elds D Any sub eld of R must contain Q as a subset C7 V Show that a b l a7b E Q is a proper sub eld of R which properly contains Q Notice that is the smallest sub eld ofR which contains Q and That is if F is any sub eld ofR such that Q C F and 6 F then C F O Show the same for a lngl a7b E Q CL Neither of and is a subset of the other 31 32 6 Fields and Sub elds e Show that a lug2 cx7221abe E Q is a sub eld of R Hint Compute a lug2 e322d ey2 f722 where d a2 7 2be e 202 7 ab and f b2 7 ac To show that the product is nonzero use 14g f Give examples of in nitely many proper sub elds K of R which properly contain Q Note A is a proper subset of B if A C B but A 31 B 65 De nition A eld F is an ordered eld if it satis es the order axioms OTC OTR OA and OM given in 113 An ordered eld is called completely ordered if in addition it satis es the least upper bound axiom 47 We have assumed that the real numbers R form a completely ordered eld 66 Theorem Ordered elds and sub elds a A sub eld of art ordered eld is art ordered eld b Q Q2 Q3 and are ordered elds c Q is not completely ordered See theorem 417 II Modular Arithmetic 67 De nition For each positive integer n 2 2 we set Zn 0123n 7 1 and de nite operations and on Z by a b remainder after division of the usual sum by 71 ab remainder after division of the usual product by n For example in Z7 3 6 236 4 and 62 1 68 Remark One can show and we will assume that for each n all of the eld axioms hold in Z except possibly MlV Note that for n 12 the operations de ned above form the arithmetic of a clock 69 Exercise Sample computations a Compute in Z8 5 7 5 7 72 b Compute in Z5 72 2 7 4 2 c Which elements of Z10 have a multiplicative inverse Compute those that exist 610 Theorem Let n 2 2 H Modular Arithmetic 33 a The set of those elemerits of Zn which are relatively prime to n is closed urider multi plicatiori Hint See 314d7 314f Ari elemerit a iri Zn has a multiplicative iriverse i a aridn are relatively prime Hint See 314a and 611 below 3 Zn is a eld i n is a prime 0 d No order relatiori cart be placed ori Zn so that Zn becomes art ordered eld 611 Exercise If a 6 Zn with a relatively prime to n7 then7 using the Euclidean algorithm one can nd integers r and k such that or nk 1 If r is then reduced via the division algorithm7 r nq b7 0 S b lt n7 then b is the multiplicative inverse of a in Zn Show that this is indeed true and then use this method to compute a The multiplicative inverse of 7 in ng b The multiplicative inverse of 11 in Z1255 34 6 Fields and Sub elds 7 Complex Numbers 71 De nition The samplers numbers is the set 3 ab la7b R on which equality7 multiplication7 and addition are de ned as follows Equality a M c dz39 means a c and b d Addition a in c dz39 a c b dz39 Multiplication a in c dz39 ac 7 bd ad bcz39 For a complex number 2 a in7 1 is called the real part of z and b is called the imaginary part of z The complex numbers are represented geometrically by the Cartesian coordinate plane 2 a in is paired with the point having coordinates a7b as indicated below imaginary axis real T1 l1 391 axis 7239 O b a M 72 Exercise Complex arithmetic a Show that the sum and product of complex numbers de ned above is the same as if one treated the numbers as polynomials in 239 and let 2392 71 Hence by an abuse of notation7 we write7 for example7 2 7 3239 for 2 73z39 b Find the sum7 product and quotient See 75d of i 2 3239 and i2 7 5239 n 5 and 72 2 iii 4239 and 6239 c Locate in the complex plane 3 7 2397 74 32397 722397 2 35 36 7 Complex Numbers d Compute 7 3i3 e Interpret complex number addition geometrically in the plane 73 De nition For 2 a bi in C7 a 2 a 7 bi7 the conjugate of z b m the absolute value of z 74 Exercise Geometric interpretations of conjugate and absolute value a What are the relative positions of 27 72 27 and 72 in the complex plane b lnterpret geometrically 75 Theorem If 2 21 and 22 are in C then a m 71 72 b m 7172 c z is real i z 2 d 22 Hence 2 1 22 22 22 2le Use de nition 16 for division of compler numbers that is is the unique number w such that 21 22w 6 lzl l Zl lil Hintx Consider using d above f lzlzgll21ll22l and 2 21 22 E 21 22 S lzll triangle inequality Hintx First show the Schwarz inequality ac bd2 S a2 b2 c2 76 Theorem C forms a eld 77 Theorem Complex sub elds a There erists no sub eld K ofC with R C K C C and R 31 K 31 C b There is however a proper sub eld ofC that is not a subset of R Give an eccample of such c No order relation can be placed on C so that C becomes an ordered eld 37 78 Remark In doing arithmetic with complex numbers it is useful to have the exponential function e1 for real and complex numbers and the trigonometric functions sinz and cosx for real numbers In the following7 assume that these functions have been de ned for real numbers and assume without proof that they have their familiar properties for real numbers We will use this assumption in order to extend the de nition of e1 to complex numbers 2 and to prove that it still satis es the familiar properties for complex numbers 2 79 De nition For 2 a bi 6 7 one can write a rcos6 and b rsin6 7 where r and 6 are as shown below Hence 2 rcos6 isin 67 the polar form of 2 Notice that r and 6 tan 1 or7 if a lt 07 then 6 7139 tan 1 The angle 6 is called the argument of z The exponential function can be extended from R to C by de ning em cos6 isin6 Thus can write 2 rcos6 isin6 rem rcos6isin6 re a bi 7 56 Examples 2 7 2i 2 COS72S1H7 71 z 2cos 2 isin 2 i 1cosisin 710 Theorem If 21 rcos 6 isin 6 and 22 scos b i sin b then a 2122 rscos6 b isin6 15 new and b a cos6 7 b isin6 45 EEW W 22 8 e elt11m ezle 711 Exercise Polar form and geometric interpretation of multiplication a Write in polar form 2 2i7 7 i 72i 73 b lnterpret complex number multiplication geometrically in the plane 712 Theorem DeMoivre7s Theorem Ifz rcos6 isin 6 and n is a positive integer then 2 r cos n6 isin n6 713 Theorem Let 2 rcos 6 isin 6 be a nonzero compler number Then 2 has emactly n n th roots namely 6 2 6 2 wk Wltcos 1k isin 7 fork 071727n71 n n n n 38 7 Complex Numbers 714 Example Some complex roots in Cartesian and polar form D The square roots of 1 are we 1cos0z39sin0 wl 71 cos7r sin7r b The cube roots of 1 are see gure at left below we 1 cos0 sin0 7 M3 27r w 27r wli 2nL j zicos 3 zs1n 3 77 339 AM w 47r LUgi 2 227cos 3 zs1n 3 The square roots of 4239 are see gure at right below we 2cos z sin wl 2cos aquot z39sin O 4239 wo 715 Exercise Determine and graph in the complex plane all 4th roots of 1 D C7 5th roots ofz39 Cube roots of 8 0 CL 4th roots of 16239 Square roots of 1 Z39 D 4th roots of 71 7 t 1 91 716 Exercise Determine all solutions in C of ax47160 d3764 0 b6640 ez4810 cz38 0 fx572430 8 Polynomials 81 De nition Polynomials and their arithmetic a A polynomial Pz oyer a eldF or over Z is a symbol C7 0 V Pxa0a1a22anz in which al 6 F or al 6 Z for each i and al 0 for all i from some point on The set of all polynomials over F or over Z is denoted by or and is called the polynomial ring over F Examples 2 x x2 is in BM 1z2z23z3nz and CM but not in QM or ZM is not a polynomial why The degree of a non zero polynomial Pz a0 alz and n such that an 31 0 Notation deg P The zero polynomial all al 0 is not assigned a degree is the largest Examples 4 3x2 5x4 has degree 4 nonzero constant polynomials Pz a0 a0 31 0 have degree zero Addition and multiplication of polynomials are de ned as follows For Pz a0a1a2z2 anx and Q b0b1b2xz bnx 7 i Pz Q a0 be a1 b1x an bad ii PxQx co clz 02x2 and 7 where for each n7 On 3 Z aibj aObn albnil aan72 anilbl Inbo ijn 82 Exercise lf Pz 1 4x 2x2 and Qz 4 7 z x2 3H7 compute Pz Qz and PxQx a Using the formal de nitions given in 81c b As you did in high school algebra Compare the computations7 not just the results 83 Theorem Closure under and gtlt The sum and product of two polynomials over a eld F or over Z are polynomials rather than just power series Moreover if Pz and Qz are nonzero polynomials oyer a eld F or over Z then 39 40 8 Polynomials a degPz S maxdegP7 deg Q prouided Pz Qz 31 0 Give an example to show that strict inequality can hold b deg PxQx deg Pz deg 84 Theorem For any eld F and a Satis es all the eld accioms epeept MIV b Has no diuisors of zero That is PxQz 0 implies Pz 0 or Qz 0 e PxQz PRx 31 0 implies Q 85 Theorem Division Algorithm Let Pz and D be polynomials ouer a eldF with Dz 31 0 Then there exist unique polynomials Qz and Rz such that Pz DQz Rz with either deg Rz lt deg Dz or R 0 86 Exercise Compute via long division Qz and Rz in the division algorithm if a Pz 4 7 3x2 z 3 and D 2x2 71 b Pz 5x4 7 2x3 12z 7 6 and D x2 4 c Pz 2x4 2x3 3x2 z 1 and Dz 2x2 1 87 De nition Suppose that Pz a0 alz 1ng and is a polynomial over a eldFanchF a The value of Pz at c is de ned to be Pc a0alca202anc F b c is called a zero of Pz or a root of Pz 0 if Pc 0 88 Theorem Remainder Theorem If the polynomial Pz over a eld F is divided by 70 0 E F to give Pz z7cQ R then R Pc R Rz is constant Why 89 Notation Synthetic DivisionSubstitution The computations involved in dividing a polynomial Pz by z 7 c can be placed in a convenient format synthetic division For example7 to divide 3x4 7 2 5x 2 by z 7 2 one can write coef cients of Pz C 7 3 0 71 5 2 E add middle 6 12 22 54 bottom X c 3 7 6 7 117 27 56 remainder 130 V quotient 3x3 6x2 11z 27 Notice that this process computes the remainder R7 which by theorem 88 is equal to Pc Hence the process of synthetic division is also a convenient method for computing Pc When used in this way7 it can be called synthetic substitution 41 810 Exercise Practice with synthetic divisionsubstitution a Use synthetic division to divide 4x5 7 3x4 5x2 9 by z 2 b Use synthetic substitution to compute P3 if Pz 7x4 7 6x3 2x2 7 12 c Use synthetic substitution to compute if Pz 3x4 7 3 7 3x2 4x 7 1 811 De nition Suppose Pz7 Qz are in or One says that Pz divides Qz in or written if there is a polynomial Rz in or such that Qz 812 Example z 7 7 2 in RM but not in 312z 5 in QM but not in 813 Theorem Factor Theorem Suppose Pz is in and c E F Then z 7 clPz i Pc 0 814 Corollary A polynomial of degree n over a eld can have at most n distinct zeros in the eld 815 Theorem Rational Root Theorem Let Pz a0 alz anz an 31 0 be a polynomial oyer Z If is a reduced rational zero of Pz then plao and qlan When searching for zeros of a polynomial oyer Z this narrows the search for rational zeros to nitely many possibilities 816 Example Any rational zeros of Pz 2x37z2 74z2 must occur among17 17 27 27 7 7 why Evaluating Pz at these numbers reveals that 0 hence z 7 Synthetic division then yields Pz z 7 2z2 7 4 What are the other zeros of Pz7 817 Exercise Applications of the Rational Root Theorem a Find all rational zeros of Pz and a factorization in QM of Pz if Pz i 5 7 3x4 7 3x3 9x2 7 4x 12 103954 711953 1095 7 4 iii 954 2x3 2x2 7 4x 7 8 b Use the rational root theorem to show that i is irrational ii 51 is irrational 818 Theorem Quadratic Formula The zeros in C of the quadratic polynomial az2bzc a 31 0 over R are 7bb274ac d 7b7xb274ac an 7 2a 2a 7b x4ac7b2 7b x4ac7b2 i and 7 i7 2a 2a 2a 2a if b2 7 4ac 2 07 and isz 7 4ac lt 0 42 8 Polynomials b 2 b2 7 4ac H1nt D1V1de by a7 then complete the square to get z 2 a a l 819 Exercise Zeros of polynomials in a Find all zeros in C of i x2 4x 13 ii x2 7 6x 4 iii 2x3z2p71 b Use the method suggested by the hint in 818 to nd all zeros in C of the following polynomials over C i z24z 49i n x274iz713 820 Theorem Fundamental Theorem of Algebra Every polynomial over C of positive degree has at least one zero in C We will assume this important theorem lts proof involves concepts well beyond the scope of this course It tells us that in order to ensure that all polynomial equations have roots7 there is no need to extend our number system beyond C 821 Corollary Every polynomial Pz over C of positive degree can be factored in CM into a product of linear rst degree factors 1325 am 7 ma 7 r2 z T 822 De nition A polynomial over a eld F of positive degree is called irreducible over F if it is not the product of two polynomials in of lesser degree 823 Example x2 7 2 is irreducible over Q but not over R x2 1 is irreducible over R but not over C 824 Theorem Irreducible polynomials a Every linear polynomial is irreducible b The only irreducible polynomials over CM are the linear ones c A quadratic polynomial axz bx c a 74 0 over R is irreducible over RM i b2 7 4ac lt 0 d There eccist irreducible polynomials in QM of degree three 825 Lemma Suppose Pz is in RM and z E C Ifz is a zero of Px then so is 2 Thus the nonreal zeros of a polynomial over R must occur in complep conjugate pairs Hint First show W 43 826 Theorem Every polynomial over R is the product of polynomials over R of degree at most 2 Hintx First factor in CM x 7 z x 7 2 7 827 Exercise lrreducible polynomials a Describe all irreducible polynomials over C Over R b Write the following polynomials as a product of irreducible polynomials over C Over i x47239x22x710 i x57348x378z27z75 iii 35 7134 223 7 302 32 7 8 iv 4 1 c Are the following irreducible over Q Explain d Are there irreducible polynomials in QM of arbitrarily large degree e Can you describe all irreducible polynomials in QM of degree 2 Of degree 3 Of any degree 44 8 Polynomials 9 Answers to selected exercises 121 a z 317 a 11 b 1 c 80 d 252 325 a 403 13 317 1815 3 5 112 26208 25 32 7 13 lt77orxgt5 c4 z 5 dnorealnumber fzgt71 5 3 13 5 424 0457 04285717 g 0147727 E 0384615 11 7 428 a 2389 61679 C 8653 11100 138875 25000 428432s3t6 432s0t6 432s3t1 432z2t0 69 611 a 9 b 91 72 b 23 7275 11716239 d 1 711 a 2 22 2 2cos 2sin 7 72 2cos37quot 7sin37quot 715 agt1w11 61 7quot d w2 6 7 5 gm e w 2 07 7 716 01961 95 7 5 77 3 HTquot a 1944 95 5 3 2quot 86 a Q zzii Rz z 817 aiii N0 rational zeros7 yet reducible over Q 45 46 9 Answers to selected exercises ai i2 32 i2 7 3239 aiii is a zero bii 3 22397 73 2239 827 bii three irreducible factors over Q biV reducible over R Ci yes Cii no Ciii yes CiV yes Notes by David Groisser Copyright 1998 Mathematical grammar and correct use of terminology Sentences in mathematical writing often use mathematical symbols These symbols have very precise meanings Some examples are 1 E0 00 4 U 5 L4 77 stands for equals which equals or is equal to It does not stand for Dong the next step in this problem I arrive at the expression to the right of the equals sign V stands for for all for every or for each 3 stands for there exists or there exist i stands for implies implying or which implies stands for which is implied by this can also be read implies if you read from right to left or from the bottom of a page up ltgt stands for if and only if or which is equivalent to C stands for subset in is a subset of as in the sentence W C V a subset of or be a subset of as in the sentence Let W C V A common convention among mathematicians is that in a sentence subset can be also used as a preposition a word like in or on that indicates the relation of two objects to one another Example In Let W C V be a subspace C is a preposition and the sentence is read Let W subset V be a subspace or Let W in V be a subspace If we want the sentence instead to read Let W a subset of V be a subspace we have to punctuate it accordingly Let W C V be a subspace Using mathematical symbols does not relieve the writer of the responsibility to punctuate his or her sentences correctly the symbols do not incorporate punctuation marks Your written work should have the property that when the conventional English meanings of your symbols are substituted for the symbols themselves the result is a collection of sentences with correct grammar and punctuation with logical connections between the sentences In particular this applies to equations which are examples of sentences and to strings of equations which are often used as long sentences that detail the logical ow of an argument A common way to achieve mathematical gibberish is simply to write equations down on a page with no words connecting them to indicate their logical relation to one another A string of equations each of which is implied by the previous one should be unambiguously readable as a grammatical English sentence com plete with punctuation although sometimes a very long and tedious one For example suppose you are asked to do the following problem Show that if z is a positive real number and 2 2x 7 3 07 then x 1 Valid proof Assume z is a positive real number and x2 2x 7 3 0 Then 2 2x 7 3 0 i x 3z 71 07 i z 3 0 or z 71 7 i z 73 or z 1 Since z is positive7 z 31 737 and therefore z 1 I The equation part of this argument reads in English as Then x2 2x 7 3 equals 07 which implies x 3 x 7 1 equals 07 which implies z 3 equals 0 or z 7 1 equals 07 which implies z equals 73 or z equals 1 Gibberish version of same argument z2273 0 z3z71 0 x30 x710 z73 z x1 This reads 2 2x 7 3 equals 0 x 3 x 7 1 equals 0 z 3 equals 0 z 7 1 equals 0 z equals 73 z equals 1 z equals 1 Which way makes more sense Some common mistakes All of the mistakes below were taken from students7 homework in past MAS 4105 classes 1 Mistaken order of quanti ers The symbols V and 3 are called quanti ers The order in which they appear makes a di erence For example7 consider the two statements 1 V persons p 3 a shirt 5 such that 5 ts p 2 3 a shirt 5 such that V persons p7 5 ts p The rst statement says that every person can nd a shirt that ts The second says that there7s one magic shirt that ts every single person E0 Mistakenly using i in place of then Do not replace the construction if then with if i Example of correct usage If x 57 then 2 25 9 7 9 CT Example of correct usage z 5 i 2 25 This reads z 5 implies 2 25 and has cccactly the same meaning as If x 5 then 2 25 Example of incorrect usage If x 5 i 2 25 This reads If x 5 implies x2 25 7 which is not even a complete sentence It also phrases an absolute truth 52 25 as part of a conditional statement Mistaken omission of set brackets 7an l each 11 E R 7an7 where each 11 E R Example of correct usage R a1 Example of incorrect usage R 117 Mistakenly using parentheses instead of curly brackets For example7 if 1 E V or 71 C V Parentheses are used to denote an ordered n tuple7 not a set 111 1 are elements of a vector space V7 it is correct to write 111 111 wn C V 7 but incorrect to write 11771n E V or 111 Mistaken usage of such that or so that Such that means having the property that or have the property that For example Let x be such that u 5 means Let x have the property that f 5 Such that is not used to indicate that something is implied by something else For example7 it is wrong to write Let 2x 107 such that z 5 What you can correctly write instead is Let 2x 107 so that z 5 In contrast to such that7 the phrase s0 that7 when preceded by a comma7 always means that what7s to the right of the comma is implied by what7s to the left So that can be used to mean the same thing as such that in certain cases7 but never if it is preceded by a comma For a valid use of so that to mean such that 7 see the de nition of vector space on p 6 of Friedberg7 lnsel7 and Spence Had the authors preceded so that by a comma7 the meaning would have been entirely di erent Had they replaced so that by such that 7 the meaning would have been the same Here are two more examples Example of incorrect usage Let 111 7 be a basis of R 7 such that any 1 E R is a linear combination of 111 un Example of correct usage Let 111 70 be a basis of R 7 so that any 1 E R is a linear combination of 111 un Example of correct usage Choose vectors 1702 such that cl l 112 lmproper use of the word let The grammatical construction Let X be such and such or Let X have this or that property means Assume X is such and such or Assume X has this or that property It is generally used to x notation at the start of an argument It cannot be used if X is not a variable object eg if X 57 or if X has in the context of that argument already been assumed to be something else7 or if X has already been assumed to have the indicated property7 or if you are about to assume that X has properties that could con ict with those you7ve already assigned it Example of correct usage Let x E R satisfy 2 25 Example of incorrect usage Let x 5 satisfy x2 25 Example of correct usage Let x E R be such that x2 25 Example of correct usage Let x 57 so that 2 25 Further mistakes involving terminology H F 9 The word equation An equation is a sentence with an equals sign in it Expres sions that lack signs are not equations In particular 0 A vector is not an equation 0 A sum of vectors is not an equation 0 A linear combination of vectors is not an equation 0 An inequality is not an equation The word solution Equations and inequalities can have solutions see handout What is a solution However7 o A vector does not have a solution 0 A matrix does not have a solution Miscellaneous 0 In a general vector space7 there is no such thing as division by a vector 0 In a general vector space7 there is no such thing as 1 over a vector 0 You cannot add a scalar to a vector in R unless n 1 o The components of a vector in R are real numbers they are not elements of R unless n 1 o A vector is not the same thing as a vector space A set of vectors does not equal a vector 0 A set of vectors is not the same thing as a linear combination of vectors 0 A basis is not the same thing as the vector space its a basis of A basis is not the same thing as a linear combination of vectors A basis is not the same thing as a sum of vectors A basis is not the same thing as a solution set to a system of linear equations A set of linear combinations of vectors is not the same thing as a linear com bination of vectors A linear combination of vectors is a single vector7 not an in nite set of vectors A set of linear combinations of nonzero vectors is an in nite set of vectors The number of elements in a vector space is not the same thing as the number of elements in a basis of that space The vector space 0 has exactly one element Every other vector space has in nitely many elements For n7 m gt 07 R has just as many77 elements as Rm7 no matter which of nm is larger A plus sign does not mean the same thing as a comma7 or as the word and Do not put plus signs between elements of a list of vectors unless you really mean to add the vectors A matrix is not the same thing as a system of equations One can associate a matrix to a system of equations7 but they are not the same animal


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Steve Martinelli UC Los Angeles

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

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.