Sets are the next building block of mathematics. Just as we did with propositions, this section defines basic terms and explores how we can combine these objects to build new ones.
If \(A\) is a set and \(a\) is an element of \(A\text{,}\) we write \(a \in A\text{.}\) If \(b\) isn’t an element of \(A\text{,}\) we write \(b \not\in A\text{.}\)
\(\mathbb{R} \) is the set of all real numbers. In Calculus, we wrote the interval \((-\infty, \infty)\text{.}\) This includes all fractions and those irrational numbers that can’t be written as fractions.
Here are several examples showing a variety of ways of writing sets:
\(\{x \mid |2x+1| \le 10 \and x \in \Z\}\) tells us our elements are going to be whatever \(x\) satisfy the expression \(|2x+1| \le 10\) where our variables are integers. This will be exactly \(\{-5, -4, -3, -2, -1, 0, 1, 2, 3, 4\}\)
\(\{a \in \N \mid \frac{a}{2} \ge 4 \}\) means that the elements will be natural numbers (this is the first part, \(a \in \N\)), and the qualification to be in the set is that \(a/2 \ge 4\text{.}\) Note that same letter \(a\text{!.}\) A little algebra says \(a\ge 8\) is the requirement to be a member, and since the elements are those same \(a\) numbers, our set is \(\{8, 9, 10, 11, 12, \dots\}\)
\(\{\frac{a}{2} \in \Q \mid a \in \N\}\) means the elements will be rational numbers of the form \(\frac{a}{2}\) (this is the first part, \(\frac{a}{2} \in \Q\)). Since the qualification is just that the \(a\) is a natural number, that tells us to feed all natural numbers into our set, so we have \(\{0, \frac12, 1, \frac32, 2, \frac52, \dots\}\)
We can also write, \(\{3\}\subset S\text{,}\) because although the set \(\{3\}\) is a subset of \(S\text{,}\) they’re unequal: \(\{3\} \ne S\text{,}\) so it’s a proper subset.
The following theorem tells us that every set contains itself and also the empty set. That every set is a subset of itself maybe feels obvious, but the other half, that the empty set is a subset of every set, is a little less obvious. We will formally prove both statements are true in Example 2.2.2 after we develop the tools of logical proof.
Let \(S\) be a set. If there are exactly \(n\) distinct elements in \(S\) where \(n\) is a non-negative integer, then we say that \(S\) is a finite set with cardinality of \(n\text{,}\) and write \(|S|=n\text{.}\)
Ordered pairs will be familiar from algebra and calculus when you plotted points on the Cartesian plane. \((x, y)\) meant that the \(x\) came from one set (corresponding to the horizontal axis), and \(y\) came from another set (corresponding to the vertical axis).
Let \(A\) and \(B\) be sets. The Cartesian Product of \(A\) and \(B\text{,}\) denoted by \(A\times B\text{,}\) is the set of all ordered pairs \((a,b)\) where \(a\in A\) and \(b \in B\text{.}\) That is,
\begin{equation*}
A \times B = \{ (a,b) \mid a\in A \text{ and } b \in B\}
\end{equation*}
Returning to our calculus experience, for the ordered pair \((x,y)\text{,}\) our \(x\) and \(y\) variables all came from the set of real numbers, so we’d formally say that the point \((x,y)\) is an element in the set \(\R \times \R\) or \(\R^2\text{,}\) that is, \((x,y) \in \R^2\text{.}\) If you’ve had calc 3, the points \((x,y,z) \in \R^3\text{,}\) live in three-dimensional space. Let’s take a look at discrete examples.
If \(A\) and \(B\) are two sets, we define the union of \(A\) and \(B\text{,}\) denoted \(A \cup B\text{,}\) to be the set of all elements that are in \(A\) or \(B\text{,}\) or both.
\begin{equation*}
A \cup B = \{ x \mid x \in A \text{ or } x \in B\}
\end{equation*}
If \(A\) and \(B\) are two sets, we define the intersection of \(A\) and \(B\text{,}\) denoted \(A \cap B\text{,}\) to be the set of only elements that are in both \(A\) and \(B\text{.}\)
\begin{equation*}
A \cap B = \{ x \mid x \in A \text{ and } x \in B\}
\end{equation*}
If \(A\) and \(B\) are two sets, we define the difference of \(A\) and \(B\text{,}\) denoted \(A \setminus B\text{,}\) to be the set of only elements that are only in \(A\) and not in \(B\text{.}\)
\begin{equation*}
A \setminus B = \{ x \mid x \in A \text{ and } x \not\in B\}
\end{equation*}
What do you observe about some combination of the cardinalities above? Be on the lookout for patterns as you work through more cardinality questions. We’ll find formulas in the future for things such as \(|A \cup B|\text{,}\)\(\mathcal{P}(A)\text{,}\) and \(|A \times B|\)
An identity is a statement which is true if we replace the variables with specific sets. One way that we can show that an identity is true by shading a Venn Diagram for each side of the equality.
It would be good practice to take a moment and confirm for yourself that these identities are true by shading a Venn diagram for each side of the equalities.
What kind of object is each of the following? Is it a set, a number, or a logical proposition? If it’s a set, give its elements. If it’s a number, give the number. If it’s proposition, give its truth value.
Let \(A = \{1, 2, 3, 4, 5, 6\}\text{,}\)\(B = \{2, 4, 6\}\text{,}\)\(C = \{1, 2, 3\}\) and \(D = \{7, 8, 9\}\text{.}\) Determine which of the following are true, false, or meaningless.
True. \(3\) is the only element of the set \(\{3\}\text{,}\) and is an element of \(C\text{,}\) so every element in \(\{3\}\) is an element of \(C\text{.}\)
\((D \cap \bar C) \cup \bar{A \cap B} = \{1, 3, 5, 7, 8, 9, 10\}.\) The set contains all elements that are either in \(D\) but not in \(C\) (i.e., \(\{7,8,9\}\)), or not in both \(A\) and \(B\) (i.e., \(\{1,3,5,7,8,9,10\}\)).
Let \(A = \{x \in \N \st 3 \le x \le 13\}\text{,}\)\(B = \{x \in \N \st x \mbox{ is even} \}\text{,}\) and \({C = \{x \in \N \st x \mbox{ is odd} \}}\text{.}\)
Venn diagram of \(\bar A \cap B \cap \bar C\text{.}\) Three circles are labeled A, B, and C. Only the part of B that doesn’t overlap A and doesn’t overlap C is shaded.
Venn diagram of \((A \cup B) \setminus C\text{.}\) Three circles are labeled A, B, and C. Only those parts of A and B that do not overlap C are shaded.
There are eight possible sets. \(B\) can be any of \(\{2,3,5\}\text{,}\)\(\{1,2,3,5\}\text{,}\)\(\{2,3,4, 5\}\text{,}\)\(\{2,3,5,6\}\text{,}\)\(\{1,2,3,4,5\}\text{,}\)\(\{1,2,3,5,6\}\text{,}\)\(\{2,3, 4, 5, 6\}\text{,}\)\(\and \{1, 2, 3, 4, 5, 6\}\)
Let \(A = \{1,2,\ldots, 10\}\text{.}\) How many subsets of \(A\) contain exactly one element (i.e., how many singleton subsets are there)? How many doubleton subsets (containing exactly two elements) are there?
There are many examples. Here’s one possibility: \(A = \{ a, b, c\}, B=\{b,c,d,e\}\text{.}\) Then the union is \(A \cup B = \{a, b, c, d, e\}\text{.}\)
In a regular deck of playing cards there are 26 red cards and 12 face cards. Explain, using sets and what you have learned about cardinalities, why there are only 32 cards which are either red or a face card.
The intersection of the set of red cards and the set of face cards is nonempty. It includes six cards: Jack of Hearts, Queen of Hearts, King of Hearts, Jack of Diamonds, Queen of Diamonds, and King of Diamonds.
Recall \(\Z = \{\ldots,-2,-1,0, 1,2,\ldots\}\) (the integers). Let \(\Z^+ = \{1, 2, 3, \ldots\}\) be the positive integers. Let \(2\Z\) be the even integers, \(3\Z\) be the multiples of 3, and so on.
\(2\Z \cap 3\Z\) is the set of all integers which are multiples of both 2 and 3 (these are the multiples of 6). Therefore \(2\Z \cap 3\Z = \{6x \st x \in \Z )\}\text{.}\)
