Skip to main content
\( \def\negchoose#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}_{-1}} \newcommand{\mchoose}[2]{\left(\!\binom{#1}{#2}\!\right)} \newcommand{\cycle}[1]{\arraycolsep 5 pt \left(\begin{array}#1\end{array}\right)} \newcommand{\importantarrow}{\Rightarrow} \newcommand{\qchoose}[2]{\left[{#1\atop#2}\right]_q} \newcommand{\bp}{ \begin{enumerate}{\setcounter{enumi}{\value{problemnumber}}}} \newcommand{\ep}{\setcounter{problemnumber}{\value{enumi}} \end{enumerate}} \newcommand{\ignore}[1]{} \renewcommand{\bottomfraction}{.8} \renewcommand{\topfraction}{.8} \newcommand{\apple}{\text{🍎}} \newcommand{\ap}{\apple} \newcommand{\banana}{\text{🍌}} \newcommand{\ba}{\banana} \newcommand{\pear}{\text{🍐}} \newcommand{\pe}{\pear} \DeclareMathOperator{\Fix}{Fix} \DeclareMathOperator{\Orb}{Orb} \newcommand{\F}{\mathcal{F}} \newcommand{\alert}{\fbox} \def\d{\displaystyle} \def\course{Math 228} \newcommand{\f}[1]{\mathfrak #1} \newcommand{\s}[1]{\mathscr #1} \def\N{\mathbb N} \def\B{\mathbf{B}} \def\circleA{(-.5,0) circle (1)} \def\Z{\mathbb Z} \def\circleAlabel{(-1.5,.6) node[above]{$A$}} \def\Q{\mathbb Q} \def\circleB{(.5,0) circle (1)} \def\R{\mathbb R} \def\circleBlabel{(1.5,.6) node[above]{$B$}} \def\C{\mathbb C} \def\circleC{(0,-1) circle (1)} \def\F{\mathbb F} \def\circleClabel{(.5,-2) node[right]{$C$}} \def\A{\mathbb A} \def\twosetbox{(-2,-1.5) rectangle (2,1.5)} \def\X{\mathbb X} \def\threesetbox{(-2,-2.5) rectangle (2,1.5)} \def\E{\mathbb E} \def\O{\mathbb O} \def\U{\mathcal U} \def\pow{\mathcal P} \def\inv{^{-1}} \def\nrml{\triangleleft} \def\st{:} \def\~{\widetilde} \def\rem{\mathcal R} \def\sigalg{$\sigma$-algebra } \def\Gal{\mbox{Gal}} \def\iff{\leftrightarrow} \def\Iff{\Leftrightarrow} \def\land{\wedge} \def\And{\bigwedge} \def\entry{\entry} \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge} \def\Vee{\bigvee} \def\VVee{\d\Vee\mkern-18mu\Vee} \def\imp{\rightarrow} \def\Imp{\Rightarrow} \def\Fi{\Leftarrow} \def\var{\mbox{var}} \def\Th{\mbox{Th}} \def\entry{\entry} \def\sat{\mbox{Sat}} \def\con{\mbox{Con}} \def\iffmodels{\bmodels\models} \def\dbland{\bigwedge \!\!\bigwedge} \def\dom{\mbox{dom}} \def\rng{\mbox{range}} \def\isom{\cong} \DeclareMathOperator{\wgt}{wgt} \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}} \newcommand{\va}[1]{\vtx{above}{#1}} \newcommand{\vb}[1]{\vtx{below}{#1}} \newcommand{\vr}[1]{\vtx{right}{#1}} \newcommand{\vl}[1]{\vtx{left}{#1}} \renewcommand{\v}{\vtx{above}{}} \def\circleA{(-.5,0) circle (1)} \def\circleAlabel{(-1.5,.6) node[above]{$A$}} \def\circleB{(.5,0) circle (1)} \def\circleBlabel{(1.5,.6) node[above]{$B$}} \def\circleC{(0,-1) circle (1)} \def\circleClabel{(.5,-2) node[right]{$C$}} \def\twosetbox{(-2,-1.4) rectangle (2,1.4)} \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)} \def\ansfilename{practice-answers} \def\shadowprops{{fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}}} \newcommand{\hexbox}[3]{ \def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2} \def\y{-\r*#1-sin{30}*\r*#1} \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle; \draw (\x,\y) node{#3}; } \newcommand{\card}[1]{\left| #1 \right|} \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

SectionB.2Sets

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 a 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.

SubsectionB.2.1Notation

We need some notation to make talking about sets easier. Consider,

\begin{equation*} A = \{1, 2, 3\}. \end{equation*}

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:

\begin{equation*} a \in \{a, b, c\}. \end{equation*}

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\text{,}\) \(b\text{,}\) and \(c\text{.}\) Note that this is a true statement. It would also be true to say that \(d\) is not in that set:

