離散-2

考研相關文章參考資料為 wjungle 大神提供的筆記

L2 關係與函數

L2-2 基本關係

定義

• reflexive (反身性): $R\text{ 具有反身性}\Longleftrightarrow\forall a\in A,\ (a,a)\in R$

• irreflexive (非反身性): $R\text{ 具有非反身性}\Longleftrightarrow\forall a\in A,\ (a,a)\notin R$

Note

若 $|A|=n$:

• $A$ 上的 binary relation 個數: $2^{n^2}$
• $A$ 上的 reflexive relation 個數: $2^{n^2-n}$
• $A$ 上的 irreflexive relation 個數: $2^{n^2-n}$

定義

• symmetric (對稱性): $\forall a,b\in A, aRb\Rightarrow bRa$

• asymmetric (非對稱性): $\forall a,b\in A, aRb\Rightarrow\neg(bRa)$

  • asymmetric relation 一定具有 irreflexive

• antisymmetric (反對稱性): $\forall a,b\in A, (aRb\land bRa)\Rightarrow a=b$

Note

若 $|A|=n$:

• $A$ 上的 symmetric relation 個數: $2^{\frac{n(n+1)}{2}}$
• $A$ 上的 asymmetric relation 個數: $3^{\binom{n}{2}}$
  • 對角線固定為 0
• $A$ 上的 antisymmetric relation 個數: $2^n\cdot3^{\binom{n}{2}}$
  • 對角線可 0/1

定義

• transitive (遞移性): $\forall a,b,c\in A,\ (aRb\land bRc)\Rightarrow aRc$
  • $\leq$、整除具有遞移性；$\neq$、朋友關係不具有遞移性

L2-3 等價關係

定義

equivalence relation (等價關係): $R\subseteq A\times A$ 同時具有 reflexive、symmetric、transitive

定義

若 $R$ 為 $A$ 上的 equivalence relation，$a\in A$:

$[a]=\{x\in A\mid xRa\}$ 稱為 $a$ 的 equivalence class (等價類)

定義

若 $A_1,\ldots,A_k\subseteq A$ 滿足:

• $A_i\neq\varnothing$
• $A_1\cup\cdots\cup A_k=A$ (cover)
• $A_i\cap A_j=\varnothing,\ \forall i\neq j$ (disjoint)

則稱 $\{A_1,\ldots,A_k\}$ 為 $A$ 的 partition (分割)。

定理

若 $R$ 為 $A$ 上的 equivalence relation，則 $P=\{[a]\mid a\in A\}$ 形成 $A$ 的 partition。

• 相異等價類會形成分割
• 等價關係與分割一一對應
  • 利用 $A$ 之所有可能分割數量來計算等價關係數量

定理

令 $P_n$ 表示 $n$ 個元素上的 equivalence relation 數量，則:

$P_0=1,\quad P_n=\sum_{i=0}^{n-1}\binom{n-1}{i}P_i\quad(n\geq1)$

• $P_0=1$
• $P_1=\binom00P_0=1$
• $P_2=\binom10P_0+\binom11P_1=2$
• $P_3=\binom20P_0+\binom21P_1+\binom22P_2=5$
• $P_4=\binom30P_0+\binom31P_1+\binom32P_2+\binom33P_3=15$
• $P_5=\binom40P_0+\binom41P_1+\binom42P_2+\binom43P_3+\binom44P_4=52$

L2-4 關係之包

定義

若 $R\subseteq A\times A$:

• $r(R)$: 包含 $R$ 的最小 reflexive relation，稱為 reflexive closure
  • $r(R)=R\cup I_A$，其中 $I_A=\{(a,a)\mid a\in A\}$
• $s(R)$: 包含 $R$ 的最小 symmetric relation，稱為 symmetric closure
  • $s(R)=R\cup R^{-1}$
• $t(R)$: 包含 $R$ 的最小 transitive relation，稱為 transitive closure
  • $t(R)=R^+=\displaystyle\bigcup_{k=1}^{\infty}R^k$
  • 若 $|A|=n$，則 $t(R)=R\cup R^2\cup\cdots\cup R^n$
  • 計算時先畫圖，之後依序補上:
    • 1 步可走到、2 步可走到…

包含 $R$ 的最小 XX-relation，稱為 XX-closure。

Note

若 $R_1,R_2$ 為 equivalence relation，對應的 partition 為 $\pi_1,\pi_2$:

• $R_1\cap R_2$ 仍為 equivalence relation，對應 partition 記為 $\pi_1\times\pi_2$
• $t(R_1\cup R_2)$ 為 equivalence relation，對應 partition 記為 $\pi_1+\pi_2$

