等价关系（4学时）
【教学目的】
了解、掌握等价关系及相应的等价类与集合划分的基本概念及例子
【教学要求】
正确地掌握等价关系及相应的等价类与集合划分之间的关系；给定A 上的等价关系R ，会求所有的等价类和商集A/R，或者求与R 相对应的划分；反之给定集合A 上的划分π，求对应于π的等价关系
【教学重点】
等价关系、偏序关系的各种性质的判断和证明；
【教学难点】
如何正确地掌握等价关系及相应的等价类与集合划分之间的关系
【教学方法】
讲练结合教学法、提问式与启发式相结合教学法。
【教学手段】
传统板书与多媒体课件辅助教学相结合。
【课型】新授课
教学过程
4.1一种特殊的二元关系——等价关系(Equivalence Relation).
一、等价关系(Equivalence Relation)
1、定义4.18 设R 为非空集合上的关系. 如果R 是自反的、对称的和传递的, 则称R 为A 上的等价关系. 设R 是一个等价关系, 若∈R, 称x 等价于y, 记作:x ~ y. 例4.17 设A = { 1, 2, …, 8 }, 如下定义A 上的关系R:
R = { | x, y∈A ∧x ≡y （mod 3） }
其中x ≡y （mod 3）是x 与y 模3.
不难验证R 为A 上的等价关系, 因为:
∀x ∈A , 有: x≡x （mod 3）
∀x,y ∈A, 若x ≡y （mod 3）, 则有: y≡x （mod 3）
∀x,y,z ∈A, 若x ≡y （mod 3）, y≡z （mod 3）, 则有: x≡z. （mod 3） 该关系的关系图如右图所示.
不难看到, 上述关系图被分为三个互不连通的部分. 每部分中的数两两都有关系. 不同部分中的数则没有关系, 每一部分中的所有的顶点构成一个等价类.
4.2等价关系与划分
2、定义4.19 设R 为非空集合A 上的等价关系, ∀x ∈A, 令
[x]R = { y | y∈A ∧xRy }
称[x]R为x 关于R 的等价类(Equivalent Class), 简称为x 的等价类, 简记为[x]. 从以上定义可以知道, x的等价类是A 中所有与x 等价的元素构成的集合.
例4.17中的等价类是:
[1] = [4] = [7] = { 1, 4, 7 }
[2] = [5] = [8] = { 2, 5, 8 }
[3] = [6] = { 3, 6 }
关于等价类，有如下性质：
定理4.8 设R 为非空集合A 上的等价关系, 则
(1) ∀x ∈A, [x]是A 的非空子集;
(2) ∀x,y ∈A, 若∈R, 则[x] = [y];
(3) ∀x,y ∈A, 若∉R, 则[x]与[y]不交;
(4) ∪{ [x] | x∈A } = A.
证 (1) 由等价类的定义可知, ∀x ∈A, 有: [x] ⊆ A.
由“等价关系的自反性”可知: x∈[x], 即: [x]非空.
(2) 任取z, 则有
z ∈[x] → ∈R → ∈R (因为R 是对称的)
因此有
∈R ∧∈R → ∈R (因为R 是传递的)
→ ∈R (因为R 是对称的)
从而证明了z ∈[y].综合上述, 必有: [x] ⊆ [y].
同理可证: [x] ⊆ [y].这就得到了: [x] = [y].
(3) 假设: [x]∩[y] ≠ φ.
由假设可知: ∃z ∈[x]∩[y], 即: z∈[x]∧z ∈[y].
所以, ∈R 和∈R.
由“R 的对称性”和“∈R ”可知: ∈R.
再由R 的对称性可得: ∈R.
这就与“已知条件: ∉R ”相矛盾.
所以, 命题成立, 即: [x]∩[y] = φ.
(4) 先证: ∪{ [x] | x∈A } ⊆ A
证:
(4.1) 任取y,
y ∈∪{ [x] | x∈A }
⇒ ∃x(x∈A ∧y ∈[x])
⇒ y∈A
从而有: ∪{ [x] | x∈A } ⊆ A
再证: A ⊆ ∪{ [x] | x∈A }.
(4.2) 任取y,
y ∈A ⇒ y∈[y]∧y ∈A
⇒ y∈∪{ [x] | x∈A }
从而有: A⊆∪{ [x] | x∈A }成立.
综合上述得: ∪{ [x] | x∈A } = A.
3、定义4.20 设R 为非空集合A 上的等价关系, R所有等价类所组成集合称为A 关于R 的
商集, 记作A/R, 即: A/R ＝ {[x]R |（一切x ∈A ）}
例4.17中的商集为: { {1, 4, 7 }, { 2, 5, 8 }, { 3, 6 } }.
和等价关系及商集有密切联系的概念是集合的划分.
定义7.18 设A 为非空集合, 若A 的子集族π(π ⊆ P(A)), 是A 的子集构成的集合) 满足下面的条件: (1) φ∉π
(2) ∀x ∀y(x, yπ∈ ∧x ≠ y ◊ x∩y = φ)
(3) ∪π = A
则称π是A 的划分(Partition), 称π中的元素为A 的划分块.
例7.17 设A = { a, b, c, d }, 给定π1, π2, π3, π4, π5和π6, 如下:
π1 = { { a, b, c }, { d } }
π2 = { { a, b }, { c }, { d } }
π3 = { { a }, { a, b, c, d } }
π4 = { { a, b }, { c } }
π5 = { φ, { a, b }, { c, d } }
π6 = { { a, { a } }, { b, c, d } }
解答：π1是A 的划分; π2是A 的划分
不是A 的划分, π3中的子集中有公共元素a; 不是A 的划分, ∪π4 ≠ A
不是A 的划分, π5中含有空集; 不是A 的划分, π6根本不是A 的子集族
商集是A 的一个划分, 并且不同的商集将对应于不同的划分. 任给A 的一个划分π, 定义A 上的关系R 如下:
R = { | x, y∈A ∧x 与y 在π的同一划分块中 }
不难证明: R为A 上的等价关系, 且该等价关系所确定的商集就是π, 因此, A上的等价关系与A 的划分是一一对应的.
即给定集合A 上的一个等价关系R ，由R 可以唯一产生集合A 的一个划分π＝A/R，反之，对集合A 的任一划分π ＝ {A1,A 2, „,A k }，可唯一对应集合A 上的一等价关系R ＝（A 1×A 1）∪（A 2×A 2）∪„∪（A k ×A k ）。
例4.20 给出A = { 1, 2, 3 }上所有的等价关系.
解 如下图, 先做出A 的所有划分.
这些划分与A 上的等价关系之间的一一对应是: π1对应全域关系EA, π5对应恒等关系IA, π2, π3和π4分别对应于等价关系R2, R3和R4, 其中:
R2 = { , } U IA
R3 = { , } U IA
R4 = { , } U IA
【教学目的】
了解偏序关系的基本概念及例子；给定A 上的偏序关系≤，画出偏序集的哈斯图，反之给定偏序集的哈斯图，求A 和≤的集合表达式；确定偏序集的的任意非空子集B 的最大元，最小元，极大元，极小元，上界，下界，上确界，下确界。
【教学要求】
掌握偏序关系的有关基本概念；理解和判断偏序关系的八种特殊元素。
【教学重点】
偏序关系的各种性质的判断和证明；
【教学难点】
如何正确的理解和判断偏序关系的八种特殊元素。
【教学方法】
讲练结合教学法、提问式与启发式相结合教学法。
【教学手段】
传统板书与多媒体课件辅助教学相结合。
【课型】新授课
教学过程
课题导入
下面介绍另一种重要的关系——偏序关系.
定义4.22 设R 为非空集合A 上的关系. 如果R 是自反的、反对称的和传递的, 则称R 为A 上的偏序关系, 记作≤.
设为偏序关系, 如果∈≤, 则记作x ≤ y, 读作“小于或等于”.
注意: 这里的“小于或等于”不是指数的大小, 而是在偏序关系中的顺序性.
x “小于或等于”y 的含义是: 依照这个序, x排在y 的前边或者x 就是y.
不同偏序的定义有不同的序解释.
例如整除关系是偏序关系, 3 ≤ 6的含义是3整除6; 大于或等于关系也是偏序关系, 针对这个关系写5 ≤ 4是说大于或等于关系中5排在4的前边, 也就是5比4大.
定义4.23 设R 为非空集合A 上的偏序关系, 定义
(1) ∀x, y∈A, x
(2) ∀x, y∈A, x与y 可比 ⇔ x ≤ y∨y ≤ x.
其中: x
有以上两个定义可知: 在具有偏序关系的集合A 中任取两个元素x 和y, 可能有下述几种情况发生:
x
例如: A = { 1, 2, 3 }, ≤是A 上的整除关系, 则有:
1
1 = 1, 2 = 2, 3 = 3,
2和3不可比.
定义4.24 设R 为非空集合A 上的偏序关系, 如果R 是反自反的、反对称的和传递的, 则称R 为A 上的拟序关系，简称为拟序，记作
定义4.25 设R 为非空集合A 上的偏序关系, 如果x, y∈A, x与y 都是可比的, 则称R 为A 上的全序关系(或线序关系).
例如: 数集上的小于等于关系是全序关系, 因为任何两个数总是可比大小的.
一般来说, 整除关系不是全序关系. 如: 集合{ 1, 2, 3 }上的整除关系就不是全序关系, 因为2和3不可整除.
定义7.22 集合A 和A 上的偏序关系一起叫做偏序集, 记作
.
例如: 整数集合Z 和数的小于等于关系≤构成偏序集
, 集合A 的幂集P(A)和包含关系R 构成偏序集
.
利用偏序关系的自反性、反对称性和传递性可简化偏序关系的关系图, 该关系图称为哈斯图(Hasse Diagram).
为了说明哈斯图的画法, 先定义偏序集中顶点之间的覆盖关系.
定义7.23 设为偏序集, ∀x,y ∈A, 如果x
例如: { 1, 2, 4, 6 }集合上的整除关系, 有2覆盖1, 4和6都覆盖2. 但, 4不覆盖1, 因为有1
在画偏序集的哈斯图时, 首先适当排列顶点的顺序, 使得: ∀x,y ∈A,
若x
对于A 中的两个不同元素x 和y, 如果y 覆盖x, 就用一条线段连接x 和y.
例4.22 画出偏序集和
的哈斯图. 解 两个哈斯图如右图所示.
}
{a,b }
{a }
ф
例4.23 已知偏序集的哈斯图如下图, 试求出集合A 和关系R 的表达式.
b,c } c }
A = { a, b, c, d, e, f, g, h }
R = { , , , , , , , , } ∪ IA
下面考虑偏序集中的一些特殊元素.
定义4.28 设为偏序集, B⊆A, y∈B.
(1) 若∀x(x∈B →y ≤x) 成立, 则称y 为B 的最小元;
(2) 若∀x(x∈B →x ≤y) 成立, 则称y 为B 的最大元;
(3) 若∀x(x∈B ∧x ≤y →x=y)成立, 则称y 为B 的极小元;
(4) 若∀x(x∈B ∧y ≤x →x=y)成立, 则称y 为B 的极大元.
从以上定义可以看出: 最小元与极小元是不一样的.
最小元是B 中最小的元素, 它与B 中其它元素都可比;
极小元不一定与B 中元素都可比, 只要没有比它小的元素, 它就是极小元.
对于有穷集B, 极小元一定存在, 而且还可能有多个.
最小元不一定存在, 若存在, 则它一定是唯一的.
若B 中只有一个极小元, 则它一定是B 的最小元.
类似的, 极大元与最大元也有这种区别.
例7.21 设偏序集如下图所示, 求A 的极小元, 最小元, 极大元, 最大元.
解 极小元: a, b, c, g.
极大元: a, f, h.
没有最小元与最大元.
由这个例子可以知道, 哈斯图中的孤立顶点既是极小元也是极大元.
定义7.25 设为偏序集, B⊆A, y∈A.
(1) 若∀x(x∈B →x ≤y) 成立, 则称y 为B 的上界;
(2) 若∀x(x∈B →y ≤x) 成立, 则称y 为B 的下界;
(3) 令C = { y | y为B 的上界 }, 则称C 的最小元为B 的最小上界或上确界;
(4) 令D = { y | y为B 的下界 }, 则称D 的最大元为B 的最大下界或下确界
;
由上面定义可知:
B 的最小元一定是B 的下界, 同时也是B 的最大下界;
B 的最大元一定是B 的上界, 同时也是B 的最小上界.
反过来不一定正确, B 的下界不一定是B 的最小元, 因为它可能不是B 中的元素, B 的上界也不一定是B 的最大元.
B 的上界, 下界, 最小上界, 最大下界都可能不存在. 如果存在, 最小上界与最大下界是唯一的.
4良序集
若是偏序集，对A 的任何一个非空子集都有最小元，则“≤”称为良序关系，称为良序集。
“≤”是良序关系⇒“≤”是全序关系⇒“≤”是偏序关系。
【教学目的】
熟练掌握函数的基本概念，函数的复合运算，逆运算的计算
【教学要求】
给定f 是从集合A 到B 的二元关系，判断f 是否为从A 到B 的函数f ：A →B ，若是，要能用按定义证明法证明f ：A →B 是否为单射，满射，双射；熟练掌握函数的复合运算，逆运算的计算
【教学重点】
函数的各种性质的判断和证明；
【教学难点】
如何正确地判断三种特殊函数
【教学方法】
讲练结合教学法、提问式与启发式相结合教学法。
【教学手段】
传统板书与多媒体课件辅助教学相结合。
【课型】新授课
教学过程
函数(Function)是一种特殊的二元关系.
5.1 函数的定义与性质
定义5.1 设f 为二元关系, 若∀x ∈domf, 都存在唯一的y ∈ranf, 使xfy 成立, 则称f 为函数(或映射).
对于函数f, 如果有xfy, 则记作y=f(x), 并称y 为f 在x 的值.
由于函数是集合, 可用集合相等来定义函数的相等.
定义5.2 设F 和G 为函数, 则, F=G ⇔ F⊆G ∧G ⊆F .
由以上定义可知, 如果两个函数F 和G 相等, 一定满足下面两个条件:
1). domF = domG
2). ∀x ∈domF = domG, 都有: F(x) = G(x)
例如: 函数F(x) = (x2-1)/(x+1), G(x) = x-1是不相等的, 因为 domF = { x | x ∈R ∧x ≠ -1 } , domG = R.
定义5.3 设A 和B 为集合, 如果f 为函数, 且domf = A, ranf⊆B, 则称f 为从A 到B 的函数, 记作f:A→B.
例如 f:N→N, f(x) = 2x是从N 到N 的函数,
g:N→N, g(x) = 2也是从N 到N 的函数.
定义5.4 所有从A 到B 的函数的集合记作BA, 读作“B 上A ”. 符号化表示为B = { f | f: A→B }.
例5.2 设A = { 1, 2, 3 }, B = { a, b }, 求B .
解 B = { f0, f1,„, f7 }, 其中
f0 = { , , } f1 = { , , } f2 = { , , } f3 = { , , } f4 = { , , } f5 = { , , } f6 = { , , } f7 = { , , } 由排列组合知识不难证明: 若|A| = m, |B| = n, 且m, n > 0, 则|BA| = nm. 在例5.2中, |A| = 3, |B| = 2, 所以, |BA| = 23 = 8.
当A 或B 中至少有一个集合是空集时, 可以分成下面三种情况:
1). A = φ且B = φ, 则BA = φφ = { φ }.
2). A = φ且B ≠ φ, 则BA = Bφ = { φ }.
3). A ≠ φ且B = φ, 则BA = φA = φ.
5.1.2函数的像与完全原像.
定义5.6 设函数f: A→B, A1 ⊆ A, B1 ⊆ B.
(1) 令f(A1) = { f(x) | x∈A1 }, 称f(A1)为A1在f 下的像. 特别的, 当A1=A时称f(A)为函数的像.
(2) 令f-1(B1) = { x | x∈A ∧f(x)∈B1 }, 称f-1(B1)为B1在f 下的完全原像.
这里需区别: 函数的值和像. 函数值f(x)∈B, 而
像f(A1) ⊆ B.
假设: B1 ⊆ B, 显然, B1在f 下的完全原像 f-1(B1)是A 的子集.
考虑A1 ⊆ A, 那么, f(A1) ⊆ B.
f(A1)的完全原像就是f-1(f(A1)).
一般有: f-1(f(A1)) ≠ A1, A1 ⊆ f-1(f(A1)).
例如: 函数f: { 1, 2, 3 }→{ 0, 1 }, 满足: f(1)=f(2)=0, f(3)=1
令A1 = { 1 }, 那么, 有:
f-1(f(A1)) = f-1(f({1})) = f-1({0}) = { 1, 2 }
这时, A1 ⊂ f-1(f(A1)).
例8.3 设f: N→N, 且 A A A
⎧x /2若x 为偶数f (x ) =⎨⎩x +1若x 为奇数
假设: A1 = { 0, 1 }, B1 = { 2 }, 那么, 有
f(A1) = f({0,1}) = { f(0), f(1) } = { 0, 2 }
f-1(B1) = f-1({2}) = { 1, 4 }
下面讨论函数的性质.
定义5.7 设f: A→B,
(1) 若ranf = B, 则称f: A→B 是满射的(Onto);
(2) 若∀y ∈ranf, 都存在唯一的x ∈A, 使得:
f(x) = y, 则称f: A→B 是单射的(One-to-one);
(3) 若f 既是满射又是单射, 则称f 是双射的(或一一映射)(One-to-one Correspondence).
由定义不难看出:
若f: A→B 是满射的, 则对于∀y ∈B, 都存在x ∈A, 使得: f(x) = y;
若f: A→B 是单射的, 则对于∀x1, x2∈A, x1 ≠ x2, 一定有: f(x1) ≠ f(x2);
若∀x1, x2∈A, 有: f(x1) = f(x2), 则有: x1 = x2.
例5.4 判断下面函数是否为单射, 满射, 双射的, 为什么?
(1) f: R→R, f(x) = -x2+2x-1
(2) f: Z+→R, f(x) = lnx, Z+为正整数集
(3) f: R→Z, f(x) = ⎣x ⎦
(4) f: R→R, f(x) = 2x+1
(5) f: R+→R+, f(x) = (x2+1)/x, 其中R+为正实数集.
解
(1) f: R→R, f(x)是开口向下的抛物线, 非单调函数, 并且在x = 1点取得极大值0, 它既不是单射, 也不是满射的;
(2) f: Z+→R, f(x)是单调上升, 单射, 但不是满射的, 因为ranf = { ln1, ln2, „ } ⊂ R;
(3) f: R→Z, f(x)是满射的, 不是单射的, 例如: f(1.5) = f(1.2) = 1;
(4) f: R→R, f(x) = 2x+1是双射的;
(5) f: R+→R+, f(x) = (x2+1)/x不是单射的, 也不是满射的.
当x →0+时, f(x)→+∞;
当x →+∞时, f(x)→+∞;
在x = 1处函数f(x)取得极小值f(1) = 2.f(2) = f(1/2) = 2.5.
例5.5 对于以下各题给定的A 、B 和f, 判断是否构成函数f:A→B. 如果是, 说明f: A→B 是否为单射, 满射, 双射的, 并根据要求进行计算.
(1) A = {1,2,3,4,5}, B = {6,7,8,9,10}, f = {,,,,}
(2) A,B同(1), f = { , , , , }
(3) A,B同(1), f = { , , , }
(4) A = B = R, f(x) = x3
(5) A = B = R+, f(x) = x/(x2+1)
(6) A=B=R ⨯ R, f()=, 令L={|x,y∈R ∧y=x+1}, 计算f(L)
(7) A = N ⨯ N, B = N, f() = |x2-y2|.计算f(N ⨯ {0}), f-1({0})
解 (1) 能.f: A→B 既不是单射, 也不是满射.
(2) 不能.∈f 和, 与函数定义矛盾.
(3) 不能. 因为domf = {1,2,3,4} ≠ A.
(4) 能.f: A→B 是双射的.
(5) 能.F: A→B 既不是单射, 也不是满射的. 因为该函数在x=1取得极大值f(1)=1/2.函数不是单调的, 且ranf ≠ R+.
(6) 能.F: A→B 是双射的.
f(L) = { | x∈R } = R ⨯ {-1}
(7) 能.F: A→B 既不单射, 也不满射. 因为f() = f() = 0, 且2∉ranf. f(N ⨯ {0}) = {n2-02 | n∈N} = {n2 | n∈N},
f-1({0}) = { | n∈N}.
下面定义一些常用的函数.
定义8.7
(1) 设f:A→B, 若∃y ∈B, ∀x ∈A, 都有: f(x) = y, 则称f:A→B 是常函数;
(2) ∀x ∈A, 都有: IA(x) = x, 称恒等关系IA 为A 上的恒等函数;
(3) 设和为偏序集, f: A→B
∀x1, x2∈A, 若x1
∀x1, x2∈A, 若x1
类似的也可以定义单调递减和严格单调递减的函数
(4) 设A 为集合, 对于任意的A ’ ⊆ A, A’的特征函数(Characteristic Function)XA’: A→{0,1}定义为(读: Kai) a ∈A ' ⎧1χ(a ) =⎨ ⎩0a ∈A -A '
(5) 设R 是A 上的等价关系, 令g: A→A/R, g(a) = [a], ∀a ∈A, 称g 是从A 到商集A/R的自然映射.
实数集R 上的函数f: R→R, f(x) = x+1, 它是严格单调递增的.
单调函数可以定义于一般的偏序集上.
例如, 给定偏序集
, .
等价关系（4学时）
【教学目的】
了解、掌握等价关系及相应的等价类与集合划分的基本概念及例子
【教学要求】
正确地掌握等价关系及相应的等价类与集合划分之间的关系；给定A 上的等价关系R ，会求所有的等价类和商集A/R，或者求与R 相对应的划分；反之给定集合A 上的划分π，求对应于π的等价关系
【教学重点】
等价关系、偏序关系的各种性质的判断和证明；
【教学难点】
如何正确地掌握等价关系及相应的等价类与集合划分之间的关系
【教学方法】
讲练结合教学法、提问式与启发式相结合教学法。
【教学手段】
传统板书与多媒体课件辅助教学相结合。
【课型】新授课
教学过程
4.1一种特殊的二元关系——等价关系(Equivalence Relation).
一、等价关系(Equivalence Relation)
1、定义4.18 设R 为非空集合上的关系. 如果R 是自反的、对称的和传递的, 则称R 为A 上的等价关系. 设R 是一个等价关系, 若∈R, 称x 等价于y, 记作:x ~ y. 例4.17 设A = { 1, 2, …, 8 }, 如下定义A 上的关系R:
R = { | x, y∈A ∧x ≡y （mod 3） }
其中x ≡y （mod 3）是x 与y 模3.
不难验证R 为A 上的等价关系, 因为:
∀x ∈A , 有: x≡x （mod 3）
∀x,y ∈A, 若x ≡y （mod 3）, 则有: y≡x （mod 3）
∀x,y,z ∈A, 若x ≡y （mod 3）, y≡z （mod 3）, 则有: x≡z. （mod 3） 该关系的关系图如右图所示.
不难看到, 上述关系图被分为三个互不连通的部分. 每部分中的数两两都有关系. 不同部分中的数则没有关系, 每一部分中的所有的顶点构成一个等价类.
4.2等价关系与划分
2、定义4.19 设R 为非空集合A 上的等价关系, ∀x ∈A, 令
[x]R = { y | y∈A ∧xRy }
称[x]R为x 关于R 的等价类(Equivalent Class), 简称为x 的等价类, 简记为[x]. 从以上定义可以知道, x的等价类是A 中所有与x 等价的元素构成的集合.
例4.17中的等价类是:
[1] = [4] = [7] = { 1, 4, 7 }
[2] = [5] = [8] = { 2, 5, 8 }
[3] = [6] = { 3, 6 }
关于等价类，有如下性质：
定理4.8 设R 为非空集合A 上的等价关系, 则
(1) ∀x ∈A, [x]是A 的非空子集;
(2) ∀x,y ∈A, 若∈R, 则[x] = [y];
(3) ∀x,y ∈A, 若∉R, 则[x]与[y]不交;
(4) ∪{ [x] | x∈A } = A.
证 (1) 由等价类的定义可知, ∀x ∈A, 有: [x] ⊆ A.
由“等价关系的自反性”可知: x∈[x], 即: [x]非空.
(2) 任取z, 则有
z ∈[x] → ∈R → ∈R (因为R 是对称的)
因此有
∈R ∧∈R → ∈R (因为R 是传递的)
→ ∈R (因为R 是对称的)
从而证明了z ∈[y].综合上述, 必有: [x] ⊆ [y].
同理可证: [x] ⊆ [y].这就得到了: [x] = [y].
(3) 假设: [x]∩[y] ≠ φ.
由假设可知: ∃z ∈[x]∩[y], 即: z∈[x]∧z ∈[y].
所以, ∈R 和∈R.
由“R 的对称性”和“∈R ”可知: ∈R.
再由R 的对称性可得: ∈R.
这就与“已知条件: ∉R ”相矛盾.
所以, 命题成立, 即: [x]∩[y] = φ.
(4) 先证: ∪{ [x] | x∈A } ⊆ A
证:
(4.1) 任取y,
y ∈∪{ [x] | x∈A }
⇒ ∃x(x∈A ∧y ∈[x])
⇒ y∈A
从而有: ∪{ [x] | x∈A } ⊆ A
再证: A ⊆ ∪{ [x] | x∈A }.
(4.2) 任取y,
y ∈A ⇒ y∈[y]∧y ∈A
⇒ y∈∪{ [x] | x∈A }
从而有: A⊆∪{ [x] | x∈A }成立.
综合上述得: ∪{ [x] | x∈A } = A.
3、定义4.20 设R 为非空集合A 上的等价关系, R所有等价类所组成集合称为A 关于R 的
商集, 记作A/R, 即: A/R ＝ {[x]R |（一切x ∈A ）}
例4.17中的商集为: { {1, 4, 7 }, { 2, 5, 8 }, { 3, 6 } }.
和等价关系及商集有密切联系的概念是集合的划分.
定义7.18 设A 为非空集合, 若A 的子集族π(π ⊆ P(A)), 是A 的子集构成的集合) 满足下面的条件: (1) φ∉π
(2) ∀x ∀y(x, yπ∈ ∧x ≠ y ◊ x∩y = φ)
(3) ∪π = A
则称π是A 的划分(Partition), 称π中的元素为A 的划分块.
例7.17 设A = { a, b, c, d }, 给定π1, π2, π3, π4, π5和π6, 如下:
π1 = { { a, b, c }, { d } }
π2 = { { a, b }, { c }, { d } }
π3 = { { a }, { a, b, c, d } }
π4 = { { a, b }, { c } }
π5 = { φ, { a, b }, { c, d } }
π6 = { { a, { a } }, { b, c, d } }
解答：π1是A 的划分; π2是A 的划分
不是A 的划分, π3中的子集中有公共元素a; 不是A 的划分, ∪π4 ≠ A
不是A 的划分, π5中含有空集; 不是A 的划分, π6根本不是A 的子集族
商集是A 的一个划分, 并且不同的商集将对应于不同的划分. 任给A 的一个划分π, 定义A 上的关系R 如下:
R = { | x, y∈A ∧x 与y 在π的同一划分块中 }
不难证明: R为A 上的等价关系, 且该等价关系所确定的商集就是π, 因此, A上的等价关系与A 的划分是一一对应的.
即给定集合A 上的一个等价关系R ，由R 可以唯一产生集合A 的一个划分π＝A/R，反之，对集合A 的任一划分π ＝ {A1,A 2, „,A k }，可唯一对应集合A 上的一等价关系R ＝（A 1×A 1）∪（A 2×A 2）∪„∪（A k ×A k ）。
例4.20 给出A = { 1, 2, 3 }上所有的等价关系.
解 如下图, 先做出A 的所有划分.
这些划分与A 上的等价关系之间的一一对应是: π1对应全域关系EA, π5对应恒等关系IA, π2, π3和π4分别对应于等价关系R2, R3和R4, 其中:
R2 = { , } U IA
R3 = { , } U IA
R4 = { , } U IA
【教学目的】
了解偏序关系的基本概念及例子；给定A 上的偏序关系≤，画出偏序集的哈斯图，反之给定偏序集的哈斯图，求A 和≤的集合表达式；确定偏序集的的任意非空子集B 的最大元，最小元，极大元，极小元，上界，下界，上确界，下确界。
【教学要求】
掌握偏序关系的有关基本概念；理解和判断偏序关系的八种特殊元素。
【教学重点】
偏序关系的各种性质的判断和证明；
【教学难点】
如何正确的理解和判断偏序关系的八种特殊元素。
【教学方法】
讲练结合教学法、提问式与启发式相结合教学法。
【教学手段】
传统板书与多媒体课件辅助教学相结合。
【课型】新授课
教学过程
课题导入
下面介绍另一种重要的关系——偏序关系.
定义4.22 设R 为非空集合A 上的关系. 如果R 是自反的、反对称的和传递的, 则称R 为A 上的偏序关系, 记作≤.
设为偏序关系, 如果∈≤, 则记作x ≤ y, 读作“小于或等于”.
注意: 这里的“小于或等于”不是指数的大小, 而是在偏序关系中的顺序性.
x “小于或等于”y 的含义是: 依照这个序, x排在y 的前边或者x 就是y.
不同偏序的定义有不同的序解释.
例如整除关系是偏序关系, 3 ≤ 6的含义是3整除6; 大于或等于关系也是偏序关系, 针对这个关系写5 ≤ 4是说大于或等于关系中5排在4的前边, 也就是5比4大.
定义4.23 设R 为非空集合A 上的偏序关系, 定义
(1) ∀x, y∈A, x
(2) ∀x, y∈A, x与y 可比 ⇔ x ≤ y∨y ≤ x.
其中: x
有以上两个定义可知: 在具有偏序关系的集合A 中任取两个元素x 和y, 可能有下述几种情况发生:
x
例如: A = { 1, 2, 3 }, ≤是A 上的整除关系, 则有:
1
1 = 1, 2 = 2, 3 = 3,
2和3不可比.
定义4.24 设R 为非空集合A 上的偏序关系, 如果R 是反自反的、反对称的和传递的, 则称R 为A 上的拟序关系，简称为拟序，记作
定义4.25 设R 为非空集合A 上的偏序关系, 如果x, y∈A, x与y 都是可比的, 则称R 为A 上的全序关系(或线序关系).
例如: 数集上的小于等于关系是全序关系, 因为任何两个数总是可比大小的.
一般来说, 整除关系不是全序关系. 如: 集合{ 1, 2, 3 }上的整除关系就不是全序关系, 因为2和3不可整除.
定义7.22 集合A 和A 上的偏序关系一起叫做偏序集, 记作
.
例如: 整数集合Z 和数的小于等于关系≤构成偏序集
, 集合A 的幂集P(A)和包含关系R 构成偏序集
.
利用偏序关系的自反性、反对称性和传递性可简化偏序关系的关系图, 该关系图称为哈斯图(Hasse Diagram).
为了说明哈斯图的画法, 先定义偏序集中顶点之间的覆盖关系.
定义7.23 设为偏序集, ∀x,y ∈A, 如果x
例如: { 1, 2, 4, 6 }集合上的整除关系, 有2覆盖1, 4和6都覆盖2. 但, 4不覆盖1, 因为有1
在画偏序集的哈斯图时, 首先适当排列顶点的顺序, 使得: ∀x,y ∈A,
若x
对于A 中的两个不同元素x 和y, 如果y 覆盖x, 就用一条线段连接x 和y.
例4.22 画出偏序集和
的哈斯图. 解 两个哈斯图如右图所示.
}
{a,b }
{a }
ф
例4.23 已知偏序集的哈斯图如下图, 试求出集合A 和关系R 的表达式.
b,c } c }
A = { a, b, c, d, e, f, g, h }
R = { , , , , , , , , } ∪ IA
下面考虑偏序集中的一些特殊元素.
定义4.28 设为偏序集, B⊆A, y∈B.
(1) 若∀x(x∈B →y ≤x) 成立, 则称y 为B 的最小元;
(2) 若∀x(x∈B →x ≤y) 成立, 则称y 为B 的最大元;
(3) 若∀x(x∈B ∧x ≤y →x=y)成立, 则称y 为B 的极小元;
(4) 若∀x(x∈B ∧y ≤x →x=y)成立, 则称y 为B 的极大元.
从以上定义可以看出: 最小元与极小元是不一样的.
最小元是B 中最小的元素, 它与B 中其它元素都可比;
极小元不一定与B 中元素都可比, 只要没有比它小的元素, 它就是极小元.
对于有穷集B, 极小元一定存在, 而且还可能有多个.
最小元不一定存在, 若存在, 则它一定是唯一的.
若B 中只有一个极小元, 则它一定是B 的最小元.
类似的, 极大元与最大元也有这种区别.
例7.21 设偏序集如下图所示, 求A 的极小元, 最小元, 极大元, 最大元.
解 极小元: a, b, c, g.
极大元: a, f, h.
没有最小元与最大元.
由这个例子可以知道, 哈斯图中的孤立顶点既是极小元也是极大元.
定义7.25 设为偏序集, B⊆A, y∈A.
(1) 若∀x(x∈B →x ≤y) 成立, 则称y 为B 的上界;
(2) 若∀x(x∈B →y ≤x) 成立, 则称y 为B 的下界;
(3) 令C = { y | y为B 的上界 }, 则称C 的最小元为B 的最小上界或上确界;
(4) 令D = { y | y为B 的下界 }, 则称D 的最大元为B 的最大下界或下确界
;
由上面定义可知:
B 的最小元一定是B 的下界, 同时也是B 的最大下界;
B 的最大元一定是B 的上界, 同时也是B 的最小上界.
反过来不一定正确, B 的下界不一定是B 的最小元, 因为它可能不是B 中的元素, B 的上界也不一定是B 的最大元.
B 的上界, 下界, 最小上界, 最大下界都可能不存在. 如果存在, 最小上界与最大下界是唯一的.
4良序集
若是偏序集，对A 的任何一个非空子集都有最小元，则“≤”称为良序关系，称为良序集。
“≤”是良序关系⇒“≤”是全序关系⇒“≤”是偏序关系。
【教学目的】
熟练掌握函数的基本概念，函数的复合运算，逆运算的计算
【教学要求】
给定f 是从集合A 到B 的二元关系，判断f 是否为从A 到B 的函数f ：A →B ，若是，要能用按定义证明法证明f ：A →B 是否为单射，满射，双射；熟练掌握函数的复合运算，逆运算的计算
【教学重点】
函数的各种性质的判断和证明；
【教学难点】
如何正确地判断三种特殊函数
【教学方法】
讲练结合教学法、提问式与启发式相结合教学法。
【教学手段】
传统板书与多媒体课件辅助教学相结合。
【课型】新授课
教学过程
函数(Function)是一种特殊的二元关系.
5.1 函数的定义与性质
定义5.1 设f 为二元关系, 若∀x ∈domf, 都存在唯一的y ∈ranf, 使xfy 成立, 则称f 为函数(或映射).
对于函数f, 如果有xfy, 则记作y=f(x), 并称y 为f 在x 的值.
由于函数是集合, 可用集合相等来定义函数的相等.
定义5.2 设F 和G 为函数, 则, F=G ⇔ F⊆G ∧G ⊆F .
由以上定义可知, 如果两个函数F 和G 相等, 一定满足下面两个条件:
1). domF = domG
2). ∀x ∈domF = domG, 都有: F(x) = G(x)
例如: 函数F(x) = (x2-1)/(x+1), G(x) = x-1是不相等的, 因为 domF = { x | x ∈R ∧x ≠ -1 } , domG = R.
定义5.3 设A 和B 为集合, 如果f 为函数, 且domf = A, ranf⊆B, 则称f 为从A 到B 的函数, 记作f:A→B.
例如 f:N→N, f(x) = 2x是从N 到N 的函数,
g:N→N, g(x) = 2也是从N 到N 的函数.
定义5.4 所有从A 到B 的函数的集合记作BA, 读作“B 上A ”. 符号化表示为B = { f | f: A→B }.
例5.2 设A = { 1, 2, 3 }, B = { a, b }, 求B .
解 B = { f0, f1,„, f7 }, 其中
f0 = { , , } f1 = { , , } f2 = { , , } f3 = { , , } f4 = { , , } f5 = { , , } f6 = { , , } f7 = { , , } 由排列组合知识不难证明: 若|A| = m, |B| = n, 且m, n > 0, 则|BA| = nm. 在例5.2中, |A| = 3, |B| = 2, 所以, |BA| = 23 = 8.
当A 或B 中至少有一个集合是空集时, 可以分成下面三种情况:
1). A = φ且B = φ, 则BA = φφ = { φ }.
2). A = φ且B ≠ φ, 则BA = Bφ = { φ }.
3). A ≠ φ且B = φ, 则BA = φA = φ.
5.1.2函数的像与完全原像.
定义5.6 设函数f: A→B, A1 ⊆ A, B1 ⊆ B.
(1) 令f(A1) = { f(x) | x∈A1 }, 称f(A1)为A1在f 下的像. 特别的, 当A1=A时称f(A)为函数的像.
(2) 令f-1(B1) = { x | x∈A ∧f(x)∈B1 }, 称f-1(B1)为B1在f 下的完全原像.
这里需区别: 函数的值和像. 函数值f(x)∈B, 而
像f(A1) ⊆ B.
假设: B1 ⊆ B, 显然, B1在f 下的完全原像 f-1(B1)是A 的子集.
考虑A1 ⊆ A, 那么, f(A1) ⊆ B.
f(A1)的完全原像就是f-1(f(A1)).
一般有: f-1(f(A1)) ≠ A1, A1 ⊆ f-1(f(A1)).
例如: 函数f: { 1, 2, 3 }→{ 0, 1 }, 满足: f(1)=f(2)=0, f(3)=1
令A1 = { 1 }, 那么, 有:
f-1(f(A1)) = f-1(f({1})) = f-1({0}) = { 1, 2 }
这时, A1 ⊂ f-1(f(A1)).
例8.3 设f: N→N, 且 A A A
⎧x /2若x 为偶数f (x ) =⎨⎩x +1若x 为奇数
假设: A1 = { 0, 1 }, B1 = { 2 }, 那么, 有
f(A1) = f({0,1}) = { f(0), f(1) } = { 0, 2 }
f-1(B1) = f-1({2}) = { 1, 4 }
下面讨论函数的性质.
定义5.7 设f: A→B,
(1) 若ranf = B, 则称f: A→B 是满射的(Onto);
(2) 若∀y ∈ranf, 都存在唯一的x ∈A, 使得:
f(x) = y, 则称f: A→B 是单射的(One-to-one);
(3) 若f 既是满射又是单射, 则称f 是双射的(或一一映射)(One-to-one Correspondence).
由定义不难看出:
若f: A→B 是满射的, 则对于∀y ∈B, 都存在x ∈A, 使得: f(x) = y;
若f: A→B 是单射的, 则对于∀x1, x2∈A, x1 ≠ x2, 一定有: f(x1) ≠ f(x2);
若∀x1, x2∈A, 有: f(x1) = f(x2), 则有: x1 = x2.
例5.4 判断下面函数是否为单射, 满射, 双射的, 为什么?
(1) f: R→R, f(x) = -x2+2x-1
(2) f: Z+→R, f(x) = lnx, Z+为正整数集
(3) f: R→Z, f(x) = ⎣x ⎦
(4) f: R→R, f(x) = 2x+1
(5) f: R+→R+, f(x) = (x2+1)/x, 其中R+为正实数集.
解
(1) f: R→R, f(x)是开口向下的抛物线, 非单调函数, 并且在x = 1点取得极大值0, 它既不是单射, 也不是满射的;
(2) f: Z+→R, f(x)是单调上升, 单射, 但不是满射的, 因为ranf = { ln1, ln2, „ } ⊂ R;
(3) f: R→Z, f(x)是满射的, 不是单射的, 例如: f(1.5) = f(1.2) = 1;
(4) f: R→R, f(x) = 2x+1是双射的;
(5) f: R+→R+, f(x) = (x2+1)/x不是单射的, 也不是满射的.
当x →0+时, f(x)→+∞;
当x →+∞时, f(x)→+∞;
在x = 1处函数f(x)取得极小值f(1) = 2.f(2) = f(1/2) = 2.5.
例5.5 对于以下各题给定的A 、B 和f, 判断是否构成函数f:A→B. 如果是, 说明f: A→B 是否为单射, 满射, 双射的, 并根据要求进行计算.
(1) A = {1,2,3,4,5}, B = {6,7,8,9,10}, f = {,,,,}
(2) A,B同(1), f = { , , , , }
(3) A,B同(1), f = { , , , }
(4) A = B = R, f(x) = x3
(5) A = B = R+, f(x) = x/(x2+1)
(6) A=B=R ⨯ R, f()=, 令L={|x,y∈R ∧y=x+1}, 计算f(L)
(7) A = N ⨯ N, B = N, f() = |x2-y2|.计算f(N ⨯ {0}), f-1({0})
解 (1) 能.f: A→B 既不是单射, 也不是满射.
(2) 不能.∈f 和, 与函数定义矛盾.
(3) 不能. 因为domf = {1,2,3,4} ≠ A.
(4) 能.f: A→B 是双射的.
(5) 能.F: A→B 既不是单射, 也不是满射的. 因为该函数在x=1取得极大值f(1)=1/2.函数不是单调的, 且ranf ≠ R+.
(6) 能.F: A→B 是双射的.
f(L) = { | x∈R } = R ⨯ {-1}
(7) 能.F: A→B 既不单射, 也不满射. 因为f() = f() = 0, 且2∉ranf. f(N ⨯ {0}) = {n2-02 | n∈N} = {n2 | n∈N},
f-1({0}) = { | n∈N}.
下面定义一些常用的函数.
定义8.7
(1) 设f:A→B, 若∃y ∈B, ∀x ∈A, 都有: f(x) = y, 则称f:A→B 是常函数;
(2) ∀x ∈A, 都有: IA(x) = x, 称恒等关系IA 为A 上的恒等函数;
(3) 设和为偏序集, f: A→B
∀x1, x2∈A, 若x1
∀x1, x2∈A, 若x1
类似的也可以定义单调递减和严格单调递减的函数
(4) 设A 为集合, 对于任意的A ’ ⊆ A, A’的特征函数(Characteristic Function)XA’: A→{0,1}定义为(读: Kai) a ∈A ' ⎧1χ(a ) =⎨ ⎩0a ∈A -A '
(5) 设R 是A 上的等价关系, 令g: A→A/R, g(a) = [a], ∀a ∈A, 称g 是从A 到商集A/R的自然映射.
实数集R 上的函数f: R→R, f(x) = x+1, 它是严格单调递增的.
单调函数可以定义于一般的偏序集上.
例如, 给定偏序集
, .