[PDF] Logic, Sets, and Proofs - Amherst College

41264_1logicsetsproof.pdf

Logic, Sets, and Proofs

David A. Cox and Catherine C. McGeoch

Amherst College

1 Logic

Logical Statements.Alogical statementis a mathematical statement that is either true or false. Here we denote logical statements with capital lettersA;B. Logical statements be combined to form new logical statements as follows:

NameNotation

ConjunctionAandBDisjunctionAorBNegationnotA:AImplicationAimpliesBifA, thenBA)BEquivalenceAif and only ifBA,B

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

Here are two logical statements that are true:

x >4)x >2. x

2= 1,(x= 1 orx=1).

Note that \x= 1 orx=1" is usually writtenx=1.

Converses, Contrapositives, and Tautologies.We begin with converses and contrapositives: Theconverseof \AimpliesB" is \BimpliesA". Thecontrapositiveof \AimpliesB" is \:Bimplies:A"

Thus the statement \x >4)x >2" has:

Converse:x >2)x >4. Contrapositive:x2)x4. 1 Some logical statements are guaranteed to always be true. These aretautologies. Here are two tautologies that involve converses and contrapositives: (Aif and only ifB),((AimpliesB) and (BimpliesA)). In other words,A andBare equivalent exactly when bothA)Band its converse are true. (AimpliesB),(:Bimplies:A). In other words, an implication is always equivalent to its contrapositive. This is important to know. There 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 statementDescription

Aor (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 proof

In a course that discusses mathematical logic, one usestruth tablesto prove the above tautologies.

2 Sets

Asetis a collection of objects, which are calledelementsormembersof the set. Two sets areequalwhen they have the same elements.

Common Sets.Here are some important sets:

The set of allintegersisZ=f:::;3;2;1;0;1;2;3;:::g. The set of allreal numbersisR. The set of allcomplex numbersisC. The set with no elements is;, theempty set. Another important set is the set ofnatural numbers, denotedN. In our book,

N=f1;2;3;:::g;

However, you should be aware that in some other books,N=f0;1;2;3;:::g. 2

Basic Denitions and Notation about Sets.

x2S:xis an element or member ofS.Example:22Z. x =2S:xis not an element ofS, i.e.,:(x2S).Example:12 =2Z. ST: Every element ofSis also an element ofT. We say thatSis asubset ofTand thatTcontainsorincludesS.Examples:ZRCandZZ. S6T: This means:(ST), i.e., some element ofSis not an element ofT.

Example:R6Z.

ST: This meansSTandS6=T. We say thatSis aproper subsetofT and thatTproperly containsorproperly includesS.Example:ZR.

Note thatS=Tis equivalent toSTandTS.

Describing Sets.There are two basic ways to describe a set. Listing elements: Some sets can be described by listing their elements inside bracketsfandg.Example:The set of positive squares isf1;4;9;16;:::g. When listing the elements of a set, order is unimportant, as are repetitions. Thus f1;2;3g=f3;2;1g=f1;1;2;3g; since all three contain the same elements, namely 1, 2 and 3. Set-builder notation: We can sometimes describe a set by the conditions its elements satisfy.Example:The set of positive real numbers is fx2Rjx >0g: This can also be writtenfxjx2Randx >0g. We read \j" as \such that".

Operations on Sets.LetSandTbe sets.

TheunionS[Tis the set

S[T=fxjx2Sorx2Tg:

Thus an element lies inS[Tprecisely when it lies inat least oneof the sets.

Examples:

f1;2;3;4g [ f3;4;5;6g=f1;2;3;4;5;6g fn2Zjn0g [ fn2Zjn <0g=Z: 3 TheintersectionS\Tis the set

S\T=fxjx2Sandx2Tg:

Thus an element lies inS\Tprecisely when it lies inbothof the sets.Examples: f1;2;3;4g \ f3;4;5;6g=f3;4g fn2Zjn0g \ fn2Zjn <0g=;: Theset dierenceSTis the set of elements that are inSbut not inT.

Example:

f1;2;3;4g f3;4;5;6g=f1;2g:

A common alternative notation forSTisSnT.

3 Variables and Quantiers

Often we are working with elements of a xed set. In calculus, this xed set is often the real numbersRor an interval [a;b]R. In linear algebra, the xed set is often R n,Cnor an abstract vector spaceV(all of these terms will eventually be dened). In the discussion that follows, this xed set will be denotedU. Avariablesuch asxrepresents some unspecied element from the xed setU. Example:IfZis the xed set, then \xis even" is a statement that involves the variable x, and \x > y" involvesxandy. When a logical statement contains one or more variables, then the truth of the statement depends on which particular members of the xed set are plugged in for the variables. We combinequantierswith statements involving variables to form statements about members of the xed setU. IfP(x) is a statement depending on the variable xfrom the xed setU, then there are two basic types of quantiers:  8x2U(P(x)). Thisuniversal quantiermeans that for all (orfor everyor for eachorfor any) value ofxinU,P(x) is true.Example:8x2R(2x= (x+ 1) + (x1)).  9x2U(P(x)). Thisexistential quantiermeans that there exists a (orthere is at least one) value ofxinUfor whichP(x) is true.Example:9x2Z(x >5). If the xed setUis understood, it may be omitted from the quantier. For example, assuming that the xed set isZ, then the above statement can be written more simply as9x(x >5). A general strategy for proving things about statements with quantiers is towork one element at a time. Even when we are dealing with universal quantiers and innite xed sets, we proceed by thinking about the properties that a particular but arbitrary element of the xed set would have. 4 Statements with Variables and Sets.A statement depending on a variable, such asP(x), is often used to describe a set in terms of the set-builder notation

S=fx2UjP(x)g:

This means that the setSconsists of all elementsxof the xed set for which the statementP(x) is true.Example:The denitionS=fn2Zjn >5gmeansn2Sif and only ifnis an integer greater than 5. If the xed set is assumed to beZ, it can be left out of the denition, so thatS=fnjn >5g. We can recast set inclusions using quantiers. Thus

STis equivalent to8x(x2S)x2T)

is equivalent to8x2S(x2T) As a general rule, we prove things about sets by working with the statements that dene them. We will see later that the equivalences forSTlead to a useful proof strategy. As with the case of quantiers and statements, provingSTmeans working with one element at a time. Negations of Quantiers.It is important to understand how negation interacts with quantiers. Here are the basic rules.  :8xP(x) is equivalent to9x(:P(x)).  :9xP(x) is equivalent to8x(:P(x)). Example:For the xed set isR, we can understand:8x(x >0) as follows: :8x(x >0) is equivalent to9x(:(x >0)) is equivalent to9x(x0). The last statement is clearly true (takex=1, for example), hence our original statement is true.

4 Proof Strategies

Aproofstarts with a list ofhypothesesand ends with aconclusion. The proof shows the step-by-step chain of reasoning from hypotheses to conclusion. Every step needs to be justied. You can use any of the reasons below to justify a step in your proof: A hypothesis. A denition. Something already proved earlier in the proof. A result proved previously. A consequence of earlier steps according to the rules of logic. 5 Be sure to proceed one step at a time. Writing a good proof requires knowing de- nitions and previously proved results, understanding how the notation and the logic works, and having a bit of insight. It also helps to be familiar with some common strategies for dierent types of proofs. Direct Proof.The simplest way to proveA)Bis to assumeA(the \hypothe- sis") and proveB(the \conclusion"). See Proof 2 in Section 5 for a direct proof of nis even)n2is even. Proof by Contradiction.One way to proveA)Bis to assume thatAis true and Bis false. In other words, you assume that the hypothesis is true but the conclusion is false. Then you try to derive a contradiction. See Proof 2 is Section 5 for a proof by contradiction ofn2is even)nis even. Proof by Contrapositive.A closely related strategy to proveA)Bis to instead prove its contrapositive:B) :A. Hence the stategy is to assume thatBis false and prove that this implies thatAis also false. Proof Strategies for Quantiers.Here is a list of strategies for proving the truth of quantied statements.  9x2U(P(x)). Give an example value of the variablexthat makesP(x) true. Example:To prove9x(x >12), you can simply indicate that settingx= 14 makesx >12 true.  8x2U(P(x)). Assume (as a hypothesis) thatxhas the properties of the xed set, but don't assume anything more about it. Show as a conclusion that the statement must be true for that (arbitrary) value ofx. If you have a statement of the form8x(P(x) orQ(x)) or9x(P(x) orQ(x)), then you can rewrite the statementP(x) orQ(x) using any logical tautology. The same is true if \or" is replaced by \and", \implies" or "if and only if". Example:By the contrapositive tautology, proving8x(x1)x21) is equivalent to proving8x(x2<1)x <1).

