Logic, Sets, and Proofs - Amherst College

1 Logic, Sets, and ProofsDavid A. Cox and Catherine C. McGeochAmherst College1 LogicLogical statementis a mathematical statement that is eithertrue or false. Here we denote logical statements with capital lettersA, B. Logicalstatements be combined to form new logical statements as follows:NameNotationConjunctionAandBDisj unctionAorBNegationnotA AImplicationAimpliesBifA, thenBA BEquivalenceAif and only ifBA BHere are some examples of conjunction, disjunction and negation:x >1 andx <3: This is true whenxis in the open interval (1,3).x >1 orx <3: This is true for all real numbersx. (x >1): This is the same asx are two logical statements that are true:x >4 x > 1 (x= 1 orx= 1).Note that x= 1 orx= 1 is usually writtenx= , Contrapositives, and begin with converses andcontrapositives: Theconverseof AimpliesB is BimpliesA . Thecontrapositiveof AimpliesB is Bimplies A Thus the statement x >4 x >2 has: Converse:x >2 x >4.

2 Contrapositive:x 2 x logical statements are guaranteed to always be true. These are two tautologies that involve converses and contrapositives: (Aif and only ifB) ((AimpliesB) and (BimpliesA)). In other words,AandBare equivalent exactly when bothA Band its converse are true. (AimpliesB) ( Bimplies A). In other words, an implication is alwaysequivalent to its contrapositive. This is important to are many other tautologies. Some are pretty obvious, such as(AorB) (BorA)(similarly for and ), while others take a bit of thought, such as the following:StatementEquivalent statementDescriptionAor (BandC)(AorB) and (AorC) or distributes over and Aand (BorC)(AandB) or (AandC) and distributes over or (AorB) Aand BDe Morgan s law for or (AandB) Aor BDe Morgan s law for and A (B C)(AandB) Cconditional proofIn a course that discusses mathematical logic, one usestruth tablesto prove the SetsAsetis a collection of objects, which are calledelementsormembersof the set.

3 Twosets areequalwhen they have the same are some important sets: The set of allintegersisZ={.. , 3, 2, 1,0,1,2,3, ..}. The set of allreal numbersisR. The set of allcomplex numbersisC. The set with no elements is , theempty important set is the set ofnatural numbers, denotedN. In our book,N={1,2,3, ..},However, you should be aware that in some other books,N={0,1,2,3, ..}.2 Basic Definitions and Notation about Sets. x S:xis an element or member :2 Z. x / S:xis not an element ofS, , (x S).Example:12/ Z. S T: Every element ofSis also an element ofT. We say thatSis asubsetofTand :Z R CandZ Z. S6 T: This means (S T), , some element ofSis not an element :R6 Z. S T: This meansS TandS6=T. We say thatSis aproper subsetofTand thatTproperly containsorproperly :Z thatS=Tis equivalent toS TandT are two basic ways to describe a set. Listing elements: Some sets can be described by listing their elements insidebrackets{and}.

4 Example:The set of positive squares is{1,4,9,16, ..}. Whenlisting the elements of a set, order is unimportant, as are repetitions. Thus{1,2,3}={3,2,1}={1,1,2,3},since all three contain the same elements, namely 1, 2 and 3. Set-builder notation: We can sometimes describe a set by the conditions itselements :The set of positive real numbers is{x R|x >0}.This can also be written{x|x Randx >0}. We read | as such that .Operations on sets. TheunionS Tis the setS T={x|x Sorx T}.Thus an element lies inS Tprecisely when it lies inat least oneof the :{1,2,3,4} {3,4,5,6}={1,2,3,4,5,6}{n Z|n 0} {n Z|n <0}= TheintersectionS Tis the setS T={x|x Sandx T}.Thus an element lies inS Tprecisely when it lies inbothof the :{1,2,3,4} {3,4,5,6}={3,4}{n Z|n 0} {n Z|n <0}= . Theset differenceS Tis the set of elements that are inSbut not :{1,2,3,4} {3,4,5,6}={1,2}.A common alternative notation forS TisS\ Variables and QuantifiersOften we are working with elements of a fixed set.

5 In calculus, this fixed set is oftenthe real numbersRor an interval [a, b] R. In linear algebra, the fixed set is oftenRn,Cnor an abstract vector spaceV(all of these terms will eventually be defined).In the discussion that follows, this fixed set will be asxrepresents some unspecified element from the fixed :IfZis the fixed set, then xis even is a statement that involves the variablex, and x > y a logical statement contains one or more variables, then the truth of thestatement depends on which particular members of the fixed set are plugged in forthe combinequantifierswith statements involving variables to form statementsabout members of the fixed setU. IfP(x) is a statement depending on the variablexfrom the fixed setU, then there are two basic types of quantifiers: x U(P(x)). Thisuniversal quantifiermeans that for all (orfor everyorfor eachorfor any) value ofxinU,P(x) is : x R(2x=(x+ 1) + (x 1)).

