J. Munkres. Topology (2013) Chapter I: Set Theory and Logic. 7: Countable and Uncountable Sets

Definition: Countably Infinite

A set is countably infinite iff it is bijective with \(\mathbb{Z}_+\).

Example

The set \(\mathbb{Z}\) is countably infinite.

Definition: Countable

A set is countable iff it is either finite or countably infinite; otherwise it is uncountable.

Principle of Recursive Definition

Let \(A\) be a set. Let \(a_0 \in A\). Let \(\rho\) be a function from \( \{ f \mid \exists n \in \mathbb{Z}_+. f : \{1, \ldots, n\} \rightarrow A \} \) to \(A\). Then there exists a unique function \(h : \mathbb{Z}_+ \rightarrow A\) such that

\[ \begin{align} h(1) & = a_0 \\ h(i) & = \rho(h \restriction \{1, \ldots, i-1\}) & (i > 1) \end{align} \]

Proof

  • For every positive integer \(n\), there exists a unique function \(f_n : \{1, \ldots, n\} \rightarrow A\) such that \(f_n(1) = a_0\) and, for all \(i = 2, 3, \ldots, n\), we have \(f_n(i) = \rho(f_n \restriction \{1, \ldots, i-1\})\).
    • Let \(P(n)\) be the statement: there exists a unique function \(f_n : \{1, \ldots, n\} \rightarrow A\) such that \(f_n(1) = a_0\) and, for all \(i = 2, 3, \ldots, n\), we have \(f_n(i) = \rho(f_n \restriction \{1, \ldots, i-1\})\).
    • \(P(1)\)
      • Take \(f_1 = \{(1,a_0)\}\).
    • For every positive integer \(n\), if \(P(n)\) then \(P(n+1)\).
      • Assume \(P(n)\). Define \(f_{n+1} = f_n \cup \{(n+1, \rho(f_n))\}\).
  • Let \(h : \mathbb{Z}_+ \rightarrow A\) be the union of all the functions \(f_n\).
  • \( h(1) = a_0\)
  • For all \(i \in \mathbb{Z}_+\) we have \(h(i) = \rho(h \restriction \{1, \ldots, i-1\})\).
  • \(h\) is unique.
  • \(\Box\)

Lemma 7.2

Every infinite subset of \(\mathbb{Z}_+\) is countably infinite.

Proof

  • Let \(C\) be an infinite subset of \(\mathbb{Z}_+\).
  • Define \(h : \mathbb{Z}_+ \rightarrow C\) by recursion by: \(h(1)\) is the least element of \(C\), and for \(n > 1\), we have \(h(n)\) is the least element of \(C - h(\{1, \ldots, n-1\})\).
    • \(C - h(\{1, \ldots, n-1\})\) is nonempty because \(C\) is infinite.
  • \(h\) is injective.
    • If \(m < n\) then \(h(n) \in C - h(\{1, \ldots, n-1\})\) and so \(h(n) \neq h(m)\).
  • \(h\) is surjective.
    • Let \(c \in C\).
    • Let \(m\) be least such that \(h(m) \geq c\).
      • We cannot have \(h(\mathbb{Z}_+) \subseteq \{1, \ldots, c-1\}\) because \(h\) is injective and so \(h(\mathbb{Z}_+\)\) is infinite.
    • \(c \notin h(\{1, \ldots, m-1\})\)
    • \(h(m) \leq c\)
      • Since \(h(m)\) is the least element of \(C - h(\{1, \ldots, m-1\})\).
    • \(h(m) = c\)
  • \(\Box\)

Theorem 7.1

Let \(B\) be a nonempty set. Then the following are equivalent:

  1. \(B\) is countable.
  2. There is a surjective function \(\mathbb{Z}_+ \rightarrow B\).
  3. There is an injective function \(B \rightarrow \mathbb{Z}_+\).

