Cantor’s Diagonal Argument

1890/91, Cantor (1845-1918)

THEOREM: $|(0,1)| \neq |\mathbb{Z}^+|$

• Suppose that $|(0,1)| = |\mathbb{Z}^+|$. Then there is a bijection $f: \mathbb{Z}^+ \to (0,1)$

• Let $b_i = \begin{cases} 4, & b_{ii} \neq 4 \\ 5, & b_{ii} = 4 \end{cases}$ for $i = 1,2,3,\dots$
• $b = 0.b_1b_2b_3b_4b_5b_6b_7b_8b_9\cdots$ is in $(0,1)$
• $b = 0.b_1b_2b_3b_4b_5b_6b_7b_8b_9$ must have a preimage
  • however, $b \neq f(i)$ for every $i = 1,2,\dots$
• $f$ cannot be a bijection

Cantor’s Theorem

THEOREM (Cantor) Let $A$ be any set. Then $|A| < |\mathcal{P}(A)|$.

• $\mathcal{P}(A)$: the power set of a set $A$, i.e., the set of all subsets of $A$
  • For example: $\mathcal{P}(\{1,2\}) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$
• $|A| \leq |\mathcal{P}(A)|$
  • The function $f: A \to \mathcal{P}(A)$ defined by $f(a) = \{a\}$ is injective.
• $|A| \neq |\mathcal{P}(A)|$
  • Assume that there is a bijection $g: A \to \mathcal{P}(A)$
  • Define two lists $L = \{a\}_{a\in A}$($= A$) and $R = \{g(a)\}_{a\in A}$($= \mathcal{P}(A)$)
  • Define $X = \{a: a \in A \text{ and } a \notin g(a)\}$
  • We must have that $X \in R$.
    • $X = g(x)$ for some $x \in A$
      • If $x \in X$, then $x \notin g(x) = X$
      • If $x \notin X$, then $x \in g(x) = X$

The Halting Problem

Function$\text{HALT}(P, I) =\begin{cases}\text{“halts”} & \text{if } P(I) \text{ halts}; \\\text{“loops forever”} & \text{if } P(I) \text{ loops forever}.\end{cases}$

• $P$: a program; $I$: an input to the program $P$.

QUESTION: Is there a Turing machine computing $\text{HALT}$?

• Turing machine: can be represented as an element of $\{0,1\}^*$
• $\{0,1\}^* = \cup_{n\geq 0}\{0,1\}^n$: the set of all finite bit strings

THEOREM: There is no Turing machine computing $\text{HALT}$.

• Assume there is a Turing machine $\textbf{HALT}$ computing $\text{HALT}$
• Define a new Turing machine $\textbf{Turing}(P)$ that runs on any Turing machine $P$
  • If $\textbf{HALT}(P, P) =$ “halts”, loops forever
  • If $\textbf{HALT}(P, P) =$ “loops forever”, halts
• $\textbf{Turing}(\textbf{Turing})$ loops forever $\implies \textbf{HALT}(\textbf{Turing}, \textbf{Turing}) =$ “halts” $\implies \textbf{Turing}(\textbf{Turing})$ halts
• $\textbf{Turing}(\textbf{Turing})$ halts $\implies \textbf{HALT}(\textbf{Turing}, \textbf{Turing}) =$ “loops forever” $\implies \textbf{Turing}(\textbf{Turing})$ loops forever

Countable and Uncountable

DEFINITION: A set $A$ is countable if $|A| < \infty$ or $|A| = |\mathbb{Z}^+|$; otherwise, it is said to be uncountable.

• countably infinite: $|A| = |\mathbb{Z}^+|$

EXAMPLE: $\mathbb{Z}^-, \mathbb{Z}^+, \mathbb{Z}, \mathbb{N}, \mathbb{Q}^-, \mathbb{Q}^+, \mathbb{Q}$ are countable; $\mathbb{R}^-, \mathbb{R}^+, \mathbb{R}, (0,1), [0,1], (0,1], [0,1)$ are uncountable.

THEOREM: A set $A$ is countably infinite if and only if its elements can be arranged as a sequence $a_1, a_2, \dots$

• If $A$ is countably infinite, then there is a bijection $f: \mathbb{Z}^+ \to A$
  • $a_i = f(i)$ for every $i = 1,2,3 \dots$
