Discrete Mathematics for Computing (Draft)

In order to start working with sets, we’ll need to introduce some notation. As mentioned in the introduction to this champter, a set is a (possibly empty) collection of items, called elements. A useful mental paradigm for sets is to think of a set as a "bag of items". The elements of a set are the items which can be observed by reaching into the bag and taking something out. In general, sets will be denoted using capital letters such as \(A\text{,}\) \(B\text{,}\) \(X\text{,}\) etc. Elements of those sets will be denoted using lowercase letters. We have the following additional notation for working with sets.

Since sets contain elements, it is useful to have a notation to denote whether and element belongs to a set. The notation \(a\in A\) states that the element \(a\) is in the set \(A\text{,}\) while the notation \(b\not \in A\) states that the element \(b\) is not an element of the set \(A\text{.}\) For convenience, we may write \(a, b, c\in A\text{,}\) to indicate that all of the elements \(a\text{,}\) \(b\text{,}\) and \(c\) belong to the set \(A\text{.}\) Finally, if a set has no elements, it is called the empty-set and is denoted by \(\emptyset\text{.}\)

We need methods for describing the contents of a set. Two are quite common: roster notation lists all of the elements containined in a set, while set-builder notation describes a condition which determines set membership. Roster notation is useful when the set to be described contains few elements or follows a simple pattern. For example, \(A = \{1, 2, 3, 11\}\) and \(B = \{2, 4, 6, 8, \cdots\}\) are both descriptions in roster notation. Set-builder notation follows the form \(A = \{\text{ sample element } : \text{ condition }\}\text{.}\) For example, \(X = \{x : x \in \mathbb{R} \text{ and } x^2 < 9\}\) is the set of all real numbers (\(\mathbb{R}\)) whose squares are less than \(9\text{.}\)

In addition to roster and set-builder notation, some sets are simply so common that they have their own notations. The set of natural numbers, \(\{1, 2, 3, \cdots\}\text{,}\) is denoted by \(\mathbb{N}\text{.}\) The set of integers, \(\{\cdots, -2, -1, 0, 1, 2, \cdots\}\text{,}\) is denoted by \(\mathbb{Z}\text{.}\) The set of all rational numbers is denoted by \(\mathbb{Q}\) and the set of all real numbers is denoted by \(\mathbb{R}\text{,}\) as you saw in the example above.

In addition to describing the conents of a set, an ability to describe relationships between sets is also useful. If every element of the set \(A\) is also an element of the set \(B\text{,}\) then we say that \(A\) is a subset of \(B\) and we write \(A\subseteq B\) to denote this. If \(A\subseteq B\) and \(B\subseteq A\text{,}\) then we write \(A = B\) since \(A\) and \(B\) contain exactly the same elements.

Now that you’ve practiced with some of our basic set notation, we’ll introduce one more concept before moving on to the next section. Given a set containing a finite number of elements, it is sometimes useful to identify the number of elements in the set. The cardinality of a set \(A\) measures the number of elements in the set \(A\text{.}\) The cardinality of \(A\) is often denoted by \(n\left(A\right)\) or \(\left|A\right|\text{.}\)

In this section we’ve built up a familiarity with sets and their elements. We’ve also described relationships between sets. In particular, we’ve considered what it means for one set to be a subset of another set as well as what it means for two sets to be equal to one another. In the next section, we’ll consider operations on and between sets.