Skip to content

12.30 Infinite set

Infinite Sets

  • Denumerable: \(\approx \mathbb{N}\) (\(\exists\) bijection)
  • Uncountable

Denumerable

We say \(A\) is denumerable if \(A\) can be written as \(A = \{ a_1, a_2, a_3, a_4, \dots \}\) where

  1. the set has no repetitions.

  2. Any \(a \in A\) shows up in the sequence.

Example

  1. \(\mathbb{N}\)

  2. \(\mathbb{Z} = \{ 0, 1, -1, 2, -2, 3, -3, \dots \}\)

The bijective function \(f: \mathbb{N} \to \mathbb{Z}\) is: \(f(2k) = k\) and \(f(2k+1) = -k\)

Lemma:

If \(S\) is an infinite set and \(S \subseteq \mathbb{N}\), then \(S\) is denumerable.

Proof

Let:

  • \(S_1 = \min S\)
  • \(S_2 = \min (S - \{ S_1 \})\)
  • \(\vdots\)
  • \(S_n = \min (S - \{ S_1, S_2, \dots, S_{n-1} \})\)

\(\uparrow\) no repetitions.

We prove that \(S = \{ S_1, S_2, \dots \}\).

Take \(s \in S\). Since \(S_1 < S_2 < S_3 < \dots\), \(\exists \, n\) such that \(s<S_{n}=\min(S-\{S_1,\dots,S_{n-1}\})\).

So \(s \notin (S - \{ S_1, \dots, S_{n-1} \})\), thus \(s\in\{S_1,S_2,\dots,S_{n-1}\}\). So \(S = S_k\) for some \(k\).

Example

\(\mathbb{N} \times \mathbb{N}\) is denumerable.

Define \(f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) by \(f(a, b) = 2^a 3^b\)

This function is injective by the Fundamental theorem of arithmetic

If \(2^{a} 3^{b} = 2^{a'} 3^{b'}\), \(\implies a = a'\), \(b = b'\)​\(\implies \mathbb{N} \times \mathbb{N} \approx \text{Im } f \subseteq \mathbb{N}\) (infinite subset).

So by the Lemma \(\text{Im } f \approx \mathbb{N}\). Finally, \(\mathbb{N} \times \mathbb{N} \approx \mathbb{N}\) by transitivity.

Countable

A set \(A\) is called countable if \(A\) is denumerable or finite.

image​

Proposition

\(A\) is countable \(\iff\)​\(\exists f:A\to \N\) is injective

Proof

If \(A\) is finite, by construction....

If \(A\) is denumerable, then by definition of denumerable it is bijective, in particular is injective.