Proof

  • \(1 \Rightarrow 2\)
    • Assume \(B\) is countable. Prove: There exists a surjective function \(\mathbb{Z}_+ \rightarrow B\).
    • Case \(B\) is finite.
      • Pick a positive integer \(n\) and a bijection \(f : \{1, \ldots, n\} \approx B\).
      • Define a surjection \(h : \mathbb{Z}_+ \rightarrow B\) by \(h(i) = f(i)\) if \(i \leq n\), \(f(1)\) otherwise.
    • Case \(B\) is countably infinite.
      • There is a bijection \(\mathbb{Z}_+ \approx B\).
  • \(2 \Rightarrow 3\)
    • Let \(f : \mathbb{Z}_+ \rightarrow B\) be a surjection.
    • Define an injection \(g : B \rightarrow \mathbb{Z}_+\) by \(g(b)\) is the least positive integer such that \(f(g(b)) = b\).
  • \(3 \Rightarrow 1\)
    • Every subset of \(C\) is countable.
      • By Lemma 7.2
    • Let \(f : B\rightarrow \mathbb{Z}_+\) be an injection.
    • \(f(B)\) is countable.
    • \(B\) is countable.

Corollary 7.3

A subset of a countable set is countable.

Corollary 7.4

The set \(\mathbb{Z}_+^2\) is countably infinite.

Proof

Define \(f : \mathbb{Z}_+^2 \rightarrow \mathbb{Z}_+\) by \(f(m,n) = 2^n 3^m\).

Example

The set \(\mathbb{Q}\) is countably infinite. We have \(\mathbb{Z} \times (\mathbb{Z} - \{0\})\) is countably infinite (since \(\mathbb{Z}\) and \(\mathbb{Z} - \{0\}\) are both bijective with \(\mathbb{Z}_+\)), and so \(\mathbb{Q}\) is countably infinite because the function that maps \((m,n)\) to \(m/n\) is a surjection.

Theorem 7.5

A countable union of countable sets is countable.

Proof

  • Let \(\{A_n\}_{n \in J\}\) be a family of countable sets where \(J = \{1, \ldots, N\}\) for some \(N\) or \(J = \mathbb{Z}_+\).
  • Assume w.l.o.g. each \(A_n\) is nonempty.
  • For \(n \in J\), pick a surjection \(f_n : \mathbb{Z}_+ \rightarrow A_n\).
  • Pick a surjection \(g : \mathbb{Z}_+ \rightarrow J\).
  • Define \(h : \mathbb{Z}_+^2 \rightarrow \bigcup_{n \in J} A_n\) by \(h(m,n) = f_{g(m)}(n)\).
  • \(h\) is a surjection.
  • \(\Box\)

Theorem 7.6

The product of two countable sets is countable.

Proof

  • Let \(A\) and \(B\) be countable sets.
  • Assume w.l.o.g. \(A\) and \(B\) are nonempty.
  • Pick surjections \(f : \mathbb{Z}_+ \rightarrow A\) and \(g : \mathbb{Z}_+ \rightarrow B\).
  • Define \(h : \mathbb{Z}_+^2 \rightarrow A \times B\) by \(h(m,n) = (f(m),g(n))\).
  • \(h\) is surjective.
  • \(\Box\)

Theorem 7.7

Let \(X\) denote the two-element set \(\{0,1\}\). Then the set \(X^\omega\) is uncountable.

Proof

  • Let \(g : \mathbb{Z}_+ \rightarrow X^\omega\). Prove: \(g\) is not surjective.
  • Let \((a_n)\) be the sequence in \(X\) with \(a_n = 1\) iff \(g(n)_n = 0\) for \(n \in \mathbb{Z}_+\).
  • For all \(n \in \mathbb{Z}_+\), \(a_n \neq g(n)_n\).
  • For all \(n \in \mathbb{Z}_+\), \((a_n) \neq g(n)\).
  • \((a_n) \notin g(\mathbb{Z}_+)\)
  • \(\Box\)

Theorem 7.8

Let \(A\) be a set. There is no injective map \(\mathcal{P} A \rightarrow A\), and there is no surjective map \(A \rightarrow \mathcal{P} A\).

Proof

  • There is no surjective map \(A \rightarrow \mathcal{P} A\).
    • Let \(f : A \rightarrow \mathcal{P} A\). Prove: \(f\) is not surjective.
    • Let \(S = \{x \in A \mid x \notin f(x)\}\).
    • For all \(a \in A\) we have \(a \in S \Leftrightarrow a \notin f(a)\).
    • For all \(a \in A\) we have \(S \neq f(a)\).
    • \(S \notin f(A)\)
  • There is no injective map \(\mathcal{P} A \rightarrow A\).
    • Assume for a contradiction \(f : \mathcal{P} A \rightarrow A\) is injective.
    • Choose a function \(g : A \rightarrow \mathcal{P} A\) such that, for all \(a \in A\), we have \(f(g(a)) = a\).
    • \(g\) is surjective.

