Use the definition of cardinality to verify that \(\card{A} = 8\) for
\begin{equation*}
A = \{1,2,4,8,16,32,64,128\} \text{.}
\end{equation*}
Activity12.2.
The steps below will guide you through a proof of the following statement.
If \(B\) is finite and \(A \subseteq B\text{,}\) then \(A\) is also finite.
(a)
Start by assuming that \(B\) is finite. Write out what this means. (You may do this using the technical definition of finite set, or you may do this using the sequence characterization of finiteness in Fact 12.2.1.)
(b)
Now add the assumption that \(A \subseteq B\text{.}\) Try to use your technical expression of the assumption “\(B\) is finite” from Task a to determine a similar technical expression of the desired conclusion “\(A\) is finite.”
Activity12.3.
Use the sequence characterization of finiteness in Fact 12.2.1 to prove the following statement.
If \(A\) and \(B\) are finite and do not intersect, then \(\abs{A \sqcup B} = \abs{A} + \abs{B}\text{.}\)
Use separate finite sequences to “count” the elements of \(A\) and \(B\text{.}\) Then use these two sequences to build a sequence that “counts” the elements of \(A \sqcup B\text{.}\)
Activity12.4.
In each of the following, demonstrate that the two sets satisfy the technical definition of same size by explicitly describing a bijection between them.
(a)
The set of natural numbers and the set of positive natural numbers.
(b)
The set of natural numbers and the set of natural numbers that are greater than \(9,999,999\text{.}\)
(c)
The set of even natural numbers and the set of odd natural numbers.
(d)
The set of even natural numbers and the set of natural numbers.
(e)
The set of natural numbers and the set of integer powers of \(2\text{.}\)
Demonstrate that \(\powset{A}\) and \(\words{\Sigma}_5\) have the same size. (Recall that \(\words{\Sigma}_5\) means the set of words in \(\words{\Sigma}\) of length exactly \(5\text{.}\)) Do this not by determining the cardinality of each of the two sets, but by showing that the sets satisfy the technical definition of same size. As in Activity 12.4, this will require that you explicitly describe a bijection between the two sets.
Think of a \(5\)-letter word in the alphabet \(\Sigma\) as the answers to five yes-or-no questions. How does such a string of answers correspond to some subset of \(A\text{?}\)
(b)
Describe how you could use the bijection you set up in Task a to turn the problem of counting the number of subsets of \(A\) that have exactly \(3\) elements into a problem of counting a related collection of words in the alphabet \(\Sigma\text{.}\)
(Note: You are not asked to actually determine the number of such subsets. You are only asked to describe how the result of Task a can be adapted to this counting problem.)
