Can you use this \(f\) to conclude that \(\mathbb N\times\mathbb N\) is denumerable?
4.
Describe a partition of \(\mathbb{N}\) that divides \(\mathbb{N}\) into \(\aleph_0\) countably infinite subsets. That is, partition \(\mathbb{N}\) into an infinite number of subsets, each of which is itself infinite.
5.
Theorem 12.2.3 states that \(\mathbb{Z}\) is denumerable. We claimed that \(f:\mathbb{N}\rightarrow\mathbb{Z}\) given by
\begin{equation*}
f(n)=\begin{cases}
\frac{1-n}{2} \amp n \text{ is odd}
\\
\frac{n}{2} \amp n \text{ is even}
\end{cases}
\end{equation*}
is a bijection. Prove this now.
6.
Determine if each of the following sets is denumerable.
The set of irrational numbers, \(\mathbb{I}\)
\(\displaystyle [0,1]\cap \mathbb{Q}\)
\(\displaystyle \set{\pi+q:q\in\mathbb{Q}}\)
\(\set{a+q:q\in\mathbb{Q}}\) for some fixed \(a\in\mathbb{R}\)
\(\displaystyle \set{\pi q:q\in\mathbb{Q}}\)
\(\set{aq:q\in\mathbb{Q}}\) for some fixed \(a\in\mathbb{R}\)
7.
Prove that the set of all irrational numbers is uncountable. You may assume the fact that the set of real numbers is uncountable.
8.
Prove that \((-\infty, -\sqrt{29})\) and \(\mathbb{R}\) are equinumerous by constructing an explicit bijection between them.
9.
Let \(S\) be the set of all functions \(f: \mathbb{N} \rightarrow \set{0, 1}\text{.}\) Prove that \(S\) is uncountable.
Notice that the codomain of these functions is the set that contains just two elements, zero and one. It is not the set of all reals between 0 and 1.
10.
Show that \(\mathbb{R}\) and \((0,1)\) are equinumerous by giving two different explicit bijections.
11.
Show that the two given sets have equal cardinality by describing a bijection from one to the other. Describe your bijection with a formula (not as a table).
\(\mathbb{R}\) and \((\sqrt 2,\infty)\)
The set of even integers and the set of odd integers
\(\mathbb{Z}\) and \(S = \{x \in\mathbb{R}: \sin x = 1\}\)
\(\{0, 1\}\times\mathbb{N}\) and \(\mathbb{Z}\)
12.
Let \(A,B,C,D\) be any nonempty sets. Suppose that \(A\cap C=\emptyset\) and \(B\cap D=\emptyset\text{,}\) and that \(|A|=|B|\) and \(|C|=|D|\text{.}\) Show that \(|A\cup C|=|B\cup D|\text{.}\)
13.
Construct an explicit bijection between the sets \((0,\infty) \) and \((0,\infty)-\set{1}\) to show that \(|(0,\infty)| =|(0, \infty)-\set{1}|\text{.}\)
You must prove that your function is a bijection.
14.
Show that the following pairs of sets are equinumerous.
\((0,1)\times(0,1)\) and \((0,1)\)
\(\mathbb{R}^2\) and \(\mathbb{R}\)
15.
Let \(A\) and \(B\) be equinumerous sets. Show that \(|\mathcal{P}(A)|=|\mathcal{P}(B)|\text{.}\)
16.
Prove or disprove: The set \(\set{(a_1, a_2, a_3, \ldots): a_i \in\mathbb{Z}}\) of infinite sequences of integers is countably infinite.
17.
Let \(A\) and \(B\) be sets. Let \(P\) be a partition of \(A\text{,}\) and let \(Q\) be a partition of \(B\text{.}\) Suppose that we have a bijection between the partitions, \(h\colon P\to Q\text{,}\) with the additional property that \(|X| = |h(X)|\) for every set \(X\in P\text{.}\)
Prove that the underlying sets, \(A\) and \(B\text{,}\) have the same cardinality.
18.
Let \(A\text{,}\)\(B\text{,}\) and \(C\) be sets.
Suppose that \(|A|\leq |B|\) and \(|B|\leq |C|\text{.}\) Show that \(|A|\leq |C|\text{.}\)
Suppose that \(|A|\leq |B|\leq |C|\text{,}\) and that \(|A|=|C|\text{.}\) Then \(|A|=|B|=|C|\text{.}\)
19.
Let \(F_n= \{ X \subset \mathbb{N} \colon |X| = n \}\subseteq \mathcal{P}(\mathbb{N})\text{.}\)
Prove that for every \(n\in\mathbb{N}\text{,}\)\(|F_n|= |\mathbb{N}|\text{.}\)
Also show that \(\big|\bigcup\limits_{n\in \mathbb N}F_n \big|=|\mathbb{N}|\text{.}\)
Does the result in part (b) contradict the fact that \(|\mathbb{N}| \lt |\mathcal{P}(\mathbb{N})|\text{?}\) Explain why or why not (you do not need to give a formal proof).
20.
Consider the following questions about countable unions of countable sets.
Let \(A_1,A_2,A_3,\dots\) be denumerable sets, and suppose that \(A_m\cap A_n=\emptyset\) whenever \(m\neq n\text{.}\) Show that
Redo part (b), but without the assumption that \(A_m\cap A_n=\emptyset\) whenever \(m\neq n\text{.}\)
21.
In the following exercises, you may use the result from Exercise 12.7.20 and the Fundamental Theorem of Algebra: a degree \(n\) polynomial has at most \(n\) real solutions.
Let \(m\in \mathbb{N}\text{.}\) Define \(P_m\) to be the set of degree \(m\) polynomials with rational coefficients. That is,
\begin{equation*}
P_m = \set{a_0+a_1x+\cdots+a_mx^m \so a_i \in \mathbb Q \mbox{ for all }i\in \{0,1,\ldots,m\}, \, a_m\neq 0}.
\end{equation*}
Show that \(P_m\) is countable.
Now, define \(P\) to be the set of all polynomials with rational coefficients. That is,
\begin{equation*}
P = \left\{a_0+a_1x+\cdots+a_nx^n \so n \in \mathbb N \;\text{and}\;
a_i \in \mathbb Q \;\text{for all}\; i\in \{0,1,\ldots,n\}, \, a_n\neq 0 \right\}.
\end{equation*}
Prove that \(P\) is countable.
Define \(A\) to be the set of all real numbers that are the roots of a polynomial in \(P\text{.}\) That is,
\begin{equation*}
A = \set{x \in \mathbb R \so \exists f \in P\setminus\set{0} \; \text{s.t.}\; f(x)=0 }.
\end{equation*}
