MAT102 Lecture 11B

• 05FunctionIExercises_Student.pdf
• In class exercise
  • $f:A\to B$
  • If $U\subseteq A$ how is $U$ related to $f^{-1}(f(U))$
  • Is one a subset of another?
  • Are they equal?
  • I know that the image of the set is like the range
  • The pre-image is anything that maps to an element in it.
  • $f(A)=B$
  • $f^{-1}(B)$ does not necessarily mean $A$
  • Why:
    • If the function isn't injective, there's a value missed from $A$ which doesn't map to $B$
  • $U\subseteq f^{-1}(f(U))$
  • Proof:
    • Let $x\in f^{-1}(U)$
    • $f(x)\in U$
    • The output of $f(x)\in B$
    • $f(A)=B$
    • $f(U)=B$
  • Solution:
    • Example:
      • $f:\mathbb{R}\to \mathbb{R},f(x)=x^2$
      • $U=\{0,2\}$
      • $f(U)=\{0,4\}$
      • $f^{-1}(f(U))=f^{-1}(\{0,4\})$
      • $f^{-1}(f(U))=\{-2,0,2\}$
    • Claim:
      • If $f:A\to B$ and $U\subseteq A$
      • Then $U\subseteq f^{-1}(f(U))$
      • Subset Inclusion
      • $\subseteq$
        • Let $x\in U$
        • $f^{-1}(v)=\{x\in a:f(x)\in v\}$
        • $f^{-1}(f(u))=\{x\in a:f(x)\in f(u)\}$
        • Now we want to show that $f(x)\in f(U)$
        • If $x\in U$ then $f(\{x\in A:x\in U\})\in f(U)$ will be true.
      • $U=f^{-1}(f(U))$ when $U$ is injective
      • If not, then when we do the pre-image, there can be something else mapping to the same output.
• Theorem:
  • Let $f:A\to B$
  • #tk term test 1 would be questions until this
  • $f$ is injective $⟺$ $\mathrm{\forall }u\in A$, $u=f^{-1}(f(U))$
  • $⟹$
    • If $f$ is injective, then $f(A)=B$
    • The image of the entire domain is the codomain
    • $\subseteq$
      • Let $x\in U$
      • $f^{-1}(v)=\{x\in a:f(x)\in v\}$
      • $f^{-1}(f(u))=\{x\in a:f(x)\in f(u)\}$
      • Now we want to show that $f(x)\in f(U)$
      • If $x\in U$ then $f(\{x\in A:x\in U\})\in f(U)$ will be true.
    • $\supseteq$
      • Let $x\in f^{-1}(f(U))$ so at least it would be $\subseteq U$
      • so $x\in f^{-1}(\{f(x):x\in U\})$
      • $x\in \{x\in A:\{f(x):x\in U\}\in U\}$
      • $x\in \{x\in A:U\}$
  • $⟸$ #tk
    • Contrapositive
    • $f$ is injective $⟺$ $\mathrm{\forall }U\subseteq A$, $u=f^{-1}(f(U))$
    • Contrapositive
    • $\mathrm{\exists }U\subseteq A$, $u\ne f^{-1}(f(U))$ $⟺$ $f$ is not injective
      • This is essentially surjectivity, we're saying that there is an element of the pre-image of the image where it maps to an element that wasn't in the image.
  • Solution:
    • Suppose $f$ is injective
    • To show equality, we'll show that $f^{-1}(f(U))\subseteq U$
    • Since the other inclusion is already proven.
    • $\subseteq$
      • Let $x\in f^{-1}(f(U))=\{x\in A:f(x)\in f(U)\}$
      • Since $x$ is in that set.
      • Then $f(x)\in \underset{\text{Image}}{\underbrace{f(U)}}$
        • $f(U)=\{f(x):x\in U\}$
        • Can't use injectivity yet
      • $f(x)\in \{f(y):y\in U\}$
      • So there $\mathrm{\exists }y\in U:f(x)=f(y)$
      • Since $f$ is injective, if we have two outputs equal, the inputs are equal
      • $f(x)=f(u)$ so $x=u\in U$
