第一章集合与映射1.1集合论我们回忆一下集合论最基本的一些概念和记号。我们假设A,B,X为集合，，y为集合的元。TEA为集合A的元；CEA不为集合A的元；ACBA为B的子集，即rEA→rEB;A=BACB且BCA,即EA台rEB;ADBBCA;集合(r：EA且rEB);AnBAUB集合(rEA或rEB);AxB集合(r,y)：EA且yEB)。称作A和B的Descartes 积;A\B集合(：EA且B);CxA, CA, Ac若ACX，指A相对于X的补集，即X\A。A△B集合(A|B)U(BA)。称作A和B的对称差；P(X)集合X所有子集构成的集合族。称作X的幂集。1.1.1 关系定义1.1.从X到Y的一个（有序）关系是指X×Y的一个子集R。若(r,y)eR，我们记作rRy。若X=Y，则称R为X上的关系
第一章 集合与映射 1.1 集合论 我们回忆一下集合论最基本的一些概念和记号。我们假设 A, B, X 为集 合，x, y 为集合的元。 x ∈ A x 为集合 A 的元； x ̸∈ A x 不为集合 A 的元； A ⊂ B A 为 B 的子集，即 x ∈ A ⇒ x ∈ B； A = B A ⊂ B 且 B ⊂ A，即 x ∈ A ⇔ x ∈ B； A ⊃ B B ⊂ A； A ∩ B 集合 {x : x ∈ A 且 x ∈ B}； A ∪ B 集合 {x : x ∈ A 或 x ∈ B}； A × B 集合 {(x, y) : x ∈ A 且 y ∈ B}。称作 A 和 B 的 Descartes 积； A \ B 集合 {x : x ∈ A 且 x ̸∈ B}； ∁XA, ∁A, Ac 若 A ⊂ X，指 A 相对于 X 的补集，即 X \ A。 A △ B 集合 (A \ B) ∪ (B \ A)。称作 A 和 B 的对称差； P(X) 集合 X 所有子集构成的集合族。称作 X 的幂集。 1.1.1 关系 定义 1.1. 从 X 到 Y 的一个（有序）关系是指 X × Y 的一个子集 R。若 (x, y) ∈ R，我们记作 xRy。若 X = Y ，则称 R 为 X 上的关系
10第一章集合与映射例1.2.设X=[1,2,3,4)。若R为X上通常的关系“<”，则R为序对R = [(1,2), (1,3), (1,4),(2,3), (2, 4), (3,4))若rRy意味着ay（即r可被y整除），则R = {(1,1), (1, 2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4))定义1.3.设R为从X到Y的关系，ACX，BCY。则称集合R(A)=(yEY:rRy对某rEA)为A在R下的像，称集合R-1(B)=(rEX :rRy对某yE B)为B在R下的原像。注1.4.设R为从X到Y的关系。我们引入R-1为从Y到X的关系：yR-la台rRy.R-1称作关系R的反关系。定义1.5.设R为从X到Y的关系。我们称集合R-(Y)=(rEX:rRy对某yEY)为R的定义域，称集合R(X)=(yEY:rRy对某rEX)为R的值域。例1.6.设X,Y为非空集合，F：X→Y为一映射，F可以看成一个从X到Y的关系满足以下条件：(i)F的定义域为X(ii)若rFy且rFz，则y=ze我们的定义表明。任给reX，对至少一个yeY，rFy,。对至多一个yEY，aFy，即F((r))：=yEY:(r,y)EF)为单点集。此时这个唯一的使得F((r))={y)的yEY称作在F下的像，记作F(a)。关系F可以表示成F= (r,y)eXxY: y=F(r))关于映射的其他基本概念我们就不在这里赞述
10 第一章 集合与映射 例 1.2. 设 X = {1, 2, 3, 4}。若 R 为 X 上通常的关系“<”，则 R 为序对 R = {(1, 2),(1, 3),(1, 4),(2, 3),(2, 4),(3, 4)}. 若 xRy 意味着 x|y（即 x 可被 y 整除），则 R = {(1, 1),(1, 2),(1, 3),(1, 4),(2, 2),(2, 4),(3, 3),(4, 4)}. 定义 1.3. 设 R 为从 X 到 Y 的关系，A ⊂ X，B ⊂ Y 。则称集合 R(A) = {y ∈ Y : xRy 对某 x ∈ A} 为 A 在 R 下的像，称集合 R −1 (B) = {x ∈ X : xRy 对某 y ∈ B} 为 B 在 R 下的原像。 注 1.4. 设 R 为从 X 到 Y 的关系。我们引入 R−1 为从 Y 到 X 的关系： yR−1x ⇔ xRy. R−1 称作关系 R 的反关系。 定义 1.5. 设 R 为从 X 到 Y 的关系。我们称集合 R −1 (Y ) = {x ∈ X : xRy 对某 y ∈ Y } 为 R 的定义域，称集合 R(X) = {y ∈ Y : xRy 对某 x ∈ X} 为 R 的值域。 例 1.6. 设 X, Y 为非空集合，F : X → Y 为一映射，F 可以看成一个从 X 到 Y 的关系满足以下条件：(i) F 的定义域为 X; (ii) 若 xF y 且 xF z，则 y = z。 我们的定义表明 ◦ 任给 x ∈ X，对至少一个 y ∈ Y ，xF y; ◦ 对至多一个 y ∈ Y ，xF y，即 F({x}) := {y ∈ Y : (x, y) ∈ F} 为单点集。 此时这个唯一的使得 F({x}) = {y} 的 y ∈ Y 称作 x 在 F 下的像，记作 F(x)。关系 F 可以表示成 F = {(x, y) ∈ X × Y : y = F(x)}. 关于映射的其他基本概念我们就不在这里赘述
111.1集合论例1.7.设X,Y为非空集合，我们称F：XY为一集值映射若对任意aEX存在Y的非空子集F(r)。最常见的集值映射包括映射f的“逆”f-1,局部Lipschitz函数的广义导数等。这里我们将集值映射F理解成从X到Y的关系只需使得其定义域非空即可，而无需要求例1.6中的条件(i)。此时F(())不必是单点集。例1.8.集合X上的偏序是一类重要的关系。设X为非空集合，X上的关系“”称作偏序若(I)任给EX，≤（自反性)；(2)若≤y，y≤z，则≤z（传递性）；(3)若≤y且y≤，则=y（反对称性）。例1.9.设X为一非空集合，X上的关系R称作等价关系若。R对任意EX（自反性）。若rRy，则yRa（对称性)；。若rRy且yRz，则zRz（传递性）。通常我们用“～”表示一个集合上的等价关系。任何一等价关系决定了一个等价类[国] := (yeX :r~y]由选择公理，我们能保证我们在每个等价类【]可以选取一个代表元。我们称集合X/ ~:= [[] : rE X) c P(X)为集合X关于等价关系～的商集。元：→[国]称作商映射。思考题：非空集合X的一个分划是指X的一个子集族A满足（1）任意AEA均非空(2)任给A,BEA,若A+B，则AnB=O;(3)UAeAA=X。我们是否可以说X上的等价关系与上的分划是一一对应的？1.1.2对等·集合的基数在集合论中，集合元素的个数是一个基本问题。定义1.10.集合A与B称作对等，记作A～B，若存在f：A→B为一双射。对任意集合族A，上述对等的概念给出了一个等价关系。后面我们引入的所谓集合A的基数（或者势）card（A）可以看成A关于上述等价关系~的一个等价分类。稍后我们具体讨论这个概念。例1.11.我们先来考虑几个简单的例子
1.1 集合论 11 例 1.7. 设 X, Y 为非空集合，我们称 F : X ⇝ Y 为一集值映射若对任意 x ∈ X 存在 Y 的非空子集 F(x)。最常见的集值映射包括映射 f 的“逆”f −1， 局部 Lipschitz 函数的广义导数等。这里我们将集值映射 F 理解成从 X 到 Y 的关系只需使得其定义域非空即可，而无需要求例1.6中的条件 (ii)。此时 F({x}) 不必是单点集。 例 1.8. 集合 X 上的偏序是一类重要的关系。设 X 为非空集合，X 上的关 系“⩽”称作偏序若 (1) 任给 x ∈ X，x ⩽ x（自反性）；(2) 若 x ⩽ y，y ⩽ z， 则 x ⩽ z（传递性）；(3) 若 x ⩽ y 且 y ⩽ x，则 x = y（反对称性）。 例 1.9. 设 X 为一非空集合，X 上的关系 R 称作等价关系若 ◦ xRx 对任意 x ∈ X（自反性）; ◦ 若 xRy，则 yRx（对称性）； ◦ 若 xRy 且 yRz，则 zRz（传递性）。 通常我们用“∼”表示一个集合上的等价关系。任何一等价关系决定了一个 等价类 [x] := {y ∈ X : x ∼ y}. 由选择公理，我们能保证我们在每个等价类 [x] 可以选取一个代表元。我们 称集合 X/ ∼:= {[x] : x ∈ X} ⊂ P(X) 为集合 X 关于等价关系 ∼ 的商集。π : x 7→ [x] 称作商映射。 思考题：非空集合 X 的一个分划是指 X 的一个子集族 A 满足 (1) 任意 A ∈ A 均非空; (2) 任给 A, B ∈ A，若 A ̸= B，则 A∩B = ∅；(3) ∪A∈AA = X。 我们是否可以说 X 上的等价关系与 X 上的分划是一一对应的？ 1.1.2 对等·集合的基数 在集合论中，集合元素的个数是一个基本问题。 定义 1.10. 集合 A 与 B 称作对等，记作 A ∼ B，若存在 f : A → B 为一双 射。 对任意集合族 A，上述对等的概念给出了一个等价关系。后面我们引入 的所谓集合 A 的基数（或者势）card (A) 可以看成 A 关于上述等价关系 ∼ 的一个等价分类。稍后我们具体讨论这个概念。 例 1.11. 我们先来考虑几个简单的例子
12第一章集合与映射(1) N~2N, N~2N+1。(2) N× N~ N。定义函数f：N×N-→N：f(i, ) = 2i-1(2j -1),(i,j)ENxN由算术基本定理（即整数的唯一分解定理），任给nEN，n有如下表示：n =2P-q,pENU(O),qE2N+1.这表明f为满射。f为单射易证。(3) (-1,1) ~ R。定义函数f：(-1,1)→R：f(a) = i1-r2 re(-1,1),则f为所需的双射。设X和Y为非空集合。我们描述关系card(X）≤card(Y）若存在X到Y的单射。注意到这里我们并没有给出card（X）和card(Y）的具体的含义。我们后面分别称之为集合X和Y的基数。容易看出，关系“≤”满足自反性和传递性。事实上，我们将证明这一关系还满足反对称性，从而给出所有集合的基数的全体上的偏序关系。定理1.12(Schroder-Bernstein').设X和Y为非空集合。若card(X）≤card(Y)且card（Y）≤card（X)，则存在X到Y的双射。1.1.3集合族（列）设A为一集合族，我们通常需要一个公理：存在一个集合X使得所有的AEA均包含于X。该公理允许我们定义集合的任意并集。事实上，假设A=[A)ier为一集合族（即一个映射I→P(X))，我们定义A的并集为JA=rEX:rEA对某iEIiel换句话说，集合族A的并集为满足上面公理的集合X中最小的集合。类似我们可以定义A的交集为A,-{rEXrEA对任意iEI)EI！专著【16]给出了下面定理的一些历史注记。作者指出（第33页），定理1.12是Cantor错失的（他渴望证明它），后来由Schroder和Bernstein各自独立证明
12 第一章 集合与映射 (1) N ∼ 2N，N ∼ 2N + 1。 (2) N × N ∼ N。 定义函数 f : N × N → N： f(i, j) = 2i−1 (2j − 1), (i, j) ∈ N × N. 由算术基本定理（即整数的唯一分解定理），任给 n ∈ N，n 有如下表示： n = 2p · q, p ∈ N ∪ {0}, q ∈ 2N + 1. 这表明 f 为满射。f 为单射易证。 (3) (−1, 1) ∼ R。 定义函数 f : (−1, 1) → R： f(x) = x 1 − x 2 , x ∈ (−1, 1), 则 f 为所需的双射。 设 X 和 Y 为非空集合。我们描述关系 card (X) ⩽ card (Y ) 若存在 X 到 Y 的单射。注意到这里我们并没有给出 card (X) 和 card (Y ) 的具体的含义。 我们后面分别称之为集合 X 和 Y 的基数。容易看出，关系“⩽”满足自反 性和传递性。事实上，我们将证明这一关系还满足反对称性，从而给出所有 集合的基数的全体上的偏序关系。 定理1.12 (Schröder-Bernstein1 ). 设X 和Y 为非空集合。若card (X) ⩽ card (Y ) 且 card (Y ) ⩽ card (X)，则存在 X 到 Y 的双射。 1.1.3 集合族（列） 设 A 为一集合族，我们通常需要一个公理：存在一个集合 X 使得所有 的 A ∈ A 均包含于 X。该公理允许我们定义集合的任意并集。事实上，假 设 A = {Ai}i∈I 为一集合族（即一个映射 I → P(X)），我们定义 A 的并集 为 ∪ i∈I Ai := {x ∈ X : x ∈ Ai 对某 i ∈ I}. 换句话说，集合族 A 的并集为满足上面公理的集合 X 中最小的集合。类似 我们可以定义 A 的交集为 ∩ i∈I Ai := {x ∈ X : x ∈ Ai 对任意 i ∈ I}. 1专著 [16] 给出了下面定理的一些历史注记。作者指出（第 33 页），定理1.12是 Cantor 错失的（他渴望 证明它），后来由 Schröder 和 Bernstein 各自独立证明
1.1集合论13命题1.13.(DeMorgan法则）设【Aa)ael为集合族，则UA.)=NA,OA)=UASiEIielieliel接下来，我们来讨论集合族的乘积。设A为一集合族，X,ier包含于A，即存在映射I→A使得任给iEI其像为X。我们可以看出，若设U=UierXi，则Xier的乘积由元（r）组成，这里a,EU且以iEI为标签。换句话说，它恰恰是所有这样的映射f：I→U组成：任给iEI，f(i）EX。我们记【Xihiel得乘积为IIx.iel很明显IlierX，中两个元（r）和（yi）相同当且仅当任给iEI，;=yi。我们称，为（）的第i个坐标。注1.14.若对某jEI，X,=の，很明显此时IlierX=0。由选择公理，若每一X,均非空，则IlierX≠の。此时，映射元：（r)→，iI，称作从乘积IlielX，到X，的投影
1.1 集合论 13 命题 1.13. （De Morgan 法则） 设 {Aα}α∈I 为集合族，则 (∪ i∈I Ai )c = ∩ i∈I A c i , (∩ i∈I Ai )c = ∪ i∈I A c i . 接下来，我们来讨论集合族的乘积。设 A 为一集合族，{Xi}i∈I 包含 于 A，即存在映射 I → A 使得任给 i ∈ I 其像为 Xi。我们可以看出，若设 U = ∪i∈IXi，则 {Xi}i∈I 的乘积由元 (xi) 组成，这里 xi ∈ U 且以 i ∈ I 为 标签。换句话说，它恰恰是所有这样的映射 f : I → U 组成：任给 i ∈ I， f(i) ∈ Xi。我们记 {Xi}i∈I 得乘积为 ∏ i∈I Xi . 很明显 ∏ i∈I Xi 中两个元 (xi) 和 (yi) 相同当且仅当任给 i ∈ I，xi = yi。我 们称 xi 为 (xi) 的第 i 个坐标。 注 1.14. 若对某 j ∈ I，Xj = ∅ ，很明显此时 ∏ i∈I Xi = ∅。由选择公理， 若每一 Xi 均非空，则 ∏ i∈I Xi ̸= ∅。此时，映射 πi : (xi) 7→ xi，i ∈ I，称 作从乘积 ∏ i∈I Xi 到 Xi 的投影