Chapter 2
Sets, Relations, Orders

2.1 Set Inclusions and Equalities

To keep the solutions as clear and concise as possible, we will make use of the logical notation introduced in Section 1.2. We will also be making use of the logical constant , which always takes the truth value "true", and the logical constant , which always takes the truth value "false".

1. (1a) 
2. (1b)
3. (1c)
4. (1d) Let . Then and , which means that and .
5. (1e) Assume . First, the left-to-right inclusion follows from 1(d). For the other inclusion, let . However, since , . Hence, . For the converse direction, assume . Then there is some such that but . Hence, but , which means that .
6. (1f)
7. (1g)
8. (1h)
9. (1i)  For the sake of a contradiction, assume or . If , then there is some such that but ; implies that and ,which contradicts the fact that . On the other hand, if , then there is some such that but . Hence, and , which again is a contradiction.
10. (1j) Assume and let . Then or . If , we are done. On the other hand, if , then since . Hence, . For the other inclusion, let ; then, clearly, . For the converse, assume and let . We have to show that . However, implies that . Hence, since , .
11. (1k) Assume and , and let . Then or . If , then since and, similiarly, if , then since . Hence, in both cases, , which means that .
12. (2a) For the sake of a contradiction, assume . Then or . However, since is a subset of any set, . This means that there is some such that but . Hence, and . This is a contradiction since has no elements.
13. (2b) For the right-to-left inclusion, let . However, has no elements, so . Hence, . For the left-to-right inclusion, suppose . Then there is some such that but ; implies that and , which contradicts the fact that .
14. (2c) For the sake of a contradiction, assume . Then there is some such that and . However, implies that and , which contradicts the fact that .
15. (2d) For the left-to-right direction, assume . Then there is some such that but . However, this means that . Hence, . For the converse, assume . Then there is some in . Hence, but , which means that .
16. (2e) For the sake of a contradiction, assume . Then there is some such that . Hence, and . This means that while and while , which is a contradiction.
17. (2f)
18. (2g)
19. (2h)
20. (2i)
21. (2j)
22. (2k) , so, by 1(d), .
23. (2l) , so, by 1(i), .
24. (3a) Assume and let . Then . However, , so , which means that .
25. (3b) Assume and . Then and . To show that , we have to show that . To see this, let . Then and . However, and , so , which proves that . The fact that follows from 1(k). To show that , let . Then and . However, since , , and so , which proves that . Finally, by 2(c), , so .
26. (4a) 
27. (4b) 
28. (4c) 
29. (4d) 

2.2 Functions

1. (1a) is the function from to given by , and, furthermore, dom rng
2. (1b) is the function from to given by , and, furthermore, dom rng is the set of non-negative real numbers.
3. (1c) No, is not defined.
4. (1d) No, is binary, not unary.
5. (1e) No, has range , while has domain .
6. (2a)
7. (2b)
8. (2c)
9. (2d)
10. (3) Let : and : , where and .
11. (4) Let : and : , where and .
12. (5a) cod
13. (5b)

    rng

    rng

    rng

14. (5c) and are injective.
15. (5d) and are surjective.
16. (5e) is the only bijective function.
17. (6a) The fixed points of are 0 and 1.
18. (6b)
19. (6c) has infinitely many fixed points.
20. (7) Let : and assume is bijective. Then has an inverse which is also bijective by Proposition 4.2.11. Hence, has an inverse . Now, let . Then where the second and last steps follow from Definition 4.2.10.
21. (8a) Let : and : be surjective mappings and let . To show that is surjective, we have to find some such that . However, since is surjective, there is some such that . Similarly, since is surjective, there is some such that . Hence, , as desired.
22. (8b) Let : and : , and assume that is injective. Now, suppose . Then . Hence, by definition, . However, is injective, so , and we are done.
23. (9) Let : , : and : . Then
24. (10) Let : . To prove the left-to-right direction, assume is surjective, and consider the mappings : and : . Furthermore, suppose . We have to show that . Now, let . Since is surjective, there is some such that . Hence,
25. For the converse, suppose is not surjective. Then there is some such that, for all , . We have to find two mappings and such that but . Let : and : such that for all , and for all but for an arbitrary fixed element . Then
26. while and we are done.

2.3 Binary Relations and Operations on Them

1. (1) dom(ParentOf) is the set of all humans who have children, while rng(ParentOf) is the set of all humans.

   dom(IsMArriedTo) and rng(IsMarriedTo) are the set of all married humans.

   dom(OwnsDog) is the set of all humans owning a dog, while rng(OwnsDog) is the set of all dogs owned by some human.

   dom(IsCitizenOf) is the set of all humans who are citizens of some country, while rng(IsCitizenOf) are the set all countries.

   dom(IsMemberOf) is the set of all humans who are member of some club, while rng(IsMemberOf) is the set of all clubs that have at least one member.

2. (2a)
3. (2b)
4. (2c)
5. (2d)
6. (3a) The set of all Dachshunds owned by citizens of European countries.
7. (3b) The set of all Scotish Terriers owned by the children of members of the Rotary Club.
8. (3c) The set of all Scotish Terriers owned by parents of members of the Rotary Club.
9. (3d) The set of all those humans who have a parent who is a citizen of a European country and a parent who is a citizen of an African country.
10. (3e) The set of parents whose children are citizens of both African and European countries.
11. (3f) The set of all sons of members of the Rotary Club.
12. (3g) The set of all mothers of members of the Rotary Club.
13. (4a) :
14. (4b) :
15. (4c) :
16. (4d) :
17. (4e) :
18. (4f) :
19. (5a) The graphical representation of contains the overlapping arrows if we were to put the graphical representations of and on top of each other.
20. (5b) The graphical representation of contains the arrows of both graphical representations of and .
21. (5c)  The graphical representation of contains the arrows of the graphical representation of but without those occurring in the graphical representation of .
22. (5d) The graphical representation of contains all possible arrows between nodes but without those occurring in the graphical representation of .
23. (5e) The graphical representation of is the same as the graphical representation of but with the arrows in the opposite direction.
24. (5f) If there is an arrow from to in and an arrow from to in , there is an arrow from to in .
25. (6a)
26. (6b)
27. (6c)
28. (6d)
29. (6e)
30. (6f)
31. (7a) Place 1's everywhere where there are 1's in the matrix representations of both and and 0's everywhere else.
32. (7b) Place 1's everywhere where there is a 1 in at least one of the matrix representations of and and 0's everywhere else.
33. (7c) Change all the 1's in the matrix representation of to 0's if the matrix representation of also contains a 1 in the corresponding row and column, and leave the remaining entries the same as in the matrix representation of .
34. (7d) In the matrix representation of , change the 0's to 1's and the 1's to 0's.
35. (7e) Reflect the representation matrix of about its diagonal.
36. (7f) If there is a 1 in row column of the representation matrix of and a 1 in row column of the representation matrix of , place a 1 in row column of the representation matrix of , and 0's everywhere else.
37. (8a) 
38. (8b) 
39. (8c) 
40. (9a) Consider the set with and on .
41. (9b) Consider the set with and on .
42. (9c) Consider the set with and on .
43. (9d) Consider the set with and on .
44. (10a) 
45. (10c) 
46. (10b) 
47. (10d) 
48. (11) 

2.4 Special Binary Relations

1. (2a) The relation on , defined by iff and leave the same remainder after division by .
2. (2b) The inclusion relation on a collections of sets.
3. (2c) The...