MAT102 Lecture 19

• 2
  • a
    • Base is $MI\in H$
    • We get $MII,MIIU$
    • Then again
      • $MIIIU,MIIII,MIIUIIU$
      • $MUU,MUI,MUUUU$
    • So we can get $MUI$
    • Eventually we can get $MIU$ because we end up expanding a term lik $MIIU$ and eventually get $xUUx$ then we can cut it out.
    • I don't think we can get $MIU$ because we will keep on getting $III$ and then replace it with $U$, but if it ends with $I$ then it becomes $IU$. So in my head it looks like it'll be an inf loop which we can cut out enough to get $MU$.
  • b
    • For an element $x\in H$, defind $f(x)$ to be the number of $I$'s in $x$.
    • $f(MIUIUII)=4$.
    • $\mathrm{\forall }x\in H,3\nmid f(x)$
    • $f(x)\not\equiv 0(\mathrm{mod}3)$
    • Base Case:
      • $f(MI)=1$
      • $3\nmid 1$
    • Induction Hypothesis:
      • For any $f(x)$ in $H$, then for any cases, $3\nmid f(x)$.
      • Assume that $f(x)=1,3(\mathrm{mod}3)$
    • Induction Step:
      • Case 1:
        • If $Mx\in H$ then $Mxx\in H$.
        • $f(Mxx)=2f(x)$
        • This is because the $M$ obviously won't be counted in the counter of $I$.
        • So we just double the end, which will be the same.
        • Case 1: $f(x)=1$
          • $2f(x)=2(\mathrm{mod}3)$
• Solution
• 2b
  • Proceed by structural induction.
  • Base Case:
    • $MI\in H$
    • $f(MI)=1$
    • $1\not\equiv 0(\mathrm{mod}3)$
  • Induction Hypothesis:
    • Combined strategy
    • Suppose that $x\in H$ and $f(x)\not\equiv 0(\mathrm{mod}3)$
    • C1)
      • We that $f(c_1(x))=2f(x)$
      • If $f(x)\not\equiv 0(\mathrm{mod}3)$
        • Then it's either $1$ or $2$. Why? Because the only remainders from dividing by $3$, is $1$ or $2$.
        • Then:
        • $f(x)\equiv 1(\mathrm{mod}3)$
          • This means $2f(x)\equiv 2(\mathrm{mod}3)$
        • $f(x)\equiv 2(\mathrm{mod}3)$
          • This means $2f(x)\equiv 4(\mathrm{mod}3)$
          • Then $4\mathrm{\%}3$ is $2$ as a remainder so:
          • $2f(x)\equiv 2(\mathrm{mod}3)$
        • The above cases are not congruent to $0(\mathrm{mod}3)$.
    • C2 and C3)
      • $f(c_2(x))=f(x)$
      • $f(c_3(x))=f(x)$
      • These constructors don't change the number of $I$'s.
      • If they're equal then none of these cases here are $\not\equiv 0(\mathrm{mod}3)$
    • C4)
      • $f(c_4(x))=f(x)-3$
      • We know that $3$ $I$'s are removed.
      • $3\equiv 0(\mathrm{mod}3)$
      • So we get $f(x)-3\equiv f(x)(\mathrm{mod}3)$
      • That's $\not\equiv 0(\mathrm{mod}3)$
    • So we can see that none of these cases are congruent to $0(\mathrm{mod}3)$.