Discrete Mathematics for Computer Science

Operations on Sets 27

quite reasonable is, in fact, true. In the case discussed following Theorem 4, a counterex-
ample would give a concrete instance of sets that satisfy the hypothesis of the alternate
statement, whereas the same sets do not satisfy the conclusion. This proof idea is shown in
Template 1.9.

To disprove results starting "for every x c A," find an x that can be proven to be in A

and for which the result fails.

Theorem 7 in Section 1.3.2 proved that if A C B, then B C A by assuming that A C
B and B K A. We then showed this led to a contradiction. The format for this proof is
summarized in Template 1.10.

To prove an assertion a by contradiction, use one of the following two forms:

Form 1: Assume assertion a is false, and prove that some other assertion b is false

where assertion b is known to be true.

Form 2: Assume assertion a is false. For some assertion b, prove that both assertion

b is true and assertion b is false.

The statement of Theorem 7(b) can be construed as saying that a statement and its con-
trapositive have the same truth value. For example, think of "A C B" as being translated
"if x E A, then x E B." Similarly, think of "B C A" as "if x 0 B, then x 0 A." How
would an if-then statement be proved to be true or false just when its contrapositive is?
The answer is almost exactly the way that Theorem 7(b) was proved. The idea of this proof
technique is summarized in Template 1.11.

To prove a theorem using an indirect proof, prove "if p, then q" by proving "if not q,

then not p."