Discrete Mathematics for Computer Science

Subsection 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\text{,}\) if \(x\) is an element of \(A\text{,}\) then we will write \(x \in A\text{.}\) On the other hand, if \(x\) is not an element of \(A\text{,}\) we write \(x \notin A\text{.}\) 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\}\text{.}\) The choice of a name for these sets would be arbitrary; but it would be “logical” to call them \(B\) and \(D\text{,}\) 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,\ldots , x, y, z\}\text{,}\) and \(G = \{1, 2, \ldots , 99, 100\}\text{.}\) 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,\ldots \}\text{,}\) indicating that the list goes on infinitely. If we want to list a more general set such as the integers between 1 and \(n\text{,}\) where \(n\) is some undetermined positive integer, we might write \(\{1,\ldots ,n\}\text{.}\)

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

• \(\mathbb{(N)}\text{:}\) the natural numbers, \(\{0, 1, 2, 3, \ldots \}\)

• \(\mathbb{(Z)}\text{:}\) the integers, \(\{\ldots , -3, -2, -1, 0, 1, 2, 3,\ldots \}\)

  • \(\mathbb{(Z)}^+\) or \(\mathbb{(P)}\text{:}\) the positive integers, \(\{1, 2, 3,\ldots \}\)

• \(\mathbb{(Q)}\text{:}\) the rational numbers

• \(\mathbb{(R)}\text{:}\) the real numbers

• \(\mathbb{(C)}\text{:}\) the complex numbers

Set-Builder Notation. Another way of describing sets is to use set-builder notation. For example, we could define the rational numbers as

Note that in the set-builder description for the rational numbers:

• \(a/b\) indicates that a typical element of the set is a “fraction.”

• The vertical line, \(\mid\text{,}\) is read “such that” or “where,” and is used interchangeably with a colon.

• \(a, b\in \mathbb{Z}\) is an abbreviated way of saying \(a\) and \(b\) are integers.

• Commas in mathematics are read as “and.”

The important fact to keep in mind in set notation, or in any mathematical notation, is that it is meant to be a help, not a hindrance. We hope that notation will assist us in a more complete understanding of the collection of objects under consideration and will enable us to describe it in a concise manner. However, brevity of notation is not the aim of sets. If you prefer to write \(a\in \mathbb{Z}\) and \(b\in \mathbb{Z}\) instead of \(a, b\in \mathbb{Z}\text{,}\) you should do so. Also, there are frequently many different, and equally good, ways of describing sets. For example, \(\{x\in \mathbb{R} \mid x^{2}-5x+6 =0\}\) and \(\{x \mid x \in \mathbb{R}, x^{2}-5x+6=0\}\) both describe the solution set \(\{2, 3\}\text{.}\)

A proper definition of the real numbers is beyond the scope of this text. It is sufficient to think of the real numbers as the set of points on a number line. The complex numbers can be defined using set-builder notation as \(\mathbb{C} = \{a + b i:a, b \in \mathbb{R}\}\text{,}\) where \(i^2 = -1\text{.}\)

In the following definition we will leave the word “finite” undefined.

As we will see later, there are different infinite cardinalities. We can't make this distinction until Chapter 6, so we will restrict cardinality to finite sets for now.

Subsection 1.1.2 Subsets

A few comments are in order about the expression “if and only if” as used in our definitions. This expression means “is equivalent to saying,” or more exactly, that the word (or concept) being defined can at any time be replaced by the defining expression. Conversely, the expression that defines the word (or concept) can be replaced by the word.

Occasionally there is need to discuss the set that contains no elements, namely the empty set, which is denoted by \(\emptyset\). This set is also called the null set.

It is clear, we hope, from the definition of a subset, that given any set \(A\) we have \(A\subseteq A\) and \(\emptyset \subseteq A\text{.}\) If \(A\) is nonempty, then \(A\) is called an improper subset of \(A\text{.}\) All other subsets of \(A\text{,}\) including the empty set, are called proper subsets of \(A\text{.}\) The empty set is an improper subset of itself.