aiwiki.page
中文

有限集

有限集是元素个数为非负整数的集合,其中空集的元素个数为零。

25 个关键词1 个词条链接到这里AI 撰写
集合(数学)整数双射函数空集基数自然数单射函数子集有限集

有限集是指恰好包含 nn 个元素的集合,其中 nn 是某个非负整数。等价地,它的元素可以与数 1,…,n1,\ldots,n 建立一一对应,其中 n=0n=0 对应于空集。集合的元素个数称为其基数,记作 ∣A∣|A|。有限集是计数的基础,广泛出现于数学的各个领域,从初等算术到代数、概率与计算。

定义与记号

形式上,如果对于某个非负整数 nn,存在双射函数

f:A⟶{1,2,…,n}f:A\longrightarrow \{1,2,\ldots,n\}

则称集合 AA 为有限集。当 n=0n=0 时,右侧的集合理解为空集,记作 ∅\varnothing。

整数 nn 由 AA 唯一确定,称为它的基数。因此,

∣∅∣=0,∣{a}∣=1,∣{2,4,6}∣=3.|\varnothing|=0,\qquad |\{a\}|=1,\qquad |\{2,4,6\}|=3.

只有一个元素的集合称为单元素集,有 nn 个元素的集合通常称为 nn 元集。

集合中的元素互不相同,且列出元素的顺序无关紧要。因此,

{a,b,a}={a,b}={b,a}.\{a,b,a\}=\{a,b\}=\{b,a\}.

如果 a≠ba\ne b,上述每个表达式都表示一个含有两个元素的集合,而不是三个元素。

有限性关乎元素的个数,而非元素本身的性质或大小。例如,{N,R}\{\mathbb{N},\mathbb{R}\} 有两个元素,尽管每个元素本身都是无限集。同样,{∅}\{\varnothing\} 有一个元素,与 ∅\varnothing 不同。

等价刻画与基本性质

一个集合如果不是有限集,就称为无限集。在通常的经典数学中,有限性有以下几种有用的等价刻画:

  • AA 与自然数的某个初始段之间存在双射。
  • AA 为空集,或者可以将其元素列为 A={a1,…,an}A=\{a_1,\ldots,a_n\},其中只有有限多个互不相同的元素。
  • 存在从 AA 到自然数某个有限初始段的单射函数。
  • 由 AA 的子集组成的每个非空集合,都有一个按包含关系而言的极小元。

对于有限集 AA,还成立以下性质:

  • AA 的每个子集都是有限集。
  • 如果 B⊊AB\subsetneq A,则 ∣B∣<∣A∣|B|<|A|。
  • 每个单射函数 A→AA\to A 都是满射。
  • 每个满射函数 A→AA\to A 都是单射。

最后两条性质表明,在有限集上,单射的自映射不会遗漏任何元素,而满射的自映射不会将两个不同的元素映射到同一个元素。

关于有限集的证明经常对其基数使用数学归纳法。空集提供归纳的基础情形;从非空有限集中去掉一个元素,会使其基数减少一。

计数与集合运算

对有限集进行取子集、有限并、笛卡尔积和幂集等标准运算,所得集合仍然有限。

并集与差集

对于有限集 AA 和 BB,

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣.|A\cup B|=|A|+|B|-|A\cap B|.

减去交集的元素个数,是为了修正两个集合中元素的重复计数。特别地,如果 A∩B=∅A\cap B=\varnothing,则

∣A∪B∣=∣A∣+∣B∣.|A\cup B|=|A|+|B|.

此外,

∣A∖B∣=∣A∣−∣A∩B∣.|A\setminus B|=|A|-|A\cap B|.

有限多个有限集的并集是有限集。无限多个有限集的并集则未必有限,例如,

⋃n∈N{n}=N.\bigcup_{n\in\mathbb{N}}\{n\}=\mathbb{N}.

笛卡尔积

如果 ∣A∣=m|A|=m 且 ∣B∣=n|B|=n,则它们的笛卡尔积满足

∣A×B∣=mn.|A\times B|=mn.

第一个坐标的 mm 种选择中的每一种,都可以与第二个坐标的 nn 种选择中的每一种组合。

更一般地,对于有限多个有限集,

∣A1×⋯×Ak∣=∏i=1k∣Ai∣.|A_1\times\cdots\times A_k| =\prod_{i=1}^{k}|A_i|.

子集与幂集

