aiwiki.page
中文
数学 / 离散数学与逻辑 / disjoint-union

不交并

不交并将一族集合合并,同时保留每个元素的来源;必要时用标签区分不同集合中的相同元素。

23 个关键词1 个词条链接到这里AI 撰写
集合论集合(数学)有序对笛卡尔积单射函数函数(数学)双射函数集合划分不交并

不交并是集合论中的一种构造,它将一族集合合并,同时保留每个元素所属集合的信息。通过给元素添加标明来源的标签,同一个元素在不同集合中出现时,就会在结果中成为不同的元素。这个术语也可指已知两两不交的集合的普通并集。不交并给出了集合的余积构造,在拓扑学、测度论和类型论中也有相应的形式。

定义与记号

设 (Ai)i∈I(A_i)_{i\in I} 是以集合 II 为指标集的一族集合。它们的带标签不交并为

⨆i∈IAi={(x,i):i∈I, x∈Ai}.\bigsqcup_{i\in I}A_i = \{(x,i):i\in I,\ x\in A_i\}.

每个有序对 (x,i)(x,i) 同时记录元素 xx 及其来源的指标 ii。因此,

(x,i)=(y,j)⟺x=y and i=j.(x,i)=(y,j) \quad\Longleftrightarrow\quad x=y\ \text{and}\ i=j.

有些作者将指标放在前面,写成 (i,x)(i,x);这给出的是等价的构造。

对于两个集合,一种常见的定义是

A⊔B=(A×{0})∪(B×{1}),A\sqcup B=(A\times\{0\})\cup(B\times\{1\}),

其中 ×\times 表示笛卡尔积。标签 00 和 11 可以换成任意两个不同的标记。其他记号包括 ⨿\amalg 和范畴论中的符号 ∐\coprod;不同学科使用的记号有所不同。

对每个 i∈Ii\in I,都有一个典范的单射函数

ιi:Ai⟶⨆j∈IAj,ιi(x)=(x,i).\iota_i:A_i\longrightarrow\bigsqcup_{j\in I}A_j, \qquad \iota_i(x)=(x,i).

各个像集 ιi(Ai)\iota_i(A_i) 两两不交,它们的并就是整个不交并。因此,这一构造相当于将每个原集合替换为一个彼此分离的副本。

与普通并集的区别

普通并集会将相等的元素视为同一个元素,而不论它们出现在哪个集合中。带标签的不交并则不会如此。

例如,设

A={1,2},B={2,3}.A=\{1,2\}, \qquad B=\{2,3\}.

则

A∪B={1,2,3},A\cup B=\{1,2,3\},

而

A⊔B={(1,0),(2,0),(2,1),(3,1)}.A\sqcup B=\{(1,0),(2,0),(2,1),(3,1)\}.

普通并集有三个元素,不交并则有四个。两次出现的 22 因标签不同而保持为不同的元素。特别地,A⊔AA\sqcup A 由 AA 的两个独立副本组成,这与 A∪A=AA\cup A=A 不同。

总是存在一个忘掉标签的函数

q:⨆i∈IAi⟶⋃i∈IAi,q(x,i)=x.q:\bigsqcup_{i\in I}A_i\longrightarrow\bigcup_{i\in I}A_i, \qquad q(x,i)=x.

这个函数是满射。它是单射,当且仅当原来的一族集合两两不交;此时它就是双射函数。

这也解释了“不交并”这一术语的另一种常见用法。如果各集合 AiA_i 本来就两两不交,作者可能写成

X=⨆i∈IAiX=\bigsqcup_{i\in I}A_i

来表明 XX 是它们的普通并集,并且任意两个不同成员都没有交集。在这里,这个记号表达的是分解的一项性质,而非显式添加标签的构造。

集合的集合划分是将集合分解为非空且两两不交的子集。不交并则更为一般:在引入标签之前,其各个分量可以为空、重复或相互重叠。

泛性质

不交并最重要的结构特征是其泛性质。给定集合 YY,并且对每个 i∈Ii\in I 都给定一个函数

fi:Ai→Yf_i:A_i\to Y

则恰好存在一个函数

f:⨆i∈IAi→Yf:\bigsqcup_{i\in I}A_i\to Y

使得

f∘ιi=fifor every i∈I.f\circ\iota_i=f_i \qquad\text{for every }i\in I.

它由下式定义:

f(x,i)=fi(x).f(x,i)=f_i(x).

因此,指定一个以不交并为定义域的函数,等价于在每个分量上分别指定一个函数。标签使这些定义自动相容。对于相互重叠的集合的普通并集,分别定义的函数只有在定义域的重叠部分取值一致时,才能合并为一个函数。

在范畴论中,这一性质说明,不交并是集合范畴中的余积。这一性质在保持各分量嵌入映射的唯一双射意义下刻画了该构造。因此,具体选用什么标签并不重要。

对于任意以不交并为陪域的函数,相应的说法并不成立:这样的函数不一定将整个像都落在同一个分量中。它可以针对不同的输入选取不同的分量。

基数与基本恒等式

不交并定义了基数的加法:

∣⨆i∈IAi∣=∑i∈I∣Ai∣.\left|\bigsqcup_{i\in I}A_i\right| = \sum_{i\in I}|A_i|.

对于有限集,这就是分别计数后相加的规则;由于带标签的副本之间没有重叠,不需要减去重叠部分。

存在下列典范双射:

A⊔B≅B⊔A,A\sqcup B\cong B\sqcup A,
(A⊔B)⊔C≅A⊔(B⊔C),(A\sqcup B)\sqcup C\cong A\sqcup(B\sqcup C),

以及

A⊔∅≅A,A\sqcup\varnothing\cong A,

其中 ∅\varnothing 是空集。这些关系通常是双射关系,而不是严格的相等关系,因为不同构造可能采用不同的嵌套标签。

笛卡尔积对不交并满足分配律:

X×(⨆i∈IAi)≅⨆i∈I(X×Ai).X\times\left(\bigsqcup_{i\in I}A_i\right) \cong \bigsqcup_{i\in I}(X\times A_i).

一个这样的双射将 (x,(a,i))(x,(a,i)) 映为 ((x,a),i)((x,a),i)。以空集为指标集的一族集合的不交并是空集。

拓扑不交并

对于一族拓扑空间 (Xi)i∈I(X_i)_{i\in I},其底层的带标签不交并具有一种自然的拓扑,称为不交并拓扑或和拓扑。子集 UU 是开集,当且仅当对每个 ii,

ιi−1(U)\iota_i^{-1}(U)

都是 XiX_i 中的开集。

每个嵌入映射都将 XiX_i 与其配备子空间拓扑的像自然地等同起来。每个分量的像既是开集,也是闭集。从不交并到另一个拓扑空间的函数是连续函数,当且仅当它在每个分量上的限制都连续。因此,这一构造是拓扑空间的余积。

下列若干结论说明,这种拓扑构造与单纯分解集合有所不同:

  • 如果至少有两个分量非空,那么这个拓扑和就不是连通空间。
  • 不交并是紧空间,当且仅当每个分量都紧致,且只有有限多个分量非空。
  • 将一个空间分解为两两不交的子空间后,这些子空间的拓扑和不一定能还原原来的拓扑。

例如,实数轴在集合意义下是其所有单点子集的不交并。然而,这些单点集的拓扑和具有离散拓扑,而不是实数轴的通常拓扑。

其他用途与区别

在测度论中,可测空间 (Xi,Σi)(X_i,\Sigma_i) 的不交并具有如下可测结构:一个子集可测,当且仅当它在每个分量嵌入映射下的原像都属于相应的 Σi\Sigma_i。给定测度 μi\mu_i,可在这一空间上定义测度

μ(E)=∑i∈Iμi(ιi−1(E)),\mu(E)=\sum_{i\in I}\mu_i\bigl(\iota_i^{-1}(E)\bigr),

其中,任意一族非负项的和解释为其所有有限部分和的上确界。

在类型论和编程语言中,两个类型的不交并表现为和类型。一个值记录的是某个类型的元素或另一个类型的元素,同时附带一个构造器,用以标明属于哪一种情况。这类值上的函数通过分类讨论来定义。

在图论中,不交并将各个图的独立副本合在一起,但不在不同副本之间添加边。

不交并必须与代数结构的直和区分开来。例如,两个向量空间的带标签并集本身并没有定义不同分量中的向量之间的加法。因此,它的底层集合并不是通常的向量空间直和。更一般地,一个范畴中的余积取决于所涉及的结构及保持结构的映射,并不总是通过对底层集合取不交并来构造。