Discrete Mathematics for Computer Science

4 CHAPTER 1 Sets, Proof Templates, and Induction

We often list the elements of a set in a way that shows an obvious association between

the natural numbers and the elements of the set. For example, 1, 2, 22, 2', 24 ..... We call

such a set a sequence. We can refer to a sequence by ao, al, a2 ..... In the above example,

we have ao = 1, al = 2, a2 = 22 ... , a, = 2n ..... The notion of a sequence will be

examined more carefully in Section 4.4. At this time, we just need to have a way to refer

to sets of this form.

Special Sets

There are special names for certain common sets of numbers. Some of them are listed here.

Special Sets

N: the set of natural numbers, or the set of non-negative integers {0, 1, 2, 3, 4, ....

Z: the set of integers, or {. .. ,-3, -2, -1, 0, 1, 2, 3 ... }.

Q: the set of rational numbers, or the set of fractions of integers with nonzero de-

nominator, such as I or 9-7

R: the set of real numbers, or the set of numbers written with a decimal point, such

as 7r = 3.14159. .. , -2.715, or 2.35353535....

0: the empty set, or the set I } with no elements.

In some circumstances, it is convenient to write the set of squares of natural numbers

as {x^2 : x e N} rather than as {x : x E N and for some k E N, x = k^2 }.

1.1.2 Set Membership

To prove an element is a member of a set, you must prove that the element shares the

property that defines membership. For example, we can define the notion of a number

being a prime without knowing that any particular number is a prime. We must then show

that any number we think is a prime has the defining property. First, we need to know what

a divisor is before we can define a prime. For integers m and n, we say m is a divisor of n,

denoted as mIn, if there is a natural number k such that n = m .k. A natural number p is

prime if p : 1 and its only divisors are 1 and p. Let P = {n : n E N and n is a prime). In

Example 1, we will show that P is nonempty.

Example 1. Prove that 3 is a prime-that is, that 3 E P.

Solution. We must show 3 has the property that its only divisors are 1 and 3. Since the

only other possibility is 2 and 2 does not divide 3, 3 is therefore a prime. U

A divisor of an integer is also called a factor.

1.1.3 Equality of Sets

In mathematics, precise language is important if we are all to understand the same meaning

for a statement. For example, what does it mean for two sets to be equal?