\(\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.2Subsets and Sets of Sets
We continue our discussion of sets by revisiting the concept of a subset and describing how to represent subsets using bit strings. Next, we consider sets whose elements are also sets, including the set of all subsets of a set. We conclude by working with set-theoretic functions.
We first encountered subsets in Section 2.3. We repeat that initial description here. In many situations, we want to select some of the elements of a set. We can think of a set as corralling its elements inside a rope. For example, the set \(A=\{1,2,3,7,8\}\) is drawn in Figure 7.2.1. If we corral some, all, or none of the elements within \(A\text{,}\) we get a subset of \(A\text{.}\) For example, Figure 7.2.1 shows the subset \(\{2,8\}\) shaded in gray.
The set \(S\) is a subset of the set \(A\text{,}\) denoted \(S \subseteq A\text{,}\) if every element of \(S\) is an element of \(A\text{.}\) That is, \(\forall x \in S, x \in A\) or, equivalently,
\begin{equation*}
x \in S \to x \in A\text{.}
\end{equation*}
For example, \(\{2,8\} \subseteq \{1,2,3,7,8\}\) because \(2 \in \{1,2,3,7,8\}\) and \(8 \in \{1,2,3,7,8\}\text{.}\) Similarly, \(\{3\} \subseteq \{1,2,3,7,8\}\) because \(3 \in \{1,2,3,7,8\}\text{.}\) Note that \(\{3\}\) is different from the integer 3. For example, it would not be appropriate to write \(3 \subseteq \{1,2,3,7,8\}\) without the set brackets around 3.
If the set \(S\) is not a subset of the set \(A\text{,}\) we write \(S \nsubseteq A\text{.}\) For example, \(\{1,5,6\}\nsubseteq \{1,2,3,7,8\}\) because, for example, \(5 \in \{1,5,6\}\) but \(5 \notin \{1,2,3,7,8\}\text{.}\)
Note that the set \(A\) is a subset of itself. Think of corralling all the elements of \(A\text{.}\) For example, \(\{1,2,3,7,8\} \subseteq \{1,2,3,7,8\}\text{.}\) A subset \(S\) of a set \(A\) is proper if \(S \neq A\text{.}\) For example \(\{2,8\}\) is a proper subset of \(\{1,2,3,7,8\}\text{.}\)
For example, \(\varnothing \subseteq \{1,2,3,7,8\}\text{.}\) Think of corralling no elements of \(A\) or drawing a shaded shape within \(A\) that contains none of the elements of \(A\text{.}\) Note that any statement beginning \(\forall x \in \varnothing\) is vacuously true since there is nothing to check. In particular, \(\forall x \in \varnothing, x \in A\) is true. Similarly, any statement beginning “if \(x \in \varnothing\)” is also true because \(x \in \varnothing\) is false and any conditional with false hypothesis is true. In particular, \(x \in \varnothing \to x \in A\) is true.
How many 3-element subsets does \(A = \{1,2,3,4,5\}\) have?
Solution.
There are \(\binom{5}{3}\) 3-element subsets from a set of 5 elements, by definition of the binomial coefficients Definition 2.3.5. We can evaluate \(\binom{5}{3}=10\text{,}\) or just leave the answer as \(\binom{5}{3}\text{.}\)
Prove that \(X\) is a proper subset of \(E\text{.}\)Solution.
Since we know that \(X\) is a subset, it remains to show that \(X\) is proper. For that, all we need is an example of \(E-X\text{,}\) that is, an element of \(E\) that is not in \(X\text{.}\) Any even number that is not a multiple of 6 will do. For example, \(4 \in E\) but \(4 \notin X\text{.}\)
Let \(S = \{ b \in \mathbb{B}_5 \mid b \text{ has exactly two \bs{0}s } \}\) and let \(T = \{ b \in \mathbb{B}_5 \mid b \text{ has exactly three \bs{1}s } \}\) where \(\mathbb{B}_5\) is the set of bit strings of length five. For example, \(\bs{10101} \in S\) because it has two \(\bs{0}\) s and \(\bs{10101} \in T\) because it has three \(\bs{1}\) s. Can you see that \(S = T\text{?}\) Prove \(S=T\text{.}\)
Proof: First, let \(b \in S\text{.}\) That is, \(b\) is a bit string of length five that has exactly two \(\bs{0}\) s. The remaining \(5-2=3\) bits must be \(\bs{1}\) s. Thus \(b \in T\text{.}\)
Conversely, let \(b \in T\text{.}\) That is, \(b\) is a bit string of length five that has exactly three \(\bs{1}\) s. The remaining \(5-3=2\) bits must be \(\bs{0}\) s. Thus \(b \in S\text{.}\)
Notice in Example 7.2.7 that we showed \(S=T\) by showing that \(S \subseteq T\) (if \(x \in S\text{,}\) then \(x \in T\)) and then showing the converse that \(T \subseteq S\) (if \(x \in T\text{,}\) then \(x \in S\)), as in Definition 5.4.1. Putting these two parts together, we conclude that the elements of \(S\) and \(T\) are the same, and so \(S=T\text{.}\)
How many subsets does \(\{1,2,3,\ldots,n\}\) have? Hint: Count using Step 1: Decide if 1 is in the subset (yes/no). Step 2: Decide if 2 is in the subset (yes/no). And so on.
Consider the sets \(Q = \{ n^2 \mid n \in \mathbb{N}\}\) and \(P = \{2^n \mid n \in \mathbb{N}\}\text{.}\) Describe \(Q\) and \(P\) in words, then show that neither of \(Q\) or \(P\) is a subset of the other.
Subsection7.2.BBit String Representation of Subsets
Set operations can be useful in sorting data, as we saw in the examples in Definition 7.1.12. But working with sets can be bulky. It turns out that we can represent subsets using bit strings, and we can encode set operations as bit string operations.
Definition7.2.10Bit string representation of subsets.
Let \(U = \{a_1, a_2, a_3, \ldots,
a_n\}\) be a finite set and let \(S\) be a subset of \(U\text{.}\) The bit string representation of \(S\) (in \(U\)) is \(b=b_1b_2b_3\ldots b_n\) where
\begin{equation*}
b_i = \left\{ \begin{array}{cl} \bs{1} \amp \text{ if } a_i \in S \\ \bs{0} \amp \text{ if } a_i \not\in S \end{array} \right.
\end{equation*}
For example, for \(U = \{1,2,3,4,5,6\}\text{,}\) let’s calculate the bit string representation of the subset \(S =\{1,2,3\}\text{.}\) It can help to write the universal set as a reference set as in Table 7.2.11.
Table7.2.11.Representing the subset \(S =\{1,2,3\}\) of the universal set \(U = \{1,2,3,4,5,6\}\) using the bit string \(b=\bs{111000}\)
The first bit of \(b\) is \(\bs{1}\) because \(1 \in S\text{,}\) the second bit of \(b\) is \(\bs{1}\) because \(2 \in S\text{,}\) the third bit of \(b\) is \(\bs{1}\) because \(3 \in S\text{,}\) the fourth bit of \(b\) is \(\bs{0}\) because \(4 \notin S\text{,}\) the fifth bit of \(b\) is \(\bs{0}\) because \(5 \notin S\text{,}\) and the sixth bit of \(b\) is \(\bs{0}\) because \(6 \notin S\text{.}\) Thus, \(b=\bs{111000}\text{.}\)
Note that each subset of \(U\) has a unique bit string and each bit string has a unique subset. That is, \(S \leftrightarrow b\) is a pairing. We can use bit-wise operators to perform set operations. Here is an example.
Make a conjecture about the relationship in general: if \(b \leftrightarrow S\) and \(c \leftrightarrow T\text{,}\) then \(b \land c \leftrightarrow \underline{\hspace{1in}}\text{.}\)Solution.
Suppose \(b \leftrightarrow S\) and \(c \leftrightarrow T\text{.}\) The only way we have a \(\bs{1}\) in \(b \land c\) is when there is a \(\bs{1}\) in \(b\) and a \(\bs{1}\) in the same place in \(c\text{.}\) That is, when that element of \(U\) is in the set \(S\) and in the set \(T\text{.}\) We conjecture that
\begin{equation*}
b \land c \leftrightarrow S \cap T
\end{equation*}
Activity7.2.BBit string representation of subsets.
List the bit string corresponding to each subset of \(U = \{1,2,3,4,5,6,7,8,9,10\}\text{:}\)\(\{1,3,5,7,9\}\text{,}\)\(\{2, 4, 6, 8, 10\}\text{,}\)\(\{10\}\text{,}\) and \(U\text{.}\)
List the subset of \(U = \{1,2,3,4,5,6,7,8,9,10\}\) corresponding to each bit string: \(\bs{1100110011}\text{,}\)\(\bs{1000000001}\text{,}\) and \(\bs{0000000000}\text{.}\)
In the universal set \(U = \{1,2, 3, 4, 5\}\text{,}\) write the subsets corresponding to \(b = \bs{10011}\text{,}\)\(c = \bs{11001}\text{,}\) and \(b \lor c\text{.}\) It might help to write the universal set as a reference.
Make a conjecture about the relationship in general: if \(b \leftrightarrow S\) and \(c \leftrightarrow T\text{,}\) then \(b \lor c \leftrightarrow \underline{\hspace{1in}}\text{.}\)
Which of those sets contains the element \(x\text{?}\) The element \(y\text{?}\)Solution.
Looking at the list of elements, we see that the sets \(\{x, y\}\) and \(\{x,\{y\}\}\) contain the element \(x\text{,}\) but only the set \(\{x, y\}\) contains the element \(y\text{.}\)
Given a set \(A\text{,}\) the power set of \(A\text{,}\) denoted \(\mathscr{P}(A)\) is the set of all subsets of \(A\text{.}\) That is, \(\mathscr{P}(A) = \{ S \mid S \subseteq A\}\text{.}\) For example, the power set of \(\{0,1\}\) is \(\mathscr{P}(\{0,1\}) = \{ \varnothing, \{0\}, \{1\}, \{0,1\}\}\text{.}\)
Example7.2.16Sets of sets defined using set-builder notation.
Give examples of two different elements in each set. Recall that \(\mathscr{P}(\mathbb{Z})\) is the set of all subsets of \(\mathbb{Z}\text{.}\)
\(\mathscr{S} = \{ A \in \mathscr{P}(\mathbb{Z}) \mid 2 \in A \text{ but } -3 \notin A\}\)Solution.
We want subsets of \(\mathbb{Z}\) that contain 2 but not -3. One example is \(\{2,4,6\}\) since \(2 \in \{2,4,6\}\) and \(-3 \notin \{2,4,6\}\text{.}\) Another example is \(\mathbb{N}\) because \(2 \in \mathbb{N}\) but \(-3 \notin \mathbb{N}\text{.}\)
Recall that \(\mathscr{P}(\mathbb{Z})\) is the set of all subsets of \(\mathbb{Z}\text{.}\) Give two examples of elements of the set \(\mathscr{D} = \{ A \in \mathscr{P}(\mathbb{Z}) \mid A \cap \{1,2,3\} = \varnothing\}\text{.}\)
In Section 6.2, we saw functions that involve bit strings, number theory, and graph theory. Let’s look at some examples of functions involving set theory.
Evaluate \(\fn{seven}(\{1,3,4,7\})\) and \(\fn{seven}(\{0,2,4,6,8\})\text{.}\)Solution.
Since 7 is one of the elements in \(\{1,3,4,7\}\text{,}\) we are in the first case and so \(\fn{seven}(\{1,3,4,7\})=1\text{.}\) Since 7 is not one of the elements in \(\{0,2,4,6,8\}\text{,}\) we are in the second case and so \(\fn{seven}(\{0,2,4,6,8\})=0\text{.}\)
Is \(\fn{seven}\) onto? Is \(\fn{seven}\) one-to-one?
Solution.
First, \(\fn{seven}\) is onto because the image is the entire codomain. For example, we saw that \(\fn{seven}(\{0,2,4,6,8\})=0\) and \(\fn{seven}(\{1,3,4,7\})=1\text{.}\)
The function \(\fn{card}:\mathscr{P}(\{0,1,2,3,4,5,6,7,8,9\}) \to \mathbb{N}\) is defined by \(\fn{card}(A)=|A|\text{,}\) the number of elements in the set \(A\text{.}\)
Evaluate \(\fn{card}(\{1,4,5,7\})\) and \(\fn{card}(\{0\})\text{.}\)Solution.
The set \(\{1,4,5,7\}\) has four elements, so \(\fn{card}(\{1,4,5,7\})=4\text{.}\) The set \(\{0\}\) has one element, so \(\fn{card}(\{0\})=1\text{.}\)
Identify the domain, codomain, and image of \(\fn{card}\text{.}\)Solution.
The domain is \(\mathscr{P}(\{0,1,2,3,4,5,6,7,8,9\})\text{,}\) meaning we can input any subset of \(\{0,1,2,3,4,5,6,7,8,9\}\text{.}\) The codomain is \(\mathbb{N}\) meaning the output is always a nonnegative integer. The image is the set of actual output values. Since each subset of \(\{0,1,2,3,4,5,6,7,8,9\}\) has between 0 and 10 elements, and all are possible, the image is \(\{0,1,2,3,4,5,6,7,8,9,10\}\text{.}\)
How many elements \(A\) of \(\mathscr{P}\) have \(\fn{card}(A)=4\text{?}\) Explain how you counted.
Solution.
A set \(A\) has \(\fn{card}(A)=4\) exactly when \(A\) has four elements. The number of 4-element subsets of \(\{0,1,2,3,4,5,6,7,8,9\}\) is, by Definition 2.3.5, exactly \(\binom{10}{4}\text{.}\) In case you are curious, \(\binom{10}{4}=210\text{.}\)
Let \(P = \mathscr{P}(\mathbb{N})\text{,}\) the set of all subsets of \(\mathbb{N}\text{,}\) and let \(P^*\) be the set of all nonempty subsets of \(\mathbb{N}\text{.}\)
The function \(\fn{del7}: P \to P\) is defined by \(\fn{del7}(A) = A-\{7\}\text{.}\) Evaluate \(\fn{del7}(\{2,4,7\})\) and \(\fn{del7}(\{1,2,3,4\})\text{.}\) What are the fixed points of \(\fn{del7}\text{,}\) meaning which sets \(A\) have \(\fn{del7}(A) = A\text{?}\)
The function \(\fn{max}:P^* \to \mathbb{N}\) is defined by \(\fn{max}(A)=\) the largest integer in \(A\text{.}\) Evaluate \(\fn{max}(\{2,4,7\})\text{.}\) How many sets \(A\) have \(\fn{max}=2\text{?}\) List them.
Consider the sets \(T = \{3k \mid k \in \mathbb{N}\}\) and \(X = \{6k \mid k \in \mathbb{N}\text{.}\) For each statement, either prove the statement is true (following Example 7.2.6(b)) or prove a counterexample to show the statement is false.
How are these subsets related? State your answer as a conjecture: if \(b \leftrightarrow S\) and \(c \leftrightarrow T\text{,}\) then \(b \oplus c \leftrightarrow \underline{\hspace{1in}}\text{.}\)
How are these subsets related? State your answer as a conjecture: if \(b \leftrightarrow S\text{,}\) then \(\neg b \leftrightarrow \underline{\hspace{1in}}\text{.}\)
We know from Theorem 2.4.8 that there are \(2^n\) bit strings of length \(n\text{.}\) Use this fact and the bit string representation of subsets to explain why it follows that if \(U\) is a set with \(n\) elements, then \(U\) has \(2^n\) subsets.
We know from the definition of the binomial coefficients Definition 2.3.5 that if \(U\) is a set with \(n\) elements, then there are \(\binom{n}{k}\) subsets of \(U\) that have exactly \(k\) elements. Use this fact and the bit string representation of subsets to explain why it follows that there are \(\binom{n}{k}\) bit strings of length \(n\) with exactly \(k\)\(\bs{1}\) s Theorem 2.4.11.
Give examples of two different elements in each set. Note that the elements are themselves sets. Recall that \(\mathscr{P}(\mathbb{Z})\) is the set of all subsets of \(\mathbb{Z}\text{.}\)
\(\displaystyle \{ A \in \mathscr{P}(\mathbb{Z}) \mid 1, 2, 3 \in A \text{ but } 4 \notin A\}\)
Consider the graph \(G\) in Figure 7.1.37 with vertex set \(V\text{.}\) Recall that \(\mathscr{P}(V)\) is the set of all subsets of \(V\text{.}\) List two elements in each set.
\(\displaystyle \{ D \in \mathscr{P}(V) \mid |D| = 4\}\)
How many elements does \(\{ A \in \mathscr{P}(W) \mid |A| = 2\}\text{,}\) the set of all doubleton (two element) subsets of \(W\) have? List or count, your choice.
In this problem, we explore one definition of the set of natural numbers using sets. We will use boldface \(\mathbf{0}, \mathbf{1}, \mathbf{2}, \ldots\) to distinguish what we are defining from the usual natural numbers \(0, 1, 2, \ldots\text{.}\) To start, define \(\mathbf{0} = \varnothing\text{.}\) Note that \(|\mathbf{0}|=0\text{.}\) As in Exercise 22, for any set \(K\text{,}\) the successor of \(K\) is \(\mathscr{S}(K)= K \cup \{K\}\text{.}\)
Define \(\mathbf{1} = \mathscr{S}(\mathbf{0})\text{.}\) Write \(\mathbf{1}\) in terms of \(\mathbf{0}\text{,}\) write \(\mathbf{1}\) in terms of \(\varnothing\text{,}\) and calculate \(|\mathbf{1}|\text{.}\)
Define \(\mathbf{2} = \mathscr{S}(\mathbf{1})\text{.}\) Write \(\mathbf{2}\) in terms of \(\mathbf{0}\) and \(\mathbf{1}\text{,}\) write \(\mathbf{2}\) in terms of \(\varnothing\text{,}\) and calculate \(|\mathbf{2}|\text{.}\)
SubsubsectionExercises for 7.2.D Detour: Set-theoretic Functions
27.Practice.
Let \(P = \mathscr{P}(\mathbb{N})\text{,}\) the set of all subsets of \(\mathbb{N}\) and let \(P^*\) be the set of all nonempty subsets of \(\mathbb{N}\text{.}\) The function \(\fn{min}:\mathscr{P}^* \to \mathbb{N}\) is defined by \(\fn{min}(A)\) is the smallest number in the set \(A\text{.}\)
Evaluate \(\fn{min}(\{1,3,4,7\})\) and \(\fn{min}(\{5\})\text{.}\)
The function \(\fn{del0}:\mathscr{P}(\{0,1,2,3,4,5,6,7,8,9\}) \to \mathscr{P}(\{0,1,2,3,4,5,6,7,8,9\})\) is defined by \(\fn{del0}(A)=A -\{0\}\text{.}\)
Evaluate \(\fn{del0}(\{0,4,6\})\) and \(\fn{del0}(\{5,6,7\})\text{.}\)
As usual, \(\mathscr{P}(\mathbb{N})\) is the set of all subsets of \(\mathbb{N}\text{.}\) Define \(\fn{sqrt}: \mathscr{P}(\mathbb{N}) \to \mathscr{P}(\mathbb{N})\) by \(\fn{sqrt}(A) = \{a \in \mathbb{N} \mid a^2 \in A\}\text{.}\)
The function \(\fn{three}:\mathscr{P}(\{0,1,2,3,4,5,6,7,8,9\}) \to \{0,1\}\) is defined by
\begin{equation*}
\fn{three}(A) = \left\{ \begin{array}{cl} 1 \amp \text{ if 3 is in the set } A \\ 0 \amp \text{ if 3 is not in the set } A \end{array} \right.
\end{equation*}
Identify the domain and codomain of \(\fn{three}\) and evaluate \(\fn{three}(\{1,3,4,7\})\) and \(\fn{three}(\varnothing)\text{.}\)
Consider the function \(\fn{both}:\mathscr{P}(\{0,1,2,3,4,5,6,7,8,9\}) \to \{0,1\}\) defined by
\begin{equation*}
\fn{both}(A) = \left\{ \begin{array}{cl} 1 \amp \text{ if 3 and 7 are both in the set } A \\ 0 \amp \text{ otherwise } \end{array} \right.\text{.}
\end{equation*}
Identify the domain and codomain of \(\fn{both}\) and evaluate \(\fn{both}(\{1,3,4,7\}\) and \(\fn{both}(\{5,6,7,8\}\text{.}\)
Write a formula for the function \(\fn{both}\) that is not piecewise-defined by using the function \(\fn{three}\) from 31.(a) and the function \(\fn{seven}\) from Example 7.2.18.
