2-7. 計數問題

Theorem of Finite Set Relation

$|A|$ = $m$ < $\infty$, $|B|$ = $n$ < $\infty$,

• $f$: $A \rightarrow B$ 1-1 $\Rightarrow m \le n$

• $f$: $A \rightarrow B$ onto $\Rightarrow m \ge n$

• $f$: $A \rightarrow B$ 1-1 且 onto $\Rightarrow m$ = $n$

Define Cardinality

$A$, $B$: sets, 若 $\exists f$: $A \rightarrow B$ 為 1-1 且 onto, 稱 $A$ 與 $B$ 具相同之基數(cardinality): $|A|$ = $|B|$, 記作 $A \sim B$

$\sim$ 為一等價關係

Define Finite and Infinite Set

$A$: set, $A$ = $\emptyset$ 或 $\exists n \in Z^+$ s.t. $A \sim$ { $1$, $2$, ..., $n$ }, 稱 $A$ 為有限集(finite set) $\leftrightarrow A \ne \emptyset$ 且 $\nexists n \in Z^+$ s.t. $A \sim$ { $1$, $2$, ..., $n$ } 稱 $A$ 為無限集(infinite set)

Define Countable and Uncountable Set

$A$: set, $A$ 為有限集或 $A \sim Z^+$, 則稱 $A$ 為可數集(countable set) $\leftrightarrow A$ 為無限集且 $A \nsim Z^+$, 稱 $A$ 為不可數集(uncountable set)

$Z^+$ 為無限可數集(countably infinite set)

Theorem of Z is countable

$Z$ 為可數集

proof:

定義 $f$: $Z \rightarrow Z^+$ by $f$($x$) $= \begin{cases} 1 &\text{, if } x = 0 \\ 2x &\text{, if } x > 0 \\ -2x + 1 &\text{, if } x < 0 \end{cases}$

$x$	...	-2	-1	0	1	2	...
$f$($x$)	...	5	3	1	2	4	...

$\Rightarrow f$($x$): 1-1 且 onto $\therefore Z \sim Z^+$

Properties of Countable and Uncountable Set

• 有限集 $\Rightarrow$ 可數集

  可數集 $\nRightarrow$ 有限集, $^{ex.} Z^+$

• 不可數集 $\Rightarrow$ 無限集

  無限集 $\nRightarrow$ 不可數集, $^{ex.} Z^+$

• $A$, $B$: sets, $A \subseteq B$

  • $B$ is countable $\Rightarrow A$ is countable.

  • $B$ is uncountable $\Rightarrow A$ is uncountable.

Corollary of Countably Infinite Set

$A$: infinite set, $\exists f$: $A \rightarrow Z^+$ 1-1 $\Rightarrow A$ is countable.

Theorem of Positive Z Product

Countable

$Z^+ \times Z^+$ is countable.

proof:

定義 $f$: $Z^+ \times Z^+ \rightarrow Z^+$ by $f$($a$, $b$) = $2^a 3^b$ $\because$ 質因數分解必唯一 $\therefore f$ is 1-1 By Corollary of Countably Infinite Set, $f$: $Z^+ \times Z^+$ is countable.

Same Cardinality with Positive Z

$Z^+ \times Z^+ \sim Z^+$

proof:

定義 $f$: $Z^+ \times Z^+ \rightarrow Z^+$ by $f$($i$, $j$) = ($\displaystyle\sum_{k=1}^{i + j - 2} k$) + $j$ = $\dfrac{(i + j - 2)(i + j - 1)}{2}$ + $j$ $\Rightarrow$ 2 維陣列 $\rightarrow$ 1 維陣列，依對角線做編號

($i$, $j$)	(1, 1)	(2, 1)	(1, 2)	(3, 1)	(2, 2)	(1, 3)	...
$f$($i$, $j$)	1	2	3	4	5	6	...

$\Rightarrow f$: 1-1 且 onto $\therefore Z^+ \times Z^+ \sim Z^+$

Corollary of Positive Z Product

• $A$, $B$: countable $\Rightarrow A \times B$: countable.

• $A_i$ is countable, $\forall i$ = $1$, $2$, ... $\Rightarrow \displaystyle\bigcup_{i=1}^\infty A_i$ is countable.

