1.1集合与逻辑初步称为集族（Familyofsets)，I称为这个这个集族的指标集(Indexset)这里有几点关于这个定义的说明：1.我们并不要求i时有Ai≠Ai集族中的元素是允许重复的7；2.我们不要求A，是非空的，不过集族当然是非空的3.不一定是个数字，虽然你在之后最先接触到的指标集大多都是数集有了这样的定义，我们就可以自然地定义若干个集合的并与交：定义1.17（集族的交和并）设X为集合，A：=[AiEI)为X的一个子集族我们分别定义这个集族的交和并为：NA, :=(rEXIViEI,rEA),与UA, :-{rexlFieI,reA)“顾名思义，这个集族里面的元素都是X的子集，显然，子集族的并与交也是X的子集此外关于记号的事情，我们也经常写成A,和UAi，ilNAEAA和UAEAA.如果A为有限集族，那么这些集合可以用有限多个自然数来标记，指标集I=C[0,1,.…,n],我们也经常写为下面两个形式：nnn.A4,UAi,i=0i=0与Aon...nAn.Ao U...U An.此时我们可以去拓展一下命题1.1的那些性质：命题1.3（集族的运算律）设{A;|iEI}和[B,liEJ)为集合X的子集族,那么：1.结合律：(N;A)n(n, B)=N(ij)A;nBj;。(U, A) U (U, B,) =U(ii) A, U Bj;2.分配律：(N; A) U (N, B,) =N(i) A;U B;。(U, A:)n (U, B,) =U() A;nBy;3.德摩根反演律： (N; A)C =U, A:(U, A)C=N, AC.这里(i,i)遍历指标集I× J.7这一点看起来与集合的不相容性相俘，事实上集族的确不一定是个集合，不过我们不会在这一点上作更深的讨论，感兴趣的话可以去阅读集合论的相关书籍12
1.1 集合与逻辑初步 ♣ 称为集族 (Family of sets), I 称为这个这个集族的指标集 (Index set). 这里有几点关于这个定义的说明： 1. 我们并不要求 i 6= j 时有 Ai 6= Aj , 集族中的元素是允许重复的7 ; 2. 我们不要求 Ai 是非空的, 不过集族当然是非空的; 3. i 不一定是个数字, 虽然你在之后最先接触到的指标集大多都是数集. 有了这样的定义, 我们就可以自然地定义若干个集合的并与交： 定义 1.17 (集族的交和并) ♣ 设 X 为集合, A := {Ai | i ∈ I} 为 X 的一个子集族a . 我们分别定义这个集族的交和并为： \ i Ai := {x ∈ X | ∀ i ∈ I, x ∈ Ai}, 与 [ i Ai := {x ∈ X | ∃ i ∈ I, x ∈ Ai}. a顾名思义, 这个集族里面的元素都是 X 的子集. 显然, 子集族的并与交也是 X 的子集. 此外, 关于记号的事情, 我们也经常写成 T i∈I Ai 和 S i∈I Ai , T A∈A A 和 S A∈A A. 如果 A 为有限集族, 那么这些集合可以用有限多个自然数来标记, 指标集 I = {0, 1, · · · , n}, 我们也经常写为下面两个形式: \n i=0 Ai , [n i=0 Ai , 与 A0 ∩ · · · ∩ An, A0 ∪ · · · ∪ An. 此时我们可以去拓展一下命题1.1的那些性质： 命题 1.3 (集族的运算律) ♠ 设 {Ai | i ∈ I} 和 {Bj | j ∈ J} 为集合 X 的子集族, 那么： 1. 结合律: ( T i Ai) ∩ ( T j Bj ) = T (i,j) Ai ∩ Bj ; ( S i Ai) ∪ ( S j Bj ) = S (i,j) Ai ∪ Bj ; 2. 分配律: ( T i Ai) ∪ ( T j Bj ) = T (i,j) Ai ∪ Bj ; ( S i Ai) ∩ ( S j Bj ) = S (i,j) Ai ∩ Bj ; 3. 德摩根反演律: ( T i Ai) C = S i AC i ; ( S i Ai) C = T i AC i . 这里 (i, j) 遍历指标集 I × J. 7这一点看起来与集合的不相容性相悖, 事实上集族的确不一定是个集合, 不过我们不会在这一点上作更深的讨论, 感兴趣的话 可以去阅读集合论的相关书籍. 12
1.2映射证明类似，留作习题，你感兴趣可以试试2笔记你可能会注意到，比起这两小节来讲，第一小节关于集合的描述似乎有点模糊得令人吃惊，的确，我们没有很严谨地定义“集合”和“元素”这两个概念，事实上，这两个概念在数学上也是未定义的.我们往往把它们视作公理（Axiom），即那些不证自明的法则.关于更加细致和严谨的讨论，你们应当去学习更加高等的课程，阅读更加深入的书籍资料，但我们在这里要强调的是，关于集合和元素到底是什么的问题并不重要，我们更关心的是如何去处理这些概念在本节的最后，我们介绍一个关于集合的概念定义1.18（分拆）店设X为集合,A:=[A,iEI}为X的一个子集族，若UA; = X,且对Vi,jEI,AnAj=O,即子集族元素两两不交则称A为X的一个分拆(Partition).说明白点，分拆就是把一个集合分成几部分，就像你可以把一个蛋糕切成几块，你可以把一个班按男生，女生分类，你当然也可以把一个集合给它分成几部分，这也是很自然的事情，以及在此种条件下，一个分拆对应的子集族的并，称为不交并(Disjointunion)，记为A，正如其iElMATHEMATICA双叶数理名，这些集合两两是不交的1.2映射ABA1.2.1映射的基本概念在介绍了基本的集合概念与集合的相关运算后，我们转而关心集合的对应关系.集合在生活中到处都是，我们往往在意两个集合间是如何对应起来的，这就要提到本节的概念映射：定义1.19（映射）一个从集合X到集合Y的映射(Map）是一种对应法则，使得对每一个X中的元素，对应着唯一确定的Y中元素，我们写作：f: X →Y, af(r).af(r）EY称为f在处的值(Value)，集合X称为f的定义域(Domain),记为dom(f)，Y称为f的到达域/陪域（Codomain）.而Im(f),Ran(f) := (yeY EaE X,y = f(r))称为f的像集(Image)或值域(Range).而graph(f) :=((r,y) eX xY Iy = f(a)) = (r, f(r))EXxY IreX)称为f的图像（Graph)“也经常简写为f：X→Y事实上不交并还有另外一层含义，考虑一个子集族A那么我们称（，）「EA为这个子集族的不交并，这样你会发现，即使子集间互相有重叠，我们也可以分辨出那些重叠的元素来自哪个子集，因为i起到了指示作用，13
1.2 映射 证明类似, 留作习题, 你感兴趣可以试试. 笔记 你可能会注意到, 比起这两小节来讲, 第一小节关于集合的描述似乎有点模糊得令人吃惊, 的确, 我 们没有很严谨地定义 “集合” 和 “元素” 这两个概念, 事实上, 这两个概念在数学上也是未定义的. 我们往 往把它们视作公理 (Axiom), 即那些不证自明的法则. 关于更加细致和严谨的讨论, 你们应当去学习更 加高等的课程, 阅读更加深入的书籍资料. 但我们在这里要强调的是, 关于集合和元素到底是什么的问 题并不重要, 我们更关心的是如何去处理这些概念. 在本节的最后, 我们介绍一个关于集合的概念. 定义 1.18 (分拆) ♣ 设 X 为集合, A := {Ai | i ∈ I} 为 X 的一个子集族, 若 [ i Ai = X, 且对 ∀ i, j ∈ I, Ai ∩ Aj = ∅, 即子集族元素两两不交. 则称 A 为 X 的一个分拆 (Partition). 说明白点, 分拆就是把一个集合分成几部分, 就像你可以把一个蛋糕切成几块, 你可以把一个班按 男生, 女生分类, 你当然也可以把一个集合给它分成几部分, 这也是很自然的事情. 以及在此种条件下, 一个分拆对应的子集族的并, 称为不交并 (Disjoint union)8 , 记为 F i∈I Ai , 正如其 名, 这些集合两两是不交的. 1.2 映射 1.2.1 映射的基本概念 在介绍了基本的集合概念与集合的相关运算后, 我们转而关心集合的对应关系. 集合在生活中到处 都是, 我们往往在意两个集合间是如何对应起来的, 这就要提到本节的概念———映射： 定义 1.19 (映射) ♣ 一个从集合 X 到集合 Y 的映射 (Map) 是一种对应法则, 使得对每一个 X 中的元素, 对应着唯一 确定的 Y 中元素, 我们写作： f : X → Y, x 7→ f(x). a f(x) ∈ Y 称为 f 在 x 处的值 (Value), 集合 X 称为 f 的定义域 (Domain), 记为 dom(f), Y 称为 f 的到达域/陪域 (Codomain). 而 Im(f), Ran(f) := {y ∈ Y | ∃ x ∈ X, y = f(x)} 称为 f 的像集 (Image) 或值域 (Range). 而 graph(f) := {(x, y) ∈ X × Y | y = f(x)} = {(x, f(x)) ∈ X × Y | x ∈ X} 称为 f 的图像 (Graph). a也经常简写为 f : X → Y . 8事实上不交并还有另外一层含义, 考虑一个子集族 A, 那么我们称 {(x, i) | x ∈ Ai} 为这个子集族的不交并, 这样你会发现, 即 使子集间互相有重叠, 我们也可以分辨出那些重叠的元素来自哪个子集, 因为 i 起到了指示作用. 13
1.2映射im(f)图1.3:映射笔记值得一提的是，一→箭头用于集合之间，→箭头用于元素之间，这两者不应混清你应当注意到Im(f）一般都是Y的子集，而graph(f）一般都是X×Y的子集，然而在图1.4中，G可以是从X到Y的一个映射的图像，但H不可以，因为一个可能对应了多个y，有的却没有对应任何y：X4图1.4:映射的图像注事实上，如果我先给你这个图，也就是说，我先给你一个X×Y的子集G，使得它具有性质“对VEX,!yEY s.t.(r,y)EG9",那么我们也可以定义一个映射：f: X →Y, rμ f(α) s.t. (r, f(r)) EG.显然，这个映射是良定义的(Well-defined),也就是说，每一个rEX都真真切切地有Y中的唯一的元素与其对应.显然，graph(J）=G，于是你意识到，映射的对应法则与映射的图像其实是息息相关，互相确定的.10因此这启发我们去换一种方式来定义映射：一个映射是一个有序三元组（X,GY),这里GCX×Y满足对任意rEX，存在唯一的yEY使得(r,y)EG.这种定义方式就避开了有用但是不太明确的词“法则”，而且也只用了我们集合论中的概念映射这个概念其实也比较易于理解，你当然也可以顾名思义去理解它，就好比我站在阳光下，阳光将我的身影拓在地上，我的向阳面就是定义域，地面就是到达域，影子就是值域或者像集，而阳光就是这个映射，它将我身上的点映射到了地面上，于是我的影子就依赖于这种对应关系而形成当然，我们更关心数学中的映射，比如数集间的映射：例题1.11.f:N→N，n→n2,即将每个自然数对应到它的平方;2.f:R2→R，（a1,22)→2+2,即将实平面上的点对应到它到原点的距离的平方；'s.t是使得的意思，这个记号也经常使用10用我们等下要学的话讲，叫一一对应14
1.2 映射 图 1.3: 映射 笔记 值得一提的是, → 箭头用于集合之间, 7→ 箭头用于元素之间, 这两者不应混淆. 你应当注意到 Im(f) 一般都是 Y 的子集, 而 graph(f) 一般都是 X × Y 的子集, 然而在图 1.4 中, G 可以是从 X 到 Y 的一个映射的图像, 但 H 不可以, 因为一个 x 可能对应了多个 y, 有的 x 却没有对应 任何 y： 图 1.4: 映射的图像 注 事实上, 如果我先给你这个图, 也就是说, 我先给你一个 X × Y 的子集 G, 使得它具有性质 “对 ∀ x ∈ X, ∃! y ∈ Y s.t. (x, y) ∈ G9 ”, 那么我们也可以定义一个映射： f : X → Y, x 7→ f(x) s.t. (x, f(x)) ∈ G. 显然, 这个映射是良定义的 (Well-defined), 也就是说, 每一个 x ∈ X 都真真切切地有 Y 中的唯一的元素 与其对应. 显然, graph(f) = G, 于是你意识到, 映射的对应法则与映射的图像其实是息息相关, 互相确 定的. 10因此这启发我们去换一种方式来定义映射： 一个映射是一个有序三元组 (X, G, Y ), 这里 G ⊆ X × Y 满足对任意 x ∈ X, 存在唯一的 y ∈ Y 使得 (x, y) ∈ G. 这种定义方式就避开了有用但是不太明确的词 “法则”, 而且也只用了我们集合论中的概念. 映射这个概念其实也比较易于理解. 你当然也可以顾名思义去理解它. 就好比我站在阳光下, 阳光 将我的身影拓在地上, 我的向阳面就是定义域, 地面就是到达域, 影子就是值域或者像集, 而阳光就是这 个映射, 它将我身上的点映射到了地面上, 于是我的影子就依赖于这种对应关系而形成. 当然, 我们更关心数学中的映射, 比如数集间的映射： 例题 1.1 1. f : N → N, n 7→ n 2 , 即将每个自然数对应到它的平方; 2. f : R 2 → R, (x1, x2) 7→ x 2 1 + x 2 2 , 即将实平面上的点对应到它到原点的距离的平方; 9 s.t. 是使得的意思, 这个记号也经常使用. 10用我们等下要学的话讲, 叫一一对应. 14
1.2映射3.f：Z×N+→Q，（9,P)→,即将一个整数组对应到以它们为分子分母的分数当然啦，如果f是一个从X到Y的映射，那么对于X中的元素，Y会有相应的元素，如果我们取X的一个子集，也应当有Y的一个子集与其对应.即：定义1.20（像与原像）设f:X-→Y 为映射,ACX,BCY,则f(A) :=[f(r) IrE A)称为A在f下的像(Image)f-l(B) := (rEX If(r) EB)称为B在f下的原像(Preimage)你可以参考这个图：f(A)f-1(B)R图1.5：像与原像当然，原像集可以是空的，如果X中没有元素映射到B中的话，比如例1.1中的1,显然f-1（[2)）=の，毕竞2不是完全平方数如果我们只考虑Y中一个单元素集的对应情况的话，我们有如下定义：定义1.21（纤维）对VyEY,集合f-l((y)) := reX If(ar) =y)称为f的一根纤维(Fiber)比如刚才的f-1（[21）就是f的一根纤维.事实上，纤维就是方程f(r）=y的解集我们来举一点例子来说明一些细节，顺便帮你熟悉一下这些概念例题1.21.注意到之前我并没有告诉你们如果X或者Y是空集的情况下，这个映射会怎么样.如果X=の，则也存在唯一的映射：空映射(Emptymap):：α→Y，为什么说它唯一呢？因为它的图像G≤15
1.2 映射 3. f : Z × N+ → Q, (q, p) 7→ q p , 即将一个整数组对应到以它们为分子分母的分数. 当然啦, 如果 f 是一个从 X 到 Y 的映射, 那么对于 X 中的元素, Y 会有相应的元素, 如果我们取 X 的一个子集, 也应当有 Y 的一个子集与其对应. 即： 定义 1.20 (像与原像) ♣ 设 f : X → Y 为映射, A ⊆ X, B ⊆ Y , 则 f(A) := {f(x) | x ∈ A} 称为 A 在 f 下的像 (Image). f −1 (B) := {x ∈ X | f(x) ∈ B} 称为 B 在 f 下的原像 (Preimage). 你可以参考这个图： 图 1.5: 像与原像 当然, 原像集可以是空的, 如果 X 中没有元素映射到 B 中的话, 比如例 1.1 中的 1, 显然 f −1 ({2}) = ∅, 毕竟 2 不是完全平方数. 如果我们只考虑 Y 中一个单元素集的对应情况的话, 我们有如下定义： 定义 1.21 (纤维) ♣ 对 ∀ y ∈ Y , 集合 f −1 ({y}) := {x ∈ X | f(x) = y} 称为 f 的一根纤维 (Fiber). 比如刚才的 f −1 ({2}) 就是 f 的一根纤维. 事实上, 纤维就是方程 f(x) = y 的解集. 我们来举一点例子来说明一些细节, 顺便帮你熟悉一下这些概念. 例题 1.2 1. 注意到之前我并没有告诉你们如果 X 或者 Y 是空集的情况下, 这个映射会怎么样. 如果 X = ∅, 则也存在唯一的映射：空映射 (Empty map):∅: ∅ → Y , 为什么说它唯一呢? 因为它的图像 G ⊆ 15
1.2映射×Y=の，而空集的子集是唯一的，也是空集.如果Y=の但X≠,则这个映射不存在2.我们说两个映射f：X→Y与g:U→V相等，记为f=9，指的是：X=U, Y=V 且 f(r)=g(r), rEX.也就是说，两个映射相等，当且仅当它们的定义域，到达域与法则均一致。一旦有一个不一致，那么两个映射就不同例题1.31.映射idx：X→X称为(X的）恒等映射(Identitymap),若X在上下文中不言自明，也可以省略不写，记为id.2.若XY则i：X→Y，→称为X到Y的包含映射(Inclusionmap)/嵌人(Embedding)我们通常使用弯钩箭头来表示嵌人：i：X→Y.值得一提的是，i=idx台X=Y3.若X和Y均非空，bEY,那么f：X→Y，→b称为常值映射(Constantmap)14.若f：X→Y,ACX,那么flA:A→Y，→f(a)称为映射f对A的限制(Restriction)5.设ACX,g:A→Y,则任意一个映射f：X→Y使得flA=g称为g的扩张(Extension),记为f2g12.比方说，对于2的例子，idy2i6.设X≠の，ACX，则A的示性映射/特征映射（Characteristiemap)指的是：TEAXA: X -→[0,1AO,TEAC7.若X1，Xn为非空集合，则你之前学过的投影Prk: Ix,→Xk, a=(a1,...,an)→ak, k=1, ..,ni=1FUTABA也是一个映射1.2.2映射的复合就像我们对集合做过的一样，在介绍完基本概念之后，我们再来考虑它的性质与运算.这里我们先介绍运算定义1.22（映射的复合）设有两个映射fX→Yg:Y→V,我们定义一个新的映射gof.称为f与g的复合映射(Compositionmap)g o f: X →V, a→ g(f(r)).(1.8)5我们把图1.3扩充一下就得到复合映射的过程：而实际上效果就是图1.7左下角的映射，它是另外两个映射的综合效果复合映射无非就是你两步并为一步走，把两个箭头干脆直接用一根箭头代替，从而更加简便。当然，我们也可以去考虑多个映射的复合，先看看这个命题1"事实上你更多地看到这个映射称为常值函数，但还没有讲到函数，所以暂且继续沿用映射的叫法，12你可能觉得集合的记号用在这里有点怪怪的，但从上面的注来看，这是十分自然的一件事情。16
1.2 映射 ∅ × Y = ∅, 而空集的子集是唯一的, 也是空集. 如果 Y = ∅ 但 X 6= ∅, 则这个映射不存在. 2. 我们说两个映射 f : X → Y 与 g : U → V 相等, 记为 f = g, 指的是： X = U, Y = V 且 f(x) = g(x), x ∈ X. 也就是说, 两个映射相等, 当且仅当它们的定义域, 到达域与法则均一致. 一旦有一个不一致, 那么 两个映射就不同. 例题 1.3 1. 映射 idX : X → X 称为 (X 的) 恒等映射 (Identity map), 若 X 在上下文中不言自明, 也可以省略 不写, 记为 id. 2. 若 X ⊆ Y , 则 i: X → Y, x 7→ x 称为 X 到 Y 的包含映射 (Inclusion map)/嵌入 (Embedding). 我们通常使用弯钩箭头来表示嵌入：i: X ,→ Y . 值得一提的是, i = idX ⇔ X = Y 3. 若 X 和 Y 均非空, b ∈ Y , 那么 f : X → Y, x 7→ b 称为常值映射 (Constant map)11 4. 若 f : X → Y , A ⊆ X, 那么 f|A : A → Y, x 7→ f(x) 称为映射 f 对 A 的限制 (Restriction). 5. 设 A ⊆ X, g : A → Y , 则任意一个映射 f : X → Y 使得 f|A = g 称为 g 的扩张 (Extension), 记为 f ⊇ g 12 . 比方说, 对于 2 的例子, idY ⊇ i. 6. 设 X 6= ∅, A ⊆ X, 则 A 的示性映射/特征映射 (Characteristic map) 指的是： χA : X → {0, 1}, x 7→ 1, x ∈ A 0, x ∈ AC 7. 若 X1, · · · , Xn 为非空集合, 则你之前学过的投影： Prk : Yn i=1 Xi → Xk, x = (x1, · · · , xn) 7→ xk, k = 1, · · · , n 也是一个映射. 1.2.2 映射的复合 就像我们对集合做过的一样, 在介绍完基本概念之后, 我们再来考虑它的性质与运算. 这里我们先 介绍运算. 定义 1.22 (映射的复合) ♣ 设有两个映射 f : X → Y , g : Y → V , 我们定义一个新的映射 g ◦ f, 称为 f 与 g 的复合映射 (Composition map)： g ◦ f : X → V, x 7→ g(f(x)). (1.8) 我们把图 1.3 扩充一下就得到复合映射的过程： 而实际上效果就是图 1.7 左下角的映射, 它是另外两个映射的综合效果： 复合映射无非就是你两步并为一步走, 把两个箭头干脆直接用一根箭头代替, 从而更加简便. 当然, 我们也可以去考虑多个映射的复合, 先看看这个命题： 11事实上你更多地看到这个映射称为常值函数, 但还没有讲到函数, 所以暂且继续沿用映射的叫法. 12你可能觉得集合的记号用在这里有点怪怪的, 但从上面的注来看, 这是十分自然的一件事情. 16