\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \)
deepdream of
          a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \)
Math and science::Analysis::Tao::08. Infinite sets

Count all the things (countability propositions)

A number of propositions related to countable sets:

  • All subsets of the natural numbers are at most countable.
  • Let \( Y \) be a set, and let \( f: \mathbb{N} \rightarrow Y \) be a function. Then the image \( f(\mathbb{N}) \) is at most countable.
  • Let \( X \) be a countable set, and let \( f : X \rightarrow Y \) be a function. Then \( f(X) \) is at most countable.
  • Let \( X \) and \( Y \) be countable sets. Then \( X \cup Y \) is a countable set.
  • The integers \( \mathbb{Z} \) are countable.
  • The set \( A := \{(n, m)\ \in \mathbb{N} \times \mathbb{N} : 0 \le m \le n\} \) is countable.
  • The set \( \mathbb{N} \times \mathbb{N} \) is countable.
  • The rationals \( Q \) are countable.
  • The set of all functions from \( {0, 1} \) to \( \mathbb{N} \) is countable.
  • The set of all functions from \( \mathbb{N} \) to \( {0, 1} \) is uncountable, representing an arbitrary binary string.

Maybe some of these should be split up and their proofs outlined.


Once we have a bijection from \( \mathbb{N} \) to \( \mathbb{N} \times \mathbb{N} \), we can have a bijection to the rationals, which are defined as a pairing of two numbers to make a quotient.


Source

p185-188