MAT102 Term Test 1 Prep

Functions

• a: $f:\mathbb{N}\setminus \{3\}\to \mathbb{N}\times \mathbb{N},f(n)=(\frac{2n^2-n-13}{n-3},2n+5)$
  • Injective
    • $f(a)=f(b)$
    • Want to show that $a=b$
    • $(\frac{2a^2-a-13}{a-3},2a+5)=(\frac{2b^2-b-13}{b-3},2b+5)$
    • By in class proof we know if one component is injective, so is the composition
    • $2a+5=2b+5$
    • $2a=2b$
    • $a=b$
    • Injective
  • Surjective
    • $f(a)=(q,r)$
    • $(\frac{2a^2-a-13}{a-3},2a+5)=(q,r)$
    • $\frac{2a^2-a-13}{a-3}=q$
      • $2a^2-a-13=q(a-3)$
      • $2a^2-a=q(a-3)+13$
      • $2a^2-a=qa-3q+13$
      • $2a^2-a-qa+3q=13$
      • $f(a,q)=2a^2-a-qa+3q$
      • $2(\frac{r-5}{2}{)}^2-(\frac{r-5}{2})-q(\frac{r-5}{2})+3q=13$
      • $2(\frac{(r-5{)}^2}{4})-(\frac{r-5}{2})-q(\frac{r-5}{2})+3q=13$
      • $\left(\frac{(r-5{)}^2}{2}\right)-\left(\frac{r-5}{2}\right)-q\left(\frac{r-5}{2}\right)+3q=13$
      • $(r-5{)}^2-(r-5)-q(r-5)+6q=26$
      • $(r-5{)}^2-(r-5)-qr-5q+6q=26$
      • $(r-5{)}^2-r+5-qr-11q=26$
      • $(r-5{)}^2-r-qr-11q=21$
      • $(r-5)(r-5)-r-qr-11q=21$
      • $(r^2-10r+25)-r-qr-11q=21$
      • $r^2-10r+25-r-qr-11q=21$
      • $r^2-11r+25-qr-11q=21$
      • $r^2-11r-qr-11q=-4$
      • $g(q,r)=r^2-11r-qr-11q+4$
    • $2a+5=r$
      • $2a=r-5$
      • $a=\frac{r-5}{2}$
    • Counterexample:
      • $6$ is not reachable
      • $8$ is also not reachable
      • $(2n^2-n-13)$

Tutorial

• MAT102 Tutorial W4B
• 1
  • $f:{\mathbb{R}}^2\to \mathbb{R}$
  • $f(x,y)=\frac{1}{x^2+y^2+1}$
  • a
    • Injective
      • $f(a,b)=f(x,y)⟹(a,b)=(x,y)$
      • $\frac{1}{a^2+b^2+1}=\frac{1}{x^2+y^2+1}$
      • $a^2+b^2+1=x^2+y^2+1$
      • $a^2+b^2=x^2+y^2$
      • $a^2=x^2+y^2-b^2$
      • $x^2+y^2-b^2+b^2=x^2+y^2$
      • $x^2+y^2=x^2+y^2$
      • Since addition is commutative this is not injective
      • Counterexample:
        • $f(1,0)=f(0,1)$
    • Surjective
      • Counterexample
        • $0\in \mathbb{R}$
        • However $\frac{1}{x^2+y^2+1}\ne 0$ for any $x,y\in {\mathbb{R}}^2$
    • Bijective
      • Not injective and surjective, so not bijective
  • b
    • Image of ${\mathbb{R}}^2$ for $f$
    • $x^2+y^2+1>0$
    • $x^2+y^2>-1$
    • $x^2\ge 0$
    • $y^2\ge 0$
    • $x^2+y^2$ is always greater than $-1$
    • Output is $\frac{1}{1}\to \frac{1}{\mathrm{\infty }}=0$
    • $(0,1]$ is the range
    • $U=\{x,y:x\ge 0,y\ge 0\}$
    • $f(U)=o\in (0,1]$
    • Where $o$ is our output
    • $f^{-1}(f(U))$
    • $f^{-1}(o\in (0,1])$
      • Everything that maps to $(0,1]$
      • It's just ${\mathbb{R}}^2$
