91Ó°ÊÓ

Let \(A=\\{a, b, c\\}\). For each of the following, draw a directed graph that represents a relation with the specified properties. (a) A relation on \(A\) that is symmetric but not transitive (b) A relation on \(A\) that is transitive but not symmetric (c) A relation on \(A\) that is symmetric and transitive but not reflexive on \(A\) (d) A relation on \(A\) that is not reflexive on \(A\), is not symmetric, and is not transitive (e) A relation on \(A\), other than the identity relation, that is an equivalence relation on \(A\)

Let \(A=\\{0,1,2,3, \ldots, 999,1000\\} .\) Define the relation \(R\) on \(A\) as follows: For \(x, y \in A, x R y\) if and only if \(x\) and \(y\) have the same number of digits. Prove that \(R\) is an equivalence relation on the set \(A\) and determine all of the distinct equivalence classes determined by \(R\).

Let \(U\) be a nonempty set, and let \(R\) be the "subset relation" on \(\mathcal{P}(U)\). That is, $$ R=\\{(S, T) \in \mathcal{P}(U) \times \mathcal{P}(U) \mid S \subseteq T\\} $$ (a) Write the open sentence \((S, T) \in R\) using standard subset notation. (b) What is the domain of this subset relation, \(R ?\) (c) What is the range of this subset relation, \(R ?\) (d) Is \(R\) a function from \(\mathcal{P}(U)\) to \(\mathcal{P}(U)\) ? Explain.

Let \(U\) be a nonempty set, and let \(R\) be the "element of" relation from \(U\) to \(\mathcal{P}(U) .\) That is, $$ R=\\{(x, S) \in U \times \mathcal{P}(U) \mid x \in S\\} $$ (a) What is the domain of this "element of' relation, \(R ?\) (b) What is the range of this "element of" relation, \(R ?\) (c) Is \(R\) a function from \(U\) to \(\mathcal{P}(U)\) ? Explain.

Define the relation \(\sim\) on \(\mathbb{Q}\) as follows: For \(a, b \in \mathbb{Q}, a \sim b\) if and only if \(a-b \in \mathbb{Z}\). In Progress Check 7.9 of Section \(7.2,\) we showed that the relation \(\sim\) is an equivalence relation on \(\mathrm{Q}\). Also, see Exercise (9) in Section \(7.2 .\) (a) Prove that \(\left[\frac{5}{7}\right]=\left\\{m+\frac{5}{7} m \in \mathbb{Z}\right\\} .\) (b) If \(a \in \mathbb{Z},\) then what is the equivalence class of \(a\) ? (c) If \(a \in \mathbb{Z},\) prove that there is a bijection from \([a]\) to \(\left[\frac{5}{7}\right]\).

Use mathematical induction to prove Proposition \(7.21 .\) If \(n\) is a nonnegative integer, then \(10^{n} \equiv 1(\bmod 9),\) and hence for the equivalence relation of congruence modulo \(9,\left[10^{n}\right]=[1]\).

Let \(\sim\) and \(\approx\) be relations on \(\mathbb{Z}\) defined as follows: \- For \(a, b \in \mathbb{Z}, a \sim b\) if and only if 2 divides \(a+b\). \- For \(a, b \in \mathbb{Z}, a \approx b\) if and only if 3 divides \(a+b\). (a) Is \(\sim\) an equivalence relation on \(\mathbb{Z} ?\) If not, is this relation reflexive, symmetric, or transitive? (b) Is \(\approx\) an equivalence relation on \(\mathbb{Z} ?\) If not, is this relation reflexive, symmetric, or transitive?

Let \(U\) be a finite, nonempty set and let \(\mathcal{P}(U)\) be the power set of \(U\). That is, \(\mathcal{P}(U)\) is the set of all subsets of \(U\). Define the relation \(\sim\) on \(\mathcal{P}(U)\) as follows: For \(A, B \in \mathcal{P}(U), A \sim B\) if and only if \(A \cap B=\emptyset .\) That is, the ordered pair \((A, B)\) is in the relation \(\sim\) if and only if \(A\) and \(B\) are disjoint. Is the relation \(\sim\) an equivalence relation on \(\mathcal{P}(U) ?\) If not, is it reflexive, symmetric, or transitive? Justify all conclusions.

Use mathematical induction to prove that if \(n\) is a nonnegative integer then \(10^{n} \equiv(-1)^{n}(\) mod 11\() .\) Hence, for congruence classes modulo \(11,\) if \(n\) is a nonnegative integer, then \(\left[10^{n}\right]=\left[(-1)^{n}\right]\).

Prove the following proposition: For each \(a \in \mathbb{Z},\) if there exist integers \(b\) and \(c\) such that \(a=b^{4}+c^{4}\), then the units digit of \(a\) must be \(0,1,2,5,6,\) or 7 .