MAT102 Lecture 21

• If you're injective and bijective, you can have an invertible function.

  • Injective: $f(A)=B$
    

• Injective Proof

  • $f:\mathbb{Z}\to \mathbb{Z}\times \mathbb{Z},f(k)=(k^2,k^3)$
  • Suppose $f(n)=f(m)$
  • so then $(n^2,n^3)=(m^2,m^3)$
  • So them $n^2=m^2$ and $n^3=m^3$
  • So since $n^3=m^3$ we know that $n=m$
  • Why? because a negative will remain negative, so it's not like $n^2$ where we lose the negative numbers.
  • Here we prove that we have two inputs. So then we prove that if we have two inputs, and they're the same output, then the input was the same.
    • provingt it's a one-to-one function.

• Surjective Counterexample

  • $f:\mathbb{Z}\to \mathbb{Z}\times \mathbb{Z},f(k)=(k^2,k^3)$
  • Let $y=(-1,0)$. There is no $k\in \mathbb{Z}$ such that $k^2=-1$ and $k^3=0$
  • So it's not surjective

• For every theory about injectivity, there's a dual theory about surjectivity

• If $f:B\to C$ and $g:A\to B$ are functions and $f\text{o}g$ is surjective then:

  • Show $f$ is surjective
  • $A\to B\to C$
  • To show this, let $c\in C$ be arbitrary.
  • Since $f\text{o}g$ is surjective, there $\mathrm{\exists }a\in A:f(g(a))=c$
  • If $b=g(a)$ then $f(b)=c$, then $f$ is surjective.
  • Plug into $f$ and get $c$ out.

• Why does $g$ not need to be surjective?

  • $f:\mathbb{R}\to [0,\mathrm{\infty })$
  • $f(x)=x^2$
  • $g:[0,\mathrm{\infty })\to \mathbb{R}$
  • $g(x)=\sqrt{x}$
  • Not that $f\text{o}g:[0,\mathrm{\infty })\to [0,\mathrm{\infty })$
  • So $f(g(x))=(\sqrt{x}{)}^2=x$
  • This is surjective, the composition.
  • So $f\text{o}g$ is surjective.
  • But $g$ isn't surjective, cause we cannot take all $\mathbb{R}$ and get everything in $[0,\mathrm{\infty })$.

• $h:A\to B\times B$ as $h(x)=(f(x),g(x))$

  • If $f$ is injective, then $h$ is injective
    • proof
    • Suppose $f$ is injective, let $x,y\in A:h(x)=(f(x),g(x))=(f(y),g(y))=h(y)$
    • Thus $f(x)=f(y)$ and $g(x)=g(y)$
    • If $f$ is injective, then $x=y$ becaus e$f(x)=f(y)$
    • If you have one injective component, then everything is injective.

  ---

  • Suppose $h(a)=h(b)$
  • So $(f(a),g(a))=(f(b),g(b))$
  • $(f(a),g(a))=(f(b),g(b))$

  ---

  • If $f$ and $g$ are surjective, then $h$ is surjective.
  • Let $f:\mathbb{Z}\to \mathbb{Z},f(k)=k$
  • $g:\mathbb{Z}\to \mathbb{Z},g(k)=k$
  • Let $h:\mathbb{Z}\to \mathbb{Z}\times \mathbb{Z}:h(k)=(k,k)$
  • We can't have $(1,2)\to \mathbb{Z}$ because $h(k)$ says that it must be $(1,1)$.
  • $h$ is injective but neither $f$ or $g$ are injective
    • $f:(0,2\pi )\to \mathbb{R},f(x)=\cos x$
    • $g:(0,2\pi )\to \mathbb{R},g(x)=\sin x$
    • Both individually aren't injective, they don't pass the horizontal line test
    • but $h:(0,2\pi )\to {\mathbb{R}}^2$
    • $x\mapsto (\cos x,\sin x)$

• 1: Suppose that $f:A\to B$ is a function
  • a: Show that for every $U\subseteq A,U\subseteq f^{-1}(f(U))$
    • If $U\subseteq A$ then the image of $U$ is $f(U)=\{y\in B:\mathrm{\exists }x\in U,f(x)=y\}$
    • If $V\subseteq B$ then $f^{-1}(V)=\{x\in A:f(x)\in V\}$
    • $U\subseteq f^{-1}(\{f(x):x\in U\})$
    • We know that $f^{-1}(B)=A$
    • $U\subseteq f^{-1}(\{f(x):x\in U\})$
    • If $\{f(x):x\in U\}\subseteq B$ let this be $T$
    • So $U\subseteq f^{-1}(T)$
    • $f^{-1}(T)=A$
    • $U\subseteq A$
  • b: Give an explicit example of a function $f$ such that the above inclusion is strict; that is, $U⊊f^{-1}(f(U))$
    • let $f:\mathbb{R}\to [0,\mathrm{\infty }),x\mapsto x^2$
    • Let the image $U=\{2\}$
    • Then evaluating the image we get:
    • $f(U)=\{f(2)\}=\{2^2\}=4$
    • $f^{-1}(f(U))=f^{-1}(\{4\})=\{x\in \mathbb{R}:f(x)=4\}=\{x\in \mathbb{R}:x^2=4\}=\{-2,2\}$
    • Since the image is $U=\{2\}$ and the pre-image is $f^{-1}(f(U))=\{-2,2\}$.
    • Then we have that $U⊊f^{-1}(f(U))$ because $-2\in f^{-1}(f(U))$ but $-2\notin U$.
  • c: Show that $f$ is injective $⟺\mathrm{\forall }U\subseteq A,U=f^{-1}(f(U))$
    • $f$ is injective if and only if the image is a subset of the domain, and the image is exactly the preimage of the image.
    • $⟹$
      • If $f$ is injective then if we have $f(a)=f(b),a=b$
      • If $f$ is one-to-one.

Solution

• a
  • Note that $f^{-1}(f(U))=\{x\in A:f(x)\in f(u)\}$
  • Suppose $x\in U$, so $f(x)\in f(u)$ so $x\in f^{-1}(f(U))$
• b
  • Show in general that they're not always equal
  • Let $f:\mathbb{R}\to \mathbb{R},x\mapsto x^2$
  • Let $U=\{0,1\}$
  • So that $f(U)=\{0,1\}$
    • The image of $\{0,1\}$ is still $\{0,1\}$ because we square the $x$ and get our range.
  • The preimage: $f^{-1}(f(\{0,1\}))=f^{-1}(\{0,1\})=\{-1,1\}$
  • So we know that $\{0,1\}⊊f^{-1}(f(\{0,1\}))$
• c
  • $⟹$
    • Suppose $f$ is injective
    • Want to show that the preimage of the image of $U$ is a subset of $U$
    • $f^{-1}(f(U))\subseteq U$
    • Let $x\in f^{-1}(f(U))$ so $f(x)\in f(u)$
    • $f(x)\in f(u)$ if $x=u$ for some $u\in U$.
    • So let $u\in U:f(x)\in f(u)$
    • By injectivity, $x=u$, because the results are equal.
    • $x=u\in U$
    • Done
  • $⟸$
    • Contrapositive
    • Suppose if $f$ is not injective
    • Thus there are $x,y\in A:f(x)=f(y)$ but $x\ne y$
      • Two points mapping to the same thing
    • Let $U=\{x\}$ so that $\{x,y\}\subseteq f^{-1}(f(U))=f^{-1}(\{f(x)\})$
    • Thus, $u=\{x\}⊊\{x,y\}\subseteq f^{-1}(f(U))$