• 2
  • $F$ is $\{f:[0,1]\to \mathbb{R}\}$
  • $T:F\to F$ as $[T(f)](x)=f(x)+2f(1-x)$
  • a
    • For an arbitrary $h\in F$ suppose that $[T(h)](x)=0$ for all $x\in [0,1]$
    • Prove that $h(x)=0$ for all $x\in [0,1]$
    • $[T(h)](x)=0$
    • $h(x)+2h(1-x)=0$
    • $[T(h)](1-x)=0$
    • $h(1-x)+2(h(x))=0$
    • $h(x)=-2h(1-x)$
    • $h(1-x)+2(-2h(1-x))=0$
    • $h(1-x)+4h(1-x)=0$
    • $5h(1-x)=0$
    • $h(1-x)=0$
    • $h(x)+2(0)=0$
    • $h(x)=0$
    • This shows that $h(x)$ is $0$ for all $x\in [0,1]$
  • b
    • Is $T$ injective
    • $[T(f)](x)=[T(g)](x)$ then $g=f$
    • Linear Method
      • $f(x)+2f(1-x)=g(x)+2g(1-x)$
      • $f(1-x)+2f(x)=g(1-x)+2g(x)$
      • $f(x)+2f(1-x)=g(x)+2g(1-x)$
      • $2f(1-x)+4f(x)=2g(1-x)+4g(x)$
      • $f(x)-4f(x)=g(x)-4g(x)+2g(1-x)-2g(1-x)$
      • $-3f(x)=-3g(x)$
      • $f(x)=g(x)$
      • We're done
    • Other method
      • $[T(f)](x)=[T(g)](x)$
      • $[T(f-g)](x)$
      • By part A
      • $h=f-g$
      • $[T(h)](x)=0$
      • $f(x)-g(x)=0$
      • $f(x)=g(x)$
  • c
    • Is $T$ surjective
    • $T(f)=n$ for an arbitrary $n$
    • Since $n\in F$ then $n:[0,1]\to \mathbb{R}$
    • $[T(f)](x)=n(x)$
    • $f(x)+2f(1-x)=n(x)$
    • $[T(f)](1-x)=n(1-x)$
    • $f(1-x)+2f(x)=n(1-x)$
    • $f(x)+2f(1-x)=n(x)$
    • $2f(1-x)+4f(x)=2n(1-x)$
    • $f(x)-4f(x)=n(x)-2n(1-x)$
    • $-3f(x)=n(x)-2n(1-x)$
    • $f(x)=-\frac{1}{3}n(x)-\frac{2}{3}n(1-x)$
    • $(-\frac{1}{3}n(x)-\frac{2}{3}n(1-x))+2f(1-x)=n(x)$
    • $2f(1-x)=n(x)-(-\frac{1}{3}n(x)-\frac{2}{3}n(1-x))$
    • $2f(1-x)=n(x)+\frac{1}{3}n(x)+\frac{2}{3}n(1-x)$
    • $2f(1-x)=\frac{4}{3}n(x)+\frac{2}{3}n(1-x)$
    • $f(1-x)=\frac{2}{3}n(x)+\frac{1}{3}n(1-x)$
    • $(-\frac{1}{3}n(x)-\frac{2}{3}n(1-x))+2(\frac{2}{3}n(x)+\frac{1}{3}n(1-x))=n(x)$
    • $(-\frac{1}{3}n(x)-\frac{2}{3}n(1-x))+(\frac{4}{3}n(x)+\frac{2}{3}n(1-x))=n(x)$
    • $(-\frac{1}{3}n(x)\cancel{-\frac{2}{3}n(1-x)})+(\frac{4}{3}n(x)\cancel{+\frac{2}{3}n(1-x)})=n(x)$
    • $n(x)=n(x)$
    • It's surjective
