第1讲 集合的定义 Jan 06, 2018 Shawn Abstract Algebra No comments yet 第2讲 集合的运算 Jan 06, 2018 Shawn Abstract Algebra No comments yet 第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 1 2
![关系 • 定义 ○ 对于任意集合 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)
