Discrete Mathematics for Computer Science

12 CHAPTER 1 Sets, Proof Templates, and Induction

of B, say, 2ko + 2 for some k0 E Z and ko > -1, is an element of A, we must find a

j E N such that 2j = 2k 0 + 2. This implies that j must satisfy j = ko + 1 if 2k 0 + 2 is an

element of A. Since ko > -1, we have ko +^1 > 0, and k 0 +^1 defines an element of A.

Because A C B and B C A, it follows that A = B. U

There are often many different descriptions for a single set. One problem is to make

sure that the set description that is given in fact describes the set intended. The idea of a

proof to show that two sets are not equal is given in the next template.

The way to show that A C B is false is to find an element x such that x G A and x g B.

Showing that B C A is false is done analogously, but only one of these implications needs

to be shown to prove that A A B.

Example 9. Let

A = {n: n E N and n = 4j2 - 3 for some j G N}

and

B = {n E N: n = 2k^2 - 3 for somek E N}

Prove that A A B.

Solution. To show that A : B, it suffices to find an element in A that is not an element

of B. We will show that 1 is such an element.

We can write 1 = 4(1)2 - 3. Therefore, 1 E A. If 1 E B, then 1 = 2k^2 - 3 for some

k : N. If this were so, then the element k would satisfy the equation k^2 - 2. Since no such

k exists in N, 1 0 B. I

Other Proofs

In Theorem 2 (Section 1.1.5) we needed to prove two things to conclude the result. This

kind of a proof is typical when you are trying to prove that two statements are simply

different ways of saying the same thing. In Theorem 2 we found that set equality could be

stated either in terms of element membership or in terms of the subset relation. The proof

is formalized in Template 1.7.