有序组

(Kuratowski) 对任意 `x, y`, 定义 `(x, y) = (:x, y:) := {{x},{x,y}}`, 称为由 `x, y` 组成的有序对 (ordered pair, 或有序二元组). 这个集合的存在惟一性分别由配对公理和外延公理保证.

`(x, y) = (u, v) iff x = u and y = v`.

`(x,y) = (u,v)` `iff {{x},{x,y}} = {{u},{u,v}}` `iff ({x} = {u} and {x,y} = {u,v})` `or ({x} = {u,v} and {x,y} = {u})` `iff (x = u and y = v) or (x = y = u = v)` `iff x = u and y = v`.

1. `x, y in S rArr (x, y) in 2^(2^S)`;
2. `(x,y) in S rArr x, y in uuu(uuu S)`.

1. 由 `x,y in S` 得 `{x}, {x,y} in 2^S`, 从而 `(x,y) = {{x},{x,y}} in 2^(2^S)`.
2. 由 `{{x},{x,y}} in S` 得 `{x}, {x,y} in uuu S`, 从而 `x, y in uuu(uuu S)`.

注意, 不能用类似 Kuratowski 定义有序对的方式来定义有序三元组: 假设 `(x,y,z) := {{x},{x,y},{x,y,z}}`, 则 `(a,a,b) = {{a},{a},{a,b}}` `= {{a},{a,b}}` `= {{a},{a,b},{a,b}} = (a,b,a)`. 这不是我们想要的性质.

对任意 `x_1, x_2, cdots, x_n` 递归地定义 `(x_1, x_2, cdots, x_n) := ((x_1, cdots, x_(n-1)), x_n)`, 称为有序 `bm n` 元组.

Descartes 积

对任意集合 `A, B`, 存在集合 `X`, 使得 `x in X` 当且仅当存在 `a in A` 和 `b in B`, 使得 `x = (a, b)`: `AA A AA B EE X AA x(x in X harr EE a EE b(a in A ^^ b in B ^^ x = (a, b)))`. 由外延公理可证集合 `X` 惟一, 称为 `A, B` 的 Descartes 积 (Descartes product), 记为 `X = A xx B := {(a,b): a in A, b in B} sube 2^(2^(A uu B))`.

因为 `a, b in A uu B`, 所以 `(a, b) in 2^(2^(A uu B))`. 由子集公理, 集合 `X = {x in 2^(2^(A uu B)): EE a in A, EE b in B, x = (a, b)}` 存在.

二元关系

1. 设集合 `X, Y != O/`, 集合 `R sube X xx Y` 称为 `X` 到 `Y` 上的一个二元关系, 记作 `R: X to Y`. 显见 `R in 2^(X xx Y)`. 如果 `(x, y) in R`, 则称 `x, y` 是 `bm R`-相关的, 记为 `x R y`. 即 `x R y iff (x, y) in R`.
2. 分别称 `"dom"R = {x in X: EE y in Y, (x,y) in R} sube X`,
   `"ran"R = {y in Y: EE x in X, (x,y) in R} sube Y`,
   `"fld"R = "dom"R uu "ran"R` 为 `R` 的定义域 (domain), 值域 (range) 和域 (field).
   由定义知, `"fld" R = uuu(uuu R)`, `R sube "dom"R xx "ran"R sube "fld"R xx "fld"R`.
3. 定义二元关系 `R: X to Y` 的逆为: `R^-1 := {(y,x): (x,y) in R}`. `AA A sube "dom"R`, 定义 `A` 的截口 (section) 为: `R(A) := {y in Y: EE x in A, (x, y) in R}`, 特别 `R(X) = "ran"R`. 又定义单点集的截口为: `R(x) := {y in Y: (x, y) in R}`, `quad AA x in "dom"R`. 二元关系 `R: X to Z` 与 `S: Z to Y` 的复合为: `R @ S := {(x,y): EE z in Z, (x,z) in S and (z,y) in R}`. 换言之, `x, y` 有关系 `R @ S` 当且仅当存在中间元 `z`, 使得 `x S z` 且 `z R y`. 关系的复合满足结合律.

映射

映射的概念

1. 设集合 `X, Y != O/`, 考虑 `X` 到 `Y` 上的二元关系 `f`. 如果对任意 `x in X`, 都存在惟一的 `y in Y`, 使 `(x, y) in f`, 换言之, `X = "dom"f`, `quad (x,y) in f and (x,z) in f rArr y = z`, 换言之 `AA x in X`, `|f(x)| = 1`, 则称 `f` 为 `X` 到 `Y` 的一个 (良定义的) 映射 (mapping), 记为 `f: X to Y`.
   
