\(\newcommand{\newpara}{}
\newcommand{\nats}{\mathbb{N}}
\newcommand{\subcountawry}{\bf{When\ Counting\ Goes\ Awry}}
\newcommand{\seccountingstepscases}{\bf{Counting\ with\ Steps\ and\ Cases}}
\newcommand{\subalgfac}{\bf{Algebra:\ Factorials}}
\newcommand{\seccountingsubsets}{\bf{Counting\ Subsets}}
\newcommand{\secbitstrings}{\bf{Counting\ Bit\ Strings}}
\newcommand{\subhs}{Counting Handshakes}
\newcommand{\circled}[1]{\tikz[baseline=(char.base)]{\node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\newcommand{\xcircle}[1]{\circled{#1}}
\newcommand{\subdiscrete}{What is Discrete Mathematics?}
\newcommand{\sublearning}{Learning Discrete Mathematics}
\newcommand{\exerR}{Recap}
\newcommand{\subcountingawry}{When Counting Goes Awry}
\newcommand{\exerP}{Practice}
\newcommand{\subfactorials}{Algebra: Factorials}
\newcommand{\exerU}{Understand}
\newcommand{\subsubsetschoose}{Subsets and the Binomial Coefficients}
\newcommand{\exerE}{Explore}
\newcommand{\subcombinecount}{Combining Counting Techniques}
\newcommand{\subproofscountnosums}{Proof Format: Combinatorial Proof}
\newcommand{\subbitstrings}{Bit Strings}
\newcommand{\subcountbitstrings}{Number of Bit Strings}
\newcommand{\subrephrasingsubset}{Detour: Rephrasing the Question}
\newcommand{\subexplog}{Algebra: Exponential Notation and Logarithms}
\newcommand{\subbridges}{Crossing Bridges}
\newcommand{\subdefngraph}{The Definition of a Graph}
\newcommand{\subgraphcomp}{Graph Complements}
\newcommand{\subdegseq}{Degree Sequences}
\newcommand{\substdgraphs}{Standard Graphs}
\newcommand{\subadjmat}{The Adjacency Matrix of a Graph}
\newcommand{\subcolormaps}{Coloring Maps}
\newcommand{\subchromatic}{Coloring Graphs}
\newcommand{\subgraphconj}{Graph Conjectures}
\newcommand{\subplanarity}{Planarity}
\newcommand{\subisograph}{Isomorphic Graphs}
\newcommand{\subgraphtrees}{Subgraphs and Trees}
\newcommand{\subnonisograph}{Nonisomorphic Graphs}
\newcommand{\subgraphclassification}{Graph Classification}
\newcommand{\subrobots}{Detour: Robots}
\newcommand{\sublockers}{Opening and Closing Lockers}
\newcommand{\subevenodd}{Even and Odd Integers}
\newcommand{\subdivides}{Divisibility}
\newcommand{\subfractions}{Algebra: Equivalent Fractions}
\newcommand{\subdivalg}{The Division Algorithm, \fn{div}, and \fn{mod}}
\newcommand{\subpolys}{Algebra: Polynomials}
\newcommand{\subpffcases}{Proof Format: Proof by Cases}
\newcommand{\subnotlast}{Not Last Game}
\newcommand{\submod}{The Mod Clock}
\newcommand{\subzn}{The Integers mod $n$}
\newcommand{\subprimes}{Primes and Composites}
\newcommand{\subprimefact}{Prime Factorization}
\newcommand{\subcountdiv}{Detour: Listing and Counting Divisors}
\newcommand{\subgcd}{Greatest Common Divisor}
\newcommand{\subea}{The Euclidean Algorithm}
\newcommand{\subcoprime}{Coprime Integers}
\newcommand{\subandor}{And and Or}
\newcommand{\subpffandor}{Proof Formats: $\land$ and $\lor$ by Cases}
\newcommand{\subequivneg}{Logical Equivalence and Negations}
\newcommand{\subpffcontra}{Proof Format: Contradiction}
\newcommand{\subsetgame}{The Game SET}
\newcommand{\subquant}{Quantifiers}
\newcommand{\subpffquants}{Proof Formats: $\forall$ and $\exists$}
\newcommand{\subcex}{Negating Quantified Statements and Counterexamples}
\newcommand{\subifthen}{Promises: Conditional Statements}
\newcommand{\subpffifthen}{Proof Format: Direct Proof of $\to$}
\newcommand{\subnegcond}{Broken Promises: Negating Conditional Statements}
\newcommand{\subpfforimplication}{Proof Formats: Proof of $\lor$ Using Implication}
\newcommand{\subconv}{The Converse and Biconditional Statements}
\newcommand{\subpffiff}{Proof Format: $\leftrightarrow$}
\newcommand{\subcp}{The Contrapositive}
\newcommand{\subpffcp}{Proof Format: $\to$ Using the Contrapositive}
\newcommand{\subequiv}{Logical Equivalence}
\newcommand{\subneg}{Simplifying Negations}
\newcommand{\subinference}{Logical Inference}
\newcommand{\subinfsetsnumbers}{Infinite sets of numbers}
\newcommand{\subdefnfnnotation}{Function Notation and Vocabulary}
\newcommand{\subpiecewise}{Piecewise-defined Functions}
\newcommand{\subfndotgraphs}{Dot Diagrams and Graphs of Functions}
\newcommand{\subfloorceiling}{Floor and Ceiling}
\newcommand{\subnumberfn}{Number-theoretic Functions}
\newcommand{\subfngraphs}{Graph-theoretic Functions}
\newcommand{\subbitstringfunctions}{Functions Involving Bit Strings}
\newcommand{\suborderedpair}{Ordered Pairs and the Definition of Function}
\newcommand{\subpairing}{Pairings}
\newcommand{\subonetooneonto}{One-to-one and Onto}
\newcommand{\subperms}{Permutations}
\newcommand{\subinverses}{Inverse Functions}
\newcommand{\subpffunique}{Proof Format: Uniqueness}
\newcommand{\subdefnseq}{The Definition of Sequence}
\newcommand{\submodelseq}{Modeling with Explicitly-defined Sequences}
\newcommand{\subseqprimes}{Detour: Sequences Involving Primes}
\newcommand{\subelements}{Elements of a Set}
\newcommand{\subsetbuild}{Set-Builder Notation}
\newcommand{\subsetops}{Set Operations}
\newcommand{\subsubsets}{Subsets of a Set}
\newcommand{\subbsrepsubset}{Bit String Representation of Subsets}
\newcommand{\subsetsofsets}{Sets of Sets}
\newcommand{\subsetfn}{Detour: Set-theoretic Functions}
\newcommand{\subdefnpartition}{The Definition of Partition}
\newcommand{\subselfconj}{Conjugate Partitions}
\newcommand{\subbulgsol}{Collecting Coins}
\newcommand{\subcartprod}{The Cartesian Product of Sets}
\newcommand{\subfncartprod}{Functions Involving Cartesian Products}
\newcommand{\subdefnrelation}{Relations and Their Representations}
\newcommand{\subrelppty}{Properties of Relations}
\newcommand{\subequivclass}{Equivalence Relations and Equivalence Classes}
\newcommand{\subcongmod}{Congruence mod $n$}
\newcommand{\subhanoi}{The Towers of Hanoi}
\newcommand{\subrecdefseq}{Recursively-defined Sequences}
\newcommand{\subntr}{Modeling with Recursively-defined Sequences}
\newcommand{\subpffmathind}{Proof Format: Mathematical Induction}
\newcommand{\subalgind}{Algebra: Evaluating $f(n-1)$}
\newcommand{\subpffindseq}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Rule for a Recursively-defined Sequence}
\newcommand{\submatpowers}{Matrix Products and Powers}
\newcommand{\subpffindmatrix}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Formula for the Power of a Matrix}
\newcommand{\subgroups}{Finite Groups}
\newcommand{\subproperbs}{Proper Bit Strings}
\newcommand{\subrecsets}{Recursively-defined Sets}
\newcommand{\subrecgraphs}{Recursively-defined Graphs}
\newcommand{\subfib}{The Fibonacci Sequence and Higher Order Recursions}
\newcommand{\submodelhigher}{Modeling with Higher Order Recursions}
\newcommand{\subfibpatterns}{Detour: Fibonacci Patterns and Proof}
\newcommand{\subpffstrongind}{Proof Format: Strong Mathematical Induction}
\newcommand{\subhowmanysq}{Counting Squares}
\newcommand{\subfactrep}{Factorial Representations}
\newcommand{\subsigmapi}{Sum and Product Notation}
\newcommand{\subbaseb}{Base $b$ Representation}
\newcommand{\subbinary}{Binary Representation}
\newcommand{\subhex}{Hexadecimal Representation}
\newcommand{\subhexforbinary}{Hex as a Shorthand for Binary}
\newcommand{\subsumconj}{Sum Conjectures}
\newcommand{\subprodconj}{Product Conjectures}
\newcommand{\subsumfib}{Detour: Fibonacci Sums}
\newcommand{\subfactorpolys}{Algebra: Factoring Polynomials}
\newcommand{\subarithtri}{The Arithmetic Triangle}
\newcommand{\subpascalpatterns}{Patterns in the Arithmetic Triangle}
\newcommand{\subbinomthm}{The Binomial Theorem}
\newcommand{\subfactorialbinom}{Explicit Formula for Binomial Coefficients}
\newcommand{\subpffsumproofsind}{Proof Format: Special Case of Mathematical Induction for Proving Sum and Product Formulas}
\newcommand{\subpffcombsums}{Proof Format: Combinatorial Proof of Sums}
\newcommand{\subspecialsum}{Detour: Special Sums}
\newcommand{\subfracalg}{Algebra: Fraction Arithmetic}
\newcommand{\subhotelinf}{Hotel Infinity}
\newcommand{\subdefndiscrete}{The Definition of Discrete}
\newcommand{\seclisting}{Organized Listing}
\newcommand{\vocab}{\textbf}
\newcommand{\str}{\texttt}
\newcommand{\fn}{\texttt}
\newcommand{\bs}{\texttt}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section7.1Sets
We have been using the idea of sets throughout this course. In this section, we discuss sets more formally, including how to define sets using set-builder notation. We also explore ways to combine sets through set operations, which have applications to working with databases.
As in Section 2.1, a set is understood to be an unordered collection of objects called elements. There is a lot of vocabulary related to sets. We start with definitions related to the elements of a set.
If the object \(x\) is an element of the set \(S\text{,}\) then we use element notation and write \(x \in S\text{.}\) If \(x\) is not an element of \(S\text{,}\) then we write \(x \notin S\text{.}\) For example, if \(S=\{1,3,4\}\text{,}\) then \(3 \in S\) and then \(2 \notin S\text{.}\)
An ellipsis is \(\ldots\) which is used to indicate missing items that follow a pattern. For an infinite set described using ellipses we need to recognize the pattern to know if an object is an element. For example, the set \(F = \{4,8,12,\ldots, 64\}\) is the set of multiples of 4 from 4 to 64. Thus, \(20 \in F\) because \(4 \mid 20\) and \(4 \le 20 \le 64\text{.}\) On the other hand, \(18 \notin F\) because \(4 \nmid 18\) and \(80 \notin F\) because \(80 >64\text{.}\) We see a more rigorous way to define such sets in Subsection 7.1.B.
The cardinality of a finite set \(S\text{,}\) denoted \(|S|\text{,}\) is the number of (distinct) elements in \(S\text{.}\) For example, \(|\{1,3,4\}|=3\) because there are three elements in \(\{1,3,4\}\) namely 1, 3, and 4.
Is \(\bs{110} \in \mathbb{B}_3\text{?}\) Is \(\bs{0111}\in \mathbb{B}_3\text{?}\)Solution.
Since \(\bs{110}\) is a bit string of length three and appears on the list of elements of \(\mathbb{B}_3\text{,}\) we have \(\bs{110} \in \mathbb{B}_3\text{.}\) Since \(\bs{0111}\) is a bit string of length 4 and does not appear on the list of elements of \(\mathbb{B}_3\text{,}\) we see that \(\bs{0111} \notin \mathbb{B}_3\text{.}\)
We can count the elements of \(\mathbb{B}_3\text{.}\) There are 8 elements listed so \(|\mathbb{B}_3|=8\text{.}\) Note that by Theorem 2.4.8, we knew there were \(2^3=8\) bit strings of length three so, again, \(|\mathbb{B}_3|=8\text{.}\)
Sets \(S\) and \(T\) are equal if they have the exact same set of elements. For example, \(\{1,3,4\}=\{4,4,3,1\}\) because each set has the same three elements: 1, 3, and 4.
At the other extreme, \(S\) and \(T\) are disjoint if they do not have any elements in common. For example, \(\{1,3,4\}\) and \(\{2,7\}\) are disjoint.
Consider the set \(A = \{0,3,5,6\}\text{.}\) Is \(0 \in A\text{?}\) Is \(1 \in A\text{?}\) Calculate \(|A|\text{,}\) the number of elements in \(A\text{.}\)
Give an example of a set of integers \(Y\) that is disjoint from \(A\text{.}\) By Definition 7.1.3, that means find a set \(Y\) that has no elements in common with \(A\text{.}\)
There are many ways to describe a set. We can explicitly list some of the elements of a known set, such as \(\mathbb{Z}\) or \(\mathbb{R}\text{,}\) perhaps using an ellipsis (\(\ldots\)) if the list is long. Alternatively, we can select the elements of a known set that satisfy some implicit condition or build elements of an explicit format from the elements of a known set.
A predicate (or Boolean) is a statement that is true or false.
\(P(x)\) defined for all elements \(x \in S\text{,}\) the set
\begin{equation*}
A=\{ x \in S \mid P(x)\}\text{,}
\end{equation*}
pronounced “the set of all elements \(x\) in \(S\) such that \(P(x)\)”, is the set of all elements \(x\) of \(S\) that satisfy implicit condition \(P(x)\text{.}\) Note that \(A\) is a subset of \(S\text{.}\) For example, if \(S=\{1,2,3,7,8\}\) and \(P(n)\) is the statement “\(n\) is even”, then
\begin{equation*}
A = \{ n \in S \mid P(n)\} = \{ n \in A \mid n \text{ is even } \}= \{2,8\}\text{.}
\end{equation*}
For example, \(2 \in A\) because 2 is even but \(3 \notin S\) because 3 is not even.
Given a set \(S\) and a function \(f\) where \(f(x)\) is defined for all \(x \in S\text{,}\) the set
\begin{equation*}
A=\{ f(x) \mid x \in S\}\text{,}
\end{equation*}
pronounced “the set of all elements of the form \(f(x)\) where \(x\) in an element of \(S\)”, is the set of all elements of the explicit format \(f(x)\) where \(x\in S\text{.}\) For example, if \(S=\{1,2,3,7,8\}\) and \(f(n)=n^3\text{,}\) then
\begin{equation*}
A = \{ n^3 \mid n \in S\} = \{1^3,2^3,3^3,7^3,8^3\}= \{1, 8, 27, 343, 512\}\text{.}
\end{equation*}
To show \(343 \in A\) we write \(343=7^3\text{.}\) Note that \(A\) need not be a subset of \(S\text{.}\) It is just built using the set \(S\text{.}\)
The sets \(\{ x \in S \mid P(x)\}\) and \(\{ f(x) \mid x \in S\}\) are described in set-builder notation because the notation tells us how to build the set.
In Definition 7.1.1, we saw the set \(F = \{4,8,12,\ldots, 64\}\) which represents the set of multiples of 4 from 4 to 64. Use set-builder notation to define \(F\text{.}\)
Example7.1.8Listing elements of implicit and explicitly-defined sets of bit strings.
As usual, let \(\mathbb{B}_3\) denote the set of all bit strings of length three.
List all elements of the implicitly-defined set
\begin{equation*}
A= \{b \in \mathbb{B}_3 \mid b \text{ has weight two } \}\text{.}
\end{equation*}
Recall from Definition 2.4.1 that the weight of a bit string is the number of \(\bs{1}\) s in the bit string.
Solution.
There are bit strings of length three and weight two are: \(\bs{011}\text{,}\)\(\bs{101}\text{,}\) and \(\bs{110}\) and so \(A = \{\bs{011}, \bs{101}, \bs{110}\}\text{.}\)
Show that \(16 \in Q\) and \(16 \in P\text{.}\)Solution.
To show \(16 \in Q\) we need to write 16 as a square, that is \(16=n^2\) for some \(n \in \mathbb{N}\text{.}\) We can write \(16=4^2\) and so \(16 \in Q\text{.}\)
Similarly, to show \(16 \in P\) we need to write 16 as a power of two, that is \(16=2^n\) for some \(n \in \mathbb{N}\text{.}\) We can write \(16=2^4\) and so \(16 \in T\text{.}\)
Similarly, as in (b), to check that an integer \(m\) is an element of \(P\) we need to find a nonnegative integer \(n\) such that \(m=2^n\text{.}\) Thus
\begin{equation*}
P = \{ m \in \mathbb{Z} \mid m=2^n \text{ for some } n \in \mathbb{N}\}
\end{equation*}
Consider the set \(A = \{ n \in \mathbb{Z} \mid n^2+1=5\}\text{.}\) Show that \(4 \notin A\text{,}\) list the elements of \(A\text{,}\) and calculate \(|A|\text{.}\)
Consider the set \(B= \{n^2+1 \mid n \in \{-2,1,0,1,2\}\}\text{.}\) Show that \(5 \in B\text{,}\) list the elements of \(B\text{,}\) and calculate \(|B|\text{.}\)
Consider the set \(T = \{ n \in \mathbb{N} \mid n \fn{~mod~} 4 = 1\}\text{.}\) Show that \(23 \notin T\text{.}\) Give an example of an element of \(T\text{.}\)
For each of the sets \(A\text{,}\)\(B\text{,}\)\(V\text{,}\) and \(T\) decide if it is described implicitly, explicitly, or as a combination of implicit and explicit.
Let \(S\) and \(T\) be subsets of a set \(U\text{.}\) In this context, \(U\) is the universal set.
The intersection of \(S\) and \(T\text{,}\) denoted \(S \cap T\) and pronounced “\(S\) intersect \(T\)”, is the set
\begin{equation*}
S\cap T = \{x \in U \mid x \in S \land x \in T\}\text{,}
\end{equation*}
where \(\land\) is the logical connective “and”, as introduced in Definition 5.1.2. Note that \(\cap\) looks similar to \(\land\text{.}\) For example, we might be interested in the intersection of the set of students who have completed a discrete mathematics course and the set of students who have completed a linear algebra course, because such students have the prerequisite to take an abstract algebra course.
The union of \(S\) and \(T\text{,}\) denoted \(S \cup T\) and pronounced “\(S\) union \(T\)”, is the set
\begin{equation*}
S\cup T = \{x \in U \mid x \in S \lor x \in T\}\text{,}
\end{equation*}
where \(\lor\) is the logical connective “(inclusive) or”, as introduced in Definition 5.1.2. Note that \(\cup\) looks similar to \(\lor\text{.}\) For example, we might be interested in the union of the set of students who are math majors and the set of students who are computer science majors because we would like to invite that whole group to a talk.
The symmetric difference of \(S\) and \(T\text{,}\) denoted \(S \oplus T\text{,}\) is the set
\begin{equation*}
S \oplus T= \{ x \in U \mid x \in S \oplus x \in T\}\text{,}
\end{equation*}
where \(\oplus\) (or xor) is the logical connective “exclusive or”, as introduced in Definition 5.1.2. For example, we might want to identify people who attended a recent performance of La Bohème or of Tosca, but not both, to offer them the opportunity to buy a season membership to the opera, noting that people who already have a season membership will likely have attended both. If \(S\) is the set of people who attended La Bohème and \(T\) is the set of people who attended Tosca, then the set we want is \(S \oplus T\text{.}\)
The difference of \(S\) and \(T\text{,}\) denoted \(S - T\) and pronounced “\(S\) without \(T\)”, is the set
\begin{equation*}
S-T =\{x \in U \mid x \in S \text{ but } x\notin T\}\text{.}
\end{equation*}
For example, we might want to send a reminder to patients who received a flu vaccine last year but have not yet done so this year. That would be the set \(S -T\) where \(S\) is the set of people who received a flu vaccine last year and \(T\) is the set of people who received a flu vaccine this year. Note that \(T-S\) is usually different. In our example, \(T-S\) would be the patients who received their flu vaccine this year but not last year. The symbol \(-\) looks like the logical operator \(\neg\text{.}\)
The complement of \(S\) (in a universal set \(U\)), denoted \(\overline{S}\text{,}\) is the set
\begin{equation*}
\overline{S}= \{ x \in U \mid x \notin S\}\text{.}
\end{equation*}
Yes, \(\overline{S}=U-S\text{.}\) For example, we might want to reach out to all students who are not yet registered for the fall term. If \(S\) is the set of all students who have registered for fall term and \(U\) is the set of all students, then \(S-U\) is the set we want.
A Venn diagram represents a set by a circle, square, or other curve surrounding all the elements in that set. The standard Venn diagram for two sets looks somewhat like a butterfly. (You will have to imagine the antennae yourself.) For example, the Venn diagram of sets \(S = \{2,3,5\}\) and \(T = \{1,2,3,4\}\) is shown in Figure 7.1.14.
In the butterfly image of a Venn diagram, the intersection of two sets is the body of the butterfly and the union is the entire butterfly as shown in Figure 7.1.15.
In the butterfly image of a Venn diagram, the symmetric difference is the wings of the butterfly and each wing is the difference (as shown in Figure 7.1.16).
For sets \(S = \{2,3,5\}\) and \(T = \{1,2,3,4\}\) calculate the following sets. You might want to look back at Figure 7.1.14.
The union \(S \cap T\) and the intersection \(S \cup T\text{.}\)Solution.
The intersection includes the elements in the overlap of \(S\) and \(T\) so \(S \cap T = \{2,3\}\text{.}\) The union includes all elements in \(S\) or \(T\) or both so \(S \cup T = \{1,2,3,4,5\}\text{.}\)
The symmetric difference \(S \oplus T\) and each difference \(S-T\) and \(T-S\text{.}\)Solution.
The symmetric difference includes the elements in exactly one of \(S\) or \(T\) but not both so \(S \oplus T = \{1,4,5\}\text{.}\) The difference \(S-T\) includes the elements of \(S\) that are not also in \(T\) so \(S-T = \{5\}\text{.}\) Similarly, the difference \(T-S\) includes the elements of \(T\) that are not also in \(S\) so \(T-S = \{1,4\}\text{.}\)
In the set of all bit strings \(\mathbb{B}\text{,}\) consider the set
\begin{equation*}
Z = \{b \in \mathbb{B} \mid b \text{ has at least one } \bs{0}\}\text{.}
\end{equation*}
Evaluate \(\overline{Z}\text{.}\)Solution.
The complement includes all bit strings that do not have at least one \(\bs{0}\text{,}\) that is all bit strings consisting solely of \(\bs{1}\text{,}\) and the empty string \(\lambda\text{.}\) That is
In this example, every element of \(S\) happens to already lie within \(T \cup Y\text{,}\) but in other examples there might be some element in that part of the diagram.
Calculate \((S\cap Y) \cup T\text{.}\)Solution.
Note that \(S\cap Y=\{2,5\}\text{.}\) Thus,
\begin{equation*}
(S\cap Y) \cup T = \{2,5\} \cup \{1,2,3,4\}=\{1,2,3,4,5\}
\end{equation*}
For sets \(X = \{0,1,2,3\}\) and \(Y=\{2,3,4,5,6\}\text{,}\) draw the standard Venn diagram of the sets that includes each element where it belongs and calculate \(X \cup Y\text{,}\)\(X \cap Y\text{,}\)\(X - Y\text{,}\)\(Y-X\text{,}\) and \(X \oplus Y\text{.}\)
For set \(X = \{0,1,2,3\}\) in the universal set \(U = \{0,1,2,3, \ldots, 10\}\text{,}\) draw the standard Venn diagram of the sets that includes each element where it belongs and calculate \(\overline{X}\text{.}\)
Draw a standard Venn diagram for generic sets \(S\) and \(T\) within the same universal set \(U\) and shade in \(\overline{S \cap T}\text{.}\) Repeat for \(\overline{S}\) and repeat again for \(\overline{T}\text{.}\)
As usual, \(\mathbb{N} = \{0,1,2,3,\ldots\}\text{,}\) the set of natural numbers. Is \(4 \in \mathbb{N}\text{?}\) Is \(0 \in \mathbb{N}?\text{?}\) Is \(-3 \in \mathbb{N}\text{?}\)
As usual, \(\mathbb{Z}^+ =\{1,2,3,, \ldots\)\}, the set of positive integers. Is \(4 \in \mathbb{Z}^+\text{?}\) Is \(0 \in \mathbb{Z}^+?\text{?}\) Is \(-3 \in \mathbb{Z}^+\text{?}\)
As usual, \(\mathbb{Z} = \{ \ldots, -3, -2, -1, 0, 1, 2,3, \ldots\}\text{,}\) the set of integers. Is \(4 \in \mathbb{Z}\text{?}\) Is \(0 \in \mathbb{Z}?\text{?}\) Is \(-3 \in \mathbb{Z}\text{?}\)
Hint: One set is empty. Possible elements of the other sets, in some order, are: \(\bs{01111}\text{,}\)\(\bs{00011}\text{,}\) and \(\bs{10101}\text{.}\)
Write each interval in set-builder notation where \(a,
b \in \mathbb{R}\) with \(a \lt b\text{.}\) For example, \((a,b] =\{x \in \mathbb{R} \mid a \lt x \le b\}\text{.}\)
Let \(V=\{r,s,t,u,w,x,y,z\}\) be the set of vertices of the graph \(G\) drawn in Figure 7.1.37. Give an example of an element in each set or explain why the set is empty.
\(A = \{ v \in V \mid v \text{ is adjacent to the vertex } x\}\text{.}\) Recall that \(v\) and \(x\) are adjacent if \(\{v,x\}\) is an edge. This set is the set of neighbors of the vertex \(v\text{.}\)
For the function \(f: \mathbb{R} \to \mathbb{R}\) defined by \(f(x) = x^2-1\text{,}\) identify the set \(Z = \{x \in \mathbb{Z} \mid f(x) = 0\}\text{.}\)
For the function \(\fn{ceil}: \mathbb{R} \to \mathbb{Z}\) defined by \(\fn{ceil}{x}=\lceil x \rceil\text{,}\) identify the set \(F=\{x \in \mathbb{Z} \mid \fn{ceil}(x) = 5\}\text{.}\)
For the function \(\fn{countdiv}: \mathbb{Z} \to \mathbb{N}\) defined by \(\fn{countdiv}{n}=\) the number of (positive) divisors of \(n\text{,}\) identify the set \(T = \{x \in \mathbb{Z} \mid \fn{countdiv}(x) = 2\}\text{.}\)
For readers who have studied calculus, \(f'\) is the derivative of \(f\text{.}\) Write \(D=\{f: \mathbb{R} \to \mathbb{R} \mid f \text{ is differentiable } \}\text{.}\) Give an example of an element in each set. In each case, the elements are functions.
Hint: \(m \in Q\) if \(m = n^2\) for some \(n \in \mathbb{N}\) and \(m \in P\) if \(m = 2^k\) for some \(k \in \mathbb{N}\text{.}\) (You cannot use \(n\) for both.) The answer can be written in the form
\begin{equation*}
\{m \in \mathbb{N} \mid \text{\underline{\hspace{.5in}} and \underline{\hspace{.5in}}} \}
\end{equation*}
Let \(V\) denote the set of all bit strings that have at least two \(\bs{0}\) s. Let \(W\) denote the set of bit strings that have at most two \(\bs{0}\) s.
Give an example of an element in \(V \cap W\text{,}\) then describe which bit strings are in \(V \cap W\text{.}\)
Draw a standard Venn diagram for general sets \(S\text{,}\)\(T\text{,}\) and \(V\) and shade in \(S \cap (T \cup V)\text{.}\) Show some intermediate calculations or explain why you drew the Venn diagram you drew.
How might we express \(\overline{S \cup T}\) in terms of \(\overline{S}\) and \(\overline{T}\text{?}\) Explain. This property is one of DeMorgan’s laws for sets.
How to find \(S \cap T\text{,}\)\(S \cup T\text{,}\)\(S \oplus T\text{,}\)\(S - T\text{,}\) and \(T-S\) for sets \(S\) and \(T\) and how to draw the corresponding Venn diagrams?
\begin{equation*}
A \oplus (B \oplus C) = (A \oplus B) \oplus C
\end{equation*}
for all sets \(A\text{,}\)\(B\text{,}\) and \(C\text{?}\) If true, explain why using Venn diagrams (showing intermediate calculations) or if false, give a counterexample.
Given sets \(A\) and \(B\text{,}\) notice that \(|A|+|B|\) counts each element of \(A \cap B\) exactly twice. How might we use that fact to write \(| A \cup B|\) in terms of \(|A|\) and \(|B|\) and \(|A \cap B|\) for finite sets \(A\) and \(B\text{?}\) This property is inclusion-exclusion.