\begin{equation*} d \not\in \{a, b, c\}. \end{equation*}

Be warned: we write “\(x \in A\)” when we wish to express that one of the elements of the set \(A\) is \(x\text{.}\) For example, consider the set,

\begin{equation*} A = \{1, b, \{x, y, z\}, \emptyset\}. \end{equation*}

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

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,

\begin{equation*} A = \{0, 2, 4, 6, \ldots\}, \end{equation*}

but this is a little imprecise. A better way would be

\begin{equation*} A = \{x \in \N \st \exists n\in \N ( x = 2 n)\}. \end{equation*}

Breaking that down: “\(x \in \N\)” means \(x\) is in the set \(\N\) (the set of natural numbers, \(\{0,1,2,\ldots\}\)), “\(:\)” is read “such that” and “\(\exists n\in \N (x = 2n) \)” is read “there exists an \(n\) in the natural numbers for which \(x\) is two times \(n\)” (in other words, \(x\) is even). Slightly easier might be,

\begin{equation*} A = \{x \st x\text{ is even} \}. \end{equation*}

Note: Sometimes people use \(|\) or \(\backepsilon\) for the “such that” symbol instead of the colon.

Defining a set using this sort of notation is very useful, although it takes some practice to read them correctly. It is a way to describe the set of all things that satisfy some condition (the condition is the logical statement after the “\(\st\)” symbol). Here are some more examples:

ExampleB.2.1

Describe each of the following sets both in words and by listing out enough elements to see the pattern.

  1. \(\{x \st x + 3 \in \N\}\text{.}\)
  2. \(\{x \in \N \st x + 3 \in \N\}\text{.}\)
  3. \(\{x \st x \in \N \vee -x \in \N\}\text{.}\)
  4. \(\{x \st x \in \N \wedge -x \in \N\}\text{.}\)
Solution
  1. This is the set of all numbers which are 3 less than a natural number (i.e., that if you add 3 to them, you get a natural number). The set could also be written as \(\{-3, -2, -1, 0, 1, 2, \ldots\}\) (note that 0 is a natural number, so \(-3\) is in this set because \(-3 + 3 = 0\)).

  2. This is the set of all natural numbers which are 3 less than a natural number. So here we just have \(\{0, 1, 2,3 \ldots\}\text{.}\)

  3. This is the set of all integers (positive and negative whole numbers, written \(\Z\)). In other words, \(\{\ldots, -2, -1, 0, 1, 2, \ldots\}\text{.}\)

  4. Here we want all numbers \(x\) such that \(x\) and \(-x\) are natural numbers. There is only one: 0. So we have the set \(\{0\}\text{.}\)

We already have a lot of notation, and there is more yet. Below is a handy chart of symbols. Some of these will be discussed in greater detail as we move forward.

Special sets
\(\emptyset\)

The empty set is the set which contains no elements.

\(\U\)

The universe set is the set of all elements.

\(\N\)

The set of natural numbers. That is, \(\N = \{0, 1, 2, 3\ldots\}\text{.}\)

\(\Z\)

The set of integers. That is, \(\Z = \{\ldots, -2, -1, 0, 1, 2, 3, \ldots\}\text{.}\)

\(\Q\)

The set of rational numbers.

\(\R\)

The set of real numbers.

\(\pow(A)\)

The power set of any set \(A\) is the set of all subsets of \(A\text{.}\)

Set Theory Notation
\(\{, \}\)

