Discrete Mathematics for Computer Science

Basic Definitions 9

of another set, and that two sets are or are not equal. First, we state a template for proving

that an element is a member of a set.

Let A be a given set. To prove x E A, show that x has the property that defines mem-

bership in A.

Example4. LetA={n:nENandn=3k+5forsomekEN}.ls23EA?

Solution. To show that 23 c A, we must find a natural number ko such that

23 = 3k 0 + 5

since every element of A has the form 3k + 5 for some k E N. To find out if there is such

a k, we simply solve the equation for ko and see if the solution is an integer.

3k 0 + 5 = 23

3k 0 = 23 - 5

ko = 18/3 = 6

Since 6 is a natural number, we know 3- 6 + 5 = 23 E A. 0

We use the template for element membership in a set to develop a template for proving
that one set is a subset of another set.

To prove that one set is a subset of another (A C_ B), show that every element x of A

is also in B.

Example 5. Let

A = In n = 2k + 5 for some k E NJ

and

B = {n n = 2j + 1 for some j c N}

Is A C B?

Solution. By writing out a few of the elements in each of these sets, we can at least get
an idea about whether we think A C B. The first six elements of A are 5, 7, 9, 11, 13, and

15. The first six elements of B are 1, 3, 5, 7, 9, and 11. The difference between the two sets
    seems to be the initial values. To show that A C B, we must take an arbitrary element of

A, say, n = 2k0 + 5 for some ko E N, and show that this can be written as 2j + 1 for some