• 3
  • Let $A,B\subseteq \mathbb{R}$ and $f:\mathbb{R}\to \mathbb{R}$ is an arbitrary function
  • Find out if $f(A\cap B)=f(A)\cap f(B)$
  • $A=[-1,0]$
  • $B=\{10\}$
  • $f(A\cap B)=0$
  • $f(A)=\{x^2:-1\le x\le 0\}$
  • $f(B)=\{100\}$
  • See that $f(A\cap B)\ne f(A)\cap f(B)$
  • $f(A\cap B)\subseteq f(A)\cap f(B)$
  • $\subseteq$
    • Let $x\in f(A\cap B)$
    • Let $y\in A\cap B$
    • Because $y\in A$ and $y\in B$
    • Then we get that $y$ produces $f(A)$ where $x\in f(A)$
    • We also get that $y$ produces $f(B)$ where $x\in f(B)$
    • So we can get that $x$ produces $f(A)\cap f(B)$

Composition Proof Surjective

• If one component function is not surjective, then the whole composition isn't surjective.
  • $h:A\to B\times B$
  • $h(x)=(f(x),g(x))$
  • Example:
    • $h:\mathbb{Z}\to \mathbb{Z}\times \mathbb{Z}$
    • $h(x)=(x^2,x)$
    • Surjective counterexample:
      • Let $n$ be arbitrary
      • $(-3,n)$ is never reached
      • $-3$ will never be reached by $x^2$
  • Assume that $f(x)$ is not surjective
    • So let $D$ be the domain of $f(x)$ and take the complement as $D^c:D^c\subseteq B$ and let this be $C$
    • So $C\subseteq B$ but $C$ is the set of all values in the codomain that cannot be reached by $h(x)$, so then $h(x)$ is not surjective due to $f(x)$ not being surjective.
  • For the sake of contradiction, suppose $f(x)$ and $g(x)$ are surjective
    • $f(x)=n$
    • $g(x)=u$
      • For an arbitrary $n,u\in B$
    • Then $h(x)=(n,u)$

Relations

• 04RelationsExercises_Students.pdf
• (04RelationsExercises_Students, p.1)
• There are no positive integer solutions to the equation $x^2=8y^2$
• Contradiction
  • For the sake of contradiction suppose there are integer solutions to $x^2=8y^2$
  • Notice that $x^2=8y^2$
  • $x$ is even
  • $x=2k$
  • $(2k{)}^2=8y^2$
  • $4k^2=8y^2$
  • $k^2=2y^2$
  • $y$ is even
  • $y=2\ell$
  • $k^2=2(2\ell {)}^2$
  • $k^2=8{\ell }^2$
  • Now we have the same equation as the beginning
  • We can keep on doing this and have an infinite descent case.
