HW2P5213(1)(5)(7),14,20,21,补充题7。(要交的) EX2-P52-13(2)63)(4),15,17,19。 (不交的练习) 复习P6-13,预习P13-25 dier jiang 重点:1.序关系,偏序集全序集,归纳法原理; 2.一元,二元运算,集的运算规律 3单射,满射,双射,映射的乘积,可逆映射 1-4序关系偏序集全序集数学归纳法原理 集合的元素可按大小、先后、重要性等原则排序 定义1.10 集X中的一个二元关系R称为偏序关系,如 果R具有自反性、反对称性和传递性 偏序关系R常记作<,a<b读作“a小于或等于b”,具有偏序关 系<的集X称为偏序集,记作(X,<)。 例实数集中的≤关系,幂集P(X)中的c关系,自然数集N 中的整除关系“”,都是偏序关系。 在一个集合中,可以定义不同的偏序关系。对于数集 A={1,2,5,6,10,30} (A,≤)和(A,整除)都是偏序集,但二者有所不同,A中任两个元 素a,b都有a≤b或b≤a,A中全部元素可按≤排序,即 1≤2≤5≤6≤10≤30 A中任两个元素未必有a|b或者ba的关系,因此,A只有某些 子集的元素可按整除关系排序。例如A的子集 A1={1,2,6,30} 对整除关系有 6,630 A1可排序为1,2,6,30,对整除关系,A子集 2,6,30},A子集{1,5,10,30}可排序等。 定义1.11设(X,<)是一个偏序集, (1)如果对任意的a,b∈X,均有a-b或b<a,则称(X,<)为全 序集,<为全序关系 (2)如果X的任意非空子集都有最小元a(即对任意的x∈A, 均有a<x),则称(X,<)为良序集。 良序集必是全序集,因为良序集中任两个元素a,b组成的子集 必有a-b或b<a 例(R,≤),(Z,≤)都是全序集,但不是良序集;(N,≤)既是全序 集也是良序集
HW2-P52—13(1)(5)(7), 14， 20, 21, 补充题 7 。(要交的) EX2-P52—13(2)(3)(4), 15，17, 19。 （不交的练习） 复习 P6-13,预习 P13-25 di er jiang 重点：1. 序关系，偏序集 全序集, 归纳法原理; 2. 一元，二元运算, 集的运算规律； 3.单射，满射，双射，映射的乘积，可逆映射. 1-4 序关系 偏序集 全序集 数学归纳法原理 集合的元素可按大小、先后、重要性等原则排序。 定义 1.10 集 X 中的一个二元关系 R 称为偏序关系，如 果 R 具有自反性、反对称性和传递性。 偏序关系 R 常记作，ab 读作“a 小于或等于 b”, 具有偏序关 系的集 X 称为偏序集，记作(X, )。 例 实数集中的 关系，幂集 P(X)中的 关系，自然数集 N 中的整除关系 “”，都是偏序关系。 在一个集合中，可以定义不同的偏序关系。对于数集 A = {1, 2, 5, 6, 10, 30} (A, )和(A,整除)都是偏序集，但二者有所不同， A 中任两个元 素 a, b 都有 a b 或 b a， A 中全部元素可按 排序，即 1 2 5 6 10 30 A 中任两个元素未必有 ab 或者 ba 的关系，因此，A 只有某些 子集的元素可按整除关系排序。例如 A 的子集 A1 = {1, 2, 6, 30} 对整除关系有 12, 26, 630. A1可排序为 1，2，6，30; 对整除关系,A 子集 ｛2，6, 30｝，A 子集｛1，5，10, 30｝可排序等。 定义 1.11 设 (X, ) 是一个偏序集， (1) 如果对任意的 a, b X，均有 ab 或 ba，则称(X, )为全 序集，为全序关系； (2) 如果 X 的任意非空子集都有最小元 a ( 即对任意的 xA , 均有 ax ), 则称(X, ) 为良序集。 良序集必是全序集，因为良序集中任两个元素 a, b 组成的子集 必有 ab 或 ba。 例 (R, ), (Z, )都是全序集，但不是良序集；(N, )既是全序 集也是良序集。 1 10 6 5 2 30
数学归纳法原理的基础是自然数集为良序集 定理1.3假设MN*,如果1∈M,且当n-l∈M时,可推 出n∈M,则M=N*。 证反证法:设M=N*\M≠⑧,则1gM,由于McN*,所 以M必有最小数a∈M于是a>1,a-1∈M,即a-1∈M,如此由 定理假设又得a∈M,这与agM矛盾。故M=⑦,即M=N* 因此,要证明一个命题对所有自然数成立,只需证明:(1)命题 对n=1成立;(2)若命题对k-1成立,则命题对k也成立。这就是 通常的数学归纳法。 第二数学归纳法原理 设P(n)是与自然数N*有关的一个命题,如果 (1)P(n)对n=1成 (2)假设P(n)对任意的nY, 并称β为a在σ下的象,a为β在σ下的一个原象,记作 σ:aP>β,或σ(a)=β. 称X为σ的定义域,并把ⅹ中全体元素在σ下的象的集合称为 σ的值域,或称σ的象,记作σ(X)或Imσ,即 (X)={o(a)a∈X}
数学归纳法原理的基础是自然数集为良序集. 定理 1.3 假设 MN*，如果 1M，且当 n−1M 时，可推 出 nM，则 M=N*。 证 反证法：设 M#= N* \ M ，则 1 M#，由于 M#N*, 所 以 M#必有最小数 a M,于是 a 1, a−1 M#，即 a−1M，如此由 定理假设又得 a M，这与 a M 矛盾。故 M#= ，即 M = N*。 因此，要证明一个命题对所有自然数成立，只需证明：(1)命题 对 n=1 成立；(2)若命题对 k −1 成立，则命题对 k 也成立。这就是 通常的数学归纳法。 第二数学归纳法原理 设 P(n)是与自然数 N*有关的一个命题，如果: (1) P(n)对 n=1 成立； (2) 假设 P(n)对任意的 n k 成立，则 P(n)对 n = k 也成立， 那末命题 P(n)对一切自然数 n 都成立。 证 设命题 P(n)对 N*的非空子集 M 不成立，令 M 的最小数为 a，由条件(1)知 a 1,而且 a − j M (j=1, 2,, a−1)，因此根据假设， 命题 P(n)对小于 a 的一切自然数都成立，于是由条件(2)知，命题 对 a 成立，这与 a M(即命题对 a 不成立)矛盾。故命题对一切自 然数都成立。 1-5 运 算 与 映 射 一个数的运算：乘方，开方, 倒数，对数和三角函数； 两个数的运算+，−, , , 最大公因数(a,b) , 最小公倍数 [a,b] , 平均值 (a+b)/2 , 最大值 max(a, b ) , 最小值 min(a ,b ) 等，都是由 一个或两个数按一定规则确定另一个数（一元运算或二元运算）。 集 X 的子集 A B, A B 是幂集 P(X)中的“运算”。 定义 1.12 设 X, Y, Z 都是非空集，定义在 X, Y 上取值于 Z 的 二元运算“。”是一个法则， 指： xX 和yY 都有唯一的 zZ 与之对应，记作 xy = z。如果 X=Y=Z，则称这个二元运算为 X 上 的一个代数运算，或说 X 上的二元运算是封闭的。 定义 1.13 设 X, Y 是非空集，定义在 X 上取值于 Y 的一元运 算 是一个法则, 它使 X 中每个元素 都有 Y 中唯一确定的元 素 与之对应。这个一元运算 也称为集合 X 到 Y 的一个映射， 记作 : X→ Y, 并称 为 在 下的象， 为 在 下的一个原象，记作 ： , 或 () = . 称 X 为 的定义域，并把 X 中全体元素在 下的象的集合称为 的值域，或称 的象，记作 (X) 或 Im，即 (X) = { ()X}
X到它自身的映射,有时也称为X的变换。 注意,a的象是唯一的,但β的原象不一定是唯一的。 例1设a,an…,ahn∈A,则max{a,a,,an}是取值于A的n元 运算 例2设R是实数集,对任意的a,b∈R,定义 ab=(a,b)∈R×R 则“。”是定义在R上取值于R×R的一个二元运算,也称它为“笛 卡尔乘积”,一般a∞b≠ba 例3自动售货机售货问题 自动售货机能接受币值为a,b的硬币,投入任两枚这种硬币, 它按下表出售商品。 *ab 桔子水一瓶糖一包 糖一包 冰淇淋一杯 即,a*a=桔子水一瓶,b*b=冰淇淋一杯,a*b=b*a=糖一包 这可视为定义在硬币集{a,b}上取值于食品集{桔子水,糖。冰 淇淋}的一个二元运算。 例4开关电路一逻辑运算 在图1-1中,两个开关K,K2的开,关都确定了电路S的导通 和不通中的一种状态。这就是集{K1K2}上的一个二元运算。“0 电路“通”,“1”-“不通”, 开关串联,“√”--并联, 图1-1 1∧1=1,1v1=lv0=0v1=1,表示S导通 1∧0=0A1=0A0=0,0V0=0,表示S不通。 ∧”:逻辑乘or“与”运算;“√”:逻辑加or“或”运算。“∧”,“√”-” 运算统称为逻辑运算,是布尔代数中的基本运算。 例5设P(X)是集X的幂集,A,B∈P(X),则 AUB,A∩B,AB, 都是P(X)上的二元运算,A是P(X)上的一元运算。集合的交、并、 余(或差)三种运算适合以下运算律: (1)A∪B=B∪A,A∩B=B∩A;(交换律) (2)(AUB)∪C=A∪(B∪C);(A^B)∩C=A∩(B⌒C);(结合律) (3)A∩(BC)=(A∩B)∪(A⌒C);A∪(B∩C)=(A∪B)∩ (A∪C);(分配律)
X 到它自身的映射，有时也称为 X 的变换。 注意， 的象是唯一的，但 的原象不一定是唯一的。 例 1 设 a1, a2,, anA,则 max{ a1, a2,, an }是取值于 A 的 n 元 运算 例 2 设 R 是实数集，对任意的 a, b R，定义 ab = ( a, b ) RR 则“”是定义在 R 上取值于 RR 的一个二元运算，也称它为“笛 卡尔乘积”，一般 abba。 例 3 自动售货机售货问题 自动售货机能接受币值为 a, b 的硬币，投入任两枚这种硬币， 它按下表出售商品。 * a b a 桔子水一瓶 糖一包 b 糖一包 冰淇淋一杯 即，aa = 桔子水一瓶，bb = 冰淇淋一杯，ab = ba = 糖一包。 这可视为定义在硬币集 {a, b} 上取值于食品集 {桔子水，糖。冰 淇淋} 的一个二元运算。 例 4 开关电路 — 逻辑运算 在图 1-1 中，两个开关 K1, K2的开，关都确定了电路 S 的导通 和不通中的一种状态。这就是集{K1, K2}上的一个二元运算。“0” -----电路“通”, “1”------“不通”， “”-----开关串联, “”------并联， K1 K2 0 0 0 0 K 1 K 2 0 0 0 0 图 1-1 1 1 = 1 , 11 = 1 0 = 0 1 = 1 , 表示 S 导通； 10 = 0 1 = 0 0 = 0 , 0 0 = 0 , 表示 S 不通。 “”:逻辑乘 or“与”运算；“”：逻辑加 or“或”运算。“”,“””” 运算统称为逻辑运算，是布尔代数中的基本运算。 例 5 设 P(X)是集 X 的幂集，A, B P(X) , 则 AB , AB , A\B , 都是 P(X)上的二元运算; A 是 P(X)上的一元运算。集合的交、并、 余(或差)三种运算适合以下运算律： (1) AB = BA , AB = BA；（交换律） (2) (AB) C = A (BC) ; (AB) C = A (BC) ; (结合律) (3) A (BC) = (AB) (AC) ; A (BC) = (AB) (AC) ; (分配律)
(4)AU=A;A∩X=A;(恒等律) (5)A∩=,A∪X=X;(零律 (6)A∪A=X,A∩A=②;(互补律 (7)A=A;(否定律) (8)A∪B=A∩B,A∩B=A∪B;( DeMorgan律) (9)AB=A∩B 这些运算律可用运算的定义作推理证明,也可画图证明。 (A∩B)∪(A⌒C),(A∪B)∩(A∪C) A∪B=A∩B.A∩B=AUB 例证明AOB=A∪B 设x∈A∩B,则xEA∩B,即x不同属于A,B,所以xgA或xEB, 从而ⅹ∈A或x∈B,即ⅹ∈AB,故 AoBcA∪B;反之,若 x∈A∪B,则x∈A或x∈B,所以x∈A∩B,即x∈AB,故 AUBCAOB; 于是A∪B=AAB 例证明∩4=UA。 WxE∩4→x∩4→310(15b5m)xEA,x∈A→x∈∪4 所以左式c右式,上式步骤可逆,右式c左式,即等式成立。 下面介绍单射(内射)、满射和双射,映射的相等、乘法(或称合 成)运算,映射可逆的充要条件。 例1定义在(-∞,+∞)上的一元实单值函数y=f(x)是实数 集R到自身的映射 例2设A={a,b,c},B={1,2,3,4},定义 f: aH1, bH4, Ch1; g: aH3, bh1 则f是A到B的映射,但g不是A到B的映射,只是A的子集X ={a,b}到B的映射。 b
(4) A = A ; AX = A ; (恒等律) (5) A = , AX = X; (零律) (6) A A = X, A A = ; (互补律) (7) A = A ; (否定律) (8) AB = AB, AB = AB ; (DeMorgan 律) (9) A\B=A B 这些运算律可用运算的定义作推理证明，也可画图证明。 A B C A B C A B (AB) (AC)， (AB) (AC) A B = A B, A B = A B 例 证明 AB = AB . 设 x AB , 则 xAB,即 x 不同属于 A, B，所以 xA 或 xB， 从而 x A 或 x B ，即 x AB ，故 AB AB ; 反之，若 x AB ，则 xA 或 xB，所以 xAB，即 x AB ，故 AB AB ; 于是 AB = AB. 例 证明 n i i n i Ai A =1 =1 = 。 (1 ), , . 1 0 0 1 1 0 0 n i i i i n i i n i x Ai x A i i n x A x A x A = = = 所以左式右式，上式步骤可逆，右式左式，即等式成立。 下面介绍单射(内射)、满射和双射，映射的相等、乘法(或称合 成)运算，映射可逆的充要条件。 例 1 定义在 (−, +) 上的一元实单值函数 y = f (x) 是实数 集 R 到自身的映射。 例 2 设 A={ a, b, c }, B={ 1, 2, 3, 4 }, 定义 f : a 1, b4, c1; g : a3, b1; 则 f 是 A 到 B 的映射，但 g 不是 A 到 B 的映射，只是 A 的子集 X = { a, b } 到 B 的映射。 a 1 a 1 b 2 b 2
3 4 例3设X某班学生集,M月份集,每个人对应于他的生日月 份是ⅹ到M的一个映射。|x|>12,至少有两个人的生日对应于 同一个月份。这就是所谓的狄里克莱( Dirichlet)抽屉原理(或称鸽 舍原理) 定义1.14设σ是X到Y的一个映射,如果 (1)对任意的a,a2∈X,当α1≠α2时,o(a)≠(a2),则 称σ为单射(内射, Injection (2)σ(X)=Y,即对于任意的β∈Y,存在α∈X,使σ(a)=β 则称σ为满射(映上的, Surjection); (3)σ既是单射又是满射,则称σ为双射(一一对应 Bijection) (4)va∈X,,I(a)=a),称映射I为Ⅹ上的恒等映射。 有限集到有限集的映射的三种情况,可用下图示意。 单射(不满) 满射(不单) 双射 定义1.15如果σ,τ都是Ⅹ→Y的映射,且对任意的a∈X,o(ax) =τ(a),则称σ=t 定义1.16设G和τ分别是集合A到B和B到C的两个映射, 我们规定其乘积 (τo)=t(o() ∈A 显然τ是集合A到C的一个映射 对于集X到Y的任一个映射σ,显然有 IYG=σIx=σ 其中Ix和I分别是X和Y的恒等映射单位映射) 映射的乘法满足结合律, 映射G:A→B,τ:B→o v(τo)=(v 是A→D的映射,而且对任意的a∈A,均有 v(τo)(α)=v[(to)(a)=v[τ(o(a)=(vτ)o(a)=[(vyo](a) 因此,v(o)=(vτ)成立
c 3 c 3 4 4 例 3 设 X:某班学生集，M:月份集，每个人对应于他的生日月 份是 X 到 M 的一个映射。X>12，至少有两个人的生日对应于 同一个月份。这就是所谓的狄里克莱 (Dirichlet) 抽屉原理(或称鸽 舍原理)。 定义 1.14 设是 X 到 Y 的一个映射，如果: (1) 对任意的 1 , 2 X，当 1 2 时， (1) ( 2)，则 称为单射(内射，Injection) ; (2) (X) = Y, 即对于任意的 Y，存在 X, 使 () = , 则称为满射(映上的，Surjection ) ; (3) 既是单 射又是 满射 ，则称 为双 射 (一一 对应， Bijection)。 (4) X, , I() =)，称映射 I 为 X 上的恒等映射。 有限集到有限集的映射的三种情况，可用下图示意。 X ⎯⎯ → Y X ⎯⎯ → Y X ⎯⎯ → Y 单射（不满） 满射（不单） 双射 定义 1.15 如果,都是 X→Y 的映射，且对任意的 X , () = ()，则称= . 定义 1.16 设和 分别是集合 A 到 B 和 B 到 C 的两个映射， 我们规定其乘积 ()() = ( ()), A . 显然是集合 A 到 C 的一个映射。 对于集 X 到 Y 的任一个映射，显然有 IY = IX ＝ 其中 IX 和 IY 分别是 X 和 Y 的恒等映射(即单位映射)。 映射的乘法满足结合律， 映射 ：A→B , ：B → C , ： C→D，则 () = () 是 A→D 的映射，而且对任意的 A，均有 [()]()=[()()]=[( ())]=()( ())=[()]() , 因此， ()=()成立。 () C B A A D
乘法不满足交换律,例如,f(x)=tanx,g(x)=2+3x,则 g(f(x)=2+tan x f(g(x))tan(2+3x) 定义1.17设σ是集X到Y的一个映射,如果存在集Y到X 的一个映射τ,使 和 同时成立,则称σ是可逆映射(简称σ可逆),并称τ为o的逆映射 记作σ-1=τ.且τ可逆,且τl=o 如果映射是可逆的,则其逆映射是唯一的。事实上,如果τ1 和v2是o的两个逆映射,即 τG=τ2G=Ix且τ1=0τ2=I 则有 τ=TIy=t(oτ2)=(τ)t2=Ixt2=τ2 故σ的逆映射是唯一的。 定理1.4集X到Y的映射G可逆的充要条件是σ为双射。 证条件是必要的:设σ可逆,即有唯一的τ:Y→X,使 Ix且στ=Iy σ是满射:Vβ∈Y,β=IY(B)=(oτ)β)=σ(τ(B),3a=t(B)∈X 使得σ(a)=β σ是单射:若o(a1)=G(a2) a1=Ix(an)=r(o(1))=(o(a2)=lx(a2)=2;故σ是双射。 条件是充分的:当σ为双射时 β∈Y,彐唯一的a∈X,使σ(αx)=β,定义τY→X,使τ(β)=a, a∈X (ro)(a)=(o(a)=τ(β)=a即τo=I Vβ∈Y,(oτβ)=o(τ(β)=o(a)=β即στ=IY 因此σ是可逆的。 B 定义1.18设σ:X→Y,BCY, G-(B)={aa∈X且o(a)∈B}cX 称为B在σ下的完全原象(或逆象)(记号σ-(β)不意味着映射σ是可 逆的),当B={B}时,(B)表示β在X中的所有原象的集合 σ不是满射,有可能σ-1(β)为空集; σ不是单射,3β∈Y,使σ1(β)至少包含两个元素 σ是双射,Vβ∈Y,集合1(B)都只包含Ⅹ中的一个元素
乘法不满足交换律，例如，f (x) = tan x, g (x) = 2+ 3x, 则 g (f (x))=2+3tan x ; f(g (x))=tan (2+3x) 故 gf fg . 定义 1.17 设是集 X 到 Y 的一个映射，如果存在集 Y 到 X 的一个映射 ，使 = IX 和 = IY 同时成立，则称是可逆映射(简称可逆)，并称 为的逆映射， 记作 −1=. 且可逆，且 −1=. 如果映射是可逆的，则其逆映射是唯一的。事实上，如果 1 和 2 是的两个逆映射，即 1= 2= IX 且 1 =2 = IY , 则有 1= 1 IY =1 (2)= (1) 2 = IX 2＝2 故的逆映射是唯一的。 定理 1.4 集 X 到 Y 的映射可逆的充要条件是为双射。 证 条件是必要的：设可逆，即有唯一的 : Y→X，使 = IX 且 = IY 是满射： Y , = IY( ) = ()() = ( ()) , =() X ； 使得 ()=; 是单射：若 (1 ) = (2) , 1 = IX (1) = ( (1)) = ( (2)) = IX (2) = 2；故是双射。 条件是充分的：当为双射时， Y，唯一的 X, 使 ()＝，定义 :Y→X，使 () = ， X ， ()() = ( ()) = () = 即 = IX； Y， ()() = (()) = () = 即 = IY 因此是可逆的。 −1 (B) B 定义 1.18 设：X→Y， BY， X Y −1 (B)= { X 且 ()B} X 称为 B 在下的完全原象(或逆象)（记号 −1 ()不意味着映射是可 逆的）,当 B = {}时， −1 () 表示 在 X 中的所有原象的集合。 不是满射, 有可能 −1 ()为空集; 不是单射， Y，使 −1 () 至少包含两个元素； 是双射， Y，集合 −1 ()都只包含 X 中的一个元素。