Comments

Post a Comment

Popular posts from this blog

J. Munkres. Topology (2013) Chapter 4: Countability and Separation Axioms. 32: Normal Spaces

Theorem 32.1 Every second countable regular space is normal. Proof Let \(X\) be a second countable regular space. Pick a countable basis \(\mathcal{B}\). Let \(A\) and \(B\) be disjoint closed sets in \(X\). Pick a countable covering \(\{U_1, U_2, \ldots\}\) of \(A\) by open sets whose closures are disjoint from \(B\). Let \(\{U_1, U_2, \ldots\} = \{U \in \mathcal{B} \mid \overline{U} \cap B = \emptyset\}\). Prove: this covers \(A\). Let \(x \in A\). Prove: there exists \(U \in \mathcal{B}\) such that \(x \in U\) and \(\overline{U} \cap B = \emptyset\). Pick disjoint open sets \(U\) and \(V\) such that \(x \in U\) and \(B \subseteq V\). By regularity. Pick \(U' \in \mathcal{B}\) such that \(x \in U' \subseteq U\). \(x \in U'\) and \(\overline{U'} \cap B \subseteq \overline{U} \cap B \subseteq (X - V) \cap B = \emptyset\) Pick a countable covering \(\{V_1, V_2, \ldots\}\) of \(B\) by open sets whose ...
Read more

J. Munkres. Topology (2013) Chapter 3: Connectedness and Compactness. 27: Compact Subspaces of the Real Line

Theorem 27.1 Let \(X\) be a linearly ordered set with the least upper bound property in the order topology. Every closed interval in \(X\) is compact. Proof Let \(a,b \in X\) with \(a Let \(\mathcal{A}\) be a covering of \([a,b]\) by sets open in \(X\). \( \langle 1 \rangle 1 \) For any \(x \in [a,b)\), there exists \(y \in (x,b]\) such that \([x,y]\) can be covered by at most two elements of \(\mathcal{A}\). Let \(x \in [a,b)\). Pick \(U \in \mathcal{A}\) such that \(x \in U\). Pick \(y > x\) such that \([x,y) \subseteq U\). Assume w.l.o.g. \(y \leq b\). Pick \(V \in \mathcal{A}\) such that \(y \in V\). \([x,y]\) is covered by \(U\) and \(V\). Let \(C = \{y \in (a,b] \mid [a,y] \text{ can be covered by finitely many elements of } \mathcal{A} \}\). Let \(c = \sup C\). \(C\) is nonempty. Pick \(y \in (a,b]\) such that \([a,y]\) can be covered by at most two elements of \(\mathcal{A}\). \(\...
Read more

J. Munkres. Topology (2013) Chapter 4: Countability and Separation Axioms. 31: The Separation Axioms

Definition A topological space \(X\) is regular iff it is \(T_1\) and, for any point \(x \in X\) and closed set \(B\) such that \(x \notin B\), there exist disjoint open sets \(U\) and \(V\) with \(x \in U\) and \(B \subseteq V\). A topological space \(X\) is normal iff it is \(T_1\) and, for any disjoint closed sets \(A\) and \(B\), there exist disjoint sets \(U\) and \(V\) with \(A \subseteq U\) and \(B \subseteq V\). Lemma 31.1 Let \(X\) be a \(T_1\) space. \(X\) is regular if and only if, for every point \(x \in X\) and neighbourhood \(U\) of \(x\), there exists a neighbourhood \(V\) of \(x\) such that \(\overline{V} \subseteq U\). \(X\) is normal if and only if, for every closed set \(A\) and open set \(U\) including \(A\), there exists an open set \(V\) including \(A\) such that \(\overline{V} \subseteq U\). Proof If \(X\) is regular then, for every point \(x \in X\) and neighbourhood \(U\) of \(x\), there exists a neighbourhood \(V\) of \(x\) such th...
Read more