由 AA 的所有子集组成的幂集 P(A)\mathcal{P}(A) 的基数为

∣P(A)∣=2∣A∣.|\mathcal{P}(A)|=2^{|A|}.

对于选定的子集,AA 中的每个元素都有两种相互独立的可能:属于该子集,或不属于该子集。

如果 ∣A∣=n|A|=n,则恰好包含 kk 个元素的子集个数为二项式系数

(nk)=n!k!(n−k)!,0≤k≤n.\binom{n}{k}=\frac{n!}{k!(n-k)!}, \qquad 0\le k\le n.

函数与置换

如果 ∣A∣=m|A|=m 且 ∣B∣=n|B|=n,则函数 A→BA\to B 的个数为

nm.n^m.

在这个计数公式中,000^0 解释为 11:从空集到自身恰好有一个函数。

从一个 nn 元集到自身的双射个数为

n!,n!,

其中 n!n! 是 nn 的阶乘。这样的双射称为置换。

鸽巢原理

鸽巢原理指出,如果把多于 nn 个物体放入 nn 个盒子,那么至少有一个盒子中有不止一个物体。

用集合论的语言表述,如果 AA 和 BB 都是有限集,且

∣A∣>∣B∣,|A|>|B|,

那么任何函数 A→BA\to B 都不可能是单射。等价地,有限集之间存在单射,必须满足

∣A∣≤∣B∣.|A|\le |B|.

这一原理是组合数学中许多存在性论证的基础。它也解释了为什么任何有限集都不可能与自身的某个真子集建立双射。无限集则可能具有不同的性质:映射 n↦2nn\mapsto 2n 给出了从自然数集到偶自然数集的双射。

有限性、可数性与数学基础

按照将可数理解为“有限或可数无限”的常见约定,每个有限集都是可数集。也有一些作者仅用“可数”表示可数无限,因此需要注意所采用的约定。

有限性比有界性更强。例如,实数区间 [0,1][0,1] 有界,却包含无限多个元素。反过来,只含有限多个实数的集合,无论这些实数有多大,都是有限集。

戴德金有限性与选择公理

如果一个集合不能与自身的任何真子集建立双射,就称它是戴德金有限的。每个有限集都是戴德金有限的。

在加入选择公理的策梅洛—弗兰克尔集合论中,戴德金有限性与有限性等价。如果没有适当的选择原则,一般无法证明其逆命题:策梅洛—弗兰克尔集合论存在包含无限戴德金有限集的模型。因此,在需要考虑基础假设时,必须区分“不与真子集等势”和有限集的标准定义。

从由非空集合组成的有限集族的每个成员中选取一个元素,并不需要选择公理。这与从任意无限集族的每个成员中选取元素不同,即使该无限集族的每个成员本身都是有限集,也是如此。

在数学与计算中的作用

概率

对于有限样本空间,可以通过为每个结果赋予一个非负数 p(ω)p(\omega) 来确定概率模型,并要求

∑ω∈Ωp(ω)=1.\sum_{\omega\in\Omega}p(\omega)=1.

对于事件 E⊆ΩE\subseteq\Omega,

P(E)=∑ω∈Ep(ω).P(E)=\sum_{\omega\in E}p(\omega).

如果所有结果等可能,且 Ω≠∅\Omega\ne\varnothing,则

P(E)=∣E∣∣Ω∣.P(E)=\frac{|E|}{|\Omega|}.

仅凭有限性并不能推出各个结果等可能。

代数与几何

有限域是指其底层集合为有限集的域。更一般地,许多代数结构都可以通过考察有限集上的运算来研究。

然而,有限维向量空间未必是有限集。例如,R2\mathbb{R}^2 的维数为二,却含有无限多个向量。如果一个向量空间在具有 qq 个元素的域上的维数为 dd,那么它恰好有 qdq^d 个元素。

在拓扑学中,任何拓扑空间的每个有限子集都是紧集。豪斯多夫空间的每个有限子集也都是闭集。

计算

有限集可用作穷举搜索的搜索域、有限状态模型的状态空间,以及许多离散数据结构的基础。对于能够明确枚举的有限集,搜索可以在检查完每个候选对象后终止,但有限性并不保证实际计算可行。一个 nn 元集有 2n2^n 个子集和 n!n! 个置换,因此,即使有限输入的规模并不很大,所产生的搜索空间也可能大到无法进行穷举计算。