Class Note for MATH 300 at UMass(4)
Class Note for MATH 300 at UMass(4)
Popular in Course
Popular in Department
This 34 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 16 views.
Reviews for Class Note for MATH 300 at UMass(4)
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: 02/06/15
Appendix L A September 17 2007 draft No exciting books suit feverish patients Unexciting books make one drowsy 39 No books suit feverish patients except such as make one drowsy 7 Lewis Carroll This appendix1 reveals a bit of the logical infrastructure needed for mathematicsijust enough we hope to get you going in reading and writing proofs It discusses what is meant by combinations of state ments formed with such words as or and if then and how the quan tifying phrases for every and there exists are applied It points out some of the most common patterns of mathematical proofi but your best guide to what patterns are considered legitimate are the actual proofs throughout this book What it includes is treated for the most part informally and descriptively One of the dif culties with learning logic is that logic ought to pre cede everything else in mathematics that uses it yet without any other mathematics to treat logic is wholly abstract Accordingly to explain logical ideas we shall often have to talk about mathematical sets num bers functions etc along with a few examples from our everyday lan guage about the real world For the essentials about sets and functions see Appendix A and Appendix B In a few instancesifor example the more generous meanings in logic of or and there exists ilogical language differs a bit from every day usage Otherwise logic just makes explicit and crisp those patterns of deductive reasoning used by careful speakers and writers 1Copyright 2007 Murray Eisenberg All Rights Reserved L2 Appendix L A Little Logic September 17 2007 draft L1 The logic of solving equations What is really going on from a logical Viewpoint when you carry out familiar algebraic steps to solve an algebraic equation or an inequality or a system of equations or of inequalities Example L11 Consider the quadratic equation x2 x 7 6 0 To solve this you would write something like this x2x7670 x72x30 x720 x30 262 2673 and then write the solution as x 2 73 Several questions arise First what do the commas mean in the expres sions x 296 73 and x 2 73 We understand the commas to mean or so that both expressions mean 26 2 or x 73 there are two values of x that are solutions of the original equation Second what is the connection between successive lines in the write up Presumably it is not just that an x satisfying the equations in one line also satis es the equation in the succeeding line but also that an x satisfying the equations in the succeeding line also satis es the equations in its preceding line For example it is not just that if a value of 6 satis es x2 x 7 6 0 then the same value of 6 satis es 6 7 2 x 3 0 but also if avalue ofx satis es 6 7 2 x 3 0 then the same value of 6 satis es x2 x 7 6 0 In other words you can not only go from one line to the next but you can also go from that next line to the one preceding it the steps are reversible Put more tersely anx satis es the equations in one line if and only if it satis es the equations in the succeeding line the assertions in the one line and the succeeding line are logically equivalent to one another Such logical equivalence is indicated by the symbol ltgt which may be read as if and only ifquot Thus a more careful writeup of the solution would be x2x7670 ltgt x72x30 ltgtx7200rx30 ltgtx20rx73 L1 The logic of solving equations L3 By the way sometimes the two letters in or are more than we want to write and then we use the logical symbol v to mean or Thus as we found above x2x760 ltgtx2vx73 How would you answer the question of what the solution to the original quadratic equation is You might write X23 just as in the original writeup and say The solutions are 2 and 73 Yes you would doubtless use the word and but surely you would not intend to suggest that a particular solution has both the values 2 and 73 at the same time It is still a matter of or rather than and You can avoid the and or confusion in such situations by using an expression such as x 2 or x 73 explicitly involving or You can also avoid the confusion by giving the solution set of the equationi the set of all solutions In the example the two numbers 2 and 73 are solutions and no other number is a solution Thus the solution set S is given by S 2 73 and this means exactly S xx20rx 73 Thus a number 6 belongs to the set S exactly when x 2 or x 73 more brie y xES ltgtX201 X3 Unless you are careful about the logic of what you are doing you may get results that are not only confusing but actually wrong Look at the next example Example L12 Consider the algebraic equation x xx2 7 S 1 To solve this you might write x x2751 m7xl mgt27x12 x275x272x1 2266 x L4 Appendix L A Little Logic September 17 2007 draft and thereby conclude that the given equation has unique solution 3 But you would be wrong In fact 3 does not satisfy the original equation 3x327S32S 1 So what went wrong There were no slipups in the algebraic manip ulations and each step in the writeup from one equation to the next is correct What is wrong is that one of the steps is not reversible the step from xx2 7 726 1 to XXZ 7 S2 7x 12 Every other step is reversible In general it is correct that if a b then a2 b2 However it is not in general correct that if a2 b2 then a b All you can conclude from a2 b2 is that a b or a 7b In the situation with our equation take a xX2 7 S and b 7x I and note that a2 x2 7 S because y2 p for every positive number p In view of the preceding analysis a careful writeup of the solution would be x x27571 ltgt xx27577x1 2 xx275 726712 not ltgt ltgt x275x272x1 ltgt 2266 ltgt x73 There is one step having just an if then form7implicati0n7as indi cated by the symbol gt since that step is not reversible the implica tion 7 cannot be replaced with a logical equivalence ltgt Hence all that the writeup tells us is If 6 satis es the original equation then 6 must have value 3 But as we checked 3 is not a solution of the origi nal equation 3 is as some people refer to it an extraneous solution which was obtained by squaring the squareroot The given equation has no solutions whatsoever Then its solution set S is the set to which no number belongs S ll This set with no elements is the empty set denoted by Q Strictly speaking none of the logical equivalences or implications used above make sense because they are not quali ed in any way as to the domain of values of their variable x for which they are allegedly true Thus in Example L11 about solving the equation x2 x 7 6 0 probably the intent was to nd the real numbers 6 that are solutions In L1 The logic of solving equations LS that case the writeup of the solution at the bottom of page L2 should really look like this Vxe Rx2x760 S x72x30 S x7200rx30 S x20rx73 Here the initial string Vx E R is read as For all x in Rquot or more verbosely as For all real numbers 6quot Here R stands for the set of all real numbers And then the intention is that each of the equivalences is true for every real number As it so happens the solutions of the equation x2 7 x 7 6 are integersielements of the set Z of all integersiso it would be equally correct to write Verx2x760 S x72x3 0 S x7200rx30 S x 2 or x 73 Of course until you actually work through the steps of solving the equa tion you would not necessarily know that the solutions were actually integers So it would be safer to work with R instead of with Z But for some other equations not even R might be a large enough set of numbers you might need say the set C of all complex numbers For example VxECx29O S x73ix3i 0 S x73i00rx773i 0 S x 3iorx 73139 Here i is the complex number having the property that i2 71 Thus the solution set here is 31 73139 Exercise L13 Suppose nonetheless you tried to work out a solution of x2 9 0 using the set R of real numbers Vxe Rx290 S x What might you write as the end where the dots are This is a question you might need to ponder for a while And what is the solution setias a subset of R The equation x2 x 7 6 0 has at least one solution in fact it has precisely two solutions that are real numbers To indicate it has at least one we write Elx Rx2xi6O L6 Appendix L A Little Logic September 17 2007 draft The string Elx E R is read as There exists 6 in Rquot or more verbosely There exists a real number xquot The logical connectives 0r implies S and if and only if S already used above as well as the connectives not 3 and and amp can help solve inequalities too Example L14 The problem we pose is to solve l2x 7 ll 2 3 But it is simpler to solve the inequality l2x 7 ll lt 3 l2x71llt3 S 73lt2x71lt3 S 72lt2xlt4 S 71ltxlt2 In other words l2x71llt3 S 71ltxampxlt2 Then l2x71l23 S 3l2x71llt3 S 71ltxampxlt2 S il lt x or x lt 2 S x s 71 orx 2 2 The nexttolast equivalence above used one of De Morgan s Laws of logic Tautologies L410 namely 3P amp Q S P or 3Q In terms of sets the solution set T of l2x 7 ll lt 3 is T 712 x71ltxampxlt2 x71ltx xxlt 2 7100 ioo2 whereas the solution set S of the original inequality l2x 7 ll 2 3 we found is Sxxsilorx22 xxsiluxx22 70 1 U 2 0 The logical equivalence l2x 7 ll 2 3 S 3l2x 7 ll lt 3 may be expressed in terms of the solution sets S and T of l2x 7 ll 2 3 and l2x 7 ll lt 3 respectively as SRT In other words the subset S of the set R of all real numbers is the complement in R of its subset T Thus SRSloo ioo2 L1 The logic of solving equations L7 Notice the different meanings of parentheses there the inside ones are used to denote open rays whereas the outer ones are punctuation One of De Morgan s Laws about sets Proposition A14 implies that SR71 7002 R71 UR7002 70 71 U 2 00 Of course that is the same solution set obtained before Exercises L15 Give careful writeups including appropriate use of or amp gt and ltgt for solving the equations or inequality Do this both without using and with using the V quali cation Then tell what the solution set is using the setbuilder notation 1 x372x275x670 2 x71x2 lt0 3 x 7 12 lt 4 4 x 4 wsz 14x Exercise L16 The equation x xx2 7 S l in Example L12 has no solutions whatsoever and we indicated this by writing that its solution set is the empty set Q How without referring to the solution set might you indicate that the equation has no solutions Hint Recall that the notation El may be used to indicate existence of an equation s solution Exercise L17 Let fx 5x4 7265 Determine a the set x f x 0 of all critical points of f b the set x f x gt 0 on which f is increasing and the set x f x lt 0 on which f is decreasing c the set x f x gt 0 on which f is concave upward and the set x f x lt 0 on which f is concave downward Exercise L18 For which values of x is xXl 7 6 de ned as a real number In other words in Calculus I terms what is the domain of x 1 7 x L8 Appendix L A Little Logic September 17 2007 draft L2 Formulas and Statements Section Ll introduced informally the logical symbols v amp ltgt and gt which connect statements about mathematical objects In order to understand just how these logical symbols behave you need rst to understand how to form such statements and objects And to un derstand that involves looking at a rather quotformalquot description of the language of logic and mathematics To begin we need symbols Our symbols will include letters such as x C N and A to make things more readable and to prevent us from running out of letters when many are involved we allow letters to be ornamented in various ways such as x b Aoy99 N17 the logical connectives negation v disjunction conjunc tion gt implication and ltgt equivalence the logical quanti ers V universal quanti er El existential quan ti er and 1 descriptor the settheoretic signs equality and E elementhoodithe lat ter not to be confused with the Greek epsilon E and parentheses as punctuation marks In actual mathematical writing we often use ordinary words and whole phrases instead of the connectives quanti ers and other symbols Such words and phrases used as shown in Table Ll on page L9 sug gest the meanings we intend for the corresponding symbols Here are some mnemonics for the logical connectives and quanti ers The symbol is reminiscent of a negative sign it means not The symbol amp is the usual ampersand it means and The symbol gt in P Q goes from P to Q it means ifP then Q The symbol a in P a Q goes from P to Q as well as from Q back to P it means P ifand only ifQ The symbol V resembles an upsidedown letter A it means forull The symbol El resembles abackwards letter E it means there exists The descriptor 1 is an upsidedown Greek letter iota L When we use such words as part of English sentences with embedded mathematical L2 Formulas and Statements L9 Table L1 Meanings of logical symbols Symbolism Meanings nP not P it is not the case that P PampQ P and Q both P and Q P but Q P yet Q P whereas Q P VQ P or Q P andor Q either P or Q or both P and Q P Q P implies Q if P then Q P only if Q Q if P Q provided that P P is suf cient for Q Q is necessary for P Q because P Q since P P whence Q P lt2 Q P if and only if Q P iff Q P is logically equivalent to Q P is necessary and suf cient for Q P precisely when Q VXP for all x P for every x P for each x P for arbitrary x P for any x P 3XP there exists 6 such that P there is an x such that P for some 6 P 7XP the x such that P the unique 6 such that P xy 6 equals 3 xeY x is an element of Y x is a member of Y 6 belongs to Y x is in Y L10 Appendix L A Little Logic September 17 2007 draft symbolism we shall also use commas and other punctuation besides parentheses Writing one or more of such symbols in succession gives us a string For example x and x E A are strings2 A letter 6 is said to be bound in a string S in case any one of the strings Vx Elx 1x occurs as part of S3 Otherwise the letter is said to be free in the string In particular the letter is free in the string if it does not occur there at all Here are two examples which use the notations N for the set 0 I 2 of all natural numbers and Z for the set 72 710 I 2 3 of all integers First 11 is bound in VnWLE N 2ngtn which means that the double of each natural number is greater than the number itself Second 11 is bound in 1nnEZamp2nn which represents the one and only natural number whose double is itself namely 0 However 11 is free in each of the three strings 2ngtn neN2ngtn kENgt2kgtk When a particular occurrence of a letter 6 is bound in a string S because that occurrence is within part of S that has one of the three form Vx P Elx P 126 P then that occurrence of x is said to be within the scope of that quanti er V El or 1 Most strings we could write would be utter nonsenseithe sort of thing a roomful of monkeys typing at random would produce before they ever happened to get around to Shakespeare The strings that are to be regarded as meaningful are terms and formulas Informally a term denotes an object that the logical language talks about such as the natural number 0 the set of those 6 for which 6 at x the set of natural numbers the variable x A formula by contrast denotes an 2We just mentioneditalked aboutithree speci c strings and therefore used single quotes around them in order to name them In a formal presentation of logic we would have to distinguish carefully between things and the names of things In our informal treatment we shall be rather sloppy about the distinction and we will revert to the more careful naming only when it would be utterly confusing not to do so For example once we begin to use the word and in place of the connective amp to mean Pamp Q we shall need to write P and Q rather than P and Q lest we confuse the latter with the phrase P and Q as in the assertion The statements P and Q are true 3We just did iticonfused the name of a thing with the thing itself When we wrote in a string 5 we did not necessarily mean to refer to the oneletter string 5 but rather an arbitrary string that we are temporarily naming 5 L2 Formulas and Statements L11 assertioninot necessarily trueiabout such objects such as SEN l2l3 15 Elx x E RampVyy E R gt x gty Thus a formula in the sense meant here need not at all be a formula in the customary sense such as V nrzh telling how to compute one quantity from others More formally terms and formulas are those strings that can be built up by a nite number of applications of the following rules each letter is a term if X and Y are terms then both X Y and X E Y are formulas if P is a formula then P is a formula ifP and Q are formulas then each of P v Q P Q P Q and P ltgt Q are formulas if P is a formula and x is a letter that is free in P then both VxP and ElxP are formulas and if P is a formula and x is a letter that is free in P then 126 P is a term For example Vxnxx and 7AVxx A ltgt nxx are formulas The rst of these makes the false statement that each object is unequal to itself The second represents the object character ized by the property that no object belongs to itithe empty set Notice that a string such as VxExx 26 is not a formula according to the preceding rules because the letter 6 is already bound in Vxx 6 On the other hand VxElyx E 31 is a formula Obviously formulas and terms written in strict compliance with those rules can be awkward to read because of their length and all the nested parentheses In practice we shorten such strings to make them more readable and writable One way to do so is to omit any pair of parentheses immediately surrounding any quanti ed formulaione of the form Vx P Elx P or 126 Piin a larger formula Thus we write VxEYx E Y L12 Appendix L A Little Logic September 17 2007 draft to mean Vx3Yx E Y and write Vxx x v 3y y 31 to mean Vxx 20 V HyH O y Terms and formulas become still shorter and more readable when additional parentheses are omitted in accordance with a rule of order of precedence The order of precedence in logic is similar to the one in algebra where multiplication takes precedence over addition so that x 3 2 means 6 3 2 rather than 26 3 2 In logic ifwe consider the connectives and settheoretic signs in the order lt7 weaker E n amp v gt ltgt stronger a from weakest to strongest then the rule is when parentheses are missing the stronger sign reaches further For example 6 E A v x EBmeansx EAvx EBandx y gt x EAmeans x y gt x E A The formula on page L11 may now be written in the shorter form Vx n x x and the term on page L11 may now be written much more readably as 1AVxx EA a x x The rule of precedence hardly allows us to remove all parentheses For example the string P gt Q gt Q gt P is ambiguous When parenthesized as PgtQ gt Qgt P it will turn out to be a true formula no matter what the formulas P and Q are when parenthesized as gt P it is a formula that is true for some formulas P and Q but false for others namely when P is true and Q is false Such examples suggest two of the commonly used de nitionsi abbreviations in effectishown in Table L2 These de nitions provide another way to shorten formulas and terms L2 Formulas and Statements L13 Table L2 Some common logical abbreviations Abbreviation Stands for Meaning Xi uXy 3615 not equaltoy x e A x 6 A x is not an element of A VXEXP Vxx XgtP forallxinXP 3x 6 XP 3xx E X ampP there exists 6 inX such that P With the rst of the abbreviations in Table L2 along with omis sions of super uous parentheses the formula and the term from page L11 may be written in the still shorter forms Vxx at x and 1AVx 6 EA a x at 6 What do you now think the preceding formula and term mean Use Tables LI and L2 Some quanti ed formulas such as Vxx x are intended to make universal statements about all possible objects Many quanti ed formulas however are intended to make statements about only those objects that are elements of some particular set Here are two expressed in typically informal mathematical language Every integer n that is a multiple of 4 is even Some real number has square 2 These statements are in other words For every integer n if n is a multiple of 4 then 11 is even There is a real number x such that x2 2 The intended meanings of these statements are For every n E Z if n is a multiple of 4 then 11 is even There exists 6 E R such that x2 2 And the latter two statements in turn are understood to mean For every n if n E Z then if n is a multiple of 4 then 11 is even There exists 6 such that x E R and x2 2 L14 Appendix L A Little Logic September 17 2007 draft Using the nal two abbreviations in Table L2 we may express these statements more formally using quanti ers as V11 6 Z n is a multiple of 4 gt n is even Elx e emf 2 Suppose you were asked to prove the rst of these two statements To do so you would of course have to know the precise meaning of n is a multiple of 4 and n is even By de nition 11 is even when n 2 k for some integer k that is ElkEZn2k Exercise L21 a Write a de nition for n is a multiple of 4 rst including words and then using symbols alone b Using your de nition from a and the meaning of even now prove V11 6 Z n is a multiple of4 gt n is even c What if anything is wrong with the following proof of the state ment in b Proof Let n E Z Assume n is a multiple of 4 Let k be an integer for which n 4 k such exists by the meaning of multiple of 4 Then also 11 2 k This means that n is even d Is it true that V11 6 Z n is even gt n is a multiple of 4 If so prove it if not tell why not Exercise L22 Symbolize the formula saying that for no integer n gt 2 does the equation aquot bquot cquot have a solution in integers a b and 6 other than a b c 0 You may use the term Zithe set of all integers Then try to write the symbolized formula without using the abbreviations and omissions of parentheses discussed above Exercise L23 Symbolize the following sentences a The squares of real numbers are nonnegative b A differentiable function is continuous Use f to denote the set of all realvalued functions of a real variable According to the rules for forming terms and formulas terms are of two typesithose of the form 126 P and those that are single letters A term of the form 726 P represents a speci c object such a term is like a proper noun Neil Armstrong or a de nite description the rst L2 Formulas and Statements L15 human to walk on the Moon in ordinary English A term that is a single letterialso called a variableiambiguously represents an unspeci ed object a variable is like a common noun a person a thing or a pronoun she it When a formula or term is or includes a string of the form Vx P ElxP or 1xP then the letter 6 is sometimes called a dummy variable This terminology is used to indicate that without the meaning being altered the variable could be replaced by any other letter not already occurring in that formula or term Thus the two formulas For everyx E Nx2 20 For everyn 6 N112 2 0 although different say in effect the same thing namely that the square of each natural number is nonnegative We stipulate that in such a case one is true exactly when the other is true Likewise the terms 1yVx x E y ltgt x at x ISVy y 6 S ltgt y at y are different but represent the same object namely the empty set Q We stipulate that in such a case the two objects are equal The situation with dummy variables in logic is akin to the one in cal culus where the letter 6 in 01 22 dx is a dummy variable that could be replaced by any other letter except e and d 01 22 dx J01 e 2 alt But it is different from the situation with limits where there is a dis tinction between limit of a function of a real variable x on the one hand and the limit of a sequence de ned in terms of a discrete integer valued variable 11 on the other hand The convention in calculus is that letters such as x and y and I refer to real variables whereas let ters such as m and m and k refer to integers Thus the statement limxkoo 2x 1 x 2 refers to the limiting behavior of the function fx 2x1 6 de ned for all real 6 at 71 whereas the statement lim1boo 211 1 n 2 refers to the limiting behavior of the sequence 2243 64 85 106 Of course the formula for the limit of the function of the real variable 6 implies the formula for the limit of the sequence involving 11 In various realms of mathematical discourse it is not unusual to adopt conventions about the domains of different sets of letters just like those used in calculus In this book however we shall generally avoid such conventions and instead explicitly state the domain of the variables we use For example we would not write V139L1 L2 2 0 to suggest by agreementquot that the n is restricted to integers Instead we write V11 6 Z1 L2 2 0 L16 Appendix L A Little Logic September 17 2007 draft To deal with formulas involving dummy variables some notation helps If x is a letter that occurs in a string P and that S is a string then Pan will mean the string obtained by replacing each occurrence of x in P by S For example if P is the formula Vx E N x2 2 0 and S is the letter 3 then Px y is the formula V31 6 Ny2 2 0 A formula in our sense is like a declarative sentence in ordinary lan guage Thus 0 lt 1 and The empty set is a subset of X are informal renderings of formulas whereas the command Solve x2 1 and the question Is TTe gt equot are not Formulas like terms are of two types A Closed formula is one that contains no free letters A closed formula may make a de nite assertion about the speci c objects named in it for example The empty set Q is an element of the oneelement set Or a closed formula may make a de nite assertion about all objects for example For every X the empty set is a subset of X An open formula is one that contains at least one free letter For example The empty set is a subset of X An open formula makes an actual statement only when the free letters in it are replaced by terms that are not letters For example replacing X by Q in The empty set is a subset of X yields the formula The empty set is a subset of Q which is no longer open and so is a statement A closed formula is sometimes called a statement or sentence It makes sense to ask whether a statement is true However we shall soon become sloppy about this usage and refer even to open formulas such as x x as statements To emphasize that a formula P is open because the variable 6 oc curring in it is free we sometimes write Px and then call the formula a predicate in 6 For example Ely x E y is a predicate in x but it is not a predicate in 3 because 3 is bound in the whole formula Similarly we can have a predicate Px 3 in two variables such as x E 3 v y E x It does not seem to make sense to ask whether an open formula is true because of the ambiguity of its free variables For example if P x is the predicate x E R x gt 0 then Px is true when the variable x is replaced by the term J but false when x is replaced by 71 L3 Proof and truth L17 L3 Proof and truth Logic is like a seweriwhat you get out of it depends on what you put into it it cannot provide any absolute truth only the truth of state ments relative to the truth of assumptions from which they are de duced So we have to start with certainbasic assumptions and these are called axioms The three simplest axioms customarily used in mathe matics are Axioms L31 Axioms for Equality 1 re exivity Vx x x 2 symmetry VxVy x y ltgt y x 3 transitivity VxVyVz x y ampy 2 gt x z The letters 6 y and z in these axioms are dummy variables so we must agree to accept as axioms all statements that result when we legitimately replace these letters consistently by letters different from x y and 2 For example we take VxVA x A gt A x to be an axiom too A statement C is said to be true when it has a proof By a proof of C is meant a nite list of statements one after or under the other whose last statement is C and in which each statement is an axiom another already proved true statement or a statement Q where P and P gt Q are true statements that appear before Q in the proof The statements in a proof are called the steps of the proof When you are asked to prove a statement you are of course being asked to furnish a proof of it Synonyms for prove are show verify demonstrate establish and deduce The central ingredient of any proof is the pattern P P gt Q Q which may be written with the aid of the symbol therefore in the form PgtQ L18 Appendix L A Little Logic September 17 2007 draft Many steps could intervene between P and P gt Q This pattern is known as Modus Ponens Often one of the words therefore hence or thus is used before the conclusion of a Modus Ponens Here is an example We shall prove that 4 2 2 not that you doubted it We use the de nitions abbreviations 2 3 and 4 for the terms 1 1 2 1 and 3 1 respectively We take to be true the associative law VmeNVneNVk Nmnkmnk for addition of natural numbers Why this associative law is true is another matter entirelyisee Exercise 1211 1 b For brevity abbre viate the associative law by A Then our proof that 4 2 2 is as follows 431thatis42ll A 211211 39211211 VxVyVzxyampyz gt 262 4211amp211211 4211 4211thatis422 The idea behind the second step in the preceding proof is to sub stitute 2 for m 1 for n and 1 for k respectively in the associative law this is an application of Universal Specialization Axiom LS2 stated later The fth step is just transitivity of equalityione of Ax ioms L31 Then the nexttolast step follows from that by substituting 4 for x 2 1 1 for y and 2 1 1 for 2 respectively this is another application of Universal Specialization In practice we neveriwell hardly everiwrite a proof quite that formally And in practice we often include in the proof justi cations for many of its steps An informal version of the same proof would be Proof By the de nitions 4 3 1 that is 4 2 1 1 From the associative law for addition 4 2 1 1 This means 4 2 2 E The symbole marks the end of a proof it is the modernday equiv alent of the traditional QEDian abbreviation for the Latin quad erat demonstrandum meaning which was to be proved In a technical sense every true because proved statement may be called a theorem Then the justproved statement 4 2 2 is a theoremibut hardly an earthshaking one Generally we designate as theorems only the most signi cant true statements You will nd only a handful of theorems in this book A true statement of lesser L4 Combining Statements L19 signi cance may be called a proposition whereas an easily proved consequenceifor example a special caseiof a proposition or theorem is usually called a corollary A true statement whose main interest is only in its use as a step in proving a more signi cant result is called a lemma In view of the de nition of what a proof is we shall accept as a proof of an implication P gt Q the sequence of steps as shown in the following proof rule Proof Rule L32 Direct ProofiAH A list of steps of the following form produces a proofofan implication P gt Q Assume P Steps of a proof in which P is treated as if it were an axiom 39Q In such a proof P is known as the assumed hypothesis So the rule is sometimes referred to as the Method of the Assumed Hypothesisi hence the abbreviation AH A fancier name for the method of direct proof is the HerbrandTarski Deduction Criterion For example here is a proof of the implication that if a positive integer n is divisible by 4 then 11 is even that is n is divisible by 2 Proof Let n be a positive integer Assume n is divisible by 4 This means there is some integer k for which n 4k Then 11 22k and 2k is an integer Thus 11 is even 1 We shall reexamine this proof later because several issues involving quanti ers are involved Exercise L33 Write out or nd in a calculus book a proof of some implication about differentiability of functions whose proof exploits the HerbrandTarski Deduction Criterion L4 Combining Statements In our development of logic the next thing to do is establish a series of axioms governing the meaning of statements formed by combining others through use of the connectives not or and implies and if and only if These axioms will also provide new proof rules as shortcuts for constructing proofs Since most meaningful examples of proofs involve quanti ers we defer stating these proof rules until Section L6 The simplest thing to do with a statement aside from asserting it is to deny it For a statement P its negation is the statement P which is also expressed as not P In mathematical writing P may be L20 Appendix L A Little Logic September 17 2007 draft expressed more verbosely for example as in It is not the case that 2 lt 71 The negation ofP is deemed to be false when P is true and true when P is false We can express this situation by a truth table as follows P P T F F T Down the left column of the truth table we have written the two possible truth values T and F for P These are of course abbreviations for true and false respectively In the right column of the table are the truth values of nP corresponding to each of those two truth values in turn4 Implicitly in the truth table for n we just gave meaning to the word false Here it is explicitly A statement P is false when its negation nP is trueithat is when nP can be proved For example 4 at 2 2 is false because as was proved on page L18 the statement 4 2 2 is true Do not think that a negated statement notP has to be false just because it has the word not in it n0 I that is 0 at I is true because 0 I is false This situation resembles that with negation in algebra an expression of the form 726 need not denote a negative number because for example 7 71 gt 0 For statements P and Q their conjunction P amp Q which is also expressed by P and Q is the statement that is true when both P and Q are true but false otherwise In other words the truth table for amp anal is In the two columns at the left we have systematically written all four of the possible pairs of truth values TT TF FT and FF in the column at the right are the truth values of PampQ corresponding to each of these four combinations of truth values in turn As with all the connectives so amp anal is rendered in various ways in 4Strictly speaking the column headings of a truth table such as P and P above are not actual statements but rather statementforms The table indicates what truth value to ascribe in each case to the statement obtained from the heading of the last column by replacing each of the constituent letters in the statementform by an actual statement Nonetheless we shall often speak as if the statement forms in a truth table were actual statements L4 Combining Statements L21 informal mathematical writing as indicated in Table L1 For example 211 is even but 211 3 is odd Q is empty whereas Q is nonempty xzzOyetxltO For statements P and Q their disjunction P v Q which is also ex pressed by P or Q is the statement that is true when at least one of P Q is trueiin other words when P is true Q is true or P and Q are both trueiand false otherwise Thus or is used in the inclusive sense to allow that both individual statements connected by it be true and yet their disjunction also be true In other words the only case in which P v Q is false is that in which both P and Q are false The truth table for v or is The inclusive sense of or is just what is intended for example in the mathematical statement that x s 3 v y 5 x is true for all real numbers 6 and y when x y then both 6 s y and y s x are separately true In ordinary language this use of or in the inclusive sense can be annoying pity the poor restaurant waiter who upon asking the mathematician diner Would you like soup or saladquot receives the answer Yes Students are sometimes puzzled or even annoyed when they are told that the statement 4 s 2 2 is true they complain How can 4 be less than or equal to 2 2 when in fact 4 is exactly equal to 2 2quot Now according to the de nition of s the statement 4 s 2 2 means 4 lt 2 2 or 4 2 2 Whereas the statement 4 lt 2 2 is false the statement 4 2 2 is true Then the truth table for v gives us no choice the disjunction 4 lt 2 2 or 4 2 2 must be true Exercises L41 For statements P and Q how would you symbolize each of the following 1 Exactly one ofP and Qquot As in for example Ifx E R and x at 0 then exactly one of x lt 0 and x gt 0 holdsquot 2 Neither P nor Qquot As in for example The number 0 is neither positive nor negativequot A statement may also be built up using logical connectives from more than two constituent statements For example PampQ VR involves L22 Appendix L A Little Logic September 17 2007 draft three statements P Q and R Then the truth table for this statement requires 2 2 2 23 8 combinations of truth values To help us obtain the result column of truth values for the entire statementwe ordinarily insert intermediate columns showing the truth values of its components Apply the truth table for v in the special case that Q is the negation P of P The rst and fourth rows of the body of the table are irrelevant here in view of the truth table for n the truth value of Q cannot be chosen independently of the truth value of P Thus we get the truth table According to the table no matter what the truth value of P itself the statement P v P has the truth value T A statement such as this is called a tautology to mean that each of the entries in the last column of its truth table is a T Tautology L42 Law of the Excluded Middle LetP be a statement Then P v P We stipulate that every taatology is an axiom For example according to the Law of the Excluded Middle P v P is an axiom no matter what the statement P might be5 When asked on an exam to prove a certain proposition a student once answered By the Law of the Excluded Middle either the proposi tion is true or it is false If it is true then there is no need for me to prove it if it is false I can hardly be asked to prove itquot The student s response betrays a fundamentaliand all too commonimisunderstanding of the 5Strictly speaking the phrase P v P is only an axiomform because the P there is only a statement form Our stipulation about axioms resulting from tautologies really means the following Every statementthatresults from replacing each constituent letter in a tautology by an actual statement is an axiom For example the instance Tr 2 lt equot v TI 2 2 equot ofP v Pis suchanaxiom so is 2 2 E Q v 2 2 e Qwhere Q is the set of all rational numbers L4 Combining Statements L23 Law of the Excluded Middle All this tautology does is assert the truth of the compound statement P v P no matter what the truth value of P itself it says nothing about the truth or falsity of P itself For example it is true that 29 is rational or 29 is irrational but so far nobody has been able to determine which of the two possibilities holds Moreover it is entirely possible albeit disconcerting that somebody will discover a mathematical statement that cannot be proved and yet whose nega tion also cannot be provediin other words that some mathematical statement is neither true nor false The logical connective most central to the very notion of proof is gt For statements P and Q the implication P Q may be expressed as P implies Q as ifP then Q or in one of the other ways listed in Table L1 The implication P gt Q is taken to be true in every case except when P is true and Q is false In other words the truth table for gt 1s In an implication P gt Q the statement P is called the hypothesis or premise and the statement Q is called the conclusion Most people have no difficulty accepting what the truth table for gt indicates in the two cases where P is true But the two cases where P is false often cause some consternation They should not because these two cases do re ect the way if then is used in everyday language For example If you are good then I will give you some candyquot We understand this as a promise to be honored no matter what If you are not good and I give you no candy I certainly do not break the promise If you are not good and yet I still give you candy I also do not break the promise even though my promise may not have the intended effect the next time I make it6 Notice the asymmetry between P and Q in P gt Q For particular statements P and Q the implication P gt Q may be true whereas its converse Q gt P may be false For example take P to be the statement I 0 and Q to be the statement 0 0 Then the implication I 0 gt 0 0 is true because its hypothesis 1 0 is false However the converse implication 0 0 gt I 0 is false because its hypothesis 0 0 is true whereas its conclusion I 0 is false 6Calling an implication true when its hypothesis and conclusion are both false is problematic however when the hypothesis and conclusion are about realworld events For example If Great Britain had won the War for Independence then the United States would be a British colony today What do we realy mean when we utter such a counterfactual conditional L24 Appendix L A Little Logic September 17 2007 draft Exercise L43 What is the relationship between the truth of an impli cation P gt Q and that of its contrapositive Q gt P 7 Numerous tautologies and resulting axioms can now be derived One such tautology is PampQgtP Its truth table is Notice that the fourth column headed P repeats the rst The fourth column is not really needed but it was inserted to the right of the column headed P amp Q to facilitate using the truth table for gt in order to ll in the nal column Here are a couple more tautologies involving implication P gt PVQ PgtQ gt RVPgtRVQ For statements P and Q the logical equivalence P a Q may be expressed as P is equivalent to Q as P if and only if Q or in one of the other ways listed in Table L1 The equivalence P gt Q is taken to be true exactly when P and Q have the same truth value that is when they are both true or else both false In other words the truth table for ltgt 1s An equivalence P a Q is true precisely when the implication P gt Q and its converse Q gt P are both true In other words the following is a tautology Tautology L44 letP and Q be statements Then P ltgt Q ltgt P ltgt Q ampQltgtP To verify this tautology compare the truth table for P a Q with that for P gt Q amp Q P L4 Combining Statements L25 A common way to prove a statement of the form P S Q is to prove separately the implications P S Q and Q S P Can you justify that way Many of the most useful tautologies are logical equivalences Here are some Tautologies L45 Let P Q andR be statements Then 1 double negation P S P idempotent law P VP S P idempotent law P ampP S P commutative law P v Q S Q v P commutative law P ampQ S Q ampP associative law P v Q v R S P v Q v R associative law P ampQ ampR S P amp Q ampR distributive law P v Q ampR S P v Q amp P v R 9 distributive law P amp Q v R S P ampQ v P ampR Exercise L46 Use truth tables to establish parts 1 2 4 6 and 8 of the preceding list of tautologies 9 NPgtPWHgtP7N The following three tautologies express fundamental properties of logical equivalence They are easy enough to establish by constructing truth tables They may also be deduced from Tautology L44 and some of the other previously listed tautologies Tautologies L47 Let P Q andR be statements Then 1 P S P 2 PltgtQ S QSP 3 UP gt QampQ gtRgt S P gtRgt That an implication P S Q is false only in the case that P is true but Q is false and the implication is true in every other case is also expressed by the following tautology Tautology L48 LetP and Q be statements Then PSQ ltgt uPVQ Exercise L49 Use connectives to symbolize P unless Q for state ments P and Q L26 Appendix L A Little Logic September 17 2007 draft Often in constructing proofs you will want to form the negation of a compound or or analstatement For this the following pair of tautologies are relevant Tautologies L410 De Morgan s Laws Let P anal Q be statements Then 1 aPvQ ltgt 3Pamp3Q 2 3P ampQ lt2 3PV3Q Here is an instance of the rst of De Morgan s Laws To deny that an integer n is a multiple of 2 or a multiple of 3 is to af rm that it is not the case that n is a multiple of 2 and a multiple of 3 in other words that n is neither a multiple of 2 nor a multiple of 3 You should be able to write a similar instance of the second of De Morgan s Laws Exercise L411 Use De Morgan s Laws to deduce Tautologies L4S parts 3 S 7 and 9 from parts 2 4 6 and 8 respectively For ex ample use the idempotent law P VP a P together with De Morgan s Laws to deduce the idempotent law P ampP a P It is easy to check that the following are tautologies pPampP ltgtP39 nP39 ltP VQampP ltgtP ampQ gt Q P VQ PampQ amp P gt P39 amp Q gt Q P39ampQ P QampP ltgtP39ampQ ltgt Q39 P39 ltgt Q39 Together these tautologies justify the following rule LetS be a state ment built up in some way from simpler statements P1 P2 Pn by us ing the logical connectives lfone or more of the constituent statements Pi are replaced by equivalentstatements Pi39 then the resulting statement 8 has the same truth value as the original statement S We have not attempted to list here all the tautologies commonly used in constructing proofs Consequently when you see a proof whose pattern is unfamiliar you should suspect that it is justi ed by an ax iom resulting directly from some asyetunstated tautologyiand you should attempt to write that tautology and verify it by using other tautologies or directly by constructing the truth table LS Quanti ers The logical quanti ers V for all for every El there exists for some and 1 the were already introduced Here we examine them further and in particular state some axioms and tautologies involving them LS Quanti ers L27 The quanti ers have no real effect unless the formula to which they are applied involve a free variable That is why to emphasize the fact that a letter 6 is a free variable in the formula P we also denote the formula by P x and then call it a predicate in 6 Recall that in partic ular x is free in P when 6 does not occur in P but still we might write Px The letter 6 used in a universally or existentially quanti ed state ment about a predicate P x is a dummy variable that can be replaced by another letter as stated precisely in the following axiom Axiom L51 Letx he a free variable in the formula P anal lety he a letter that does not occur in P Then 1 VxPx ltgt VyPXa3 2 3XPX ltgt 3yPxay As already suggested in Table L1 the statement VxPx involv ing the universal quanti er V may be read or expressed variously as for every x Px for all x Px for each x Px for arbitrary x Px Sometimes VxPx is even expressed as for any x P x quot However it is best to avoid using any this way since in some contexts any can mean some Compare Can you draw any conclusion from thatquot Often a statement of the form VxPx is expressed with addi tional words such as for every x it is the case that Px for each x the property Px holds The word any is sometimes used to suggest auniversally quanti ed statement For example Any even integer has a square that is evenquot Any integer that is even has an even squarequot The square of any even integer is evenquot Sometimes the every all each or any is deleted as in An even integer has an even squarequot and The square of an even integer is evenquot The universal quanti er was used for example in formulating the Axioms for Equality Axioms L31 which were Vxx x VxVy x 31 3 x VxVyVz x yampy z gt x z L28 Appendix L A Little Logic September 17 2007 draft The intended meaning of the universal quanti er V in VxPx is that VxPx be true precisely when Px is true no matter What particular term is substituted for x in Px We formulate this mean ing in an axiom The formulation uses the notation Px a X which you should recall means that every occurrence of the letter 6 in P is replaced by the string X Axiom L52 Universal Specialization Letx he a free variable in the formula P anal letX he a term Then VxPx gt Fix Xl Informally speaking Universal Specialization expresses that when some property holds about every object in the mathematical world it must also hold for any particular object For example according to US Vxxx gt Q Q is an axiom Since Vx x x is an axiom then Q Q is therefore true More generally in view of AH the HerbrandTarski Deduction Crite rion Proof Rule L32 the preceding axiom provides a corresponding proof rule Proof Rule L53 Universal SpecializationiUS Letx he a free vari able in the formula P anal letX he a term If VxPx is true then Px a X is true The order of consecutive universal quanti ers in a statement is im material Axiom L54 Letx analy be free in the formula Pxy Then Vx VyPxy ltgt Vy VxPXy Exercise L55 a Does the order of consecutive existential quanti ers in a statement matter That is is Elx ElyPx y logically equivalent to Ely ElxPx 3 Why or Why not b Is Elx ElyPx y logically equivalent to Ely ElxPy 6 Why or Why not Notice that here the order of the letters in Px 3 is also reversed Axioms L56 Letx be free in the formulasPx anal Qx Then 1 VxPxampQx ltgt VxPx ampVxQx LS Quanti ers L29 2 Vx Px Qx ltgt VXPX i39 VXQX As always so in the preceding pair of axioms the letter 6 need not actually occur in either P or Q If 6 does not occur say in P but does occur as a free variable in Q we could rewrite the rst of the pair as VxPampQx ltgt VxPampVxQx Similarly for the second axiom Often you will see the axioms for equality written in the simpler forms xx xy gtyx xyampyz gtxz where the universal quanti ers are omitted but implicit To justify such omissions we rely upon the following proof rule Proof Rule L57 Universal GeneralizationiUG Suppose the letterx is free in the formula Px IfPx is true then Vx Px is true In view of this proof rule we sometimes refer to an formula as if it too were a statement Notice that we did not rst give as an axiom P x gt VxPxquot and then suggest that the proof rule U6 is a consequence Indeed there are two essential restrictions upon the use of U6 The letter 6 is not free in any preceding step in the proof that results by using Existential Specialization ES and If in a preceding step of the proof AH Proof Rule L32 was used to deduce a statement C by assuming a hypothesis H then AH has already been invoked to prove H gt C and H is no longer being assumed In particular Universal Generalization may not be used in a proof of the following form Assume P x VxPx by UG Px gt VxPx by the Deduction Criterion And thus Universal Generalization may not be invoked so as to prove the formula Px gt VxPx Wrong L30 Appendix L A Little Logic September 17 2007 draft That formula is wrong because the letter 6 is unbound in Px but bound in VxPx In fact suppose it were legitimate to deduce that implication Since 6 is a dummy variable in VxPx then x in this universally quanti ed statement could be replaced by a different letter 3 so as to deduce Px gt VyPy Wrong Why that restriction Just suppose that to the contrary it were legitimate to deduce the preceding implication As an example take Px tobe the predicatex E N gt x gt 0 Then 6 E N gt x gt 0 gt Vx x E N gt x gt 0 would be true Replace x by y in the quanti ed part of this formula to obtain 6 E N gt x gt 0 gt Vyy E N gt y gt 0 which would then also be true Now the hypothesis 1 E N gt1 gt 0 is true Hence the conclusion Vyy E N gt y gt 0 would also be true But clearly it is false Here is an example of how proof rule U6 is employed Suppose you want to prove that VxVyVzx yamp2y gt x 2 Note that in this statement the amp has a higher precedence than gt so that the statement means VXVyVZ X yampZ 31 ltgt X 2 Then you could write a proof of the statement without any quanti ers whatsoever by using the axioms for equality and invoking US implicitly as follows Proof 231 gt xyampzy gtxyampyz xyampyz gt xyampzy gtxz D In practice we do not usually write the proof in such excruciating detail Rather we shorten it and express it more informally as follows Proof Assume x y and z 3 By symmetry of equality y z By transitivity of equality then x z 1 In the proof on page L19 that if a positive integer n is divisible by 4 then 11 is even several steps appear only implicitly Here is a more complete version of the proof in which those steps have been made explicit LS Quanti ers L31 Let n be a positive integer Assume n is divisible by 4 This means there is some integer k for which n 4k Let k be such an integer Then 11 22k Let t 2k Then I is an integer such that n 2t This means that there is some integer t such that n 2t Thus 11 is even Recall that the step Assume n is divisible by 4 indicates a use of the HerbrandTarski Deduction Criterion Proof Rule L32 Aside from that proof rule three issues about quanti ers are also involved in the preceding proof 1 What is being proved is really a universally quanti ed statement For every positive integer n if n is divisible by 4 then 11 is even To prove this universally quanti ed statement we removed the For every part For every positive integer nquot involving the uni versal quanti er and instead wrote Let n be a positive integerquot7 meaning Let n be an arbitrary but speci c positive integerquot Then using several steps we proved If n is divisible by 4 then 11 is divisible by 2quot That this procedure actually proves the univer sally quanti ed statement is justi ed by Universal Generalization Proof Rule LS7 2 Recall that the assumption that n is divisible by 4 meant that there exists some integer k such that n 4 k So the more complete version of the proof said next Let k be such an integerquot in other words Let k be a particular integer such that n 4k That is justi ed by the principle of Existential SpecializationiES for short 3 After letting t 2k where k was that particular integer obtained from ES we deduced that n2t for that particular I which depended upon the particular k And from that in turn we deduced There is some integer t such that n 2t Putting the existential quanti er back there is justi ed by the prin ciple of Existential GeneralizationiEG for short L32 Appendix L A Little Logic September 17 2007 draft Here are the precise formulations of ES and EC Proof Rule L58 Existential SpecializationiES Letx he a letter that is free in P and does not occur in C Suppose that hath 3xPx anal Px gt C are true Then C is true Proof Rule L59 Existential GeneralizationiEG Supposex is free in P analS is a term IfPx a S is true then ElxPx is true Existential Generalization says in effect that one way to prove ex istence of an object 6 with a certain property Px is to construct or exhibit a particular object S having that property For example to prove there exists some nonempty setithat is EIA A at Qiyou could construct the set Q and note that Q is not emptyithat is Q at Qibecause Q E Q Or to prove there exists some negative integer whose square is 4 you could exhibit the integer 72 and note that 722 2 Recall that Elx E XPx is an abbreviation for Elx x E XampPx Then Existential Generalization has as a particular case the situation where the formula Px takes the form x E X amp Qx for a predicate Q06 Proof Rule L510 Existential Generalizationirelative formiEG Supposex is free in P and s and X are terms Ifs E X analPx a s are both true then ElxPx is true Recall that Vx E X P is an abbreviation for Vxx E X gt P For now we shall also take as axiomatic the following variant of Universal Specialization Axiom L 5 1 1 Universal Specializationirelative form Letx he a free variable in the formula P and eta analX he terms Then Vx EXPx A zaEX gt Px aa The preceding axiom means that when some property holds for ev ery element of a set X and when a is one of the elements of X then the property must hold in particular for a Surely you have no qualms about accepting that Actually it can be deduced from US As an example of this relative form of US look again at the proof that 4 2 2 see page L18 Again abbreviate by A the associative law Vme NVn NVke Nmnkm nk LS Quanti ers L33 Then our proof that 4 2 2 is as follows 431 thatis42ll A A gt 211211 39211211 VxVyVzxyampyz gt 262 4211amp211211 4211 394211thatis422 The third step and sixth steps are applications of the relative form of US The relative form of Universal Specialization Axiom LS11 justi es the following proof method Proof Rule L512 LetX is a set and letPx he a predicate in 6 Then following is a proofofVx E XPx Letx E X Proof of Px where x E X is assumed to be an axiom Intuitively to deny that a certain property holds for all x is to as sert that it fails to hold for some 6 We express this formally in an axiom which relates universal and existential quanti cation by means of negation Axiom L513 LetPx he a predicate in 6 Then 3VxPx ltgt 3x Px By applying negation to both sides of the equivalence in Axiom L S 1 3 and replacing P x in it by Px we obtain at once the rst part of the following theorem the second part follows from the rst by replacing negating both sides of the rst part Theorem L514 LetPx he a predicate in 6 Then 1 3ElxPx a Vx Px 2 ElxPx a 3Vx Px The second part of the preceding theorem implies something sig ni cant about mathematical proof as it is commonly understood To prove existence of some 6 for which Px holds it suf ces to prove it false that the negation ofPx holds for every x L34 Appendix L A Little Logic September 17 2007 draft Thus one can prove existence of an object with a certain property without actually constructing or exhibiting a particular object with that property7 L6 More proof rules 7A small minority of mathematicians the constructivists object to establishing existence of an obj ect having a givenproperty Without actually constructing a particular object having that property In other words they reject Axiom LS1 3
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'