6 X U(P(x)). Thisexistential quantifiermeans that there exists a (orthereis at least one) value ofxinUfor whichP(x) is : x Z(x >5).If the fixed setUis understood, it may be omitted from the quantifier. Forexample, assuming that the fixed set isZ, then the above statement can be writtenmore simply as x(x >5).A general strategy for proving things about statements with quantifiers is toworkone element at a time. Even when we are dealing with universal quantifiers andinfinite fixed sets, we proceed by thinking about the properties that a particular butarbitrary element of the fixed set would with Variables and statement depending on a variable,such asP(x), is often used to describe a set in terms of the set-builder notationS={x U|P(x)}.This means that the setSconsists of all elementsxof the fixed set for which thestatementP(x) is :The definitionS={n Z|n >5}meansn Sifand only ifnis an integer greater than 5.

7 If the fixed set is assumed to beZ, it canbe left out of the definition, so thatS={n|n >5}.We can recast set inclusions using quantifiers. ThusS Tis equivalent to x(x S x T)is equivalent to x S(x T)As a general rule, we prove things about sets by working with the statementsthat define them. We will see later that the equivalences forS Tlead to a usefulproof strategy. As with the case of quantifiers and statements, provingS Tmeansworking with one element at a of is important to understand how negation interactswith quantifiers. Here are the basic rules. x P(x) is equivalent to x( P(x)). x P(x) is equivalent to x( P(x)).Example:For the fixed set isR, we can understand x(x >0) as follows: x(x >0) is equivalent to x( (x >0))is equivalent to x(x 0).The last statement is clearly true (takex= 1, for example), hence our originalstatement is proof StrategiesAproofstarts with a list ofhypothesesand ends with aconclusion.

8 The proof showsthe step-by-step chain of reasoning from hypotheses to conclusion. Every step needsto be justified. You can use any of the reasons below to justify a step in your proof : A hypothesis. A definition. Something already proved earlier in the proof . A result proved previously. A consequence of earlier steps according to the rules of sure to proceed one step at a time. Writing a good proof requires knowing defi-nitions and previously proved results, understanding how the notation and the logicworks, and having a bit of insight. It also helps to be familiar with some commonstrategies for different types of simplest way to proveA Bis to assumeA(the hypothe-sis ) and proveB(the conclusion ). See proof 2 in Section 5 for a direct proof ofnis even n2is by way to proveA Bis to assume thatAis true andBis false. In other words, you assume that the hypothesis is true but the conclusionis false.

9 Then you try to derive a contradiction. See proof 2 is Section 5 for a proofby contradiction ofn2is even nis by closely related strategy to proveA Bis to insteadprove its contrapositive B A. Hence the stategy is to assume thatBis falseand prove that this implies thatAis also Strategies for is a list of strategies for proving the truthof quantified statements. x U(P(x)). Give an example value of the variablexthat makesP(x) :To prove x(x >12), you can simply indicate that settingx= 14makesx >12 true. x U(P(x)). Assume (as a hypothesis) thatxhas the properties of the fixedset, but don t assume anything more about it. Show as a conclusion that thestatement must be true for that (arbitrary) value ofx. If you have a statement of the form x(P(x) orQ(x)) or x(P(x) orQ(x)),then you can rewrite the statementP(x) orQ(x) using any logical same is true if or is replaced by and , implies or if and only if.

10 Example:By the contrapositive tautology, proving x(x 1 x2 1) isequivalent to proving x(x2<1 x <1). proof Strategies for Sets. (Membership) Strategy to provex S: Show thatxhas the properties thatdefine membership inS. (Inclusion) Strategy to proveSis a subset ofT, ,S T: Take an arbitaryelementxofS. That is,xrepresents any specific member ofS; you can assumexhas the properties that defineS, but you can t assume anything more about6it. Then show thatxmust also be an element ofTusing the membershipstrategy described above. Remember that you can assume thatxsatisfies thedefining properties ofS. (Equality) Strategy to proveSequalsT, ,S=T: First prove thatS prove thatT Sample ProofsHere we give two simple Proofs to illustrate various proof , B, Cbe sets. Prove the distribution law for over , which statesA (B C) = (A B) (A C). proof has two parts because we want to prove two sets are proveA (B C) (A B) (A C), takex A (B C).