Proof Strategies for Sets.

(Membership) Strategy to provex2S: Show thatxhas the properties that dene membership inS. (Inclusion) Strategy to proveSis a subset ofT, i.e.,ST: Take an arbitary elementxofS. That is,xrepresents any specic member ofS; you can assume xhas the properties that deneS, but you can't assume anything more about 6 it. Then show thatxmust also be an element ofTusing the membership strategy described above. Remember that you can assume thatxsatises the dening properties ofS. (Equality) Strategy to proveSequalsT, i.e.,S=T: First prove thatST.

Then prove thatTS.

5 Sample Proofs

Here we give two simple proofs to illustrate various proof strategies. Proof 1.LetA;B;Cbe sets. Prove the distribution law for[over\, which states

A[(B\C) = (A[B)\(A[C).

Proof.The proof has two parts because we want to prove two sets are equal. To proveA[(B\C)(A[B)\(A[C), takex2A[(B\C). Then we have a series of implications: x2A[(B\C) impliesx2Aorx2B\CDef[ impliesx2Aor (x2Bandx2C) Def\ implies (x2Aorx2B) and (x2Aorx2C) Dist impliesx2A[Bandx2A[CDef[ impliesx2(A[B)\(A[C) Def\.

This shows thatA[(B\C)(A[B)\(A[C).

For the opposite inclusion (A[B)\(A[C)A[(B\C), takex2(A[B)\(A[C). The implications in the rst part of the proof are reversible, so thatx2A[(B\C). This proves (A[B)\(A[C)A[(B\C), and equality follows. QED

Proof 2.Prove that8n2Z(nis even,n2is even).

Proof.Fix an arbitraryn2Z. Then we need to prove thatnis even,n2is even. The proof has two parts because we want to prove an equivalence. Proof thatnis even)n2is even: Taken2Zand assumenis even. By the denition of even, this meansn= 2mfor somem2Z. Then n

2= (2m)2= (2m)(2m) = 2(2m2);

which shows thatn2is even. Proof thatn2is even)nis even: Now taken2Zand assumen2is even. We prove thatnis even by contradiction. So assumenis not even, i.e.,nis odd. This meansn= 2m+ 1 for somem2Z. Then n

2= (2m+ 1)2= (2m+ 1)(2m+ 1) = 4m2+ 4m+ 1 = 2(2m2+ 2m) + 1;

which shows thatn2is odd. This contradicts our assumption thatn2is even, and it follows thatnmust be even. QED 7