Sets
A set is an unordered collection of objects. Consider the set of books with two-word titles, the set of prime numbers, or the set of english words that are spelled the same forwards as backwards. Imagine the set of all sets that have three elements in them. The foundation of mathematics is built with sets.
We will consider sets that look like this: \[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.
We can write: \[a \in \{a,b,c\} \] to say that \(a\) "is an element of" the set. It would also be true to say that \(d\) is not in the set, or: \[ d \notin \{a,b,c\} \]
Relationships Between Sets
Two sets are equal if they have exactly the same elements. For exmaple, \[\{1,2,3\}=\{2,1,3\} \]
What about the sets \(A =\{1,2,3\}\) and \(B=\{1,2,3,4\}\)? Clearly \(A \neq B\), but notice that every element of \(A\) is also an element of \(B\text{.}\) Because of this, we say that \(A\) is a subset of \(B\), or in symbols \(A \subset B\) or \(A \subseteq B\text{.}\) 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\text{.}\) This is anlaogous to the difference between \(<\) and \(\leq\text{.}\)
The cardinality of a set is the size of a set, and is equal to the number of elements in the set. If set \(A\) has \(3\) elements then we say that \(|A|=3\text{.}\)
We call the set of all subsets of \(A\) the power set of \(A\text{.}\) For \(A=\{1,2,3\}\), the power set \(\mathcal{P}(A) = \{ \{\},\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\} \}\)
Operations
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\text{,} \] read, "\(C\) is the union of \(A\) and \(B\text{,}\)" means that the elements of \(C\) are exactly the elements which 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\}\text{,}\) then \(A \cup B = \{1, 2, 3, 4\}\text{.}\)
The other common operation on sets is intersection. We write, \[ C = A \cap B \] and say, “\(C\) is the intersection of \(A\) and \(B\text{,}\)” when the elements in \(C\) are precisely those both in \(A\) and in \(B\text{.}\) So if \(A = \{1, 2, 3\}\) and \(B = \{2, 3, 4\}\text{,}\) then \(A \cap B = \{2, 3\}\text{.}\)
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 \(\mathbb{N}\text{.}\) Sometimes we denote this universe by \(\mathcal{U}\text{.}\) Given this context, we might wish to speak of all the elements which are not in a particular set. We say \(B\) is the complement of \(A\text{,}\) and write, \[ B = \bar A \] when \(B\) contains every element not contained in \(A\text{.}\) So, if our universe is \(\{1, 2,\ldots, 9, 10\}\text{,}\) and \(A = \{2, 3, 5, 7\}\text{,}\) then \(\bar A = \{1, 4, 6, 8, 9,10\}\text{.}\)
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 which are both elements of \(A\) and not elements of \(B\text{.}\) What have we done? We've started with \(A\) and removed all of the elements which were in \(B\text{.}\) 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).
Venn Diagrams
A Venn diagram is a a diagram depicting overlapping sets and their relationships. Below are several Venn diagrams that visualize set operations.
Special Sets
| \(\emptyset\) | The empty set is the set which contains no elements. |
| \(\mathcal{U}\) | The universe set is the set of all elements. |
| \(\mathbb{N}\) | The set of natural numbers. That is, \(\mathbb{N} = \{0, 1, 2, 3\ldots\}\text{.}\) |
| \(\mathbb{Z}\) | The set of integers. That is, \(\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, 3, \ldots\}\text{.}\) |
| \(\mathbb{Q}\) | The set of rational numbers. |
| \(\mathbb{R}\) | The set of real numbers. |
| \(\mathcal{P}(A)\) | The power set of any set \(A\) is the set of all subsets of \(A\text{.}\) |
Set Theory Notation
| \(:\) | \(\{x : x > 2\}\) is the set of all \(x\) such that \(x\) is greater than 2. |
| \(\in\) | \(2 \in \{1,2,3\}\) asserts that 2 is an element of the set \(\{1,2,3\}\text{.}\) |
| \(\not\in\) | \(4 \notin \{1,2,3\}\) because 4 is not an element of the set \(\{1,2,3\}\text{.}\) |
| \(\subseteq\) | \(A \subseteq B\) asserts that \(A\) is a subset of \(B\): every element of \(A\) is also an element of \(B\text{.}\) |
| \(\subset\) | \(A \subset B\) asserts that \(A\) is a proper subset of \(B\): every element of \(A\) is also an element of \(B\text{,}\) but \(A \ne B\text{.}\) |
| \(\cap\) | \(A \cap B\) is the intersection of \(A\) and \(B\): the set containing all elements which are elements of both \(A\) and \(B\text{.}\) |
| \(\cup\) | \(A \cup B\) is the union of \(A\) and \(B\): is the set containing all elements which are elements of \(A\) or \(B\) or both. |
| \(\times\) | \(A \times B\) is the Cartesian product of \(A\) and \(B\): the set of all ordered pairs \((a,b)\) with \(a \in A\) and \(b \in B\text{.}\) |
| \(\setminus\) | \(A \setminus B\) is set difference between \(A\) and \(B\): the set containing all elements of \(A\) which are not elements of \(B\text{.}\) |
| \(\bar{A}\) | The complement of \(A\) is the set of everything which is not an element of \(A\text{.}\) |
| \(|A|\) | The cardinality (or size) of \(A\) is the number of elements in \(A\text{.}\) |