• If $A = \{a_1, a_2, \dots\}$, then the $f: \mathbb{Z}^+ \to A$ defined by $f(i) = a_i$ is a bijection

THEOREM: Let $A$ be countably infinite, then any infinite subset $X \subseteq A$ is countable.

• Let $A = \{a_1, a_2, \dots\}$. Then $X = \{a_{i_1}, a_{i_2}, \dots\}$

THEOREM: Let $A$ be uncountable, then any set $X \supseteq A$ is uncountable.

• If $X$ is countable, then $A$ is finite or countably infinite

THEOREM: If $A, B$ are countably infinite, then so is $A \cup B$

• $A = \{a_1, a_2, a_3, \dots\}, B = \{b_1, b_2, b_3, \dots\}$
• $A \cup B = \{a_1, b_1, a_2, b_2, a_3, b_3, \dots\}$ // no elements will be included twice
  • Application: the set of irrational numbers is uncountable

THEOREM: If $A, B$ are countably infinite, then so is $A \times B$

• $A = \{a_1, a_2, a_3, \dots\}, B = \{b_1, b_2, b_3, \dots\}$
• $A \times B = \{(a_1, b_1), (a_1, b_2), (a_2, b_1), (a_1, b_3), (a_2, b_2), (a_3, b_1), (a_1, b_4), \dots\}$

Schröder-Bernstein Theorem

QUESTION: How to compare the cardinality of sets in general?

• $|\mathbb{Z}^-| = |\mathbb{Z}^+| = |\mathbb{Z}| = |\mathbb{N}| = |\mathbb{Q}^-| = |\mathbb{Q}^+| = |\mathbb{Q}| = |\mathbb{N} \times \mathbb{N}|$
• $|\mathbb{R}^-| = |\mathbb{R}^+| = |\mathbb{R}| = |(0,1)| = |[0,1]| = |(0,1]| = |[0,1)|$
• $|\mathbb{Z}^+| < |[0,1)|$
• $|\mathbb{Z}^+| < |\mathcal{P}(\mathbb{Z}^+)|$
• $|\mathcal{P}(\mathbb{Z}^+)|\,?\,|[0,1)|$

THEOREM: If $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$.

EXAMPLE: Show that $|(0,1)| = |[0,1)|$

• $|(0,1)| \leq |[0,1)|$
  • $f: (0,1) \to [0,1),\ x \mapsto \frac{x}{2}$ is injective
• $|[0,1)| \leq |(0,1)|$
  • $g: [0,1) \to (0,1),\ x \mapsto \frac{x}{4} + \frac{1}{2}$ is injective

EXAMPLE: $|\mathcal{P}(\mathbb{Z}^+)| = |[0,1)|$

• $|\mathcal{P}(\mathbb{Z}^+)| \leq |[0,1)|$
  • $f: \mathcal{P}(\mathbb{Z}^+) \to [0,1),\ \{a_1, a_2, \dots\} \mapsto 0.\dots 1_{a_1} \dots 1_{a_2} \dots$ is an injection.
• $|[0,1)| \leq |\mathcal{P}(\mathbb{Z}^+)|$
  • $\forall x \in [0,1), x = 0.r_1r_2\dots$ ($r_1, r_2, \dots \in \{0, \dots, 9\}$, no $\dot{9}$)
    • $0 \leftrightarrow 0000, 1 \leftrightarrow 0001, \dots, 9 \leftrightarrow 1001$
    • $x$ has a binary representation $x = 0.b_1b_2\dots$
      • $f: [0,1) \to \mathcal{P}(\mathbb{Z}^+),\ x \mapsto \{i: i \in \mathbb{Z}^+, b_i = 1\}$ is an injection

THEOREM: $\underset{\aleph_0}{{|\mathbb{Z}^+|}} < \underset{2^{\aleph_0}}{{|\mathcal{P}(\mathbb{Z}^+)|}} = |[0,1)| = |(0,1)| = \underset{c}{{|\mathbb{R}|}}$

The Continuum Hypothesis: There is no cardinal number between $\aleph_0$ and $c$, i.e., there is no set $A$ such that $\aleph_0 < |A| < c$.

Basic Rules of Counting

DEFINITION: Let $A$ be a finite set. A partition of set $A$ is a family $\{A_1, A_2, \dots, A_k\}$ of nonempty subsets of $A$ such that

