Shawn Zhong

Shawn Zhong

钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Shawn Zhong

钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Abstract Algebra

Home / Mathematics / Notes / Abstract Algebra / Page 2

第5讲 罗素悖论(选修)

  • Jan 06, 2018
  • Shawn
  • Abstract Algebra
  • No comments yet
理发师悖论 • 小城里的理发师放出豪言: • 他只为,而且一定要为,城里所有不为自己刮胡子的人刮胡子。 • 但问题是:理发师该为自己刮胡子吗? • 如果他为自己刮胡子,那么按照他的豪言,他不应该为自己刮胡子。 • 如果他不为自己刮胡子,同样按照他的豪言,他又应该为自己刮胡子。 罗素悖论 • 假设 A={所有集合} • 令 B={A 里所有包含自己为元素的集合} • 即 B={x∈A| x∈x} • 因为 A∈A 所以 A∈B • 考虑 B 在 A 里的补集 B^c 是否属于 B^c? • 如果 B^c∈B^c⇒B^c∈B⇒B^c∉B^c • 如果 B^c∉B^c⇒B^c∉B⇒B^c∈B^c • 以上矛盾被称为罗素悖论 • 在公理化集合论中, 我们将上述例子中的 A 看作类 • 所有的集合都是类,但是不是所有的类都是集合 • 是集合的类被称作小类,不是集合的类被称作真类 书目悖论 • 一个图书馆要编纂一本书 • 其内容是列出该图书馆里所有不列出自己书名的书的名字。 • 那么作为目录的书该不该列出自己的书名? 思考题 • 怎么把理发师悖论与罗素悖论联系起来? ○ 令 S={城里所有不为自己刮胡子的人} ○ 若 理发师∈S⇒理发师要为自己刮胡子⇒理发师∉S ○ 若 理发师∉S⇒理发师不应为自己刮胡子⇒理发师∈S • 怎么把书目悖论与罗素悖论联系起来? ○ 令 S={图书馆里所有不列出自己书名的书} ○ 若 目录书∈S⇒目录书没有列出自己的书名⇒目录书∉S ○ 若 目录书∉S⇒目录书列出了自己的书名⇒目录书∈S
Read More >>

第6讲 势与基数(选修)

  • Jan 06, 2018
  • Shawn
  • Abstract Algebra
  • No comments yet
无限集合与有限集合 • 定义 ○ 若集合 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 ○ 已被证明连续统假设和公理化集合论相洽 ○ 即在公理化集合论内无法证明或真伪这个问题
Read More >>

第7讲 定义良好

  • Jan 06, 2018
  • Shawn
  • Abstract Algebra
  • No comments yet
复习 • 商集 ○ 令 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]
Read More >>

第8讲 群的定义

  • Jan 06, 2018
  • Shawn
  • Abstract Algebra
  • No comments yet
