Foundations of Analysis
Foundations of Analysis MATH 314
Popular in Course
Breanne Schaden PhD
verified elite notetaker
Popular in Mathematics (M)
This 7 page Class Notes was uploaded by Breanne Schaden PhD on Saturday October 3, 2015. The Class Notes belongs to MATH 314 at Boise State University taught by Melvin Holmes in Fall. Since its upload, it has received 25 views. For similar materials see /class/217993/math-314-boise-state-university in Mathematics (M) at Boise State University.
Reviews for Foundations of Analysis
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/03/15
Manual of Logical Style M Randall Holmes February 15 2007 This is the promised or threatened document about how to write proofs It is based on the idea that the logical form of a sentence provides a strong hint as to the appropriate strategy for proving it if it is a goal or using it if it is an assumption 1 A Menagerie of Logical Forms A mathematical statement is of one of the following forms usually atomic No logical structure equations or inequalities are examples of atomic statements negation It is not true that A We often say not A for brevity but this is not a correct English sentence construction The logical notation for this is A Negation is often absorbed into atomic sentences we7ll say a a b instead of no b and a S b instead of no gt b for example Negations of logically complex sentences are very awkward to express in English conjunction A and B In formal logical notation this is written A B disjunction A or B Remember that in mathematics this usually means A or B or both lawyers write A andor B to make the same point clear In logical notation this is written A V B implication if A then B A implies B B if A A is suf cient for B B is necessary for A There are all kinds of ways to say this because it is important The logical notation is A a B It is important to note that for a mathematician A a B is false just in case A is true and B is false7 and is true under all other circumstances In particular7 A a B is always true if A is false This is not just a convention about symbolism nothing here is really about symbolism it applies just as well to the mathematician7s uses of the English phrases above biconditional A if and only if B 7 A i B The logical notation is Alt gtB universal quanti er for all 7 Pm for every 7 Pm 7 similarly any 7 each Some of these English words behave di erently when nested quanti ers are involved if we run into trouble with this Ill try to say something about it The formal notation is Restricted forms like Vm E AP or Vm lt can be rewritten with an implication wa E A a or wa lt n a existential quanti er for some 7 Pm there is m such that Pm there exists m such that Pm The logical notation is Restricted forms like Hm E AP or Hm lt can be rewritten as quanti ed conjunctions 3mm 6 A or 3mm lt n disguised quanti ers All men are mortal is a disguised universally quan ti ed implication For all L if m is a man then m is mortal Similarly7 Some unicorns are obnoxious is a disguised existentially quanti ed conjunction For some L m is a unicorn and m is obnoxious implicit universal quanti ers It is very usual in mathematics to conceal universal quanti ers the statement m y y m of algebra really has the logical form VmWyw y y Here I have omitted the intended domain of the quanti ers7 which is also something that sometimes happens Vm E RWy E Rx y y is better This can cause confusion when such a statement is to be negated whereupon a transformation is usually applied which converts the implicit universal quanti er into an explicit existential one remark on dummy variables Just as there is no speci c real number if mentioned in the expression fol t2 df7 so there is no object m mentioned in a universally quanti ed sentence or in an existentially quanti ed sentence This is harder to see somehow for the existential statement7 but notice that the m mentioned in 2 may for example not be uniquely determined in Hm E sz 1 it is not correct to say that m is 1 or to say that it is 71 it is not correct to say that it is 1 or 71 either though it is tempting m simply does not name any speci c number at all 2 Negating Complex Sentences de Morgan s Laws We commented above that it is awkward to negate complex statements in English In fact it is usual to automatically transform negations of complex sentences into sentences in Which simpler sentences are negated The trick is to do this correctly negation Of course A is equivalent to A conjunction To say It is not the case that both A and B is to say A is false or B is false or both In symbols A B is equivalent to A V B disjunction To say It is not the case that either A or B is to say A is false and B is false In symbols A V B is equivalent to A B implication To say that A does not imply B is to say that A is true and B is false This can be confusing When the negated statement is not really strictly an implication a statement P does not necessarily imply Q may really be the negation of an implicitly universally quanti ed implication in symbols VPx a Q Which transforms to Hm PQ a Q Which transforms to 3P Q that is for some m Pm but not Qx Notice that but has the same logical meaning as and but here conveys a comment that the second conjunct might be surprising biconditional To say that A i B is false is to say that A is true and B is false or to say that A is false and B is true It is also equivalent to the exclusive sense of or A or B but not both universal quanti er To say that it is false that for all m Pm is to assert for some m P ln symbols VP is equivalent to 3 P We have already used this above in the discussion un der implication This is an important principle to deny a universal statement is to assert the existence of a counterexample existential quanti er To say that it is false that for some a P77 is to assert for all a P ln symbols 3P is equivalent to V P 3 General Remarks Goals and Assumptions We divide the statements mentioned into a theorem into two classes goals and assumptions A goal is a statement we are trying to prove an assumption is a statement we are allowed perhaps just locally to a part of the proof to assume is true Our proof strategy falls into two parts pointers on how to prove goals of particular logical forms and pointers on how to use assumptions of particular logical forms in proofs It is convenient to introduce the name l for a false statement the absurd 4 Proving Statements of Given Logical Forms In this section we give strategies for proving goals of given forms One of these proof by contradiction actually applies to a statement of any form at all negation To prove the goal A introduce A as an assumption and take l as the new goal assume A and show that an absurdity follows This is a direct proof of a negative statement it is not the same thing as proof by contradiction which is described below Notice that the assumption A is local to this part of the proof if it occurs as a subproof of a larger proof once l is proved the assumption A goes away conjunction To prove the goal A B rst prove A then prove B or if you prefer rst prove B then prove A implication To prove the goal A a B assume A then adopt B as the new goal note that once B is proved the assumption A goes away the assumption is local to the proof of the implication 4 There is an alternative strategy7 which is to prove the equivalent con trapositive statement B a A assume B and adopt A as the new goal Note that negative assumptions and goals may have the trans formations of negative sentences described above applied to them as a matter of course if you use these transformations make sure you use them correctly To prove the contrapositive is once again not quite the same thing as proof by contradiction disjunction To prove the goal A V B one could if one were lucky just prove A or just prove B7 but unfortunately this does not always work Our of cial strategy for proving A V B as a goal comes in two symmetrical avors either Assume A and prove B as the new goal or Assume B and prove A as the new goal biconditional To prove the goal A lt gt B is to prove the goal A a B then prove the goal B a A The proof of a biconditional falls naturally into two parts Further7 the contrapositive might be proved instead of one or both of the implications A proof outline might look like this Assume A now prove B assume B now prove A It is important to notice that the assumption in each part can only be used in that same part Once B is proved at the end of the rst part7 neither the assumption A nor anything deduced from that assumption in the rst part of the proof can be used in the second part of the proof Another possible proof outline using the contrapositive on the second part is Assume A now prove B assume A now prove B proof by contradiction To prove a statement A of arbitrary form7 assume A and aim for the new goal l Notice that this is the same as proving A by the strategy for proving a negation universally quanti ed statement To prove 7 let a be an ar bitrary object about which no additional assumptions can be made and prove Pa as the new goal To prove Vm E AP7 let a be an arbitrary object7 assume a 6 A7 and prove Pa as a new goal Notice that once this proof is complete7 there is no further need to refer to the arbitrary object a it is local to this proof existentially quanti ed statement To prove 3P nd a speci c 75 for which you can prove Pt To prove Hm E AP nd a speci c 75 for which you can prove t E A and prove Pt Here you actually have to gure out what object 75 will work 3P can also be proved by assuming V Px and deducing a contradiction Such a proof of an existential statement is surprising because it does not necessarily tell us what object if has Pt true 5 Using Assumptions of Given Logical Forms negation If you have shown or assumed A and A deduce any proposi tion B in particular this is the only way that l can be deduced conjunction If you have proved or assumed A B you have also shown A and B separately disjunction If you have proved or assumed A V B and want to prove goal G it is time for the strategy called proof by cases assume A and prove G then assume B and prove G and you have shown that G follows from A V B Also if you have proved or assumed A V B and also A you can conclude B and similarly if you have proved or assumed A V B and also B you can conclude A implication If you have proved or assumed A and you have proved or assumed A a B you have shown B This is called modus ptmens If you have proved or assumed A a B and you have proved or assumed B you can draw the conclusion A This is called modus tollens biconditional You can draw the same conclusions using A lt gt B that you can draw from either A a B or B a A universal quanti er If you have proved or assumed and t is any speci c object you can draw the conclusion Pt If you have proved or assumed Vm E AP and t is a particular object for which if E A has been proved or assumed then you can conclude Pt existential quanti er If you have proved or assumed 3P then you can introduce a new object 0 with the assumption Pc you are not 6 allowed to assume anything else about 0 c is otherwise arbitrarily Cho sen lf you have proved or assumed Hm E AP7 then you can introduce a neW object 0 With the assumptions 0 E A and Pc