### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Linear Algebra MATH 110

GPA 3.93

### View Full Document

## 24

## 0

## Popular in Course

## Popular in Mathematics (M)

This 56 page Class Notes was uploaded by Kavon Feest on Thursday October 22, 2015. The Class Notes belongs to MATH 110 at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 24 views. For similar materials see /class/226605/math-110-university-of-california-berkeley in Mathematics (M) at University of California - Berkeley.

## Reviews for Linear Algebra

### 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/22/15

George M Bergman Math H110 Fall 2008 Supplementary material Some notes on sets logic and mathematical language 4 These are generic notes for use in Math 110 113 104 or 185 This printing is adapted for use in Math 110 with Friedberg Insel and Spence s Linear Algebra Part 1 below has a large overlap with Appendices A and B of that text but I have left it in for completeness and because it gives further examples of the concepts in question These pages do not develop in detail the de nitions and concepts to be mentioned That is done to various degrees in Math 55 Math 74 Math 125 and Math 135 I hope you will nevertheless nd them useful and thoughtprovoking I recommend working the exercises for practice but don t hand them in unless they are listed in a homework assignment for the course 1 Set theoretic symbols Symbol Meaning usage examples discussion Q The empty set N I Here 1N denotes the set of all natural numbers ie 0 1 2 3 while I from Zahl German for number denotes the set of all integers 73 72 71 0 1 2 3 Many older authors started the natural numbers with 1 but it is preferable to start with 0 since natural numbers are used to count the elements of nite sets and Q is a nite set D R 1 Of these 03 for quotient denotes the set of all rational numbers ie fractions that can be written with integer numerator and denominator 1R denotes the set of real numbers and I the set of complex numbers The ve sets just named used to be and often still are denoted by boldface letters N Z Q R and C The forms 1N Ll arose as quick ways to write these boldface letters on the blackboard Since it is convenient to have distinctive symbols for these important sets printed forms imitating the blackboard bold symbols were then designed and are now frequently used as shown However Friedberg Insel and Spence have set up their own convention under which all elds are denoted by italic letters eg F so that in particular the real and complex elds are R and C while vector spaces are sansserif so that the ndimensional vector spaces over F R and C are written Fquot Rquot and Cquot They do not use any symbols for the natural numbers integers or rationals 6 Is a member of Eg 361 The set of all This is often used together with or different authors prefer the one or the other Friedberg Insel and Spence use which stand for such that For instance the set ofpositive integers can be written 12 3 or neZ ngt0 or n nel ngt0 The set of all square integers can be written 0 1 4 9 n2 or n2 ne Z Note also that n2nel m2mel m22m1mel Why Is a subset of Eg Q g 1 g N g I g R C 0 n2 If nel g neZ nZO I g Z C or C Is a proper subset of that is a subset that is not the whole set For instance I g R In fact all the formulas used above to illustrate g remain true with g in place of g except for I g Z Since a proper subset is in particular a subset one may use g even when g is true and one generally does so unless one wants to emphasize that a subset is proper But beware some authors especially in Eastern Europe use C for is a subset of 2 e etc for fX gtY Obvious variants of the above symbols A Q B means B Q A xeX means x is not a member of X A g B means A is nota subset of B etc Warning The phrases A lies in X and A is contained in X can mean either AeX or A gX The former phrase more often means A eX and the latter A gX but this is no guarantee So in your writing if there is danger of ambiguity either use the mathematical symbols or use the unambiguous phrases is a member of and is a subset of Intersection A B x both xeA and x 6B are true For instance xel xgt9 xelR xS 12 1011 12 Intersection of an indexed family of sets For instance if A0 A1 are sets then quot01mAn also written nEWAn OZZOAn and Ao Al GA 0 means x x is a member of all ofAO A1 etc In an intersection WIE1 A I does not have to be a set of integers it can be any set such that Al is de ned for each ie When a set I is used in this way to index ie list other entities it is called an index set Union AUB x xeA or xeB For instance er xgt0 U xel xlt 12 Z Note thatif AgB then AUB B and A BA Union of an indexed family of sets Thus Un01m An UnEW An AOUAI U UAn U Example UnEW ieiN iltn W Often when the intent is clear from context the above notations are abbreviated For instance if we know that we have one set Al for each i in a certain indexset I then instead of UiEIAi we may write U1 Al or UiAZ orjust UAi Likewise if we have a set Xn for each positive integer n the intersection 0 21 Xn may be written Wan or simply W X 7 co 7 T Un0An T Complement of cA means x xeA But x xeA makes no sense if we don t say what x s are allowed So the notation cA is used only when discussing subsets of a xed set For instance if we are discussing subsets of the integers then ceven integers odd integers while if we are considering subsets of G then ceven integers denotes the set consisting of all odd integers and noninteger rationals To be more precise we can use the next symbols AiB or AB means xeA xe B Eg Z 7 even integers odd integers Note that AiB is de ned even if B is not a subset of A For instance I 7 negative real numbers W This indicates that f is a function also called a map or mapping from the set X to the set Y In reading the symbol out loud one can use words such as the map f from X to Y or sending X to Y Such an f is said to be 0net00ne or infective if for every two distinct elements x1 x2 eX the elements fx1 and fx2 of Y are also distinct For instance the operation of cubing an integer is a onetoone function Z gt Z but the squaring map is not onetoone because in n The function f X gt Y is said to be onto Y if every element of Y equals fx for some xe X For instance the squaring and cubing maps Z gt Z are not onto since not all integers are squares or cubes On the other hand the cubing map R gt R is both onetoone and onto Given f X gt Y the set X is called the domain of What about the set at the other end of the arrow A complication is that if f is not onto Y then Y and fx xeX are different sets Traditionally these were called the range and the image of f respectively but the usage was not rm range was often used as a synonym for image Hence nowadays the unambiguous term codomain has been introduced to describe Y A function is called onto if it is onto its codomain a synonymous term is surjective from French sur onto A map f X gt Y that is both onetoone and onto has an inverse map g Y gt X taking each ye Y to the unique element xeX such that fx y Thus f may be thought of as de ning a matching X gt Y under which each element of X is matched with a unique element of Y and vice versa such a matching is called a onetoone correspondence between X and Y So the phrases onetoone and onto function all describe the same thing still another term for this is bijective map bijective meaning both injective and surjective aa 44 invertible function and onetoone correspondence This symbol is used in three di erent ways which are related but not quite the same A lot of confusion can result if they are not distinguished First if f is onetoone and onto then f1 denotes the inverse of f discussed above Secondly if f X gt Y is any map and S is any subset of Y then f1S denotes xeX fxeS called the inverse image or preirnage of S under When f is invertible it is not hard to check that this is precisely the image of the set S under the inverse function f Y gt X However this de nition of f S makes sense even when f is not invertible Finally for ye Y the symbol f1y is often simpli ed to f1y Hence when the symbol f is used you must check whether the context indicates that f is an invertible function If so you can be con dent that f denotes the inverse function if not then f does not stand for a function but is a way of writing inverse images of sets or elements under f While the ordinary arrow referred to above is used to show what the domain and codomain of a function are the attailed arrow shows which element is carried to which Thus f x H 6 means that f is the squaring function de ned by fx x2 We can use this kind of arrow to describe a function without denoting it by a letter eg the function x H x2 which can be read the function xgoestoxz or the function taking x to x2 If A and B are sets AgtltB means the set of ordered pairs a b aeA beB I won t discuss here precisely how an ordered pair is de ned simply think of it as a list of length 2 Note that a function f of two variables one Avalued and one Bvalued which takes values in a set C can be thought of as a map f A gtltB gt C For example addition of integers is a map Z X Z gt Z given by rn n H in n while exponentiation of real numbers using natural numbers as exponents given by x n H xquot is a map R X N gt HQ Likewise A gtltBgtltC denotes the set of ordered 3tuples a b c aeA beB ce C and one de nes a function of three variables as a map on such a triple productset and so on The set AgtltB is called the product or direct product of the sets A and B because if A and B are nite A having rn members and B having n members then A gtltB will have rn n members In analytic geometry one regards the set R X R of pairs of real numbers as labeling the points of the plane The numbers so used are called the Cartesian coordinates of the points after Rene Descartes who developed this approach to geometry Hence one often calls the direct product AgtltB of any two sets their Cartesian product If f X gt Y is a function then x fx xeX g Xgtlt Y is called the graph of f H again the idea comes from analytic geometry Exercise 1 Let X and Y be sets Find conditions on a subset S C XgtltY that are necessary and suf cient for S to be the graph of a function X gt Y Ie necessary and suf cient conditions on S for there to exist a function f X gt Y such that S is the graph of f If these conditions hold will S uniquely determine the function In View of the answer to the above exercise settheorists often de ne a function from a set X to a set Y as a subset of X X Y having the appropriate 2properties The sets AgtltA AgtltA gtltA etc are often written A A3 etc Also if A and B are sets the set of functions from A to B is often written BA since if A is a nite set with in elements and B a nite set with n elements this set of functions will have nm elements 2 Logical connectives Let us begin by noting that there is a kind of inverse relation between statements and possibilities 7 the more statements we make the more we limit the set of possibilities the more possibilities there are the more limited is the set of true statements For instance suppose we are considering an integervalued variable x If we require that x be positive then the set of possibilities we are considering forms the set 1 2 3 If instead we had stated that x is even then the set would have been 74 72 0 2 4 If we impose both conditions then the only possibilities for x are the positive even integers a proper subset of the two sets named More generally if P and Q are any two conditions and we assume that P and Q hold then the set of cases we are allowing is the intersection of the set of cases allowed by P alone and the set of cases allowed by Q alone This will help you remember the next symbol which is similar to m A And If P and Q are two statements then we de ne P A Q to hold if and only if P and Q both hold For example the condition 0 S x S l is an abbreviation of 0 S x A xS l The operation A is called conjunction On the other hand if we want to consider all cases allowed by a condition P and also all cases allowed by Q 7 the union of the two sets of cases 7 then we are considering the condition P or Q holds This is a weaker condition than either P or Q in line with the inverse relation noted above between statements and cases The symbol used is similar to U namely v Or If P and Q are two statements we say that P v Q holds in a situation if P holds or if Q holds possibly both For instance for all real numbers x we have xlt 10 v xgt0 The condition x S y is equivalent to x lt y v x y As another example for all integers a b we have 12 0 v b2 0 v abZ l The operation v is called disjunction The inverse relation between statements and possibilities that we have mentioned is sometimes a cause of confusion Many beginning calculus students when asked to say what real numbers x satisfy x2gtl will describe these as the set of x satisfying xgtl and xlt7l What they mean is that the set consists ofall x satisfying xgtl and all x satisfying xlt7l But the correct way to express this union of cases is not by the conjunction xgtl and xlt7l but by the disjunction xgtl or xlt7l That is xx2gtl 7oo7lUloo xxlt7l U xxgt l xxlt7l vxgt 1 7 Not Eg x y means x y 2 Implies For instance if xe P then xgt2 2 xgt 0 If P and Q are statements then P 2 Q is a statement which is considered to be true in Ch iff all cases except those where P is true but Q is false P 2 Q may also be expressed in words If P then Q or Q if P For instance the true statement xgt2 2 xgt0 can expressed xgt0 if xgt2 There are certain conventions in the everyday nonmathematical use of words such as or and if which we use unconsciously but need to become aware of so as to understand that they do not apply to mathematical usage In everyday life we generally use the word or only when we do not know which of the two possibilities is true Eg if a letter comes in the mail and you say This is either from John or Stephanie you are asserting that it is from one of them but also implicitly that you do not yet know which one There are variants on this convention If you say I am holding a penny in either my right hand or my left hand then you know which hand it is in but the person you are speaking to does not On the other hand a mathematical statement P vQ is considered to be true even when we do know which of P or Q holds For instance we have noted that for all real numbers x xlt 10 v xgt 0 So in particular the statement 100 lt 10 v 100gt 0 is true and so is 5 lt10 v 5 gt 0 and so is 0 lt10 v 0gt 0 Of course a mathematician does not pointlessly write down P vQ when he or she and the reader both know that P is true or both know that Q is true any more than a nonmathematician would But it must be understood that P vQ is true in such cases in order that the truth of a mathematical statement not be lost when our knowledge increases Similarly in nonmathematical usage we generally make statements of the form If P then Q only when there is some uncertainty as to whether the statements P andor Q hold but again to make mathematical usage consistent we must accept P 2 Q as true in all cases except when P holds and Q does not Note also that in nonmathematical usage P or Q sometimes means P or Q but not bot Eg in the John or Stephanie example and the which hand example above In mathematical usage the meaning of or is not restricted in that way so 5 lt 10 v 5 gt 0 is a true statement P2 Q means P2 Q AQ2P ie P is true if and only if Q is true synonymous with if and only if often abbreviated by mathematicians to iff Thus 2 is The next two exercises give some practice with the logical connectives described in this section Exercise 2 Suppose x is an element and A B are sets Find for each statement in the lefthand column below the logically equivalent statement in the righthand column There is one statement in the righthand column not equivalent to any of the statements in the lefthand column xeAUB xeAxeB xeA B xeA2xeB xe cA xeA Ax B xe A B xeA xeA vxe B Exercise 3 Suppose P and Q are two mathematical assertions Examples might be ngt0 and n is even if we are talking about an integer n Find for each statement in the lefthand column below the logically equivalent statement in the righthand column There are two statements in the righthand column not equivalent to any of the statements in the lefthand column FAQ QgtP Pv Q QAP P 43 Q PvQ P AHQ PAQ P th P General warning Do not confuse statements called by logicians propositions with sets For instance if X is a statement eg 11gt 10 then it makes no sense to write ueX or an And if X and Y are sets then Xgt Y makes no sense There are of course important relations between statements and sets For instance if X and Y are sets then XgY is a statement while if Px is a statement about a real number x then xe IR Px 1s a set 3 Quanti ers Here are two symbols that are extremely important in constructing mathematical statements V For all or for every If we are referring to real numbers then V x n12 x2 2xl is a true statement so is V x xlt0 v x 0 v xgt 0 Referring to integers n the statement V n 2n7 1 gt 0 is true though it is not true for real numbers To make such formulas precise we should show what class of possible n we are talking about We can do this by writing for instance V ne 2 2n7 1 gt 0 For greater clarity parentheses may be introduced eg V nel 2n7 l2gt0 or V nel 2n7 1 gt 0 El There exists such that or for some For example El xel xgt 10 says that there exists an element x belonging to the set of integers and such that xgt 10 or brie y There exists an integer greater than 10 Similarly El xe R x2 square is 3 Both of these are true statements Still another way of reading El xe IR is For at least one real number x it is true that Some people also write El or Ell to mean For exactly one value or equivalently There exists a unique value such that 3 means There exists a real number whose Exercise 4 Suppose Px and Qx are statements about an integer x Examples of such statements are xgt 0 x is odd x 55 xx etc In each of the cases below if you believe that the equivalence asked about holds say brie y why while if you decide that two statements are not equivalent try to nd an example of propositions P and Q for which one of the statements is true and the other is not a Is V x Px equivalent to El x Px b Is El x Px A Qx equivalent to 3 x Px A 3 x Qx c Is V xe 1 2 3 Px equivalent to P l A P2 A P3 d Is V x Px equivalent to V x Px Exercise 5 To show that the statement El xe Z x2 x is true it is enough to give the single example x 0 Suppose Px is a statement about an element x and we want to prove one of the statements below In which cases can this be done by giving just a single example In each such case say what the nature of the example must be 1 a El x Px b VxPx C V x 39Px d 39V x Px Exercise 6 Suppose A and B are sets Translate each of statements ab below which are expressed using the symbols V and El into a statement about and B expressed using only the settheoretic symbols discussed in the rst section of this note a V x 96614 gt 9663 C V 96 Xe1 b V x 96614 Cgt 66 3 d El 96 NA MICE 3 Exercise 7 Suppose A0 A1 A2 are subsets of a set X a Match each set on the left with the set on the right that is equal to it UiEWAZ xeXE ielN xeAi WIEN Al xeX V ie N xeAi b Show that one has the equality xeX El ielN xeAi xeX V ie N xeAi if and only if the sets A0 A1 A2 are all equal Note The English word any sometimes means V and sometimes El we usually understand which is meant from context Thus if you say I wonder whether anyone knows you are asking whether El x x knows is true But the sentence Anyone you ask will be able to tell you means V x If you ask x x can tell you Hence in learning to use the mathematical symbols V and El you must pay attention to the meanings of statements not just the English words used Bound and free variables Suppose we write an equation such as x5 x There are various things that we may mean i x may represent a de nite number that we are considering eg the height of a certain bridge in meters or the greatest common divisor of 2 fl and 2 71 In this case x x is an assertion about that number This assertion is either true or false ii We may regard x5 x as a condition on integers x This is then satis ed by some integers and not by others Taken by itself it is neither true nor false iii We may be asserting x5 x as an identity Eg if we are considering integers then by x5 x we would really mean V xe Z x x which is false On the other hand in Math 113 one encounters the ring Z5 and x x is a valid identity in that ring ie V xe Z5 x x is true iv We may use the equation x5 x in the proposition El xe Z x5 x which is true v We may use the equation x5 x in de ning the set xe Z x5 x which equals 71 0 1 In use i x is a constant it represents a speci c number we are talking about even if we don t know its value and as we have said the statement x x is then true or false In uses iiv x is a variable But there is a difference between ii and the other cases In ii x x is a condition in which we may substitute different values of x making the condition true or false x is called afree variable In iii and iv the variable is bound by the quanti er V or El One cannot ask whether the statement El xe Z x x is true for x 3 although one can ask whether x x is true for x3 Similarly it makes no sense to ask whether V xe Z x x is true for x l or for x 2 because it is not a statement about a single integer x but a statement whose validity is determined by substituting all integers for x in the statement x x and seeing whether it holds in every case It doesn t so as mentioned in iii above V xe Z x5 x is false One could avoid the ambiguity of x5 x meaning either i ii or iii by insisting that different letters be used for constants and variables and that the symbol V xeX be written whenever it is meant We shall not impose such strict rules but we should always understand what we mean and be explicit when necessaryfor clarity A bound variable is an example of the more general concept of a dummy variable This is a variable symbol say x which occurs within an expression but such that the expression is not a function of x39 rather the value of the expression is determined by some process that involves considering different values of x We have seen how this is so in iii and iv The x in v is also a dummy variable because the set in question is determined by looking over all values of x in Z and collecting those which satisfy x You have seen similar situations in calculus recall the difference between formulas like x and 261 x The rst is a function of x while the second represents a speci c number 385 computed with the help of the rst function Likewise in the expression F0 x dx x is a dummy variable There is a sixth meaning that x x can have which one learns about in the latter half of Math 113 Under this interpretation x is an indeterminate in a polynomial ring such as x I will say no more about this here except that so interpreted the equation x x is false since x and x are different polynomials and that this interpretation is like i in that x is a particular element rather than a X 10 variable Exercise 8 a Give an elementary description of xe P El ye P x lt y lt x2 and prove it is orrect Suggestion First gure out by experimentation which real numbers belong to that set then think about how to prove the answer you get To do so you will need to prove two sets equal namely the set given above and the set you describe Two sets X and Y are equal if and only if every element of X is an element of Y and vice versa So to prove such an equality one can begin Let reX and deduce from what is known that re Y and then turn around and say Now let re Y and deduce from what is known that reX b Give an elementary description of xe R El ye Z x lt y lt x2 and prove it is correct 5 Order of quanti ers If we take a sentence about integers involving a free variable x and attach to it one of the pre xes El xe Z or V xe Z then we have seen above that we get a new statement in which x is a bound variable Now consider a sentence with two free variables such as y x and y Suppose that we add to this the pre x El xe Z getting the statement El er y x2 Then x has been bound and the result is a condition on the integervalued variable y in words y is a square For some values of y this is true namely 0 l 4 9 For other values it is false In particular since the set of y for which this condition is satis ed is nonempty it is true that El ye ZE xe Z y x2 Since the set does not contain all integers it is false that V ye ZE xe Z y x2 These examples illustrate the process of adding several pre xes to a statement so as to successively bind several variables Consider now the statement about two integers x and y x gt y Note that the statement El xe Z x gt y is true for all y because there is no largest integer y Hence VyeZEer x gt y is a true statement On the other hand the statement V ye Z x gt y is not true for any integer x39 if it were then x would be an integer larger than all integers including itself Hence 2 a condition on a pair of integers x El erVyel x gt y is a false statement Since one statement is true and the other false they do not mean the same thing so a change in the order of the pre xes El xe Z and V ye I can change the meaning of a statement Exercise 9 Consider the sentence There is someone at the hotel who cleans every room Explain two ways this sentence can be interpreted and translate them into two quanti cations of the relation X cleans R Which words in the sentence correspond to El in the translation and which to V Ambiguities in the meanings of English sentences like the one in the above exercise are generally cleared up by context So I repeat what I said at the end of section 3 in translating a sentence into symbols we must look at the idea not just the words to see how the quanti ers should be used Some mathematicians treat V simply as an abbreviation of the words for all and put it where they might put those words in a sentence writing things like n1 gt n V n I strongly advise against this under that usage a formula El x Px y V y has exactly the ambiguity illustrated in the above exercise since one might bracket it either as El x Px y Vy or as El x Pxy Vy Rather I recommend putting quanti cation symbols before the statement being quanti ed as in the examples given above In the next exercise you will get practice with quanti ers by using them to write symbolically some de nitions that were given with the help of words in freshman calculus Exercise 10 Let f P gt P be a realvalued function of one real variable Translate conditions iivi listed below into symbols Since all variables here are realvalued you may omit e R Part i is done for you as an example In your answers do not use symbols such as limux u or ddx since these are the concept you are trying to de ne Use only basic operations and relations of the real numbers such as 7 lxl gt lt etc In this exercise don t even use in later parts concepts you have de ned in earlier parts rather if appropriate incorporate the symbols of the earlier translation into the later one ou may use letters such as e and 6 for some of your variables but do not write things like 6x to mean a number 6 which may depend on x or by the same token f x Rather the order of quanti ers in your answers should show what can and what cannot depend on what i f is bounded Answer EIMV x lfxl lt M ii f is continuous at the point xe HQ iii f is everywhere continuous iv f has a limit as x gt 00 v f is differentiable at x 5 vi f is everywhere differentiable We end with a quick selftest on material from the preceding sections Exercise 11 Mark the following true or false Answers at the bottom of page a W627 f Elxe Vye xy b N C I g 3x603 Vye x y c I UQ C h VxeCD EIyeCD x y d Z iN W i Vxe Elye x y e If subsets A and B ofa set X 139 El xe G3 Vye Z x y satisfy A B Q then A XiB 10 6 Some mathematical language There are several turns of phrase used in mathematical writing that one generally picks up by seeing how they are used But it can be helpful to have explanations available so I give below at the suggestion of John Peloquin a glossary of some of these phrases necessary and sa icient conditions To say that a statement A is necessary and suf cient for a statement B to hold simply means that A C B For instance if x is a real number a necessary and suf cient condition for limnam xn 0 to hold is that xl lt 1 In this usage suf cient refers to the forward implication A z B and necessary to the reverse implication A c B and these words can be used separately So in considering whether a sum of integers m n is even we see that a su icient condition is that both m and n be even but it is not necessary while for m n to be odd a necessary condition is that at least one of m and n be odd but it is not suf cient When one proves a statement of the form A C B by proving the implication rst in one and then in the opposite direction the proof that A z B is often called the proof of su iciency and the proof that A c B the proof of necessity A necessary and suf cient condition for something to be true is called a criterion for it to be true one also speaks of necessary criteria and suf cient criteria which just go one way For instance most of the tests for convergence of a series 2 an that one learns in calculus are su icient criteria for convergence but the statement that for 2 an to converge one must have lim an 0 is a necessary I I n gt co criterion If one proves a necessary and suf cient condition for an element x to have a certain property this is called a characterization of the elements that have that property to identify To identify two mathematical objects means to regard them as the same For instance when we consider the geometry of the plane R x y xye R and of threedimensional space R xy Z xy 26 R we often regard R 2 as a subset of R 3 by identifying each point xy of the plane with the point x y 0 of 3space we thus identi R 2 with the xyplane xy Z Z 0 in R How one justi es regarding two different things as the same in a precise logical science such as mathematics takes some pondering In examples like the above it can be thought of as a notational shorthand we can say that when we speak about points and subsets of the plane R as lying in 3dimensional space we mean the images of those points under the map p R gt R de ned by pxy x y 0 and because p preserves geometric structure eg distance the property of lying in a straight line etc geometric statements about points of R remain true of their images under p Some other uses of the term are a little different For instance the unit circle parametrized by radian measure is sometimes described as the interval 027r with the two ends 0 and 27 identi ed I will not go into how to think of this sort of identi cation here wellde ned When one gives a statement that is supposed to be a de nition it is sometimes necessary to verify that it really does precisely de ne some mathematical object For instance if we tried to de ne a function a from positive rational numbers to positive rational numbers by saying that whenever r mn with m and n positive integers we let ar m ln l we would face the problem that a positive rational number can be written in more than one way as a ratio of positive integers eg 23 46 so we would need to know whether our de nition depended only on the given rational number r or on the Answers to Exercise 11 a F b T c T d T e F f F g F h T i T j T 11 way we chose to write it as a ratio rnn In fact we see that 2 l3 1 and 4 l6 1 are not the same rational number so the above is not a usable de nition On the other hand if for rn n we de ne br in n we nd that this rational number does not depend on our choice of how to write r as a ratio In fact br r2 If some entity we have de ned is indeed determined by the rules we have stated rather than varying with choices implicit in our de nition we say that it is wellde ned Proofs of wellde nedness become essential in areas of mathematics where certain entities are de ned as equivalence classes of other entities and operations on them are de ned by choosing representatives of these equivalence classes performing operations on these and taking the equivalence class of the resulting element This is not the place to go into those constructions but you will see proofs of well de nedness coming up frequently when you study such topics unique The unique element having a property means the only element with that property Thus in mathematics the word unique is always used relative to the statement of some property 7 often mentioned in the same sentence but sometimes implicit in the context For instance 2 is the unique real number x such that x3 8 so that equation has a unique solution in R On the other hand the equation x2 4 does not have a unique solution in R since both 2 and 72 are solutions I have actually used the word unique four times in the preceding pages of this note trusting that most students either knew its mathematical meaning or would recognize what I meant up to This phrase allows one to modify a statement so as to allow more leeway For instance if a is a positive real number then the equation x a has a realnumber solution which is unique up to Sign This means that if x1 and x2 are both solutions to that equation we do not assert that x1 x2 as we would if we simply said that the solution was unique but rather that x1 i x2 Likewise if fx is a continuous function on the real line then there is a function g whose derivative is f and this g is unique up to or determined up to an additive constant In High School geometry when one learns that a triangle is determined by sideangleside ie by the lengths of two sides and the value of the angle between them a fuller statement would be that the triangle is determined up to congruence by this data In other words triangles that agree in this data must be congruent but need not actually consist of the same points of the plane The fact that most geometry textbooks do not add up to congruence to such statements means that in these statements they are identi ing congruent triangles without loss afgenerulity In giving a mathematical proof if we say that without loss of generality we may assume that some condition X holds this means that we can establish the result in the case where X holds we can deduce from this that it holds in general After saying this one usually assumes that X holds for the rest of the proof For instance in proving a theorem about a function f on an interval 1 b an author might say Without loss of generality we may assume 1 b 01 Typically the reason is that if f is a function on 11 b then the function g on 0 1 de ned by gx fabia x has properties closely corresponding to those of the original function For instance g0 fa gl fb g is differentiable if and only if f is differentiable etc Depending on the theorem one is trying to prove one may be able to see that knowing the theorem is true for the above function g implies that it is true for In that case it suf ces to go through the details of one s proof for functions on 01 and if this makes the proof easier to write out or to follow one may say Without loss of generality we shall assume 1 b 01 and complete the proof under that assumption Of course whether it is clear that knowing a result in one case implies that it is true in the other case depends on the situation and on the mathematical background of one s readership If the author of a text you are reading says without further explanation that without loss of generality some assumption may 12 be made this means that he or she judges that the reduction to that case should be straightforward for students at the level at which the text is aimed and you should take up the challenge and see whether you can supply the reason If you can t you should ask your instructor In other cases an author may say explicitly why a without loss of generality statement is justi ed You should then look carefully at the arguments by which he or she reduces the general case to the special case Mathematicians writing for other mathematicians often abbreviate without loss of generality to wlog but this abbreviation seldom appears in undergraduate textbooks The turns of phrase listed above are ones that I have seen students have a great deal of trouble with The next couple haven t led to problems as often but they are also worth noting once one has mastered the preceding ones maximal This is a term that is used in the context of sets that have among their members a relation of some being greater than others This is not the place to discuss the various ways in which such relations arise so I will just talk about one case sets with the greater than relation being the relation of one set containing another So suppose S is some set of subsets of a set X Then an element Ae S is said to be maximal in S if no other member of S contains it For instance if we take X 1 2 3 4 5 and let S consist of all subsets of X that do not contain any two adjacent integers integers that are next to each other in the list 1 2 3 4 5 then 1 g 13 g 135 are members of S and these inclusions imply that 1 and 13 are not maximal elements of S You might check for yourself that S has exactly four maximal elements 1 3 5 1 4 2 4 and 2 5 An element in such a set which contains all other elements is called a greatest element of the set If a set has a greatest element that will also be a maximal element but as the example of the preceding paragraph shows not every maximal element is a greatest element39 the set S of that paragraph does not have a greatest element An example of a set that has no maximal elements and hence also no greatest element is the set of all nite subsets of W by choice of This is best illustrated by an example If in an argument one has said Suppose the polynomial fx has a positive root r then if one later says that something is true by choice of r this means it is true because r is a root of fx or because r is positive or because both these statements are true in other words because of the assumptions we made when we speci ed r So the phrase by choice of is a signal to look back at the point where an element was introduced and see what was assumed about it Let me end with a warning about an incorrect use of words I have often seen students make If one wants to describe a2 rte I it is not correct to call this the set containing all squares of integers because there are many sets that t those words For instance the set of all positive integers and the set of all real numbers both contain all squares of integers along with other elements The correct description of n2 rte Z is the set of all squares of integers If for some reason one wants a more emphatic word than of one may say the set consisting of all squares of integers or the set whose members are all squares of integers Math 110 Fall 05 Lectures notes 15 Oct 3 Monday Our goal is to study inverses of linear transformations Def Let T V gt W be linear A function U W gt V is called an inverse of U of T if 1 UT V gt V is the identity function UT IV on V ie lVv v for all v in V 2 TU W gt W is the identity function TU IW on W ie lWw w for all w in W If T has an inverse we call T invertible and write U T 1 As noted in App B inverse are unique From now on we will assume that V and W are finite dimensional Recall our earlier theorem Thm 1 T V gt W is invertible if and only if rankT dimW dimV Lemma 1 Let T V gt W and S W gt Z both be invertible Then ST V gt Z is invertible and ST 1 T 1 S 1 2 if it exists then T 1 W gt V is linear 3 T 1 W gt V is invertible too and T 1 1 T Proof 1 If T is invertible it makes a 1 to 1 correspondence between V and W via Tv w Similary S creates a 1 to 1 correspondence between W and Z via Sw 2 So STv z is a 1 to 1 correspondence between V and Z so ST is invertible If STv 2 then we need to show v T 1S 1z v IV v def of IV T 1Tv def of T 1 T 1Tv def of function composition T 1IWTv def of lW T 1S 1STV def of S 1 T 1S 1STv associativity of composition T 1S 1Z def of STv so T 1S 1 is the inverse of ST 2 We need to show T 1cx1x2 cT 1X1 T 1X2 Let T 1X1 yl and T 1X2 y2 or Tyl X1 and Ty2 X2 Then T 1CX1 X2 T 1cTy1 Ty2 def of y1y2 T 1TCy1y2 T linear cy1y2 T 1T IV cT 1x1T 1x2 def of y1y2 3 Apply def of inverse to T 1 to see that its inverse is T Continuing our goal of connecting properties of linear transformations and matrices we define Def Let A be an n by n matrix Then A is invertible if there is an n by n matrix B such that AB BA In n x n identify matrix Thm 2 Let V and W be finite dimensional vectors spaces with ordered bases beta and gamma resp Let T V gt W be linear Then T is invertible if and only if Tbeta gamma is invertible in which case Tbeta gamma 1 T 1gamma beta Proof Suppose T is invertible Then by Thm 1 dimV dimw n and so Tbeta gamma is n x n Now T 1T IV and so In IVbeta beta by def of IV T 1Tbeta beta T 1gamma beta Tbeta gamma by an earlier theorem and similarly In IWgamma gamma by def of IW T T 1gamma gamma Tbeta gamma T 1gamma beta So T 1gamma beta satisfies the definition of the inverse of matrix Tbeta gamma Now suppose A Tbeta gamma is invertible let B be the inverse We need to show T is invertible and BT 1gamma beta Let beta v1vn and gamma w1wn and define U w gt V by Uwj sumi1 to n Bijvi We will show that U T 1 TUwj Tsumi1 to n Bijvi by def of Uwj sumi1 to n BijTvi since T linear sumi1 to n Bijsumk1 to n Akiwk by def of Tvi sumi1 to n sumk1 to n BijAkiwk move Bij into summation sumk1 to n sumi1 to n BijAkiwk reverse order of summation sumk1 to n wk sumi1 to n BijAki move wk out of inner summation sumk1 to n wk ABkj def of matrix product AB sumk1 to n wk lnkj since AB In wj def of In Since lWwj wj for all j too by uniqueness we have TU IW One can similarly show UTvi vi and so UT IV EX T R 2 gt R 2 where TX1X2 X1 2X2 2X1 X2 beta gamma e1e2 standard ordered basis T is invertible because we can solve TX1X2 y1y2 for X1X2 given any y1y2 as follows y1 X1 2X2 gt y22y1 3X2 gt X2 23y1 13y2 y2 2X1 X2 gt X1 y1 2X2 13y1 23y2 and T 1y1y2 13y1 23y2 23y1 13y2 so T 1gamma beta 13 23 23 13 Also Tbeta gamma Te1gamma Te2gamma 1 2gamma 2 1gamma 1 2 2 1 and so Tbeta gamma 1 1 2 2 1 det 1 2 2 13 T 1gamma beta as expected Corollary If V W and beta gamma and T V gt W is invertible then Tbeta 1 T 1beta Proof Follows from Thm 2 Corollary Let A be an n X n matriX Then A is invertible if and only if LA is invertible Proof Homework Dne to one correspondences have a special name when they are linear Def Let V and W be vector spaces If there is an invertible linear transformation T V gt W then we say V and W are isomorphic vector spaces and T is called an isomorphism EX V R 2 W P1R Ta1a2 a1 a2X is an isomorphism Thm Let V and W be finite dimensional vector spaces Then they are isomorphic if and only if dimV dimW Proof If V and W are isomorphic let T V gt W be an isomorphism Then we know T is invertible if and only if rankT dimV dimW Now suppose dimV dimW n Let beta v1vn and gamma w1wn be ordered bases for V and W resp Define T by Tvi wi for i1n Then RT spanTv1Tvn spanw1wn W so rankT n dimW dimV so T is an isomorphism Corollary Let V be a vector space over F Then V is isomorphic to F n if and only if n dimV Thm Let V and W have finite dimensions n and m resp with ordered bases beta and gamma resp Then Phi LVW gt Mm X nF defined by PhiT Tbeta gamma is an isomorphism Proof We have proved most of this already We know Phi is linear It is one to one because the property of a basis implies that sumi aiwi 0 if and only if all ai 0 so the only way Tbeta gamma can be the zero matrix is if Tvi OW for all i implying Tv O for all v It is onto because given a matrix A if we define Tvi sumj1 to n Ajiwj then T is linear and Tbeta gamma A George M Bergman Spring 2006 Supplementary material Some notes on sets logic and mathematical language These are generic notes for use in Math 110 113 104 or 185 These pages do not develop in detail the de nitions and concepts to be mentioned That is done to various degrees in Math 55 Math 74 Math 125 and Math 135 I hope you will nevertheless nd them useful and thought provoking I recommend working the exercises for practice but don t hand them in unless they are listed in a homework assignment for the course 1 Settheoretic symbols Symbol Q W l D P l E Q C or g 2 65 etc Meaning usage examples discussion The empty set Here lN denotes the set of all natural numbers ie 0 1 2 3 while I from Zahl German for number denotes the set of all integers 3 2 1 0 1 2 3 Many older authors started the natural numbers with 1 but it is preferable to start with 0 since natural numbers are used to count the elements of nite sets and Q is a nite set Of these 03 for quotient denotes the set of all rational numbers ie fractions that can be written with integer numerator and denominator P denotes the set of real numbers and G the set of complex numbers The ve sets just named used to be and often still are denoted by bold face letters N Z Q R and C The forms iN G arose as quick ways to write these boldface letters on the blackboard Since it is convenient to have distinctive symbols for these important sets printed forms imitating the blackboard bold symbols were then designed and are now frequently used as shown Is a member of Eg 361 The set of all This is often used together with or different authors prefer the one or the other which stand for such that For instance the set of positive integers can be written 1 23 or n61 ngt0 or n nEZ ngt0 The set of all square integers can be written 0 14 9 n2 or n2 n62 Note also that n2 n61 m2 mEZ m22m1mEZ Why Is asubset of Eg Q Q 1 Q W E I Q P Q E n2 n61 Q n62 n20 I Q I Is a proper subset of that is a subset that is not the whole set For instance I g R In fact all the formulas used above to illustrate Q remain true with g in place of Q except for I E Z Since a proper subset is in particular a subset one may use Q even when E is true and one generally does so unless one wants to emphasize that a subset is proper But beware some authors especially in Eastern Europe use C for is a subset of Obvious variants of the above symbols A 2 B means B Q A fo means x is not a member of X A 2 B means A is not a subset of B etc Warning The phrases A lies in X and A is contained in X can mean either AEX or Ag X The former phrase more often means AEX and the latter Ag X but this is no guarantee So in your writing if there is danger of ambiguity either use the mathematical symbols or use the unambiguous phrases is a member of and is a subset of or fX gtY Intersection A B x both xEA and x63 hold For instance x61 xgt 9 xElR xs 12 10 11 12 Intersection of an indexed family of sets For instance if A0 A1 are sets then 110 1 NA also written WHEN A n ii A and A00 A1 0 0 A 0 means x xis a member of all of A0 A1 etc In an intersection IIEl A n i I does not have to be a set of integers it can be any set such that Al is de ned for each iEI When a set I is used in this way to index ie list other entities it is called an index set Union AUB x xEA or xEB For instance x61 xgt0 U xEZ xlt12 Z Note that if A Q B then AUB 3 and A03 A Union of an indexed family of sets Thus Un0 1 A AOUAI U UAn U Example U EW iEiN iltn w Often when the intent is clear from context the above notations are abbreviated For instance 00 Un0A UnElNAn n if we know that we have one set Al for each i in a certain index set I then instead of UiEI Ar each positive integer n the intersection f1 X may be written an X or simply I X we may write U1 Al or Ui Al or just U Ai Likewise if we have a set X for Complement of 0A means x xEA But x xEA makes no sense if we don t say what x s are allowed So the notation CA is used only when discussing subsets of a xed set For instance if we are discussing subsets of the integers then 0even integers odd integers while if we are considering subsets of Q then 0even integers denotes the set consisting of all odd integers and non integer rationals To be more precise we can use the next symbols AiB or AB means xEA x653 Eg ZZ even integers odd integers Note that A73 is de ned even if B is not a subset of A For instance I negative real numbers W This indicates that f is a function also called a map or mapping from the set X to the set Y In reading the symbol out loud one can use words such as the map f from X to Y or sending X to Y Such an f is said to be aneitaiane or infective if for every two distinct elements x1 x2 EX the elements fx1 and fx2 of Y are also distinct For instance the operation of cubing an integer is a one to one function Z gt Z but the squaring map is not one to one because n2 n2 The function f X gt Y is said to be onto Y if every element of Y equals fx for some xEX For instance the squaring and cubing maps Z gt Z are not onto since not all integers are squares or cubes On the other hand the cubing map P gt P is both one to one and onto Given f X gt Y the set X is called the domain of f What about the set at the other end of the arrow A complication is that if f is not onto Y then Y and fx xEX are different ss sets Traditionally these were called the range and the image of f respectively but the usage was not rm range was often used as a synonym for image Hence nowadays the unambiguous term codomain has been introduced to describe Y A function is called onto if it is onto its codomain a synonymous term is surjective from French sur onto A map f X gt Y that is both one to one and onto has an inverse map g Y gt X taking each yEY to the unique element xEX such that fx y Thus f may be thought of as de ning a matching X lt gt Y under which each element of X is matched with a unique element of Y and vice versa such a matching is called a oneitoione correspondence between X and Y So the phrases one to one and onto function invertible function and one to one correspondence all describe the same thing still another term for this is bijective map bijective meaning both injective and surjective This symbol is used in three di erent ways which are related but not quite the same A lot of confusion can result if they are not distinguished First if f is one to one and onto then f71 denotes the inverse of f discussed above Secondly if f X gt Y is any map and S is any subset of Y then f 1S denotes xEX fx ES called the inverse image or preimage of S under f When f is invertible it is not hard to check that this is precisely the image of the set S under the inverse function fil Y gt X However this de nition of f 1S makes sense even when f is not invertible Finally for yEY the symbol f 1y is often simpli ed to f 1y Hence when the symbol fil is used you must check whether the context indicates that f is an invertible function If so you can be con dent that f71 denotes the inverse function if not then f71 does not stand for a function but is a way of writing inverse images of sets or elements under f While the ordinary arrow referred to above is used to show what the domain and codomain of a function are the at tailed arrow shows which element is carried to which Thus f x t x2 means that f is the squaring function de ned by fx x2 We can use this kind of arrow to 2 describe a function without denoting it by a letter eg the function x H x which can be read the function x goes to x or the function taking x to x2 If A and B are sets AxB means the set of ordered pairs a b aEA bEB I won t discuss here precisely how an ordered pair is de ned simply think of it as a list of length 2 Note that a function f of two variables one A valued and one B valued which takes values in a set C can be thought of as a map f AxB gt C For example addition of integers is a map I XI gt Z given by m n 39 gt mn while integer exponentiation given by m n a m is a map I X W gt Z Likewise AxB xC denotes the set of ordered 3 tuples a b c aEA bEB cEC and one de nes a function of three variables as a map on such a triple product set and so on The set AxB is called the product or direct product of the sets A and B because if A and B are nite A having in members and B having n members then A xB will have mn members In analytic geometry one regards the set P x P of pairs of real numbers as labeling the points of the plane The numbers so used are called the Cartesian coordinates of the points after Rene Descartes who developed this approach to geometry Hence more generally one often calls the direct product AxB of any two sets their Cartesian product If f X gt Y is a function then x fx xEX Q Xx Y is called the graph of f again the idea comes from analytic geometry Exercise 1 Let X and Y be sets Find conditions on a subset S Q XX Y that are necessary and suf cient for S to be the graph of a function X gt Y Ie necessary and suf cient conditions on S for there to exist a function f X gt Y such that S is the graph of f If these conditions hold will S uniquely determine the function In view of the answer to the above exercise set theorists often de ne a function from a set X to a set Y as a subset of Xx Y having the appropIiate properties The sets A xA A xA xA etc are often written A2 A3 etc Also if A and B are sets the set of functions from A to B is often written BA I won t go here into the set theoretic ideas behind these conventions 2 Logical connectives Let us begin by noting that there is a kind of inverse relation between statements and possibilities the more statements we make the more we limit the set of possibilities the more possibilities there are the more limited is the set of true statements For instance suppose we are considering an integer valued variable x If we require that x be positive then the set of possibilities we are considering forms the set 1 23 If instead we had stated that x is even then the set would have been 4 2 0 2 4 If we impose both conditions then the only possibilities for x are the positive even integers a proper subset of the two sets named More generally if P and Q are any two conditions and we assume that P and Q hold then the set of cases we are allowing is the intersection of the set of cases allowed by P alone and the set of cases allowed by Q alone This will help you remember the next symbol which is similar to 0 A And If P and Q are two statements then we de ne P A Q to hold if and only if P and Q both hold For example the condition 0 s x s 1 is an abbreviation of 0 s x A x5 1 The operation A is called conjunction On the other hand if we want to consider all cases allowed by a condition P and also all cases allowed by Q the union of the two sets of cases then we are consideIing the condition P or Q holds This is a weaker condition than either P or Q in line with the inverse relation noted above between statements and cases The symbol used is similar to U namely v Or If P and Q are two statements we say that P v Q holds in a situation if P holds or if Q holds possibly both For instance for all real numbers x we have xlt 10 v xgt0 The condition x s y is equivalent to xlty v xy As another example for all integers a b we have a2 0 v b2 0 v abz 1 The operation v is called disjunction The inverse relation between statements and possibilities that we have mentioned is sometimes a cause of confusion Many beginning calculus students when asked to say what real numbers x satisfy x gt1 will descIibe these as the set of x satisfying xgt1 and xlt 1 What they mean is that the set consists of all x satisfying xgt1 and all x satisfying xlt 1 But this union of cases corresponds not to the conjunction xgt1 and xlt 1 but to the disjunction xgt1 or xlt 1 That is x x2gt1 00 1U1oo x xlt 1Ux xgt 1 xxlt 1vxgt1 iff Not Eg ux y means x a y Implies For instance if xEP then xgt2 gt xgt 0 If P and Q are statements then P gt Q is a statement which is considered to be true in all cases except those where P is true but Q is false P gt Q may also be expressed in words If P then Q or Q if P For instance the true statement xgt2 gt xgt0 can expressed xgt0 if xgt2 There are certain conventions in the everyday nonmathematical use of words such as or and if which we use unconsciously but need to become aware of so as to understand that they do not apply to mathematical usage In everyday life we generally use the word or only when we do not know which of the two possibilities is true Eg if a letter comes in the mail and you say This is either from John or Stephanie you are asserting that it is from one of them but also implicitly that you do not yet know which one There are variants on this convention If you say I am holding a penny in either my right hand or my left hand then you know which hand it is in but the person you are speaking to does not On the other hand a mathematical statement P v Q is considered to be true even when we do know which of P or Q holds For instance we have noted that for all real numbers x xlt 10 v xgt 0 So in particular the statement 100lt 10 v 100gt 0 is true and so is 5lt 10 v 5gt 0 and so is 0lt 10 v 0gt 0 Of course a mathematician does not pointlessly write down P v Q when he or she and the reader both know that P is true or both know that Q is true any more than a nonmathematician would But it must be understood that P v Q is true in such a cases in order that the truth of a mathematical statement not be lost when our knowledge increases Similarly in nomnathematical usage we generally make statements of the form If P then Q only when there is some uncertainty as to whether the statements P andor Q hold but again to make mathematical usage consistent we must accept P gt Q as true in all cases except when P holds and Q does not Note also that in nonmathematical usage P or Q sometimes means P or Q but not both Eg in the John or Stephanie example and the which hand example above In mathematical usage the meaning of or is not restricted in that way so 5lt 10 v 5gt 0 is a true statement as Pltgt Q means Pgt Q AQgtP ie Thus ltgt is synonymous with if and only if often abbreviated by mathematicians to iff P is true if and only if Q is true The next two exercises give some practice with the logical connectives described in this section Exercise 2 Suppose x is an element and A B are sets Find for each statement in the left hand column below the logically equivalent statement in the right hand column There is one statement in the right hand column not equivalent to any of the statements in the left hand column xEAUB xEA xEB xEA B xEAgtxEB x6 CA xEA xEB xEAB xEA xEA v xEB Exercise 3 Suppose P and Q are two mathematical assertions Examples might be ngt0 and n is even if we are talking about an integer n Find for each statement in the left hand column below the logically equivalent statement in the right hand column There are two statements in the right hand column not equivalent to any of the statements in the left hand column PAQ QgtP Pv uQ QAP P PgtQ PVQ PIQ PAQ PVQ uP u uP General warning Do not confuse statements called by logicians propositions with sets For instance if X is a statement eg agt 10 then it makes no sense to write MEX or aEX And if X and Y are sets then Xgt Y makes no sense There are of course important relations between statements and sets For instance if X and Y are sets then XQ Y is a statement while if Px is a statement about a real number x then xElR Px is a set 3 Quanti ers Here are two symbols that are extremely important in constructing mathematical statements V For all or for every If we are referring to real numbers then Vx c12 x2 2x1 is a true statement so is V x xlt0 v x 0 v xgt 0 Referring to integers n the statement V n 2n 12gt 0 is true though it is not true for real numbers To make such formulas precise we should show what class of possible n we are talking about We can do this by writing for instance V nEZ 2n 12gt 0 For greater clarity parentheses may be introduced eg V nEZ 2n 12gt0 or V nEZ 2n 12gt 0 El There exists such that or for some For example El x61 xgt 10 says that there exists an element x belonging to the set of integers and such that xgt 10 or brie y There exists an integer greater than 10 Similarly El xElR x 3 means There exists a real number whose square is 3 Both of these are true statements Still another way of reading El xElR is For at least one value of x it is true that Some people write El or Ell to mean For exactly one value or equivalently There exists a unique value such that P Exercise 4 Suppose Px and Qx are statements about an integer x Examples of such statements are xgt 0 x is odd x 55 xx etc In each of the cases below if you believe that the equivalence asked about holds say brie y why while if you decide that two statements are not equivalent try to nd an example of propositions P and Q for which one of the statements is true and the other is not a Is V x Px equivalent to u El 6 uPx b Is El 6 Px A Qx equivalent to 3 x Px A 3 x Qx c Is V xE1 23 Px equivalent to P1 A P2 A P3 d Is u V x Px equivalent to V x Px Exercise 5 To show that the statement El xEZ x2 x is true it is enough to give the single example x 0 Suppose Px is a statement about an element x and we want to prove one of the statements below In which cases can this be done by giving just a single example In each such case say what the nature of the example must be a El 6 PM 0 V x 39Px b V 6 PM 1 n V 6 PM Exercise 6 Suppose A and B are sets Translate each of statements a b below which are expressed using the symbols V and El into a statement about A and B expressed using only the set theoretic symbols discussed in the rst section of this note a V x XEA gt 0653 C V 6 16654 b V x XEA ltgt 0653 1 El 6 fo A 0653 Exercise 7 Suppose A0 A1 A2 are subsets of a set X a Match each set on the left with the set on the right that is equal to it UZEN A xEX El iEiN xEAln iEW Ai xEX v iEiN xEAin b Show that one has the equality xEX El iEiN XE41 xEX V iEiN XE41 if and only if the sets A0 A1 A2 are all equal Note The English word any sometimes means V and sometimes El we usually understand which is meant from context Thus if you say I wonder whether anyone knows you are asking whether El 6 x knows is true But the sentence Anyone you ask will be able to tell you means V x If you ask x x can tell you Hence in learning to use the mathematical symbols V and El you must pay attention to the meanings of statements not just the English words used Bound and free variables Suppose we write an equation such as x5 x There are various things that we may mean i meters or the greatest common divisor of 25 1 and 28 1 In this case x5 x is an assertion about x may represent a de nite number that we are considering eg the height of a certain bridge in that number This assertion is either true or false ii We may regard x5 x as a condition on integers x This is then satis ed by some integers and not by others Taken by itself it is neither true nor false 5 5 x as an identity Eg if we are considering integers then by x x we 5 iii We may be asserting x would really mean V xEZ x ring 275 and x5 x is a valid identity in that ring ie V x6275 x5 x is true x which is false On the other hand in Math 113 one encounters the iv We may use the equation x5 x in the proposition El xEZ x5 x which is true v We may use the equation x5 x in de ning the set x627 x5 x which equals 10 1 In use i x is a constant it represents a speci c number we are talking about even if we don t know its value and as we have said the statement x5 x is then true or false In uses ii v x is a variable But there is a difference between ii and the other cases In ii x is a condition in which we may substitute different values of x making the condition true or false x is called afree variable In iii and iv the variable is bound by the quanti er V or El One cannot ask whether the statement El xEZ x x is true for x3 one can only ask whether for x3 the equation x5 x holds Similarly it makes no sense to ask whether V x61 x x is true for x 1 or for x 2 because it is not a statement about a single integer x but a statement whose validity is determined by substituting all integers for x in the statement x x and seeing whether it holds in every case It doesn t so as mentioned in iii above V xEZ x x is false One could avoid the ambiguity of xs x meaning either i ii or iii by insisting that different letters be used for constants and variables and that the symbol V xEX be written whenever it is meant We shall not impose such strict rules but we should always understand what we mean and be explicit when necessary for Clarity A bound variable is an example of the more general concept of a dummy variable This is a variable symbol say x which occurs within an expression but such that the expression is not a function of x rather the value of the expression is determined by some process that involves considering different values of x We have seen how this is so in iii and iv The x in v is also a dummy variable because the set in question is determined by looking over all values of x in Z and collecting those which satisfy 2 x You have seen similar situations in calculus recall the difference between formulas like x and 10 2cl the help of the rst function Likewise in the expression fro x dx x is a dummy variable x2 The rst is a function of x while the second represents a speci c number 385 computed with There is a sixth meaning that xs x can have which one learns about in the latter half of Math 113 Under this interpretation x is an indeterminate in a polynomial ring such as x I will say no more about this here except that so interpreted the equation x x is false since x and x are different elements of 6 and that this interpretation is like i in that x is a particular element rather than a variable Exercise 8 a Give an elementary description of inR El yEiR x lt y lt x2 and prove it is correct Suggestion First gure out by experimentation which real numbers belong to that set then think about how to prove the answer you get To do so you will need to prove two sets equal namely the set given above and the set you describe Two sets X and Y are equal if and only if every element of X is an element of Y and vice versa So to prove such an equality one can begin Let rEX and deduce from what is known that rEY and then tum around and say Now let rEY and deduce from what is known that rEX b Give an elementary description of xElR El yEZ x lt y lt x2 and prove it is correct 5 Order of quanti ers If we take a sentence about integers involving a free variable x and attach to it one of the pre xes El x61 or V xEZ then we have seen above that we get a new statement in which x is a bound variable 2 a condition on a pair of integers x and y Suppose that we add to this the pre x El xEZ getting the statement El xEZ y x2 Then x has been bound and the result is a condition on the integer valued variable y in words y is a square Now consider a sentence with two free variables such as y x For some values of y this is true namely 0 1 4 9 For other values it is false In particular since the set of y for which this condition is satis ed is nonempty it is true that El 326 El x627 y x2 Since the set does not contain all integers it is false that VyEZE x61 y x2 so as to successively bind several variables These examples illustrate the process of adding several pre xes to a statement Consider now the statement about two integers x and y x gt y Note that the statement El xEZ x gt y is true for all y because there is no largest integer y Hence V yEZXEI x61 x gt y is a true statement On the other hand the statement V 3261 x gt y is not true for any integer x if it were then x would be an integer larger than all integers including itself Hence El xEZXVyEZ x gt y is a false statement Since one statement is true and the other false they do not mean the same thing so a change in the order of the pre xes El x61 and V 3262 can change the meaning of a statement Exercise 9 Consider the sentence There is someone at the hotel who cleans every room Explain two ways this sentence can be interpreted and translate them into two quanti cations of the relation X cleans R Which words in the sentence correspond to El in the translation and which to V Ambiguities in the meanings of English sentences like the one in the above exercise are generally cleared up by context So I repeat what I said at the end of section 3 in translating a sentence into symbols we must look at the idea not just the words to see how the quanti ers should be used Some mathematicians treat V simply as an abbreviation of the words for all and put it where they might put those words in a sentence writing things like n1 gt n V n I strongly advise against this under that usage a formula El x Px y V y has exactly the ambiguity illustrated in the above exercise since one might bracket it either as El x Px y Vy or as El x Pxy Vy Rather I recommend putting quanti cation symbols before the statement being quanti ed as in the examples given above In the next exercise you will get practice with quanti ers by using them to write symbolically some de nitions that were given with the help of words in freshman calculus 10 Exercise 10 Let f R gt TR be a real valued function of one real variable Translate conditions ii vi listed below into symbols Since all variables here are real valued you may omit ETR Part i is done for you as an example In your answers do not use symbols such as limuex fu or ddx since these are the concept you are trying to de ne Use only basic operations and relations of the real numbers such as le gt lt etc In this exercise don t even use in later parts concepts you have de ned in earlier parts rather if appropriate incorporate the symbols of the earlier translation into the later one You may use letters such as s and 6 for some of your variables but do not write things like 6x to mean a number 6 which may depend on x or by the same token f x Rather the order of quanti ers in your answers should show what can and what cannot depend on what i f is bounded Answer El MV x fx lt M ii f is continuous at the point xETR iii f is everywhere continuous iv f has a limit as x gt 00 v f is differentiable at x 5 vi f is everywhere differentiable We end with a quick self test on material from the preceding sections Exercise 11 Mark the following true or false Answers at the bottom of page a TNEZ f EIxE D VyEQ x y b N E I g 3x603 VyEQ x a y c I U Q Q h VxEQ EIyECD x y d 2 0 IN w i VxE EIyEQ x y e If subsets A and B of a set X 139 El xE VyEZ x y satisfy A B Q then A X7B 6 Some mathematical language There are several turns of phrase used in mathematical writing that one generally picks up by seeing how they are used But it can be helpful to have explanations available so I give below at the suggestion of John Peloquin a glossary of some of these phrases necessary and su icient conditions To say that a statement A is necessary and suf cient for a statement B to hold simply means that A ltgt B For instance if x is a real number a necessary and suf cient condition for lim m x 0 to hold is that le lt 1 In this usage suf cient refers to the forward implication A gt B and necessary to the reverse implication A lt B and these words can be used separately So in considering whether a sum of integers m n is even we see that a su lcient condition is that both In and n be even but it is not necessary while for m n to be odd a necessary condition is that at least one of m and n be odd but it is not suf cient When one proves a statement of the form A ltgt B by proving the implication rst in one and Answers to Exercise 11 a F b T c T d T e F f F g F h T i T j T 11 then in the opposite direction the proof that A gt B is often called the proof of su iciency and the proof that A lt B the proof of necessity A necessary and suf cient condition for something to be true is called a criterion for it to be true one also speaks of necessary criteria and suf cient criteria which just go one way For instance most of the tests for convergence of a series 2 a that one learns in calculus are su icient criteria for convergence but the statement that for 2 a to converge one must have lim m a 0 is a necessary criterion If one proves a necessary and suf cient condition for an element x to have a certain property this is called a characterization of the elements that have that property to identify To identify two mathematical objects means to regard them as the same For instance when we consider the geometry of the plane R 2 x y xyER and of three dimensional space R3 x y z I x y ZER we often regard R 2 as a subset of R3 by identifying each point x y of the plane with the point xy 0 of 3 space we thus identify R 2 with the xy plane x y z Z 0 in R3 How one justi es regarding two different things as the same in a precise logical science such as mathematics takes some pondering In examples like the above it can be thought of as a notational shorthand we can say that when we speak about points and subsets of the plane R 2 as lying in 3 dimensional space we mean the images of those points under the map p R 2 gt R 3 de ned by pxy x y 0 and because p preserves geometric structure eg distance the property of lying in a straight line etc geometric statements about points of R 2 remain true of their images under p Some other uses of the term are a little different For instance the unit circle parametrized by radian measure is sometimes described as the interval 0 2a with the two ends 0 and 2a identi ed I will not go into how to think of this sort of identi cation here wellde ned When one gives a statement that is supposed to be a de nition it is sometimes necessary to verify that it really does precisely de ne some mathematical object For instance if we tried to de ne a function a from positive rational numbers to positive rational numbers by saying that whenever r mn with m and n positive integers we let ar m1n1 we would face the problem that a positive rational number can be written in more than one way as a ratio of positive integers eg 23 46 so we would need to know whether our de nition depended only on the given rational number r or on the way we chose to write it as a ratio mn In fact we see that 213 1 and 4161 are not the same rational number so the above is not a usable de nition On the other hand if for mn we de ne br mZnz we nd that this rational number does not depend on our choice of how to write r as a ratio In fact br r2 If some entity we have de ned is indeed determined by the rules we have stated rather than varying with choices implicit in our de nition we say that it is wellidefined Proofs of well de nedness become essential in areas of mathematics where certain entities are de ned as equivalence classes of other entities and operations on them are de ned by choosing representatives of these equivalence classes performing operations on these and taking the equivalence class of the resulting element This is not the place to go into those constructions but you will see proofs of well de nedness coming up frequently when you study such topics up to This phrase allows one to modify a statement so as to allow more leeway For instance if a is a positive real number then the equation x a has a real number solution which is unique up to 12 sign This means that if x1 and x2 are both solutions to that equation we do not assert that x1 x2 as we would if we simply said that the solution was unique but rather that x1 1 x2 Likewise if fx is a continuous function on the real line then there is a function g whose derivative is f and this g is unique up to or determined up to an additive constant In High School geometry when one learns that a triangle is determined by side angle side ie by the lengths of two sides and the value of the angle between them a fuller statement would be that the triangle is determined up to congruence by this data In other words triangles that agree in this data must be congruent but need not actually consist of the same points of the plane The fact that most geometry textbooks do not add up to congruence to such statements means that in these statements they are identifying congruent triangles without loss of generality In giving a mathematical proof if we say that without loss of generality we may assume that some condition X holds this means that if we can establish the result in the case where X holds we can deduce from this that it holds in general After saying this one usually assumes that X holds for the rest of the proof For instance in proving a theorem about a function f on an interval a b an author might say Without loss of generality we may assume a b 01 Typically the reason is that if f is a function on a b then the function g on 01 de ned by gx fabia x has properties closely corresponding to those of the original function f For instance g0 fa g1 fb g is differentiable if and only if f is differentiable etc Depending on the theorem one is trying to prove one may be able to see that knowing the theorem is true for the above function g implies that it is true for f In that case it suf ces to go through the details of one s proof for functions on 01 and if this makes the proof easier to write out or to follow one may say Without loss of generality we shall assume a b 01 and complete the proof under that assumption ss Of course whether it is clear that knowing a result in one case implies that it is true in the other case depends on the situation and on the mathematical background of one s readership If the author of a text you are reading says without further explanation that without loss of generality some assumption may be made this means that he or she judges that the reduction to that case should be straightforward for students at the level at which the text is aimed and you should take up the challenge and see whether you can supply the reason If you can t you should ask your instructor In other cases an author may say explicitly why a without loss of generality statement is justi ed You should then look carefully at the arguments by which he or she reduces the general case to the special case ss Mathematicians writing for other mathematicians often abbreviate without loss of generality to wlog but this abbreviation seldom appears in undergraduate textbooks Let me end with one warning of an incorrect use of words I have often seen students make If one wants to describe n2 n62 it is not correct to call this the set containing all squares of integers because there are many sets that t those words For instance the set of all positive integers and the set of all real numbers both contain all squares of integers along with other elements A more correct statement is that n2 n61 is the set consisting of all square of integers or whose members are all square of integers Math 110 amp 128 Separate May 17 2002 1224 pm Separation of Clouds by a Plane This note concerns attempts to draw a hyperplane that partitions a given pointset into two subsets called clusters like two clouds in an otherwise clear sky Of course such attempts are futile if the given points do not fall into two separable clusters so any partitioning algorithm described herein may be merely a solution in search of a problem Given are K points zl z2 z3 zK in a Euclidean space of arbitrary but nite dimension Actually each zk is a column vector drawn from the origin 0 to a point in that space but we shall ignore this distinction and assemble the vectors into a matrix Z z1 z2 z3 zK whose name shall be used for the pointset too We characterize any hyperplane H in that space by choosing a nonzero linear functional row nT and scalar constant 15 thus every point x on H satis es nTx 15 Such aplane H partitions the pointset Z into two clusters distinguished well just when 5 falls into a relatively wide gap between the elements of the row nTZ were its elements sorted in monotonic order differences between elements that straddle B would be noticeably bigger than differences between adjacent elements on the same side of B However pointsets cannot all be partitioned that well by planes Failure Modes Any algorithm designed to nd a separating plane must fail or at least falter when no relatively wide gap exists among the elements of nTZ no matter how nT is chosen This can happen when clouds overlap a little perhaps two clouds would be wellseparated if some relatively few points were deleted from Z Even if the clouds are quite distinct they can be situated like the c and O in the character where no plane can separate them Perhaps the given point set consists of three or more wellseparated clusters then separating planes may be abundant though none is so much better than all others that it deserves to be singled out by the algorithm Evidently separation is a matter of degree and sometimes illde ned even when conspicuous Moreover separation alone lends itself to misinterpretation For instance a border separates the USA from Mexico and separates also almost all of their citizens although many of each country s citizens reside on the other s side of the border A census that counted just adult bodies would overestimate the numbers of eligible voters in border states Here is another instance Suppose the scores achieved by a student on each of several standardized tests are assembled into a column vector z and suppose the array Z is assembled from the scores of K students coming from two different highschools but mixed up so that nobody knows from which school any particular scorevector comes Suppose too that the scorevectors form two clusters that both abut a separating plane though their centers are wellseparated suggesting strongly that the students come from two distinct populations If someone jumped to the conclusion that each cluster s students almost all come from the same highschool he would overestimate the differences between the two highschools students scores by attributing to one highschool all the scores on its side of the separating plane thus omitting this school s scores on the other side of the plane while attributing to it some of the other school s scores Prof W Kahan Page 14 Tlm39a rln nm an xxvna quotAnnl ML 17mm Ab Anlmr A n A Math 110 amp 128 Separate May 17 2002 1224 pm Dividing Points on a Line into Two Clouds Let nTx B be the equation of a plane H that does partition set Z into two clusters and suppose nT is known how can 5 be determined The elements of row nTZ can be Viewed as a set of points on a line and ideally B divides that set into two clusters one substantially above and the other substantially below 5 This much separation is probably too much to demand Instead a value 5 can be deemed acceptable if it lies in a neighborhood where elements of nTZ are sparse compared with neighborhoods above and below 5 where elements are dense Here neighborhood sparse and dense are terms too vague to de ne an algorithm they merely convey the intention behind the procedure to be described next Let sT s1 s2 sK be the row obtained from nTZ by sorting it into say ascending order so that s1 Ss2 S S sK If 1 S i ltj S K the Average Gap between si and Si is defined here to be sJ 7 siiii it is roughly the reciprocal of the average density of elements of nTZ between si and sJ For some integer k between 1 and K a plot of sik 7 sik against i l 2 Kik should show comparatively small Average Gaps where elements of nTZ are dense in the neighborhood between si and sik and large Average Gaps where elements are sparse If Z deserves to be partitioned into two clusters by H the plot should show a pronounced peak between two regions where the Average Gap is comparatively low If the increment k is chosen too big the uctuations in the plot of Average Gap will be too few and too subdued to locate a gap between clusters If k is chosen too small the plot of Average Gap my uctuate too wildly to locate that separating gap A plausible initial choice for the increment k is roughly WE and a plausible initial estimate for the separating gap is within the neighborhood where the Average Gap is maximized between neighborhoods where the Average Gap is comparatively low If k is big enough the maximizing neighborhood will be determined uniquely then plotting the Average Gap again around that neighborhood with a smaller choice of increment k will produce a narrower maximizing neighborhood with a bigger Average Gap Thus plots of Average Gap for a sequence of diminishing incrememts k will produce a nested sequence of narrowing neighborhoods with growing Average Gaps all bigger than those in neighborhoods on both sides When k gets down to l the separating gap in which 5 belongs will have been located Finding the Direction of a Separating Plane In a Euclidean space where the length ofa vector x is HxH VxTx the vector n is normal perpendicular to the plane H whose equation is nTx B The distance from H to apoint z is Hz7HH nTzimHnH because x z 7nnTz45nTn is the point in H closest to z This is so because x satis es the equation of H and every other point x in H can easily be shown to satisfy HFXH2 HP X 7 KHZ HzixHZ HLXHZ 2 HZQHZ Prof W Kahan Page 24 Math 110 amp 128 Separate May 17 2002 1224 pm An alternative form of the equation of H is nTxw 0 for any point c in H for which nTc B This alternative form lends itself better to the solution of a Least Squares Problem Given n i o and a set matrix Z z1 z2 Z3 zK of points choose c to minimize Zj HzJ7HHZ This sum of squared distances can be rewritten as Ed HzJ7HH2 Zj nTzJ 7 c2nTn nTZ 7 cuTZ7cuTTnnTn in which uT 1 l l with K elements Aminimizing choice for c turns out to be c ZuK regardless of n This 9 is the average or mean of the points Z their center of gravity It minimizes the sumofsquares because z 7 cusz7cuTT z 7 guTz79uTT Kmme In short among all parallel planes with the same normal n the plane that minimizes the sum of squared distances from the pointset Z passes through its center of gravity regardless of n A plane that partitions the points Z into two separated clusters should be as far as possible from both clusters while passing between them though it need not pass through Z s center of gravity This thought motivates the following M axiMin Problem Choose the normal n to a plane H through c in such a way as to maximize Zj HzJ7HH2 In other words choose c and n to find maxn minc nTZ7cuTZ7cuTTnnTn This sumof squares is maximized when the normal n an eigenvector of Z 7 ltuTZ7ltuTT belonging to its largest eigenvalue another way to put it is that the maximizing n is the singular vector belonging to the biggest singular value of Z 7 cuT In its Singular Value Decomposition Z 7 cuT PVQT where PTP QTQ I an identity matrix and V is a positive diagonal matrix with the nonzero singular values of Z 7 cuT on its diagonal in descending order n is the first column of P If we presume that this n is the normal to a plane H that partitions Z into two clusters the choice of B to select H can be achieved as discussed earlier Example A perfectly partitionable set Z b b b d d d consists of M repetitions ofa point b and K7M repetitions of another point d Now 9 Mb K7MdK is the center of gravity of Z so b c 7 K7Me and d c Me where e d7bK Then Z 7 cu erT where rT is a row starting with M repetitions of M7K followed by K7M repetitions of M The singular vector belonging to the biggest and only nonzero singular value of erT is e which is the best normal for a plane that separates d from b On the other hand any normal not perpendicular to e would work too if not so well so this example is not a hard test of the procedure described above Prof W Kahan Page 34 Math 110 amp 128 Separate May 17 2002 1224 pm Warning Despite its success on one example the procedure described above has a disquieting property If an invertible linear operator L maps the set Z to another set LZ it should map a separating plane H to another separating plane LH of the set LZ The equation n x B satis ed by points x in H should transform into an equation nTLily B satisfied by points y Lx on LH But the procedure described above will generally get a normal different from nTL 1 for the plane that separates the clusters of LZ the new separating plane will not match LH in general nor will the two clusters of LZ be images of the two clusters of Z Perhaps LZ does not deserve to be separated by LH Suppose the points of Z are the four vertices of a nondegenerate tetrahedron with one vertex at the origin 0 Any such tetrahedron can be mapped to any other by an invertible linear transformation L A tetrahedron whose vertex at o is well separated from the three others can be mapped to a tetrahedron whose vertex at o is close to two others but far from the third This is a case when the clustering of a point set is changed drastically by a linear map tantamount to a nonorthogonal change of coordinates A nonlinear map can change clustering utterly for instance the c and O in the character that cannot be separated by a line are mapped to easily separable sets by a change to polar coordinates centered inside the c In general attempts to separate nonconvex clusters by a plane seem unlikely to succeed unless the clusters can be circumscribed by nonintersecting convex surfaces mostly farther apart than their diameters not like two coins lying at one on the other In other words the separability of a pointset into two clusters may depend upon the coordinate system chosen for the points Also important is the precision with which points are located since the gap between clusters may be misleading if the points locations are in error by much more than the gap The procedure described above makes sense only if the choice of coordinate system has this property The insignif1cance of a small perturbation of any point s position is roughly independent of the point and of the perturbation s direction and therefore determined almost entirely by the perturbation s length in roughly the same way for every point Prof W Kahan Page 44 Math 110 amp 128 Separate May 17 2002 1224 pm Separation of Clouds by a Plane This note concerns attempts to draw a hyperplane that partitions a given pointset into two subsets called clusters like two clouds in an otherwise clear sky Of course such attempts are futile if the given points do not fall into two separable clusters so any partitioning algorithm described herein may be merely a solution in search of a problem Given are K points zl z2 z3 zK in a Euclidean space of arbitrary but nite dimension Actually each zk is a column vector drawn from the origin 0 to a point in that space but we shall ignore this distinction and assemble the vectors into a matrix Z z1 z2 z3 zK whose name shall be used for the pointset too We characterize any hyperplane H in that space by choosing a nonzero linear functional row nT and scalar constant 15 thus every point x on H satis es nTx 15 Such aplane H partitions the pointset Z into two clusters distinguished well just when 5 falls into a relatively wide gap between the elements of the row nTZ were its elements sorted in monotonic order differences between elements that straddle B would be noticeably bigger than differences between adjacent elements on the same side of B However pointsets cannot all be partitioned that well by planes Failure Modes Any algorithm designed to nd a separating plane must fail or at least falter when no relatively wide gap exists among the elements of nTZ no matter how nT is chosen This can happen when clouds overlap a little perhaps two clouds would be wellseparated if some relatively few points were deleted from Z Even if the clouds are quite distinct they can be situated like the c and O in the character where no plane can separate them Perhaps the given point set consists of three or more wellseparated clusters then separating planes may be abundant though none is so much better than all others that it deserves to be singled out by the algorithm Evidently separation is a matter of degree and sometimes illde ned even when conspicuous Moreover separation alone lends itself to misinterpretation For instance a border separates the USA from Mexico and separates also almost all of their citizens although many of each country s citizens reside on the other s side of the border A census that counted just adult bodies would overestimate the numbers of eligible voters in border states Here is another instance Suppose the scores achieved by a student on each of several standardized tests are assembled into a column vector z and suppose the array Z is assembled from the scores of K students coming from two different highschools but mixed up so that nobody knows from which school any particular scorevector comes Suppose too that the scorevectors form two clusters that both abut a separating plane though their centers are wellseparated suggesting strongly that the students come from two distinct populations If someone jumped to the conclusion that each cluster s students almost all come from the same highschool he would overestimate the differences between the two highschools students scores by attributing to one highschool all the scores on its side of the separating plane thus omitting this school s scores on the other side of the plane while attributing to it some of the other school s scores Prof W Kahan Page 14 Tlm39a rln nm an xxvna quotAnnl ML 17mm Ab Anlmr A n A Math 110 amp 128 Separate May 17 2002 1224 pm Dividing Points on a Line into Two Clouds Let nTx B be the equation of a plane H that does partition set Z into two clusters and suppose nT is known how can 5 be determined The elements of row nTZ can be Viewed as a set of points on a line and ideally B divides that set into two clusters one substantially above and the other substantially below 5 This much separation is probably too much to demand Instead a value 5 can be deemed acceptable if it lies in a neighborhood where elements of nTZ are sparse compared with neighborhoods above and below 5 where elements are dense Here neighborhood sparse and dense are terms too vague to de ne an algorithm they merely convey the intention behind the procedure to be described next Let sT s1 s2 sK be the row obtained from nTZ by sorting it into say ascending order so that s1 Ss2 S S sK If 1 S i ltj S K the Average Gap between si and Si is defined here to be sJ 7 siiii it is roughly the reciprocal of the average density of elements of nTZ between si and sJ For some integer k between 1 and K a plot of sik 7 sik against i l 2 Kik should show comparatively small Average Gaps where elements of nTZ are dense in the neighborhood between si and sik and large Average Gaps where elements are sparse If Z deserves to be partitioned into two clusters by H the plot should show a pronounced peak between two regions where the Average Gap is comparatively low If the increment k is chosen too big the uctuations in the plot of Average Gap will be too few and too subdued to locate a gap between clusters If k is chosen too small the plot of Average Gap my uctuate too wildly to locate that separating gap A plausible initial choice for the increment k is roughly WE and a plausible initial estimate for the separating gap is within the neighborhood where the Average Gap is maximized between neighborhoods where the Average Gap is comparatively low If k is big enough the maximizing neighborhood will be determined uniquely then plotting the Average Gap again around that neighborhood with a smaller choice of increment k will produce a narrower maximizing neighborhood with a bigger Average Gap Thus plots of Average Gap for a sequence of diminishing incrememts k will produce a nested sequence of narrowing neighborhoods with growing Average Gaps all bigger than those in neighborhoods on both sides When k gets down to l the separating gap in which 5 belongs will have been located Finding the Direction of a Separating Plane In a Euclidean space where the length ofa vector x is HxH VxTx the vector n is normal perpendicular to the plane H whose equation is nTx B The distance from H to apoint z is Hz7HH nTzimHnH because x z 7nnTz45nTn is the point in H closest to z This is so because x satis es the equation of H and every other point x in H can easily be shown to satisfy HFXH2 HP X 7 KHZ HzixHZ HLXHZ 2 HZQHZ Prof W Kahan Page 24 Math 110 amp 128 Separate May 17 2002 1224 pm An alternative form of the equation of H is nTxw 0 for any point c in H for which nTc B This alternative form lends itself better to the solution of a Least Squares Problem Given n i o and a set matrix Z z1 z2 Z3 zK of points choose c to minimize Zj HzJ7HHZ This sum of squared distances can be rewritten as Ed HzJ7HH2 Zj nTzJ 7 c2nTn nTZ 7 cuTZ7cuTTnnTn in which uT 1 l l with K elements Aminimizing choice for c turns out to be c ZuK regardless of n This 9 is the average or mean of the points Z their center of gravity It minimizes the sumofsquares because z 7 cusz7cuTT z 7 guTz79uTT Kmme In short among all parallel planes with the same normal n the plane that minimizes the sum of squared distances from the pointset Z passes through its center of gravity regardless of n A plane that partitions the points Z into two separated clusters should be as far as possible from both clusters while passing between them though it need not pass through Z s center of gravity This thought motivates the following M axiMin Problem Choose the normal n to a plane H through c in such a way as to maximize Zj HzJ7HH2 In other words choose c and n to find maxn minc nTZ7cuTZ7cuTTnnTn This sumof squares is maximized when the normal n an eigenvector of Z 7 ltuTZ7ltuTT belonging to its largest eigenvalue another way to put it is that the maximizing n is the singular vector belonging to the biggest singular value of Z 7 cuT In its Singular Value Decomposition Z 7 cuT PVQT where PTP QTQ I an identity matrix and V is a positive diagonal matrix with the nonzero singular values of Z 7 cuT on its diagonal in descending order n is the first column of P If we presume that this n is the normal to a plane H that partitions Z into two clusters the choice of B to select H can be achieved as discussed earlier Example A perfectly partitionable set Z b b b d d d consists of M repetitions ofa point b and K7M repetitions of another point d Now 9 Mb K7MdK is the center of gravity of Z so b c 7 K7Me and d c Me where e d7bK Then Z 7 cu erT where rT is a row starting with M repetitions of M7K followed by K7M repetitions of M The singular vector belonging to the biggest and only nonzero singular value of erT is e which is the best normal for a plane that separates d from b On the other hand any normal not perpendicular to e would work too if not so well so this example is not a hard test of the procedure described above Prof W Kahan Page 34 Math 110 amp 128 Separate May 17 2002 1224 pm Warning Despite its success on one example the procedure described above has a disquieting property If an invertible linear operator L maps the set Z to another set LZ it should map a separating plane H to another separating plane LH of the set LZ The equation n x B satis ed by points x in H should transform into an equation nTLily B satisfied by points y Lx on LH But the procedure described above will generally get a normal different from nTL 1 for the plane that separates the clusters of LZ the new separating plane will not match LH in general nor will the two clusters of LZ be images of the two clusters of Z Perhaps LZ does not deserve to be separated by LH Suppose the points of Z are the four vertices of a nondegenerate tetrahedron with one vertex at the origin 0 Any such tetrahedron can be mapped to any other by an invertible linear transformation L A tetrahedron whose vertex at o is well separated from the three others can be mapped to a tetrahedron whose vertex at o is close to two others but far from the third This is a case when the clustering of a point set is changed drastically by a linear map tantamount to a nonorthogonal change of coordinates A nonlinear map can change clustering utterly for instance the c and O in the character that cannot be separated by a line are mapped to easily separable sets by a change to polar coordinates centered inside the c In general attempts to separate nonconvex clusters by a plane seem unlikely to succeed unless the clusters can be circumscribed by nonintersecting convex surfaces mostly farther apart than their diameters not like two coins lying at one on the other In other words the separability of a pointset into two clusters may depend upon the coordinate system chosen for the points Also important is the precision with which points are located since the gap between clusters may be misleading if the points locations are in error by much more than the gap The procedure described above makes sense only if the choice of coordinate system has this property The insignif1cance of a small perturbation of any point s position is roughly independent of the point and of the perturbation s direction and therefore determined almost entirely by the perturbation s length in roughly the same way for every point Prof W Kahan Page 44 Math 110 TWO Problems February 20 2002 1215 pm 1 Must Triangular Matrices have Triangular Inverses The rst problem was to show why every triangular matrix has a triangular inverse whenever the inverse exists The following demonstration goes by induction The claim is obviously true for lbyl triangular matrices scalars Suppose now for some integer n 2 1 that every nby n uppertriangular matrix U has an uppertriangular inverse U 1 whenever it exists Let U be any nlbynl uppertriangle with an inverse A It must satisfy UA 1 the n1 bynl identity Partition each matrix in this equation conformally into submatrices thus UuAc 10 oTu rTB 0T1 Here submatrices U A and I are nbyn columns 11 c and o are nbyl rows rT and oT are lbyn and scalars M B and l are lbyl These submatrices satisfy UAurTI UcuBo oTAurToT oTcuBl Since oT is a row ofzeros the last two equations simplify to MrT oT and 3915 l These equations can both be satis ed only if M i 0 which is necessary for U 1 to exist and then B ltt and rT oT Then A U 1 and c iUilutl Consequently U71 0 0T B is uppertriangular because U71 is This completes the induction for uppertriangles showing that the ones with nonzero diagonals have uppertriangular inverses For lowertriangles we U IA transpose the equation UA 1 to get ATUT l which shows why every lowertriangle UT with a nonzero diagonal has a lowertriangular inverse AT Note too from the relation 15 ltt that two triangular matrices inverse to each other have diagonal elements respectively reciprocals of each other 2 When are Triangular Factorizations Unique The second problem was to show that whenever a square matrix B LU has triangular factors L unitlowertriangular with l s on its diagonal and U uppertriangular with all its diagonal elements nonzero except perhaps its last diagonal element then B determines L and U uniquely For this purpose kissilme first that the diagonal of U is altogether nonzero and that another factorization B LU has been found perhaps by a different method with unit lowertriangle L and uppertriangle U The equation LU LU implies L71 L UU 1 here L71 L is the lowertriangular product of lowertriangles and UU 1 is an uppertriangle similarly so the products can be equal only if both are diagonal This makes L71 L I it is the product of just the diagonal elements of L71 and L which are l s Therefore L L and it soon follows that U U too which makes the triangular factorization of B unique Now consider a triangular factorization when the uppertriangular factor s last diagonal element is zero For this purpose let us write Prof W Kahan Page 12 The r n nm an xxvna quotAnnl ML 17mm AT Anlmr A n A Math 110 TWO Problems February 20 2002 1215 pm B c 7 L o U u bT B rT 1 0T 0 in which c o and u are columns bT rT and oT are rows and the 0 s contain zeros This triangular factorization s submatrices satisfy B LU c Lu bTrTU BrTu0 We have seen that the equation B LU determines unitlowertriangle L and uppertriangle U uniquely when all diagonal elements of U are nonzero as is assumed here Then column u L71 c and row rT bTU 1 are determined uniquely too by c and bT as is the upper triangle s last diagonal element 15 7 rTu That it happens to vanish does not alter the uniqueness of the triangular factorization up to this point The nonuniqueness or nonexistence of LU triangular factorization when any but the last diagonal element of U vanishes is illustrated by examples First is a nonunique factorization 12 3 100 123 2 410 21039004 3 630 3B1 oou in which M 21 7 4B The second example has no triangular factorization Prof W Kahan Page 22 George M Bergman Math H110 Fall 2008 Supplementary material Some notes on sets logic and mathematical language These are generic notes for use in Math 110 113 104 or 185 These pages do not develop in detail the de nitions and concepts to be mentioned That is done to various degrees in Math 55 Math 74 Math 125 and Math 135 I hope you will nevertheless nd them useful and thoughtprovoking I recommend working the exercises for practice but don t hand them in unless they are listed in a homework assignment for the course 1 Set theoretic symbols Symbol Q If 2 e etc Meaning usage examples discussion The empty set Here 1N denotes the set of all natural numbers ie 0 1 2 3 while I from Zahl German for number denotes the set of all integers 73 72 71 0 1 2 3 Many older authors started the natural numbers with 1 but it is preferable to start with 0 since natural numbers are used to count the elements of nite sets and Q is a nite set Of these 03 for quotient denotes the set of all rational numbers ie fractions that can be written with integer numerator and denominator 1R denotes the set of real numbers and I the set of complex numbers The ve sets just named used to be and often still are denoted by boldface letters N Z Q R and C The forms 1N Ll arose as quick ways to write these boldface letters on the blackboard Since it is convenient to have distinctive symbols for these important sets printed forms imitating the blackboard bold symbols were then designed and are now frequently used as shown Is a member of Eg 361 The set of all This is often used together with or different authors prefer the one or the other which stand for such that For instance the set of positive integers can be written 1 2 3 or n61 ngt0 or n nel ngt0 The set of all square integers can be written 0149n2 or n2 n62 Note also that n2 nel m2 meZ m22m1mel Why Is asubset of Eg Q g 1 g N g I g R g 0 n2neZ g n62 n20 I g I Is a proper subset of that is a subset that is not the whole set For instance I g R In fact all the formulas used above to illustrate g remain true with g in place of g except for I g Z Since a proper subset is in particular a subset one may use g even when g is true and one generally does so unless one wants to emphasize that a subset is proper But beware some authors especially in Eastern Europe use C for is a subset of Obvious variants of the above symbols A Q B means B Q A xeX means x is not a member of X A g B means A is nota subset of B etc Warning The phrases A lies in X and A is contained in X can mean either AeX or A gX The former phrase more often means A eX and the latter A gX but this is no guarantee So in your writing if there is danger of ambiguity either use the mathematical symbols or use the unambiguous phrases is a member of and is a subset of Intersection A B x both xeA and xeB are true For instance er xgt9 xelR xS 12 10 11 12 for fX gtY Intersection of an indexed family of sets For instance if A0 A1 also written nEWAn OZZOAn and Ao Al GA 0 all ofAO A1 etc In an intersection WIE1 A I does not have to be a set of integers it can be any set such that Al is de ned for each ie When a set I is used in this way to index ie list other entities it is called an index set are sets then n0 1WA n means x x is a member of Union AUB x xeA or xeB For instance xel xgt0 U xel xlt 12 Z Note thatif A g B then AUB B and A03 A Union of an indexed family of sets Thus Un0 1 An AOUAI UUAnU Example UnEW ieiN iltn W Often when the intent is clear from context the above notations are abbreviated For instance if we know that we have one set Al for each i in a certain indexset I then instead of UiEIAi we may write U1 Al or UiAZ orjust UAi Likewise if we have a set Xn for each positive integer n the intersection 0 21 Xn may be written Wan or simply W X 7 co 7 7 UnEFNAn 7 Un0An 7 Complement of cA means x x A But x xeA makes no sense if we don t say what x s are allowed So the notation cA is used only when discussing subsets of a xed set For instance if we are discussing subsets of the integers then ceven integers odd integers while if we are considering subsets of G then ceven integers denotes the set consisting of all odd integers and noninteger rationals To be more precise we can use the next symbols AiB or AB means xeA xe B Eg Z 7 even integers odd integers Note that A73 is de ned even if B is not a subset of A For instance Z 7 negative real numbers W This indicates that f is a function also called a map or mapping from the set X to the set Y In reading the symbol out loud one can use words such as the map f from X to Y or sending X to Y Such an f is said to be onetoone or infective if for every two distinct elements x1 x2 eX the elements fx1 and fx2 of Y are also distinct For instance the operation of cubing an integer is a onetoone function Z gt Z but the squaring map is not onetoone because in n The function f X gt Y is said to be onto Y if every element of Y equals fx for some xe X For instance the squaring and cubing maps Z gt Z are not onto since not all integers are squares or cubes On the other hand the cubing map R gt R is both onetoone and onto Given f X gt Y the set X is called the domain of What about the set at the other end of the arrow A complication is that if f is not onto Y then Y and fx xe X are different sets Traditionally these were called the range and the image of f respectively but the usage was not rm range was often used as a synonym for image Hence nowadays the unambiguous term codomain has been introduced to describe Y A function is called onto if it is onto its codomain a synonymous term is surjective from French sur onto A map f X gt Y that is both onetoone and onto has an inverse map g Y gt X taking each ye Y to the unique element xeX such that fx y Thus f may be thought of as de ning a matching X gt Y under which each element of X is matched with a unique element of Y and vice versa such a matching is called a onetoone correspondence between X and Y So the phrases onetoone and onto function invertible function and onetoone correspondence all describe the same thing still another term for this is bijective map bijective meaning both injective and surjective This symbol is used in three di erent ways which are related but not quite the same A lot of confusion can result if they are not distinguished First if f is onetoone and onto then f1 denotes the inverse of f discussed above Secondly if f XH Y is any map and S is any subset of Y then f1S denotes xeX fxeS called the inverse image or preirnage of S under When f is invertible it is not hard to check that this is precisely the image of the set S under the inverse function f Y H X However this de nition of f S makes sense even when f is not invertible Finally for ye Y the symbol f1y is often simpli ed to f1y Hence when the symbol f is used you must check whether the context indicates that f is an invertible function If so you can be con dent that f denotes the inverse function if not then f does not stand for a function but is a way of writing inverse images of sets or elements under f While the ordinary arrow referred to above is used to show what the domain and codomain of a function are the attailed arrow shows which element is carried to which Thus f x H 6 means that f is the squaring function de ned by fx x2 We can use this kind of arrow to describe a function without denoting it by a letter eg the function x H x2 which can be read the function xgoestoxz or the function taking x to x2 If A and B are sets AgtltB means the set of ordered pairs a b aeA be B Iwon t discuss here precisely how an ordered pair is de ned simply think of it as a list of length 2 Note that a function f of two variables one Avalued and one Bvalued which takes values in a set C can be thought of as a map f A gtltB H C For example addition of integers is a map Z X I H Z given by rn n H m n while exponentiation of real numbers using natural numbers as exponents given by x n H xquot is a map R X N H HQ Likewise AgtltBgtltC denotes the set of ordered 3tuples a b c aeA be B ce C and one de nes a function of three variables as a map on such a triple productset and so on The set AgtltB is called the product or direct product of the sets A and B because if A and B are nite A having rn members and B having n members then A gtltB will have rn n members In analytic geometry one regards the set R X R of pairs of real numbers as labeling the points of the plane The numbers so used are called the Cartesian coordinates of the points after Rene Descartes who developed this approach to geometry Hence one often calls the direct product AgtltB of any two sets their Cartesian product If f XH Y is a function then x fx xeX g Xgtlt Y is called the graph of f H again the idea comes from analytic geometry Exercise 1 Let X and Y be sets Find conditions on a subset S C XgtltY that are necessary and suf cient for S to be the graph of a function X H Y Ie necessary and suf cient conditions on S for there to exist a function f X H Y such that S is the graph of f If these conditions hold will S uniquely determine the function In view of the answer to the above exercise settheorists often de ne a function from a set X to a set Y as a subset of X X Y having the appropriate 2properties The sets AgtltA AgtltA gtltA etc are often written A A3 etc Also if A and B are sets the set of functions from A to B is often written B since if A is a nite set with rn elements and B a nite set with n elements this set of functions will have nm elements 2 Logical connectives Let us begin by noting that there is a kind of inverse relation between statements and possibilities 7 the more statements we make the more we limit the set of possibilities the more possibilities there are the more limited is the set of true statements For instance suppose we are considering an integervalued variable x If we require that x be positive then the set of possibilities we are considering forms the set 1 2 3 If instead we had stated that x is even then the set would have been 74 72 0 2 4 If we impose both conditions then the only possibilities for x are the positive even integers a proper subset of the two sets named More generally if P and Q are any two conditions and we assume that P and Q hold then the set of cases we are allowing is the intersection of the set of cases allowed by P alone and the set of cases allowed by Q alone This will help you remember the next symbol which is similar to m A And If P and Q are two statements then we de ne P A Q to hold if and only if P and Q both hold For example the condition 0 S x S l is an abbreviation of 0 S x A xS l The operation A is called conjunction On the other hand if we want to consider all cases allowed by a condition P and also all cases allowed by Q 7 the union of the two sets of cases 7 then we are considering the condition P or Q holds This is a weaker condition than either P or Q in line with the inverse relation noted above between statements and cases The symbol used is similar to U namely v Or If P and Q are two statements we say that P v Q holds in a situation if P holds or if Q holds possibly both For instance for all real numbers x we have xlt 10 v xgt0 The condition x S y is equivalent to x lt y v x y As another example for all integers a b we have 12 0 v b2 0 v abZ l The operation v is called disjunction The inverse relation between statements and possibilities that we have mentioned is sometimes a cause of confusion Many beginning calculus students when asked to say what real numbers x satisfy x2gtl will describe these as the set of x satisfying xgtl and xlt7l What they mean is that the set consists ofall x satisfying xgtl and all x satisfying xlt7l But the correct way to express this union of cases is not by the conjunction xgtl and xlt7l but by the disjunction xgtl or xlt7l That is x x2gtl 7oo7lu1oo x xlt71 U x xgt l x xlt71 vxgt 1 7 Not Eg x y means x y 2 Implies For instance if xe R then xgt2 2 xgt 0 If P and Q are statements then P 2 Q is a statement which is considered to be true in all cases except those where P is true but Q is false P 2 Q may also be expressed in words If P then Q or Q if P For instance the true statement xgt2 2 xgt0 can expressed xgt0 if xgt2 There are certain conventions in the everyday nonmathematical use of words such as or and if which we use unconsciously but need to become aware of so as to understand that they do not apply to mathematical usage In everyday life we generally use the word or only when we do not know which of the two possibilities is true Eg if a letter comes in the mail and you say This is either from John or Stephanie you are asserting that it is from one of them but also implicitly that you do not yet know which one There are variants on this convention If you say I am holding a penny in Ch iff either my right hand or my left hand then you know which hand it is in but the person you are speaking to does not On the other hand a mathematical statement P vQ is considered to be true even when we do know which of P or Q holds For instance we have noted that for all real numbers x xlt 10 v xgt 0 So in particular the statement 100 lt 10 v 100gt 0 is true and so is 5 lt10 v 5 gt 0 and so is 0 lt10 v 0gt 0 Of course a mathematician does not pointlessly write down P vQ when he or she and the reader both know that P is true or both know that Q is true any more than a nonmathematician would But it must be understood that P vQ is true in such cases in order that the truth of a mathematical statement not be lost when our knowledge increases Similarly in nonmathematical usage we generally make statements of the form If P then Q only when there is some uncertainty as to whether the statements P andor Q hold but again to make mathematical usage consistent we must accept P 2 Q as true in all cases except when P holds and Q does not Note also that in nonmathematical usage P or Q sometimes means P or Q but not both Eg in the John or Stephanie example and the which hand example above In mathematical usage the meaning of or is not restricted in that way so 5 lt 10 v 5 gt 0 is a true statement PC Q means Pgt Q AQgtP ie P is true if and only if Q is true synonymous with if and only if often abbreviated by mathematicians to iff Thus cgt is The next two exercises give some practice with the logical connectives described in this section Exercise 2 Suppose x is an element and A B are sets Find for each statement in the lefthand column below the logically equivalent statement in the righthand column There is one statement in the righthand column not equivalent to any of the statements in the lefthand column xeAUB xeAxeB xeA B xeAgtxeB xe cA xeA Ax B xeAB eA x xeA vxe B Exercise 3 Suppose P and Q are two mathematical assertions Examples might be ngt0 and n is even if we are talking about an integer n Find for each statement in the lefthand column below the logically equivalent statement in the righthand column There are two statements in the righthand column not equivalent to any of the statements in the lefthand column FAQ QgtP Pv Q QAP P 43 Q PvQ P AHQ PAQ P th P P General warning Do not confuse statements called by logicians propositions with sets For instance if X is a statement eg 11gt 10 then it makes no sense to write ueX or an And if X and Y are sets then Xgt Y makes no sense There are of course important relations between statements and sets For instance if X and Y are sets then XC Y is a statement while if Px is a statement about a real number x then xe R Px is a set 3 Quanti ers Here are two symbols that are extremely important in constructing mathematical statements V For all or for every If we are referring to real numbers then V x xl2 x2 2xl is a true statement so is V x xlt0 v x 0 v xgt 0 Referring to integers n the statement V n 2171 gt 0 is true though it is not true for real numbers To make such formulas precise we should show what class of possible n we are talking about We can do this by writing for instance V rte Z 2171 gt 0 For greater clarity parentheses may be introduced eg V nel 217 l2gt0 or V nel 2171 gt 0 El There exists such that or for some For example El er xgt 10 says that there exists an element x belonging to the set of integers and such that xgt 10 or brie y There exists an integer greater than 10 Similarly El xe R x2 3 means There exists a real number whose square is 3 Both of these are true statements Still another way of reading El xe R is For at least one real number x it is true that Some people also write El or Ell to mean For exactly one value or equivalently There exists a unique value such that Exercise 4 Suppose Px and Qx are statements about an integer x Examples of such statements are xgt 0 x is odd x 55 xx etc In each of the cases below if you believe that the equivalence asked about holds say brie y why while if you decide that two statements are not equivalent try to nd an example of propositions P and Q for which one of the statements is true and the other is not a Is V x Px equivalent to El x Px b Is El x Px A Qx equivalent to 3 x Px A 3 x Qx c Is V xe 1 2 3 Px equivalent to P l A P2 A P3 d Is V x Px equivalent to V x Px Exercise 5 To show that the statement El xe Z x2x is true it is enough to give the single example x 0 Suppose Px is a statement about an element x and we want to prove one of the statements below In which cases can this be done by giving just a single example In each such case say what the nature of the example must be a El x Px 0 V x 39Px b V x Px d 39V x Px Exercise 6 Suppose A and B are sets Translate each of statements ab below which are expressed using the symbols V and El into a statement about A and B expressed using only the settheoretic symbols discussed in the rst section of this note a V x 96614 gt 0663 C V x xeA b Vxx Acgtx B d 3xxAAx B Exercise 7 Suppose A0 A1 A2 are subsets of a set X a Match each set on the left with the set on the right that is equal to it UiEWAZ xeX El ielN xeAi WIEN Al xeX V ie N xeAi b Show that one has the equality xeX El ie N xeAi xeX V ielN xeAi if and only if the sets A0 A1 A2 are all equal Note The English word any sometimes means V and sometimes El we usually understand which is meant from context Thus if you say I wonder whether anyone knows you are asking whether El x x knows is true But the sentence Anyone you ask will be able to tell you means V x If you ask x x can tell you Hence in learning to use the mathematical symbols V and El you must pay attention to the meanings of statements not just the English words used Bound and free variables Suppose we write an equation such as x5 x There are various things that we may mean i x may represent a de nite number that we are considering eg the height of a certain bridge in meters or the greatest common divisor of 2 fl and 2 71 In this case x x is an assertion about that number This assertion is either true or false ii We may regard x5 x as a condition on integers x This is then satis ed by some integers and not by others Taken by itself it is neither true nor false iii We may be asserting x5 x as an identity Eg if we are considering integers then by x5 x we would really mean V xe Z x x which is false On the other hand in Math 113 one encounters the ring IS and x x is a valid identity in that ring ie V xe ZS x x is true iv We may use the equation x5 x in the proposition El xe Z x5 x which is true v We may use the equation x5 x in de ning the set xe Z x5 x which equals 71 0 1 In use i x is a constant it represents a speci c number we are talking about even if we don t know its value and as we have said the statement x5 x is then true or false In uses iiv x is a variable But there is a difference between ii and the other cases In ii x is a condition in which we may substitute different values of x making the condition true or false x is called a free variable In iii and iv the variable is bound by the quanti er V or El One cannot ask whether the statement El xe Z x5 x is true for x 3 although one can ask whether 5 x is true for xl x is true for x 3 Similarly it makes no sense to ask whether V xe Z x or for x 2 because it is not a statement about a single integer x but a statement whose validity is determined by substituting all integers for x in the statement x x and seeing whether it holds in every case It doesn t so as mentioned in iii above V xe Z x5 x is false One could avoid the ambiguity of x5 x meaning either i ii or iii by insisting that different letters be used for constants and variables and that the symbol V xeX be written whenever it is meant We shall not impose such strict rules but we should always understand what we mean and be explicit when necessaryfor clarity A bound variable is an example of the more general concept of a dummy variable This is a variable symbol say x which occurs within an expression but such that the expression is not a function of x39 rather the value of the expression is determined by some process that involves considering different values of x We have seen how this is so in iii and iv The x in v is also a dummy variable because the set in question is determined by looking over all values of x in Z and collecting those which satisfy x You have seen similar situations in calculus recall the difference between formulas like x and 2 x2 The rst is a function of x while the second represents a speci c number 385 computed with the help of the rst function Likewise in the expression 110 x2 dx x is a dummy variable There is a sixth meaning that x5 x can have which one learns about in the latter half of Math 113 Under this interpretation x is an indeterminate in a polynomial ring such as x I will say no more about this here except that so interpreted the equation x x is false since x and x are different polynomials and that this interpretation is like i in that x is a particular element rather than a variable Exercise 8 a Give an elementary description of xe P El ye P x lt y lt x2 and prove it is orrect Suggestion First gure out by experimentation which real numbers belong to that set then think about how to prove the answer you get To do so you will need to prove two sets equal namely the set given above and the set you describe Two sets X and Y are equal if and only if every element of X is an element of Y and vice versa So to prove such an equality one can begin Let reX and deduce from what is known that re Y and then turn around and say Now let re Y and deduce from what is known that reX b Give an elementary description of xe R El ye Z x lt y lt x2 and prove it is correct 5 Order of quanti ers If we take a sentence about integers involving a free variable x and attach to it one of the pre xes El xe Z or V xe 2 then we have seen above that we get a new statement in which x is a bound variable Now consider a sentence with two free variables such as y x and y Suppose that we add to this the pre x El xe Z getting the statement El xel y x2 Then x has been bound and the result is a condition on the integervalued variable y in words y is a square For some values of y this is true namely 0 l 4 9 For other values it is false In particular since the set of y for which this condition is satis ed is nonempty it is true that El ye ZE xe 2 y x2 Since the set does not contain all integers it is false that V ye ZE xe 2 y x2 These examples illustrate the process of adding several pre xes to a statement so as to successively bind several variables Consider now the statement about two integers x and y x gt y Note that the statement El xe Z x gt y is true for all y because there is no largest integer y Hence VyeZEer x gt y is a true statement On the other hand the statement V ye Z x gt y is not true for any integer x if it were then x would be an integer larger than all integers including itself Hence El erVyeZ x gt y 2 a condition on a pair of integers x is a false statement Since one statement is true and the other false they do not mean the same thing so a change in the order of the pre xes El xe Z and V ye I can change the meaning of a statement Exercise 9 Consider the sentence There is someone at the hotel who cleans every room Explain two ways this sentence can be interpreted and translate them into two quanti cations of the relation X cleans R Which words in the sentence correspond to El in the translation and which to V Ambiguities in the meanings of English sentences like the one in the above exercise are generally cleared up by context So I repeat what I said at the end of section 3 in translating a sentence into symbols we must look at the idea not just the words to see how the quanti ers should be used Some mathematicians treat V simply as an abbreviation of the words for all and put it where they might put those words in a sentence writing things like n1 gt n V n I strongly advise against this under that usage a formula El x Px y V y has exactly the ambiguity illustrated in the above exercise since one might bracket it either as El x Px y Vy or as El x Pxy Vy Rather I recommend putting quanti cation symbols before the statement being quanti ed as in the examples given above In the next exercise you will get practice with quanti ers by using them to write symbolically some de nitions that were given with the help of words in freshman calculus Exercise 10 Let f P gt TR be a realvalued function of one real variable Translate conditions iivi listed below into symbols Since all variables here are realvalued you may omit 6 TR Part i is done for you as an example In your answers do not use symbols such as limux fu or ddx since these are the concept you are trying to de ne Use only basic operations and relations of the real numbers such as 7 lxl gt lt etc In this exercise don t even use in later parts concepts you have de ned in earlier parts rather if appropriate incorporate the symbols of the earlier translation into the later one You may use letters such as e and 6 for some of your variables but do not write things like 6x to mean a number 6 which may depend on x or by the same token f x Rather the order of quanti ers in your answers should show what can and what cannot depend on what i f is bounded Answer EIMV x lfxl lt M ii f is continuous at the point xe TR iii f is everywhere continuous iv f has a limit as x gt 00 v f is differentiable at x 5 vi f is everywhere differentiable We end with a quick selftest on material from the preceding sections Exercise 11 Mark the following true or false Answers at the bottom of page a TNEZ f Elxe VyeQ xy b N C I g 3x603 Vye x y c I UQ C h VxeCD EIyeCD x y d Z TN N i Ver Elye x y e If subsets A and B ofa set X 139 El xe G3 Vye Z x y satisfy A B Q then A XiB 6 Some mathematical language There are several turns of phrase used in mathematical writing that one generally picks up by seeing how they are used But it can be helpful to have explanations available so I give below at the suggestion of John Peloquin a glossary of some of these phrases necessary and su icient conditions To say that a statement A is necessary and suf cient for a statement B to hold simply means that A C B For instance if x is a real number a necessary and suf cient condition for limngtoo xn 0 to hold is that lxl lt 1 In this usage suf cient refers to the forward implication A z B and necessary to the reverse implication A c B and these words can be used separately So in considering whether a sum of integers Answers to Exercise 11 a F b T c T d T e F f F g F h T i T j T 10 rn n is even we see that a su icient condition is that both rn and n be even but it is not necessary while for rn n to be odd a necessary condition is that at least one of rn and n be odd but it is not suf cient When one proves a statement of the form A C B by proving the implication rst in one and then in the opposite direction the proof that A z B is often called the proof of su iciency and the proof that A c B the proof of necessity A necessary and suf cient condition for something to be true is called a criterion for it to be true one also speaks of necessary criteria and suf cient criteria which just go one way For instance most of the tests for convergence of a series 2 an that one learns in calculus are su icient criteria for convergence but the statement that for 2 an to converge one must have limn 00 an 0 is a necessary criterion If one proves a necessary and suf cient condition for an element x to have a certain property this is called a characterization of the elements that have that property to identify To identify two mathematical objects means to regard them as the same For instance when we consider the geometry of the plane IR 2 x y xye IR and of threedimensional space R 3 xy Z xy 26 IR we often regard IR 2 as a subset of IR 3 by identifying each point x y of the plane with the point x y 0 of 3space we thus identi IR 2 with the xyplane xy Z Z 0 in R3 How one justi es regarding two different things as the same in a precise logical science such as mathematics takes some pondering In examples like the above it can be thought of as a notational shorthand we can say that when we speak about points and subsets of the plane IR 2 as lying in 3dimensional space we mean the images of those points under the map p R 2 gt R 3 de ned by pxy x y 0 and because p preserves geometric structure eg distance the property of lying in a straight line etc geometric statements about points of IR 2 remain true of their images under p Some other uses of the term are a little different For instance the unit circle parametrized by radian measure is sometimes described as the interval 027r with the two ends 0 and 27 identi ed I will not go into how to think of this sort of identi cation here wellde ned When one gives a statement that is supposed to be a de nition it is sometimes necessary to verify that it really does precisely de ne some mathematical object For instance if we tried to de ne a function a from positive rational numbers to positive rational numbers by saying that whenever r rn n with rn and n positive integers we let ar rn ln l we would face the problem that a positive rational number can be written in more than one way as a ratio of positive integers eg 23 46 so we would need to know whether our de nition depended only on the given rational number r or on the way we chose to write it as a ratio rnn In fact we see that 2 l3 1 and 4 l6 1 are not the same rational number so the above is not a usable de nition On the other hand if for rn n we de ne br rn n we nd that this rational number does not depend on our choice of how to write r as a ratio In fact br r2 If some entity we have de ned is indeed determined by the rules we have stated rather than varying with choices implicit in our de nition we say that it is wellde ned Proofs of wellde nedness become essential in areas of mathematics where certain entities are de ned as equivalence classes of other entities and operations on them are de ned by choosing representatives of these equivalence classes performing operations on these and taking the equivalence class of the resulting element This is not the place to go into those constructions but you will see proofs of well de nedness coming up frequently when you study such topics unique The unique element having a property means the only element with that property Thus in mathematics the word unique is always used relative to the statement of some property 7 often 11 mentioned in the same sentence but sometimes implicit in the context For instance 2 is the unique real number x such that x 8 so that equation has a unique solution in R On the other hand the equation x 4 does not have a unique solution in R since both 2 and 72 are solutions I have actually used the word unique four times in the preceding pages of this note trusting that most students either knew its mathematical meaning or would recognize what I meant up to This phrase allows one to modify a statement so as to allow more leeway For instance if a is a positive real number then the equation x2 a has a realnumber solution which is unique up to Sign This means that if x1 and x2 are both solutions to that equation we do not assert that x1 x2 as we would if we simply said that the solution was unique but rather that x1 i x2 Likewise if fx is a continuous function on the real line then there is a function g whose derivative is f and this g is unique up to or determined up to an additive constant In High School geometry when one learns that a triangle is determined by sideangleside ie by the lengths of two sides and the value of the angle between them a fuller statement would be that the triangle is determined up to congruence by this data In other words triangles that agree in this data must be congruent but need not actually consist of the same points of the plane The fact that most geometry textbooks do not add up to congruence to such statements means that in these statements they are identi ing congruent triangles without loss of generality In giving a mathematical proof if we say that without loss of generality we may assume that some condition X holds this means that we can establish the result in the case where X holds we can deduce from this that it holds in general After saying this one usually assumes that X holds for the rest of the proof For instance in proving a theorem about a function f on an interval 1 b an author might say Without loss of generality we may assume 1 b 01 Typically the reason is that if f is a function on 11 b then the function g on 0 1 de ned by gx fabia x has properties closely corresponding to those of the original function For instance g0 fa gl fb g is differentiable if and only if f is differentiable etc Depending on the theorem one is trying to prove one may be able to see that knowing the theorem is true for the above function g implies that it is true for In that case it suf ces to go through the details of one s proof for functions on 01 and if this makes the proof easier to write out or to follow one may say Without loss of generality we shall assume 1 b 01 and complete the proof under that assumption Of course whether it is clear that knowing a result in one case implies that it is true in the other case depends on the situation and on the mathematical background of one s readership If the author of a text you are reading says without further explanation that without loss of generality some assumption may be made this means that he or she judges that the reduction to that case should be straightforward for students at the level at which the text is aimed and you should take up the challenge and see whether you can supply the reason If you can t you should ask your instructor In other cases an author may say explicitly why a without loss of generality statement is justi ed You should then look carefully at the arguments by which he or she reduces the general case to the special case Mathematicians writing for other mathematicians often abbreviate without loss of generality to wlog but this abbreviation seldom appears in undergraduate textbooks The turns of phrase listed above are ones that I have seen students have a great deal of trouble with The next couple haven t led to problems as often but they are also worth noting once one has mastered the preceding ones maximal This is a term that is used in the context of sets that have among their members a relation of some being greater than others This is not the place to discuss the various ways in which such 12 relations arise so I will just talk about one case sets with the greater than relation being the relation of one set containing another So suppose S is some set of subsets of a set X Then an element Ae S is said to be maximal in S if no other member of S contains it For instance if we take X 1 2 3 4 5 and let S consist of all subsets of X that do not contain any two adjacent integers integers that are next to each other in the list 1 2 3 4 5 then 1 g 13 g 135 are members of S and these inclusions imply that 1 and 13 are not maximal elements of S You might check for yourself that S has exactly four maximal elements 1 3 5 1 4 2 4 and 2 5 An element in such a set which contains all other elements is called a greatest element of the set If a set has a greatest element that will also be a maximal element but as the example of the preceding paragraph shows not every maximal element is a greatest element39 the set S of that paragraph does not have a greatest element An example of a set that has no maximal elements and hence also no greatest element is the set of all nite subsets of W by choice of This is best illustrated by an example If in an argument one has said Suppose the polynomial fx has a positive root r then if one later says that something is true by choice of r this means it is true because r is a root of fx or because r is positive or because both these statements are true in other words because of the assumptions we made when we speci ed r So the phrase by choice of is a signal to look back at the point where an element was introduced and see what was assumed about it Let me end with a warning about an incorrect use of words I have often seen students make If one wants to describe n2 rte Z it is not correct to call this the set containing all squares of integers because there are many sets that t those words For instance the set of all positive integers and the set of all real numbers both contain all squares of integers along with other elements The correct description of n2 rte Z is the set of all squares of integers If for some reason one wants a more emphatic word than of one may say the set consisting of all squares of integers or the set whose members are all squares of integers Math 110 Fall 05 Lectures notes 1 Aug 29 Monday Name class URL wwwcsberkeleyedu demmelma110 on board See Barbara Peavy in 967 Evans Hall for all enrollment issues All course material will be on the web page If this is inadequate please send me email and I will put copies at Copy Central Northside Read Course Outline on web page for course rules and grading policies You are responsible for reading this and knowing the rules Text which we will follow fairly closely Linear Algebra 4th Edition by FriedbergInselSpence same as last semester Topics following table of contents Chap 1 Vector spaces quotvectorsquot and their basic properties Chap 2 Linear transformations quotmatricesquot and their basic properties Chap 3 Elementary Matrix Dperations quickly Chap 4 Determinants Chap 5 Diagonalization eigenvalues and vectors Chap 6 Inner products orthgonality singular value decomposition Chap 7 Jordan Form generalizations of eigenvectors Examples why is linear algebra important Linear Equations Consider new Bay Bridge how is it designed How do they know it will be strong enough to hold up the traffic If you imagine a car sitting on the end of a beam you can write a simple relationship F force from weight of car on bridge k stiffness of beam x how much beam bends So if you know the weight of the car and the stiffness of the beam you can solve one linear equation in one unknown Fkx for x Fk to get the amount the bridge bends and compare that to how much you are willing to let it bend In a real bridge there are many cars many beams and many x s describing how each beam bends and the the beams are connected So instead of of 1 linear equation in 1 unknown you get thousands of linear equations in thousands of unknowns which civil engineers have to solve The same process applies to any important structures buildings airplanes cars certain computer chips See CE 130 ME 104 ASK amp ASK amp All radio light and other electromagnetic radiation in free space satisfy a system of linear equations called Maxwell s equations These are partial differential equations but linear nonetheless See Ph 7B or Ph 110 EG Aim 2 flashlights at board and observe that lit spot 1 is same whether or not beam 2 passes through beam 1 WAIT Can you explain this using linear algebra Eigenvalues and Eigenvectors WAIT Each of you depends on an eigenvector of one of the world s largest matrices many times each day How big is the matrix Hint what number do you see when you go to wwwgooglecom Schroedinger equation every atom molecule your physical body is most acccurately described as an quoteigenvectorquot of Schroedinger s equation which is a partial differential equation The eigenvalues correspond to energy levels and the eigenvectors describe how the electrons are distributed around all the atomic nuclei See Ph 7C or Ph 137 What we will cover We will concentrate on definitions and theorems describing basic properties of these linear algebra objects like linear transformations their inverses when they exist eigenvalues and eigenvectors when they exist In particular you will practice reading and writing clear and correct mathematical proofs We will also try to look at concepts and problem solving from at least 2 points of view algebra and geometry because linear algebra natually incorporates and can be understood both ways EG One can either say 2 equations in 2 unknowns can 1 have a unique solution 2 have no solutions 3 have infinitely many solutions or 2 lines in the plane can 1 intersect in a point 2 be parallel and not intersect 3 be identical What we will not cover practical algorithms for solving linear equations finding eigenvaluesvectors Ma128ab Ma221 This course is a prerequisite for such courses Prereq Math 54 including definitions of sets functions Apps A B Homework will be due Thursdays at the start of section There will be brief weekly quizzes to make sure people are keeping up To get started let s talk carefully about the numbers that we will be writing in our vectors and matrices As motivation Consider solving 2X 1 even though there are only integers in the equation we can t solve for X if we only look for X in Z set of integers we need Q set of rational numbers Consider solving X 2 2 0 even though there are only rational numbers in the equation we can t solve for rational X we need real numbers R Consider solving X 2 pi 0 even though there are only real numbers in the equation we can t solve for real X we need complex numbers C DEF A set of numbers also called scalars F is called a field if there are two binary operations addition and multiplication so that Xy and Xy are unique numbers in F for all X and y in F and such that and satisfy the following conditions 1 for all X and y in F XyyX and XyyX commutativity of addition and multiplication 2 for all X y z in F Xyz Xyz and Xyz Xyz associativity of addition and multiplication 3 There eXist distinct scalars O and 1 such that for all X in F XOX and X1X eXistence of identity elements for addition multiplication 4 For all X in F and nonzero y in F there eXist X and y such that X X O and yy 1 We denote X by X and y by y 1 eXistence of inverses for addition multiplication 5 for all Xyz in F Xyz Xy XZ distributivity ASK amp WAIT Is Z a field Why ASK amp WAIT Is Q a field ASK amp WAIT Is R a field ASK amp WAIT Is C a field ASK amp WAIT ls S ql q2sqrt2 q1 and q2 in Q a field ASK amp WAIT Is A all roots of polynomials with integer coeffs a field EG Z2 01 with OOO O11 11O OOO O1O 111 Can show this is a field homework ASK amp WAIT Does this field with its operations have other names EG Zp O12p 1 where p is a prime Xy Xy mod p remainder after dividing Xy by p Xy Xy mod p remainder after dividing Xy by p Can show this is a field homework Used in cryptography see Ma55 DEF A field F has characteristic p if 111 p times O for some positive integer p Utherwise F has characteristic 0 ASK amp WAIT What is the characteristic of Q ASK amp WAIT What is the characteristic of R C S A ASK amp WAIT What is the characteristic of Z2 ASK amp WAIT What is the characteristic of Zp EG FX rational functions in X with coefficients from another field F of characteristic 0 So fields don t have to be quotnumbersquot in the usual sense Some of the results in the book are for any field some are only for characteristic 0 We will try to carefully distinguish but when in doubt eg for homework assume characteristic 0 unless told otherwise The point of fields is that all the familiar rules of algebra just work In other words given the 5 properties above other familiar ones follow Thm Cancellation Laws a for all Xyz in field F XZ yz implies Xy b for all Xy nonzero z in field F XZ yz implies Xy Proof a homework b 2 nonzero gt exists 2 such that zz 1 then XZ yz gt Xzz yzz by def of mult gt Xzz yzz by associativity of mult gt X1 y1 by def of 2 gt X y by def of 1 Thm uniqueness of 01 inverses a O and 1 from part 3 are unique b x and y from part 4 are unique Proof a suppose there are two zeros O and 0 To show they must be equal note that 00 O by def of O and O O O by def of 0 Apply cancellation law to 00 OO O O ASK amp WAIT how do we prove b Thm aO 0 Proof 0 aO aO by def of O aO O by def of O aO aO by distributivity so 0 aO by part a of Cancellation Law Def Subtraction a b is defined as a b where b is additive inverse of Def Division ab for nonzero b is defined as a b 1 where b 1 is multiplication inverse of b Thm O 1 does not exist ie can t divide by zero Proof by last thm there is no a such that aO 1 First homework Review Apps A B Read App C Read Chap 11 14 Due Thursday Sep 8 1 Prove part a of Cancellation Law for all xyz in field F xz yz implies xy 2 Prove Z2 is a field Hint you can either make tables of all possible values needed to confirm the properties in the definition or claim it as a special case of the next problem Extra credit Prove Zp is a field Hint To show there is a multiplicative inverse of any nonzero b apply pigeon hole principle to set of p 1 numbers 1b mod p 2b mod p p 1b mod p 4 Sec 12 1 justify your answers 3 V 12 but for odd functions f t ft not even 15 16 19 5 Sec 13 1 justify your answers 2d 5 8 9 11 as stated and also changed to read quotfx0 and fX has degree lt 11quot 12 15 23 28 6 Sec 14 1 justify your answers 13 7 Sec 15 1 justify your answers 12

### 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

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

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "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!"

#### "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.