Discrete Mathematics for Computer Science

10 CHAPTER 1 Sets, Proof Templates, and Induction

j e N, which would prove that 2k 0 + 5 = 2j + 1 E B. The algebra needed to see if this is

possible involves solving for j in terms of ko. This computation

2j+] =2k 0 +5

2j =2k 0 +5-1 =2k 0 +4

j =k0+2

shows that for any ko, the needed j is ko + 2, which is clearly an element of N. This says

that we can write an element of A as 2k 0 + 5 = 2(ko + 2) + 1 for k 0 + 2 E N. Therefore,

since an arbitrary element of A is an element of B, we have A C B. U

If the condition in Template 1.2 is not satisfied-that is, for two sets A and B, we

have A Z B-this means that there is an element in A that is not an element of B. We

summarize this observation in Template 1.3.

To prove that one set is not a subset of another (A g B), show that some element x of

A is not in B.

Example 6. Let

A={ncN:n=2k -3forsomek EN)

and

B = {n: n N and n = j2 + 3 for some j E NJ

Prove that A g B.

Solution. We must find some element of A that is not an element of B. If we list

the first few elements of A and B, perhaps a candidate element will appear. A =

{-3, -1, 5, 15, 47 .... }, and B = {3, 4, 7, 12, 19, ... 1. An obvious candidate is -3, since

-3 E A and -3 V B. We need to show that there is some fixed integer of the form 2k 0 - 3,

for ko e N, that can be written as j2 + 3 for some choice ofj c N. If such a j existed, we

would have 2k 0 - 3 = j2 + 3. In the case ko = 0, the element j would have to satisfy

-3 = j^2 +3 or j^2 + 6 = 0 for -3 to be in B. Since no such j exists, -3 0 B. U

One last possibility for set inclusion: One set can be a subset of a second subset, but

not every element of the first set need be an element of the second set. This proper inclusion

is formalized in the next template.

To prove that one set is a proper subset of another (A C B), first prove that A __ B,

and then show that some element x of B is not in A.