範例

令:

• $\pi_1=\{\{a,b,c,d\},\{e,f,g\},\{h,i\},\{j,k\}\}$
• $\pi_2=\{\{a,b,c,h\},\{d,i\},\{e,f,j,k\},\{g\}\}$

則:

• $\pi_1\times\pi_2=\{\{a,b,c\},\{d\},\{e,f\},\{g\},\{h\},\{i\},\{j,k\}\}$
  • 取兩個 partition 中各集合的非空交集
• $\pi_1+\pi_2=\{\{a,b,c,d,h,i\},\{e,f,g,j,k\}\}$
  • 聯集對應關係後再取 transitive closure

L2-7 計數問題

定義

若存在 bijection (1-1, onto) $f:A\to B$，則稱 $A$ 與 $B$ 具有相同的 cardinality (基數)，記作 $A\sim B$。

定義

若 $A=\varnothing$，或存在 $n\in\mathbb{Z}^+$ 使得 $A\sim\{1,2,\ldots,n\}$，則稱 $A$ 為 finite set (有限集)；否則稱為 infinite set。

定義

若 $A$ 為 finite set，或 $A\sim\mathbb{Z}^+$，則稱 $A$ 為 countable set (可數集)。

Note

• 若 $A,B$ 為 countable set，則 $A\times B$ 也是 countable set
• 若每個 $A_i$ 皆為 countable set，則 $\displaystyle\bigcup_{i=1}^{\infty}A_i$ 也是 countable set

---

定理

$(0,1)$ 為 uncountable set (不可數集)。

對角線證法:
假設 $(0,1)$ 可數，則存在 onto function $f:\mathbb{Z}^+\to(0,1)$，將所有元素排列為:

$\begin{aligned} f(1)&=0.a_{11}a_{12}a_{13}\cdots\\ f(2)&=0.a_{21}a_{22}a_{23}\cdots\\ f(3)&=0.a_{31}a_{32}a_{33}\cdots \end{aligned}$

取 $x=0.x_1x_2x_3\cdots$，其中:

$x_i= \begin{cases} 5,&a_{ii}=4\\ 4,&a_{ii}\neq4 \end{cases}$

則 $x\in(0,1)$，且第 $i$ 位小數與 $f(i)$ 不同，所以 $x\neq f(i)$ 對所有 $i$ 皆成立，與 $f$ 為 onto 矛盾。因此 $(0,1)$ 不可數。

定理

$\mathbb{R}$ 為 uncountable set，且 $(0,1)\sim\mathbb{R}$。

定義:
$h(x)=\tan\left(\pi x-\frac{\pi}{2}\right),\qquad x\in(0,1)$

• $x\mapsto\pi x-\frac{\pi}{2}$ 為 $(0,1)$ 到 $\left(-\frac{\pi}{2},\frac{\pi}{2}\right)$ 的 bijection
• $\tan x$ 為該區間到 $\mathbb{R}$ 的 bijection

因此 $h:(0,1)\to\mathbb{R}$ 為 bijection。

故 $(0,1)\sim\mathbb{R}$；又 $(0,1)$ 不可數，所以 $\mathbb{R}$ 也不可數。

整理

countable set	uncountable set
任意有限集	$\mathbb{R}$
$\mathbb{N},\mathbb{Z}^+,\mathbb{Z}$	任意非退化實數區間，如 $(a,b),[a,b]$
$\mathbb{Z}^+\times\mathbb{Z}^+\sim\mathbb{Z}^+$	無理數集合 $\mathbb{R}\setminus\mathbb{Q}$
$\mathbb{Q}^+\sim\{(p,q)\in\mathbb{Z}^+\times\mathbb{Z}^+\mid\gcd(p,q)=1\}$ $\mathbb{Q}=\mathbb{Q}^+\cup(-\mathbb{Q}^+)\cup\{0\}$	$\mathbb{C}\sim\mathbb{R}^2\sim\mathbb{R}$
$\mathbb{N}^k,\mathbb{Z}^k,\mathbb{Q}^k$，其中 $k\in\mathbb{Z}^+$	$\mathbb{R}^k$，其中 $k\in\mathbb{Z}^+$
algebraic numbers (代數數)	transcendental numbers (超越數)
countable sets 的有限 Cartesian product	power set $\mathcal{P}(\mathbb{N})$
countable sets 的可數聯集	無窮二進位序列集合 $\{0,1\}^{\mathbb{N}}$