Discrete Mathematics for Computer Science

Basic Definitions 3

Set-Theoretic Notation

Three methods to describe the set with elements 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 are:

1. List the elements in braces: {0, 1, 2, 3, 4, 5, 6, 7, 8, 91. We can also abbreviate this
   list as 10, 1, 2,..., 9}.


2. Describe the elements in terms of some property they satisfy:

{x : x is an integer and x > -1/2 and x < 19/2)

This notation is read as "the set of (all) x such that x is an integer and x is greater

than minus one-half and x is less than nineteen halves." The colon is read as "such

that." The description following the colon tells what property these x's have.

3. Describe the elements as the set of all elements in some other set that satisfy some
   property. Here, if Z denotes the set of integers, then the set can be defined as

{x E Z : x> -1/2 andx < 19/21

Methods 2 and 3 are almost the same. Method 3 is preferred, however, because in

some really peculiar circumstances, method^2 can cause trouble.

1

There is a particular disadvantage to using ellipses with method 1. If someone writes

A = {0, 1,2,...,^71

it is assumed everyone will understand what is intended-that is, the set A contains the
elements 0, 1, 2, 3, 4, 5, 6, and 7. Frequently, however, the intended pattern is not as
obvious as the person using the ellipsis thinks. Suppose

A = {2, 4,..., 655361

What are the other elements? Guessing what was meant requires understanding the pattern
that gives rise to the elements listed. Since 65536 = 216, one conjecture might be

A = {2', 22, 2', 24, 25, 26, 2', 28, 2', 210, 211, 212, 213, 214, 215, 2161

It could just as well be conjectured that

A = {, 2 22 2222} = {2, 4, 16, 655361

There are endless other possibilities, with no real way to choose among them. (Nobody
said the pattern had to be simple.) This notation should only be used when it is obvious
from the context exactly what is meant.

1 After Cantor defined set theory, researchers found some paradoxes. The most famous is Russell's paradox,
which is similar to the so-called "liar's paradox": "This sentence is a lie." Work through it: If it is false, then it is
true, and if it is true, then it is false.
Russell's paradox is this. Let x be the set of all sets that are not elements of themselves. Now, is x an element
of itself?
Work through it: If it is, then it is not, and if it is not, then it is. What's wrong? Most modem set theorists assert
that using definition method 2 is at fault-note that Bertrand Russell (English mathematician and philosopher,
1872-1970) used that form in defining x. The set of all sets which are not elements of themselves is deemed "too
big" to be a set. By using definition method 3, we avoid constructing sets which are "too big."
Because we are not going into axiomatic set theory, however, we will be unable to avoid method 2 entirely in
this book.