2.1集合论19定义2.9.对任给ACX和BCY，定义A在f下的像与B关于f的原像分别为f(A)=(yEY:y=f(r),rEA), f-I(B)=(rEX:f(r)EB)f称作满射若f(X)=Y。f称作单射若对i,2EX,i2,f(ri)f(r2)。称作双射（或一一映射）若于既为单射亦为满射。若f为双射，则可定义f的逆映射f-1:Y→X，即任给eY，f-1(y)=a，其中f(a)=y。若映射f:X→Y,g:Y→Z,则h(r)=gf(r)=g(f(a)),EX定义了f与g的复合映射h：X→Z。在继续之前，我们先来看前面提到的集合族的直积的问题。设[Xa}aeI为集合族，则IIXα=(r:: I →UaeiXa,使得对任给 α I,r(a) Aa),aeI由此，所有X到Y的映射的全体可以看成（无穷）乘积空间Yx - II y.TEX定义2.10.设ACX，定义A上的特征函数1,rEA,1A =LO,rA通过特征函数，我们可以将集合的问题与集合上的函数的问题联系起来。设F(X)为所有X到R的函数全体构成的向量空间，对f,gEF(X)定义格运算fVg=max(f.g),fAg=min(fg)则F(X)为一（向量）格。不难验证，对A,BCX，1AUB=1AVB=1AV1B,1ANB=1AAB=1AAIB建立了集合上的函数与集合之间的联系
2.1 集合论 19 定义 2.9. 对任给 A ⊂ X 和 B ⊂ Y ，定义 A 在 f 下的像与 B 关于 f 的原像 分别为 f(A) = {y ∈ Y : y = f(x), x ∈ A}, f −1 (B) = {x ∈ X : f(x) ∈ B}. f 称作满射若 f(X) = Y 。f 称作单射若对 x1, x2 ∈ X，x1 ̸= x2，f(x1) ̸= f(x2)。f 称作双射（或一一映射）若 f 既为单射亦为满射。若 f 为双射，则可 定义 f 的逆映射f −1 : Y → X，即任给 y ∈ Y ，f −1 (y) = x，其中 f(x) = y。 若映射 f : X → Y ，g : Y → Z，则 h(x) = g ◦ f(x) = g(f(x)), x ∈ X 定义了 f 与 g 的复合映射 h : X → Z。 在继续之前，我们先来看前面提到的集合族的直积的问题。设 {Xα}α∈I 为集合族，则 ∏ α∈I Xα = {x : x : I → ∪α∈IXα, 使得对任给 α ∈ I, x(α) ∈ Aα}. 由此，所有 X 到 Y 的映射的全体可以看成（无穷）乘积空间 Y X = ∏ x∈X Y. 定义 2.10. 设 A ⊂ X，定义 A 上的特征函数 1A = { 1, x ∈ A; 0, x ̸∈ A. 通过特征函数，我们可以将集合的问题与集合上的函数的问题联系起 来。 设 F(X) 为所有 X 到 R 的函数全体构成的向量空间，对 f, g ∈ F(X) 定义格运算 f ∨ g = max{f, g}, f ∧ g = min{f, g}, 则 F(X) 为一（向量）格。不难验证，对 A, B ⊂ X， 1A∪B = 1A∨B = 1A ∨ 1B, 1A∩B = 1A∧B = 1A ∧ 1B 建立了集合上的函数与集合之间的联系
20第二章准备工作思考题：验证以下关于特征函数的基本性质：11AUB=1A+IB-IAnB;2.1AnB=IA-IB;3. 1A\B = 1A(1 - 1B);4. 1AAB = [IA - 1Bl;5. limsuPe A = limsupk→ lAr;6. lim infe- Ak = lim infk-00 lAk o集合的对等在集合论中，集合元素的个数是一个基本问题。定义2.11.集合A与B称作对等，记作A～B，若存在f：A→B为一双射。上述对等的概念给出了幂集2X上的一个等价关系，即(1)A～A；(2)若A～B，则B～A；(3)若A～B,B～C，则A～C。后面我们引入的所谓集合的基数（或者势）可以看成幂集关于上述等价关系～的一个等价分类。稍后我们具体讨论这个概念。例2.12.我们先来考虑几个简单的例子。(1) N ~ 2N, N~ 2N +1。(2) N × N ~ N。定义函数f：N×N→N：f(i,j) =2i-1(2j -1),(i,j) eNxnN.由算术基本定理（即整数的唯一分解定理），任给nEN，n有如下表示：n=2P-q,PENU(0),qE2N+1这表明f为满射。f为单射易证。(3) (-1, 1) ~ Rc定义函数f：(-1,1)→R：f(ar) = i1-a2) ze (-1,1),则f为所需的双射
20 第二章 准备工作 思考题：验证以下关于特征函数的基本性质： 1. 1A∪B = 1A + 1B − 1A ∩ B； 2. 1A∩B = 1A · 1B； 3. 1A\B = 1A(1 − 1B)； 4. 1A△B = |1A − 1B|； 5. 1lim supk→∞ Ak = lim supk→∞ 1Ak； 6. 1lim infk→∞ Ak = lim infk→∞ 1Ak。 集合的对等 在集合论中，集合元素的个数是一个基本问题。 定义 2.11. 集合 A 与 B 称作对等，记作 A ∼ B，若存在 f : A → B 为一双 射。 上述对等的概念给出了幂集 2 X 上的一个等价关系，即 (1) A ∼ A；(2) 若 A ∼ B，则 B ∼ A；(3) 若 A ∼ B, B ∼ C，则 A ∼ C。后面我们引入的所谓 集合的基数（或者势）可以看成幂集关于上述等价关系 ∼ 的一个等价分类。 稍后我们具体讨论这个概念。 例 2.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 为所需的双射
212.1集合论定理2.13.（Cantor-Bernstein）若X与Y的真子集对等，且Y与X的真子集对等，则X~Y。证明：我们首先证明断言：设f：X→Y，g：X→Y，则存在分解X=AUA Y-BUB其中 B=f(A), A=g(B), AnA=0, BnB=O。断言的证明：设d=(EcX:Eng(Y\f(E))=0)注意到至少E。令A=UEeaE，下面证明AE4。任给EE4，ECA。由于Eng(Y\f(E))=0,则Eng(Y\f(A))=，从而Ang(Y \f(A)=)ng(Y \f(A)ELEEd= U (Eng(Y\f(A) =0.EEd所以AE4、且A为4中的最大元。令B=f(A)，B=Y\B，A=g(B),容易验证Y=BUB, BnB=O下面证明余下的结论。由于AnA=Ang(B)=Ang(Y\B)=Ang(Yf(B))=の,故AUA=X。不然，存在oEX，o史AUA。设Ao=AUro)，则= AnA=Ang(B) =Ang(Y\f(A)DAng(Y /f(Ao)这表明Ang(Y/f(Ao))=の。又o AUA→ A→r g(Y\f(A0)故Aong(Y/f(Ao))=(AU(ro))ng(Y\f(Ao)= Ang(Y If(Ao)) = 0
2.1 集合论 21 定理 2.13. （Cantor-Bernstein）若 X 与 Y 的真子集对等，且 Y 与 X 的真子 集对等，则 X ∼ Y 。 证明：我们首先证明 断言： 设 f : X → Y ，g : X → Y ，则存在分解 X = A ∪ A, Y ˜ = B ∪ B, ˜ 其中 B = f(A)，A˜ = g(B˜)，A ∩ A˜ = ∅，B ∩ B˜ = ∅。 断言的证明： 设 A = {E ⊂ X : E ∩ g(Y \ f(E)) = ∅}. 注意到至少 ∅ ∈ A 。令 A = ∪E∈A E，下面证明 A ∈ A 。 任给 E ∈ A ，E ⊂ A。由于 E ∩ g(Y \ f(E)) = ∅, 则 E ∩ g(Y \ f(A)) = ∅，从而 A ∩ g(Y \ f(A)) = ( ∪ E∈A E ) ∩ g(Y \ f(A)) = ∪ E∈A (E ∩ g(Y \ f(A)) = ∅. 所以 A ∈ A ，且 A 为 A 中的最大元。 令 B = f(A)，B˜ = Y \ B，A˜ = g(B˜)，容易验证 Y = B ∪ B, B ˜ ∩ B˜ = ∅. 下面证明余下的结论。 由于 A ∩ A˜ = A ∩ g(B˜) = A ∩ g(Y \ B) = A ∩ g(Y \ f(B)) = ∅，故 A ∪ A˜ = X。不然，存在 x0 ∈ X，x0 ̸∈ A ∪ A˜。设 A0 = A ∪ {x0}，则 ∅ = A ∩ A˜ = A ∩ g(B˜) = A ∩ g(Y \ f(A)) ⊃ A ∩ g(Y \ f(A0)), 这表明 A ∩ g(Y \ f(A0)) = ∅。又 x0 ̸∈ A ∪ A˜ ⇒ x0 ̸∈ A˜ ⇒ x0 ̸∈ g(Y \ f(A0)), 故 A0 ∩ g(Y \ f(A0)) = (A ∪ {x0}) ∩ g(Y \ f(A0)) = A ∩ g(Y \ f(A0)) = ∅
22第二章准备工作I即AoE4，这与A的极大性矛盾。设f：X→Y，9:Y→X为单射，则由断言，存在分解X=AUA, Y=BUB, B=f(A), A=g(B)注意到flA及gl均为双射，因此定义f(r),rEAF(r)=Ig-(r),reA,rex,口则F：X→Y为双射，从而X~Y。推论2.14.若CCACB且B~C,则B~A。证明：由B～C，存在单射f:B→CCA，而包含映射为A到B的单射，口B～A是定理2.13的直接推论。例2.15.[-1,1]～R。这是因为(-1,1)C[-1, 1] C R例2.12.(3)表明（-1,1）~R，故由定理2.13，[-1,1]～R。注意不可能找到连续函数建立这种对等关系。集合的基数对每一个集合A，与之联系的一个概念是A的元素的个数，记作cardA，称作A的基数（或势)。例如若A=[1,2,...,n]，则cardA为A的元素个数，即此时cardA=n。设A,B为集合，若A～B，则称A与B具有相同的基数，即cardA=card B。若存在f：A→B为单射，即A与B的真子集f(A)对等，则称cardA小于cardB，记作cardA≤cardB。因此，Cantor-Bernstein定理事实上是说：若cardA≤card B且card B≤card A，则cardA=cardB。我们先来考虑一个简单的情形。集合A称作有限集若存在nEN使得A与集合1,2,...,n}对等。此时cardA=n。个集合称作无穷集若它不是有限集。关于无穷集，两个重要的例子是自然数集N与实数集R。下面我们以这两个集合为基础展开讨论。N的基数·可数集
22 第二章 准备工作 即 A0 ∈ A ，这与 A 的极大性矛盾。 \\\\ 设 f : X → Y ，g : Y → X 为单射，则由断言，存在分解 X = A ∪ A, Y ˜ = B ∪ B, B ˜ = f(A), A˜ = g(B˜). 注意到 f|A 及 g|B˜ 均为双射，因此定义 F(x) = { f(x), x ∈ A g −1 (x), x ∈ A˜ , x ∈ X, 则 F : X → Y 为双射，从而 X ∼ Y 。 □ 推论 2.14. 若 C ⊂ A ⊂ B 且 B ∼ C，则 B ∼ A。 证明：由 B ∼ C，存在单射 f : B → C ⊂ A，而包含映射为 A 到 B 的单射， B ∼ A 是定理2.13的直接推论。 □ 例 2.15. [−1, 1] ∼ R。这是因为 (−1, 1) ⊂ [−1, 1] ⊂ R, 例2.12.(3) 表明 (−1, 1) ∼ R，故由定理2.13，[−1, 1] ∼ R。注意不可能找到 连续函数建立这种对等关系。 集合的基数 对每一个集合 A，与之联系的一个概念是 A 的元素的个数，记作 card A， 称作 A 的基数（或势）。例如若 A = {1, 2, . . . , n}，则 card A 为 A 的元素个 数，即此时 card A = n。 设 A, B 为集合，若 A ∼ B，则称 A 与 B 具有相同的基数，即 card A = card B。若存在 f : A → B 为单射，即 A 与 B 的真子集 f(A) 对等，则称 card A 小于 card B，记作 card A ⩽ card B。因此，Cantor-Bernstein 定理事实 上是说：若 card A ⩽ card B 且 card B ⩽ card A，则 card A = card B。 我们先来考虑一个简单的情形。集合 A 称作有限集若存在 n ∈ N 使得 A 与集合 {1, 2, . . . , n} 对等。此时 card A = n。 一个集合称作无穷集若它不是有限集。关于无穷集，两个重要的例子是 自然数集 N 与实数集 R。下面我们以这两个集合为基础展开讨论。 N 的基数·可数集
232.1集合论我们将N的基数cardN记作No，与N对等的集合称作可数（无穷）集。显然若A为可数集，则cardA=No。显然，每一可数集A均可以写成如下形式：A=(ai,a2...,an,...J, a,EA, ieN.下面是可数集的一些基本性质：(1）无穷集中必包含可数集。设A为任意无穷集，则由数学归纳法，我们很容易构造A的可数子集。这表明N。为无穷集中的最小的基数。(2）有限集与可数集的并为可数集。设A=a1,a2an)为有限集，B=[bi,b2.bn...]为可数集，定义f:N→AUB1≤k≤nak,F(k) :,kEN.bk-n，k>n不难验证F为一双射。(3）可数个可数集之并为可数集。设【AnneN为可数集合列，每一An均可数，A=UneNAn。不失一般性，假设An两两互不相交。设An =[anl,an2,...,anm,...], neN,则我们可以将A中元素排列如下：a11a12a13a1m..KKa21a22...a23..a2mKa31a32a33.....a3m：:1：an1an2an3..anm：按照箭头所示，A为可数集。（4）可数集的有限直积为可数集。设nEN，这等价于考虑Nn，按照字典序可以证明
2.1 集合论 23 我们将 N 的基数 card N 记作 ℵ0，与 N 对等的集合称作可数（无穷）集。 显然若 A 为可数集，则 card A = ℵ0。显然，每一可数集 A 均可以写成如下 形式： A = {a1, a2 . . . , an, . . .}, ai ∈ A, i ∈ N. 下面是可数集的一些基本性质： (1) 无穷集中必包含可数集。 设 A 为任意无穷集，则由数学归纳法，我们很容易构造 A 的可数子集。 这表明 ℵ0 为无穷集中的最小的基数。 (2) 有限集与可数集的并为可数集。 设 A = {a1, a2 . . . , an} 为有限集，B = {b1, b2 . . . , bn, . . .} 为可数集，定 义 f : N → A ∪ B， F(k) = { ak, 1 ⩽ k ⩽ n bk−n, k > n , k ∈ N. 不难验证 F 为一双射。 (3) 可数个可数集之并为可数集。 设 {An}n∈N 为可数集合列，每一 An 均可数，A = ∪n∈NAn。不失一般 性，假设 An 两两互不相交。设 An = {an1, an2, . . . , anm, . . .}, n ∈ N, 则我们可以将 A 中元素排列如下： a11 a12 a13 · · · a1m · · · ↙ ↙ a21 a22 a23 · · · a2m · · · ↙ a31 a32 a33 · · · a3m · · · . . . . . . . . . . . . . . . an1 an2 an3 · · · anm · · · . . . . . . . . . . . . 按照箭头所示，A 为可数集。 (4) 可数集的有限直积为可数集。 设 n ∈ N，这等价于考虑 N n，按照字典序可以证明