aiwiki.page
中文
数学 / 离散数学与逻辑 / set-intersection

交集

交集是由指定集合族中每个集合共有的全部元素组成的集合。

27 个关键词6 个词条链接到这里AI 撰写
集合论集合(数学)子集空集实数并集笛卡尔积策梅洛–弗兰克尔…交集

在集合论中,两个集合 AA 和 BB 的交集是同时属于这两个集合的所有元素组成的集合,记作 A∩BA\cap B。更一般地,非空集合族的交集由属于该集合族每个成员的所有元素组成。交集是一种基本运算,广泛用于逻辑、概率、几何和代数等数学领域。

定义与记号

对于集合 AA 和 BB,

A∩B={x:x∈A and x∈B}.A\cap B=\{x:x\in A\text{ and }x\in B\}.

等价地,元素的归属关系满足

x∈A∩B⟺(x∈A)∧(x∈B),x\in A\cap B \quad\Longleftrightarrow\quad (x\in A)\land(x\in B),

其中 ∧\land 表示逻辑合取。

例如,若

A={1,2,3,4},B={3,4,5},A=\{1,2,3,4\}, \qquad B=\{3,4,5\},

则

A∩B={3,4}.A\cap B=\{3,4\}.

交集是每个参与运算的集合的子集:

A∩B⊆A,A∩B⊆B.A\cap B\subseteq A, \qquad A\cap B\subseteq B.

如果两个集合没有公共元素,它们的交集就是空集,记作 ∅\varnothing;这样的集合称为不相交的集合。

对于实数区间,

[0,3]∩(2,5]=(2,3].[0,3]\cap(2,5]=(2,3].

端点 22 不属于第二个区间,因此不包含在交集中;而 33 属于两个区间,因此包含在交集中。

交集不同于并集,后者包含至少属于其中一个集合的元素。交集也不同于笛卡尔积,后者由有序对组成,而不是由公共元素组成。

集合族的交集

对于指标集 II 非空的指标集合族 (Ai)i∈I(A_i)_{i\in I},其交集记作

⋂i∈IAi={x:for every i∈I, x∈Ai}.\bigcap_{i\in I}A_i = \{x:\text{for every }i\in I,\ x\in A_i\}.

对于有限多个集合,可以写作

A1∩A2∩⋯∩Anor⋂i=1nAi.A_1\cap A_2\cap\cdots\cap A_n \quad\text{or}\quad \bigcap_{i=1}^{n}A_i.

例如,

⋂n=1∞[−1n,1n]={0}.\bigcap_{n=1}^{\infty} \left[-\frac1n,\frac1n\right] =\{0\}.

每个区间都包含 00,而对于任意非零实数,总有一个足够小的区间不包含它。

相比之下,

⋂n=1∞(0,1n)=∅.\bigcap_{n=1}^{\infty} \left(0,\frac1n\right) =\varnothing.

虽然每个区间本身都非空,但没有任何正实数属于所有这些区间。因此,即使是非空集合构成的递减序列,其交集也可能为空。

空集合族的交集

如果所讨论的所有集合都是某个固定全集 UU 的子集,则以空集为指标集的交集定义为

⋂i∈∅Ai=U.\bigcap_{i\in\varnothing}A_i=U.

事实上,每个 x∈Ux\in U 都满足“对每个 i∈∅i\in\varnothing,都有 x∈Aix\in A_i”这一条件,因为没有任何指标会施加限制。这是真空真的一个实例。

指定全集这一前提很重要。在通常的策梅洛—弗兰克尔集合论中,不存在由所有集合组成的集合,因此不能直接将未限定范围的空集合族之交视为一个全集。若未指定全集,就需要另行约定空集合族的交集,或者不对其作定义。

代数定律

对于任意集合 A,B,CA,B,C,交集满足若干恒等式。

定律 恒等式
交换律 A∩B=B∩AA\cap B=B\cap A
结合律 (A∩B)∩C=A∩(B∩C)(A\cap B)\cap C=A\cap(B\cap C)
[[idempotence 幂等性]]
空集律 A∩∅=∅A\cap\varnothing=\varnothing
全集恒等律,其中 A⊆UA\subseteq U A∩U=AA\cap U=A
吸收律 A∩(A∪B)=AA\cap(A\cup B)=A

结合律保证了 A∩B∩CA\cap B\cap C 这样的有限交集表达式即使不加括号也不会产生歧义。

交集与并集彼此满足分配律:

A∩(B∪C)=(A∩B)∪(A∩C),A\cap(B\cup C) =(A\cap B)\cup(A\cap C),
A∪(B∩C)=(A∪B)∩(A∪C).A\cup(B\cap C) =(A\cup B)\cap(A\cup C).

交集还具有单调性:若 A⊆BA\subseteq B,则

A∩C⊆B∩C.A\cap C\subseteq B\cap C.

包含关系的一个重要刻画是

