2.6: Exercises

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 $2.6$ 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 $2.17$ is an equivalence.

EXERCISE 2.5. Prove that congruence $\bmod n$ is an equivalence relation on $\mathbb{Z}$.

EXERCISE 2.6. Prove that two integers are in the same congruence class $\bmod n$ if and only if they have the same remainder when divided by $n$.

EXERCISE 2.7. Suppose $R$ is a relation on $X$. What does it mean if $R$ 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 $X=\{k \in \mathbb{N}: k \geq 2\}$. Consider the following relations on $X$ :

(i) $j R_{1} k$ if and only if $\operatorname{gcd}(j, k)>1(\operatorname{gcd}$ stands for greatest common divisor).

(ii) $j R_{2} k$ if and only if $j$ and $k$ are coprime (i.e. $\operatorname{gcd}(j, k)=1$ ).

(iii) $j R_{3} k$ if and only if $j \mid k$.

(iv) $j R_{4} k$ if and only if $$\{p: p \text { is prime and } p \mid j\}=\{q: q \text { is prime and } q \mid k\} .$$ For each relation, say which of the properties of Reflexivity, Symmetry, Antisymmetry, Transitivity it has.

ExERCISE 2.10. For $j, k$ in $\mathbb{N}^{+}$, define two relations $R_{1}$ and $R_{2}$ by $j R_{1} k$ if $j$ and $k$ have a digit in common (but not necessarily in the same place) and $j R_{2} k$ if $j$ and $k$ have a common digit in the same place (so, for example, $108 R_{1} 82$, but $(108,82) \notin R_{2}$ ).

(i) If $j=\sum_{m=0}^{M} a_{m} 10^{m}$ and $k=\sum_{n=0}^{N} b_{n} 10^{n}$, with $a_{M} \neq 0$ and $b_{N} \neq 0$, how can one mathematically define $R_{1}$ and $R_{2}$ in terms of the coefficients $a_{m}$ and $b_{n}$ ?

(ii) Which of the four properties of reflexivity, symmetry, antisymmetry and transitivity do $R_{1}$ and $R_{2}$ have?

EXERCISE 2.11. Let $X=\{a, b\}$. List all possible relations on $X$, 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 $2.12$ for a set with $N$ 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 $\bmod 3$ ? EXERCISE 2.15. What is the last digit of $3^{5^{7}}$ ? Of $7^{5^{3}}$ ? Of $11^{10^{6}}$ ? Of $8^{5^{4}}$ ?

ExERCISE 2.16. What is $2^{1000000} \bmod 17$ ? What is $17^{77} \bmod 14$ ?

EXERCISE 2.17. Show that a number’s residue $\bmod 3$ is the same as the sum of its digits.

ExERCISE 2.18. Show that the assertion of Exercise $2.17$ is not true $\bmod n$ for any value of $n$ 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 $f: X \rightarrow Y$ and $g: Y \rightarrow Z$. What can you say about the relationship between $X / f$ and $X /(g \circ f)$ ?

ExERCISE 2.21. Let $R$ be the relation on $X=\mathbb{Z} \times \mathbb{N}^{+}$defined in Example 2.17. Define an operation $\star$ on $X / R$ as follows: for $x=(a, b)$ and $y=(c, d)$, $$[x] \star[y]=[(a d+b c, c d)] .$$ Is $\star$ well-defined?

EXERCISE 2.22. Let $X$ be the set of functions from finite subsets of $\mathbb{N}$ to $\ulcorner 2\urcorner$ (that is $f \in X$ iff there is a finite set $D \subseteq \mathbb{N}$ such that $f: D \rightarrow\ulcorner 2\urcorner$ ). Define a relation $R$ on $X$ as follows: if $f, g \in X, f R g$ iff $\operatorname{Dom}(g) \subseteq \operatorname{Dom}(f)$ and $g=\left.f\right|_{\operatorname{Dom}(g)}$. Is $R$ a partial ordering? Is $R$ an equivalence relation?

ExERCISE $2.23$. Let $X$ be the set of all infinite binary sequences. Define a relation $R$ on $X$ as follows: For any $f, g \in X, f R g$ iff $f^{-1}(1) \subseteq$ $g^{-1}(1)$. Is $R$ a partial ordering? Is $R$ an equivalence relation?

EXERCISE 2.24. Let $X=\{\ulcorner n\urcorner \mid n \in \mathbb{N}\}$. Let $R$ be a relation on $X$ defined by $x, y \in R$ iff $x \subseteq y$. Prove that $R$ is a linear ordering. ExERCISE 2.25. Let $X=\{f: \mathbb{R} \rightarrow \mathbb{R} \mid f$ is a surjection $\}$. Define a relation $R$ on $X$ by $f R g$ iff $f(0)=g(0)$. Prove that $R$ is an equivalence relation. Let $F: X \rightarrow \mathbb{R}$ be defined by $F(f)=f(0)$. Show that the level sets of $F$ are the equivalence classes of $X / R$. That is show that $$X / R=X / F .$$ EXERCISE 2.26. Let $f: X \rightarrow Y$. Show that $X / f$ is composed of singletons (sets with exactly one element) iff $f$ is an injection.