群 • 定义 ○ 一个群 (G,∗) 是一个由集合 G 以及定义在 G 上的二元运算 ∗ ○ 二元运算∗:G×G→G,(a,b)↦a∗b 要符合以下条件 i. 结合律:(a∗b)∗c=a∗(b∗c) ii. 恒等元素:G 里存在 e 使得 ∀a∈G,均有a∗e=e∗a=a iii. 逆元素:∀a∈G,存在 a^(−1)∈G,使得 a∗a^(−1)=a^(−1)∗a=e ○ 注:这个二元运算又叫做乘法 • 例1:(Z+) ○ ∀m,n∈Z, m+n∈Z ○ (m+n)+l=m+(n+l) ○ m+0=0+m=m ○ m+(−m)=(−m)+m=0 • 例2:(Zn,+) • 例3:({e},∗) ○ e∗e=e ○ 我们将这个群称为平凡群 • 例4 ○ 定义 [n]={1,2,…,n} ○ 定义 S_n={所有从 [n] 到 [n] 的双射} ○ 可以证明复合运算 ∘ 在 S_n 上定义了一个群结构 § (f∘g)∘h=f∘(g∘h § 1_[n] ∘h=h∘1_[n] =h § ∀f∈S_n, f^(−1):[n]↦[n] § f∘f^(−1)=f^(−1)∘f=1_[n] ○ 我们将这个群称为 n 次对称群 • 例5 ○ 在三维空间内选定一个点 P ○ ({所有围绕 P 的旋转},∘) 是一个群,记为 〖SO〗_3 • 例6 ○ 让 n 为任意正整数,构造正 n 边形 P_n ○ D_2n={所有 P_n 的对称} ○ |D_2n |=2n ○ 例如正五边形包括5个轴对称和5个中心对称 ○ (D_2n,∘) 构成一个群 ○ 我们将这个群称为二面体群 • 例7 ○ 定义 S^1={z∈ℂ│|z|=1} ○ (S^1,×) 构成一个群 ○ 若 |z|=|w|=1, ○ 我们将这个群称为单位圆群 • 阿贝尔群 ○ 阿贝尔群 = 交换群 ○ 群是可交换的当且仅当 ∀a,b, a∗b=b∗a 群的性质 • 定理 1:群的恒等元素只有一个 ○ 假设 e 和 e′ 都是恒等元素 ○ 那么 e=e∗e^′=e^′ • 定理 2:对于任意元素 a ○ 假设 a 有两个逆 b,b^′ ○ b=e∗b=(b^′∗a)∗b=b^′∗(a∗b)=b^′∗e=b^′ • 定理3:对于任意 a,b∈G, (a∗b)^(−1)=b^(−1)∗a^(−1) ○ (ab)(b^(−1) a^(−1) )=a(bb^(−1) ) a^(−1)=aea^(−1)=aa^(−1)=e ○ (b^(−1) a^(−1) )(ab)=b^(−1) (a^(−1) a)b=b^(−1) eb=b^(−1) b=e • 定理 4:对于任意元素 a∈G,(a^(−1) )^(−1)=a ○ a∗(a^(−1) )=(a^(−1) )∗a=e ○ ⇒a=(a^(−1) )^(−1)
Read More >>

第9讲 子群与生成

  • Jan 10, 2018
  • Shawn
  • Abstract Algebra
  • No comments yet
子群 • 定义 ○ 群 (G,∗) 的一个子群是 H⊆G ○ 并且 ∗ 限定到 H 上,使得 H 称为一个群 ○ 记作 H≤G ○ 若 H 是 G 的真子群,则记作 H<G • 例1 ○ (Z+) ○ 令 nZ={kn|k∈Z ○ 则 (nZ+) 是 (Z+) 的子群 • 例2 ○ S_n=({[n]→[n] 的双射},∘) ○ 令 H={f∈S_n |f(n)=n} 则 H<S_n ○ 事实上,H 和 S_(n−1) 是一样的群 • 例3 ○ (D_2n,∘) ○ D_2n 中有两种对称,轴对称和中心旋转对称 ○ 只考虑中心旋转对称,我们可以得到一个群 (C_n,∘) ○ 则 (C_n,∘) 是 (D_2n,∘) 的子群 • 例4 ○ 对于任意群 G,{e}≤G ○ 即平凡群是任何群的子群 ○ 正如空集是任意集合的子集 子群的性质 • 定理1:如果 H≤G,那么 H 的恒等元素也是 G 的恒等元素 ○ 假设 H 的恒等元素为 e^′,那么 (e^′ )^2=e^′ ○ 〖(e^′ )^(−1) (e^′ )〗^2=(e^′ )^(−1) e^′ ○ 即 e^′=e • 定理2:如果 H≤G, a∈H,那么 a 在 H 里的逆等于 a 在 G 里的逆 ○ 分别把 a 在 H,G 里的逆记为 b^′,b ○ 那么有 b^′=b^′ e=b^′ (ab)=(b^′ a)b=eb=b 生成 • 定义 ○ 令 G 为任意群,S 为 G 的一个子集 ○ 定义由 S 生成的子群为 ⟨S⟩=⋂8_(S≤H≤G)▒H ○ 我们把 S 称为 ⟨S⟩ 的生成集合 ○ 把 s∈S 称为 ⟨S⟩ 的生成元素 • 定理 ○ 命题 § 当 {H_α |a∈I} 是一个由 G 里的子群所组成的集合 § 那么 H=⋂8_(α∈I)▒H_α 也是 G 的子群 ○ 证明 § 封闭性(∀a,b∈H, a∗b∈H) □ 取任意 a,b∈H □ 根据交集的定义,a,b∈H_α,∀α∈I □ 根据子群的封闭性 a∗b∈H_α, ∀α∈I □ 根据交集的定义,a∗b∈H § 结合律 □ 不需要验证,直接从 G 得到 § 存在恒等元素 □ e∈H_α, ∀α □ ⇒e∈H § 存在逆 □ 对于任意 a∈H □ a∈H_α, ∀α □ ⇒a^(−1)∈H_α, ∀α □ ⇒a^(−1)∈H § 故H=⋂8_(α∈I)▒H_α 是 G 的子群 • 练习 ○ 对于 (Z+),问以下子集生成的子群是什么? § {0} § {8} § {8,9} ○ 证明:如果 S={n_i }⊆Z,那么 ⟨S⟩=⟨{所有 n_i 的最大公约数}⟩ ○ 证明:如果 H⊆G 那么 H≤G 当且仅当 § H 不为空集 § 对于任意 a,b∈H, a^(−1),b^(−1)∈H ○ 证明:如果 G 是一个有限群,H⊆G 那么 H≤G 当且仅当 § H≠∅ § ∀a,b∈H, a∗b∈H
Read More >>
  • 1
  • 2
  • 3
  • 4
  • …
  • 6

Search

  • Home Page
  • Tutorials
  • Mathematics
    • Math 240 - Discrete Math
    • Math 375 - Linear Algebra
    • Math 431 - Intro to Probability
    • Math 514 - Numerical Analysis
    • Math 521 - Analysis I
    • Math 541 - Abstract Algebra
    • Math 632 - Stochastic Processes
    • Abstract Algebra @ 万门大学
    • Linear Algebra @ 万门大学
    • Category Theory
  • Computer Sciences
    • CS/ECE 252 - Intro to Computer Engr.
    • CS/ECE 352 - Digital System Fund.
    • Learn Haskell
  • Projects
    • 2048 Game
    • HiMCM 2016
    • 登峰杯 MCM
  • Course Notes
    • AP Macroeconomics
    • AP Microeconomics
    • AP Chemistry
    • AP Statistics
    • AP Physics C: E&M
    • AP Physics C: Mechanics
    • CLEP Psychology

WeChat Account

Categories

  • Notes (418)
    • AP (115)
      • AP Macroeconomics (20)
      • AP Microeconomics (23)
      • AP Physics C E&M (25)
      • AP Physics C Mechanics (28)
      • AP Statistics (19)
    • Computer Sciences (2)
    • Mathematics (300)
      • Abstract Algebra (29)
      • Category Theory (7)
      • Linear Algebra (29)
      • Math 240 (42)
      • Math 375 (71)
      • Math 514 (18)
      • Math 521 (39)
      • Math 541 (39)
      • Math 632 (26)
  • Projects (4)
  • Tutorials (11)

Archives

  • October 2019
  • May 2019
  • April 2019
  • March 2019
  • February 2019
  • December 2018
  • November 2018
  • October 2018
  • September 2018
  • July 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • September 2017
  • August 2017
  • July 2017
  • June 2017

WeChat Account

Links

RobeZH's thoughts on Algorithms - Ziyi Zhang
Copyright © 2018.      
TOP