• $Q^+$ = { $\dfrac{q}{p}$ | $p$, $q \in Z^+$ } $\subseteq X$ = { $\dfrac{q}{p}$ | $p$, $q \in Z^+$, 不考慮約分 } $\sim$ { ($p$, $q$) | $p$, $q \in Z^+$ } = $Z^+ \times Z^+ \sim Z^+$ is countable $\Rightarrow Q^+$ is countable.

  所有正有理數所成集合 $Q^+$ 為可數集

• $Q$ = $Q^+ \cup Q^- \cup$ { $0$ } is countable.

  所有有理數所成集合 $Q$ 為可數集

Theorem of Zero-one Interval

[$0$, $1$] 為不可數集

proof:

設 [$0$, $1$] is countable $\Rightarrow Z^+ \sim$ [$0$, $1$] $\Rightarrow \exists f$: $Z^+ \rightarrow$ [$0$, $1$] 1-1 且 onto 令 $f$($i$) = $r_i$ = $0.{a_{i1}}{a_{i2}}...$, $\forall i$ = $1$, $2$, ...

$r_1$ = $0.{\color{red}{a_{11}}}{a_{12}}{a_{13}} \ldots$ $r_2$ = $0.{a_{21}}{\color{red}{a_{22}}}{a_{23}} \ldots$ $r_1$ = $0.{a_{31}}{a_{32}}{\color{red}{a_{33}}} \ldots$ $\; \vdots \qquad \, \enspace \vdots \quad \vdots \quad \vdots \, \ddots$

取 $X$ = $0.{x_1}{x_2}{x_3} \ldots$, 其中 $x_i = \begin{cases} 5 &\text{, if } {\color{red}{a_{ii}}} = 4 \\ 4 &\text{, if } {\color{red}{a_{ii}}} \ne 4 \end{cases}$, $\forall i$ = $1$, $2$, ..., 則 $X \in$ [$0$, $1$] 但 $X \ne f$($i$), $\forall i$ = $1$, $2$, ... $\Rightarrow$ 與 $f$ 為 onto 矛盾 $\therefore$ [$0$, $1$] is uncountable.

Theorem of R and Zero-one Interval

$R$ 為不可數集且 [$0$, $1$] $\sim R$

proof:

$\rightarrow$ 用漸近線 定義 $f$: [$0$, $1$] $\rightarrow$ [-$\dfrac{\pi}{2}$, $\dfrac{\pi}{2}$] 為 $f$($x$) = $\pi{x}$ - $\dfrac{\pi}{2}$

[-$\dfrac{\pi}{2}$, $\dfrac{\pi}{2}$]: $y$ = $\tan{x}$

又定義 $g$: [-$\dfrac{\pi}{2}$, $\dfrac{\pi}{2}$] $\rightarrow R$ 為 $g$($x$) = $\tan{x}$, 則 $f$, $g$: 1-1 且 onto 取 $h$: [$0$, $1$] $\rightarrow R$ 為 $h$($x$) = ($g$ $\tiny{\circ}$ $f$)($x$) = $\tan$($\pi{x}$ - $\dfrac{\pi}{2}$), 則 $h$ 亦為 1-1 且 onto $\therefore$ [$0$, $1$] $\sim R$

Comparison of All Numbers

• $A$ is uncountable, $B$ is countable $\Rightarrow A$ - $B$ is uncountable.

  $\because A$(uncountable) = ($A$ - $B$) $\cup$ ($A \cap B$)(countable) $\therefore A$ - $B$ is uncountable.

• $\overline{Q}$ = $R$(uncountable) - $Q$(countable) $\Rightarrow$ uncountable

• $C \sim R^2 \sim R \Rightarrow$ uncountable

  $C \sim R^2$: $a$ + $bi \Rightarrow$ ($a$, $b$)

$\rightarrow \Large{|Z^+|}$ = $\Large{|Z|}$ = $\Large{|Q|}$ $\Large{\color{red}{<}}$ $\Large{|\overline{Q}|}$ = $\Large{|R|}$ = $\Large{|C|}$

• countable $\leftarrow$ $\Large{\color{red}{<}}$ $\rightarrow$ uncountable

• $|P(Z^+)|$ = $|R|$