2. 因为满足 `(x,y) in f` 的 `y` 是惟一的, 我们可以记 `y = f(x) iff (x,y) in f`. 此时称 `f` 把 `x` 映到 `y`, `y` 称为 `x` 在 `f` 下的像或像点, `x` 称为 `y` 在 `f` 下的一个原像.

在映射的定义中, 存在惟一性的条件也可以写成:
1. `(AA x in X)` `(EE y in Y)` `y = f(x)`;
2. `x_1 = x_2 rArr f(x_1) = f(x_2)`.

设 `f` 和 `g` 都是 `X` 到 `Y` 的映射, 由外延公理知 `f = g iff AA x in X, f(x) = g(x)`.

映射的像与核

设 `f: X to Y`, `A sube X`, `B sube Y`.
1. 称 `f(A) := {f(x): x in A} = {y in Y: (EE x in A) y = f(x)} sube Y` 为 `A` 在 `f` 下的像或像集. 约定 `f(O/) = O/`. 特别 `f(X) = "ran"f` 也记为 `"Im" f`, 称为 `f` 的像 (image).
2. 称 `f^-1(B) = {x in X: f(x) in B} sube X` 为 `B` 在 `f` 下的原像 (preimage)或原像集或完全原像. 单点集的原像可以简记 `f^-1({y}) = f^-1(y)`. 特别 `f^-1(Y) = "dom" f = X`.

设 `f: X to Y` 是映射, `A, A_1, A_2 sube X`, `B, B_1, B_2 sube Y`, `cc A sube 2^X`, `cc B sube 2^Y`. 又假定求交集时 `cc A, cc B != O/`, 则 `A_1 sube A_2 rArr f(A_1) sube f(A_2)`, `quad B_1 sube B_2 rArr f^-1(B_1) sube f^-1(B_2)`,
`f(uuu cc A) = uuu_(A in cc A) f(A)`, `quad f^-1(uuu cc B) = uuu_(B in cc B) f^-1(B)`,
`f(nnn cc A) sube nnn_(A in cc A) f(A)`, `quad f^-1(nnn cc B) = nnn_(B in cc B) f^-1(B)`,
`f(A_1\\A_2) supe f(A_1)\\f(A_2)`, `quad f^-1(B_1\\B_2) = f^-1(B_1)\\f^-1(B_2)`,
`f(X\\A) supe f(X)\\f(A)`, `quad f^-1(Y\\B) = X\\f^-1(B)`.

设 `f: X to Y`, 定义 `f` 的核 `"Ker" f = {(x_1, x_2) in X xx X: f(x_1) = f(x_2)}`. 换言之, `(x_1, x_2) in "Ker" f iff f(x_1) = f(x_2)`. 可以验证 `"Ker" f` 构成 `X` 上的一个等价关系 (见下文).

映射的复合与限制

设 `f, g` 为映射, 则按二元关系的复合, `f @ g` 也为一映射, 称为 `f` 与 `g` 的复合映射: `"dom"f @ g = "dom"g nn g^-1("dom"f)` `= {x in "dom"g: g(x) in "dom"f}`. 映射的复合也满足结合律.

定义集合 `X` 到自身的恒等映射或恒同映射为 `"id"_X: X to X`
`x mapsto x`. 恒等映射保持每一点不变.
容易验证, `(AA f: X to Y)` `f = f @ "id"_X = "id"_Y @ f`; `"Im"("id"_X) = X`, `"Ker"("id"_X) = Delta_X` (`X` 上最小的等价关系, 每个元素只和自身等价).

设 `f, g` 为映射. 如果 `f uu g` 还是一个映射, 亦即 `AA x in "dom"f nn "dom"g`, 都有 `f(x) = g(x)`, 则称 `f`, `g` 是相容的.
特别, 如果 `g sube f`, 即 `"dom"g sube "dom" f`, 且 `AA x in "dom"g, g(x) = f(x)`, 则称 `g` 为 `f` 的限制, `f` 为 `g` 的扩张. 记 `"dom"f = X`, `"dom"g = A sube X`, 则映射 `f: X to Y` 在子集 `A` 上的限制记为 `f|{::}_A: A to Y`
`x mapsto f(x)`. 容易验证 `f|{::}_A = f @ "id"_X|_A`, 其中 `"id"_X|_A` 称为包含映射.

满射, 单射, 双射

