Discrete Mathematics for Computer Science

8 CHAPTER 1 Sets, Proof Templates, and Induction

U

I

CM

Figure 1.2 Sample Venn diagram.

Venn diagrams are frequently used to build intuition for proofs. The diagrams are

designed to present fairly general pictures of what is known, and these pictures can often

help a person to see set-theoretic relationships. A good Venn diagram can be very useful,

but a Venn diagram itself is not a proof. In particular, if a mistake is made in drawing the

Venn diagram, it is often possible to think that a property is true when it really is not. In

especially complicated cases, it may be very difficult to see whether the picture is correct.

The picture may be vague on certain points as well. For example, Figure 1.2 suggests

that there are elements of B that are in neither A nor C. This may or may not be true.

Nevertheless, a good Venn diagram is valuable both in suggesting whether a statement

could be true and in motivating and illustrating the proof.

Theorem 3. Let A, B, and C be sets. If A C B and B C C, then A C C.

U

C

Figure 1.3 A c B and B c C.

(The Venn diagram in Figure 1.3 is drawn so that A # B and B # C, but this is not nec-

essarily true. The Venn diagram suggests that if you start with an element of A, then that

element is in B. Then, if the element is in B, it suggests that it is also in C. The proof will

proceed using these two steps.)

Proof We must prove that if A C B and B C C, then A C C. Let x E A, and prove that

x E C. (Think of this as starting the proof by picking x arbitrarily from A.) Then, since

A C B, x E B. We now have x E B, and we are given that B C C. So, it follows that

x E C. Since every element of A is an element of C, it follows that A c C. U

1.1.7 Templates

The proofs in this section use very typical techniques that you will see throughout the book.

When you try to construct a proof, getting started is always a bit daunting. The templates

shown here will give you ideas about what you need to do in a proof. The templates will

describe what is needed to prove that an element is in a set, that one set is or is not a subset