Proposition:

  1. \(A \subseteq B\), \(B\) countable \(\implies A\) countable.

    Proof

    Since \(B\) is countable, \(\exists i: B \to \mathbb{N}\) injective.

    Then \(i\left|_{A}:A\to\mathbb{N}\right.\) is also injective, so \(A\) is countable.

  2. \(A\), \(B\) countable \(\implies A \cup B\) countable.

    Proof

    Since \(A \cup B = A \cup (B - A)\) where \(A\) and \(B\) is countable, then \(B-A\) is also countable

    Then \(\exists f:A\left(\to\mathbb{N}\right)\to\mathbb{N}^{\prime}\) where \(x\mapsto x\mapsto 2x\) even number and all are injective

    \(\exists g:B-A\left(\to\mathbb{N}\right)\rightarrow\mathbb{N}^{\prime}\) where \(x\mapsto x\mapsto2x+1\) odd number and all are injective

    Define \(h: A \cup (B - A) \to \mathbb{N}\) as \(h(x) = \begin{cases} f(x), & \text{if } x \in A, \\ g(x), & \text{if } x \in B - A. \end{cases}\)

    Then \(h\) is injective.

    \(\therefore A \cup B = A \cup (B - A)\) is countable.

    We use this principle to construct function

    If:

    • \(f: A \to X\) injective,
    • \(g: B \to Y\) injective,

    and if \(A \cap B = \emptyset\), \(X \cap Y = \emptyset\), then \(\exists h: A \cup B \to X \cup Y\) injective.

  3. \(A\), \(B\) countable \(\implies A \times B\) countable.

    Proof

    Since \(\exists f: A \to \mathbb{N}\) injective, \(\exists g: B \to \mathbb{N}\) injective.

    Take \(f \times g: A \times B \to \mathbb{N} \times \mathbb{N}\) injective, \((a, b) \to (f(a), g(b))\).

    Since \(\exists \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) injective, then take the composition \(A \times B \to \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) injective.

  4. If \((A_i )_{i \in \mathbb{N}}\) is a family of countable sets, then \(\bigcup_{i=1}^{\infty}A_{i}\) countable.

    Proof

    \(\bigcup_{i=1}^\infty A_i = \{a : \exists i \text{ such that } a \in A_i \}\)​

    Define \(B_n = A_1 \cup \dots \cup A_n\). Then \(\bigcup_{i=1}^\infty A_i = \bigcup_{i=1}^\infty B_i\) and \(B_n\) is countable by induction of 2

    And \(B_1 \subseteq B_2 \subseteq B_3 \subseteq \dots\)

    Define \(C_1 = B_1\)(countable), \(C_2 = B_2 - B_1\) (countable), \(C_3 = B_3 - B_2, \dots\)

    image​

    Note that:

    1. \(\bigcup_{i=1}^\infty C_i = \bigcup_{i=1}^\infty B_i = \bigcup_{i=1}^\infty A_i\).
    2. \(C_i \cap C_j = \emptyset \; \forall i \neq j\).
    3. \(C_i\) is countable.

    Let \(f_n: C_n \to \mathbb{N}\) be an injective function.

    Define \(F: \bigcup_{n=1}^\infty C_n \to \mathbb{N} \times \mathbb{N}\) as if \(x \in C_n\), then \(F(x)=(f_{n}(x),n)\in\mathbb{N}\times\{n\}\)

    \(F(C_n) \subset \mathbb{N} \times \{n\}\) and \(F(C_{m})\subset\mathbb{N}\times\{m\}\) and \(F(C_n) \cap F(C_m) = \emptyset\) for \(n \neq m\).

    Then \(F\) is injective. We take the composition of \(F\) with some injective function \(\mathbb{N} \times \mathbb{N} \to \mathbb{N}\).

Examples

\(\mathbb{Q}\) is denumerable.

\(\mathbb{Q} = \mathbb{Q}_{>0} \cup \{ 0 \} \cup \mathbb{Q}_{<0}\), and \(\mathbb{Q}_{>0} \approx \mathbb{Q}_{<0}\).

It is enough to show that \(\mathbb{Q}_{>0}\) is denumerable.

Any \(q \in \mathbb{Q}_{>0}\) can be written as \(q = \frac{a}{b}\), such that \(a, b \in \mathbb{N}\) in a unique way, where \(\gcd(a, b) = 1\).

So \(\exists \mathbb{Q}_{>0} \to \mathbb{N} \times \mathbb{N}\) injective \(q = \frac{a}{b} \; (\gcd(a, b) = 1) \mapsto (a, b)\).

\(\therefore \mathbb{Q}_{>0} \approx\) some subset of \(\mathbb{N} \times \mathbb{N}\), so \(\mathbb{Q}_{>0}\) is countable and infinite (\(\N\subseteq\mathbb{Q}_{>0}\)​).

\(\therefore \mathbb{Q}_{>0}\) is denumerable, so \(\mathbb{Q}\) is also denumerable.

Example

\(\mathbb{N} \times \mathbb{N} \times \mathbb{N}\) is denumerable.

\(\mathbb{N}^n = \underbrace{\mathbb{N} \times \mathbb{N} \times \dots \times \mathbb{N}}_{n}\) is denumerable.

Examples of uncountable sets

\(\mathbb{N}^\mathbb{N} = \{(x_1, x_2, x_3, \dots) : x_i \in \mathbb{N}\}\) is uncountable.

Theorem(More general)

If \(X\) has at least 2 elements, then \(X^\mathbb{N} = \{(x_1, x_2, x_3, \dots) : x_i \in X\}\) is uncountable.