We use these braces to enclose the elements of a set. So \(\{1,2,3\}\) is the set containing 1, 2, and 3.

\(\st\)

\(\{x \st 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 \(A\) set-minus \(B\): the set containing all elements of \(A\) which are not elements of \(B\text{.}\)

\(\overline{A}\)

The complement of \(A\) is the set of everything which is not an element of \(A\text{.}\)

\(\card{A}\)

The cardinality (or size) of \(A\) is the number of elements in \(A\text{.}\)

Puzzle330
  1. Find the cardinality of each set below.

    1. \(A = \{3,4,\ldots, 15\}\text{.}\)
    2. \(B = \{n \in \N \st 2 \lt n \le 200\}\text{.}\)
    3. \(C = \{n \le 100 \st n \in \N \wedge \exists m \in \N (n = 2m+1)\}\text{.}\)
  2. Find two sets \(A\) and \(B\) for which \(|A| = 5\text{,}\) \(|B| = 6\text{,}\) and \(|A\cup B| = 9\text{.}\) What is \(|A \cap B|\text{?}\)

  3. Find sets \(A\) and \(B\) with \(|A| = |B|\) such that \(|A\cup B| = 7\) and \(|A \cap B| = 3\text{.}\) What is \(|A|\text{?}\)

  4. Let \(A = \{1,2,\ldots, 10\}\text{.}\) Define \(\mathcal{B}_2 = \{B \subseteq A \st |B| = 2\}\text{.}\) Find \(|\mathcal{B}_2|\text{.}\)

  5. For any sets \(A\) and \(B\text{,}\) define \(AB = \{ab \st a\in A \wedge b \in B\}\text{.}\) If \(A = \{1,2\}\) and \(B = \{2,3,4\}\text{,}\) what is \(|AB|\text{?}\) What is \(|A \times B|\text{?}\)

SubsectionB.2.2Relationships Between Sets

We have already said what it means for two sets to be equal: they have exactly the same elements. Thus, for example,

\begin{equation*} \{1, 2, 3\} = \{2, 1, 3\}. \end{equation*}

(Remember, the order the elements are written down in does not matter.) Also,

\begin{equation*} \{1, 2, 3\} = \{1, 1+1, 1+1+1\} = \{I, II, III\} \end{equation*}

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\}\text{?}\) Clearly \(A \ne B\text{,}\) 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\text{,}\) 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\text{,}\) in which case we use \(\subseteq\text{.}\) This is analogous to the difference between \(\lt\) and \(\le\text{.}\)

ExampleB.2.2

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.

  1. \(A \subset B\text{.}\)
  2. \(B \subset A\text{.}\)
  3. \(B \in C\text{.}\)
  4. \(\emptyset \in A\text{.}\)
  5. \(\emptyset \subset A\text{.}\)
  6. \(A \lt D\text{.}\)
  7. \(3 \in C\text{.}\)
  8. \(3 \subset C\text{.}\)
  9. \(\{3\} \subset C\text{.}\)
Solution
  1. False. For example, \(1\in A\) but \(1 \notin B\text{.}\)

  2. True. Every element in \(B\) is an element in \(A\text{.}\)

  3. False. The elements in \(C\) are 1, 2, and 3. The set \(B\) is not equal to 1, 2, or 3.

  4. False. \(A\) has exactly 6 elements, and none of them are the empty set.

  5. True. Everything in the empty set (nothing) is also an element of \(A\text{.}\) Notice that the empty set is a subset of every set.

  6. Meaningless. A set cannot be less than another set.

  7. True. \(3\) is one of the elements of the set \(C\text{.}\)

  8. Meaningless. \(3\) is not a set, so it cannot be a subset of another set.

  9. 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{.}\)

In the example above, \(B\) is a subset of \(A\text{.}\) You might wonder what other sets are subsets of \(A\text{.}\) If you collect all these subsets of \(A\) into a new set, we get a set of sets. We call the set of all subsets of \(A\) the power set of \(A\text{,}\) and write it \(\pow(A)\text{.}\)

ExampleB.2.3

Let \(A = \{1,2,3\}\text{.}\) Find \(\pow(A)\text{.}\)

Solution

