Introduction to Discrete Mathematics

A set is a collection of objects called elements. Typically, braces are used to denote sets as in \(\{b,c,d,f\}\text{,}\) which is the same set as \(\{b,d,c,f\}\text{,}\) and the same as \(\{c,f,c,f,d,b\}\text{.}\) If \(A\) is a set and \(x\) is an element of \(A\text{,}\) we write \({x\in A}\text{.}\) Otherwise, we write \({x\notin A}\text{.}\) For example, \(b\in \{b,d,c,f\}\) while \(e\notin \{b,d,c,f\}\text{.}\) The set containing no elements is called the empty set, and is denoted by the symbol \({\emptyset}\text{,}\) but can also be written as \({\{\}}\text{.}\) Any set that contains at least one element is referred to as a nonempty set. If we think of a set as a box potentially containing some stuff, then the empty set is a box with nothing in it.

The empty set and the set \(\{b,c,d,f\}\) are examples of finite sets. Any set that is not finite is an infinite set. For example, the natural numbers defined by \({\mathbb{N}\:= \{1,2,3,\ldots\}}\) and integers defined by \({\mathbb{Z}\:= \{0, \pm 1, \pm2, \pm 3, \ldots\}}\) are both examples of infinite sets. Some books will include zero in the set of natural numbers, but we do not. Since the set of natural numbers consists of the positive integers, the natural numbers are sometimes denoted by \({\mathbb{Z}^+}\text{.}\) The real numbers, denoted by \({\mathbb{R}}\text{,}\) is another example of an infinite set. If you look closely at our definitions for the natural numbers and integers you will notice that we wrote \({\:=}\) instead of \(=\text{.}\) We use \(\:=\) to mean that the symbol or expression on the left is defined to be equal to the expression on the right.

The cardinality of a set \(A\text{,}\) denoted by \({|A|}\text{,}\) is the number of elements in \(A\text{.}\) For example, if \(A = \{b,c,d,f\}\text{,}\) then \(|A| = 4\text{.}\) We will mostly concern ourselves with the cardinality of finite sets in this book. Cardinality gets wildly more complicated if we consider infinite sets.

If \(A\) and \(B\) are sets, then we say that \(A\) is a subset of \(B\text{,}\) written \({A\subseteq B}\text{,}\) provided that every element of \(A\) is an element of \(B\text{.}\)

Note that two sets \(A\) and \(B\) are equal, denoted \({A=B}\text{,}\) if the sets contain the same elements. It’s clear that \(A=B\) if and only if \(A \subseteq B\) and \(B \subseteq A\text{.}\) If \(A\subseteq B\text{,}\) then \(A\) is called a proper subset provided that \(A\neq B\text{.}\) In this case, we may write \({A\subset B}\) or \({A\subsetneq B}\text{.}\) Some authors use \(\subset\) to mean \(\subseteq\text{,}\) so some confusion could arise if you are not reading carefully.

Sometimes it is useful to fix a set to focus our attention on. The term universe of discourse (or domain of discourse) generally refers to the collection of objects being discussed in a specific context.

The next theorem should be clear.

The following principle is a natural notion.

The previous problems gives us an indication of how to generalize the Sum Principle (Theorem 1.11) to the case when the sets are not disjoint.

In Problem 1.15, we could describe paths to the coffee shop using expressions like \(NNENEEE\text{,}\) where we interpret the expression from left to right as instruction for which direction to walk at each step. Such expressions have a name. A string of objects of length \(k\) is a linearly ordered arrangements of \(k\) objects. The objects in a string may be repeated unless specified otherwise. For example, \(NNENEEE\) is a string of length 7 consisting of \(N\)’s and \(E\)’s. If a string consists of letters, then it may be called a word (we do not require a word to be in the dictionary!). A bit string is a string consisting of 0’s and 1’s. Each occurrence of a 0 or 1 in a bit string is called a bit. The strings \(010\) and \(100\) are two different bit strings of length 3.

Cartesian products are named after French philosopher and mathematician René Descartes (1596–1650).

We have been dancing around a fundamental counting principle. Let’s state it officially. There are three progressively more general versions, the first of which we already encountered in Problem 1.23. The second version officially follows from the first version by induction, which is a topic we will encounter later. The third version follows from the second by making a careful use of notation to identify the set \(\mathcal{O}\) with a Cartesian product.

The key difference between versions (b) and (c) of the Product Principle is that version (c) does not assume that the set of choices for step \(i\) is independent of the previous choices.

The next result is simply a special case of Theorem 1.11. Sometimes it might be easier to count the opposite of what you are looking to count and then to subtract from the size of the universe of discourse. This idea is sometimes referred to as the Subtraction Principle. Keep this in mind as a method of attack for future problems.

The next principle, called the Division Principle, provides a method for ignoring “unimportant” differences when counting things. Loosely speaking, the general idea is count a larger set of distinct objects and then use the Division Principle to “merge” the ones that are not significantly different from each other. As a motivating example, suppose my kids have 30 toys scattered around the room. After asking my kids to pick up all the toys and put each toy in a bin according to what type of toy it is (e.g., Transformer), there ends up being 6 toys in each bin. In this case, it is easy to see that there must be 5 distinct bins.