第二章 关系与映射.doc

第二章 关系与映射1、解 R的关系图如图2-1所示。 4123 图2-1 22. 在由个元素组成的集合上，可以有多少种不同的二元关系？若集合的元数分别为，试问从到有多少种不同的二元关系？ 解 因为一个由个元素组成的集合上,任何一个二元关系都是的子集,而中共有个元素,取0个到个元素可以组成子集,所以有个不同的关系。而当时，这个全关系中共有个元素，取0个到个元素组成的子集共有个，因此从到共有种不同的二元关系。3. 设集合，上的二元关系分别为： 试用定义求，并画出其关系图。解 =其关系图如图2-2所示。4123R-S213S - R2431123434212341 图2-2说明 1. 当用定义求复合关系时，先将左关系中每个序偶的第二元素作为中介元素，到右关系中每个序偶里找与其相同的第一元素，将这个元素去掉，用剩余两个元素组成新序偶成为复合关系中的元素。 2. 用定义求出的复合关系与逆关系，可以用关系矩阵来验证其正确性。4. 设集合，集合，是集合上的关系，是上的关系。试验证 证 = = =故 。5. 图2-3所示的图形是集合上关系的关系图，试根据这些关系图分别写出对应的关系矩阵，并说明每种关系所具有的性质（自反性，对称性，反对称性，传递性）。 12312321313图2-3解 = 具有自反性，对称性，反对称性与传递性。 = 具有对称性与传递性。 =具有反对称性。=具有对称性，反对称性与传递性。说明 本题判断关系所具有的性质，主要通过已知关系图与求出的关系矩阵进行，同时对于比较难于判定的传递性，都可以一结合定义进行判定。如果不破坏定义所要求的条件，可以认为满足定义要求，如对的判定。5. 5. 下列关系是否具有如下性质：自反性，对称性，反对称性，传递性？ ； ； 上的恒等关系=；上的空关系。解 具有反对称性与传递性； 具有反对称性； 具有自反性，对称性，反对称性与传递性； 上的空关系具有对称性，反对称性与传递性。说明 本题中的前两个小题均为无限集合，第小题也未给定集合的元数，这样不能得到完整的关系图与关系矩阵。但是，可以在草纸上作出部分元素的关系图与关系矩阵进行判断，同时要充分利用定义要求，便具有该种性质。第小题，与上题中题类型一致，只是元数大一些，结果应与上题相同。7. 设和是集合上的任意关系，试证明或用反例推翻下列论断：若和都是自反的，则也是自反的；若和都是对称的，则也是对称的；若和都是反对称的，则也是反对称的；若和都是传递的，则也是传递的。证 论断正确。对任意，若和都是上的自反关系，则所以，即也是自反的。论断不正确。例如，设，当 ，与都是对称的，但是已不是对称的，故原论断不正确。论断不正确。例如，设集合，当 与都是反对称的，但是，已不是反对称的，（因为），故故原论断不正确。论断不正确。例如，设集合，当，不是传递的，因为，而，故原论断不正确。证毕。8. 设的关系图如图2-4所示，试画出，的关系图。 abcdc图2-4解 ，的关系图如图2-5所示abcdc abcdc abcdc 图2-5说明 对于的关系图，因为，只要在的关系图上对没有自回路的结点都添加上自回路，使可以画成的自反闭包的关系图。 对于的关系图，因为，只要将的关系图中所有单向弧都画成双向弧，便可以画成的对称闭包的关系图。 对于的关系图，当是有限集合上的关系时，画图时，如果关系图中从结点到结点有一连串带箭头的头尾相接的弧相连着，则在的关系图上添加一条直接从到的弧，便可以画出的关系图，如图中关系图上的与，与，与，与之间都应画一条有向弧。但是这里要特别注意两个结点，原有两条到与到的有向弧，这属于总结规律中的特殊情形，作为结点看成是两个结点的重合，所以结点处要画一条自回路，表示从结点到结点。同理，结点也要画一条自回路。9. 设集合，上的关系求和，并写出它们的关系矩阵解 因为 所以 此题，故其关系矩阵为 =说明 此题，这纯属偶然情况，一般地，。10. 设是集合上的二元关系，若是传递的，则也是传递的，而不一定是传递的。证 由2.4定理1知，是传递的，当且仅当，故要证是传递的，只需证明。因为 下面用归纳法证明 当时，左端=右端假设当时，命题成立，即当时，由2.2，习题7的结论，可得=故=即 ，故是传递的。 不一定是传递的。例如 设集合上的二元关系，当，是传递的，而=时，已经不是传递的。 证毕。11. 设是集合上的二元关系，判断下列命题是否正确？ ； 。解 命题正确。由于，并利用，以及对于一切自然数，用数学归纳法的可以证明，所以 。 命题不正确。可以证明。首先证明，当时，则。这是因为，是对称的且，但是，故。由的定义，是包含的最小对称关系，故。同理可证，。由对称闭包定义，有，利用上面证过的结论：再由教材例5（2）可知，是对称的，也是对称的，又根据2.4定理1中（2），是对称的，当且仅当，因此，即。不一定成立。例如，集合上关系，则，而。故12. 设和是集合上的二元关系，试判断下列命题是否正确？；。解 命题正确。因为。命题正确。首先证明 任取，当且仅当，当且仅当或，当且仅当，或，当且仅当，故证得=而命题不正确，可以证明。因为，利用前一例题中证明中证过的结论：当时，则，有同理，有故 不一定成立。例如，设集合，上的二元关系分别为 则 而= 显然， 13. 设集合，上的关系关于等价关系的等价类为：，试求： 等价关系；写出关系矩阵；画出关系图。解 因为等价关系具有自反性，所以，。又因为在同一个等价类中，所以再因为在同一个等价类中，所以 因此 。 的关系矩阵的关系图如图2-6所示bcade图2-614. 设和是非空集合上的等价关系，下列各式哪些是上的等价关系？哪些不是上的等价关系 ？举例说明：； ； ；解 不是上的等价关系。例如，设集合，上的关系不具有自反性与传递性，故不是上的等价关系。不是上的等价关系。例如，设集合，不具有自反性和传递性，因此不是上的等价关系。是集合上的等价关系。因为是集合上的等价关系，任取，有，而且有，所以在集合上是自反的。任取，若，则存在，使得且，因为是对称的，有且，于是，所以是对称的。任取，若且，则存在，分别使得 ，且 ，且由于是传递的，元素与之间以为中介元素，与之间以为中介元素，有，再根据关系的复合，有所以是可传递的，故是集合上的等价关系 不是集合上的等价关系。由题所举例子，有不具有传递性，所以不是集合上的等价关系。是集合上的等价关系。对于任意，有且，故，因此是自反的任取，若是对称的，必有，而是自反的，对于，有，由与，得，由与，得，因此是对称的。任取，若，是传递的，必有。由于是自反的，由与，得与，得与，得故是集合上的等价关系。15. 设集合，上的四个半序关系分别为：试分别画出它们的哈斯图，并判断起其中哪个具有序关系？哪个具有良序关系？解 集合上的半序关系的哈斯图如图2-7所示。1234342113434321 图2-7 其中关系图与所有元素都排在链上，即任意两个元素之间都有关系存在，所以和都是序关系。由于和中每一非空子集都有最小元，所以也都是良序关系。 说明 此题中的阿拉伯数字已经失去了它们在实数集中的大小关系，应该把它们看成四个不同符号。16. 设集合，为上的整除关系。画出半序集的哈斯图；写出集合中的最大元，最小元，极大元，极小元；写出的子集的上界，下界，最小上界，最大下界。解 半序集的哈斯图如图2-8所示。 842241263 图2-8集合中的最大元是24，无最小元，极大元也是24，极小元是2和3。集合的上界是12与24，无下界，最小上界是12，无最大下界说明 最大元与极大元的区别在于，最大元是一个集合中的最“大”者，若有则是唯一的；而极大元则是集合中的元素没有比它“大”的，可能不唯一。对于最小元与极小元具有同样情况。这里把“大”字用引号引起来，因为实际上不一定在研究数与数之间的大小关系，而是在研究某种半序关系。17. 设是集合上的半序关系，且，试证明是上的半序关系。证 对于任意，因为，故，而是上的半序关系，则在上具有自反性，于是，且，这样可得在上是自反的。 任取，且，若，可得且，因为具有反对称性，必有，故即在上具有反对称性。 对于任意，因为，故，若且而，故，可得且，即当同时且。同理，当，也有同时且。因为在上具有传递性，由且，得。又，故，因此满足传递性，所以是上的半序关系。18 设集合，映射定义为，试求。解 因为，当时 而，设映射 故 即 为在上的限制，而为在上的扩充。19. 设和是两个有限集合，它们的元数都是，则是单射的充分必要条件是为满射证 必要性，当是单射时，的元数是，而的元数也是，故，因此是满射。充分性，若为满射时，有，则的元数为，的元数也是，个原象对应个象，即不同元素对应不同的象，因此是到的单射。设为实数集，试证明和都是满射，而不是单射。证 对于任意，可以使成立的有无数对，且，也就是说值域中每个元素都有无数原象在中，所以是满射，而不是单射。对于任意，能使成立的也不止一对实数存在。例如，而，或，即象集中每一元素都有原象，而且原象不唯一，所以是满射，而不是单射。 证毕。说明 欲证明一个映射为满射时，通常采用取值域中任意元素，按映射对应都有原象存在时，则可确定该映射为满射，或者直接证得。 欲证一个映射为单射时，按定义一般有两种方法，一是任取属于定义域，能证得。另一种方法是：取属于值域，证得。21.设集合，与为的映射，若，试求与；若与为上的两个二元关系时，与又将怎样呢？解 根据复合映射的定义，有 若与为上的两个二元关系时， 则说明 上述两种结果，当左端相同时，而右端不同，恰是一种交叉，其原因就是的复合映射与上的的规定不同，请读者再一次仔细对比两种定义的符号表示。22. 设为实数集，都是的映射。（1） 求，并分别判定是否为的满射，单射，双射？（2）