Problems

There are a lot of problems here. Just do the ones that interest you.

1. Each of the following sets has cardinality equal to $\aleph_0$, $2^{\aleph_0}$, or $2^{2^{\aleph_0}}$. Determine which, in each case, and prove it.
   1. $\{0,1,4,9,16,\dots\}$
   2. ${\mathbb{Z}}[x]$ (the set of polynomials with integer coefficients)
   3. ${\mathbb{Q}}[x]$ (the set of polynomials with rational coefficients)
   4. ${\mathbb{R}}[x]$ (the set of polynomials with real coefficients)
   5. ${\mathbb{C}}$
   6. The interval $[0,1]$ of real numbers between 0 and $1$ inclusive.
   7. The set of irrational real numbers.
   8. The set of transcendental real numbers.
   9. ${\mathbb{Z}}[i]:=\{a+bi:a,b \in {\mathbb{Z}}\}$ (the set of Gaussian integers)
   10. The set of points in the plane.
   11. The set of lines in the plane.
   12. The set of functions from ${\mathbb{N}}$ to ${\mathbb{N}}$.
   13. The set of bijections from ${\mathbb{N}}$ to ${\mathbb{N}}$.
   14. The set of functions from ${\mathbb{N}}$ to ${\mathbb{R}}$.
   15. The set of functions from ${\mathbb{R}}$ to ${\mathbb{N}}$.
   16. The set of functions from ${\mathbb{R}}$ to ${\mathbb{R}}$.

2. Prove properties 1 through 5 of cardinal numbers listed in Section 4 using only Rules 1 and 2.

3. Let $S$ and $T$ be sets. Prove that if there exists a surjective function $f: S \rightarrow T$, then $\char93 T \le \char93 S$.

4. Explain why our definition of $(\char93 S)^{(\char93 T)}$ agrees with the usual definition for natural numbers when $S$ and $T$ are finite sets.

5. Show that $\aleph_0^{\aleph_0} = 2^{\aleph_0}$.

6. Show that $\char93 {\mathcal P}(S) > \char93 S$ for any set $S$. (Hint: try to rephrase Cantor's diagonal argument purely in terms of set membership, without reference to sequences.)

7. Show that $(\alpha+\beta) \gamma = \alpha \gamma + \beta \gamma$ for any three cardinal numbers $\alpha$, $\beta$, and $\gamma$.

©Berkeley Math Circle