• Popular Set
  • 1
    • Show that $⊢$ is transitive
    • $x⊬x$
      • $x-x\in P$
      • By $P_1$ we know that $0\notin P$
      • It's not reflexive
    • $x⊢y,y⊢x$
      • $y-x\in P$
      • $x-y\in P$
      • $-y+x\in P$
      • $-(y-x)\in P$
      • By $P_3$ we have that $x\in P$ or $-x\in P$ but not both.
      • So if $y-x=k$
      • We have $k\in P$ and $-k\in P$, which is a contradiction.
      • It's not symmetric
    • $x⊢y,y⊢z:x⊢z$
      • $y-x\in P$
      • $z-y\in P$
      • Implies that $z-x\in p$
      • $a=y-x$
      • $b=z-y$
      • $a+b\in P$
      • $(y-x)+(z-y)\in P$
      • $y-x+z-y\in P$
      • $\cancel{y}-x+z\cancel{-y}\in P$
      • $-x+z\in p$
      • $z-x\in P$
      • Proved
  • 2
    • If $c\in P$ and $x⊢y$ then $cx⊢cy$
      • $x⊢y$
        • $y-x\in P$
      • $cx⊢cy$
        • $cy-cx$
      • $c\in P$ so by $P_1$ it's not $0$.
      • $c(y-x)$
      • $cy-cx\in P$ which shows us that it's in $P$.
      • This is because by $P_2$ for every $x,y$ we have $xy\in P$
      • So we can multiply.
    • If $c\notin P$
      • So $-c\in P$
      • $cy⊢cx$
        • $cx-cy$
      • $x⊢y$
        • $y-x$
        • $-c(y-x)$
        • $-cy+cx$
        • $cx-cy\in P$
  • 3
    • If $x⊢y$ and $u⊢v$
    • Then $x+u⊢y+v$
    • $x⊢y$
      • $y-x$
    • $u⊢v$
      • $v-u$
    • By $P_2$ for every $x,y\in P$ we have $x+y\in P$
    • $x,u⟹x+u\in P$
    • $y,v⟹y+v\in P$
    • By $P_3$ we know if somethings in $P$, then the negative of it, is not.
    • So we know these are valid
    • $a=x+u$
    • $b=y+v$
    • $a,b\in P$
    • $a⊢b$
      • $b-a\in P$
      • $(y+v)-(x+u)\in P$
    • $x+u⊢y+v$
      • $(y+v)-(x+u)\in P$
    • We're done
  • 4
    • If $x,y\in P$ and $x⊢y$ show that $x^2⊢y^2$
    • $x⊢y$
      • $y-x$
    • By $P_2$ for every $x,y\in P$ we have $xy\in P$
    • So $x\cdot x\in P$ if $x\in P$
    • This holds true for $x^2,y^2$
    • So $y^2-x^2\in P$
  • 5
    • If $x,y\in P$ and $x⊢y$ show that $y^{-1}⊢x^{-1}$
    • By $P_2$ we know that if $x,y\in P$ then we have $x^{-1}\in P$
    • $x⊢y$
      • $y-x$
      • $y^{-1}-x^{-1}$
      • $\frac{1}{y}-\frac{1}{x}$
      • $\frac{x}{xy}-\frac{y}{xy}$
      • $\frac{x-y}{xy}$
    • $y^{-1}⊢x^{-1}$
      • $x^{-1}-y^{-1}$
      • $\frac{1}{x}-\frac{1}{y}$
      • $\frac{y}{xy}-\frac{x}{xy}$
      • $\frac{y-x}{xy}$
      • $y-x\in P$
      • $(xy{)}^{-1}\in P$

Tutorial W3

• 1
  • Relation $R$ on a set $A$
    • Equivalence if it's reflexive, symmetric and transitive
      • $=$ sign
    • Weak partial order if it's reflexive, anti-symmetric and transitive
      • $\le$ sign
    • Strong partial order if it's irreflexive, anti-symmetric and transitive
      • $<$ sign
  • Define the relation $\preccurlyeq$ on ${\mathbb{R}}^{\ast }\times {\mathbb{R}}^{\ast }$ as $(a,b)\preccurlyeq (c,d)⟺\log \left(\frac{a+b}{c+d}\right)<0$
  • Reflexive
    • $(a,b)\preccurlyeq (a,b)$
    • $\log \left(\frac{a+b}{a+b}\right)<0$
    • $\log \left(1\right)<0$
    • $0\nless 0$
    • right now we can just say it's a strong partial order as it's irreflexive
  • Symmetric
    • $(a,b)\preccurlyeq (c,d)$
      • $\log \left(\frac{a+b}{c+d}\right)<0$
    • $(c,d)\preccurlyeq (a,b)$
      • $\log \left(\frac{c+d}{a+b}\right)<0$
    • Anti-symmetric
    • Because $\log (n)=-\log \left(\frac{1}{n}\right)$
    • So $(a,b)\preccurlyeq (c,d)$ and $(c,d)\preccurlyeq (a,b)$
    • it must mean that $(a,b)=(c,d)$
    • Which is the case
  • Transitive
    • $(a,b)\preccurlyeq (c,d)$
      • $\log \left(\frac{a+b}{c+d}\right)<0$
      • $\log (a+b)-\log (c+d)<0$
    • $(c,d)\preccurlyeq (e,f)$
      • $\log \left(\frac{c+d}{e+f}\right)<0$
      • $\log (c+d)-\log (e+f)<0$
    • $(a,b)\preccurlyeq (e,f)$
      • $\log \left(\frac{a+b}{e+f}\right)<0$
      • $\log (a+b)-\log (e+f)<0$
    • $\log (a+b)-\log (c+d)<0$
      • $\log (a+b)<\log (c+d)$
    • $\log (c+d)-\log (e+f)<0$
      • $\log (c+d)<\log (e+f)$
    • $\log (a+b)<\log (c+d)<\log (e+f)$
    • Which means that $\log (a+b)⪇\log (e+f)$
    • Which shows transitivity
  • So this is a strong partial order.
