MAT102 Tutorial W12

• 1: Determine if these functions are injective, surjective or bijective.

  • a: $f:\mathbb{N}\setminus \{3\}\to \mathbb{N}\times \mathbb{N},f(n)=(\frac{2n^2-n-13}{n-3},2n+5)$
    • To prove it's injective:
      • Suppose we have $f(a)=f(b)$
      • We want to show that if $f(a)=f(b)$ then $a=b$
      • $(\frac{2a^2-a-13}{a-3},2a+5)=(\frac{2b^2-b-13}{b-3},2b+5)$
      • This means:
        • $\frac{2a^2-a-13}{a-3}=\frac{2b^2-b-13}{b-3}$
        • $(b-3)(2a^2-a-13)=(a-3)(2b^2-b-13)$
        • $2a^{2}b-ab-13b-6a^2+3a+39=2b^{2}a-ba-13a-6b^2+3b+39$
        • $2a^{2}b-13b-6a^2+3a+39=2b^{2}a-13a-6b^2+3b+39$
        • $2a^{2}b-13b-6a^2+3a+39=2b^{2}a-13a-6b^2+3b+39$

        ---

        • $2a+5=2b+5$
        • $a=b$
        • True
    • Surjective:
      • We want to find $n\in \mathbb{N}\setminus \{3\}$ such that $f(n)=(x,y)$.
      • Let $(x,y)$ be arbitrary.
      • Let $x=\frac{2n^2-n-13}{n-3}$ and $y=2n+5$
      • Solving for $n$
      • $y=2n+5$
      • $y-5=2n$
      • $\frac{y-5}{2}=n$
      • $\frac{(y-5)-\frac{1}{2}(y-5)-13}{\frac{1}{2}(y-5)-3}$
      • $\frac{y-5-\frac{1}{2}y+\frac{5}{2}-13}{\frac{1}{2}y-\frac{5}{2}-3}$
      • $\frac{\frac{1}{2}y-\frac{31}{2}}{\frac{1}{2}y-\frac{1}{2}}$
      • $\frac{\frac{1}{2}y-\frac{31}{2}}{\frac{1}{2}(y-1)}$
  • b: $g:{\mathbb{Z}}_3\times {\mathbb{Z}}_5\to {\mathbb{Z}}_7,g(a,b)=3a+b$
    • Injective:
      • Let us have $g(a,b)=g(c,d)$
      • It must be the case that $a,b=c,d$ for this to be injective
        - $3a+b=3c+d$
  • c: $G(f)=\{(x,f(x)):x\in X\},f:x\to y$
    • $g:G(f)\to x$
    • $g(x,f(x))=x$

    ---

    • Left inverse
    • let $h:x\to G(f)$
      • Mapping backwards for inverse
    • such that $h(x)=(x,f(x))$
      • Take thei input and spit out the original.
    • Right inverse
    • $h\circ h(x)=x⟹f(h(x))=x$
    • Let $h:x\to G(f)$
    • $h(x)=(x,f(x))$
    • So the inverse of the function is $h^{-1}=(x,f(x))$
    • $h$ is the inverse of $g$. So $g$ is bijective

• Definitions:

  • Left and Right Inverse:
  • Let $f:x\to y,g:y\to x$ and $h:y\to x$
  • $g$ is a left inverse of $f$ if $g\circ f(x)=x$
  • $h$ is a right inverse of $f$ if $f\circ h(x)=x$
  • If you have a left and right inverse, you have a bijection.
  • If the left and right inverse are the same, then that is the inverse for the function.

• Show that $\mathbb{N}\times \mathbb{N}$ is countable

  • Theorem:
    • A countable union of countable sets is still countable
  • Proof:
    • Let $A_n=\{(r,s)\in \mathbb{N}\times \mathbb{N}:r+s=n\}$
    • Example $A_1=\mathrm{\varnothing }$
    • $A_3=\{(1,2),(2,1)\}$
    • Any $A_n$ is finite.
    • Notice that $A_n$ is countable because it's finite.
    • By the theorem:
      • $\bigcup _{n=1}^{\mathrm{\infty }}{A}_n$
      • Eventually this will form $\mathbb{N}\times \mathbb{N}$
      • That's it, if $A_n$ is countable and the union of any $A_n$ is countable. Since $A_n=\mathbb{N}\times \mathbb{N}$, then $\mathbb{N}\times \mathbb{N}$ is countable.

• Show that $(0,1]$ is uncountable.

  • Proof:
  • Suppose for the sake of contradiction, that $(0,1]$ is countable. This means there is a bijection between $(0,1]$ and $\mathbb{N}$.
  • Cantor's Diagonalization Theorem
    • $f(1)=0.11$
    • $f(2)=0.21$
    • $f(3)=0.34$
    • We construct a number with a decimal place different by $1$ to every other number.
    • This means this must be different from every other number here.
    • $x=0.22$ would be different from all other numbers here.
  • Construct $x\in (0,1]$ as follows:
    • $x_i$ being the $i^{\text{th}}$ digit after the decimal.
    • $$x_i=\{\begin{array}{ll}{a}_2+1& \end{array}$$
    • Notice $x_i$ is not mapped by $f$. Thus it is not surjective.