EXERCISE 2.1. Which of the properties of reflexivity, symmetry, antisymmetry and transitivity apply to the relations given in Examples 2.1-2.4?
ExERCISE 2.2. Prove that the relation in Example is a partial ordering.
EXERCISE 2.3. List every pair in the relation given in Example 2.10.
ExERCISE 2.4. Prove that the relation in Example is an equivalence.
EXERCISE 2.5. Prove that congruence is an equivalence relation on .
EXERCISE 2.6. Prove that two integers are in the same congruence class if and only if they have the same remainder when divided by .
EXERCISE 2.7. Suppose is a relation on . What does it mean if is both a partial order and an equivalence?
EXERCISE 2.8. Consider the relations on people "is a brother of", "is a sibling of", "is a parent of", "is married to", "is a descendant of". Which of the properties of reflexivity, symmetry, antisymmetry and transitivity do each of these relations have? EXERCISE 2.9. Let . Consider the following relations on :
(i) if and only if stands for greatest common divisor).
(ii) if and only if and are coprime (i.e. ).
(iii) if and only if .
(iv) if and only if For each relation, say which of the properties of Reflexivity, Symmetry, Antisymmetry, Transitivity it has.
ExERCISE 2.10. For in , define two relations and by if and have a digit in common (but not necessarily in the same place) and if and have a common digit in the same place (so, for example, , but ).
(i) If and , with and , how can one mathematically define and in terms of the coefficients and ?
(ii) Which of the four properties of reflexivity, symmetry, antisymmetry and transitivity do and have?
EXERCISE 2.11. Let . List all possible relations on , and say which are reflexive, which are symmetric, which are antisymmetric, and which are transitive.
EXERCISE 2.12. How many relations are there on a set with 3 elements? How many of these are reflexive? How many are symmetric? How many are anti-symmetric?
EXERCISE 2.13. Repeat Exercise for a set with elements.
ExERCISE 2.14. The sum of two even integers is even, the sum of an even and an odd integer is odd, and the sum of two odd integers is even. What is the generalization of this statement to residue classes ? EXERCISE 2.15. What is the last digit of ? Of ? Of ? Of ?
ExERCISE 2.16. What is ? What is ?
EXERCISE 2.17. Show that a number’s residue is the same as the sum of its digits.
ExERCISE 2.18. Show that the assertion of Exercise is not true for any value of except 3 and 9 .
EXERCISE 2.19. Prove that there are an infinite number of natural numbers that cannot be written as the sum of three squares. (Hint: Look at the possible residues mod 8).
EXERCISE 2.20. Let and . What can you say about the relationship between and ?
ExERCISE 2.21. Let be the relation on defined in Example 2.17. Define an operation on as follows: for and , Is well-defined?
EXERCISE 2.22. Let be the set of functions from finite subsets of to (that is iff there is a finite set such that ). Define a relation on as follows: if iff and . Is a partial ordering? Is an equivalence relation?
ExERCISE . Let be the set of all infinite binary sequences. Define a relation on as follows: For any iff . Is a partial ordering? Is an equivalence relation?
EXERCISE 2.24. Let . Let be a relation on defined by iff . Prove that is a linear ordering. ExERCISE 2.25. Let is a surjection . Define a relation on by iff . Prove that is an equivalence relation. Let be defined by . Show that the level sets of are the equivalence classes of . That is show that EXERCISE 2.26. Let . Show that is composed of singletons (sets with exactly one element) iff is an injection.