CS 390 Solutions to Unit 3 Exercises

pp. 36 - 42

1.28 (a) It is symmetric because for (1,3), (3,1) exists and vice versa.
(It is neither reflexive nor transitive).
(b) It is reflexive because for every element $x$ in {1,2,3} $(x,x)$ exists in $R$. It is also transitive because for (1,1) and (1,2), (1,2) exists in $R$, and for every $(x,x)$ ( and $(x,x)$ ), $(x,x)$ exists in $R$.
(It is not symmetric).
(c) It is reflexive, symmetric and transitive because those properties are vacuously satisfied, i.e. there are no ordered pairs to satisfy the conditions for those three properties.


1.61 There might be an element $a$ in $A$ which is not related to any element of $A$, that is, there may not be any $b$ that satisfies $a R b$. Then for that $a$, $a R a$ does not have to hold. Thus the second sentence is where it went wrong.

1.30(a) Reflexive and transitive but not symmetric
(c) Symmetric and transitive but not reflexive.

1.35 $x_{1}^{2} = x_{2}^{2}$ iff $x_{1} = x_{2}$ or -$x_{2}$.
Hence $xRy$ iff $x = y$ or $-y$, or equivalently iff $\mid x \mid$ = $\mid y \mid$. Thus the equivalence classes are {$x, -x$} for all real numbers $x$.

1.66 Let $B$ be the set of representatives taken one from each of the equivalence classes of $R$ on $A$. Let $f$ be the mapping that mapps $x$ in $A$ to the representative of the equivalence class $x$ belongs to. Then $f$ is a function because every element of $A$ belongs to a unique equivalence class of $R$. Also for any elements $x$ and $y$ of $A$ $f(x) = f(y)$ iff $x$ and $y$ belong to the same equivalence class. Hence $f(x) = f(y)$ iff $xRy$.