内容发布更新时间 : 2024/4/25 10:10:27星期一 下面是文章的全部内容请认真阅读。
（2）{
（3）{
9. 设Rj表示Z上模j等价关系，Rk表示Z上模k等价关系, 证明：Z/Rk细分Z/Rj当且仅当k是j的整数倍。
证明：充分性：若k是j的整数倍，即?l?Z，使k=lj， Z/Rk={[a]Rk| a?Z}，Z/Rj={[a]Rj| a?Z }，[a]Rk={x| x?Z∧aRkx}，[a]Rj={x| x?Z∧aRjx}，显然对任意的x?[a]Rk，a?x(mod k)，即?m?Z，使得a?x=km= ljm= lmj，即x?[a]Rj，因此Z/Rk细分Z/Rj。 必要性：若Z/Rk细分Z/Rj，即[a]Rk?[a]Rj，显然
10. 证明：若关系R是对称的, 则Rk(k≥1, k?N)也是对称的。 证明：
设R是A上的二元关系，?x，y?A，若xRky成立，则由关系复合的定义，存在x0=x,x1,x2,…xk-1,xk=y，使得x0Rx1, x1Rx2,…, xk-1Rxk成立，由R是对称的,故xkRxk-1, xk-1Rxk-2, …, x2Rx1, x1Rx0成立,再由关系复合的定义，有xkRkx0成立，即yRkx，因而Rk(k≥1, k?N)是对称的。
11. 设集合A={a,b,c,d}上的关系R={
?0?1MR???0??0?0?1??0??0?0?1??0??0
1000100001000100
100001000??1?00??，IA???01???0??0010010100?0??1??0?00100001?0?1??0??00100001011001010
0??0?10??，M?1??R?00???1??0011001010?0??。 1??1?0?0?? 1??0?010010000?1?? 0??0?101000010?0??, 0??0?0??1
?00??∨?1??0??0??00??0
?10??∨?1??0??0??0100001000??1
?10??=?0??0??1??00??0
?10??=?0??0??0??010000100所以r(R)={
所以s(R)={
MR2?0?1???0??00??1?00????1??0??0??0MR3?1?0???0??0?0?1???0??001001000?1?1???0??01000010011000?1??0??0?1?0??0??0?1100?0?1??0??0?0?1??0??010001000010001000??0?10????1??0??0??00??1?00????1??0??0??010000100010010001?0?? 0??0?0?1?? 0??0?MR4所以Mt(R)1?1?? 1??0?t(R)={
12. 设R和S是A上的二元关系，且R?S，证明： （1）r(R) ?r(S) （2）s(R) ?s(S) （3）t(R) ?t(S) 证明：
（1）?
（3）?
（1）r(R∪S)= (R∪S)∪IA= (R∪IA)∪(S∪IA) = r(R)∪r(S)。
（2）s(R∪S)= (R∪S)∪(R∪S) ?1= (R∪S)∪(R?1∪S?1) = (R∪R?1)∪(S∪S?1) = s(R)∪s(S)。 （3）t(R)∪t(S) =
?R∪?S，t(R∪S) =?(R?S)=?R∪?S∪?iiiiii?1i?1i?1i?1i?1?????Ri?Sj显，
1?i,j??然t(R)∪t(S)?t(R∪S)。14. 求集合{a，b，c，d }的所有划分和等价关系。
解：集合{a，b，c，d}中共有4个元素，可作如下划分：
1) 4＝1＋1＋1＋1型划分，只有一个，即{ {a}，{b}，{c}，{d}}，对应的等价关系为：{ a>， 2d}，{b}，{c}}，{ {b，c}，{a}，{d}}，{ {b，d}，{a}，{c}}，{ {c，d}，{a}，{b}}，对应的等价关系为：{ 13) 4＝3＋1型划分，有C4＝4个，即{ {a，b，c}，{d}}，{ {a，b，d}，{c}}，{ {a，c，d}， {b}}，{ {b，c，d}，{a}}，对应的等价关系为：{ 24) 4＝2＋2型划分，有C4/2＝3个，即{ {a，b}，{c，d}}，{ {a，c}，{ b，d}}，{ {a， d}，{b，c}}，对应的等价关系为：{ d>， 5) 4＝4＋0型划分，有1个，即{ {a，b，c，d}}，对应的等价关系为：{ 综上，集合{a，b，c，d}的划分和等价关系共有15个。 15. 设R是非空集合A上的二元关系。如果对?a,b,c∈A满足aRb且bRc?cRa，则称R为A上循环关系。证明：R是自反和循环的关系当且仅当R是等价关系。 证明： 必要性：若R是自反和循环的，对?a,b,c∈A，aRa成立，若aRc成立，由R是循环的，有cRa，因此R是对称的，再若aRb且bRc，由R是循环的，有cRa，再由R是对称的，有aRc，因此R是传递的，因而R是等价关系。 充分性：若R是等价关系，则显然R是自反的，只需证R是循环的。对?a,b,c∈A，若 aRb且bRc，由R的传递性，有aRc，再由R的对称性，有cRa，因此R是循环的。 16. 设A, B是非空集合，f是从A到B的映射。定义A上二元关系R为： x，y∈A, xRy当且仅当f(x)=f(y) 证明：R是A上等价关系，并描述由R生成的A的划分。 证明： 显然f(x)=f(x)，因此xRx当，即R是自反的。 若xRy，有f(x)=f(y)，因此f(y)=f(x)，所以yRx，即R是对称的。 若xRy，yRz，有f(x)=f(y)，f(y)=f(z)，因此f(x)=f(z)，所以xRz，即R是传递的。 因此R是A上等价关系。 由R生成的A的划分中凡是对应的值相同的自变量属于同一分块。 17. 给出一个既是等价关系又是偏序关系的二元关系。 解： A＝{a,b,c}上的R={ 18. 设A1、A2和A3是全集U的子集，则形如?Ai?(Ai?为Ai或~Ai)的集合称为由A1、A2和A3 i?13产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。 证明： （1）?Ai??? i?13（2）?Ai?∩?Aj?=? i?1i?133（3）(A1∩A2∩A3)∪(A1∩A2∩~A3)∪(A1∩~A2∩A3)∪(A1∩~A2∩~A3)∪(~A1∩A2∩A3)∪(~A1∩A2∩~A3)∪(~A1∩~A2∩A3)∪(~A1∩~A2∩~A3)=(A1∩A2)∪(A1∩~A2)∪(~A1∩A2)∪(~A1∩~A2) = A1∪~A1=U 因此，由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。 19. 设R和S是A上的相容关系，问： （1）复合关系RS是A上的相容关系吗？ （2）R∩S是A上的相容关系吗？ （3）R∪S是A上的相容关系吗？ 解： （1）设A={1,2,3}，R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>}，S={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}，RS={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<2,3>,<3,2>,<1,3>}，不是相容关系。 （2）R∩S显然是自反的， 20. 画出集合S={1,2,3,4,5,6}在偏序关系“整除”下的哈斯图， （1）写出{1,2,3,4,5,6}的最大(小)元和极大(小)元； （2）分别写出{2,3,6}和{2,3,5}的上(下)界、上(下)确界。 解：哈斯图如下： {1,2,3,4,5,6}的最大元：无。{1,2,3,4,5,6}的最小元：1。 {1,2,3,4,5,6}的极大元：4、5、6。{1,2,3,4,5,6}的极小元：1 546{2,3,6}的上界：6。{2,3,6}的下界：1。 {2,3,6}的上确界：6。{2,3,6}的下确界：1。 23{2,3,5}的上界：无。{2,3,5}的下界：1。 {2,3,5}的上确界：无。{2,3,5}的下确界：1。 1 习题四 1. 分析下列各个函数，指出其性质（入射、满射或双射） （1）f: Z→Z, f(j)=j mod 3 （2）f: N→N，f(j)??10j是偶数 j是奇数（3）f: N→{0,1}，f(j)??10j是偶数 j是奇数（4）f: Z→N，f(i)=|2i|+1 （5）f: R→R，f(r)=2r –15 解： （1）、（2）、（4）既不是入射，也不是满射。 （3）是满射。 （5）是双射。 2. 假设f和g是函数，求证f∩g也是函数。 证明： f∩g={ dom h ={x|x?dom f∩dom g∧f(x) =g(x)} 若y1? y2，因为f是函数，故必有y1=f(x1)，y2=f(x2)，且x1?x2，所以h = f∩g是一个函数。因为dom h存在且y1? y2时x1?x2，即 h ={ 3. 设A={1，2，?，n}，证明从A到A的任意单射函数必是满射函数，其逆亦真。 证明：设f是从A到A的单射函数，则|A|=| f(A)|，因为f是A到A的函数，所以 f(A) ? A，又因为|A|=| f(A)|，且|A|是有限的，因此必有f(A) = A，即f是满射函数。 反之，若f是从A到A的满射函数，根据满射定义有，f(A) = A，于是|A|=| f(A)|，又由|A|是有限的，故f是从A到A的单射函数。 4. 证明从N×N到N的函数f(x，y)=x+y和g(x，y)=x?y是满射，但不是单射。 证明：对任意z?N，显然存在0，1，z?N，使得0+z=z，1?z=z，因而f(x，y)=x+y和g(x，y)=x?y是满射。由于3+2=4+1=5，因而f(x，y)=x+y不是单射，由于3?2=6?1=6，因而g(x，y)=x?y不是单射。 5. 试给出满足下列条件的函数例子。 （1）是单射而不是满射。 （2）是满射而不是单射。 （3）不是单射也不是满射。 （4）既是单射又是满射。 解： （1）设A={a,b,c}，B={1,2,3,4}，f={ （3）从A到B存在入射的条件是什么？有多少不同的入射？ （4）从A到B存在满射的条件是什么？有多少不同的满射？ （5）从A到B存在双射的条件是什么？有多少不同的双射？ 解：（1）2 mn 。（2）n m。（3）m≤n，Cn?m!。 （4）n≤m，n!S(m，n)。(本题具有一定的难度，S(m，n)的意义请参见9.5节，本题即第9章44题。)（5）m=n，m！。 7. 证明： （1）f(A∪B)= f(A)∪f(B) （2）f(A∩B)? f(A)∩f(B) （3）f(A)-f(B) ? f(A-B) 证明： m（1）对任意的y?f(A∪B)有， y?f(A∪B) ??x?A∪B∧f(x)= y??x?A∨?x?B∧f(x)= y ?(?x?A∧f(x)= y)∨(?x?B∧f(x)= y) ? y?f(A)∨y?f(B) ? y?f(A)∪f(B) （2）对任意的y?f(A∩B)有， y?f(A∩B) ??x?A∩B∧f(x)= y??x?A∧?x?B∧f(x)= y ?(?x1?A∧f(x1)= y) ∧(?x2?B∧f(x2)= y) ? y?f(A)∧y?f(B) ? y?f(A)∩f(B) （3）对任意的y? f(A)-f(B)有，y?f(A)∧y?f(B)。即对某个x1?A，y=f(x1)，但对任意x?B，y?f(x)。故对某个x1?A-B，y=f(x1)，即 y? f(A-B) 于是 f(A)-f(B) ? f(A-B)。 8. 设f: A→B是满射函数，且函数g: B→P(A)定义为: g(b)={x|x∈A∧f(x)=b} 证明：g是单射。其逆成立吗？若成立给出证明，否则给出例子予以说明。 证明：因为f是满射函数，则对任意b∈B，至少存在一个x∈A，使得f(x)=b，故g的定义域为B。对任意的b1，b2?B，且b1?b2， g(b1)={x|x∈A∧f(x)= b1} g(b2)={y|y∈A∧f(y)= b2} 因为b1?b2，f(x)?f(y)，而f是函数，故x?y，所以 g(b1)?g(b2) 故g是单射。 逆不成立。 例如：A={a,b,c}，B={x,y,z}，则 f: A→B，f(a)=x，f(b)=x，f(c)=y。 g: B→P(A)，g(x)={a,b}，g(y)={c}，g(z)= ?。 g是单射，但f不是满射。 9. 证明：若f: A→B，g: B→A，且gf =IA，f g =IB，则g=f-1，且f=g-1。 证明：因为gf =IA，所以gf (a1)= g(f (a1)) =a1，gf (a2)= g(f (a2)) =a2，若a1≠a2，g(f (a1))≠g(f (a2))，所以f (a1)≠f (a2)，即f:是入射。 又对任意的a?A有gf (a)= g(f (a)) =a，即存在f (a)=b?B，使得g(b) =a，因此g是满射。同理，若f g =IB，则g是入射且f是满射，故可知f和g都是双射函数。 设 反之，若 上述证明得到 证明：设A={a,b,c}，B={1,2,3,4}，C={x,y,z}，f是A到B的函数，g是B到C的函数， f={ 则gf={