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.

2 (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. 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)).

3 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.

4 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.

5 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}.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.

6 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}=.

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

8 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)). 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).

9 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.

10 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.