Intermediate Analysis MATH 3333
Popular in Course
Popular in Mathmatics
This 4 page Class Notes was uploaded by Alvena McDermott on Saturday September 19, 2015. The Class Notes belongs to MATH 3333 at University of Houston taught by Staff in Fall. Since its upload, it has received 36 views. For similar materials see /class/208423/math-3333-university-of-houston in Mathmatics at University of Houston.
Reviews for Intermediate Analysis
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/19/15
Math 3333 Intermediate Analysis David Blecher Logic and deductive reasoning Chapter 1 Lay The following will be a review for some so we will move quickly You probably will need to read this carefully several times as well as the additional discussionexamples in the textbook Statement a phrase that is either true or false but not both Mathematics consists entirely of statements and is thus either right or wrong Be sure that your statements7 are properly written and have meaning make sense A statement which is true is also sometimes called valid or is said to hold Example of a statement Seven is an even number7 Example of a non statement This sentence is false7 Or Houston is a nice place to live Sometimes we give a statement a name For example let Q be the statement Seven is an odd number Or if z is a real number let Pz be the statement x2 7 5x 3 2 0 Note P0 is true here but Pl is false Where things live In mathematics it is very important to keep remembering where things live7 By this I mean what exactly are the objects we are talking about This is where most students get into trouble For example if you are trying to prove something about a sphere in 3 space you will get into big trouble if you forget that your variable x is a point on the sphere and start using it as if it were a real number or a rational number Obviously you cannot take the square root of a point on the sphere and you cannot apply results that work for real numbers to points on the sphere This is just an example l7m just trying to say that one gets into trouble if you confuse the role of things and forget what something is supposed to be This is true in real life tool Negation If P is a statement then N P is its negation For example if Pz is as above then Pz is the statement 2 7 5x 3 lt 0 Connectives and7 A or7 that is the inclusive or7 see p 4 V Implication If P then Q Also sometimes written as P i Q7 or P implies Q7 We sometimes call P the hypothesis and Q the conclusion Necessarysuf cient One sometimes restates an implication P i Q as for Q it is suf cient that P This can be used in reverse for P to hold it is necessary that Q hold or Q is a necessary condition for P7 Deduction words Thus7 therefore7 hence7 consequently7 this implies that 7 and so on Also sometimes written as or i Converse The converse of P i Q7 is Q i P7 or P Q7 Contrapositive P i Q is the same as N Q i N P The latter may be easier Equivalence P if and only if Q Also written as P is equivalent to Q7 P iff Q7 P ltgt Q7or for P it is necessary and suf cient that Q7 To prove that P ltgt Q we need to prove both that P i Q and its converse Q i P The rst of these two steps is sometimes called proving the necessity the second proving the suf ciency To prove an equivalence we often rst prove one of these and then say Oonversely7 and then go on to show the other Or sometimes you will see an if and only if7 proof set up as follows Proposition 01 P if and only if Q Proof P i Q Suppose that P holds Then chain of reasoning so that Q is true Q i P Conversely suppose that Q holds Then chain of reasoning so P is true 1 Sometimes proving an equivalence is not done directly for example to show that P ltgt Q it is enough to prove that P i Q and N P i N Q If we have more than two statements which are to be proved equivalent we often use TFAE7 the following are equivalent A typical result of this kind may look as follows Theorem 02 Let Then TFAE39 i P ii Q iii R Proof holds iii i ii Suppose that R holds Then chain of reasoning so that Q holds ii i Finally suppose that ii holds Then chain of reasoning so that P holds V quanti er For all7 for every whenever7 For example Vm 2 22 7 5x 10 2 0 Also acceptable here x2 7 5x 10 2 0V 2 2 or even 2751020 9522 i i iii Suppose that P holds Then chain of reasoning so that iii or 275z102 0 9522 Proving a for all7 statement usually means taking an arbitrary or generic member z from the system under consideration in the example above we would need to take an arbitrary real number x 2 2 and show that the statement asserted about z is true 3 quanti er There exists there is at least one For example 3x such that 2 752 3 71 Often such that7 is written st or 9 Proving a there exists statement7 usually means nding a clever choice of a particular x that works eg z 1 in the last example Thus we have to construct7 maybe by guesswork or intuition an example satisfying the required condition However sometimes a there exists statement7 may be proved in other ways for example by contradiction assume its negation which is a for all7 statement and show that this leads to a contradiction well talk more about proofs by contradiction later Practice 22 in text Rewrite using the symbols iv a There exists a positive number x such that 2 5 Answer 3x gt 0 st 2 5 b For every positive number N there is a positive number M such that N lt 1M Answer VN gt 03M gt 0 st N lt c If n 2 N then 7 S 3 for all z in A Answer V71 2 NVz E A 7 MM s 3 Order of quanti ers etc matters so be careful Vz y st y gt x7 is not the same statement as Hy st Vay gt 7 See end of Section 2 in text Negations of statements with quanti ers A rough guide when negating statements with quanti ers is that V7s become 3 37s become V and inequalities reverse More precisely the negation of VPx7 is Hz st N P7 and the negation of Hz st Px7 is Vx N P7 Thus the negation of Everyone in the room is asleep or equivalently the negation of Vz in room z is asleep is Hz in room st z is asleep That was a good test if you were awake Also the negation of P Q is N P V N Q and the negation of P V Q is lt P A lt Q Examples 23 in text What are the negations of the following statements a For every x 6 A7 f gt 5 Answer Hm E A st gt 5 7or Hm E A st fx 3 5 b There exists a positive number y such that 0 lt gy S 1 Answer Vy gt 0 0 lt gy S 1 Since 0 lt gy S 1 represents 0 lt S 17 its negation is 0 2 V gt1 So the nal answer is Vy gt 070 2 V gt 17 which in English reads For every y gt 07 either 0 2 gy or gy gt c V6 gt 0 EN st 7 lt 6 whenever n 2 N7 E A Answer We can do this one step at a time V6 gt 03N st V71 2 N7 6 A7 7 lt e ltgt 36 gt 0 st 3N st V71 2 N7 E A7lfn 7 lt e ltgt 36 gt 0stVN V71 2 N7 E A7lfn 7fxl lt e ltgt 36 gt 0st VN 371 2 N7 E A st 7 lt e ltgt 36 gt 0 st VN 371 2 N7 and 3x 6 A st 7 2 6 Respectively7s Often to save writing an only slightly changed sentence7 we use the word respectively7 For example The function fx is strictly increasing resp strictly decreas ing if f gt 0 resp f lt 0 for all 7 You are supposed to read the statement twice7 once without reading the words in parentheses7 and then again with the words before the parentheses replaced by the words in parentheses Similarly7 if a sentence is only slightly changed more than once For example The function f is strictly increasing resp strictly decreasing7 constant if f gt 0 resp f z lt 07 f 0 for all 7 Techniques of proof Deductive reasoning Suppose you are trying to prove that P implies Q As explained in Section 3 of the text7 this usually boils down to building a bridge of logical statements7 to connect the hypothesis P to the conclusion Q The building blocks of the bridge consist of 7 De nitions the basic meanings of the words used7 usually of the key words contained in P and Q7 7 Theorems or facts that have been previously established as true look for those using the key words contained in P and Q7 7 Statements that are logically implied by earlier statements in the proof7 7 Axioms These occur less frequently in proofs7 they are the basic assumptions one makes at the beginning of a theory7 and one does not usually discuss them too much after the rst few days of class The MOST IMPORTANT and most frequently useful technique for proving results in this class is to GO BACK TO THE DEFINITION When actually building the bridge7 it may not be at all obvious at least to a begin ning bridge builder7 which blocks to use7 and the order to use them in This comes with experience7 perseverance7 intuition7 good logical abilities7 and sometimes good luck In trying to prove P i Q7 the text suggests starting at both ends and working to the middle Ask What does P imply777 Answering this is usually just a matter of looking up the de nitions of the words in P7 and seeing what then must obviously follow Often it entails looking back in your notes to see what previously established Theorems or facts we can bring to bear on P Suppose then that we realize that P i P1 actually there may be several things that P implies Then ask what P1 implies7 using a similar process to the one we just went through Continue this process until you build a chain or chains of deductions7 and you can go no further If you havent reached Q yet7 start to work backwards from Q7 H asking What statement would imply Q777 Again answering this is usually just a matter of looking up the de nitions of the words in Q and using your head or looking back in your notes to see what previously established Theorems or facts we can use to get Q Once we have realized that Q1 i Q we repeat the process to nd Q2 with Q2 Q1 Hopefully the two parts of the bridge meet in the middle This is deductive reasoning When one gets good at it it becomes pretty automatic like eating popcorn you reach automatically and quickly for the de nition or fact you need to add to the bridge and the bridge is built in seconds It is a messy process sometimes cramming a lot of popcorn in your mouth but once a shoddy bridge is built one can then write it again economically and so that it reads nicely Example of working backwards Suppose that you were asked to prove the following Theorem 03 For every 6 gt 0 there edists a 6 gt 0 such that 176ltzlt16 impliesthat 576lt2z3lt56 Note that here we want 5 7 6 lt 2x 3 lt 5 6 Subtracting 3 the above is equivalent to 2 7 6 lt 2x lt 2 6 Dividing by 2 the last inequality is equivalent to 17 62 lt z lt 1 62 Thus if we choose 6 62 then indeed 176 lt z lt 16 implies that 576 lt 23 lt 56 We can now tidy up and write the proof economically and so that it reads nicely Proof Given any number 6 gt 0 set 6 62 Then 6 gt 0 lf17 6 lt z lt1 6 then 1 7 62 lt z lt 1 62 Multiplying this inequality through by 2 and then adding 3 we obtain 5 7 6 lt 2x 3 lt 5 6 This is what was required Proof by cases Many proofs divide naturally up into different cases each of which need to be dealt with separately For example this occurs frequently when one has to divide by a certain quantity in a proof One cannot divide by 0 so one has to break the proof into two cases rst the case where the quantity is not zero and second the case where the quantity is zero In the latter case we cannot divide through by the zero quantity and the proof has to be nished in another way Another example read 45 Example in the text Proof by contradiction One way to prove a statement P is to assume that it was false that is we assume that N P is true and then use deductive reasoning to deduce a statement Q where Q is clearly false This is proof by contradiction or reductio ad absurdum Or if we want to prove that P i Q it suf ces to show that P N Q leads to a contradiction Techniques of disproof Disproving a false statement is often harder than proving a true statement because it often means nding a counterexample A counterexample is an example showing that a statement is false Finding examples is sometimes hard Here is one that is not so hard it just takes a few minutes of perseverance Show that the statement n2 n 17 is a prime number for all positive integers n7 is false Solution n 16 is a counterexample Another way to disprove a statement P is to assume that it was true and then use deductive reasoning to show that P i Q where Q is clearly false This is also proof by contradiction General advice Write down all your reasoning particularly if you are new at this or if you want a good grade Don7t say it is clear7 if it would not be clear to a classmate Homework for Chapter 1 is on my website
Are you sure you want to buy this material for
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'