07.md

{{ book.discrete_mathematics.chapter2.2_7.title }}

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 {#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| $$