Proof: (Cantor's diagonal method)

Assume that there is some enumeration for \(X^\mathbb{N}\):

  • \(S_1 = (x_{11}, x_{12}, x_{13}, x_{14}, \dots)\)
  • \(S_2 = (x_{21}, x_{22}, x_{23}, x_{24}, \dots)\)
  • \(S_3 = (x_{31}, x_{32}, x_{33}, x_{34}, \dots)\)
  • \(\dots\)

Exercise: Show that \(X^\mathbb{N}\) is infinite.

Suppose \(X^\mathbb{N}\) is finite, then \(|X^\mathbb{N}| = m\).

\(S_1 = (x_{11}, x_{12}, \dots)\) \(S_2 = (x_{21}, x_{22}, \dots)\) \(\vdots\) \(S_m = (x_{m1}, x_{m2}, \dots)\)

However, since Cantor's theorem, we can construct \(S_{m+1}\) where:

\(x_{(m+1)1}\neq x_{11},\quad x_{(m+1)2}\neq x_{22},\quad\dots,\quad x_{\left(m+1\right)\left(m-1\right)}\neq x_{\left(m-1)\left(\right.m-1\right)},\quad x_{(m+1)m}\neq x_{mm}.\)

Thus \(S_{m+1} \notin \{S_1, S_2, \dots, S_m\}\) but \(S_{m+1} \in X^\mathbb{N}\), leading to a contradiction.

Choose \(b_{i}\in X-\{x_{ii}\}\) (Axiom of Choice).

Let \(s = (b_1, b_2, b_3, \dots) \in X^\mathbb{N}\).

We show that \(s \neq s_n \; \forall n\). In fact, if \(s = s_n\) for some \(n\), then \(b_i = x_{ni} \; \forall i\).

In particular, \(b_n = x_{nn}\).

But this is not possible because \(b_n \in X - \{x_{nn}\}\). So \(s \neq s_n \; \forall n\).

Hence, \(X^\mathbb{N}\) cannot be denumerated.

Corollary

\(\mathcal{P}(\mathbb{N})\) is uncountable.

Proof:
\(\mathcal{P}(\mathbb{N}) \approx \{0, 1\}^\mathbb{N}\)(characteristic function), so we can apply the theorem with \(X = \{0, 1\}\).

Exercise:
​\(\mathcal{P}_{n}(\mathbb{N})=\{S\subset\mathbb{N}\mid\left|S\right|=n\}\) is countable.

Consider the natural function \(\mathbb{N}^n \to \bigcup_{1 \leq k \leq n} \mathcal{P}_k(\mathbb{N})\) given by:

\[ (x_1, x_2, \dots, x_n) \mapsto \{x_1, x_2, \dots, x_n\}. \]

This is clearly surjective and therefore:

\[ |\mathcal{P}_{n}(\mathbb{N})|\leq\left|\left(\bigcup_{1\leq k\leq n}\mathcal{P}_{k}(\mathbb{N})\right)\right|\leq|\mathbb{N}^{n}|=|\mathbb{N}| \]

Theorem

\(\mathbb{R}\) is uncountable.

Proof:

  1. \(\mathbb{R}\approx\mathbb{R}_{>0}\approx\mathbb{R}_{>1}\approx(0,1)\) via \(x\mapsto e^{x}\mapsto e^{x}+1\mapsto\frac{1}{e^{x}+1}\) where we also have \(x\mapsto\ln x\) to get the inverse of exponential function

  2. Any \(x \in (0, 1)\) has a unique decimal representation: \(x = 0.a_1a_2a_3a_4\ldots\), where:

    • \(a_i \in \{0, 1, \dots, 9\}\)​
    • \(a_i \neq 0\) for infinitely many \(i\).

    For example, \(0.1250000\ldots\times\left(\text{ not good }\right)=0.1249999\ldots\checkmark\)​

    Then our goal is to prove \((0,1)\) is uncountable

    Assume that \((0, 1)\) is countable. So there is an enumeration:

    • \(S_1 = 0.a_{11}a_{12}a_{13}\dots\)
    • \(S_2 = 0.a_{21}a_{22}a_{23}\dots\)
    • \(S_3 = 0.a_{31}a_{32}a_{33}\dots\)
    • \(\dots\)

    Let \(b_{i}\in\{1,2,\dots,9\}-\{a_{ii}\}\) and take \(s = 0.b_1b_2b_3b_4\ldots\). Then \(s\) does not appear in the list.

    Thus, \((0, 1)\) is uncountable.

‍