Applied Discrete Structures

1.1 Set Notation and Relations

1.1.1 The notion of a set 

The term set is intuitively understood by most people to mean a collection of objects that are called elements (of the set). This concept is the starting point on which we will build more complex ideas, much as in geometry where the concepts of point and line are left undefined. Because a set is such a simple notion, you may be surprised to learn that it is one of the most difficult concepts for mathematicians to define to their own liking. For example, the description above is not a proper definition because it requires the definition of a collection. (How would you define “collection”?) Even deeper problems arise when you consider the possibility that a set could contain itself. Although these problems are of real concern to some mathematicians, they will not be of any concern to us. Our first concern will be how to describe a set; that is, how do we most conveniently describe a set and the elements that are in it? If we are going to discuss a set for any length of time, we usually give it a name in the form of a capital letter (or occasionally some other symbol). In discussing set A, if x is an element of A, then we will write x ∈ A. On the other hand, if x is not an element of A, we write x /∈ A. The most convenient way of describing the elements of a set will vary depending on the specific set.

Enumeration. When the elements of a set are enumerated (or listed) it is traditional to enclose them in braces. For example, the set of binary digits is {0, 1} and the set of decimal digits is {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. The choice of a name for these sets would be arbitrary; but it would be “logical” to call them B and D, respectively. The choice of a set name is much like the choice of an identifier name in programming. Some large sets can be enumerated without actually listing all the elements. For example, the letters of the alphabet and the integers from 1 to 100 could be described as A = {a, b, c, . . . , x, y, z}, and G = {1, 2, . . . , 99, 100}. The three consecutive “dots” are called an ellipsis. We use them when it is clear what elements are included but not listed. An ellipsis is used in two other situations. To enumerate the positive integers, we would write {1, 2, 3, . . .}, indicating that the list goes on infinitely. If we want to list a more general set such as the integers between 1 and n, where n is some undetermined positive integer, we might write {1, . . . , n}.

Standard Symbols. Sets that are frequently encountered are usually given symbols that are reserved for them alone. For example, since we will be refer- ring to the positive integers throughout this book, we will use the symbol P instead of writing {1, 2, 3, . . .}. A few of the other sets of numbers that we will use frequently are:

• P: the positive integers, {1, 2, 3, 4, . . .}
• N: the natural numbers, {0, 1, 2, 3, . . .}
• Z: the integers, {. . . ,−3,−2,−1, 0, 1, 2, 3, . . .}
• Q: the rational numbers
• R: the real numbers
• C: the complex numbers

Caution: Some people (roughly half of the world?) call the set {1, 2, 3, 4, . . .} the natural numbers. We are not among them. We take the pythonic approach that assumes that starting with zero is more natural than starting at one.