23666: HW 6
HelmutKnaust (Talk | contribs) (Created page with "'''Problem 26.''' Consider the following equivalence relation on the set $A=\{1,2,3,4,5,6\}$: \[R=\{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(1,2),(1,4),(2,1),(2,4),(4,1),(4,2),(3...") |
HelmutKnaust (Talk | contribs) |
||
| Line 8: | Line 8: | ||
#Find all distinct equivalence classes of this relation. | #Find all distinct equivalence classes of this relation. | ||
| − | '''Problem 28.''' Define a relation $R$ on $\mathbb{N}$ by: $xRy$ if x and y have the same prime divisors. (For | + | '''Problem 28.''' Define a relation $R$ on $\mathbb{N}$ by: $xRy$ if $x$ and $y$ have the same prime divisors. (For example, $6R12$.) |
#Show that $R$ is an equivalence relation. | #Show that $R$ is an equivalence relation. | ||
#Find the partition generated by $R$. | #Find the partition generated by $R$. | ||
'''Problem 29.''' A relation $R$ on a non-empty set $X$ is called ''reverse-transitive'' if | '''Problem 29.''' A relation $R$ on a non-empty set $X$ is called ''reverse-transitive'' if | ||
| − | \[(a,b)\in R \wedge (b,c)\in R \Rightarrow (c,a)\in R | + | \[(a,b)\in R \wedge (b,c)\in R \Rightarrow (c,a)\in R$ for all $a,b,c \in X.\] |
Show that a relation $R$ on a non-empty set $X$ is an equivalence relation if and only if it is reflexive and reverse-transitive. | Show that a relation $R$ on a non-empty set $X$ is an equivalence relation if and only if it is reflexive and reverse-transitive. | ||
Revision as of 16:24, 11 April 2019
Problem 26. Consider the following equivalence relation on the set $A=\{1,2,3,4,5,6\}$: \[R=\{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(1,2),(1,4),(2,1),(2,4),(4,1),(4,2),(3,6),(6,3)\}.\] Find the partition generated by $R$.
Problem 27. Let $R$ be a relation on $\mathbb{N}$ defined by \[(p,q)\in R \Leftrightarrow p^2+q^2 \mbox{ is even.}\]
- Show that $R$ is an equivalence relation.
- Find all distinct equivalence classes of this relation.
Problem 28. Define a relation $R$ on $\mathbb{N}$ by: $xRy$ if $x$ and $y$ have the same prime divisors. (For example, $6R12$.)
- Show that $R$ is an equivalence relation.
- Find the partition generated by $R$.
Problem 29. A relation $R$ on a non-empty set $X$ is called reverse-transitive if \[(a,b)\in R \wedge (b,c)\in R \Rightarrow (c,a)\in RUNIQ4bb61b0c5e71411a-MathJax-16-QINUa,b,c \in X.\] Show that a relation $R$ on a non-empty set $X$ is an equivalence relation if and only if it is reflexive and reverse-transitive.