\(\pow(A)\) is a set of sets, all of which are subsets of \(A\text{.}\) So

\begin{equation*} \pow(A) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1, 3\}, \{2,3\}, \{1,2,3\}\}. \end{equation*}

Notice that while \(2 \in A\text{,}\) it is wrong to write \(2 \in \pow(A)\) since none of the elements in \(\pow(A)\) are numbers! On the other hand, we do have \(\{2\} \in \pow(A)\) because \(\{2\} \subseteq A\text{.}\)

What does a subset of \(\pow(A)\) look like? Notice that \(\{2\} \not\subseteq \pow(A)\) because not everything in \(\{2\}\) is in \(\pow(A)\text{.}\) But we do have \(\{ \{2\} \} \subseteq \pow(A)\text{.}\) The only element of \(\{\{2\}\}\) is the set \(\{2\}\) which is also an element of \(\pow(A)\text{.}\) We could take the collection of all subsets of \(\pow(A)\) and call that \(\pow(\pow(A))\text{.}\) Or even the power set of that set of sets of sets.

Another way to compare sets is by their size. Notice that in the example above, \(A\) has 6 elements and \(B\text{,}\) \(C\text{,}\) and \(D\) all have 3 elements. The size of a set is called the set's cardinality . We would write \(|A| = 6\text{,}\) \(|B| = 3\text{,}\) and so on. For sets that have a finite number of elements, the cardinality of the set is simply the number of elements in the set. Note that the cardinality of \(\{ 1, 2, 3, 2, 1\}\) is 3. We do not count repeats (in fact, \(\{1, 2, 3, 2, 1\}\) is exactly the same set as \(\{1, 2, 3\}\)). There are sets with infinite cardinality, such as \(\N\text{,}\) the set of rational numbers (written \(\mathbb Q\)), the set of even natural numbers, and the set of real numbers (\(\mathbb R\)). It is possible to distinguish between different infinite cardinalities, but that is beyond the scope of this text. For us, a set will either be infinite, or finite; if it is finite, the we can determine its cardinality by counting elements.

ExampleB.2.4
  1. Find the cardinality of \(A = \{23, 24, \ldots, 37, 38\}\text{.}\)

  2. Find the cardinality of \(B = \{1, \{2, 3, 4\}, \emptyset\}\text{.}\)

  3. If \(C = \{1,2,3\}\text{,}\) what is the cardinality of \(\pow(C)\text{?}\)

Solution
  1. Since \(38 - 23 = 15\text{,}\) we can conclude that the cardinality of the set is \(|A| = 16\) (you need to add one since 23 is included).

  2. Here \(|B| = 3\text{.}\) The three elements are the number 1, the set \(\{2,3,4\}\text{,}\) and the empty set.

  3. We wrote out the elements of the power set \(\pow(C)\) above, and there are 8 elements (each of which is a set). So \(\card{\pow(C)} = 8\text{.}\) (You might wonder if there is a relationship between \(\card{A}\) and \(\card{\pow(A)}\) for all sets \(A\text{.}\) This is a good question which we will consider in Chapter 2.)

SubsectionB.2.3Operations On Sets

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,

\begin{equation*} C = A \cup B, \end{equation*}

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,

\begin{equation*} C = A \cap B \end{equation*}

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 \(\N\text{.}\) Sometimes we denote this universe by \(\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,

\begin{equation*} B = \overline A \end{equation*}

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 \(\overline A = \{1, 4, 6, 8, 9,10\}\text{.}\)

Of course we can perform more than one operation at a time. For example, consider

\begin{equation*} A \cap \overline B. \end{equation*}

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 :

\begin{equation*} A \cap \overline B = A \setminus B. \end{equation*}

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).

ExampleB.2.5

Let \(A = \{1, 2, 3, 4, 5, 6\}\text{,}\) \(B = \{2, 4, 6\}\text{,}\) \(C = \{1, 2, 3\}\) and \(D = \{7, 8, 9\}\text{.}\) If the universe is \(\U = \{1, 2, \ldots, 10\}\text{,}\) find:

  1. \(A \cup B\text{.}\)
  2. \(A \cap B\text{.}\)
  3. \(B \cap C\text{.}\)
  4. \(A \cap D\text{.}\)
  5. \(\overline{B \cup C}\text{.}\)
  6. \(A \setminus B\text{.}\)
  7. \((D \cap \overline C) \cup \overline{A \cap B}\text{.}\)
  8. \(\emptyset \cup C\text{.}\)
  9. \(\emptyset \cap C\text{.}\)