• $\bigcup_{i=1}^k A_i = A$
• $A_i \cap A_j = \emptyset$ for all $i,j \in [k]$ with $i \neq j$.

The Sum Rule: Let $A$ be a finite set. Let $\{A_1, A_2, …, A_k\}$ be a partition of $A$. Then $|A| = |A_1| + |A_2| + \dots + |A_k|$.

The Product Rule: Let $A_1, A_2, …, A_k$ be finite sets. Then $|A_1 \times A_2 \times \dots \times A_k| = |A_1| \times |A_2| \times \dots \times |A_k|$.

The Bijection Rule: Let $A$ and $B$ be two finite sets. If there is a bijection $f: A \to B$, then $|A| = |B|$.

Permutations of Set

DEFINITION: Let $A = \{a_1, …, a_n\}$ and $r \in [n]$. An $r$-permutation of $A$ is a sequence of $r$distinct elements of A.

• An $n$-permutation of $A$ is simply called a permutation of $A$.
  • The 2-permutations of $A = \{1,2,3\}$ are $1,2$; $1,3$; $2,1$; $2,3$; $3,1$; $3,2$

THEOREM: An $n$-element set has $P(n,r) = \frac{n!}{(n-r)!}$ different $r$-permutations.

DEFINITION: Let $A = \{a_1, …, a_n\}$ and $r \geq 1$. An $r$-permutation of $A$ with repetition is a sequence of $r$ elements of $A$.

• The 2-permutations of $A = \{1,2,3\}$ with repetition are:
  • $1,1$; $1,2$; $1,3$; $2,1$; $2,2$; $2,3$; $3,1$; $3,2$; $3,3$

THEOREM: An $n$-element set has $n^r$ different $r$-permutations with repetition.

Multiset

DEFINITION: A multiset is a collection of elements which are not necessarily different from each other.

• An element $x \in A$ has multiplicity$m$ if it appears $m$ times in $A$.
• A multiset $A$ is called an $n$-multiset if it has $n$ elements.
• $A = \{n_1 \cdot a_1, n_2 \cdot a_2, …, n_k \cdot a_k\}$: an $(n_1 + n_2 + \dots + n_k)$-multiset
  • $a_i$ has multiplicity $n_i$ for all $i \in [n]$.
• $T = \{t_1 \cdot a_1, t_2 \cdot a_2, …, t_k \cdot a_k\}$ is called an $r$-subset of $A$ if:
  • $0 \leq t_i \leq n_i$ for every $i \in [k]$, and
  • $t_1 + t_2 + \dots + t_k = r$

EXAMPLE: $A = \{1 \cdot a, 2 \cdot b, 3 \cdot c, 100 \cdot z\}$, $T = \{1 \cdot b, 98 \cdot z\}$

• $A$ is a 106-multiset; the multiplicities of $a,b,c,z$ are $1,2,3,100$, respectively.
• $T$ is a 99-subset of $A$

Permutations of Multiset

DEFINITION: Let $A = \{n_1 \cdot a_1, …, n_k \cdot a_k\}$ be an $n$-multiset. A permutation of $A$ is a sequence $x_1, x_2, \dots, x_n$ of $n$ elements, where $a_i$ appears exactly $n_i$ times for every $i \in [k]$.

• $r$-permutation of $A$: a permutation of some $r$-subset of $A$
  • Example: $A = \{1 \cdot a, 2 \cdot b, 3 \cdot c\}$
  • $a,b,c,b,c,c$ is a permutation of $A$; $b,c,b$ is a 3-permutation of $A$;

THEOREM: Let $A = \{n_1 \cdot a_1, n_2 \cdot a_2, …, n_k \cdot a_k\}$ be a multiset. Then $A$ has exactly $\frac{(n_1+n_2+\dots+n_k)!}{n_1!n_2!\dots n_k!}$ permutations.

REMARK: Let $A = \{a_1, a_2, …, a_n\}$ be a set of $n$ elements.

• $r$-permutation of $A$ w/o repetition: $r$-permutation of $\{1 \cdot a_1, …, 1 \cdot a_n\}$.
• $r$-permutation of $A$ with repetition: $r$-permutation of $\{\infty \cdot a_1, …, \infty \cdot a_n\}$.