DiscMat assignment 5

exercise

Title

Wenn Sie Zeit haben, bitte hilfen Sie mir, auch die Aufgabe 5.6 zu korrigieren.

5.1 Computing Representations of Relations

${\rho }^3=\{(1,1),(2,2),(4,4),(1,3)\}$ $M^{\rho }=\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 1& 1\\ 0& 0& 0& 0\\ 1& 1& 1& 1\end{array}\right]$

5.2 Operations on Relations

1.

transitive

• not reflexive
  • Counterexample: $2<\circ |2$ does not hold. There does not exist a number such that it is greater than 2 and can divide 2
• not symmetric
  • Counterexample: $2<\circ |3$ holds but $3<\circ |2$ does not hold. There does not exist a number such that it is greater than 3 and can divide 2
• transitive
  • If $a<\circ |b$ and $b<\circ |c$, then $a<c$ and $c|c$. Therefore, we have $a<\circ |c$

2.

reflexive

• reflexive
  • For any $a\in \mathbb{N}\setminus \{0\}$, we have $a|a$ and $a{\equiv }_{2}a$ so $a|\cup {\equiv }_{2}a$ always holds
• not symmetric
  • Counterexample: $3|\cup {\equiv }_{2}6$ but $6|\cup {\equiv }_{2}3$ does not hold
• not transitive
  • Counterexample: $3|\cup {\equiv }_{2}5$ and $5|\cup {\equiv }_{2}10$, but $3|\cup {\equiv }_{2}10$ does not hold

3.

reflexive, symmetric

• reflexive
  • $|$ is reflexive and $|\subseteq |\cup \widehat{|}$, so $|\cup \widehat{|}$ must also be reflexive
• symmetric
  • Suppose $a|\cup \widehat{|}b$
  • case 1: If $a|b$, then $(b,a)\in \widehat{|}$, so $(b,a)\in |\cup \widehat{|}$
  • case 2: If $a\widehat{|}b$, then $(b,a)\in |$, so $(b,a)\in |\cup \widehat{|}$
• not transitive
  • $2|\cup \widehat{|}6\wedge 6|\cup \widehat{|}3$ , however $2|\cup \widehat{|}3$ does not hold

5.3 An Equivalence Relation

1)

Proof of reflexive Let $\lambda =1$ and $a,b\in \mathbb{R}$ $(a,b)\stackrel{def}{=}(\lambda a,\lambda b)=(1a,1b)=(a,b)$ $⟹(a,b)\sim (a,b)$ is true for all

Proof of symmetric Let $a,b,c,d\in \mathbb{R}$ Suppose $(a,b)\sim (c,d)$ $(a,b)\sim (c,d)\stackrel{def}{⟺}\exists {\lambda }_1>0(a,b)=({\lambda }_{1}c,{\lambda }_{1}d)$ $⟹a={\lambda }_{1}c$ and $b={\lambda }_{1}d$ $⟹c=\frac{1}{{\lambda }_1}a$ and $d=\frac{1}{{\lambda }_1}b$ $⟹(c,d)=\left(\frac{1}{{\lambda }_1}a,\frac{1}{{\lambda }_1}b\right)$ Let ${\lambda }_2=\frac{1}{{\lambda }_1}$ $⟹(c,d)=({\lambda }_{2}a,{\lambda }_{2}b)$ $⟹(c,d)\sim (a,b)$

Proof of transitive Let $a,b,c,d,e,f\in \mathbb{R}$ Suppose $(a,b)\sim (c,d)$ and $(c,d)\sim (e,f)$ $⟹(a,b)=({\lambda }_{1}c,{\lambda }_{1}d)$ and $(c,d)=({\lambda }_{2}e,{\lambda }_{2}f)$ with ${\lambda }_1>0$ and ${\lambda }_2>0$ $⟹(a,b)=({\lambda }_1{\lambda }_{2}e,{\lambda }_1{\lambda }_{2}f)$ with ${\lambda }_1>0$ and ${\lambda }_2>0$ Let ${\lambda }_3={\lambda }_1{\lambda }_2$ with ${\lambda }_3>0$ $⟹(a,b)=({\lambda }_{3}e,{\lambda }_{3}f)$ $⟹(a,b)\sim (e,f)$

2)

Each equivalence class is a line on ${\mathbb{R}}^2$ with slope 1.

5.4 Properties of Relations

1)

$(a,c)\in \gamma ⟺\exists b((a,b)\in \rho \wedge (b,c)\in \hat{\rho })$ $⟺\exists b((b,a)\in \hat{\rho }\wedge (c,b)\in \rho )$ (definition of $\hat{\rho }$) $⟺\exists b((c,b)\in \rho \wedge (b,a)\in \hat{\rho })$ (commutativity of $\wedge$) $⟺(c,a)\in \gamma$ $⟹\gamma =\hat{\gamma }$ $⟹\gamma$ is symmetric The claim is proved.

2)

The claim is false. Counterexample: Let $\sigma$ be $=$ and $\pi$ be $<$ on $\mathbb{N}$ Then $\hat{\pi }$ is $>$ so $\gamma =\sigma \circ \hat{\pi }=\{(a,c):\exists b(a=b\wedge b>c)\}=\{(a,c):a>c\}=>$ $>$ is not symmetric because $2>1$ is true but $1>2$ is false

3)

Let ${\sim }_1$ and ${\sim }_2$ be two relations on set $A$ Let ${\sim }_3$ be ${\sim }_1\cap {\sim }_2$ We prove ${\sim }_3$ is an equivalence relation by showing it’s reflexive, symmetric and transitive

• reflexive
  • For any $x\in A$, $(x,x)\in {\sim }_1$ and $(x,x)\in {\sim }_2$ since both are reflexive. Hence $(x,x)\in {\sim }_3$
• symmetric
  • If $(x,y)\in {\sim }_3$, then $(x,y)\in {\sim }_1$ and $(x,y)\in {\sim }_2$,. Since ${\sim }_1$ and ${\sim }_2$ are both symmetric, we have $(y,x)\in {\sim }_1$ and $(y,x)\in {\sim }_2$. Hence $(y,x)\in {\sim }_3$
• transitive
  • If $(a,b)\in {\sim }_3$ and $(b,c)\in {\sim }_3$, then $(a,b)\in {\sim }_1\wedge (a,b)\in {\sim }_2\wedge (b,c)\in {\sim }_1\wedge (b,c)\in {\sim }_2$. By transitivity of ${\sim }_1$ and ${\sim }_2$, we have $(a,c)\in {\sim }_1\wedge (a,c)\in {\sim }_2$. Thus, $(a,c)\in {\sim }_3$ The claim is proved.

5.6 Antisymmetry (exam 2021)

We disprove the claim by showing a counterexample:

Let $\rho$ , $\sigma$ be two antisymmetric relations on set $\{a,b,c\}$ $\rho \stackrel{def}{=}\{(a,b),(c,b)\}$ $\sigma \stackrel{def}{=}\{(b,a),(b,c)\}$

$\rho \circ \sigma =\{(x,z)|\exists y(x\rho y\wedge y\sigma z)\}=\{(a,c),(c,a)\}$ since $a\rho b$ and $b\sigma c$ give $(a,c)$, and $c\rho b$ and $b\sigma a$ give $(c,a)$ $⟹\rho \circ \sigma$ is not antisymmetric, because both $(a,c)$ and $(c,a)$ are in $\rho \circ \sigma$ but $a\ne c$