CS202: Discrete Structures

Chapter 1: Set Theory

empty set

We begin this chapter with a brief description of discrete mathematics. We then cover some of the basic set language and notation that will be used throughout the text. Venn diagrams will be introduced in order to give the reader a clear picture of set operations. In addition, we will describe the binary representation of positive integers and introduce summation notation and its generalizations.

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 \in A$. On the other hand, if $x$ is not an element of $A$, we write $x \notin 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 $\left \{ 0,1 \right \}$ and the set of decimal digits is $\left \{ 0,1,2,3,4,5,6,7,8,9 \right \}$. 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 = \left \{ a,b,c, . . . , x,y,z \right \}$ and $G = \left \{ 1,2, . . . , 99,100 \right \}$. 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 $\left \{ 1,2,3, . . . \right \}$ 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 $\left \{ 1, . . . ,n \right \}$.

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 $\mathbb{P}$ instead of writing $\left \{ 1,2,3, . . . \right \}$. A few of the other sets of numbers that we will use frequently are:

• $\mathbb{N}$: the natural numbers, $\left \{ 0,1,2,3, . . . \right \}$
• $\mathbb{Z}$: the integers, $\left \{ . . . , -3,-2,-1,0,1,2,3, . . . \right \}$
• $\mathbb{Q}$: the rational numbers
• $\mathbb{R}$: the real numbers
• $\mathbb{C}$: 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

$\mathbb{Q} = \left \{ a/b |a,b \in \mathbb{Z}, b \neq 0 \right \}$

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, |, 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}$ you should do so. Also, there are frequently many different, and equally good, ways of describing sets. For example,

$\left \{ x \in \mathbb{R} | x^2 - 5x + 6 = 0 \right \}$ and $\left \{ x | x \in \mathbb{R} , x^2 - 5x + 6 = 0 \right \}$ both describe the solution set $\left \{ 2,3 \right \}$.

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} = \left \{ a + bi : a, b \in \mathbb{R} \right \}$, where $i^2 = -1$.

In the following definition, we will leave the word "finite" undefined.

Definition 1.1.1: Finite Set. A set is a finite set if it has a finite number of elements. Any set that is not finite is an infinite set.

Definition 1.1.2: Cardinality. Let $A$ be a finite set. The number of different elements in $A$ is called its cardinality. The cardinality of a finite set A is denoted $|A|$

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

1.1.2 Subsets

Definition 1.1.3: Subset. Let $A$ and $B$ be sets. We say that $A$ is a subset of $B$ if and only if every element of $A$ is an element of $A$. We write $A \subseteq B$ to denote the fact that $A$ is a subset of $B$.

Example 1.1.4: Some Subsets.

If $A = \left \{ 3,5,8 \right \}$ and $B = \left \{ 5,8,3,2,6 \right \}$, then $A \subseteq B$

$\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}$

If $S = \left \{ 3,5,8 \right \}$ and $T = \left \{ 5,3,8 \right \}$ then $S \subseteq T$ and $T \subseteq S$

Definition 1.1.5: Set Equality. Let $A$ and $B$ be sets. We say that $A$ is equal to $B$ (notation $A = B$ ) if and only if every element of $A$ is an element of $B$ and conversely every element of $B$ is an element of $A$; that is, $A \subseteq B$ and $B \subseteq A$

Example 1.1.6: Examples illustrating set equality.

In Example 1.1.4, $S = T$ . Note that the ordering of the elements is unimportant.

The number of times that an element appears in an enumeration doesn't affect a set. For example, if $A = \left \{ 1,5,3,5 \right \}$ and $A = \left \{ 1,5,3 \right \}$, then $A = B$. Warning to readers of other texts: Some books introduce the concept of a multiset, in which the number of occurrences of an element matters.

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 a 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$. If $A$ is nonempty, then $A$ is called an improper subset of $A$. All other subsets of $A$, including the empty set, are called proper subsets of $A$. The empty set is an improper subset of itself.

Note 1.1.7: Not everyone is in agreement on whether the empty set is a proper subset of any set. In fact earlier editions of this book sided with those who considered the empty set an improper subset. However, we bow to the emerging consensus at this time. 

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.