内容发布更新时间 : 2024/12/25 1:46:44星期一 下面是文章的全部内容请认真阅读。
3-10.1 设R和R′是集合A上的等价关系,用例子说明:R∪R′不一定是等价关系。 证明 设 A={1,2,3},S=R∪R′ R={<1,1>,<2,2>,<3,3>,<3,1>,<1,3>} R′={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>} 则R∪R′={<1,1>,<2,2>,<3,3>,<3,1>,<1,3>,<3,2>,<2,3>} 因为如<2,3>∈S∧<3,1>∈S,但<2,1>?S,故R∪R′不是传递的,即R∪R′不是A上的等价关系。 3-10.2 试问由4个元素组成的有限集上所有等价关系的个数为多少? 解 因为集合X上的等价关系与X的划分是一一对应的,所以4个元素的有限集上等价关系的数目,与4个元素集合进行划分的数目是相同的,由习题3-9.1可知共有15个不同的等价关系。 3-10.3 给定集合S={1,2,3,4,5},找出S上的等价关系R,此关系R能产生划分{{1,2},{3},{4,5}},并画出关系图。 解 我们可用如下方法产生一个等价关系: R1={1,2}×{1,2}={<1,1>,<1,2>,<2,1>,<2,2>} R2={3}×{3}={<3,3>} R3={4,5}×{4,5}={<4,4>,<4,5>,<5,4>,<5,5>} R= R1∪R2∪R3={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>} 关系图如图。 3-10.4 设R是一个二元关系,S={<a,b>∣对于某一c,有<a,c>∈R∧<c,b>∈R},证明若R是一个等价关系,则S也是一个等价关系。 证明 设R是A上的等价关系: (1) 对任一x∈A,因为R在A上自反,所以<x,x>∈R。由S定义,<x,x>∈S,所以S是自反的。 (2) 对任意x,y∈A,若<x,y>∈S,则存在某个c,使得<x,c>∈R∧<c,y>∈R,因为R是对称,故有:<y,c>∈R∧<c,x>∈R,由S的定义,可知<y,x>∈S,所以S是对称的。 (3) 对任意x,y,z∈A,若<x,y>∈S,及<y,z>∈S,则必存在某个c1,使<x,c1>∈R,<c1,y>∈R。由R的传递性,可知<x,y>∈R,同理存在c2,使<y,c2>∈R∧<c2,z>∈R,由R传递,可知<y,z>∈R。再由S定义,得<x,z>∈S。故S是传递的。 3-10.5 设正整数的序偶集合A,在A上定义二元关系R如下:<<x,y>, <u,v>>∈R,当且仅当xv=yu,证明R是一个等价关系。
证明 设A上定义的二元关系R为:
xu
<<x,y>, <u,v>>∈R? =
yvxx
① 对任意<x,y>∈A,因为 = ,所以
yy<<x,y>, <x,y>>∈R 即R是自反的。
② 设<x,y>∈A,<u,v>∈A,若
xuux
<<x,y>, <u,v>>∈R? = ? = ?<<u,v>,<x,y>>∈R
yvvy
即R是对称的。
③ 设任意<x,y>∈A,<u,v>∈A,<w,s>∈A,对
<<x,y>, <u,v>>∈R∧<<u,v>, <w,s>>∈R
xuuwxw?( = )∧( = )? =
yvvsys
?<<x,y>, <w,s>>∈R
故R是传递的,于是R是A上的等价关系。
3-10.6 设R是集合A 上的对称和传递关系,证明如果对于A中的每一个元素a,在A中同时也存在b,使在R之中,则R是一个等价关系。
证明 对任意a∈A,必存在一个b∈A,使得<a,b>∈R. 因为R是传递的和对称的,故有:
<a,b>∈R∧<b, c>∈R?<a, c>∈R?<c,a>∈R 由<a,c>∈R∧<c, a>∈R?<a,a>∈R
所以R在A上是自反的,即R是A上的等价关系。
3-10.7 设R1和R2是非空集合A上的等价关系,试确定下述各式,哪些是A上的等价关系,对不是的式子,提供反例证明。 a)(A×A)-R1; b)R1-R2; c)R12; d) r(R1-R2)(即R1-R2的自反闭包)。 解 a)(A×A)-R1不是A上等价关系。例如:
A={a,b},R1={<a,a>,<b,b>}
A×A={<a,a>,<a,b>,<b,a>,<b,b>} (A×A)-R1={<a,b>,<b,a>} 所以(A×A)-R1不是A上等价关系。 b)设 A={a,b,c}
R1={<a,b>,<b,a>,<b,c>,<c,b>,<a,c>,<c,a>,<a,a>,<b,b>,<c,c
>}
R2={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>} R1-R2={<a,b>,<b,a>,<a,c>,<c,a>}
所以R1和R2是A上等价关系,但R1-R2不是A上等价关系。 c)若R1是A上等价关系,则
<a,a>∈R1?<a,a>∈R1○R1
2
所以R1是A上自反的。
若<a,b>∈R12则存在c,使得<a, c>∈R1∧<c,b>∈R1。因R1对称,故有 <b, c>∈R1∧<c,a>∈R1?<b, a>∈R12 即R12是对称的。
若<a,b>∈R12∧<b, c>∈R12,则有 <a,b>∈R1○R1∧<b, c>∈R1○R1 ?(?e1)(<a, e1>∈R1∧<e1, b>∈R1) ∧(?e2)(<b, e2>∈R1∧<e2, c>∈R1) ?<a,b>∈R1∧<b, c>∈R1(∵R1传递) ?<a,c>∈R12 即R12是传递的。
故R1是A上的等价关系。
d)如b)所设,R1和R2是A上的等价关系,但 r(R1-R2)=(R1-R2)∪IA
={<a,b>, <b,a>, <a,c>,<c,a>,<a,a>,<b,b>, <c,c>} 不是A上的等价关系。
3-10.8 设C*是实数部分非零的全体复数组成的集合,C*上的关系R定义为:(a+bi)R(c+di)?ac>0,证明R是等价关系,并给出关系R的等价类的几何说明。
证明:(1)对任意非零实数a,有a2>0?(a+bi)R(a+bi) 故R在C*上是自反的。
(2) 对任意(a+bi)R(c+di)?ac>0, 因ca=ac>0?(c+di)R(a+bi),
*
所以R在C上是对称的。
(3)设(a+bi)R(c+di) ,(c+di)R(u+vi),则有ac>0?cu>0 若c>0,则a>0?u>0? au>0 若c<0,则a<0?u<0? au>0
所以(a+bi)R(u+vi),即R在C*上是传递的。
关系R的等价类,就是复数平面上第一、四象限上的点,或第二、三象限上的点,因为在这两种情况下,任意两个点(a,b),(c,d),其横坐标乘积ac>0。
3-10.9 设Π和Π?是非空集合A上的划分,并设R和R?分别为由Π和Π?诱导的等价关系,那么Π?细分Π的充要条件是R? ? R。
证明:若Π?细分Π。由假设aR?b,则在Π?中有某个块S?,使得a,b∈S?,因Π?细分Π,故在Π中,必有某个块S,使S?? S,即a,b∈S,于是有aRb,即R? ? R。
反之,若R? ? R,令S?为H?的一个分块,且a∈S?,则S?=[a]R?={x|xR?a}
但对每一个x,若xR?a,因R? ? R,故xRa,因此{x|xR?a} ?{x|xRa}即[a]R? ?[a]R 设S=[a]R,则S?? S
这就证明了Π?细分Π。
3-10.10 设Rj是表示I上的模j等价关系,Rk是表示I上的模k等价关系,证明I/Rk细分I/Rj当且仅当k是j的整数倍。
证明:由题设Rj={
Rk={
故
b)若对于某个r∈I,有k=rj则:
因此,Rk ? Rj,于是I/Rk细分I/Rj
2
5-1代数系统的引入 5.1.1设集合A={1,2,3,…,10},问下面定义的二元运算*关于集合A是否封闭? a) x*y=max(x,y); b) x*y=min(x,y); c) x*y=GCD(x,y);(最大公约数) d) x*y=LCM(x,y);(最小公倍数) e) x*y=质数p的个数,其中x≤p≤y。 解:a)封闭。b)封闭。c)封闭。d)不封闭。e)不封闭。 5.1.2在下表所列出的集合和运算中,请根据运算是否在相应集合上封闭,在相应位置上填写“是”或“否”,其中I表示整数集,N表示自然数集合。 是否封闭 集合 I N {x∣0≤x≤10} {x∣-10≤x≤10} {2x∣x∈I} 解: 是否封闭 集合 I N {x∣0≤x≤10} {x∣-10≤x≤10} {2x∣x∈I} 5-2运算及其性质 5.2.1对于实数集合R,下表所列的二元运算是否具有左边一列中那些性质,请在相应位置上填写“是”或“否”。 结合律 交换律 有单位元 有零元 解: 结合律 交换律 有单位元 有零元 + 是 是 是 否 - 否 否 否 否 × 是 是 是 是 max min 是 是 否 否 是 是 否 否 ∣x-y∣ 否 是 否 否 + - × max min ∣x-y∣ + 是 是 否 否 是 - 是 否 否 否 是 是 是 是 否 是 + - 运算 ∣x-y∣ max 是 是 是 是 是 min 是 是 是 是 是 ∣x∣ 是 是 是 是 是 运算 ∣x-y∣ max min ∣x∣