• 2
  • $\le$ is a weak partial order on $\mathbb{R}$
  • Supremums and infimums
  • Define a relation $\sim$ on $\mathcal{P}(\mathbb{R})=\{X:X\subseteq \mathbb{R}\}$ as $A\sim B⟺sup(A)=sup(B)\wedge inf(A)=inf(B)$
  • 1
    • Why is $\sim$ and equivalence relation
    • If we take two sets, and the infimums and supremums are the same, as in the lowest upper bound and greatest lower bound are the same, then we have the same set.
    • Example:
      • $A=\{1,2,3\}$
      • $B=\{1,2,3\}$
      • Working in $\mathbb{N}$
      • we have $inf(A)=0=inf(B)$
      • Also $sup(A)=4=sup(B)$
    • This is why without proof, we can say it's an equivalence relation
    • Proof:
      • Reflexive
        • $A\sim A$
        • $sup(A)=sup(A)$
        • and the $inf(A)=inf(A)$
        • This is trivially true
      • Symmetric
        • $A\sim B$ and $B\sim A$
        • $A\sim B$
          • $sup(A)=sup(B)$
          • and the $inf(A)=inf(B)$
        • $B\sim A$
          • $sup(B)=sup(A)$
          • and the $inf(B)=inf(A)$
        • This obviously is true
        • It's not anti-symmetric because the elements in-between may differ
        • Example:
          • $A=\{2,4,6\}$
          • $B=\{2,3,4,6\}$
          • Working in a natural space $\mathbb{N}$
          • The supremums and infimums are the same, but the sets are not.
      • Transitive
        • $A\sim B$ and $B\sim C$ then $A\sim C$
        • $A\sim B$
          • $sup(A)=sup(B)$
          • and the $inf(A)=inf(B)$
        • $B\sim C$
          • $sup(B)=sup(C)$
          • and the $inf(B)=inf(C)$
        • Want to show $A\sim C$
          • $sup(A)=sup(C)$
          • and the $inf(A)=inf(C)$
        • If $sup(A)=sup(B)$ and $sup(B)=sup(C)$ then $sup(A)=sup(C)$
        • The same argument applies for $inf(A)=\dots$
  • 2
    • Describe the set of equivalence classes
    • $[A]=\{X\in \mathcal{P}(\mathbb{R}):X\sim A\}$
    • This is any set from the power set of real number which relates to the given equivalence set $A$.
  • 3
    • Is the set $(0,8)$ in the equivalence class of $[0,8]$ under $\sim$?
    • The equivalence class is saying any set from the power set with lower bound $0$ and upper bound $8$.
    • This is included as $(0,8)\in \mathcal{P}(\mathbb{R})$ and the upper and lower bounds are the same as those of $[0,8]$

Tutorial W2

• 1
  • Can these be true at the same time?
  • First let's check if the negation of one is the other
  • $\mathrm{\forall }x\in \mathbb{Z},(\mathrm{\neg }P(x)⟹Q(x))$
  • $\mathrm{\neg }(\mathrm{\forall }x\in \mathbb{Z},(\mathrm{\neg }P(x)⟹Q(x)))$
  • $\mathrm{\exists }x\in \mathbb{Z}\mathrm{\neg }(P(x)\vee Q(x)))$
  • $\mathrm{\exists }x\in \mathbb{Z},(\mathrm{\neg }P(x)\wedge \mathrm{\neg }Q(x))$
  • See that the second statement is the negation of the first, so this cannot be the same.
