引言:先说清对象,再讨论对象之间的规则
一份课程名单、传感器编号、坐标点和模型标签看起来毫不相同,却都要求先回答两个问题:正在讨论哪些对象,以及对象之间允许怎样对应。集合给出对象的范围,映射给出从一个范围到另一个范围的确定规则。微积分里的函数、线性代数里的变换、概率论里的随机变量和计算机中的查找表,都建立在这两层语言之上。
本章从有限集合开始,因为每个结论都能逐项枚举复核;定义本身并不限于有限集合。正文采用通常的基础数学语言,不建立完整公理集合论。形如“所有满足某条件的对象”的集合,默认在已经说明的论域内取值,避免把无限制的自指描述误当成合法集合。
审阅状态说明:本文仍是 draft,checked 只记录本轮对定义、有限枚举、证明步骤和官方来源的自检。humanReviewer 保持为空,可访问性检查仍为待办;这些状态不表示已经完成独立人工审阅。
术语、符号与对象类型
| 写法 | 对象类型 | 含义 |
|---|
| x∈A | 对象与集合 | x 是 A 的元素 |
| x∈/A | 对象与集合 | x 不是 A 的元素 |
| A⊆B | 集合与集合 | A 的每个元素都属于 B |
| A⊊B | 集合与集合 | A⊆B 且 A=B |
| ∅ | 集合 | 不含任何元素的空集 |
| A∪B、A∩B | 集合 | 并集与交集 |
| A∖B | 集合 | 属于 A 但不属于 B 的元素 |
| P(A) | 集合 | A 的全部子集组成的幂集 |
| A×B | 集合 | 第一坐标来自 A、第二坐标来自 B 的有序对集合 |
| ∣A∣ | 非负整数或基数 | 集合的大小;有限集时是元素个数 |
| f:X→Y | 函数 | 定义域为 X、陪域为 Y 的映射 |
| f(S) | 集合 | S⊆X 在 f 下的像 |
| f−1(T) | 集合 | T⊆Y 在 f 下的原像 |
| g∘f | 函数 | 先执行 f,再执行 g |
成员关系与子集关系不能互换。例如对
A={1,{2,3}},有
1∈A、{2,3}∈A,但 2∈/A;同时
{1}⊆A,却没有 {1}∈A。斯坦福大学 CS103 的官方
成员与子集讲义
专门用对象类型解释 ∈ 与 ⊆ 的差别,可作为这一符号边界的外部核对。
集合、子集与相等
集合的外延相等
集合由其元素决定。两个集合相等,当且仅当它们拥有完全相同的元素:
A=B⟺∀x(x∈A⟺x∈B).
集合不记录排列顺序,也不重复计数。因此
{1,2,2,3}={3,2,1}。若顺序或重复次数重要,应改用序列、多重集或其他结构,而不是暗中改变“集合”的含义。
子集定义为
A⊆B⟺∀x(x∈A⟹x∈B).
证明 A=B 的标准方法是双向包含:先证明任意 x∈A 都属于 B,再证明任意 x∈B 都属于 A。这个方法直接使用外延相等,不依赖图形面积或元素书写次序。
并集、交集和差集可用成员条件定义:
A∪BA∩BA∖B={x:x∈A 或 x∈B},={x:x∈A 且 x∈B},={x:x∈A 且 x∈/B}.
例如证明 De Morgan 律
A∖(B∪C)=(A∖B)∩(A∖C)。任取 x,逐步改写成员条件:
x∈A∖(B∪C)⟺x∈A 且 x∈/B∪C⟺x∈A 且 x∈/B 且 x∈/C⟺x∈(A∖B)∩(A∖C).
两侧对任意 x 的成员条件等价,所以集合相等。Venn 图能提示结论,但这条成员链才是证明。
空集与幂集
空集 ∅ 没有元素。对任意集合 A,都有
∅⊆A:因为不存在一个 x∈∅ 能违反“若 x∈∅,则 x∈A”。这是空真,不是说空集中藏有某个特殊元素。
A 的幂集定义为
P(A)={S:S⊆A}.
若 A={a,b},则
P(A)={∅,{a},{b},{a,b}}.
注意 a∈A,而 {a}∈P(A)。前者是原集合的元素,后者是幂集的元素。有限集 A 有 n 个元素时,每个元素都有“选入子集”或“不选入子集”两种独立选择,所以
∣P(A)∣=2n。
幂集中的元素本身都是集合,这一点在概率论中尤其重要:样本空间的一个事件是样本点的集合,而全部事件候选组成样本空间幂集的子集族。空集对应不可能事件,整个样本空间也是自身的一个子集。
笛卡尔积与有序对
笛卡尔积
两个集合 A,B 的笛卡尔积是
A×B={(a,b):a∈A, b∈B}.有序对的坐标位置属于定义的一部分;通常 (a,b)=(b,a)。
若 A={1,2}、B={u,v,w},则
A×B={(1,u),(1,v),(1,w),(2,u),(2,v),(2,w)}.
有限情形下,每个 a∈A 都能与 B 中的 ∣B∣ 个元素配对。不同第一坐标产生互不相同的有序对,因此
∣A×B∣=∣A∣∣B∣.
若 A 或 B 为空集,则没有合法有序对,乘积为空;计数式仍成立。一般而言 A×B 与 B×A 不相等,但交换坐标的映射 (a,b)↦(b,a) 在二者之间给出双射。
笛卡尔积还固定了变量的类型。例如一张“学生—课程”登记表可以看成学生集合与课程集合的笛卡尔积的子集;把两个坐标交换后,得到的是“课程—学生”记录。信息相同但字段职责不同,不能在公式中随意交换。
映射的严格定义
函数或映射
函数 f:X→Y 可表示为 X×Y 的一个子集 Gf,并满足:对每个 x∈X,存在唯一的 y∈Y 使 (x,y)∈Gf。把这个唯一输出记为 f(x)。
“存在”保证定义域内没有漏掉输入,“唯一”保证一个输入不会同时得到两个输出。定义域 X、陪域 Y 和对应规则共同确定函数。实际出现的输出组成值域或像集
f(X)={f(x):x∈X}⊆Y.
值域可以小于陪域。同一张输入输出表若更换陪域,满射性质可能改变,因而不能只看公式或有序对。麻省理工学院开放课程(下文简称 MIT OCW)的
《计算机科学数学》官方教材
在“Mathematical Data Types”部分同样把函数作为带定义域和陪域的确定关系处理,并用箭头性质区分单射与满射。
例题一:从笛卡尔积筛出一个函数
例 1:有限关系是否构成函数
设 X={1,2,3}、Y={a,b},关系
R={(1,a),(2,a),(3,b)}⊆X×Y.逐个检查定义域:1,2,3 都恰好作为一次第一坐标出现,所以 R 定义了函数 f:X→Y。输出 a 被 1,2 同时命中,输出 b 被 3 命中。因而值域为
f(X)={a,b}=Y。
若删除 (3,b),输入 3 没有输出,关系不是定义域为 X 的函数。若再加入 (1,b),输入 1 有两个不同输出,也不是函数。有限表格中的函数检查必须同时核对“无遗漏”和“无冲突”。
这个例子也说明“关系”比“函数”更宽。任意 X×Y 的子集都是从 X 到 Y 的二元关系,只有满足全定义且单值的关系才是函数。判定时先检查函数性,再讨论单射或满射;对一个尚非函数的关系直接贴上“单射函数”标签没有意义。
单射、满射与双射
对函数 f:X→Y:
- 单射要求 f(x1)=f(x2)⟹x1=x2,即不同输入不会碰到同一输出;
- 满射要求对每个 y∈Y,都存在 x∈X 使 f(x)=y,即陪域没有漏点;
- 双射同时满足单射与满射,每个 y∈Y 恰有一个原像元素。
例题一中的 f 是满射但不是单射,因为 f(1)=f(2)=a。对有限集合,若 ∣X∣>∣Y∣,函数 X→Y 不可能单射;若 ∣X∣<∣Y∣,则不可能满射。这是抽屉原理的直接表现。集合大小相同仍不足以自动得到双射,还要核对具体对应。
例题二:平方映射的像与原像
例 2:定义域、陪域与碰撞共同决定性质
令
X={−2,−1,0,1,2},Y={0,1,4},q(x)=x2.全部输出依次为 4,1,0,1,4,所以
q(X)={0,1,4}=Y,函数是满射。它不是单射,因为
q(−2)=q(2) 且 q(−1)=q(1)。
取 S={−2,0,1}⊆X,则
q(S)={4,0,1}=Y.取 T={1,4}⊆Y,原像为
q−1(T)={−2,−1,1,2}.这里 q−1(T) 是集合原像,不要求 q 可逆。若把陪域扩大为
Y′={0,1,4,9} 而保持同一输入和公式,值域仍是
{0,1,4},函数立即不再满射。
平方映射的两次碰撞还能用原像大小复核:0 的原像含一个元素,1 与 4 的原像各含两个元素,合计 1+2+2=5=∣X∣。满射只要求这些原像都非空,并不要求它们大小相同。
像与原像的运算规律
对 S⊆X 与 T⊆Y,定义
f(S)={f(x):x∈S},f−1(T)={x∈X:f(x)∈T}.
原像保留并集、交集和相对于陪域的补集。例如
f−1(C∩D)=f−1(C)∩f−1(D).
证明只需追踪一个元素:
x∈f−1(C∩D)⟺f(x)∈C∩D⟺f(x)∈C 且 f(x)∈D⟺x∈f−1(C)∩f−1(D).
像对并集有等式
f(S∪T)=f(S)∪f(T),但对交集一般只有
f(S∩T)⊆f(S)∩f(T).
要把包含升级为等式,需要 f 在相关输入上单射。原因是右侧同一个输出可能分别来自 S 和 T 中两个不同输入,并不保证存在一个同时属于两集合的输入。
原像的等式更稳定,因为判断 x 是否进入原像时始终考察同一个输入 x;像的交集则可能把来自不同输入的相同输出合并。证明像相关等式时,应主动检查是否暗中需要单射条件。
反例:像不总是保留交集
两个不同输入碰到同一输出
令 f:R→R 为 f(x)=x2,并取
S={−1}、T={1}。因为 S∩T=∅,所以
f(S∩T)=∅。但是
f(S)={1}=f(T),f(S)∩f(T)={1}.因此两侧不相等。失败来自平方函数的非单射性,不是集合运算规则突然改变。
左侧先求输入交集,两个不同输入被消去;右侧先映射,平方函数已经把它们合并为同一输出,之后再取交集无法恢复输入身份。若 f 在 S∪T 上单射,这种碰撞不会发生,反向包含也能证明,像的交集等式才成立。
复合映射与顺序
若 f:X→Y、g:Y→Z,复合映射
g∘f:X→Z 定义为
(g∘f)(x)=g(f(x)).
右侧的 f 先执行。陪域与下一层定义域必须匹配,或至少保证 f(X) 落在 g 的定义域内。复合满足结合律,因为对每个输入 x,
(h∘(g∘f))(x)=h(g(f(x)))=((h∘g)∘f)(x).
复合通常不交换;先把摄氏温度转成华氏温度再四舍五入,与先四舍五入摄氏值再换算可能不同。
单射与满射在同类复合下保持。若 f,g 都是单射,且
(g∘f)(x1)=(g∘f)(x2),由 g 单射得到
f(x1)=f(x2),再由 f 单射得到 x1=x2。若 f,g 都是满射,任取 z∈Z,先由 g 满射找到 y∈Y 使 g(y)=z,再由 f 满射找到 x∈X 使 f(x)=y,于是
(g∘f)(x)=z。
例题三:复合与逆向复算
例 3:三步有限双射
设
X={1,2,3}、Y={a,b,c}、Z={10,20,30}。定义
f(1)=a, f(2)=b, f(3)=c,g(a)=10, g(b)=20, g(c)=30.每个函数都让定义域与陪域逐点一一对应,因此均为双射。复合结果为
(g∘f)(1)=10,(g∘f)(2)=20,(g∘f)(3)=30.逆向计算时先用 g−1,再用 f−1。例如
30↦c↦3,所以
(g∘f)−1=f−1∘g−1.顺序反转来自“撤销最后一步必须最先进行”。把三个输入逐项往返后都回到自身,给出有限表上的完整复算。
逐项往返还验证了两个恒等式:对每个 x∈X,先做复合再做其逆得到 x;对每个 z∈Z,先做逆再做复合得到 z。有限表上的这两轮检查分别对应左逆和右逆条件,缺一轮都不足以证明函数在声明的两端可逆。
逆映射存在的充要条件
函数 f:X→Y 的逆映射是一个函数
f−1:Y→X,满足
f−1∘f=idX,f∘f−1=idY.
若逆映射存在,第一式说明
f(x1)=f(x2) 时对两侧应用 f−1 可得
x1=x2,所以 f 单射;第二式说明每个
y∈Y 都等于 f(f−1(y)),所以 f 满射。因此可逆推出双射。
反过来,若 f 是双射,则每个 y∈Y 至少有一个原像(满射),且至多有一个原像(单射)。把这个唯一元素定义为 f−1(y),便得到满足两条恒等式的函数。因此
f 可逆⟺f 是双射.
符号 f−1 有两个相关但不同的用法:f−1(T) 作为集合原像对任意函数都有定义;f−1(y) 作为逆函数值只有在已经建立双射时才有定义。上下文必须说明输入是集合还是单个陪域元素。
有限集实验:计算前的预测
本章没有调用现有 InteractiveFigure。当前实验插件处理线性变换、梯度、波与神经网络等连续或模型化对象,把它们借来展示有限集合会混淆实验模型。这里采用可以手算、复制和逐项核对的有限集枚举。
设
A={a,b,c,d},B={0,1,2},
候选对应为
F={(a,0),(b,1),(c,1),(d,2)}.
计算前先写预测:A 有四个元素而 B 只有三个元素,所以任何函数
A→B 都不可能单射;但满射仍然可能。还应检查每个第一坐标是否恰好出现一次,而不能仅凭元素个数断言 F 是函数。
有限集实验:枚举、代码与复算
逐项扫描 F:a,b,c,d 各出现一次,故它确实定义函数。输出集合为
{0,1,2}=B,所以满射;b,c 同时映到 1,所以不是单射。三个单点原像为
F−1({0})={a},F−1({1})={b,c},F−1({2})={d}.
下面的纯函数复现同一检查。输入按有序对列表给出,输出包括是否为函数、像集、碰撞和遗漏陪域元素;排序只为让结果稳定。
type Pair = readonly [string, number];
export function inspectFiniteMapping(
domain: readonly string[],
codomain: readonly number[],
pairs: readonly Pair[],
) {
const domainSet = new Set(domain);
const codomainSet = new Set(codomain);
const uniquePairs = [...new Map(pairs.map((pair) => [`${pair[0]}\0${pair[1]}`, pair])).values()];
const outputs = new Map<string, number[]>();
for (const [input, output] of uniquePairs) {
outputs.set(input, [...(outputs.get(input) ?? []), output]);
}
const pairsStayInsideDeclaredSets = uniquePairs.every(
([input, output]) => domainSet.has(input) && codomainSet.has(output),
);
const isFunction =
pairsStayInsideDeclaredSets && domain.every((input) => outputs.get(input)?.length === 1);
const image = [...new Set(uniquePairs.map(([, output]) => output))].sort((a, b) => a - b);
const collisions = image.filter(
(output) => uniquePairs.filter(([, candidate]) => candidate === output).length > 1,
);
const missing = codomain.filter((output) => !image.includes(output));
return { isFunction, image, collisions, missing };
}
代入本实验数据应得到
{ isFunction: true, image: [0, 1, 2], collisions: [1], missing: [] }。这与手算一致。若删掉 (d,2),isFunction 变为 false,因为定义域元素 d 被漏掉;若保留全部有序对但把陪域改成
B′={0,1,2,3},函数仍成立,missing 变为 [3],因而不再满射。
实验后的分析
实验把四个容易混合的判断拆开了。函数性检查第一坐标是否完整且唯一;单射性检查不同第一坐标是否碰到同一输出;满射性比较像集与声明的陪域;双射性要求后两项同时成立。改变陪域不会改变有序对列表,却会改变满射结论,这正说明函数元数据不是可省略的装饰。
三个单点原像互不相交且并为整个定义域,这是函数把定义域按输出值分组的结果。碰撞发生在原像大小大于一的输出上。对有限集,这些原像大小之和等于 ∣A∣;本例为
1+2+1=4。该计数核对只验证当前有限数据,不代替一般定义或无限集合上的证明。
常见边界与误读
同一公式代表同一个函数
x↦x2 从 R 到 [0,∞) 是满射但非单射;从 [0,∞) 到 [0,∞) 是双射;从 R 到 R 既非单射也非满射。公式相同,定义域和陪域不同,得到的函数性质就不同。
原像符号已经表示逆函数
任何函数都能计算集合原像。非单射的平方函数仍有
q−1({1})={−1,1};这不是一个单值逆函数。只有双射才允许把每个陪域元素唯一送回定义域。
画出箭头就完成了证明
有限箭头图可以完整枚举一个小函数;对无限集合,它只能展示样例。一般性结论必须从量词定义推出,不能把几根箭头当成覆盖所有输入的证据。
练习
练习 1
- 所属知识
- 集合运算与笛卡尔积
- 难度
- 1/5
设 A={1,2,4}、B={2,4}。求
A∩B、A∖B,完整列出 A×B,并判断
A×B 是否等于 B×A。
查看提示
先分别列出交集和差集,再按第一坐标分组枚举有序对。
查看解答
复核过的解答:A∩B={2,4},A∖B={1}。A×B 依次为 (1,2)、(1,4)、(2,2)、(2,4)、(4,2)、(4,4),共 3×2=6 个;B×A 也有 6 个,但例如 (2,1) 属于 B×A 而不属于 A×B,所以两集合不相等。
练习 2
- 所属知识
- 函数、单射与满射
- 难度
- 2/5
设 X={0,1,2}、Y={a,b},
R={(0,a),(1,b),(2,b)}。判断 R 是否定义函数,并判断它是否单射、满射或双射。
查看提示
先检查每个定义域元素作为第一坐标出现几次,再分别查碰撞和陪域漏点。
查看解答
复核过的解答:0、1、2 各恰好出现一次,因此 R 是函数。输出为 a、b、b,像集是 {a,b},等于陪域,所以满射;1 与 2 都映到 b,所以不是单射,也不是双射。
练习 3
- 所属知识
- 复合与逆映射
- 难度
- 2/5
令 f:{1,2}→{u,v} 满足
f(1)=u,f(2)=v,令
g:{u,v}→{5,7} 满足
g(u)=5,g(v)=7。求 g∘f 及其逆映射,并用复合式核对结果。
查看提示
先从右到左计算复合;求逆时按相反顺序撤销每一步。
查看解答
复核过的解答:先算 f 得到 1↦u、2↦v,再算 g 得到 (g∘f)(1)=5、(g∘f)(2)=7。两个映射都逐点一一对应,故复合为双射。逆映射把 5↦1、7↦2,并且等于先做 g⁻¹(5↦u、7↦v)再做 f⁻¹(u↦1、v↦2)。
练习 4
- 所属知识
- 像、原像与证明
- 难度
- 3/5
证明对任意函数 f:X→Y 和 C,D⊆Y,都有
f−1(C∪D)=f−1(C)∪f−1(D).再给出反例说明一般不能把原像符号去掉后仍断言
f(S∩T)=f(S)∩f(T)。
查看提示
对原像等式追踪任意输入 x;对像的交集结论尝试让两个不同输入得到同一输出。
查看解答
复核过的解答:x 属于 f⁻¹(C∪D) 当且仅当 f(x) 属于 C 或 D,当且仅当 x 属于 f⁻¹(C) 或 f⁻¹(D),故原像等式成立。像的交集等式不总成立:取 f(x)=x²、S={-1}、T={1},则 f(S∩T)=∅,而 f(S)∩f(T)={1}。
知识关系
- 函数与图像
把映射限制到实数变量,进一步研究公式、图像、复合和反函数。
- 命题逻辑与量词
为“任意元素”和“存在唯一输出”提供形式化表达。
- 线性变换
在映射定义上增加保持加法和数乘的结构条件。
- 概率公理
把事件视为样本空间的子集,并对并、交和补集赋予概率规则。
- 凸集 在向量空间的子集上增加线段闭包条件。
已核对的外部资源
课程 · 2015MIT 6.042J Mathematics for Computer Science
Albert R. Meyer, Adam Chlipala
用于核对集合运算、函数定义、像与原像、单射满射以及有限集合上的证明方法。
打开官方来源
MIT 6.042J 第 4 章系统处理集合、关系、函数、复合、单射、满射和有限基数。本文用它核对函数三要素、箭头性质与复合结论;官方
课程讲义页
还把“Sets and Functions”列为独立课次,并提供课堂问题与解答。
课程 · 年份待核Stanford CS103 Guide to Elements and Subsets
用于核对成员符号、子集符号及二者不能互换的基础边界。
打开官方来源
斯坦福大学 CS103 的集合讲义集中解释成员与子集的对象类型、空集和嵌套集合。本文用它核对符号区分与边界例子,并保留前文的官方 PDF 直达引用,使相邻主张可以直接追溯。
以上链接均在 2026-07-11 通过学校官方域名核对。引用支持的是相邻定义和课程范围;本文中的有限枚举、De Morgan 律、复合性质与逆映射充要条件另已按定义逐步复算。
后续学习
接着阅读 命题逻辑与量词,把集合包含与函数性质写成精确量词;再进入 函数与图像,研究实函数的定义域、图像变换和反函数。之后可沿 线性变换 学习保结构映射,或沿 概率公理 学习事件集合上的运算与测度。
建议先把本章有限实验换成自己的四至六个元素数据,完整记录定义域、陪域、像集和各单点原像,再尝试用量词证明观察到的规律。进入无限集合后,枚举不再可行;双向包含、构造原像和证明唯一性会成为主要工具。