以下證明中，R = R R=\mathbb R R = R Q = Q Q=\mathbb Q Q = Q C = C C=\mathbb C C = C Z = Z Z=\mathbb Z Z = Z N = N = { 0 , 1 , 2 , … } N=\mathbb N=\{0,1,2,\ldots\} N = N = { 0 , 1 , 2 , … }
用來比較集合的函數
設 f : X → Y f:X\to Y f : X → Y
f ( X ) = { f ( x ) ∣ x ∈ X } ⊆ Y , f(X)=\{f(x)\mid x\in X\}\subseteq Y, f ( X ) = { f ( x ) ∣ x ∈ X } ⊆ Y , 對 B ⊆ Y B\subseteq Y B ⊆ Y
f − 1 ( B ) = { x ∈ X ∣ f ( x ) ∈ B } . f^{-1}(B)=\{x\in X\mid f(x)\in B\}. f − 1 ( B ) = { x ∈ X ∣ f ( x ) ∈ B } . 記號 f − 1 ( y ) f^{-1}(y) f − 1 ( y ) { y } \{y\} { y }
定義
單射、滿射與雙射 函數 f : X → Y f:X\to Y f : X → Y 單射 ，如果
f ( x 1 ) = f ( x 2 ) ⟹ x 1 = x 2 ( x 1 , x 2 ∈ X ) . f(x_1)=f(x_2)\Longrightarrow x_1=x_2
\qquad (x_1,x_2\in X). f ( x 1 ) = f ( x 2 ) ⟹ x 1 = x 2 ( x 1 , x 2 ∈ X ) . 因此 Y Y Y 滿射 ，如果
∀ y ∈ Y ∃ x ∈ X 使得 f ( x ) = y , \forall y\in Y\;\exists x\in X\text{ 使得 }f(x)=y, ∀ y ∈ Y ∃ x ∈ X 使得 f ( x ) = y , 等價地說 f ( X ) = Y f(X)=Y f ( X ) = Y 雙射 。
陪域很重要。例如 f : N → N f:N\to N f : N → N f ( n ) = n + 1 f(n)=n+1 f ( n ) = n + 1 0 0 0 N ∖ { 0 } N\setminus\{0\} N ∖ { 0 }
例題
檢查三種性質 考慮 u : { 0 , 1 , 2 } → { a , b , c , d } u:\{0,1,2\}\to\{a,b,c,d\} u : { 0 , 1 , 2 } → { a , b , c , d }
u ( 0 ) = a , u ( 1 ) = c , u ( 2 ) = a . u(0)=a,\qquad u(1)=c,\qquad u(2)=a. u ( 0 ) = a , u ( 1 ) = c , u ( 2 ) = a . 它不是單射，因為 u ( 0 ) = u ( 2 ) u(0)=u(2) u ( 0 ) = u ( 2 ) 0 ≠ 2 0\ne2 0 = 2 b b b d d d
相同基數與可數性
概念視角 結構
把基數理解為數數與配對 對於有限集合，大小很容易令人聯想到清點：把元素逐一數出來。對於任意集合，定義則把這種清點改成配對檢驗：能否把 X X X Y Y Y N N N 2 N = { 0 , 2 , 4 , … } 2N=\{0,2,4,\ldots\} 2 N = { 0 , 2 , 4 , … } n ↦ 2 n n\mapsto 2n n ↦ 2 n 2 N 2N 2 N N N N
定義
相同基數 若存在雙射 f : X → Y f:X\to Y f : X → Y X X X Y Y Y 相同基數 ，並寫成
∣ X ∣ = ∣ Y ∣ |X|=|Y| ∣ X ∣ = ∣ Y ∣ 被配對的元素不必具有相同性質。把數與有序對配對，與把兩列數字配對一樣合
法。對有限集合，這個定義與普通數數一致。
定義
有限集合 若某個 n ∈ N n\in N n ∈ N ∣ X ∣ = ∣ n ∣ |X|=|n| ∣ X ∣ = ∣ n ∣ n n n n = { 0 , … , n − 1 } n=\{0,\ldots,n-1\} n = { 0 , … , n − 1 } n = 0 n=0 n = 0 n = ∅ n=\varnothing n = ∅ X X X 有限集合 ，並寫 ∣ X ∣ = n |X|=n ∣ X ∣ = n ∣ ∅ ∣ = 0 |\varnothing|=0 ∣ ∅ ∣ = 0
定義
可數與至多可數 在本課程中，如果 X X X
∣ X ∣ = ∣ N ∣ |X|=|N| ∣ X ∣ = ∣ N ∣ 就稱 X X X 可數 。等價地，若 X X X 至多可數 。有
些教材只把無限情形稱為 countable，因此「至多可數」可以消除這種約定差異。
不是至多可數的集合稱為不可數 。
對可數無限集合來說，一個列舉是序列 x 0 , x 1 , x 2 , … x_0,x_1,x_2,\ldots x 0 , x 1 , x 2 , …
可數集合的明確列舉
整數
設 N = { 0 , 1 , 2 , … } N=\{0,1,2,\ldots\} N = { 0 , 1 , 2 , … }
e ( 0 ) = 0 , e ( 2 k − 1 ) = k , e ( 2 k ) = − k ( k ≥ 1 ) e(0)=0,\qquad e(2k-1)=k,\qquad e(2k)=-k\quad(k\ge1) e ( 0 ) = 0 , e ( 2 k − 1 ) = k , e ( 2 k ) = − k ( k ≥ 1 ) 這給出序列 0 , 1 , − 1 , 2 , − 2 , 3 , − 3 , … 0,1,-1,2,-2,3,-3,\ldots 0 , 1 , − 1 , 2 , − 2 , 3 , − 3 , …
證明。 每個整數或者是 0 0 0 k k k k ≥ 1 k\ge1 k ≥ 1 − k -k − k 0 0 0 2 k − 1 2k-1 2 k − 1 2 k 2k 2 k e e e k k k e e e e e e N N N 1 1 1
這個例子體現無限集合的基本驚訝之處：把所有負整數加入 N N N
有理數
定理
有理數是可數的 有理數集合 Q Q Q
每個正有理數都有唯一的最簡表示 p / q p/q p / q p , q ∈ { 1 , 2 , 3 , … } p,q\in\{1,2,3,\ldots\} p , q ∈ { 1 , 2 , 3 , … } gcd ( p , q ) = 1 \gcd(p,q)=1 g cd( p , q ) = 1 p / q p/q p / q p p p q q q p + q = 2 , 3 , 4 , … p+q=2,3,4,\ldots p + q = 2 , 3 , 4 , …
1 , 1 2 , 2 , 1 3 , 3 , 1 4 , 2 3 , 3 2 , 4 , … . 1,\ \frac12,\ 2,\ \frac13,\ 3,\ \frac14,\ \frac23,\ \frac32,\ 4,\ldots. 1 , 2 1 , 2 , 3 1 , 3 , 4 1 , 3 2 , 2 3 , 4 , … . 例題
為甚麼有理數的對角掃描有效 例如 7 / 5 7/5 7/5 p + q = 12 p+q=12 p + q = 12 7 / 5 7/5 7/5 ( p , q ) (p,q) ( p , q ) Q + Q_+ Q +
這個論證同時證明了兩個方向。每個正有理數都有最簡數對，所以沒有遺漏；最
簡數對唯一，所以沒有重複。若所得列舉為 q 1 , q 2 , q 3 , … q_1,q_2,q_3,\ldots q 1 , q 2 , q 3 , …
0 , q 1 , − q 1 , q 2 , − q 2 , q 3 , − q 3 , … 0,q_1,-q_1,q_2,-q_2,q_3,-q_3,\ldots 0 , q 1 , − q 1 , q 2 , − q 2 , q 3 , − q 3 , … 列出每個有理數恰好一次。零出現一次，每個非零有理數都有唯一的符號和唯一
的正絕對值。因此 Q Q Q n ↦ n n\mapsto n n ↦ n N N N Q Q Q Q Q Q
圖示。對角掃描把二維格點變成一條序列；最簡形式條件消除了同一個有理數
的不同表示。
稠密性是另一個性質。有理數與實線的每個非空開區間相交，但對角線程序仍然
能把它們放入一條序列。稠密不等於不可數。
可數集合的乘積
網格論證也給出兩個 N N N a , b ∈ N a,b\in N a , b ∈ N
π ( a , b ) = ( a + b ) ( a + b + 1 ) 2 + b \pi(a,b)=\frac{(a+b)(a+b+1)}2+b π ( a , b ) = 2 ( a + b ) ( a + b + 1 ) + b 滿足固定 a + b = s a+b=s a + b = s s ( s + 1 ) / 2 s(s+1)/2 s ( s + 1 ) /2 π \pi π n = π ( a , b ) n=\pi(a,b) n = π ( a , b ) s s s s ( s + 1 ) / 2 ≤ n < ( s + 1 ) ( s + 2 ) / 2 s(s+1)/2\le n\lt(s+1)(s+2)/2 s ( s + 1 ) /2 ≤ n < ( s + 1 ) ( s + 2 ) /2 b = n − s ( s + 1 ) / 2 b=n-s(s+1)/2 b = n − s ( s + 1 ) /2 a = s − b a=s-b a = s − b π : N × N → N \pi:N\times N\to N π : N × N → N
定理
可數三元組仍然可數 ∣ N × N × N ∣ = ∣ N ∣ |N\times N\times N|=|N| ∣ N × N × N ∣ = ∣ N ∣
證明。 定義
Φ ( a , b , c ) = π ( π ( a , b ) , c ) \Phi(a,b,c)=\pi(\pi(a,b),c) Φ ( a , b , c ) = π ( π ( a , b ) , c ) 兩次使用的 π \pi π N 3 N^3 N 3 N N N ( π ( a , b ) , c ) (\pi(a,b),c) ( π ( a , b ) , c ) ( a , b ) (a,b) ( a , b ) N N N
同一個配對也能處理有限個帶標籤的可數集合。例如用
( n , i ) ↦ π ( n , i ) (n,i)\mapsto\pi(n,i) ( n , i ) ↦ π ( n , i ) ( n , 0 ) (n,0) ( n , 0 ) ( n , 1 ) (n,1) ( n , 1 ) N N N N N N N N N
更一般地，基數比較可以沿映射傳遞。若 X → Y X\to Y X → Y Y → Z Y\to Z Y → Z ∣ X ∣ ≤ ∣ Z ∣ |X|\le|Z| ∣ X ∣ ≤ ∣ Z ∣
基數不等式
定義
基數不等式 對集合 X X X Y Y Y X → Y X\to Y X → Y
∣ X ∣ ≤ ∣ Y ∣ |X|\le |Y| ∣ X ∣ ≤ ∣ Y ∣ 若 ∣ X ∣ ≤ ∣ Y ∣ |X|\le|Y| ∣ X ∣ ≤ ∣ Y ∣ ∣ X ∣ ≠ ∣ Y ∣ |X|\ne|Y| ∣ X ∣ = ∣ Y ∣ ∣ X ∣ < ∣ Y ∣ |X|\lt|Y| ∣ X ∣ < ∣ Y ∣
箭頭方向不可忽略：從 X X X Y Y Y Y Y Y X X X N → Z N\to Z N → Z n ↦ n n\mapsto n n ↦ n ∣ N ∣ ≤ ∣ Z ∣ |N|\le|Z| ∣ N ∣ ≤ ∣ Z ∣
例題
陪域有未使用元素的有限比較 定義 r : { 1 , 2 , 3 } → { a , b , c , d } r:\{1,2,3\}\to\{a,b,c,d\} r : { 1 , 2 , 3 } → { a , b , c , d } r ( 1 ) = b r(1)=b r ( 1 ) = b r ( 2 ) = d r(2)=d r ( 2 ) = d r ( 3 ) = a r(3)=a r ( 3 ) = a ∣ { 1 , 2 , 3 } ∣ ≤ ∣ { a , b , c , d } ∣ |\{1,2,3\}|\le|\{a,b,c,d\}| ∣ { 1 , 2 , 3 } ∣ ≤ ∣ { a , b , c , d } ∣ c c c
定理
基數不等式具有偏序結構 基數上的關係 ≤ \le ≤ < \lt <
證明。 恆等映射 i d X : X → X id_X:X\to X i d X : X → X f : X → Y f:X\to Y f : X → Y g : Y → Z g:Y\to Z g : Y → Z g ∘ f g\circ f g ∘ f f f f ∣ X ∣ = ∣ X ∣ |X|=|X| ∣ X ∣ = ∣ X ∣ ∣ X ∣ < ∣ X ∣ |X|\lt|X| ∣ X ∣ < ∣ X ∣ ≤ \le ≤
不存在一個以所有集合為元素的集合。假設有這樣的全集，就可以構造
Russell 類型的自指成員關係而得到矛盾。因此，這裏的 ≤ \le ≤
滿射 X → Y X\to Y X → Y Y Y Y X X X Y → X Y\to X Y → X y ∈ Y y\in Y y ∈ Y
可數個可數集合的並仍可數
定理
可數個可數集合的並仍可數 假設選擇公理，若 A n n ∈ N {A_n}_{n\in N} A n n ∈ N A n A_n A n
A = ⋃ n ∈ N A n A=\bigcup_{n\in N} A_n A = n ∈ N ⋃ A n 可數。
若 A = ∅ A=\varnothing A = ∅ N N N A A A A n A_n A n n n n
i n : A n → N . i_n:A_n\to N. i n : A n → N . 當 A n = ∅ A_n=\varnothing A n = ∅ i n {i_n} i n
定義
h : A → N × N , h ( x ) = ( n ( x ) , i n ( x ) ( x ) ) , h:A\to N\times N,\qquad h(x)=(n(x),i_{n(x)}(x)), h : A → N × N , h ( x ) = ( n ( x ) , i n ( x ) ( x )) , 其中
n ( x ) = min { n ∈ N ∣ x ∈ A n } . n(x)=\min\{n\in N\mid x\in A_n\}. n ( x ) = min { n ∈ N ∣ x ∈ A n } . 因為 x x x 6.3 區間、Cantor 集、稠密性與良序 。
映射 h h h h ( x ) = h ( x ′ ) h(x)=h(x') h ( x ) = h ( x ′ ) n ( x ) = n ( x ′ ) = n n(x)=n(x')=n n ( x ) = n ( x ′ ) = n i n ( x ) = i n ( x ′ ) i_n(x)=i_n(x') i n ( x ) = i n ( x ′ ) i n i_n i n x = x ′ x=x' x = x ′
最後，N × N N\times N N × N N × N → N N\times N\to N N × N → N h h h A → N A\to N A → N ( 0 , 0 ) (0,0) ( 0 , 0 ) 1 1 1 2 2 2
常見錯誤
可數並不等於任意並 這個定理處理的是可數族 A n {A_n} A n
定理
有理數稠密 設 r ∈ R r\in R r ∈ R ϵ > 0 \epsilon\gt 0 ϵ > 0 n ∈ N n\in N n ∈ N n > 1 / ϵ n\gt 1/\epsilon n > 1/ ϵ { m ∈ Z ∣ m ≤ n r } \{m\in Z\mid m\le nr\} { m ∈ Z ∣ m ≤ n r } m 0 m_0 m 0
m 0 ≤ n r < m 0 + 1 ⟹ 0 ≤ r − m 0 n < 1 n < ϵ . m_0\le nr\lt m_0+1
\quad\Longrightarrow\quad
0\le r-\frac{m_0}{n}\lt\frac1n\lt\epsilon. m 0 ≤ n r < m 0 + 1 ⟹ 0 ≤ r − n m 0 < n 1 < ϵ . 於是 q = m 0 / n ∈ Q q=m_0/n\in Q q = m 0 / n ∈ Q r r r ϵ \epsilon ϵ Q Q Q R R R
多項式作為有限形式和
定義
R 上的多項式 一個實係數多項式是一個形式和
p ( x ) = ∑ i = 0 ∞ a i x i p(x)=\sum_{i=0}^{\infty}a_ix^i p ( x ) = i = 0 ∑ ∞ a i x i 其中每個 a i ∈ R a_i\in R a i ∈ R a i a_i a i R [ x ] R[x] R [ x ]
「形式」這個字很重要。多項式不是某個單一 x x x
概念視角 結構
先看係數，再作代入 兩個形式多項式相等，正是指每個對應係數相同，包括省略的零係數。因此
1 + x 1+x 1 + x 1 + x + 0 x 2 1+x+0x^2 1 + x + 0 x 2 t t t p ( t ) = ∑ i a i t i p(t)=\sum_i a_it^i p ( t ) = ∑ i a i t i
單個函數值所含的資訊少於係數列表。例如 x x x x 2 x^2 x 2 t = 0 t=0 t = 0 0 0 0 R \mathbb R R
若至少有一個係數非零，p ( x ) p(x) p ( x ) a i ≠ 0 a_i\ne0 a i = 0 i i i
deg ( 0 ) = − ∞ . \deg(0)=-\infty. deg ( 0 ) = − ∞. 這個約定可以令許多次數公式不用一直把零多項式分開處理。
非零常數的次數是 0 0 0 − ∞ -\infty − ∞ max ( − ∞ , m ) = m \max(-\infty,m)=m max ( − ∞ , m ) = m ( − ∞ ) + m = − ∞ (-\infty)+m=-\infty ( − ∞ ) + m = − ∞ m = − ∞ m=-\infty m = − ∞
若首項係數是 1 1 1 首一多項式 （monic polynomial）。例如 x 3 − 4 x + 7 x^3-4x+7 x 3 − 4 x + 7 2 x 3 − 4 x + 7 2x^3-4x+7 2 x 3 − 4 x + 7
常見錯誤
不要只看最後寫出的項就判斷次數 若寫成
p ( x ) = a 0 + a 1 x + ⋯ + a n x n , p(x)=a_0+a_1x+\cdots+a_nx^n, p ( x ) = a 0 + a 1 x + ⋯ + a n x n , 只有在 a n ≠ 0 a_n\ne0 a n = 0 deg ( p ) = n \deg(p)=n deg ( p ) = n
加法、乘法與次數
設
p ( x ) = ∑ i = 0 ∞ a i x i , q ( x ) = ∑ i = 0 ∞ b i x i . p(x)=\sum_{i=0}^{\infty}a_ix^i,\qquad
q(x)=\sum_{i=0}^{\infty}b_ix^i. p ( x ) = i = 0 ∑ ∞ a i x i , q ( x ) = i = 0 ∑ ∞ b i x i . 加法是逐項相加：
p ( x ) + q ( x ) = ∑ i = 0 ∞ ( a i + b i ) x i . p(x)+q(x)=\sum_{i=0}^{\infty}(a_i+b_i)x^i. p ( x ) + q ( x ) = i = 0 ∑ ∞ ( a i + b i ) x i . 乘法則使用卷積公式：
p ( x ) q ( x ) = ∑ i = 0 ∞ d i x i , d i = ∑ k = 0 i a k b i − k . p(x)q(x)=\sum_{i=0}^{\infty}d_ix^i,\qquad
d_i=\sum_{k=0}^{i}a_kb_{i-k}. p ( x ) q ( x ) = i = 0 ∑ ∞ d i x i , d i = k = 0 ∑ i a k b i − k . 因為非零係數只有有限多個，乘積仍然是多項式。
定理
次數規則 對 p ( x ) , q ( x ) ∈ R [ x ] p(x),q(x)\in R[x] p ( x ) , q ( x ) ∈ R [ x ]
deg ( p + q ) ≤ max { deg p , deg q } \deg(p+q)\le \max\{\deg p,\deg q\} deg ( p + q ) ≤ max { deg p , deg q } deg ( p q ) = deg p + deg q \deg(pq)=\deg p+\deg q deg ( pq ) = deg p + deg q 第二條使用了係數域沒有零因子的性質。
第一條可能是嚴格不等式，因為最高次項可以抵消。例如
( x 2 + 1 ) + ( − x 2 + x ) = x + 1. (x^2+1)+(-x^2+x)=x+1. ( x 2 + 1 ) + ( − x 2 + x ) = x + 1. 乘法規則較強：若 p p p q q q a r a_r a r b s b_s b s p q pq pq x r + s x^{r+s} x r + s a r b s a_rb_s a r b s
進一步說明為何沒有更高次項。設 deg p = r \deg p=r deg p = r deg q = s \deg q=s deg q = s i > r + s i>r+s i > r + s a k b i − k a_kb_{i-k} a k b i − k k > r k>r k > r i − k > s i-k>s i − k > s r + s r+s r + s k = r k=r k = r i − k = s i-k=s i − k = s
對加法，超過 max ( r , s ) \max(r,s) max ( r , s ) p + ( − p ) = 0 p+(-p)=0 p + ( − p ) = 0 − ∞ -\infty − ∞
定理
多項式除法算法 設 f ( x ) , g ( x ) ∈ R [ x ] f(x),g(x)\in R[x] f ( x ) , g ( x ) ∈ R [ x ] g ( x ) ≠ 0 g(x)\ne0 g ( x ) = 0 q ( x ) , r ( x ) ∈ R [ x ] q(x),r(x)\in R[x] q ( x ) , r ( x ) ∈ R [ x ]
f ( x ) = g ( x ) q ( x ) + r ( x ) , deg r < deg g . f(x)=g(x)q(x)+r(x),\qquad \deg r\lt\deg g. f ( x ) = g ( x ) q ( x ) + r ( x ) , deg r < deg g . 先證存在性。考慮非空集合
S = { f − g s : s ∈ R [ x ] } . S=\{f-gs:s\in\mathbb R[x]\}. S = { f − g s : s ∈ R [ x ]} . 取 s = 0 s=0 s = 0 f ∈ S f\in S f ∈ S 0 ∈ S 0\in S 0 ∈ S q q q f − g q = 0 f-gq=0 f − g q = 0 r = 0 r=0 r = 0 deg 0 = − ∞ \deg0=-\infty deg 0 = − ∞ S S S r 0 = f − g q 0 r_0=f-gq_0 r 0 = f − g q 0
假設 deg r 0 = k ≥ j = deg g \deg r_0=k\ge j=\deg g deg r 0 = k ≥ j = deg g c k , b j c_k,b_j c k , b j b j ≠ 0 b_j\ne0 b j = 0 c k / b j c_k/b_j c k / b j
r 1 = r 0 − g ( c k b j x k − j ) = f − g ( q 0 + c k b j x k − j ) . r_1=r_0-g\left(\frac{c_k}{b_j}x^{k-j}\right)
=f-g\left(q_0+\frac{c_k}{b_j}x^{k-j}\right). r 1 = r 0 − g ( b j c k x k − j ) = f − g ( q 0 + b j c k x k − j ) . 指數 k − j k-j k − j r 1 r_1 r 1 S S S c k x k c_kx^k c k x k k k k r 1 = 0 r_1=0 r 1 = 0 0 ∉ S 0\notin S 0 ∈ / S deg r 0 < deg g \deg r_0\lt\deg g deg r 0 < deg g q 0 , r 0 q_0,r_0 q 0 , r 0
唯一性同樣重要。若
f = g q 1 + r 1 = g q 2 + r 2 f=gq_1+r_1=gq_2+r_2 f = g q 1 + r 1 = g q 2 + r 2 且兩個餘式的次數都小於 deg g \deg g deg g
g ( q 1 − q 2 ) = r 2 − r 1 . g(q_1-q_2)=r_2-r_1. g ( q 1 − q 2 ) = r 2 − r 1 . 左邊若非零，次數至少是 deg g \deg g deg g deg g \deg g deg g q 1 = q 2 q_1=q_2 q 1 = q 2 r 1 = r 2 r_1=r_2 r 1 = r 2
證明透視
唯一性的矛盾發生在哪裏 假設商式不同，其差就是非零多項式，次數至少為 0 0 0 g g g deg g \deg g deg g
由代入取得餘式
當除式是一次式時，除法算法會變成非常實用的定理。
定理
餘式定理 設 f ( x ) ∈ R [ x ] f(x)\in R[x] f ( x ) ∈ R [ x ] a ∈ R a\in R a ∈ R f ( x ) f(x) f ( x ) x − a x-a x − a f ( a ) f(a) f ( a )
因為餘式次數小於 1 1 1 R R R
f ( x ) = ( x − a ) q ( x ) + R f(x)=(x-a)q(x)+R f ( x ) = ( x − a ) q ( x ) + R 並代入 x = a x=a x = a f ( a ) = R f(a)=R f ( a ) = R
此處 R = f ( a ) R=f(a) R = f ( a ) x − a x-a x − a x = a x=a x = a
多項式整除 g ∣ f g\mid f g ∣ f q q q f = g q f=gq f = g q g g g
定理
因式定理 對 f ( x ) ∈ R [ x ] f(x)\in R[x] f ( x ) ∈ R [ x ] a ∈ R a\in R a ∈ R
( x − a ) ∣ f ( x ) ⟺ f ( a ) = 0. (x-a)\mid f(x)\quad\Longleftrightarrow\quad f(a)=0. ( x − a ) ∣ f ( x ) ⟺ f ( a ) = 0. 因式定理把代數因式與根連起來：一個根給出一個一次因式，而一個一次因式也給出
一個根。
非零多項式可以有多少個根？
因式定理給出根的數量上界。
定理
根的數量上界 一個 R R R C C C n n n n n n
歸納起點是次數 0 0 0 n n n n + 1 n+1 n + 1 f f f a a a f ( x ) = ( x − a ) q ( x ) f(x)=(x-a)q(x) f ( x ) = ( x − a ) q ( x ) q q q n n n
若 b ≠ a b\ne a b = a 0 = ( b − a ) q ( b ) 0=(b-a)q(b) 0 = ( b − a ) q ( b ) b − a b-a b − a q ( b ) = 0 q(b)=0 q ( b ) = 0 n n n a a a n + 1 n+1 n + 1 q ( a ) ≠ 0 q(a)\ne0 q ( a ) = 0 a a a q q q
因此，若一個次數至多 n n n n + 1 n+1 n + 1
根數上界也需要精確的假設。零多項式在每個輸入處都為零，所以必須排除。
「相異」計算的是不同值，而不是某個因式出現的次數。把上界用於 p − q p-q p − q n n n n + 1 n+1 n + 1
已給枚舉的可數乘積與並
設 I ⊆ N I\subseteq\mathbb N I ⊆ N i ∈ I i\in I i ∈ I D i ⊆ N D_i\subseteq\mathbb N D i ⊆ N e i : D i → A i e_i:D_i\to A_i e i : D i → A i D i = ∅ D_i=\varnothing D i = ∅ D i D_i D i ⋃ i ∈ I A i \bigcup_{i\in I}A_i ⋃ i ∈ I A i
證明。 固定雙射 π : N 2 → N \pi:\mathbb N^2\to\mathbb N π : N 2 → N
π ( i , k ) = ( i + k ) ( i + k + 1 ) 2 + k . \pi(i,k)=\frac{(i+k)(i+k+1)}2+k. π ( i , k ) = 2 ( i + k ) ( i + k + 1 ) + k . 它依次掃描有限對角線。對於並集，只保留滿足 i ∈ I i\in I i ∈ I k ∈ D i k\in D_i k ∈ D i π \pi π e i ( k ) e_i(k) e i ( k ) x x x x x x N \mathbb N N x x x
對於乘積 A × B A\times B A × B a : D → A a:D\to A a : D → A b : E → B b:E\to B b : E → B ( j , k ) ∈ D × E (j,k)\in D\times E ( j , k ) ∈ D × E ( a ( j ) , b ( k ) ) (a(j),b(k)) ( a ( j ) , b ( k )) π \pi π
統一構造有理數列表。 固定 Q \mathbb Q Q q 0 , q 1 , … q_0,q_1,\ldots q 0 , q 1 , … n ≥ 1 n\ge1 n ≥ 1 N n \mathbb N^n N n ( i 1 , … , i n ) (i_1,\ldots,i_n) ( i 1 , … , i n ) ( q i 1 , … , q i n ) (q_{i_1},\ldots,q_{i_n}) ( q i 1 , … , q i n ) n = 0 n=0 n = 0 n n n
非零有理係數多項式只有有限個實根。對給定可數列表中的每個非零多項式，將其實根按從小到大排列；沒有實根時使用空列表。實數集合 R \mathbb R R
稠密性、可數性與有理端點區間
集合 D ⊆ R D\subseteq\mathbb R D ⊆ R D D D α \alpha α q ∈ ( a − α , b − α ) q\in(a-\alpha,b-\alpha) q ∈ ( a − α , b − α ) q + α ∈ ( a , b ) q+\alpha\in(a,b) q + α ∈ ( a , b )
例子
可數而稠密的有理點。 有理點可以編號，儘管每個區間都含有無窮多個有理數。按分母和分子列出它們，並不會使它們成為孤立點。
有限有理數據。 對每個固定的 n n n n n n n n n R \mathbb R R
練習
P01. 設 N = { 0 , 1 , 2 , … } \mathbb N=\{0,1,2,\ldots\} N = { 0 , 1 , 2 , … } N \mathbb N N
P02. 證明從不可數集合中去掉一個可數集合後，剩餘集合仍不可數。
P03. 利用有理數的稠密性，證明每個滿足 a < b a<b a < b ( a , b ) (a,b) ( a , b )
P04. 證明以有理數為端點的開區間全體構成可數集合，並證明 R \mathbb R R
完整解答
P01. 將整數列為 0 , 1 , − 1 , 2 , − 2 , … 0,1,-1,2,-2,\ldots 0 , 1 , − 1 , 2 , − 2 , … n ↦ 2 n n\mapsto2n n ↦ 2 n N \mathbb N N
P02. 如果去掉的集合和剩餘集合都可數，則它們的並可數，與原集合不可數矛盾。若去掉的集合不是原集合的子集，就改用它與原集合的交集。
P03. 固定一個無理數 α \alpha α 2 \sqrt2 2 q ∈ ( a − α , b − α ) ∩ Q q\in(a-\alpha,b-\alpha)\cap\mathbb Q q ∈ ( a − α , b − α ) ∩ Q q + α ∈ ( a , b ) q+\alpha\in(a,b) q + α ∈ ( a , b ) q q q α \alpha α
P04. 有理數對的集合可數，其中第一坐標小於第二坐標的子集也可數。若 x x x U U U ε > 0 \varepsilon>0 ε > 0 ( x − ε , x + ε ) ⊆ U (x-\varepsilon,x+\varepsilon)\subseteq U ( x − ε , x + ε ) ⊆ U r ∈ ( x − ε , x ) r\in(x-\varepsilon,x) r ∈ ( x − ε , x ) s ∈ ( x , x + ε ) s\in(x,x+\varepsilon) s ∈ ( x , x + ε ) ( r , s ) (r,s) ( r , s ) x x x U U U U U U U = ∅ U=\varnothing U = ∅