设 `f: X to Y`.
1. 如果对任意 `y in Y`, 都存在 `x in X`, 使得 `y = f(x)`, 则称 `f` 是满射 (surjection, onto);
2. 如果由 `f(x_1) = f(x_2)` 蕴含 `x_1 = x_2`, 则称 `f` 是单射 (injection, monophism, one-one);
3. 如果 `f` 既是单射又是满射, 则称 `f` 是双射 (bijection);

设 `f: X to Y`.
1. 以下各款等价:
   1. `f` 为一满射;
   2. `"Im" f = Y`;
   3. `(AA y in Y)` `|f^-1(y)| ge 1`;
   4. 存在 `g: Y to X`, 使 `f @ g = "id"_Y`.
2. 以下各款等价:
   1. `f` 为一单射;
   2. `"Ker" f = iota_X` (`iota_X` 是 `X xx X` 上最小的等价关系, 每个元素只等价于自身);
   3. `(AA y in Y)` `|f^-1(y)| le 1`;
   4. 存在 `g: Y to X`, 使 `g @ f = "id"_X`.
      
3. 以下各款等价:
   1. `f` 为一双射;
   2. `(AA y in Y)`, `|f^-1(y)| = 1`;
   3. 存在 `g: Y to X`, `g @ f = "id"_X`, `f @ g = "id"_Y`.

`f` 为双射时, 对任意 `y in Y`, 存在唯一 `x in X` 使 `y = f(x)` (其存在性由满射保证, 唯一性由单射保证), 把这一对应关系记为 `f^-1`, 则 `f^-1` 是一个映射, 称为 `f` 的逆.

关于像集, 原像集和单射, 满射的关系, 我们有 (设 `A, B` 分别为 `X, Y` 的真子集): `f(f^-1(B)) sube B`, 等号成立当且仅当 `f` 为满射;
`f^-1(f(A)) supe A`, 等号成立当且仅当 `f` 为单射.

特征函数

设 `f: X to Y`. 当 `Y = X` 时, 又称 `f` 为 `X` 上的变换. 当 `Y = RR` 时, 又称 `f` 为函数.

设 `A sube X`, 定义特征函数 `chi_A: X to {0, 1}` 如下: `chi_A(x) = { 1, if x in A; 0, if x in X\\A; :}` 一定意义上特征函数可以代表集合 `A` 本身. 如 `A = B iff chi_A = chi_B`, `quad A sube B iff chi_A le chi_B`. 关于特征函数与集合运算之间的联系, 我们有 `chi_(A^c)(x) = 1 - chi_A(x)`
`chi_(A nn B)(x) = chi_A(x) * chi_B(x)`
`chi_(A \\ B)(x) = chi_A(x)(1 - chi_B(x))`
`chi_(A uu B)(x) = chi_A(x) + chi_B(x) - chi_A(x) * chi_B(x)`
`chi_(A /_\ B)(x) = |chi_A(x) - chi_B(x)|`

等价关系

设 `R: X to X` 是一个二元关系, 满足:
1. 自反性. `AA x in X`, `x R x`;
2. 对称性. `x R y rArr y R x`;
3. 传递性. `x R y and y R z rArr x R z`.
则称 `R` 为 `X` 上的一个等价关系. `AA x in X`, 称 `R(x) = {y: x R y}` 为 `x` 的等价类.

若关系 `R` 是对称的和传递的, 则它是一等价关系.

`AA x in "dom"R`, `EE y in "ran"R`, `x R y`. 由对称性, `y R x`. 再由传递性有 `x R x`, 即 `R` 是自反的.

设 `R` 为一等价关系, 则由对称性得到 `"dom"R = "ran"R`.

设 `R` 是 `X` 上一个等价关系, 则 `(x,y) in R rArr R(x) = R(y)`, `quad (x,y) !in R rArr R(x) nn R(y) = O/`. 于是任意两个等价类要么重合, 要么不相交. 这样 `X` 就被划分为一些不相交等价类的并, 换言之, 集合 `X//R := {R(x): x in X}` 构成 `X` 的一个划分 (partition), 称 `X//R` 为 `X` 模 `R` 的商集.

`AA z in R(x)`, 有 `(x,z) in R`, 如果 `(x,y) in R`, 由对称性和传递性得到 `(y,z) in R`, 即 `z in R(y)`. 于是 `R(x) sube R(y)`. 同理 `R(y) sube R(x)`.
假设 `EE z in R(x) nn R(y)`, 有 `(x,z), (y,z) in R`. 由对称性和传递性得到 `(x,y) in R`, 矛盾.

