集合是由互不相同的对象组成、被视为单一数学对象的整体。属于某个集合的对象称为该集合的元素或成员。集合可以包含数、点、函数、其他集合,或许多不同类型的对象。集合的根本特征是,它完全由元素的归属关系决定:两个集合相等,当且仅当它们拥有完全相同的元素。元素的排列顺序和重复出现的次数都不会使集合有所不同,因此 、 和 表示同一个集合。
集合为几乎所有数学分支提供了共同的语言。数系、几何空间、代数结构和概率模型,都可以用附加了运算或关系的集合来描述。集合论研究集合本身,包括集合的大小、可能的构造方式,以及支配其存在性的公理。初等集合语言广泛用于数学的各个领域,而使用这种语言并不要求接受某一种特定的数学基础理论。
将“汇集”的直观概念用作数学基础时,必须对其加以限制:并非任意条件都能无矛盾地定义出一个由所有满足该条件的对象组成的集合。因此,现代处理方式会区分通常的集合构造与不受限制的汇集。这一区分将初等集合代数与无穷理论、数理逻辑,以及关于哪些数学对象存在的基础性问题联系起来。
元素、相等与描述
涉及集合的基本关系是隶属关系。表达式 表示 是 的一个元素,而 表示它不是。例如,若 ,则 ,而 。隶属关系联系的是一个对象与一个集合;它并不意味着该对象包含这个集合中的某些元素,从而成为集合的一部分。
集合具有外延性:一个集合是什么,完全取决于它有哪些元素。形式上,
因此,列举元素时的顺序和重复都不影响所得的集合。像 这样的单元素集只有一个元素,而且它与其元素 不同。同样, 是一个集合,其唯一的元素本身也是一个单元素集。花括号的嵌套反映了隶属结构上的实质差异。
有限集可以通过在花括号内列出其元素来指定,这种方法称为列举法。无限集有时用省略号表示,例如 ,但这种记法依赖于读者对后续规律的理解。一小段起始序列未必能唯一确定一个无限集合。因此,精确定义会使用明确的条件、先前定义的构造或递归方式来指定集合。
描述法用于描述满足某个条件的元素:
它表示已指定的集合 中使 成立的那些元素。例如,
其中 表示整数。竖线读作“使得”;冒号也是常见的写法。
并非每一种有用的集合描述都能让人在实践中立即判定隶属关系。素数集有精确定义,但判断一个很大的整数是否属于它,可能需要大量计算。还有一些可定义的集合,其隶属判定问题不存在能处理所有情况的算法。因此,数学上的集合不一定是存储起来的列表,也不一定对应可行的计算过程,其元素的隶属关系也不一定能用有效方法检验。
标准集合论允许集合成为其他集合的元素。在通常的纯集合论形式中,理论中的所有对象都是集合,不过一般的数学论述往往将数、点或符号视为已有的对象。这一区别涉及数学基础中的表示方式,而不是隶属关系的基本规则。
子集、空集与论域
当集合 的每个元素都属于集合 时,称 是 的子集,记作 :
如果 且 ,则称 是 的真子集,通常记作 。不同作者对符号 的用法有所不同:有些作者仅用它表示真包含关系,另一些作者则将其与 混用。
必须区分属于关系与包含关系。如果 ,那么 且 ,但 。集合 含有的是数 ,而不是以 为唯一元素的单元素集。不过,如果明确定义一个集合同时含有某个对象及其对应的单元素集,那么这两者也可以都是该集合的元素。
空集记作 或 ,不含任何元素。外延性保证空集恰好只有一个:任意两个不含元素的集合,其元素都完全相同。空集是任何集合的子集,因为 中不存在不属于另一个集合的元素。这是真空真的全称命题的一个例子。
集合 与 不同。前者有零个元素,后者有一个元素。在用集合构造数学对象时,这类区别至关重要。这也解释了为什么一个不含任何可能结果的集合,不同于一个含有一个结果、而该结果恰好用空集表示的集合。
包含关系为一个固定集合的所有子集赋予了次序。它具有自反性、反对称性和传递性,因此是一种偏序。反对称性给出了证明集合相等的一种标准方法:
因此,可以把证明分成两部分,分别通过考察元素的归属来证明两个方向的包含关系。
许多讨论都在一个指定的全集(也称论域) 内进行。在初等问题中, 可以是某所学校的全体学生、全体实数或平面上的所有点。这个集合包含当前讨论的所有对象,而不是包含一切数学对象。标准的策梅洛—弗兰克尔集合论中,不存在包含所有集合的全集。改变论域可能改变补集,但不会改变某个固定对象是否属于某个固定集合。
并集、交集与差集
集合的基本运算通过组合元素的归属条件来构造新集合。并集 包含所有至少属于 和 之一的元素:
这里的“或”是相容或:同时属于两个集合的元素也包含在内。交集 则恰好包含两个集合共有的元素。若 、,则它们的并集为 ,交集为 。
差集 包含属于 但不属于 的元素。与并集和交集不同,差集运算不满足交换律:在这个例子中,,而 。相对于全集 ,集合 的补集是 ,通常记作 。如果两个集合的交集为空,就称它们不相交。
包含恰好只属于这两个集合之一的元素。它对应于异或,而不是相容析取。对称差运算满足结合律和交换律,且 。特别地, 的所有子集在对称差和交集这两种运算下构成一个布尔环。
并集和交集运算满足交换律、结合律、分配律、吸收律和幂等性。例如,
相对于全集的取补运算满足德摩根定律:
逐一核对元素在等式两边的归属条件,即可证明这些恒等式。例如,第一个恒等式表明:一个对象不属于这两个集合中的任何一个,当且仅当它既在第一个集合之外,也在第二个集合之外。
文氏图用一个表示 的矩形内的各个区域来表示集合。区域重叠的部分表示交集,还可以用阴影来图示集合表达式。集合数量较少时,这类图示很有用,但不能代替一般性的证明。此外,除非另有说明,图示既不反映所表示集合的实际元素个数,也不反映这些集合的几何特征。所有子集在上述运算下形成的完整代数结构,是布尔代数的一个重要实例。
幂集与指标族
的幂集记作 ,是由 的所有子集组成的集合:
如果 ,那么
空集和 本身总是属于 。如果 有 个元素,它的幂集就有 个元素,因为对于每个元素,都可以独立地选择将其纳入某个子集或排除在该子集之外。
指标族为指标集 中的每个指标 指定一个集合 ,记作 。与单纯由集合组成的集合不同,指标族保留了指标与集合之间的对应关系。不同的指标可以对应同一个集合。例如,以非负整数为指标的族 描述了一个特定的二元集合序列,其中相邻集合彼此重叠。
一个集合族的并集定义为
而对于非空集合族,其交集定义为
因此,按指标取并对应于存在量化,按指标取交则对应于全称量化。如果所有 都是某个固定集合 的子集,那么空指标集上的交集就定义为 。空族的并集是 。如果没有指定背景集合,不受限制的空族交集就会要求存在一个全集,而这在标准集合论中是不允许的。
无限运算的表现可能与有限运算不同。例如,区间
都非空,但它们的交集却是空集。没有任何正实数能对每个正整数 都小于 。相比之下,
仅仅改变是否包含一个端点,就会改变交集。
在按包含关系排序的幂集中,任意一族子集的并集是该族的最小上界,交集则是其最大下界。因此,幂集构成一个完备格。这类序理论语言为许多构造提供了统一的表述方式:一个子集族若对指定类型的取交运算封闭,就可以定义一个闭包运算;而对指定类型的取并运算封闭的条件则出现在拓扑学和测度论中。相关的封闭性要求取决于所考虑的集合族是有限的、可数的,还是不受限制的。
笛卡尔积、关系与函数
笛卡尔积将从不同集合中选取的元素组合起来,同时保留各元素的位置。对于集合 和 ,
有序对 满足
与普通的二元素集合不同,有序对区分第一坐标和第二坐标。一般来说,,不过,交换坐标便可在两者之间建立一个自然的双射。
有序对本身也可以用集合表示。1921 年提出的库拉托夫斯基表示法为
这种表示法并不是说有序对本质上具有这样的内部形式,而是为了说明,可以用集合构造出满足所需相等规则的对象。更长的元组可以通过嵌套的有序对来编码,也可以用定义在有限指标集上的函数来编码。
从 到 的二元关系是 的一个子集。当且仅当 与 具有该关系时,有序对 属于这个关系。例如,整数上的通常次序可表示为
图、序关系和等价关系都可以用这种方式表示。
函数 为 中的每个元素指定 中唯一的一个元素。它的函数图像为
集合 是它的定义域, 是它的陪域。它的像 可能是 的真子集。有些约定将函数等同于其图像;另一些约定则将定义域和陪域也明确列为函数的组成部分。
对于指标集为 的集合族 ,乘积 由定义在 上且满足 的函数 组成。因此,乘积中的每个元素都按指标从每个因子中各选取一个元素。不含任何因子的乘积是仅含空函数的单元素集。只要有一个因子为空集,乘积就是空集。对于任意非空集合族,断言其乘积非空,在通常的数学基础框架下等价于选择公理。
划分与商集
集合 的一个集合划分是一族非空且两两不相交的子集,它们的并集为 。这些子集称为块或划分块。 的每个元素恰好属于一个块。例如,
按奇偶性对 进行了划分。两两不相交的条件保证一个元素不会同时属于两个类别,而并集条件则保证没有元素被遗漏。
划分与等价关系相互对应。等价关系具有自反性、对称性和传递性。给定 上的等价关系 , 的等价类为
每个等价类都非空,任意两个等价类要么相同,要么不相交。因此,所有等价类组成的集合构成 的一个划分。反过来,一个划分也可以定义一个等价关系:规定两个元素等价,当且仅当它们属于同一个块。
将每个等价类视为一个对象。对于整数,关系
给出了模正整数 的剩余类。这样的类恰好有 个,可分别用 表示。这一构造是模算术的基础。
在商集上引入额外运算时,需要谨慎处理。用代表元表述的规则,无论选取同一等价类中的哪个代表元,都必须给出相同的结果。例如,模 的加法定义为 。这一定义是良定义的,因为将 和 替换为与它们分别同余的整数,只会使它们的和改变 的某个整数倍。如果结果不能独立于代表元的选取,所提出的规则就无法定义商集上的运算。
每个函数 都确定了其定义域的一个划分,划分块为非空的纤维 ,其中 遍历该函数的像。两个元素属于同一个块,当且仅当函数赋予它们相同的值。由此得到的商集与 之间存在自然的双射。这从概念上将函数分为两个步骤:先将输出相同的输入视为同一对象,再将由此得到的不同输出纳入陪域。
从每个块中选取一个代表元,与构造商集是两个不同的问题。商集的存在不依赖于是否选定了代表元系;而要对任意划分同时作出这些选择,则需要借助选择原理。
有限集与可数性
集合的基数描述其大小,与元素本身的性质无关。如果两个集合之间存在双射函数,即将两个集合中的元素一一配对的函数,那么这两个集合的基数相同。如果一个有限集与 之间存在双射,就称它有 个元素;其中 的情形对应空集。
对于有限集,基数遵循常见的计数法则。如果 和 都是有限集,则
并且
减去交集的基数,是为了修正交集中的元素被重复计数的问题。这些法则可以推广为组合数学中更一般的容斥公式。如果存在从某集合到一个含 个元素的有限集的单射函数,那么该集合的大小以 为上界;如果存在从某集合到这样一个有限集的满射函数,那么该集合的大小以 为下界。
如果一个集合与自然数集 之间存在双射,就称它是可数无限集。如果一个集合是有限集或可数无限集,就称它是至多可数的;可数集一词有时指这一较广的类别,而在另一些约定中则仅指可数无限集。明确说明所采用的约定可以避免歧义。将 取为 而非 ,不影响可数性。
无限集可以与其真子集具有相同的基数。映射 将 与非负偶数集一一配对。整数集也是可数的,下面的枚举就说明了这一点:
有理数虽然在数轴上稠密分布,但仍然是可数的。可以按照分子和正分母排列分数,再沿每条有限的对角线依次枚举,同时跳过重复的数值。
有限个可数集的笛卡尔积是可数的。在通常的 ZFC 框架中,可数个可数集的并集也是可数的;但在不含选择公理的基础体系中,这一命题的完全一般形式需要某种弱选择原则。然而,可数无限个可数集的笛卡尔积不一定可数:仅所有无限二进制序列就已经构成一个不可数集。
以集合与其某个真子集之间存在双射作为判据所定义的无限性,称为戴德金无限性。在 ZFC 中,它与通常的无限性等价;但在不含选择公理的策梅洛—弗兰克尔集合论中,一般无法证明这种等价性。这说明,看似熟悉的计数命题也可能隐含着有关数学基础的假设。
不可数性、基数与序数
不是至多可数的集合称为不可数集。实数集是一个重要的例子。康托尔对角线论证表明,不可能用一个序列列出所有无限二进制序列:对于任何给定的列表,都可以构造一个新序列,使其第 位不同于列表中第 个序列的第 位。这样构造的序列与列表中的每一项都至少有一位不同,因此不在列表中。
更一般的结论是康托尔定理:任何集合的基数都严格小于其幂集的基数。如果 是满射,那么集合
就必定等于某个 所对应的 。但这样一来, 当且仅当 ,产生矛盾。由于 将 嵌入 ,后者的基数严格大于前者。因此,不存在最大的基数。
的基数记作 。实数直线的基数称为连续统,其值为
连续统假设断言,不存在严格介于 与连续统之间的基数;用通常的基数记号表示,就是 。哥德尔和科恩证明,只要 ZFC 是相容的,就既不能从 ZFC 出发否证这一命题,也不能证明它。
基数衡量集合的大小,而序数描述良序集的序型。序数 是自然数集在通常次序下的序型。序型 与 的基数相同,但作为次序结构却不同:后者有最大元素,前者则没有。因此,序数之间的区别保留了基数有意舍弃的信息。
对于任意集合,可以用单射来表述基数的比较。如果两个集合各自都存在到另一个集合的单射,那么康托尔–施罗德–伯恩斯坦定理保证它们之间存在双射,且不需要使用选择公理。相比之下,任意两个集合的基数都可比较这一断言,则等价于选择公理。
无限基数的运算与有限数的运算截然不同。在选择公理成立的条件下,任何无限基数 都满足 和 。幂运算则没有这样统一的规律:康托尔定理总能保证 ,但其确切值可能取决于额外的公理。
悖论与公理化限制
“每个条件都确定一个集合”这一非形式化原则是不相容的。1901 年发现的罗素悖论考察了这样一个假定存在的集合:
询问是否有 ,就会得出矛盾:属于自身会推出不属于自身,而不属于自身又会推出属于自身。问题不在于从已知集合中进行通常的筛选,而在于不加限制地断言:这一条件定义了由所有符合条件的对象组成的集合。
策梅洛—弗兰克尔集合论避免了无限制概括。其分离公理模式允许从已有的集合 出发,构造
。将其用于罗素悖论中的条件,便得到集合 ,并不会产生矛盾;相反,上述论证推出的是 。因此,不存在包含所有集合的集合。在引入类这一术语的理论框架中,像全体集合这样的汇集称为真类,而不是集合。
ZF 以一阶逻辑表述,通常以隶属关系作为唯一的非逻辑关系。外延公理通过元素确定集合是否相等。配对公理、并集公理和幂集公理提供基本的构造方式。无穷公理断言存在无限集合。分离公理模式允许构造可定义的子集,而替换公理模式则保证:在一个集合上按可定义的函数式对应所得到的值也组成一个集合。正则公理排除了通常意义下的隶属循环和无限递降的隶属序列。
这些原则中,有些是单独的公理;分离和替换则是公理模式,为每个符合要求的公式提供一条公理。这一区别很重要,因为一阶公式不能将所有性质作为对象加以量化。ZF 之所以能够表达通常的数学,靠的是这套受到严密约束的构造机制,而不是把每个可描述的汇集都当作集合。
加入选择公理,便得到 ZFC。选择公理断言,对于任意由非空集合组成的集合,都存在一个函数,能从其中的每个成员中选取一个元素。它的等价表述包括良序原理,即每个集合都可以赋予一个良序。选择公理支持许多标准的存在性结论,但并不给出具体的选取规则。
公理化并不能解决关于集合的所有问题。在通常的相容性假设下,选择公理独立于 ZF,连续统假设独立于 ZFC。哥德尔不完备定理也限制了足够强、可有效公理化且相容的理论对于自身所能证明的内容。这些是特定形式理论的局限,而不是集合这一基本概念本身的矛盾。
累积层级与数学构造
在标准的纯集合论中,整个集合宇宙按累积层级组织起来。各层通过超限递归定义:
其中 为极限序数。后继阶段收集前一阶段的所有子集;极限阶段则收集此前各阶段出现的所有对象。在 ZF 中,每个集合都属于某一层 。
最初几层可以明确写出:
这一层包含 的四个子集。每个有限层都是有限的,但它们的并集 是无限的。其元素是遗传有限集,即自身及其元素、元素的元素,依此类推,都是有限集的集合。像 这样的集合则出现在更高的层中。
集合的秩衡量它在这一层级中所处的高度:
空集的秩为 。从集合转向其元素时,秩总是下降的,这也说明了为什么正则公理排除集合属于自身的情形。传递集是指每个元素也都是其子集的集合;等价地, 蕴含 。各层 以及序数的标准集合表示都是传递集。
自然数可以用冯·诺伊曼构造来表示:
因此,、,每个自然数都是由所有比它小的自然数组成的集合。无限序数 汇集了所有有限序数。随后便可递归地定义算术运算。
其他数系也可以分阶段构造。将自然数对解释为差,再按适当的等价关系取商,就得到整数。有理数由分母非零的整数对构造,同样需要按等价关系取商。实数可以用有理数的戴德金分割,或有理数柯西序列的等价类来构造。复数则可以表示为实数的有序对,并赋予指定的加法和乘法。
这些构造表明,通常的数学对象都可以在集合论中表示。但这并不意味着某一种编码具有唯一的内在地位:不同的构造可以产生彼此同构的数系。通常,同构所保持的算术性质和结构性质,比某种特定表示是否使一个编码后的数恰好成为另一个数的元素更为重要。
历史发展
早在现代集合论出现之前,人们就已使用汇集与类的概念,但直到十九世纪,无穷汇集才成为数学中明确的研究对象。分析学的发展要求对实数、收敛性和点集作出精确处理。伯纳德·波尔查诺在其身后于1851年出版的《无穷的悖论》中探讨了无穷的性质。理查德·戴德金关于数与映射的研究,则推动了从结构角度处理无穷系统的方法的确立。
格奥尔格·康托尔在研究三角级数和实数点集的过程中发展了集合论。他在1874年的论文中证明了代数数的可数性和实数的不可数性。这使人们得以按大小区分无穷汇集,而不再将无穷视为单一、无差别的概念。他在后来的研究中引入了超限基数和超限序数,并于1891年提出对角线论证,为证明不可数性提供了另一种方法。
1895年,康托尔将集合描述为:把直观或思维中确定的、互不相同的对象汇集成一个整体。这一表述表达了集合的直观概念,却并不是一个公理系统。悖论的发现表明,允许不受限制地形成汇集的做法需要修正。涉及全体序数、全体基数以及罗素所提出的隶属条件的矛盾,暴露了那些被认为是最大汇集的对象所存在的问题。
戈特洛布·弗雷格为算术建立的逻辑基础直接受到了罗素悖论的冲击。1902年,正当弗雷格的《算术基本规律》第二卷即将出版时,罗素将这一悖论告知了他。矛盾源于一条允许不受限制地形成值域的原则,而不只是符号选用不当。
1908年,恩斯特·策梅洛提出了一套影响深远的公理化方案,其中包含明确表述的选择公理。亚伯拉罕·弗兰克尔和托拉尔夫·斯科伦在二十世纪二十年代作出了重要改进,尤其涉及替代公理和一阶形式化。这些发展最终形成了如今称为ZF的理论。约翰·冯·诺依曼提出了序数的标准构造,并在集合论宇宙的组织结构方面作出了重要贡献。
二十世纪,独立性结果改变了这一学科的面貌。库尔特·哥德尔通过其可构造宇宙,证明了选择公理和广义连续统假设相对于ZF的相容性;相关结果于1938年公布,并在1940年的一部专著中得到系统阐述。保罗·科恩于1963年引入力迫法,证明了选择公理相对于ZF的独立性,以及连续统假设相对于ZFC的独立性。这些结果使对不同可能的集合论宇宙的研究成为该领域的核心内容之一,与贯穿整个数学的初等集合语言并行发展。
带有数学结构的集合
单纯的集合只记录包含哪些元素,并不说明元素之间如何相互作用。数学结构则为集合赋予指定的运算、关系或特殊子集。例如,群由一个集合及其上的二元运算构成,该运算满足结合律、单位元条件和逆元条件。向量空间则在一个向量集合上配备向量加法以及某个域上的标量乘法。同一个底层集合可以承载不同的结构。
底层集合与其上结构之间的区别,解释了保结构映射的作用。任意一个双射都能将元素一一配对,而群同态还必须保持乘法运算。线性映射必须保持向量加法和标量乘法。因此,基数相等并不意味着结构等价:两个代数系统可能有同样多的元素,却并不同构。
在拓扑学中,拓扑空间由集合 和一个开集族 构成。这个集合族必须包含 和 ,并且对任意并和有限交封闭。 的选择决定了连续性和收敛的性质。度量空间给出了点之间的距离,并由此诱导出一个拓扑;但许多拓扑空间的研究并不需要选定度量。
在测度论中,测度定义在指定的子集族上,而不一定定义在每个子集上。σ代数包含整个空间,并且对补集和可数并封闭。这些封闭性质保证了可测条件的可数组合仍然可测。概率空间由样本集合 、事件构成的σ代数,以及一个赋予 总质量 的概率测度组成。
将测度的定义域限制在可测子集上,有其本质原因。在选择公理成立的前提下,实数轴上的某些子集无法在不违背勒贝格测度定义性质的情况下被赋予这种测度。因此,概率模型不只是给任意一组结果赋予数值;它还规定了哪些结果的集合是模型中的事件。
集合语言也能区分不同类型的数学研究。几何学研究具有空间结构的集合;图论研究由关系连接起来的顶点;数学分析研究具有极限结构或定量结构的空间与映射。这些学科共享一些底层构造,但采用不同的等价标准,允许的运算也各不相同。用集合来表述这些研究对象,能够提供一个共同框架,同时并不取代各学科的专门概念。
逻辑诠释与其他基础体系
集合运算与逻辑联结词密切对应。对于固定的 ,
而并集对应析取,补集对应否定。类似地,带指标的并集与交集分别对应存在量化与全称量化。这种关系解释了为什么许多集合恒等式都可以通过对隶属关系命题进行逻辑变换来证明。
子集 也可以用它的示性函数表示:
在经典数学中, 的子集与这样的函数一一对应。取交集转化为逐点相乘,而取补集转化为 。这在计数、积分和概率中都很有用。
这种经典对应关系使用了每个隶属关系命题非真即假的原则。在直觉主义逻辑中,不能不经证明就认定排中律在每个具体情形下都成立。子集的隶属关系未必是可判定的,因此,未必存在一个取值于二元集合的函数,能够对每个隶属关系问题给出确定的答案。构造性集合论在改变可用的逻辑推理规则的同时,仍保留了丰富的数学内容。
类型论提供了另一种组织数学基础的方式。对象被赋予类型,而允许进行哪些构造则取决于这些类型。类型并不等同于 ZFC 意义下不加限制的集合,不过,某些具体的类型论与集合论之间存在紧密的解释关系。依赖类型可以表达成员随输入而变化的族,以证明辅助系统所采用的方式将逻辑与数学构造联系起来。
范畴论着重研究对象以及对象之间的映射。集合范畴以集合为对象,以函数为态射。它的结构性质能够刻画积、不交并和函数空间,而不必为每一种构造指定具体的隶属关系编码。大小的区分仍然重要:在通常的 ZFC 中,所有集合构成的范畴,其对象全体本身并不是一个集合大小的汇集。
“集合”一词也被推广到一些专门的方向。多重集记录元素的重数,因此,同一元素出现两次与出现一次可以有所不同。模糊集为元素赋予隶属度,通常取值于 ,而不是采用普通的非是即否的隶属关系。这些都是额外定义的数学结构,并非普通集合的外延相等原则的例外。明确区分这些概念的基础含义,有助于避免将隶属关系、频数、不确定性和分级归类混为一谈。
计算表示与应用
在计算机科学中,集合是一种抽象数据类型,支持成员判断、插入、删除、并集和交集等操作。其数学规范不考虑顺序,也不考虑重复插入。不过,具体实现必须在内存中表示元素,并确定两个已存储的值在什么情况下视为相等。数值相等、对象同一性以及用户定义的比较规则,可能导致不同的计算行为。
哈希表利用哈希值存储元素,以便定位需要进行相等性检查的候选项。在哈希方法合适且占用率得到控制的情况下,成员判断、插入和删除操作通常具有常数级的期望时间复杂度。这些复杂度结论取决于具体实现,并非数学集合本身的性质。严重的哈希冲突或不合适的输入可能使性能大幅下降。相等性规则与哈希规则必须一致:被视为相等的值必须具有相同的哈希值。
平衡搜索树提供了另一种表示方式。它要求采用的排序规则与预期的元素区分方式相容,并支持在对数时间内完成成员判断和更新。它还支持有序遍历和范围查询,而这些操作并不是无序数学集合固有的。对于较小的有限全集,可以用位向量表示其子集,为每个可能的元素分配一个比特。这样,并集和交集就转化为按位运算,通常能同时处理许多潜在成员。
完整的幂集通常过于庞大,无法逐一枚举。一个含有 个元素的全集有 个子集,因此,即使 只有适度增加,子集数量也会呈指数增长。符号表示可以描述子集族,而不必分别存储每个子集。反过来,仅列出少量成员并不能表示一个无限集,除非同时给出确定其余成员的规则。
关系数据库采用了基于集合的思想:从数学上说,关系是元组的集合,关系运算包括选择、投影和并集。实际的 SQL 系统通常默认采用保留重复项的语义,也称为多重集语义,因此数据库查询结果未必是严格数学意义上的集合。显式消除重复项会同时改变语义和计算成本。
集合也用于自动化验证和静态分析。程序状态可以建模为状态空间中的一个元素,而一组状态可以描述可能的执行情况。转移关系将当前可能的状态映射到后续可能的状态。可达性计算反复扩大一个集合,直到达到不动点,即再执行一步也不会添加任何新状态。对于有限状态空间,这一过程可以通过穷尽所有可能状态而终止;对于无限状态空间,则往往需要符号描述或近似方法。即使实现中存储的只是压缩表示或近似表示,集合的数学语言仍能明确其预期含义。