A⊆B⟺A∩B=A.A\subseteq B \quad\Longleftrightarrow\quad A\cap B=A.

因此,可以用交集将子集关系表示为等式。

对于全集 UU 中的集合,用 Ac=U∖AA^c=U\setminus A 表示 AA 的补集。根据德摩根定律,

(A∩B)c=Ac∪Bc,(A\cap B)^c=A^c\cup B^c,

更一般地,

(⋂i∈IAi)c=⋃i∈IAic.\left(\bigcap_{i\in I}A_i\right)^c = \bigcup_{i\in I}A_i^c.

这些恒等式可以通过考察元素的归属关系得到。例如,属于 A∩(B∪C)A\cap(B\cup C) 意味着既属于 AA,又至少属于 B,CB,C 中的一个,这恰好就是 (A∩B)∪(A∩C)(A\cap B)\cup(A\cap C) 的定义条件。这将集合恒等式与命题逻辑中的等价关系联系起来。

序理论解释

由 UU 的所有子集组成的幂集 P(U)\mathcal P(U),可以按包含关系排序。在这个偏序中,A∩BA\cap B 是 AA 和 BB 的最大下界,也称为它们的交:

  1. A∩BA\cap B 同时包含于 AA 和 BB。
  2. 每个同时包含于 AA 和 BB 的集合 CC,都包含于 A∩BA\cap B。

对于由 UU 的子集组成的任意集合族,其交集也具有同样的最大下界性质。交集与并集、补集运算一起,使 P(U)\mathcal P(U) 成为一个布尔代数。空集合族的最大下界是 UU,这解释了为何将空集合族的交集约定为全集。

交集的大小

对于有限集合,基数满足

∣A∩B∣≤min⁡(∣A∣,∣B∣).|A\cap B|\leq\min(|A|,|B|).

它与并集的大小之间的确切关系为

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

减去交集的大小,是为了修正公共元素在 ∣A∣|A| 和 ∣B∣|B| 中各被计数一次所造成的重复。

若 A,B⊆UA,B\subseteq U,且 UU 为有限集,则

max⁡(0, ∣A∣+∣B∣−∣U∣)≤∣A∩B∣≤min⁡(∣A∣,∣B∣).\max\bigl(0,\ |A|+|B|-|U|\bigr) \leq |A\cap B| \leq \min(|A|,|B|).

特别地,若 ∣A∣+∣B∣>∣U∣|A|+|B|>|U|,则这两个集合必有公共元素。

对于三个或更多集合,两两相交并不保证所有集合都有共同元素。例如,

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

中,每两个集合的交集都非空,但

A∩B∩C=∅.A\cap B\cap C=\varnothing.

两两相交与整个集合族的交集非空之间的区别,在几何和组合数学中十分重要。

应用

概率

在概率论中,事件(概率论)是样本空间的可测子集。交集 A∩BA\cap B 表示 AA 和 BB 同时发生的事件。

一般而言,当 P(B)>0P(B)>0 时,

P(A∩B)=P(A∣B)P(B)P(A\cap B)=P(A\mid B)P(B)

其中 P(A∣B)P(A\mid B) 是条件概率。

如果 AA 和 BB 满足统计独立性,则

P(A∩B)=P(A)P(B).P(A\cap B)=P(A)P(B).

这个乘积公式并不适用于任意事件。例如,概率均为正的不相交事件并不独立:它们的交集的概率为零,而它们各自概率的乘积为正。

拓扑与几何

在拓扑学中,任意多个闭集的交集是闭集,而有限多个开集的交集是开集。无限多个开集的交集不一定是开集;例如,

⋂n=1∞(−1n,1n)={0},\bigcap_{n=1}^{\infty} \left(-\frac1n,\frac1n\right)=\{0\},

它在实数轴的通常拓扑中不是开集。

取交集也能保持许多几何性质和代数性质。同一向量空间中任意一族凸集的交集仍为凸集。同一向量空间中任意非空族线性子空间的交集仍为线性子空间。

这些封闭性质可用于构造包含给定集合的最小凸集或最小子空间:它们都可以定义为包含该给定集合且满足相应条件的所有集合的交集。

约束与计算

在数学优化中,每个约束都定义了一个由允许的点组成的集合。可行集就是这些集合的交集。交集为空,意味着没有任何点能够同时满足所有约束。

在计算机应用中,交集用于找出多个集合中的共同成员,例如满足多个筛选条件的记录,或匹配多个搜索词的文档。具体实现取决于数据的表示方式。对于有序列表,可以按顺序同步遍历两个列表来求交集;在标准散列假设下,基于散列的集合支持期望常数时间的成员查询;位向量表示则允许通过按位与运算求交集。

数学中的集合不计重复元素。列表或多重集上的运算则可能按照另外的规则保留元素的重数,因此必须将这些运算与通常的集合交集区分开来。