Solution
  1. \(A \cup B = \{1, 2, 3, 4, 5, 6\} = A\) since everything in \(B\) is already in \(A\text{.}\)
  2. \(A \cap B = \{2, 4, 6\} = B\) since everything in \(B\) is in \(A\text{.}\)
  3. \(B \cap C = \{2\}\) as the only element of both \(B\) and \(C\) is 2.
  4. \(A \cap D = \emptyset\) since \(A\) and \(D\) have no common elements.
  5. \(\overline{B \cup C} = \{5, 7, 8, 9, 10\}\text{.}\) First we find that \(B \cup C = \{1, 2, 3, 4, 6\}\text{,}\) then we take everything not in that set.
  6. \(A \setminus B = \{1, 3, 5\}\) since the elements 1, 3, and 5 are in \(A\) but not in \(B\text{.}\) This is the same as \(A \cap \overline B\text{.}\)
  7. \((D \cap \overline C) \cup \overline{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\}\)).
  8. \(\emptyset \cup C = C\) since nothing is added by the empty set.
  9. \(\emptyset \cap C = \emptyset\) since nothing can be both in a set and in the empty set.

You might notice that the symbols for union and intersection slightly resemble the logic symbols for “or” and “and.” This is no accident. What does it mean for \(x\) to be an element of \(A\cup B\text{?}\) It means that \(x\) is an element of \(A\) or \(x\) is an element of \(B\) (or both). That is,

\begin{equation*} x \in A \cup B \qquad \Iff \qquad x \in A \vee x \in B. \end{equation*}

Similarly,

\begin{equation*} x \in A \cap B \qquad \Iff \qquad x \in A \wedge x \in B. \end{equation*}

Also,

\begin{equation*} x \in \overline A \qquad \Iff \qquad \neg (x \in A). \end{equation*}

which says \(x\) is an element of the complement of \(A\) if \(x\) is not an element of \(A\text{.}\)

There is one more way to combine sets which will be useful for us: the Cartesian product, \(A \times B\). This sounds fancy but is nothing you haven't seen before. When you graph a function in calculus, you graph it in the Cartesian plane. This is the set of all ordered pairs of real numbers \((x,y)\text{.}\) We can do this for any pair of sets, not just the real numbers with themselves.

Put another way, \(A \times B = \{(a,b) \st a \in A \wedge b \in B\}\text{.}\) The first coordinate comes from the first set and the second coordinate comes from the second set. Sometimes we will want to take the Cartesian product of a set with itself, and this is fine: \(A \times A = \{(a,b) \st a, b \in A\}\) (we might also write \(A^2\) for this set). Notice that in \(A \times A\text{,}\) we still want all ordered pairs, not just the ones where the first and second coordinate are the same. We can also take products of 3 or more sets, getting ordered triples, or quadruples, and so on.

ExampleB.2.6

Let \(A = \{1,2\}\) and \(B = \{3,4,5\}\text{.}\) Find \(A \times B\) and \(A \times A\text{.}\) How many elements do you expect to be in \(B \times B\text{?}\)

Solution

\(A \times B = \{(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)\}\text{.}\)

\(A \times A = A^2 = \{(1,1), (1,2), (2,1), (2,2)\}\text{.}\)

\(|B\times B| = 9\text{.}\) There will be 3 pairs with first coordinate \(3\text{,}\) three more with first coordinate \(4\text{,}\) and a final three with first coordinate \(5\text{.}\)

SubsectionB.2.4Venn Diagrams

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 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 \overline B\text{,}\) or equivalently \(A \setminus B\text{:}\)

A more complicated example is \((B \cap C) \cup (C \cap \overline A)\text{,}\) 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\text{,}\) then excluded the region where \(C\) and \(A\) overlap outside of \(B\text{.}\) That region is \((A \cap C) \cap \overline B\text{.}\) So the above Venn diagram also represents \(C \cap \overline{\left((A\cap C)\cap \overline B\right)}.\) So using just the picture, we have determined that

