1
Methods of Proof and Some Notation

1.1 Methods of Proof

Consider two statements, "A" and "B," which could be either true or false. For example, let "A" be the statement "John is an engineering student," and let "B" be the statement "John is taking a course on optimization." We can combine these statements to form other statements, such as "A and B" or "A or B." In our example, "A and B" means "John is an engineering student, and he is taking a course on optimization." We can also form statements such as "not A," "not B," "not (A and B)," and so on. For example, "not A" means "John is not an engineering student." The truth or falsity of the combined statements depends on the truth or falsity of the original statements, "A" and "B." This relationship is expressed by means of truth tables; see Tables 1.1 and 1.2.

From the tables, it is easy to see that the statement "not (A and B)" is equivalent to "(not A) or (not B)" (see Exercise 1.3). This is called De Morgan's law.

In proving statements, it is convenient to express a combined statement by a conditional, such as "A implies B," which we denote "AB." The conditional "AB" is simply the combined statement "(not A) or B" and is often also read as "A only if B," or "if A then B," or "A is sufficient for B," or "B is necessary for A."

We can combine two conditional statements to form a biconditional statement of the form "AB," which simply means "(AB) and (BA)." The statement "AB" reads "A if and only if B," "A is equivalent to B," or "A is necessary and sufficient for B." Truth tables for conditional and biconditional statements are given in Table 1.3.

It is easy to verify, using the truth table, that the statement "AB" is equivalent to the statement "(not B)(not A)." The latter is called the contrapositive of the former. If we take the contrapositive to De Morgan's law, we obtain the assertion that "not (A or B)" is equivalent to "(not A) and (not B)."

Most statements we deal with have the form "AB." To prove such a statement, we may use one of the following three different techniques:

1. The direct method
2. Proof by contraposition
3. Proof by contradiction or reductio ad absurdum

In the case of the direct method, we start with "A," then deduce a chain of various consequences to end with "B."

A useful method for proving statements is proof by contraposition, based on the equivalence of the statements "AB" and "(not B)(not A)." We start with "not B," then deduce various consequences to end with "not A" as a conclusion.

Table 1.1 Truth table for "A and B" and "A or B".

Table 1.2 Truth table for "not A".

Table 1.3 Truth table for conditionals and biconditionals.

Another method of proof that we use is proof by contradiction, based on the equivalence of the statements "AB" and "not (A and (not B))." Here we begin with "A and (not B)" and derive a contradiction.

Occasionally, we use the principle of induction to prove statements. This principle may be stated as follows. Assume that a given property of positive integers satisfies the following conditions:

• The number 1 possesses this property.
• If the number possesses this property, then the number possesses it too.

The principle of induction states that under these assumptions, any positive integer possesses the property.

The principle of induction is easily understood using the following intuitive argument: If the number 1 possesses the given property, then the second condition implies that the number 2 possesses the property. But, then again, the second condition implies that the number 3 possesses this property, and so on. The principle of induction is a formal statement of this intuitive reasoning.

For a detailed treatment of different methods of proof, see [157].

1.2 Notation

Throughout, we use the following notation. If is a set, then we write to mean that is an element of . When an object is not an element of a set , we write . We also use the "curly bracket notation" for sets, writing down the first few elements of a set followed by three dots. For example, is the set containing the elements and so on. Alternatively, we can explicitly display the law of formation. For example, reads "the set of all such that is real and is greater than 5." The colon following reads "such that." An alternative notation for the same set is .

If and are sets, then we write to mean that every element of is also an element of . In this case, we say that is a subset of . If and are sets, then we denote by (" minus ") the set of all points in that are not in . Note that is a subset of . Given , the complement of is the set , i.e. all points in that are not in .

The notation means " is a function from the set into the set ." The symbol denotes arithmetic assignment. Thus, a statement of the form means " becomes ." The symbol means "equals by definition."

Throughout the text, we mark the end of theorems, lemmas, propositions, and corollaries using the symbol . We mark the end of proofs, definitions, and examples by .

We use the IEEE style when citing reference items. For example, [77] represents reference number 77 in the list of references at the end of the book.

Exercises

1. 1.1 Construct the truth table for the statement "(not B)(not A)," and use it to show that this statement is equivalent to the statement "AB."
2. 1.2 Construct the truth table for the statement "not (A and (not B))," and use it to show that this statement is equivalent to the statement "AB."
3. 1.3 Prove De Morgan's law by constructing the appropriate truth tables.
4. 1.4 Prove that for any statements A and B, we have "A (A and B) or (A and (not B))." This is useful because it allows us to prove a statement A by proving the two separate cases "(A and B)" and "(A and (not B))." For example, to prove that for any , we separately prove the cases " and " and " and ." Proving the two cases turns out to be easier than proving the statement directly (see Section 2.4 and Exercise 2.8).
5. 1.5 (This exercise is adopted from [29, pp. 80-81].) Suppose that you are shown four cards, laid out in a row. Each card has a letter on one side and a number on the other. On the visible side of the cards are printed the symbols

   Determine which cards you should turn over to decide if the following rule is true or false: "If there is a vowel on one side of the card, then there is an even number on the other side."

6. 1.6 Write a direct proof of the following statement: If an integer is even, then is also even. Recall that an integer is even if it is divisible by 2.
7. 1.7 Try to prove, first using direct proof, the following statement: For an integer , if is odd, then is odd. (Recall that an integer is odd if it is not divisible by 2 and is even otherwise.) Now prove it using contraposition and then using contradiction.
8. 1.8 Prove the following statement: For every positive integer , is divisible by 5.
9. 1.9 List all possible subsets of the following sets:
   1. ;
   2. ;
   3. ;
   4. .

   Hint: Recall that the empty set is a subset of all sets. If we view a set as a collection of elements in a box denoted , then the empty set can be viewed as an empty box. This can be described as . If a finite set has elements, then it has subsets.

10. 1.10 Which of the following statements is false,...