此條目介紹的是數學上最常用的意義,即物件的個數。關於其他的意義,請見「
基數 」。
在日常交流中,基數 (cardinal number,cardinal)或量數 ,是對應量詞 的數 ,例如「一顆蘋果」中的「一」。與序數 相對,序數是對應排列 的數,例如「第一名」中的「一」及「二年級」中的「二」。
在數學 集合論 中,基數 或勢 ,即集合 中包含的元素 的「個數」(參見勢的比較 ),是日常交流中基數的概念在數學上的精確化(並使之不再受限於有限情形)。有限集合 的基數,其意義與日常用語中的「基數」相同,例如
{
a
,
b
,
c
}
{\displaystyle \{a,b,c\}}
的基數是3。無限集合 的基數,其意義在於比較兩個集的大小,例如整數集和有理數集的基數相同;整數集的基數比實數集的小。
歷史
阿列夫數 Aleph-0,最小的無限基數
康托爾 在1874年-1884年引入最原始的集合論 (現稱樸素集合論 )時,首次引入基數概念。
他最先考慮的是集合
{
1
,
2
,
3
}
{\displaystyle \{1,2,3\}}
和
{
2
,
3
,
4
}
{\displaystyle \{2,3,4\}}
,它們並非相同 ,但有相同的基數 。驟眼看來,這是顯而易見,但究竟何謂兩個集合有相同數目的元素?
康托爾的答案,是透過所謂的一一對應 ,即把兩個集合的元素一對一的排起來——若能做到,兩個集合的基數自然相同。這答案,容易理解但卻是革命性的,因為用相同的方法即可比較任意集合的大小,包括無窮集合。
最先被考慮的無窮集合是自然數 集
N
=
{
1
,
2
,
3
,
.
.
.
}
{\displaystyle \mathbb {N} =\{1,2,3,...\}}
及其無限子集 。他把所有與
N
{\displaystyle \mathbb {N} }
能一一對應的集為可數集 。令康托爾意外的是,原來
N
{\displaystyle \mathbb {N} }
的所有無限子集都能與
N
{\displaystyle \mathbb {N} }
一一對應。他把
N
{\displaystyle \mathbb {N} }
的基數稱為
ℵ
0
{\displaystyle \aleph _{0}}
,是最小的艾禮富數 。
康托爾發現,原來有理數 集合與代數數 集合也是可數的。於是乎在1874年初,他嘗試證明是否所有無限集合均是可數,其後他得出了實數 集不可數的結論。原先的證明用到了涉及區間套的複雜論證,而在他1891年的論文中,他以簡單而巧妙的對角論證法 重新證明了這一結果。實數集的基數,記作c,代表連續統 。
接著康托爾構作一個比一個大的集合,得出一個比一個大的基數,而這些巨大集合的元素已不可如實數般書寫出來。因此關於基數的一般理論,需要一個新的語言描述,這就是康托爾發明集合論的主因。
康托爾隨後提出連續統假設 :c就是第二個超窮基數
ℵ
1
{\displaystyle \aleph _{1}}
,即継
ℵ
0
{\displaystyle \aleph _{0}}
之後最小的基數。現已知這假設是不能證明的,即接受或否定它會得出兩套不同但邏輯 上可行的公理化集合論 。
動機
在非正式使用中,基數 就是通常被稱為計數 的東西。它們同一於開始於
0
{\displaystyle 0}
的自然數 (就是
0
,
1
,
2
,
…
{\displaystyle 0,1,2,\ldots }
)。計數可以形式化地定義為有限 基數,而無限基數只出現在高等數學和邏輯中。
更正式地,一個非零的數可以用於兩個目的:描述一個集合的大小,或描述一個元素在序列中位置。對於有限集合和序列,可以輕易的看出著兩個概念是相符的,因為對於所有描述在序列中的一個位置的數,我們可以構造一個有正好大小的集合,比如3描述了
c
{\displaystyle c}
在序列
a
,
b
,
c
,
d
,
.
.
.
{\displaystyle a,b,c,d,...}
中的位置,並且我們可以構造有三個元素的集合
{
a
,
b
,
c
}
{\displaystyle \{a,b,c\}}
。但是在處理無限集合 的時候,在這兩個概念之間的區別是本質的—這兩個概念對於無限集合實際上是不同的。考慮位置的方面會引申出序數的概念,而大小則被這裡描述的基數 所廣義化。
在基數的形式定義背後的直觀想法是,可以構造一個記號來指明集合的相對大小,而不需理會它有哪些種類的成員。對於有限集合這是容易的:只需簡單的數算一個集合的成員數目。為了比較更大集合的大小,得藉助更加巧妙的概念。
一個集合
Y
{\displaystyle Y}
至少等大小於(或稱大於等於)一個集合
X
{\displaystyle X}
,如果有從
X
{\displaystyle X}
到
Y
{\displaystyle Y}
的一個單射 (一一映射)。一一映射對集合
X
{\displaystyle X}
的每個元素確定了一個唯一的集合
Y
{\displaystyle Y}
的元素。通過例子就最易理解了;假設有集合
X
=
{
1
,
2
,
3
}
{\displaystyle X=\{1,2,3\}}
和
Y
=
{
a
,
b
,
c
,
d
}
{\displaystyle Y=\{a,b,c,d\}}
,我們可以注意到有一個映射 :
1
→
a
{\displaystyle 1\to a}
2
→
b
{\displaystyle 2\to b}
3
→
c
{\displaystyle 3\to c}
這是一對一的,使用上述的大小概念,我們因此總結出
Y
{\displaystyle Y}
有大於等於
X
{\displaystyle X}
的勢。注意元素
d
{\displaystyle d}
沒有元素映射到它,但這是允許的,因為我們只要求一一映射,而不必須是一對一並且完全 的映射。這個概念的好處是它可以擴展到無限集合。
我們可以把這個概念擴展到一個類似於等式的關係。兩個集合
X
{\displaystyle X}
和
Y
{\displaystyle Y}
被稱為有相同的"勢",如果存在
X
{\displaystyle X}
和
Y
{\displaystyle Y}
之間的雙射 。通過Schroeder-Bernstein定理 ,這等價於有從
X
{\displaystyle X}
到
Y
{\displaystyle Y}
和從
Y
{\displaystyle Y}
到
X
{\displaystyle X}
的兩個一一映射。我們接著記之為
|
X
|
=
|
Y
|
{\displaystyle |X|=|Y|}
。
X
{\displaystyle X}
的基數自身經常被定義為有著
|
a
|
=
|
X
|
{\displaystyle |a|=|X|}
的最小序數
a
{\displaystyle a}
。這叫做馮·諾伊曼基數指派 ;為使這個定義有意義,必須證明所有集合都有同某個序數 一樣的勢;這個陳述就是良序原理 。然而即使不給集合的勢指派一個名字,討論集合之間相對的勢 還是可以的。
一個經典例子是無限旅館悖論,也叫做希爾伯特旅館悖論 。假設你是有無限個房間的旅館主人。旅館客滿,而又來了一個新客人。可以讓在房間1的客人轉移到房間2,房間2的客人轉移到房間3,以此類推,騰空房間1的方式安置這個新客人。我們可以明確的寫出這個映射的一個片段:
1
⟷
2
{\displaystyle 1\longleftrightarrow 2}
2
⟷
3
{\displaystyle 2\longleftrightarrow 3}
3
⟷
4
{\displaystyle 3\longleftrightarrow 4}
...
n
⟷
n
+
1
{\displaystyle n\longleftrightarrow n+1}
...
在這種方式下我們可以看出集合
{
1
,
2
,
3
,
.
.
.
}
{\displaystyle \{1,2,3,...\}}
和集合
{
2
,
3
,
4
,
.
.
.
}
{\displaystyle \{2,3,4,...\}}
有相同的勢,因為已知這兩個集合之間存在雙射。這便給"無限集合"提供了一個合適的定義,即是與自身某個真子集有著相同的勢的任何集合;在上面的例子中
{
2
,
3
,
4
,
.
.
.
}
{\displaystyle \{2,3,4,...\}}
是
{
1
,
2
,
3
,
.
.
.
}
{\displaystyle \{1,2,3,...\}}
的真子集。
當我們考慮這些大對象的時候,我們還想看看計數次序的概念是否符合上述為無限集合定義的基數。事實上是不一致的;通過考慮上面的例子,我們可以看到如果有「比無限大一」的某個對象存在,它必須跟起初的無限集合有一樣的勢。這時候可以使用另一種稱為序數 的形式概念,它是建基於計數並依次考慮每個數的想法上。而我們會發現,勢和序(ordinality)的概念對於無限的情況是有分歧的。
可以證明實數 的勢大於剛才描述的自然數的勢,透過對角論證法 可以一目瞭然。跟勢相關的經典問題(比如連續統假設 )主要關注在某一對無限基數之間是否有別的基數。現時數學家已經在描述更大更大基數的性質。
因為基數是數學中如此常用的概念,有各種各樣的名字指涉它。勢相同有時也叫做等勢 、均勢或等多(equipotence, equipollence, equinumerosity)。因此稱有相同勢的兩個集合為等勢的、均勢的或等多的(equipotent, equipollent, equinumerous)。
定義
首先,給出集合
X
{\displaystyle X}
和
Y
{\displaystyle Y}
,我們稱
X
{\displaystyle X}
的勢小於等於
Y
{\displaystyle Y}
,記作
|
X
|
≤
|
Y
|
{\displaystyle |X|\leq |Y|}
,當且僅當存在由
X
{\displaystyle X}
到
Y
{\displaystyle Y}
的單射 ;稱
X
{\displaystyle X}
的勢與
Y
{\displaystyle Y}
相等,記作
|
X
|
=
|
Y
|
{\displaystyle |X|=|Y|}
, 當且僅當存在由
X
{\displaystyle X}
到
Y
{\displaystyle Y}
的雙射 (即一一對應)。
康托爾-伯恩斯坦-施洛德定理 指出如果
|
X
|
≤
|
Y
|
{\displaystyle |X|\leq |Y|}
及
|
Y
|
≤
|
X
|
{\displaystyle |Y|\leq |X|}
則
|
X
|
=
|
Y
|
{\displaystyle |X|=|Y|}
。
假設選擇公理 ,所有集合都可良序 ,且對於所有集合
X
{\displaystyle X}
與
Y
{\displaystyle Y}
,有
|
X
|
≤
|
Y
|
{\displaystyle |X|\leq |Y|}
或
|
Y
|
≤
|
X
|
{\displaystyle |Y|\leq |X|}
。因此,我們可以定義序數 ,而
集合
X
{\displaystyle X}
的基數 則是與
X
{\displaystyle X}
等勢的最小序數
α
{\displaystyle \alpha }
。
(若不接受選擇公理,我們也可對非良序集
X
{\displaystyle X}
定義基數,就是所有與
X
{\displaystyle X}
等勢的集的階中下確界。)
有限集的基數
自然數 的一種定義是
0
=
{
}
,
1
=
{
0
}
,
2
=
{
0
,
1
}
,
3
=
{
0
,
1
,
2
}
,
…
,
N
=
{
0
,
1
,
…
,
N
−
1
}
{\displaystyle 0=\{\},1=\{0\},2=\{0,1\},3=\{0,1,2\},\ldots ,N=\{0,1,\ldots ,N-1\}}
。可以見到,與數
N
{\displaystyle N}
等勢的集必有
N
{\displaystyle N}
個元素。如集合
{
2
,
3
,
5
}
{\displaystyle \{2,3,5\}}
的基數為
3
{\displaystyle 3}
。
以下是有限集的三個等價定義:它與某自然數等勢;它只有一個等勢的序數,就是它的基數;它沒有等勢的真子集。
無限集的基數
最小的無限集合是自然數集。
{
1
,
2
,
3
,
4
,
…
,
n
,
…
}
{\displaystyle \{1,2,3,4,\ldots ,n,\ldots \}}
與
{
2
,
4
,
6
,
8
,
…
,
2
n
,
…
}
{\displaystyle \{2,4,6,8,\ldots ,2n,\ldots \}}
基數相同,因為可以讓前一集合的
n
{\displaystyle n}
與後一集合的
2
n
{\displaystyle 2n}
一一對應。從這個例子可以看出,對於一個無窮集合來說,它可以和它的一個真子集 有相同的基數。
以下是無限集的四個等價定義:它不與任何自然數等勢;它有超過一個等勢的序數;它有至少一個真子集和它等勢;存在由自然數集到它的單射。
基數算術
我們可在基數上定義若干算術 運算,這是對自然數運算的推廣。
給出集合
X
{\displaystyle X}
與
Y
{\displaystyle Y}
,定義
X
+
Y
=
{
(
x
,
0
)
:
x
∈
X
}
∪
{
(
y
,
1
)
:
y
∈
Y
}
{\displaystyle X+Y=\{(x,0):x\in X\}\cup \{(y,1):y\in Y\}}
,則基數和是
|
X
|
+
|
Y
|
=
|
X
+
Y
|
{\displaystyle |X|+|Y|=|X+Y|}
。
若
X
{\displaystyle X}
與
Y
{\displaystyle Y}
不相交,則
|
X
|
+
|
Y
|
=
|
X
∪
Y
|
{\displaystyle |X|+|Y|=|X\cup Y|}
。
基數積是
|
X
|
|
Y
|
=
|
X
×
Y
|
{\displaystyle |X||Y|=|X\times Y|}
其中
X
×
Y
{\displaystyle X\times Y}
是
X
{\displaystyle X}
和
Y
{\displaystyle Y}
的笛卡兒積 。
基數指數是
|
X
|
|
Y
|
=
|
X
Y
|
{\displaystyle |X|^{|Y|}=|X^{Y}|}
其中
X
Y
{\displaystyle X^{Y}}
是所有由
Y
{\displaystyle Y}
到
X
{\displaystyle X}
的函數 的集合。
在有限集時,這些運算與自然數無異。一般地,它們亦有普通算術運算的性質:
加法和乘法是可交換的 ,即
|
X
|
+
|
Y
|
=
|
Y
|
+
|
X
|
{\displaystyle |X|+|Y|=|Y|+|X|}
及
|
X
|
|
Y
|
=
|
Y
|
|
X
|
{\displaystyle |X||Y|=|Y||X|}
加法和乘法符合結合律 ,
(
|
X
|
+
|
Y
|
)
+
|
Z
|
=
|
X
|
+
(
|
Y
|
+
|
Z
|
)
{\displaystyle (|X|+|Y|)+|Z|=|X|+(|Y|+|Z|)}
及
(
|
X
|
|
Y
|
)
|
Z
|
=
|
X
|
(
|
Y
|
|
Z
|
)
{\displaystyle (|X||Y|)|Z|=|X|(|Y||Z|)}
分配律 ,即
(
|
X
|
+
|
Y
|
)
|
Z
|
=
|
X
|
|
Z
|
+
|
Y
|
|
Z
|
{\displaystyle (|X|+|Y|)|Z|=|X||Z|+|Y||Z|}
。
|
X
|
|
Y
|
+
|
Z
|
=
|
X
|
|
Y
|
|
X
|
|
Z
|
{\displaystyle |X|^{|Y|+|Z|}=|X|^{|Y|}|X|^{|Z|}}
|
X
|
|
Y
|
|
Z
|
=
(
|
X
|
|
Y
|
)
|
Z
|
{\displaystyle |X|^{|Y||Z|}=(|X|^{|Y|})^{|Z|}}
(
|
X
|
|
Y
|
)
|
Z
|
=
|
X
|
|
Z
|
|
Y
|
|
Z
|
{\displaystyle (|X||Y|)^{|Z|}=|X|^{|Z|}|Y|^{|Z|}}
無窮集合的加法及乘法(假設選擇公理)非常簡單。若
X
{\displaystyle X}
與
Y
{\displaystyle Y}
皆非空而其中之一為無限集,則
|
X
|
+
|
Y
|
=
|
X
|
|
Y
|
=
max
{
|
X
|
,
|
Y
|
}
{\displaystyle |X|+|Y|=|X||Y|=\max\{|X|,|Y|\}}
注意
2
|
X
|
{\displaystyle 2^{|X|}}
是
X
{\displaystyle X}
的冪集 之基數。由對角論證法 可知
2
|
X
|
>
|
X
|
{\displaystyle 2^{|X|}>|X|}
,是以並不存在最大的基數。事實上,基數的類 是真類 。
還有些關於指數的性質:
|
X
|
0
=
1
{\displaystyle |X|^{0}=1}
(特別地,
0
0
=
1
{\displaystyle 0^{0}=1}
)。
0
|
Y
|
=
0
{\displaystyle 0^{|Y|}=0}
,若
Y
{\displaystyle Y}
非空。
1
|
Y
|
=
1
{\displaystyle 1^{|Y|}=1}
。
若
|
X
|
≤
|
Y
|
{\displaystyle |X|\leq |Y|}
,則
|
X
|
|
Z
|
≤
|
Y
|
|
Z
|
{\displaystyle |X|^{|Z|}\leq |Y|^{|Z|}}
。
若
|
X
|
{\displaystyle |X|}
和
|
Y
|
{\displaystyle |Y|}
俱有限且大於1,而
Z
{\displaystyle Z}
是無窮集,則
|
X
|
|
Z
|
=
|
Y
|
|
Z
|
{\displaystyle |X|^{|Z|}=|Y|^{|Z|}}
。
若X是無窮而
Y
{\displaystyle Y}
是有限及非空,則
|
X
|
|
Y
|
=
|
X
|
{\displaystyle |X|^{|Y|}=|X|}
。
基數序列及連續統假設
對每一個基數,存在一個最小比它大的基數。這在自然數當然是對的。自然數集的基數是
ℵ
0
{\displaystyle \aleph _{0}}
,康托爾稱下一個為
ℵ
1
{\displaystyle \aleph _{1}}
,相類似的,還定義了如下一個序列 :
ℵ
0
,
ℵ
1
,
…
,
ℵ
n
…
{\displaystyle \aleph _{0},\aleph _{1},\ldots ,\aleph _{n}\ldots }
。
設
c
=
2
ℵ
0
{\displaystyle c=2^{\aleph _{0}}}
。連續統假設猜想,就是
c
=
ℵ
1
{\displaystyle c=\aleph _{1}}
。
連續統假設是與一般集論公理(即Zermelo-Fraenkel公理系統加上選擇公理)是獨立的。
更一般的假設,即
ℵ
n
+
1
=
2
ℵ
n
{\displaystyle \aleph _{n+1}=2^{\aleph _{n}}}
。
廣義連續統假設 ,就是對所有無窮基數
ℵ
{\displaystyle \aleph }
,都不存在介乎
ℵ
{\displaystyle \aleph }
與
2
ℵ
{\displaystyle 2^{\aleph }}
之間的基數。
參考文獻
Hahn, Hans, Infinity , Part IX, Chapter 2, Volume 3 of The World of Mathematics . New York: Simon and Schuster, 1956.
Halmos, Paul , Naive set theory . Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition).
外部連結