Sets

Note that this section contains a lot of detail on what we can say about sets. If you have never seen anything about unions or Venn diagrams, it is worth reading this carefully.

The most fundamental objects we will use in our studies (and really in all of math) are sets. Much of what follows might be review, but it is very important that you are fluent in the language of set theory. Most of the notation we use below is standard, although some might be a little different than what you have seen before.

For us, a set will simply be an unordered collection of objects. Two examples: We could consider the set of all actors who have played The Doctor on Doctor Who, or the set of natural numbers between 1 and 10 inclusive. In the first case, Tom Baker is an element (or member) of the set, while Idris Elba, among many others, is not an element of the set. Also, the two examples are of different sets. Two sets are equal exactly if they contain the exact same elements. For example, the set containing all of the vowels in the Declaration of Independence is precisely the same set as the set of vowels in the word questionably (namely, all of them); we do not care about order or repetitions, just whether the element is in the set or not.

We need some notation to make talking about sets easier. Consider, \[A = \{1, 2, 3\}\].

This is read, \(A\) is the set containing the elements 1, 2, and 3. We use curly braces \(\{,~~ \}\) to enclose elements of a set. Some more notation: \[a \in \{a, b, c\}\].

The symbol \(\in\) is read is in or is an element of. Thus the above means that \(a\) is an element of the set containing the letters \(a\), \(b\), and \(c\). Note that this is a true statement. It would also be true to say that \(d\) is not in that set: \[d \not\in \{a, b, c\}\].

Be warned: We write \(x \in A\) when we wish to express that one of the elements of the set \(A\) is \(x\). For example, consider the set, \[A = \{1, b, \{x, y, z\}, \emptyset\}\].

This is a strange set, to be sure. It contains four elements: the number 1, the letter b, the set \(\{x,y,z\}\), and the empty set \(\emptyset = \{ \}\), the set containing no elements. Is \(x\) in \(A\)? The answer is no. None of the four elements in \(A\) are the letter \(x\), so we must conclude that \(x \notin A\). Similarly, consider the set \(B = \{1,b\}\). Even though the elements of \(B\) are elements of \(A\), we cannot say that the set \(B\) is one of the elements of \(A\). Therefore \(B \notin A\). (Soon we will see that \(B\) is a subset of \(A\), but this is different from being an element of \(A\).)

We have described the sets above by listing their elements. Sometimes this is hard to do, especially when there are a lot of elements in the set (perhaps infinitely many). For instance, if we want \(A\) to be the set of all even natural numbers, would could write, \[A = \{0, 2, 4, 6, \ldots\}\], but this is a little imprecise. A better way would be \[A = \{x \in \N \st \text{ there exists }n \in \N \text{ such that } x = 2 n\}\].

Note: Sometimes mathematicians use \(|\) or \(\backepsilon\) for the such that symbol instead of the colon. Also, there is a fairly even split between mathematicians about whether \(0\) is an element of the natural numbers, so be careful there.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

We have already said what it means for two sets to be equal: They have exactly the same elements. Thus, for example, \[\{1, 2, 3\} = \{2, 1, 3\}\].

(Remember, the order the elements are written down in does not matter.) Also, \[\{1, 2, 3\} = \{1, 1+1, 1+1+1\} = \{I, II, III\} = \{1, 2, 3, 1+2\}\] since these are all ways to write the set containing the first three positive integers (how we write them doesn't matter, just what they are).

What about the sets \(A = \{1, 2, 3\}\) and \(B = \{1, 2, 3, 4\}\)? Clearly \(A \ne B\), but notice that every element of \(A\) is also an element of \(B\). Because of this we say that \(A\) is a subset of \(B\), or in symbols, \(A \subset B\) or \(A \subseteq B\). Both symbols are read is a subset of. The difference is that sometimes we want to say that \(A\) is either equal to or is a subset of \(B\), in which case we use \(\subseteq\). This is analogous to the difference between \(\lt\) and \(\le\).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Is it possible to add two sets? Not really, however there is something similar. If we want to combine two sets to get the collection of objects that are in either set, then we can take the union of the two sets. Symbolically, \[C = A \cup B\], read, \(C\) is the union of \(A\) and \(B\), means that the elements of \(C\) are exactly the elements that are either an element of \(A\) or an element of \(B\) (or an element of both). For example, if \(A = \{1, 2, 3\}\) and \(B = \{2, 3, 4\}\), then \(A \cup B = \{1, 2, 3, 4\}\).

The other common operation on sets is intersection. We write, \[C = A \cap B\] and say, \(C\) is the intersection of \(A\) and \(B\), when the elements in \(C\) are precisely those both in \(A\) and in \(B\). So if \(A = \{1, 2, 3\}\) and \(B = \{2, 3, 4\}\), then \(A \cap B = \{2, 3\}\).

Often when dealing with sets, we will have some understanding as to what everything is. Perhaps we are only concerned with natural numbers. In this case we would say that our universe is \(\N\). Sometimes we denote this universe by \(\U\). Given this context, we might wish to speak of all the elements that are not in a particular set. We say \(B\) is the complement of \(A\), and write, \[B = \bar A\] when \(B\) contains every element not contained in \(A\). So, if our universe is \(\{1, 2,\ldots, 9, 10\}\), and \(A = \{2, 3, 5, 7\}\), then \(\bar A = \{1, 4, 6, 8, 9,10\}\).

Of course we can perform more than one operation at a time. For example, consider \[A \cap \bar B\].

This is the set of all elements that are both elements of \(A\) and not elements of \(B\). What have we done? We've started with \(A\) and removed all of the elements that were in \(B\). Another way to write this is the set difference: \[A \cap \bar B = A \setminus B\].

It is important to remember that these operations (union, intersection, complement, and difference) on sets produce other sets. Don't confuse these with the symbols from the previous section (element of and subset of). \(A \cap B\) is a set, while \(A \subseteq B\) is true or false. This is the same difference as between \(3 + 2\) (which is a number) and \(3 \le 2\) (which is false).

Having notation like this is useful. We will often want to add or remove elements from sets, and our notation allows us to do so precisely.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

There is a very nice visual tool we can use to represent operations on sets. A Venn diagram displays sets as intersecting circles. We can shade the region we are talking about when we carry out an operation. We can also represent the cardinality of a particular set by putting the number in the corresponding region.

Each circle represents a set. The rectangle containing the circles represents the universe. To represent combinations of these sets, we shade the corresponding region. For example, we could draw \(A \cap B\) as:

Here is a representation of \(A \cap \bar B\), or equivalently \(A \setminus B\):

A more complicated example is \((B \cap C) \cup (C \cap \bar A)\), as seen below.

Notice that the shaded regions above could also be arrived at in another way. We could have started with all of \(C\) and then excluded the region where \(C\) and \(A\) overlap outside of \(B\). That region is \((A \cap C) \cap \bar B\). So the above Venn diagram also represents \(C \cap \bar{\left((A\cap C)\cap \bar B\right)}\). So using just the picture, we have determined that \[(B \cap C) \cup (C \cap \bar A) = C \cap \bar{\left((A\cap C)\cap \bar B\right)}\].