12.6: Exercises

Exercise $\PageIndex{1}$

Prove: If $B$ is finite and $A \subseteq B\text{,}$ then $A$ is finite and $\vert A \vert \le \vert B \vert\text{.}$

Exercise $\PageIndex{2}$

Suppose that $A\text{,}$ $B\text{,}$ and $C$ are finite subsets of a universal set $U\text{.}$

1. Prove: If $A$ and $B$ are disjoint, then $\vert A \sqcup B \vert = \vert A \vert + \vert B \vert\text{.}$
2. Prove: $\vert A \cup B \vert = \vert A \vert + \vert B \vert - \vert A \cap B \vert\text{.}$

Hint.

See Exercise 9.9.5, and use the equality from Task a.

3. Determine a similar formula for $\vert A \cup B \cup C \text{.}$

Hint.

Draw a Venn diagram first.

Exercise $\PageIndex{3}$

Use induction to prove directly that if $\vert A \vert = n$ then $\vert \mathscr{P}(A) \vert = 2^n\text{.}$ Use Worked Example 12.2.1 as a model for your proof of the induction step.

Exercise $\PageIndex{4}$

Prove: If $\vert A \vert = \infty$ and $A \subseteq B\text{,}$ then $\vert B \vert = \infty\text{.}$

Exercise $\PageIndex{5}$

Prove Fact 12.3.2.

Exercise $\PageIndex{6}$

Combine Example 12.3.3 and Example 12.3.10 to verify that the unit interval $(0,1)$ and $\mathbb{R}$ have the same size.

Hint.

First map the punctured circle $\hat{S}$ onto some open interval in the $x$-axis by “unrolling” $\hat{S}\text{.}$

Exercise $\PageIndex{7}$

Use Example 12.3.3 and the function $f(x) = \tan x$ to prove that the interval $(-\pi/2,\pi/2)$ and $\mathbb{R}$ have the same size.

Hint.

The function $f(x) = \tan x$ is not one-to-one, but it becomes one-to-one if you restrict its domain to an appropriate interval

Exercise $\PageIndex{8}$

Prove that if $A$ and $B$ have the same size, then so do $\mathscr{P}(A)$ and $\mathscr{P}(B)\text{.}$

Hint.

See Exercise 10.7.19.

Exercise $\PageIndex{9}$

Suppose $A$ is a set with $\vert A \vert = n\text{.}$ Then we can enumerate its elements as $A = \{a_1,a_2,\ldots ,a_n\}\text{.}$

1. Construct a bijection from the power set of $A$ to the set of words in the alphabet $\Sigma = \{T,F\}$ of length $n\text{.}$

Note that there are two tasks required here.

1. Explicitly describe a function $f: \mathscr{P}(A) \rightarrow \Sigma^\ast_n$ by describing the input-output rule: give a detailed description of how, given a subset $B \subseteq A\text{,}$ the word $f(B)$ should be produced.
2. Prove that your function $f$ is a bijection.

Hint.

When determining the input-output rule for your function $f: \mathscr{P}(A) \rightarrow \Sigma^\ast_n\text{,}$ think of how one might construct an arbitrary subset of $A\text{,}$ and then relate that process to a sequence of answers to $n$ true/false questions.

2. Use Task a to determine the cardinality of $\mathscr{P}(A)\text{.}$ Explain.

Hint

See Note 1.3.1.

3. Suppose $k$ is some fixed (but unknown) integer, with $0 \le k \le n\text{.}$ Let $\mathscr{P}(A)_k$ represent the subset of $\mathscr{P}(A)$ consisting of all subsets of $A$ that have exactly $k$ elements. Describe how your bijection from Task a, could be used to count the elements of $\mathscr{P}(A)_k\text{.}$

Hint.

Consider how restricting the domain might help.