基数
| 势 | |
|---|---|
| 术语名称 | 势 |
| 英语名称 | cardinality |
| 别名 | 基数 |
| 基数 | |
|---|---|
| 术语名称 | 基数 |
| 英语名称 | cardinal number |
| 别名 | cardinal |
势(cardinality)表示集合的大小。可以通俗地描述为集合所包含元素的个数，但势的可能取值是自然数的推广。
基数(cardinal number, 简称cardinal)指势的可能取值，用自然数（有限基数）衡量有限集合的大小，用其他基数（超限基数）衡量无限集合中的“无穷”的大小。区别于序数。
记号
| 基数 | |
|---|---|
| 运算名称 | 基数 |
| 运算符号 | [math]\displaystyle{ |\bullet| }[/math],[math]\displaystyle{ \mathrm{card} \bullet }[/math] |
| Latex | \vert\vert, \mathrm{card}
|
| 运算对象 | 集合 |
| 运算元数 | 1 |
| 运算结果 | 基数
|
集合大小的度量称为基数或势(cardinality)，集合 [math]\displaystyle{ A }[/math] 的势一般被记作 [math]\displaystyle{ |A| }[/math] ，也记作 [math]\displaystyle{ \mathrm{card} A }[/math][1]。偶尔也有人记作 [math]\displaystyle{ \# A }[/math]。
| 等势 | |
|---|---|
| 关系名称 | 等势 |
| 关系符号 | |
| Latex | |
| 关系对象 | 集合 |
| 关系元数 | 2 |
两集合间有相等的基数或势，称为集合等势(have the same cardinality)。
表示集合势的数称为基数(cardinal number, cardinal)。
取值
比较规则
集合等势当且仅当集合间存在一个双射。可通过数学归纳法证明，如此定义下，同一集合的基数是唯一的。
集合的基数有小于等于关系，当且仅当，集合间存在一个单射。
小于等于且不等于的关系定义为小于关系。
自然数基数（有限基数）和超限基数
对元素个数有限的集合，通过选择，总是能和 [math]\displaystyle{ \{ 1, 2, \dots, n \} }[/math] （ n 为自然数）建立一个双射，因此其基数就是其元素个数，是一个自然数。 基数为自然数的集合总是有限集，因此这些自然数作为基数时，称为有限基数(finite cardinals)。
对元素个数无限的集合，能够通过能否建立单射和双射，比较集合元素的多少。 大于所有有限基数（即所有自然数）的最小基数，是自然数集的势，称为 [math]\displaystyle{ \aleph_0 }[/math] ； 很多改变有限集基数的操作（如并集、笛卡尔积）作用于自然数集实际上都仍然能找到双射，也就是没有改变 [math]\displaystyle{ \aleph_0 }[/math] ，这说明后续的基数会更稳定，不会简单增长； 此后每个 [math]\displaystyle{ \aleph_n }[/math] 都定义为对应序数 [math]\displaystyle{ \omega_n }[/math] 的基数，而每个序数是上一个序数任意表达后的极限序数。 这些超出有限基数的基数统称为无限基数或超限基数(transfinite cardinals)。 （注意：公理化集合论中，需要承认选择公理等价的良序公理，才能认为每个集合都和序数一一对应，才有可比较的基数）
基数，即集合的势的可能取值，构成一个超限序列：
[math]\displaystyle{ 0, 1, 2, 3, \dots, n, \dots ; \aleph_0, \aleph_1, \aleph_2, \dots, \aleph_\alpha, \dots }[/math]
基数算术
- 对有限集 [math]\displaystyle{ X }[/math] 和对象 [math]\displaystyle{ x \notin X }[/math] ， [math]\displaystyle{ \operatorname{card} (X \cup \{x\}) = \operatorname{card} X + 1 }[/math] 。
- 对有限集 [math]\displaystyle{ X }[/math] 、 [math]\displaystyle{ Y }[/math] ， [math]\displaystyle{ X \cup Y }[/math] 必有限，且 [math]\displaystyle{ \operatorname{card} (X \cup Y) \leq \operatorname{card} X + \operatorname{card} Y }[/math] 。
- （容斥原理） [math]\displaystyle{ \operatorname{card} (X \cup Y) = \operatorname{card} X + \operatorname{card} Y - \operatorname{card}(X \cap Y) }[/math] 。
- 若 [math]\displaystyle{ X }[/math] 和 [math]\displaystyle{ Y }[/math] 不相交，则 [math]\displaystyle{ \operatorname{card} (X \cup Y) = \operatorname{card} X + \operatorname{card} Y }[/math] 。
- （容斥原理） [math]\displaystyle{ \operatorname{card} (X \cup Y) = \operatorname{card} X + \operatorname{card} Y - \operatorname{card}(X \cap Y) }[/math] 。
- 对有限集 [math]\displaystyle{ X }[/math] 和子集 [math]\displaystyle{ Y \subseteq X }[/math] ， [math]\displaystyle{ Y }[/math] 必有限，且 [math]\displaystyle{ \operatorname{card} Y \leq \operatorname{card} X }[/math] 。
- 因为 [math]\displaystyle{ Y }[/math] 到 [math]\displaystyle{ X }[/math] 的包含映射是单射。
- 在此基础上，若 [math]\displaystyle{ Y \neq X }[/math] ，即 [math]\displaystyle{ Y \subset X }[/math] ， 则有 [math]\displaystyle{ \operatorname{card} Y \lt \operatorname{card} X }[/math] 。
- 对有限集 [math]\displaystyle{ X }[/math] 、 [math]\displaystyle{ Y }[/math] ， [math]\displaystyle{ X \times Y }[/math] 必有限，且 [math]\displaystyle{ \operatorname{card} (X \times Y) = \operatorname{card} X \cdot \operatorname{card} Y }[/math] 。
- 对有限集 [math]\displaystyle{ X }[/math] ， [math]\displaystyle{ \mathcal{P}(X)=2^X }[/math] 必有限，且 [math]\displaystyle{ \operatorname{card} (2 ^ X) = 2 ^ { \operatorname{card} X } }[/math] 。
- 对有限集 [math]\displaystyle{ X }[/math] 、 [math]\displaystyle{ Y }[/math] ， [math]\displaystyle{ X^Y }[/math] 必有限，且 [math]\displaystyle{ \operatorname{card} (X ^ Y) = \operatorname{card} X ^ { \operatorname{card} Y } }[/math] 。
以上指明有限集的规则，在无限下均无效。
- 对集合 [math]\displaystyle{ X }[/math] 、 [math]\displaystyle{ Y }[/math] ，若至少一个是无限集，则 [math]\displaystyle{ \operatorname{card} (X \cup Y) = \operatorname{card} X + \operatorname{card} Y = \max(\operatorname{card} X, \operatorname{card} Y) }[/math] 。
- 对集合 [math]\displaystyle{ X }[/math] 、 [math]\displaystyle{ Y }[/math] ，若至少一个是无限集，则 [math]\displaystyle{ \operatorname{card} (X \times Y) = \operatorname{card} X \cdot \operatorname{card} Y = \max(\operatorname{card} X, \operatorname{card} Y) }[/math] （若承认选择公理）。
- 对无限集 [math]\displaystyle{ X }[/math] ， [math]\displaystyle{ \mathcal{P}(X)=2^X }[/math] 有 [math]\displaystyle{ \operatorname{card} (2 ^ X) = 2^{\operatorname{card} X} \geq \operatorname{card} X }[/math] 。
- 对有限集 [math]\displaystyle{ X }[/math] 、 [math]\displaystyle{ Y }[/math] ， [math]\displaystyle{ X^Y }[/math] 有 [math]\displaystyle{ \operatorname{card} (X ^ Y) = \operatorname{card} X ^ { \operatorname{card} Y } }[/math] ，有更复杂的理论，一般 [math]\displaystyle{ \operatorname{card} X \lt \operatorname{card} Y }[/math] 时有 [math]\displaystyle{ \operatorname{card} X ^ { \operatorname{card} Y }=2 ^ { \operatorname{card} Y } }[/math] 。
特殊基数
元素个数为0当且仅当集合是空集，基数为 0 。
元素个数为1的集合，基数为1，称为单元素集或单点集。
元素个数有限的集合，基数是自然数，称为有限集(finite set)。
元素个数无限的集合称为无限集(infinite set)。
自然数集的势为 [math]\displaystyle{ \aleph_0 }[/math] ，同等大小的称为可列集(countable set)。可列集和有限集统称可数集(countable set)，而其他的则是不可数集(uncountable set)。
注：由于英语不区分“可数”“可列”两个词语，有时按照语境也会混淆两个词的使用。需要区分时，“可列”也被称为“可数无限”/“可数无穷”(countably infinite)。
自然数集与实数集的基数
实数可以通过“对角线证明”证明比自然数多，一般将其基数记作 [math]\displaystyle{ \mathfrak{c} }[/math] ，称为连续统，且 [math]\displaystyle{ \mathfrak{c}=2^{\aleph_0} }[/math] 。 连续统假设即不存在自然数集（可列集）基数和实数集基数之间的基数，即断言 [math]\displaystyle{ \mathfrak{c}=\aleph_1 }[/math] ，但目前已证明连续统假设在 ZFC 公理系统中独立，不可能在这一框架中被证明或证伪。
| 数系 | |||||
|---|---|---|---|---|---|
| 自然数 | 整数 | 有理数 | 规矩数 | 代数数 | …… |
| 实数 | 复数 | 四元数 | 八元数 | …… | |
| 扩展自然数 | 扩展实数 | 扩展复数 | …… | ||
| 基数 | 序数 | …… | |||
- ↑ 这里的 card 即来自 cardinality 的缩写。