例4 设R,S分别是集合A?{3,4,6,8,9}上的模2同余和模3同余关系，求R?S，
R?S,R?S,R?。
解： R?{(3,3),(4,4),(6,6),(8,8),(9,9),(3,9),(9,3),(4,6),(6,4)(4,8),(8,4),(6,8),(8,6)}， S?{(3,3),(4,4),(6,6),(8,8),3()9,,(9 ),(9,6)}3),,9()3,,(69),,3()6,,(6，,9 R?S?{(3,3),(4,4),(6,6),(8,8),3()9， },9 R?S?{(3,3),(4,4),(6,6),(8,8),(9,9),(3,9),(9,3),(4,6),(6,4)(4,8),(8,4),(6,8),(8,6),(6,9),(9,6)(3,6),(6,3)}
R?S?{(4,6),(6,4),(4,8),(8,4),(6,8),(8,6)}
R??{(3,4),(4,3),(3,6),(6,3),(3,8),(8,3),(4,9),(9,4),(6,9),(9,6),(8,9),(9,8)}
例5 设集合A?{1,2,3}，回答以下问题： (1) 在集合A上可定义多少个二元关系？ (2) 在集合A上可定义多少个自反的二元关系？ (3) 在集合A上可定义多少个反自反的二元关系？ (4) 在集合A上可定义多少个对称的二元关系？
解：(1)521个，因为A?A有9个元素，所以A?A有29?512个子集。 (2)64个，因为关系必须包含恒等关系IA，26?64。 (3) 64个，因为关系不能含有元素(1,1)，(2,2)，(3,3)。
(4)64个，因为关系中元素(1,2)和(2,1)，(1,3)和(3,1)，(2,3)和(3,2)要么同时出现，要么同时不出现，则2?2?2?23?64。
例6 设R是集合A?{1,2,3,4}上的二元关系，其定义如下：
R?{(1,1),(3,1),(1,3),(3,3),(3,2),(4,3),(4,1),(4,2),(1,2)}，判定关系R的性质。
解：R不具有自反性，因为(2,2)不属于关系R；也没有对称性，因为(1,2)属于R，而(2,1)不属于R；也没有反对称性，因为(1,3)和(3,1)同时属于R。可传递性可以通过RR?R，因此R是可传递的。
例7 设R是集合A上的二元关系，试证明R是传递的当且仅当RR?R。 证明：必要性：对?(x,y)，由关系复合的定义，?z?A，使得?RR(x,z)?R,(z,y)?R，由于R是传递的，故有(x,y)?R，从而有RR?R成立；
充分性：若(,由关系复合的定义，?x,y,z?A，xy)?R且(y,z)?R，(x,z)?RR，由于RR?R，故有(x,z)?R，由定义知，R是可传递的。 例
8
设A?{1,2,3,4}，求A上的关系R?{(1,2),(，211
S?{(1,2),(2,1),(2,3),(2,4)}的传递闭包。
解：t(R)?{(1,2),(2,3),(3,4),(1,3),(2,4),(1,4)}；
t(S)?{(1,2),(2,1),(2,3),(2,4),(1,1),(2,2),(1,3),(1,4)}
例9 设集合A为有限集合，且#(A)=5，求A的所有不同的分划的个数。 解：秩为1的分划有1个
1秩为2的分划有C5?C?15个 312秩为3的分划有C5?C5C4/2?25个 2秩为4的分划有C5?10个
秩为5的分划有1个 总的分划数目为52个。
例10 证明整数集合Z上的模4同余关系?是等价关系，并求各元素的等价类集合，以及该等价关系诱导的对于Z的一个分划。 证明：因为对?i?Z,(i?i)/4?0?Z，即?具有自反性；
对?i,j?Z，若i?j，即(i?j)/4?Z，则显然有(j?i)/4?Z，即j?i，故?具有对称性；
对?i,j,k?Z，若i?j且j?k，即(i?j)/4?r?Z，(j?k)/4?s?Z，则有(i?k)/4?r?s?Z，即i?k，故?具有传递性，因此模4同余关系是等价关系。 各元素的等价类集合为
[0]??{,?12,?8,?4,0,4,8,12,}
[1]??{,?11,?7,?3,1,5,9,13,} [2]??{,?10,?6,?2,2,6,10,14,}
[3]??{,?9,?5,?1,3,7,11,15,}
由于不同等价类只有4个，且两两互不相交，故该等价关系诱导的Z的一个分划是{[0]?,[1]?,[2]?,[3]?}。
例11 设R是集合A上的自反关系，证明：R是A上的等价关系的充要条件是
?a,b,c?A，若aRb,aRc则bRc。
证明：充分性：?a?A，由于R是自反的，所以aRa。假设aRb，又因aRa，由已知条件得bRa，即R对称；又假设aRb，bRc，由于R对称，故有bRa，再由已知条件可得aRc，即R传递，因此R等价。
必要性：因为R是A上的等价关系，所以若aRb，aRc，由于R对称，有bRa。由bRa、aRc及R的传递性，可得bRc。
12
例12 判定下列命题是否恒真，并说明你的理由。
(1) 非空集合A上存在二元关系R，使得R既是A上的等价关系，又是A上的偏序关系。
(2) 设?A,R?是偏序集合，??B?A，若B有下界，则集合B有下确界。 解：(1)真命题，因为集合A的恒等关系IA既是A上的等价关系又是A上的偏序关系。
(2) 假命题。反例：设A?{a,b,c,d}，给定偏序集?A,R?的哈斯图如下图(1)所示，令B?{c,d}，则a,b均是其下界，但是B没有下确界。
图(1)
例13 对于下列每一种情况，举出有限集合和无限集合的例子各一个。 (1) 非空偏序集合，其中某些子集没有最大元；
(2) 非空偏序集合，其中有一个子集存在下确界，但是没有最小元； (3) 非空偏序集合，其中有一个子集存在上界，但没有上确界。
解：(1)令A?{1,2,3,4}，R?IA，则?A,R?是偏序集合，但是A没有最大元。 ?N,??是偏序集合，但是N没有最大元。
(2) 令A?{1,2,3}，R?IA?{(1,2),(1,3)}，则?A,R?是偏序集合，子集
B?{2,3}存在下确界1，但是没有最小元；
设A表示非负实数的集合，则?A,??是偏序集合。令B表示正实数的集合，则B存在下确界0，但是B没有最小元。
(3) 令A?{1,2,3,4}，R?IA?{(1,3),(2,3),(1,4),(2,4)}，则?A,R?是偏序集合，令B?{1,2}，则B存在上界3和4，但B没有上确界；
设A?[?1,0)?(0,1]，则?A,??是偏序集合，令B?[?1,0)，则(0,1]中的元素都是B的上界，但是B没有上确界。
例14 设A?{1,2,3,4,5,6,7,8,9,10,11,12}，偏序关系R是A上的整除关系，画出R的哈斯图，求子集{1,2,3,5}及{2,3,4,6}的极大元和极小元、最大元和最小元、上界和下界、上确界和下确界。
13
解：偏序关系的哈斯图如图(2)所示：
{1,2,3,5}的极大元是2,3,5；极小元是1；最大元无；最小元是1；上界无；
下界是1；上确界无；下确界是1；
{2,3,4,6}的极大元是4,6；极小元是2,3；最大元无；最小元是无；上界12；
下界是1；上确界是12；下确界是1；
图(2)
14
第3章 函 数
3.1 函数
3.1.1基本知识点
基本概念：函数、内射、满射、双射
基本理论：设f是A?B的函数，若A和B都是有限集合，A,B的元素个数相同，
则f是内射的充分必要条件是f是满射。
基本计算：判断二元关系是不是函数；判断函数是内射、满射还是双射；求函数
的的定义域和值域。
3.1.2重点与难点：
函数 设A和B是任意两个集合，f是A到B的二元关系，如果对于A中每一个
元素x，都有唯一的y?B，使得(x,y)?f，则称f是一个A到B的函数，记作：f是A?B的函数，对于A中任一元素a，B中对应的b?f(a)，称
b是a在函数f下的象，并称A是f的定义域，B为f的值域包。
(1) 函数也称为映射，是一种特殊的关系，集合A?B的任何子集都是关系，
但不一定是函数，函数要求对于定义域A中的每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制。
(2) 两个函数相等是指：定义域和值域相同，而且定义域内每个元素对应的
象都相同。
内射：设有函数f: A?B，若当ai?aj时，有f(ai)?f(aj)，则称f为内射； 满射：设有函数f: A?B，若f(a)?B，则称f为满射；
双射：设有函数f: A?B，若f既是内射又是满射，则称f为双射。 特殊函数的判断：给定函数，判断其是内射、满射还是双射。
典型题解：
例1：设X?{12，},Y{,?}ab，则从X到Y的不同的二元关系有24?16，分别为：
?0?? ?1?{(1,a)} ?2?{(1,b)}
}?3?{(2,a)} ?4?{(2b,)?5?{(1,a)，(1,b)} ?6?{(1,a)，(2,b)}
?7?{(2,a)，(1,b)} ?8?{(2,a)，(2,b)} ?9?{(1,a)，(2,a)} ?10?{(1,b)，(2,b)} ?11?{(1,a)，(2,a)，(1,b)}
?12?{(1,a),(2,a)，(2,b)} ?14?{(2,a)，(1,b)，(2,b)}
?13?{(1,a)，(1,b)，(2,b)}
15