• 1
  • a
    • $A=\mathbb{Z}$
    • This is any $x\in \mathbb{R}:x\in \mathbb{Z}$, we want it to be in both.

      	left=-0.5; right=10;
      	top=10; bottom=-0.5;
      	---
      	y=0|dashed
      	(0,1)
      	(1,1)
      	(2,1)
      	(3,1)
      	(4,1)
      	(5,1)
      	(6,1)
      	(7,1)
      	(8,1)
      	(9,1)
      	(10,1)
      	(-1,1)
      

  • b
    • $A=[-2,0]\cup [1,2]$
    • A line at $y=1$ with this restriction on it's domain

      	left=-3; right=10;
      	top=10; bottom=-0.5;
      	---
      	y=1|-2<=x<=0
      	y=1|1<=x<=2
      	y=0|x<=-2
      	y=0|0<=x<=1
      	y=0|1<=x
      

  • c
    • $A=\mathbb{Q}$
    • Two finely dotted lines
    • Essentially two lines

      	left=-3; right=10;
      	top=10; bottom=-0.5;
      	---
      	y=1
      	y=0
      

• 2
  • If ${\chi }_A$ is the characteristic function of…
  • ${\chi }_A^{-1}(\{1\})$
  • Since ${\chi }_A(x)=1$ if $x\in A$
  • then ${\chi }_A^{-1}(\{1\})$ is anything in $A$
  • ${\chi }_A^{-1}(\{1\})=A$
• 3
  • $A=\{1,2,3\}$
  • $|P(A)|=2^3-1$
  • $P(A)=\left\{\begin{array}{c}\{\mathrm{\varnothing }\},\{1\},\{2\},\{3\},\\ \{1,2\},\{1,3\},\{2,3\}\}\end{array}\right\}$
• 4
  • $U$ is a universe of discourse
  • $F(U)=\{f:U\to \{0,1\}\}$ be the set of all functions on $U$ that map onto $\{0,1\}$
  • Define $p:P(U)\to F(U)$ by $p(A)={\chi }_A$
  • Show that $p$ is a bijection
  • Injectivity:
    • To show injectivity, if we have two outputs being equal then the inputs are equal
    • $p(A)=p(B)$
    • ${\chi }_A={\chi }_B$
    • ${\chi }_A(x)={\chi }_B(x)$
    • $⟹$
      • Choose $a\in A$ and $b\in B$
      • ${\chi }_A(a)={\chi }_B(b)$
      • Since these functions are equal by assumption.
      • ${\chi }_A(a)=1$
      • and ${\chi }_B(b)=1$
      • So we're done.
    • $⟸$
      • Choose $a\in A$ and $b\in B$
      • Assumption functions are equal
      • ${\chi }_B(b)=1$ because $b\in B$
      • Functions are equal so, ${\chi }_A(a)=1$ as well.
    • This means $a=b$ so this is injective
    • Solution:
      • Assume $A,B\in P(U)$ and $p(A)=p(B)$
      • Show that $a=b$
      • So ${\chi }_A={\chi }_B$
      • $\subseteq$
        • Let $a\in A$
        • So ${\chi }_A(a)=1={\chi }_B(a)$
        • This shows us that $a\in B$
        • So $A\subseteq B$
  • Surjectivity: #tk
    • Fix $p(U)=n$ and show that there's always a solution
    • Definition
    • $p(U)$
      • That means there is some set $A\subseteq U$ or $A\in \mathcal{P}(A)$
      • Where it maps to ${\chi }_A$ as $f\in F(U)$
      • Pick $A$ as our set in the domain.
      • If I take the characteristic set of $A$, I get ${\chi }_A$.
      • Otherwise as $f:U\to \{0,1\}$
      • Get the pre-image as $V=\{1\}$
      • $p^{-1}(\{1\})=A$
      • Show that $p(A)={\chi }_A$
      • If $x\in A$
        • then we get $1$ from ${\chi }_A$
      • $x\notin A$
        • We get $0$ from ${\chi }_A$
    • It's a bijection