Discrete Mathematics for Computer Science

Basic Definitions 11

Example 7. Let

A = {n c N n > 2 and n = 4j - 5 for some j e N}

and

B = in E N n > 0 and n = 2k + 1 for some k e NJ

Prove that A C B.

Solution. To show that A C B, we must show that every element of A is an element

of B. Let n = 4j0 - 5 be an arbitrary element of A for some fixed jo E N. To show that

n c B, we must show that n = 2k + 1 for some k e N. We see if this is possible by solving

for k:

2k+1 =4j 0 -5

2k =^4 jo - 6

k = 2j 0-3

Now, 2jo - 3 > 0, since jo > 2. Since 2(2jo - 3) + 1 = 4j 0 - 5, every element of A is

an element of B, and A C B.

For 0 E N, 2.0 + 1 = 1 e B. If 1 E A, then 1 = 4j - 5 for some j G N. By solving

for j, we find that j must be equal to 3/2, which is not a natural number. Therefore, no j

exists. Therefore, 1 E B, and 1 0 A. It follows that A C B. 0

The next step is to deal with set equality and set inequality.

In the case that we have two set descriptions and want to know that the sets are

equal, there are actually two things to prove. The proof that two sets are equal follows

Template 1.5.

Example 8. Let

A =In : n = 2j for some j E N}

and

B = {n : n = 2k + 2 for some k E Z and k > -1)

Prove that A = B.

Solution. To show that an arbitrary element of A, say, 2jo for some jo e N, is an element
of B, we must find a k E Z such that k > -1 and 2jo = 2k + 2. Solving for k gives k =

jo - 1. Since jo > 0, k = j0 - 1 > - 1, and 2k + 2 e B. To show that an arbitrary element