• 2
  • $A=\{x\in \mathbb{Z}:\mathrm{\exists }y\in \mathbb{Z},xy>0\}$
  • $B=\{x\in \mathbb{Z}:\mathrm{\exists }y\in \mathbb{Z},xy=0\}$
  • $P(x)=x\in A$
  • $Q(x)=x\in B$
  • a
    • Rewrite $\ast$ and $\ast \ast$ as $\cap ,X^C$ and $\mathrm{\forall },\mathrm{\exists },\in ,⟹$
    • $\ast$
      • $\mathrm{\forall }x\in \mathbb{Z},(\mathrm{\neg }P(x)⟹Q(x))$
        • If we are not in $A$ we are in $B$
      • $\mathrm{\forall }x\in \mathbb{Z},x\notin A⟹x\in B$
    • $\ast \ast$
      • $\mathrm{\exists }x\in \mathbb{Z},\mathrm{\neg }P(x)\wedge \mathrm{\neg }Q(x)$
      • $\mathrm{\exists }x\in \mathbb{Z},x\in A^c\cap B^c$
  • b
    • Part $2$ is true if $A$ and $B$ don't bisect the universe

Functions Worksheet

• Suppose $f:A\to B$
• $U\subseteq A$ is an arbitrary set
• How is $U$ related to $f^{-1}(f(U))$
• Is one a subset of the other
• $f(U)$ is the image
• $f^{-1}(f(U))$ is the preimage of the image
• $U\subseteq f^{-1}(f(U))$ because of non-surjective functions
• Consider the example
• $f:\mathbb{R}\to \mathbb{R}$
• $f(x)=x^2$
• See that the preimage of the image results in only non-negative numbers.

Functions Exercises

• 1
  • $f:\mathbb{R}\to \mathbb{R}$
  • $f(x)=\sin x$
  • Find $f([-2\pi ,2\pi ])$ and $f^{-1}(0)$
  • $u=[-2\pi ,2\pi ]$
  • $\sin (-2\pi )=0$
  • $\sin (2\pi )=0$
  • $\sin (-\frac{3\pi }{2})=1$
  • $\sin \left(\frac{3\pi }{2}\right)=-1$
  • $f(u)=[-1,1]$
  • $f^{-1}(0)$ is anything that maps to $0$
  • $\sin x=0$
  • $x=\arcsin 0$
  • $x=z\pi$ for $z\in \mathbb{Z}$
• 2
  • $g:\mathbb{Z}\times \mathbb{Z}\to \mathbb{Z}$
  • as $g(x,y)=xy$
  • $U=\{(x,y)\in {\mathbb{Z}}^2:x^2+y^2\le 4\}$
  • $P$ is the set of primes
  • find $g(U)$ and $g^{-1}(P)$
  • $U$, the radius of the circle is $2$
  • $g(U)=\{-1,0,1\}$
  • $g(x,y)$'s lower bound is $0\cdot 0=0$
  • The upper bound is $2\cdot 2=4$
  • $g(U)=[0,4]$
  • $g^{-1}(P)$
  • Since primes have only $1$ and $P$ as factors
  • It would be $V=\{\{1\}\times P\}$
• 3
  • $h:\mathbb{R}\to {\mathbb{R}}^2$ by $h(x)=(x^3,x^2)$
  • Find $h^{-1}([-1,1{]}^2)$
  • I notice that with $[-1,1]\times [-1,1]$ we will get $(-1,-1)$ as an output. However there is no $x$ value for which $x^2=-1$
    • As: $x^2=-1⟹x=\sqrt{-1}$ which violates that the space under a $\sqrt{}$ must be non-negative
  • Otherwise, $h^{-1}([-1,1{]}^2)=[-1,1]$
• 6
  • a
    • $f:\mathbb{R}\to \mathbb{R}$
    • $f(x)=\left|x\right|$
    • Injective
      • Not injective
      • Counterexample:
        • $f(-1)=f(1)$
        • $|-1|=\left|1\right|$
        • $1=1$
        • True
        • However the inputs are not the same
    • Surjective
      • See that $-1$ in the codomain has no element from the domain mapping to it.
      • $\left|x\right|\ne -1$
  • b
    • $f:{\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+}\to {\mathbb{Z}}^{+}$
    • $f(x,y)=min(x,y)$
    • Injective
      • Counterexample:
        • $f(2,1)=f(1,2)$
        • $1=1$
        • But inputs are different
    • Surjective
      • $f(x,y)=n$ for an arbitrary $n$
      • $min(x,y)=n$
      • If $x<y$ and $x=n$ we are done
      • Assume $x>y$
      • Now we can show that if $y=n$ then we get that $min(x,y)=n$
      • if $x=y$ and $x=n$ then we are done.