- Last updated
- Save as PDF
- Page ID
- 23892
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\)
\( \newcommand{\vectorC}[1]{\textbf{#1}}\)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}}\)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}\)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)
3.2A. Sets and Their Elements
In mathematics, a set is a collection of objects. The objects in the collection are called “elements” (or “members”) of the set. If someone has a particular set in mind, they may wish to tell other people which set it is. One good way to do this is to list its elements. The list needs to be surrounded with curly braces (“\(\{\ \ \}\)”) to indicate that it represents a set, rather than some other type of object.
Other Terminology.
In mathematics, the term collection is a synonym for “set.”
Example \(3.2.1\).
- \(\{1, 2, 3, 4, 5\}\) is the set of natural numbers from \(1\) to \(5\).
- \(\{1,2,3,\ldots,100\}\) is the set of natural numbers from \(1\) to \(100\).
- \(\{\)♣, ♦, ♥, ♠\(\}\) is the set of suits in a standard deck of cards.
-
The set of provinces in Canada is \[\left\{\begin{array}{c}
\text { British Columbia, Alberta, Saskatchewan, Manitoba, } \\
\text { Ontario, Quebec, Newfoundland and Labrador, } \\
\text { New Brunswick, Prince Edward Island, Nova Scotia }
\end{array}\right\} .\]
Remark \(3.2.2\).
In everyday life, when you have a bunch of things that you want to keep together, you might look for a box to put them in. (The box itself probably has no value — you are interested only in the stuff that is in the box.) In mathematics, you should put the things into a set, not a box. If you think of a set as being a box of stuff, then the elements of the set are the things you see when you open the box.
Example \(3.2.3\).
- If \(A = \{1,2,3\}\), then the elements of \(A\) are the numbers \(1\), \(2\), and \(3\).
- If \(B=\{1,\{2,3\}\}\), then the elements of \(B\) are the number \(1\) and the set \(\{2,3\}\). It is important to note that the numbers \(2\) and \(3\) are not elements of \(B\).
-
To understand this, it may help to consider the analogy with boxes: if we open the box \(B\), we will see the number \(1\) and a box, but we will not see the number \(2\) or the number \(3\).
Contents of Box \(B\) (2 items):
the number "1"
a box of assorted numbers
We would need to open up the box that is inside of \(B\) in order to see those extra numbers. So \(2\) and \(3\) are not elements of the set \(B\) — they are elements of a set that is an element of \(B\). - As another illustration of this same phenomenon, suppose we make a list of the teams in a chess tournament. The list might be:
- U of Lethbridge,
- U of Alberta,
- U of Calgary.
And maybe the members of the Lethbridge team are Alice, Bob, and Cindy. Then Alice is not on the list of teams; she is a member of one of the teams on the list.
-
Notation \(3.2.4\).
We use
- “\(\in\)” as an abbreviation for “is an element of,” and
- “\(\notin\)” as an abbreviation for “is not an element of.”
For example, if \(A = \{1,2,3,4,5\}\), then we have \(3 \in A\) and \(7 \notin A\), because \(3\) is an element of \(A\), but \(7\) is not an element of \(A\).
Definition \(3.2.5\).
The set with no elements can be denoted \(\{\ \}\). (It is like an empty box.) It is called the empty set, and it comes up so often that is named by a special symbol: \[\varnothing \text { denotes the empty set. }\]
Remark \(3.2.6\).
Because the empty set has no elements, \[\text { for all } x \text {, we have } x \notin \varnothing \text {. }\]
Exercise \(3.2.7\).
Fill in each blank with \(\in\) or \(\notin\).
- \(\mathrm{t}_{-}\{\mathrm{t}, \mathrm{i}, \mathrm{m}, \mathrm{e}\}\)
- \(\mathrm{i}_{-}\{\mathrm{t}, \mathrm{i}, \mathrm{m}, \mathrm{e}\}\)
- \(\mathrm{m}_{-}\{\mathrm{t}, \mathrm{i}, \mathrm{m}, \mathrm{e}\}\)
- \(\{\mathrm{t}\}_{-}\{\mathrm{t}, \mathrm{i}, \mathrm{m}, \mathrm{e}\}\)
- \(\{\mathrm{i}\}_{-}\{\mathrm{t}, \mathrm{i}, \mathrm{m}, \mathrm{e}\}\)
- \(\{\mathrm{m}\}_{-}\{\mathrm{t}, \mathrm{i}, \mathrm{m}, \mathrm{e}\}\)
- \(\{\mathrm{t, i}\}_{-}\{\mathrm{t}, \mathrm{i}, \mathrm{m}, \mathrm{e}\}\)
- \(\{\mathrm{m, e}\}_{-}\{\mathrm{t}, \mathrm{i}, \mathrm{m}, \mathrm{e}\}\)
- \(\mathrm{t}_{-}\{\mathrm{t},\{\mathrm{i}\},\{\mathrm{m}, \mathrm{e}\}\}\)
- \(\mathrm{i}_{-}\{\mathrm{t},\{\mathrm{i}\},\{\mathrm{m}, \mathrm{e}\}\}\)
- \(\mathrm{m}_{-}\{\mathrm{t},\{\mathrm{i}\},\{\mathrm{m}, \mathrm{e}\}\}\)
- \(\{\mathrm{t}\}_{-}\{\mathrm{t},\{\mathrm{i}\},\{\mathrm{m}, \mathrm{e}\}\}\)
- \(\{\mathrm{i}\}_{-}\{\mathrm{t},\{\mathrm{i}\},\{\mathrm{m}, \mathrm{e}\}\}\)
- \(\{\mathrm{m}\}_{-}\{\mathrm{t},\{\mathrm{i}\},\{\mathrm{m}, \mathrm{e}\}\}\)
- \(\{\mathrm{t, i}\}_{-}\{\mathrm{t},\{\mathrm{i}\},\{\mathrm{m}, \mathrm{e}\}\}\)
- \(\{\mathrm{m, e}\}_{-}\{\mathrm{t},\{\mathrm{i}\},\{\mathrm{m}, \mathrm{e}\}\}\)
- \(\varnothing_{-}\varnothing\)
- \(\varnothing_{-}\{\varnothing\}\)
- \(\{\varnothing\}_{-}\varnothing\)
- \(\{\varnothing\}_{-}\{\varnothing\}\)
- \(\{\varnothing\}_{-}\{\{\varnothing\}\}\)
We said that a set is a collection of objects, but this needs a bit of elaboration:
- A set is determined by its elements. This means that there cannot be two different sets that have exactly the same elements. (Or, in other words, if two sets have the same elements, then the two sets are equal.) For example, suppose:
- \(H\) is the set of students who had a perfect score on last week’s history quiz,
- \(M\) is the set of students who had a perfect score on last week’s math quiz.
- \(\text { Alice and Bob }\) are the only two students who had a perfect score on last week’s history quiz, and
- \(\text { Alice and Bob }\) are also the only two students who had a perfect score on last week’s math quiz.
Then \(H\) and \(M\) have exactly the same elements, so \(H\) and \(M\) are just different names for the same set: namely, both represent \(\{\text { Alice, Bob \} }\). So the sets are equal: we have \(H = M\).
Suppose \(A\) and \(B\) are two sets.
We ahve \(A = B\) if and only if
for every \(x\), \(((x \in A) \Leftrightarrow(x \in B)) .\)
- A set is an unordered collection. This means that listing the elements of a set in a different order does not give a different set. For example, \(\{1,2,3\}\) and \(\{1,3,2\}\) are the same set. We write \(\{1,2,3\}=\{1,3,2\}\). Both of them are the set whose elements are \(1\), \(2\), and \(3\).
- A set is a collection without repetition. This means that repeating something in the list of elements does not change the set. For example, \(\{1,2,2,3,3\}\) is the same set as \(\{1,2,3\}\). We write \(\{1,2,2,3,3\}=\{1,2,3\}\).
Exercise \(3.2.8\).
Fill in the blank with \(=\) or \(\neq\).
- \(\{\mathrm{t}, \mathrm{i}, \mathrm{m}, \mathrm{e}\}_{\underline{ }}\{\mathrm{t}, \mathrm{m}, \mathrm{i}, \mathrm{e}\}\)
- \(\{\mathrm{t}, \mathrm{i}, \mathrm{m}\}_{\underline{ }}\{\mathrm{t}, \mathrm{m}, \mathrm{i}, \mathrm{e}\}\)
- \(\{\mathrm{t}, \mathrm{i}, \mathrm{m}\}_{\underline{ }}\{\mathrm{t}, \mathrm{m}, \mathrm{i}, \mathrm{m}\}\)
- \(\{\mathrm{t}, \mathrm{i}, \mathrm{m}\}_{\underline{ }}\{\mathrm{t}, \mathrm{m}, \mathrm{i}\}\)
- \(\{\mathrm{t}, \mathrm{i}, \mathrm{m}\}_{\underline{ }}\{\mathrm{t}, \mathrm{m}, \mathrm{i}, \mathrm{i}\}\)
- \(\{\mathrm{t}, \mathrm{i}, \mathrm{m}\}_{\underline{ }}\{\mathrm{t}, \mathrm{t}, \mathrm{t}, \mathrm{i}, \mathrm{i}, \mathrm{m}\}\)
- \(\{\mathrm{t}, \mathrm{t}\}_{\underline{ }}\{\mathrm{t}\}\)
- \(\{\mathrm{t}, \mathrm{t}\}_{\underline{ }}\{\mathrm{i}, \mathrm{i}\}\)
- \(\{\mathrm{t}, \mathrm{t}\}_{\underline{ }}\{\mathrm{t}, \mathrm{i}\}\)
Exercise \(3.2.9\).
Provide a 2-column proof of each deduction.
- \((a \in A) \Rightarrow(a \notin B), \quad(b \in B) \Rightarrow(a \in B), \quad \therefore(b \in B) \Rightarrow(a \notin A)\)
- \((p \in X) \&(q \in X), \quad(p \in X) \Rightarrow((q \notin X) \vee(Y=\varnothing)), \quad \therefore Y=\varnothing .\)
Exercise \(3.2.10\).
Write your proofs in English.
- Assume:
- If \(p \in H\) and \(q \in H\), then \(r \in H\).
- \(q \in H\).
Show that if \(p \in H\), then \(r \in H\).
- Assume:
- If \(X \neq \varnothing\), then \(a \in Y\).
- If \(X = \varnothing\), then \(b \in Y\).
- If either \(a \in Y\) or \(b \in Y\), then \(Y \neq \varnothing\).
Show \(Y \neq \varnothing\).
Notation \(3.2.11\).
It is traditional to use:
- capital letters (such as \(A,B,C, X,Y,Z\)) to represent sets, and
- lower-case letters (such as \(a,b,c,x,y,z\)) to represent numbers and other objects that are individual elements (or “atoms”), rather than sets.
Furthermore, it is a good idea to maintain a correspondence between the upper-case letters and lower-case letters: when feasible, use \(a\) to represent an element of \(A\) and \(b\) to represent an element of \(B\), for example.
Notation \(3.2.12\).
A few particularly important sets of numbers have been given names that every mathematician needs to know:
-
\(\mathbb{N} = \{0, 1, 2, ... \}\) is the set of natural numbers.
(Warning: Some textbooks do not consider \(0\) to be a natural number.) - \(\mathbb{N}^{+} = \{1, 2, ... \}\) is the set of positive natural numbers.
- \(\mathbb{Z} = \{\ldots, -3,-2,-1, 0, 1, 2,3,\ldots \}\) is the set of integers. A number is an integer if and only if it is either a natural number or the negative of a natural number.
-
\(\mathbb{Q}=\left\{\begin{array}{c|c}
p & p, q \in \mathbb{Z} \\
q \neq 0
\end{array}\right\}\) is the set of rational numbers. (This notation means that a number \(x\) is an element of \(\mathbb{Q}\) if and only if there exist integers \(p\) and \(q\), with \(q \neq 0\), such that \(x = p/q\) .) For example, \(1/2\), \(7/5\), and \(-32/9\) are elements of \(\mathbb{Q}\). - \(\mathbb{R}\) is the set of all real numbers. (That is, the set of all numbers that are either positive or negative or \(0\). Unless you have learned about “complex numbers” or “imaginary numbers,” it is probably the case that all the numbers you know are real numbers.) For example, \(\root 3 \of n\) is a real number whenever \(n \in \mathbb{Z}\); and \(\sqrt[3]{n}\) is a real number whenever \(n \in \mathbb{R}\). (“You can’t take the square root of a negative number.”)
Remark \(3.2.13\).
Sets are the most fundamental objects in mathematics. Indeed, modern mathematicians consider every object everywhere to be a set, but we will not be quite this extreme. Namely, in addition to sets, we will consider two additional types of objects: numbers and ordered pairs. (It is assumed that you already have a lot of experience with numbers, and know how to deal with them. You have probably also seen ordered pairs \((x,y)\), but their basic properties will be reviewed in Notation \(6.1.1\).) Functions are another very important class of mathematical objects, but, as will be seen in Section \(6.2\), we can think of them as being a particular type of set.
3.2B. Cardinality
Notation \(3.2.14\).
We use \(\#A\) to denote the number of elements in the set \(A\). (Thus, for example, \(\#\{\mathrm{a}, \mathrm{e}, \mathrm{i}, \mathrm{o}, \mathrm{u}\}=5\).) Mathematicians call \(\#A\) the cardinality of \(A\). This seemingly simple notion actually has some complicated implications, and will be discussed in more detail in Chapter \(9\).
Other Notation.
Many mathematicians use the notation \(|A|\) instead of \(\# A\).
Remark \(3.2.15\).
You probably already know that some sets are finite and some (such as \(\mathbb{N}\)) are infinite. We will discuss this in more detail in Chapter 9. For now, we remind you that a set \(A\) is finite iff the elements of \(A\) can be counted (and the answer is some number \(n\)); that is, if \(\#A = n\), for some \(n \in \mathbb{N}\).
Exercise \(3.2.16\).
What is the cardinality of each set? (You do not need to show your work.)
- \(\#\{\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}\}=\)
- \(\#\{\mathrm{a}, \mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{c}, \mathrm{d}\}=\)
- \(\#\{\mathrm{a},\{\mathrm{b}, \mathrm{c}\}\}=\)
- \(\#\{\mathrm{a}, \mathrm{a},\{\mathrm{b}, \mathrm{c}\},\{\mathrm{b}, \mathrm{c}, \mathrm{d}\}\}=\)
- \(\# \varnothing=\)
- \(\#\{\varnothing\}=\)
- Answer
-
Add texts here. Do not delete this text first.
See Also4.2: Subsets and Power Sets
3.2C. Subsets.
Geometry students are taught that every square is a rectangle. Translating this into the terms of set theory, we can say that if
- \(S\) is the set of all squares, and
- \(R\) is the set of all rectangles,
then every element of the set \(S\) is also an element of \(R\). For short, we say that \(S\) is a subset of \(R\), and we may write \(S \subset R\).
Definition \(3.2.17\).
Suppose \(A\) and \(B\) are two sets. We say that \(B\) is a subset of \(A\) iff every element of \(B\) is an element of \(A\).
When \(B\) is a subset of \(A\):
- In symbols, we write \(B \subset A\).
- We may say that \(B\) is contained in \(A\) or that \(A\) contains \(B\).
- We may also write \(A \supset B\) (and call \(A\) a superset of \(B\)).
Example \(\PageIndex{1}\)
- \(\{1,2,3\}\) is a subset of \(\{1,2,3,4\}\), because the elements of \(\{1,2,3\}\) are \(1\), \(2\), and \(3\), and every one of those numbers is an element of \(\{1,2,3,4\}\).
- \(\{1,3,5\}\) is not a subset of \(\{1,2,3,4\}\), because there is an element of \(\{1,3,5\}\) (namely, \(5\)) that is not an element of \(\{1,2,3,4\}\).
- We have \(\mathbb{N}^{+} \subset \mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}\).
Remark \(3.2.19\).
- We write \(B \not \subset A\) to denote that \(B\) is not a subset of \(A\).
- We have \(B \not \subset A\) iff there is at least one element of \(B\) that is not an element of \(A\).
Remark \(3.2.20\).
- In the language of everyday life, suppose someone gives you a box \(A\) that has some stuff in it. You are allowed to take some of the things from the box and put them into a new box \(B\). But you are not allowed to put anything into \(B\) if it was not in box \(A\). Then \(B\) will be a subset of \(A\).
- If you decide to take all of the things that were in box \(A\), then box \(B\) will end up being exactly the same as \(A\); that is \(B = A\). This illustrates the fact that every set is a subset of itself. \[\text { For every set } A \text {, we have } A \subset A \text {. }\]
- If you decide not to take anything at all from box \(A\), then box \(B\) will be empty. This illustrates the important fact that the empty set is a subset of every set. \[\text { For every set } A \text {, we have } \varnothing \subset A \text {. }\]
Definition \(3.2.21\).
Suppose \(A\) and \(B\) are sets. We say \(B\) is a proper subset of \(A\) iff \(B \subset A\) and \(B \neq A\).
Other Notation.
Many mathematicians use a slightly different notation: they define \(A \subset B\) to mean that \(A\) is a proper subset of \(B\). Then, to say that \(A\) is a subset of \(B\), they write \(A \subseteq B\).
Exercise \(3.2.22\).
Fill each blank with \(\subset\) or \(\notsubset\), as appropriate.
- \(\{\mathrm{s}\}_{\underline{ }}\{\mathrm{h}, \mathrm{o}, \mathrm{r}, \mathrm{n}, \mathrm{s}\}\)
- \(\{\mathrm{o, r}\}_{\underline{ }}\{\mathrm{h}, \mathrm{o}, \mathrm{r}, \mathrm{n}, \mathrm{s}\}\)
- \(\{\mathrm{n, o, r}\}_{\underline{ }}\{\mathrm{h}, \mathrm{o}, \mathrm{r}, \mathrm{n}, \mathrm{s}\}\)
- \(\{\mathrm{p, r, o, n, g}\}_{\underline{ }}\{\mathrm{h}, \mathrm{o}, \mathrm{r}, \mathrm{n}, \mathrm{s}\}\)
- \(\{\mathrm{s, h, o, r, n}\}_{\underline{ }}\{\mathrm{h}, \mathrm{o}, \mathrm{r}, \mathrm{n}, \mathrm{s}\}\)
- \(\varnothing_{\underline{ }}\{\mathrm{h}, \mathrm{o}, \mathrm{r}, \mathrm{n}, \mathrm{s}\}\)
- \(\{\varnothing\}_{\underline{ }}\{\mathrm{h}, \mathrm{o}, \mathrm{r}, \mathrm{n}, \mathrm{s}\}\)
- \(\{\mathrm{h}, \mathrm{o}, \mathrm{r}, \mathrm{n}, \mathrm{s}\}_{\underline{ }}\varnothing\)
It is intuitively clear that a subset of a set cannot have more elements than the original set. That is: \[\text { If } B \subset A, \text { then } \# B \leq \# A .\]
We will prove this fact in Exercise \(9.1.15(2)\).
In Example \(4.5.1\), we will prove that two sets are equal if and only if they are subsets of each other. This is a basic principle that will be very important in later chapters when we are doing proofs with sets: \[\text { To show two sets } A \text { and } B \text { are equal, prove } A \subset B \text { and } B \subset A \text {. }\]
Exercise \(3.2.23\).
Write a two-column proof to justify each assertion.
- \(X \subset Y \Rightarrow X \subset Z, X \subset Z \Rightarrow x \in Z, x \notin Z, \quad \therefore X \not \subset Y .\)
- \((x \in Y) \Rightarrow(X \subset Y),(x \in Y) \vee(Y \subset X), \quad \therefore(X \subset Y) \vee(Y \subset X) .\)
3.2D. Predicates.
The simplest predicates are things you can say about a single object; they are properties of individuals. For example, “\(x\) is a dog” and “\(x\) is a Harry Potter fan” are both predicates. In First-Order Logic, we symbolize predicates with capital letters \(A\) through \(Z\) (with or without subscripts). Thus, our symbolization key might include:
\(D(x)\): \(x\) is a dog.
\(H(x)\): \(x\) is a Harry Potter fan.
Predicates like these are called one-place or unary, because there is only one variable. Assigning a value to this variable yields an assertion. For example, letting \(x\) = “Lassie” in the first predicate yields the assertion “Lassie is a dog.” Note that in translating English assertions, the variable will not always come at the beginning of the assertion: “the Louvre owns at least one watercolour painted by \(x\)” is also a predicate.
Other predicates are about the relation between two things. For instance, in algebra, we have the relations “\(x\) is equal to \(y\),” symbolized as \(x = y\), and “\(x\) is greater than \(y\),” symbolized as \(x > y\). These are two-place or binary predicates, because values need to be assigned to two variables in order to make an assertion. Our symbolization key might include:
\(x\) \(F\) \(y\): \(x\) is a friend of \(y\).
\(x\) \(L\) \(y\): \(x\) is to the left of \(y\).
\(x\) \(M\) \(y\): \(x\) owes money to \(y\).
In general, we can have predicates with as many variables as we need. Predicates with \(n\) variables, for some number \(n\), are called \(n\)-place or \(n\)-ary. However, in practice, predicates almost always have only one or two variables.
A symbolization key may also include constants (that is, the names of specific objects). For example, we might have a symbolization key that looks like this:
\(H(x)\): \(x\) to is happy.
\(S(x)\): \(x\) to is singing.
\(x\) \(T\) \(y\): \(x\) is to teaching \(y\).
\(g\): Greg
\(m\): Mary
\(v\): Vikki
This allows us to symbolize assertions that use any combination of these predicates and terms. For example:
assertion | symbolization |
---|---|
Greg is happy. | \(H(g)\) |
If Mary is singing, then Vikki is happy. | \(S(m) \Rightarrow H(v)\) |
Greg and Mary are singing. | \(S(g) \& S(m)\) |
If either Greg or Mary is singing, then Vikki is not happy. | \((S(g) \vee S(m)) \Rightarrow \neg H(v)\) |
Mary is teaching Greg. | \(m \mathrel{T} g\) |
Mary is not teaching Vikki. | \(\neg( m \mathrel{T} v)\) |
Vikki is teaching either Mary or Greg. | \((v \mathrel{T} m) \vee (v \mathrel{T} g)\) |
If Mary is teaching Greg, then Mary and Vikki are happy. | \((m \mathrel{T} g) \Rightarrow \bigl( H(m) \& H(v) \bigr)\) |
Either Vikki is not singing, or she is not teaching Mary. | \(\bigl( \neg S(v) \bigr) \vee \neg (v \mathrel{T} m)\) |
If Mary is singing, then Greg is not teaching Vikki. | \(S(m) \Rightarrow \neg (g \mathrel{T} v )\) |
Warning.
Whenever you have a predicate with two (or more) variables, it is important to be careful about the order in which the variables occur. (For example, saying \(x < y\) is certainly not the same as saying \(y < x\).) Some special choices of predicates are “symmetric,” which means that if the predicate is true with variables in one order, then it is true for the same variables in a different order, but this should never be assumed. The order of the variables should always represent exactly what we know.
Exercise \(3.2.24\).
Using the same symbolization key, write these English assertions using predicates and logical connectives.
\(x\) \(O\) \(y\): \(x\) is older than \(y\).
\(x\) \(F\) \(y\): \(x\) is a friend of \(y\).
\(S\): the set of all students.
\(r\): Roger
\(s\): Sam
\(t\): Tess
- \(r\) \(O\) \(s\)
- \(t\) \(O\) \(s\)
- (\(r\) \(F\) \(t\)) \(\Rightarrow(t \in S)\)
- \(((s \in S) \&(r \in S)) \Rightarrow\) (\(s\) \(F\) \(r\))
- \((t \in S) \vee\) (\(r\) \(O\) \(t\))
- (\(r\) \(F\) \(s\)) \(\Leftrightarrow(t \notin S)\)
Exercise \(3.2.25\).
Using the same symbolizaiton key, write these English assertions using predicates and logical connectives.
- Tess is older than Roger.
- Roger is a friend of Sam.
- If Tess is a student then Tess is a friend of Sam.
- Either Sam is a student, or Roger is not a student.
- If Roger is a friend of Sam, then Sam is a student.
- Sam is older than Roger if and only if Roger is a student.
- If Sam and Roger both are students, then Sam is not a friend of Roger.
Exercise \(3.2.26\).
Using the same symbolization key, write a two-column proof to justify each of the following deductions.
- \((r \in S) \Rightarrow((r O s) \vee(r \notin S)), \quad \therefore((t \in S) \& \neg(r O s)) \Rightarrow(r \notin S)\)
- If either Roger is a student, or Tess is not a student, then Sam is older than Tess.
If Tess is a student, then Roger is also a student.
\(\therefore\) Sam is older than Tess.
3.2E. Using Predicates to Specify Subsets.
Subsets arise in everyday life whenever you want only part of something. For example, suppose you are in a kitchen with a lot of plates. If you are washing dishes, then you do not want to be given all of the plates, but only the ones that are dirty. In mathematical terms, you do not want the set of all plates, but only want a subset, those that are dirty. That is, if \(P\) represents the set of all plates, and \(D\) represents the set of all dirty plates, then \(D \subset P\).
This type of situation is handled by the following useful notation:
Suppose \(A\) is a set and \(P(x)\) is a predicate.
Then \(\{a \in A \mid P(a)\}\) denotes
the set of all elements \(a\) of \(A\), such that \(P(a)\) is true.
It is a subset of \(A\).
In the example above, you are interested in the subset \[\{p \in P \mid p \text { is dirty }\} ,\]
because this is the set of plates that are dirty. The notation tells us to look through all of the plates in \(P\), and check each one to see whether it is dirty. If it is, we put it in the subset. If it is not dirty, then we do not put it in the subset.
Example \(3.2.27\).
- Suppose \(B=\{1,2,3, \ldots, 10\}\). Then:
- \(\{b \in B \mid b \text { is odd }\}=\{1,3,5,7,9\}\).
- \(\{b \in B \mid b \text { is even }\}=\{2,4,6,8,10\}\).
- \(\{b \in B \mid b \text { is prime }\}=\{2,3,5,7\}\).
- \(\left\{b \in B \mid b^{2}-1 \text { is divisible by } 3\right\}=\{1,2,4,5,7,8,10\} \text {. }\)
- \(\left\{b \in B \mid(b-5)^{2}>4\right\}=\{1,2,8,9,10\}\).
- \(\{b \in B \mid 3 \leq b \leq 8 \text { and } b \text { is even }\}=\{4,6,8\} \text {. }\).
- For any \(n \in \mathbb{N}\), we have \(\{i \in \mathbb{N} \mid 1 \leq i \leq n\}=\{1,2,3, \ldots, n\}\).
Exercise \(\PageIndex{1}\)
Let \(A = \{1,2,3,4,5\}\) and \(B = \{1,3,5,7,9\}\). Specify each set by listing its elements.
- \(\{a \in A \mid a \text { is even }\}=\)
- \(\{b \in B \mid b \text { is even }\}=\)
- \(\{a \in A \mid a \text { is odd }\}=\)
- \(\{b \in B \mid b \text { is odd }\}=\)
- \(\{a \in A \mid a<4\}=\)
- \(\{b \in B \mid b<4\}=\)
- \(\left\{a \in A \mid(a-3)^{2}=9\right\}=\)
- \(\left\{b \in B \mid(b-3)^{2}=9\right\}=\)
- \(\{a \in A \mid a \in B\}=\)
- \(\{b \in B \mid b \in A\}=\)
- \(\{a \in A \mid a \notin B\}=\)
- \(\{b \in B \mid b \notin A\}=\)
- \(\{a \in A \mid 2 a \in B\}=\)
- \(\{b \in B \mid 2 b \in A\}=\)
- \(\left\{a \in A \mid a^{2} \in B\right\}=\)
- \(\left\{a \in A \mid a^{2}<0\right\}=\)
Students of mathematics are expected to be able to prove assertions about sets and their subsets. Before giving an example of this, let us point out that if \(A\) is a set, \(P(x)\) is a predicate, and \[B = \{\, a \in A \mid P(a) \,\} ,\]
then the assertion “\(b \in B\)” is logically equivalent to the assertion “\((b \in A) \& P(b)\).” Thus, in a proof:
- if the assertion \(b \in B\) is known to be true, then we also know that \(b \in A\) and \(P(b)\) are also true; and
- if the assertions \(b \in A\) and \(P(b)\) are both known to be true, then we also know that \(b \in B\) is true.
In a \(2\)-column proof, the justification for these assertions is “definition of \(B\)” or “because \(B = \{\, a \in A \mid P(a) \,\}\).”
Of course, not all sets are called \(A\) and \(B\), but the same principles hold for sets named with other letters.
Example \(3.2.29\).
Suppose \(X\) and \(Y\) are sets, and let \(Z = \{\, y \in Y \mid y \notin X \,\}\). Show that if \(z \in Z\), then \(z \notin X\).
Solution
Assume \(z \in Z\). Then, from the definition of \(Z\), we know \(z \in Y\) and \(z \notin X\). In particular, \(z \notin X\), as desired.
Exercise \(3.2.30\).
- Assume \(A=\{d \in D \mid d \text { is hungry }\} .\)
- If we know that \(p \in A\), then what do we know about \(p\)?
- If we want to prove that \(q \in A\), then what do we need to show?
- Assume \(f(x) = x^{2}\) and \(K=\{y \in \mathbb{R} \mid f(y)>2\}\).
- If we know that \(s \in K\), then what do we know about \(s\)?
- If we want to prove that \(t \in K\), then what do we need to show?
- Assume \(G=\{i \in I \mid M(i)\}\), where \(M(x)\) is a predicate.
- If we know that \(v \in G\), then what do we know about \(v\)?
- If we want to prove that \(w \in G\), then what do we need to show?
Exercise \(3.2.31\).
Write your proofs in English.
- Assume \(A\) and \(B\) are sets, and let \(C = \{\, a \in A \mid a \in B\,\}\). Show that if \(c \in C\), then \(c \in B\).
- Let \(A = \{\, x \in \mathbb{R} \mid x^2 - 5x = 14\,\}\). Show that if \(a \in A\), then \(a < 10\).
Notation \(3.2.32\).
When talking about sets or using predicates, we usually assume that a “universe of discourse” \(\mathcal{U}\) has been agreed on. This means that all the elements of all of the sets under discussion are assumed to be members of \(\mathcal{U}\). Then \[\{x \mid P(x)\}\]
can be used as an abbreviation for \(\{\, x \in \mathcal{U} \mid P(x) \,\}\).
The universe of discourse is sometimes assumed to be understood from the context, but it is an important concept, and it is best to specify it so that there is no room for confusion. For example, if we say “Everyone is happy,” who is included in this everyone? We usually do not mean everyone now alive on the Earth. We certainly do not mean everyone who was ever alive or who will ever live. We mean something more modest: perhaps we mean everyone in the building, or everyone in the class, or maybe we mean everyone in the room.
Specifying a universe of discourse eliminates this ambiguity. The \(\mathcal{U}\) is the set of things that we are talking about. So if we want to talk about people in Lethbridge, we define to be the set of all people in Lethbridge. We write this at the beginning of our symbolization key, like this:
\(\mathcal{U}\): the set of all people in Lethbridge
Everything that follows ranges over the universe of discourse. Given this \(\mathcal{U}\), “everyone” means “everyone in Lethbridge” and “someone” means “someone in Lethbridge.”
Each constant names some member of \(\mathcal{U}\), so, if \(\mathcal{U}\) is the set of people in Lethbridge, then constants Donald, Greg, and Mary can only be used if these three people are all in Lethbridge. If we want to talk about people in places besides Lethbridge, then we need to specify a different universe of discourse.
Example \(3.2.33\).
If \(\mathcal{U}\) is the set of all Canadian provinces, then \[\{x \mid \text { the English name of } x \text { has three syllables }\}=\{\text { Alberta, New Brunswick }\} \text {. }\]
Remark \(3.2.34\).
There is a very close relationship between sets and unary predicates. In general:
- From any unary predicate \(P(x)\), we can define the set \[\{x \mid P(x)\} .\]
- Conversely, from any set \(A\), we can define a unary predicate \(P(x)\) to be “\(x\) is a member of \(A\).”
Because of this, sets are more-or-less interchangeable with unary predicates. For example, the predicate “\(x\) is a dog” can be symbolized in two quite different ways:
- Our symbolization key could state that \(D(x)\) means “\(x\) is a dog.”
- Alternatively, our symbolization key could let \(D\) be the set of all dogs. Then “\(x\) is a dog” would be translated as “\(x \in D\).”
Mathematicians use sets much more often than unary predicates. We will see in Remark \(4.2.1.\) that this tends to make it easier to translate statements from English into First-Order Logic when quantifiers are involved.