MAT102 Worksheet 6

• 1
  • a
    • Transitivity
      • Show that $⊢$ is transitive, but not reflexive or symmetric.
      • $x⊢y⟹y-x\in P$
      • Let $x⊢y$ and $y⊢z$
      • So we want to show that $x⊢z$ if the above are true.
      • Definitions
        • $x⊢y⟹y-x$
        • $y⊢z⟹z-y$
      • Let's modulate $x⊢z$ to show that $x$ can be $⊢y$ as well
      • $z-x\in P$
      • $z-x+y-y\in P$
      • $y-x+z-y\in P$
      • $(y-x)+(z-y)\in P$
      • From $P2$ in the definition of the set $P$, we know that $x+y\in P$.
      • We also see that the definitions for $x⊢y$ and $y⊢z$ are in our above statement.
      • This shows that $⊢$ is transitive and that the result of $x⊢z$ is also $\in P$
    • Reflexitivity
      • $a⊢a$ can't happen because $a⊢a⟹a-a\in P$.
      • By $P1$, we know that $0\notin P$. So this is a contradiction, and the initial assumption of $a⊢a\in P$ is false.
    • Symmetric
      • This means if $a⊢b$, then $b⊢a$ as well.
      • So $b-a\in P$ and $a-b\in P$.
      • By $P3$ we know that we can either have a positive or a negative value in the set, but not both. So it's a contradiction:
        • $(a-b)\in P$ or $-(a-b)\in P$
        • Let $x=a-b$
        • So we have $x\in P$ and $-x\in P$.
        • It can't be symmetric, as this disobeys $P3$.
  • b
    • If $c\in P$ and $x⊢y$ then $cx⊢cy$.
      • We know $x⊢y\in P$.
      • So $y-x\in P$
      • Let's assume that $cx⊢cy$
        • Then $cy-cx\in P$
        • $c(y-x)\in P$
        • By $P2$, we know that $xy\in P$ for any $x,y\in \mathbb{R}\setminus \{0\}$.
        • So let $\{\begin{array}{l}x=c\\ z=y-x\end{array}$
        • So then we have $xz\in P$, which clearly demonstrates that this is true.
    • Show that if $c\notin P$ and is non-zero, and $x⊢y$ then $cy⊢cx$
      • We know that $c\notin P$.
      • We also know that $x⊢y⟹y-x\in P$.
      • Let's assume that $cy⊢cx$
        • This means $cx-cy\in P$
        • So $c(x-y)\in P$
        • $x-y\in P⟹y⊢x$
        • Then $c$ must be $-c\in P$.
  • c
    • If $x⊢y$ and $u⊢v$ then $x+u⊢y+v$
    • Definitions
      • $x⊢y⟹y-x\in P$
      • $u⊢v⟹v-u\in P$
    • So let's assume that $x+u⊢y+v$ is true:
      • $x+u⊢y+v$
      • This $⟹(y+v)-(x+u)\in P$
      • $(y+v)-(x+u)\in P$
      • $y+v-x-u\in P$
      • $y-x+v-u\in P$
      • $(y-x)+(v-u)\in P$
      • So we know by $P2$ that $x+y\in P$ for any two $x,y\in P\setminus \{0\}$
      • So let $\{\begin{array}{l}a=y-x\\ b=v-u\end{array}$
      • So we have $a+b\in P$, and we have proved that it is the same relation.
  • d
    • If $x,y\in P$ and $x⊢y$, show that $x^2⊢y^2$.
    • Definitions
      • $x⊢y⟹y-x$
    • Let's assume that $x^2⊢y^2$ is true:
      • $x^2⊢y^2⟹y^2-x^2\in P$
      • $y^2-x^2\in P$
      • We know by $P2$, that $xy\in P$ for any $x,y\in P$
      • So we can have $yy-xx\in P$
      • Which is still in $P$.
  • e
    • If $x,y\in P$ and $x⊢y$, show that $\frac{1}{y}⊢\frac{1}{x}$.
    • Definitions
      • $x⊢y⟹y-x\in P$
    • Let's assume that $\frac{1}{y}⊢\frac{1}{x}$ is true:
      • $⟹\frac{1}{x}-\frac{1}{y}\in P$
      • $\frac{1}{x}-\frac{1}{y}\in P$
      • $\frac{y-x}{xy}\in P$
      • $(y-x)\frac{1}{xy}\in P$
      • So we know that by $P2$, that $\frac{1}{x}\in P$ we also know $x,y\in P$ and $xy\in P$.
      • So this works, $y-x⟹x⊢y$.
• 2
  • b
    • Prove that $ax\equiv c(\mathrm{mod}m)$ has a solution $x=x_0$ iff $y_0\in \mathbb{Z}$ such that $a{x}_0+m{y}_0=c$.
    • Definitions
      • $ax\equiv c(\mathrm{mod}m)$
      • $m\mid c-ax$
    • $⟹$
      • $m\mid c-a{x}_0$
      • $m{y}_0=c-a{x}_0$
        • Divisibility statement for $m\mid c-a{x}_0$, we use this because we are looking for the solution $y_0$, so might as well incorporate that into this statement.
      • $a{x}_0+m{y}_0=c$
    • $⟸$
      • Now we know that
      • $a{x}_0+m{y}_0=c$
      • So take the$(\mathrm{mod}m)$ of everything here
      • $a{x}_0(\mathrm{mod}m)+m{y}_0(\mathrm{mod}m)=c(\mathrm{mod}m)$
      • $m(\mathrm{mod}m)=0$
      • $a{x}_0=c(\mathrm{mod}m)$
      • $a{x}_0\equiv c(\mathrm{mod}m)$
  • c
    • $ax\equiv c(\mathrm{mod}m)$ has a solution $⟺gcd(a,m)\mid c$.
    • If $x_0\in \mathbb{Z}$ is a solution, then there are $d=gcd(a,m)$ non-equivalent solutions.
    • ${}^{†}x\equiv x_0(\mathrm{mod}\frac{m}{d})$
    • ${}^{††}\equiv x_0+k\frac{m}{d}mpdm$
    • 1
      • by part $b$.

    • 2