\begin{equation*} (B \cap C) \cup (C \cap \overline A) = C \cap \overline{\left((A\cap C)\cap \overline B\right)}. \end{equation*}

SubsectionExercises

1

Let \(A = \{1,2,3,4,5\}\text{,}\) \(B = \{3,4,5,6,7\}\text{,}\) and \(C = \{2,3,5\}\text{.}\)

  1. Find \(A \cap B\text{.}\)

  2. Find \(A \cup B\text{.}\)

  3. Find \(A \setminus B\text{.}\)

  4. Find \(A \cap \overline{(B \cup C)}\text{.}\)

  5. Find \(A \times C\text{.}\)

  6. Is \(C \subseteq A\text{?}\) Explain.

  7. Is \(C \subseteq B\text{?}\) Explain.

2

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{.}\)

  1. Find \(A \cap B\text{.}\)

  2. Find \(A \cup B\text{.}\)

  3. Find \(B \cap C\text{.}\)

  4. Find \(B \cup C\text{.}\)

3

Find an example of sets \(A\) and \(B\) such that \(A\cap B = \{3, 5\}\) and \(A \cup B = \{2, 3, 5, 7, 8\}\text{.}\)

4

Find an example of sets \(A\) and \(B\) such that \(A \subseteq B\) and \(A \in B\text{.}\)

5

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.

  1. Is \(\Z^+ \subseteq 2\Z\text{?}\) Explain.

  2. Is \(2\Z \subseteq \Z^+\text{?}\) Explain.

  3. Find \(2\Z \cap 3\Z\text{.}\) Describe the set in words, and using set notation.

  4. Express \(\{x \in \Z \st \exists y\in \Z (x = 2y \vee x = 3y)\}\) as a union or intersection of two sets already described in this problem.

6

Let \(A_2\) be the set of all multiples of 2 except for \(2\text{.}\) Let \(A_3\) be the set of all multiples of 3 except for 3. And so on, so that \(A_n\) is the set of all multiple of \(n\) except for \(n\text{,}\) for any \(n \ge 2\text{.}\) Describe (in words) the set \(\overline{A_2 \cup A_3 \cup A_4 \cup \cdots}\text{.}\)

7

Draw a Venn diagram to represent each of the following:

  1. \(A \cup \overline B\)
  2. \(\overline{(A \cup B)}\)
  3. \(A \cap (B \cup C)\)
  4. \((A \cap B) \cup C\)
  5. \(\overline A \cap B \cap \overline C\)
  6. \((A \cup B) \setminus C\)
8

Describe a set in terms of \(A\) and \(B\) (using set notation) which has the following Venn diagram:

9

Find the following cardinalities:

  1. \(|A|\) when \(A = \{4,5,6,\ldots,37\}\)
  2. \(|A|\) when \(A = \{x \in \Z \st -2 \le x \le 100\}\)
  3. \(|A \cap B|\) when \(A = \{x \in \N \st x \le 20\}\) and \(B = \{x \in \N \st x \mbox{ is prime} \}\)
10

Let \(A = \{a, b, c, d\}\text{.}\) Find \(\pow(A)\text{.}\)

Hint

We are looking for a set containing 16 sets.

11

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?

12

Let \(A = \{1,2,3,4,5,6\}\text{.}\) Find all sets \(B \in \pow(A)\) which have the property \(\{2,3,5\} \subseteq B\text{.}\)

13

Find an example of sets \(A\) and \(B\) such that \(|A| = 4\text{,}\) \(|B| = 5\text{,}\) and \(|A \cup B| = 9\text{.}\)

14

Find an example of sets \(A\) and \(B\) such that \(|A| = 3\text{,}\) \(|B| = 4\text{,}\) and \(|A \cup B| = 5\text{.}\)

15

Are there sets \(A\) and \(B\) such that \(|A| = |B|\text{,}\) \(|A\cup B| = 10\text{,}\) and \(|A\cap B| = 5\text{?}\) Explain.

16

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.