第3讲 集合间的关系 Jan 06, 2018 Shawn Abstract Algebra No comments yet 第4讲 映射 Jan 06, 2018 Shawn Abstract Algebra No comments yet 第5讲 罗素悖论（选修） Jan 06, 2018 Shawn Abstract Algebra No comments yet 第6讲 势与基数（选修） Jan 06, 2018 Shawn Abstract Algebra No comments yet 第7讲 定义良好 Jan 06, 2018 Shawn Abstract Algebra No comments yet 1 … 3 4 5 6 7 … 10
![关系 • 定义 ○ 对于任意集合 A，定义 A 上的一个关系为 A×A 的子集 R • 记号 ○ A×A={(x,y)|x,y∈A} ○ 若 (x,y)∈R, 我们可以写作 xRy • 例1 ○ A={全世界的人} ○ A×A={(甲,乙)|甲,乙∈A} ○ 定义 R={(甲,乙)∈A×A|甲是乙的父亲} ○ 其中 R 为父子关系 • 例2 ○ 对于任意集合 A，定义对角线 Δ={(x,x)|x∈A}⊆A×A ○ Δ 定义了 A 上元素的相等关系 ○ xΔy⇔x=y 偏序关系 • 定义：A 上的一个偏序关系 R 是符合以下三个条件的关系 a. 自反性：∀x∈A, xRx b. 反对称性：如果 xRy 且 yRx，那么 x=y c. 传递性：如果 xRy 且 yRz，那么 xRz • 例子 ○ 对于实数集 R：≤ ○ 对于任意集合 A：= 等价关系 • 定义：A 上的一个等价关系 R 是符合以下三个条件的关系 a. 自反性：∀x∈A, xRx b. 对称性：如果 xRy 那么 yRx c. 传递性：如果 xRy 且 yRz，那么 xRz • 思考题：是否能通过 b, c 推出 a ○ 不能，自反性要求对任意 x∈A 都成立 ○ 无法保证对任意 x∈A 都存在 y 使得 xRy • 一般会用 ~ 来表示等价关系 等价类 • 定义 ○ 令 A 为任意集合，~ 为 A 上的等价关系 ○ 对于 a∈A ，定义 a 的等价类为 ○ [a]={b∈A|a~b} • 定理 1：如果[a]∩[b]≠∅，那么 [a]=[b] ○ 首先证明 [a]⊆[b] ○ 让 c∈[a]∩[b]， ○ 对于所有 x∈[a], a~x ○ 根据传递性有 c~x⇒b~x，即 x∈[b] ○ 所以 [a]⊆[b]，同理可得 [b]⊆[a] ○ 即 [a]=[b] • 定理 ○ ∀a∈A, a∈[a]⇒a∈⋃8_(a∈A)▒[a] ⇒A⊆⋃8_(a∈A)▒[a] ○ [a]⊆A⇒⋃8_(a∈A)▒[a] ⊆A ○ 故 A=⋃8_(a∈A)▒[a] ○ 又由定理1得 [a] 之间互不相交 ○ 注：我们将这一过程称为等价类分割 商集 • 定义 ○ 令 A 为任意集合，~ 为 A 上的等价关系 ○ 定义 {[a]|a∈A } 为 A 除以 ~ 的商集 ○ 记作 A\/~ • 例1 ○ 对于任意集合 A 和等价关系 = ○ A\/\= ={[a]|a∈A }={{a}|a∈{A}} • 例2 ○ 令 A={所有人} ○ 定义等价关系 ~ 为性别相同 ○ 则 A\/~ ={{所有男人},{所有女人}} • 例3 ○ 令 A=Z ○ 定义 m,n∈Z 等价当且仅当 m≡n mod a ○ 则 A\/~ ={0,1,…,a−1} A Δ A](https://shawnzhong.com/wp-content/uploads/2018/01/img_5a50f63c6ef9f.png)
![映射 • 定义 ○ 一个从集合 A 到集合 B 的映射是 A×B 的子集 f ○ 且对于任意 a∈A，存在唯一的 b∈B 使得 (a,b)∈f ○ 我们将 a,b 之间的关系 记作 f(a)=b 或 f:a↦b ○ 集合 A 称为映射的定义域 ○ 集合 B 称为映射的陪域 ○ 我们将定义域 A 到陪域 B 的映射记作 f:A→B • 例1 ○ 对于任意集合 A，定义恒等映射 1_A:A→A, a↦a • 例2 ○ 令 A=B=R，即我们学过的函数均为映射，如 ○ f(x)=x^2, g(x)=sinx 等 • 例3 ○ 令 A⊆B，定义包含映射 i:A→B, a↦a • 例4 ○ 对于 (A,~)，定义投影映射 p:A→A\/~,a↦[a] 单射、满射、双射 • 单射 ○ f:A→B 是单射当且仅当 ○ f(a)=b⇒a=b • 满射 ○ f:A→B 是满射当且仅当 ○ ∀b∈B，存在 a∈A 使得 f(a)=b • 双射 ○ f:A→B 是满射当且仅当 ○ f 即是单射又是满射 ○ 又说 A 与 B 存在一一对应 • 等势 ○ A 与 B 等势当且仅当A 与 B 存在一一对应 ○ 记作 |A|=|B| • 例1 ○ f(x)=x 是双射 • 例2 ○ g(x)=arctanx 是单射但不是满射 ○ 因为没有元素映射到 (−∞,−π/2)∪(π/2,∞) • 例3 ○ h(x)=x sinx 是满射但不是单射 ○ 因为有多个元素射到了同一个元素上 • 例4 ○ k(x)=|x| 既不是单射也不是满射 ○ 因为有多个元素射到了同一个元素上 ○ 且没有元素映射到 (−∞,0) 映射的逆 • 定义 ○ 给定 f:A→B，定义 f 的逆为 ○ f^(−1):2^B→2^A, D↦f^(−1) (D)={x∈A|f(x)∈D} ○ 当 D 为单元素集时，我们记 f^(−1) ({y})=f^(−1) (y) ○ 我们称 f^(−1) (D) 为 D 的拉回，称 f^(−1) (y) 为 y 的纤维 • 定理 ○ 给定 f:A→B 和 f 的逆 f^(−1) ○ f^(−1) (C∪D)=f^(−1 ) (C)∪f^(−1) (D) ○ f^(−1) (C∩D)=f^(−1 ) (C)∩f^(−1) (D) ○ f^(−1) (C^c )=(f^(−1 ) (C))^c 映射的推出 • 定义 ○ 给定 f:A→B，定义 f 的推出为 ○ g:2^A→2^B, C↦g(C)={y∈B|y=f(x),x∈C} ○ 我们称 g(D) 为 C 的像 • 定理 ○ 给定 f:A→B 和 f 的推出 g ○ g(C∪D)=g(C)∪g(D) ○ g(C∩D)⊆g(C)∩g(D) 卡氏幂 • 定义 ○ 对于任意集合 A,B ○ 我们将 A 到 B 的映射所组成的集合称作卡氏幂 ○ 记作 B^A • 定理：2^A 作为幂集与 2^A 作为卡氏幂有着一一对应 ○ 2={0,1} ○ 为了区分，暂时把幂集记为 P(A) ○ 构造映射 f:2^A→P(A), g↦g^(−1) (1) ○ 需要证明 f 是一个双射，即 f 是单射和满射 ○ 首先证明 f 是单射 § 假设 f(g)=f(h § 根据 f 的定义，有 g^(−1) (1)=h(−1) (1) § 即 g(x)=1 当且仅当 h(x)=1 § 又因为 g,h 的定义域为 2={0,1} § 故 g(x)=0 当且仅当 h(x)=0 § 所以 g=h § 即 f 是单射 ○ 还需证明 f 是满射 § 即对于任意 C⊆A 都有 g∈2^A 使得 f(g)=C § 构造 g:A→2, g(x)={■8(1&x∈C@0&x∉C)┤ § 即 f 是满射 ○ 即得证 康托尔－伯恩斯坦－施罗德定理 • 命题 ○ 若集合 A 与 B 之间存在单射 f:A→B, g:B→A ○ 那么 A 与 B 存在一一对应 • 证明 ○ 给定 a_0∈A 我们进行以下构造 ○ ⋯a_(−1) ⟼┴f b_(−1) ⟶┴g a_0 ⟼┴f b_0 ⟶┴g a_1 ⟼┴f b_1 ⟶┴g⋯ ○ 存在以下四种情况 1. a_0 可以往两个方向无限拉回和推出 2. a_0 可以往右无限推出，但是只能拉回到 a∈A 3. a_0 可以往右无限推出，但是只能拉回到 b∈B 4. a_0 往右推出到了 a_0 本身，形成一个闭合的圆 ○ 构造 h:A→B, h(x)={■8(f(x)&x 属于第1,2,4种情况@g^(−1) (x)&x 属于第3种情况)┤ ○ 不难看出 h 是一个双射 映射的复合 • 定义 ○ 给定 f:A→B, g:B→C ○ 定义 g 与 f 的复合为 g∘f:A→C ○ g∘f(x)=g(f(x)) • 结合律 ○ 给定 f:A→B, g:B→C, h:C→D ○ h∘(g∘f)=(hg)∘f:A→D ○ 因为 h∘(g∘f)=h(g(f(x)))=(hg)∘f • 定理：如果 f 和 g 都是单射/双射/满射，那么 g∘f 也满足相应性质 ○ 仅证明单射的情况 ○ 若 g∘f(x)=g∘f(y) ○ 因为 g 是单射， f(x)=f(y) ○ 又因为 f 是单射， x=y ○ 故 g∘f 是单射](https://shawnzhong.com/wp-content/uploads/2018/01/img_5a50f74ebd804.png)
![无限集合与有限集合 • 定义 ○ 若集合 A 与它的一个真子集存在一一对应，则称之为无限集合 ○ 若一个集合不是无限集合，我们称它为有限集合 • 例1 ○ 对于整数集 Z ○ 定义偶数集 2Z={2n∈Z n∈Z ○ 则 2Z⫋Z ○ 存在双射 f:Z→2Z, n↦2n ○ 故整数集 Z 为无限集合 • 例2 ○ 对于自然数集 N={0,1,2,…} ○ 定义 N 的真子集 N+1={1,2,…} ○ 存在双射 g:N→N+1, n↦n+1 ○ 故自然数集 N 为无限集合 集合的势 • 集合的势 ○ 集合的势即为集合的大小 ○ 集合 A 的势记作 |A| • 等势 ○ 集合 A 与 B 等势，当且仅当存在双射 f:A→B ○ 即 A 与 B 之间有一一对应 ○ 记作 |A|=|B| • 势之间的比较 ○ 集合 A 的势小于或等于 B 的势，当且仅当存在单射 f:A→B ○ 记作 |A|≤|B| • 等势的性质 ○ 对任意集合 A, |A|=|A| § 由恒等映射 1_A 是双射得出 ○ 如果 |A|=|B| § 根据双射的性质 § 对于双射 f:A→B，必然存在逆映射 f^(−1):B→A ○ 如果 |A|=|B| § 根据复合的性质 § 双射 f:A→B 和 g:B→C 的复合 g∘f:A→C 仍是双射 ○ 注：以上三条性质可以类比等价关系的三条性质 基数 • 引入 ○ 等势是集合与集合之间的一个等价关系 ○ 对于其每个等价类 [A]，我们用 |A| 来代替，又被称作 A 的基数 ○ 对于有限集合 A, |A|=元素的个数 ○ 我们可以将自然数定义为 N={有限集合的基数} • 记号 ○ |N=ℵ_0 ○ |R=c • 基数的性质 ○ 对任意集合 A, |A|=|A| § 可以通过恒等映射 1_A 得出 ○ 如果 |A|≤|B|, 且 |B|≤|A|，那么 |A|=|B| § 根据康托尔－伯恩斯坦－施罗德定理 ○ 如果 |A|≤|B|, 且 |B|≤|C|，那么 |A|≤|C| § 根据映射的复合 ○ 注：以上三条性质可以类比偏序关系的三条性质 • 基数之间的运算 ○ |A|+|B|=|A⊔B| ○ |A|×|B|=|A×B| ○ |A|^|B| =|A^B | • 练习 1. 对于有限集合，举例验证基数运算和自然数运算是一样的 2. 如果 A 是无限集合那么有 ℵ_0≤|A| 3. |A|≤|A|+|B| 4. |A|+|A|=2|A| 5. ℵ_0×ℵ_0=ℵ_0^2=ℵ_0 6. 2^(ℵ_0 )=c • 定理：对于任意集合 A，|A|<|2^A | ○ 首先证明 |A|≤|2^A | § 构造映射 f:A→2^A, a↦{a} § 易证映射 f 为单射 ○ 再用反证法证明 |A|≠|2^A | § 假设存在双射 f:A→2^A § 定义集合 B={x∈A|x∉f(x)} § 令 b∈A 使得 f(b)=B § 若 b∈f(b)=B，那么 b∉f(b) § 若 b∉f(b)=B，那么 b∈f(b) § 存在矛盾，故不存在这样的双射 § 即 |A|≠|2^A | ○ 故 |A|<|2^A | • 连续统假设 ○ |N=ℵ_0, 2^(ℵ_0 )=c ○ 根据以上定理有 ℵ_0<c ○ 康托尔将无穷基数从小到大排列为 ℵ_0, ℵ_1, ℵ_2⋯ ○ 连续统问题即 c =┴? ℵ_0 ○ 已被证明连续统假设和公理化集合论相洽 ○ 即在公理化集合论内无法证明或真伪这个问题](https://shawnzhong.com/wp-content/uploads/2018/01/img_5a50f78df0bf8.png)
![复习 • 商集 ○ 令 A 为任意集合，~ 为 A 上的一个等价关系 ○ A\/~\={[a]|a∈A} • 等价类 ○ [a]={x∈A|a~x} 定义良好 • 引入 ○ 想定义映射 f:A\/~→B, [a]↦f([a]) ○ 为计算 f([a]) 一般会在 [a] 中选取一个代表元 ○ 假设 [a]=[b] 但 a≠b ○ f([a])=f([b]) 恒成立 ○ 但 f(a)=f(b) 不一定满足 • 定义 ○ 一个从商集 A\/~ 到集合 B 的映射 f([a])=f(a) 定义良好 ○ 当且仅当对于任意 a~b 总有 f(a)=f(b) • 例1 ○ A\/~={24个小时}\/~\={钟表上的刻度} ○ 定义函数 f:A\/~→R 为该钟表刻度对应的室外温度 ○ 这个函数一般地不是定义良好 ○ 因为不能保证上午下午同一时刻的室外温度都相等 • 例2 ○ {班上的同学}\/性别={男生,女生} ○ 定义函数 f 为班上男同学与女同学的成绩之差 ○ 这个函数一般地不是定义良好 ○ 因为根据选取同学的不同，结果不同 ○ 思考题：在什么样的班上这个函数是定义良好的？ • 例3 ○ 在整数集 Z 内定义等价关系 ~ 为除以正整数 n 同余 ○ 定义集合 Z\/n=Z\/~\={0,1,2,3,…,n−1} ○ 在 Z\/n 下定义加法 +:Z\/n×Z\/n→Z\/n,([a],[b])↦([a+b]) § 验证定义良好 § 假设 a~c, b~d，那么 [a]=[c], [b]=[d] § 我们要验证 [a+b] =┴? [c+d] § 若 a 和 c 同余，则 a−c=kn, k∈N § 若 b 和 d 同余，则 b−d=ln, l∈N § (a+b)−(c+d)=(a−c)+(b−d)=(k+l)n § 即 a+b 和 c+d 同余 § 故 [a+b]=[c+d] ○ 在 Z\/n 下定义乘法 +:Z\/n×Z\/n→Z\/n,([a],[b])↦([a×b]) § 验证定义良好 § 假设 a~c, b~d，那么 [a]=[c], [b]=[d] § 我们要验证 [a×b] =┴? [c×d] § 若 a 和 c 同余，则存在 p,q 使得 a−mp=c−mq § 若 b 和 d 同余，则存在 s,t 使得 b−ms=d−mt § （a−mp）（b−ms）=(c−mq)(d−mt) § ⇒ab−cd=m(as+bp−msp−ct−dq+mqt) § 即 ab 和 cd 同余 § 故 [a×b]=[c×d]](https://shawnzhong.com/wp-content/uploads/2018/01/img_5a50f7a83f812.png)