若 `cc D` 是 `X` 的一个划分, 可以确定 `X` 上的等价关系 `R`: `x_1 R x_2 iff EE D in cc D, x_1, x_2 in D`. 此时 `cc D` 中的每个集合都是一个等价类, 于是 `R(x)` 确定了 `X` 到 `D` 上的一个满射.
反之若 `f` 是满射, 则商集 `X//"Ker"f = {f^-1(y): y in Y}` 与 `Y` 之间存在双射.

偏序与全序

设二元关系 `le: X to X` 满足:
1. 自反性. `AA x in X`, `x le x`;
2. 反对称性. `x le y and y le x` `rArr x = y`;
3. 传递性. `x le y and y le z` `rArr x le z`.
则称 `le` 为一偏序 (partial order), `(X, le)` 构成 `X` 上的偏序集. 我们记 `x ge y iff y le x`, `quad x lt y iff x le y and x != y`, `quad x gt y iff x ge y and x != y`.

偏序集 `(X, le)` 称为 `X` 上的全序 (total order) 或线序, 如果任意 `x, y in X` 都可以比较大小, 即 `AA x, y in X`, `x le y or y le x`.

设 `(X, le)` 为一偏序集, 非空集 `E sube X`. 称 `m in X` 为 `E` 的一个上界 (upper bound), 如果 `AA x in E, x le m`. 称 `m` 为 `E` 的一个最大元, 如果 `m in E`, 且 `m` 为 `E` 的一个上界. 称 `m` 为 `E` 的一个极大元, 如果 `m in E`, 且 `AA x in E`, `x gt m` 不成立. 换言之, `AA x in E`, `x ge m rArr x = m`. 类似可以定义下界, 最小元和极小元.

最大元若存在, 必惟一, 且为一极大元.

设 `(X, le)` 为一全序集, `a, b in X`, 定义以 `a, b` 为端点的闭区间和开区间分别为 `[a,b] := {x in X: a le x le b}`, `quad (a, b) := {x in X: a lt x lt b}`. 若 `(a, b) = O/`, 就称 `(a, b)` 是 `X` 的一个间隙 (gap). 称 `E sube X` 为一区间, 如果 `AA x, y in E`, `[x, y] sube E`. 如果对任意不空的开区间 `(a, b)`, 有 `(a, b) nn E != O/`, 则称 `E` 是(序) 稠密的.

设 `(X, le)` 为一全序集, 非空集 `E sube X`. 称 `s in X` 为 `E` 的一个上确界, 如果 `s` 是 `E` 的最小上界. 换言之, `s` 是 `E` 的上界, 且对 `E` 的任意上界 `m`, 有 `s le m`. 记 `s = "sup" E`. 类似可以定义 `E` 的下确界 `"inf"E`. 称 `(X, le)` 是 (序) 完备的, 如果它满足确界原理: (1) 任意有上界的子集必有上确界; (2) 任意有下界的子集必有下确界.

上 (下) 确界若存在, 必惟一.

确界原理的两个条件相互等价.

我们证明 (1) `rArr` (2). 设 `(X, le)` 任意有上界的子集都有上确界, 设非空集 `E sube X` 有下界. 下证 `E` 有下确界.
1. 令 `A` 是 `E` 的全体下界, 则 `A` 不空, 且 `AA e in E, AA a in A`, 由 `a` 是 `E` 的下界有 `a le e`, 从而 `E` 的任一元都是 `A` 的上界.
2. 令 `a = "sup"A`, 则由 `a` 是 `A` 的最小上界知, `AA e in E`, `a le e`, 从而 `a` 是 `E` 的下界, 即 `a in A`. 我们已经证明 `a` 是 `A` 的最大元, 即为 `E` 的最大下界, 所以 `a = "inf"E`, 从而 `E` 有下确界.

设 `(X, le)` 为一偏序集, 称 `C sube X` 为一链, 如果 `(C, le) := (C xx C) nn le` 是一全序集.

设 `(X, le)`, `(Y, ≼)` 是全序集. 称 `f: X to Y` 为保序映射, 如果 `x_1 le x_2 rArr f(x_1) ≼ f(x_2)`. 由定义, 保序映射是单射. 若 `f` 还是满射, 则称它是 `X` 到 `Y` 上的相似映射, 此时称 `X, Y` 相似, 或称 `(X, le)`, `(Y, ≼)` 是序同构的, 记作 `(X, le) ~ (Y, ≼)`.