在数学上,可数集 ,或称可列集 ,是与自然数 集的某个子集 具有相同基數 (等势 )的集合。在这个意义下,可数集由有限可数集 和無限可數集 组成。不是可数集的无穷集 称为不可数集 。这个术语是康托尔 创造的。可数集的元素,正如其名,是「可以计数」的:尽管计数有可能永远无法终止,集合中每一个特定的元素都将对应一个自然数。
「可数集」这个术语有时也指代可数无穷集 ,即仅代表能和自然数集本身一一对应的集合[1] 。两个定义的差别在于有限集合 在前者中算作可数集,而在后者中不算作可数集。
为了避免歧义,前一种意义上的可数 有时称为至多可数 [2] ,后一种可数集 则称为无限可数集 [3] 。
如果从
S
{\displaystyle S}
到自然數 集合
N
=
{
1
,
2
,
3
,
…
}
{\displaystyle \mathbb {N} =\left\{1,2,3,\ldots \right\))
存在单射 函数,则
S
{\displaystyle S}
称为可数集。[4]
如果
S
{\displaystyle S}
还是满射 ,则同样是双射 ,则称
S
{\displaystyle S}
是无限 可数集 。
换句话说,一个集合要想是无限可数集 ,它要和自然数集
N
{\displaystyle \mathbb {N} }
有一一对应 关系。
如上所述,这个术语不普遍:一些作者在这里使用可数来表示被称为“无限可数”,并没有包括有限集。
由定義易知所有偶數 所構成的集合為可列的,因為我們可以將所有的
n
{\displaystyle n}
都對應到
2
n
{\displaystyle 2n}
,如此就完成了一一對應。類似地,不難證明所有整數 構成的集合
Z
{\displaystyle \mathbb {Z} }
、所有有理數 構成的集合
Q
{\displaystyle \mathbb {Q} }
、甚至所有代數數 構成的集合都是可列的。
並非所有的無窮集都可數。喬治·康托 首先指出存在有不可列的無窮集合。他利用他發明的對角論證法 證明了由所有實數 構成的集合
R
{\displaystyle \mathbb {R} }
是不可列的,即
R
{\displaystyle \mathbb {R} }
與
N
{\displaystyle \mathbb {N} }
之間不可能存在一種一一對應。這同時也表示實數當中存在有一些數不是代數數,因為剛才已經說過代數數是可列的;於是這就給出了一種超越數 存在的非構造性證明 。
由定义,如果存在从
S
{\displaystyle S}
到自然數 集合
N
=
{
0
,
1
,
2
,
3
,
…
}
{\displaystyle \mathbb {N} =\left\{0,1,2,3,\ldots \right\))
存在单射函数
f
:
S
→
N
{\displaystyle f:S\rightarrow \mathbb {N} }
,则
S
{\displaystyle S}
称为可数集。
这似乎自然地把集合划分为不同类别:把所有包含一个元素的集合放在一起;包含两个元素的集合在一起......最后,把所有无限集合放在一起,并认为它们具有相同的大小。然而,在大小的自然定义下,这种观点是不确切的。
为了阐述这一点,我们需要一个双射 的概念。虽然双射看起来比数更加高深,但原本数学发展中集论定义函数要先于数字。因为它们都是基于更简单的集合。这就引出了双射的概念:
a
↔
1
,
b
↔
2
,
c
↔
3
{\displaystyle a\leftrightarrow 1,b\leftrightarrow 2,c\leftrightarrow 3}
由于
{
a
,
b
,
c
}
{\displaystyle \left\{a,b,c\right\))
的每个元素都可以和
{
1
,
2
,
3
}
{\displaystyle \left\{1,2,3\right\))
中准确的一个 配对,并且 反过来也同样,这就定义了一个双射。
我们将这个情境一般化,定义当且仅当它们之间存在双射,两个集合的大小相同。对于有限集,这里给出了“大小相同”的常用定义。那么对于无限集呢?
考虑集合
A
=
{
1
,
2
,
3
,
…
}
{\displaystyle A=\left\{1,2,3,\ldots \right\))
(正整数 集),和
B
=
{
2
,
4
,
6
,
…
}
{\displaystyle B=\left\{2,4,6,\ldots \right\))
(正偶数集)。我们说,在我们的定义下,这些集合有相同的大小,并且因此B 是无限可数集。我们需要证明它们之间存在双射。但这是很简单的,运用
n
↔
2
n
{\displaystyle n\leftrightarrow 2n}
,那么
1
↔
2
,
2
↔
4
,
3
↔
6
,
4
↔
8
,
…
{\displaystyle 1\leftrightarrow 2,2\leftrightarrow 4,3\leftrightarrow 6,4\leftrightarrow 8,\ldots }
正如前面的例子,
A
{\displaystyle A}
的每个元素都已和
B
{\displaystyle B}
中准确的一个 配对,并且 反过来也同样。因而它们大小相同。这给出了一个集合与其一个合适的子集大小相同的例子,这种情形在有限集中是不可能的。
同样,自然数的有序对 的集合,也就是自然數集合的笛卡爾積
N
×
N
{\displaystyle \mathbb {N} \times \mathbb {N} }
,是无限可数集,可以沿着图中的一种路径:
康拖尔配对函数 给每一对自然数分配了一个自然数配对结果就像这样:
0
↔
(
0
,
0
)
,
1
↔
(
1
,
0
)
,
2
↔
(
0
,
1
)
,
3
↔
(
2
,
0
)
,
4
↔
(
1
,
1
)
,
5
↔
(
0
,
2
)
,
6
↔
(
3
,
0
)
,
…
{\displaystyle 0\leftrightarrow (0,0),1\leftrightarrow (1,0),2\leftrightarrow (0,1),3\leftrightarrow (2,0),4\leftrightarrow (1,1),5\leftrightarrow (0,2),6\leftrightarrow (3,0),\ldots }
显然这个映射可以覆盖所有这些有序对。另一個證明方法是可以定義一個從自然數集合的笛卡爾積
N
×
N
{\displaystyle \mathbb {N} \times \mathbb {N} }
到自然數集合
N
{\displaystyle \mathbb {N} }
的單射 函數
f
(
p
,
q
)
=
2
p
3
q
{\displaystyle f(p,q)=2^{p}3^{q))
。
利用數學歸納法 ,可知在n是個有限的自然數時,自然數集合的n-元笛卡爾積
∏
i
=
1
n
N
=
{
(
x
1
,
…
,
x
n
)
|
x
1
∧
…
∧
x
n
∈
N
}
{\displaystyle \prod _{i=1}^{n}\mathbb {N} =\{(x_{1},\ldots ,x_{n})\ |\ x_{1}\land \;\ldots \;\land \;x_{n}\in \mathbb {N} \))
是可數的。利用自然數集的笛卡爾積是可數的這點,可以證明整數 集和有理數 集是可數集,這是因為整數可以視為自然數的有序對(可將正整數
n
{\displaystyle n}
給視為
(
n
,
0
)
{\displaystyle (n,0)}
,將負整數
−
n
{\displaystyle -n}
給視為
(
0
,
n
)
{\displaystyle (0,n)}
),而以最簡分數 形式表示的有理數
p
/
q
{\displaystyle p/q}
也可視為整數的有序對
(
p
,
q
)
{\displaystyle (p,q)}
所致。
另外,可數無限多個可數集的聯集是可數的,這是因為可以定義一個單射函數,將可數無限多個可數集的聯集給映至自然數集合的笛卡爾積
N
×
N
{\displaystyle \mathbb {N} \times \mathbb {N} }
之故。
不過可數無限多個自然數集合的笛卡爾積 不是可數的,這可以透過康托的對角論證法證明。
^ 例子参见(Rudin 1976 ,Chapter 2)
^ 参见(Lang 1993 ,§2 of Chapter I).
^ 参见(Apostol 1969 ,Chapter 13.19).
^ 因为显然N 和N * = {1, 2, 3, ...}之间显然存在双射 ,无所谓是否把0算作自然数。在任何情况,这篇文章都遵循ISO 31-11和数学逻辑 中的标准传统,将0作为自然数。
Lang, Serge , Real and Functional Analysis, Berlin, New York: Springer-Verlag , 1993, ISBN 0-387-94001-4
Rudin, Walter , Principles of Mathematical Analysis, New York: McGraw-Hill , 1976, ISBN 0-07-054235-X 可數集
自然数 (
N
{\displaystyle \mathbb {N} }
)
整数 (
Z
{\displaystyle \mathbb {Z} }
)
有理数 (
Q
{\displaystyle \mathbb {Q} }
)
規矩數
代數數 (
A
{\displaystyle \mathbb {A} }
)
周期
可計算數
可定义数
高斯整數 (
Z
[
i
]
{\displaystyle \mathbb {Z} [i]}
)
艾森斯坦整数
合成代數
可除代數 :实数 (
R
{\displaystyle \mathbb {R} }
)
複數 (
C
{\displaystyle \mathbb {C} }
)
四元數 (
H
{\displaystyle \mathbb {H} }
)
八元数 (
O
{\displaystyle \mathbb {O} }
)
凯莱-迪克森结构
实数 (
R
{\displaystyle \mathbb {R} }
)
複數 (
C
{\displaystyle \mathbb {C} }
)
四元數 (
H
{\displaystyle \mathbb {H} }
)
八元数 (
O
{\displaystyle \mathbb {O} }
)
十六元數 (
S
{\displaystyle \mathbb {S} }
)
三十二元數
六十四元數
一百二十八元數
二百五十六元數……
分裂 形式 其他超複數 其他系統