Elementary Foundations: An introduction to topics in discrete mathematics

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

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

The set of natural numbers and the set of positive natural numbers.

The set of natural numbers and the set of natural numbers that are greater than $9,999,999\text{.}$

The set of even natural numbers and the set of odd natural numbers.

The set of even natural numbers and the set of natural numbers.

The set of natural numbers and the set of integer powers of $2\text{.}$

Demonstrate that $\mathcal{P}(A)$ and ${\mathrm{\Sigma }}_5^{\ast }$ have the same size. (Recall that ${\mathrm{\Sigma }}_5^{\ast }$ means the set of words in ${\mathrm{\Sigma }}^{\ast }$ 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.

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