MAT102 Lecture 12B

• 1
  • If we have $A$ as finite and $f:A\to A$
  • Then $f$ must not be bijective
  • Example:
    • $A=\{1,2\}$
    • $f:\{1,2\}\to \{1,2\}$
      • $x\mapsto 1$
    • Not bijective
  • If $A$ is infinite, this doesn't apply.
  • #tk
    • Can you draw an injective map that's not surjective?
    • Prove the above.
    • Example:
      • $f:\mathbb{Z}\to \mathbb{Z}$
      • $n\mapsto 2n$
      • Injective, not surjective.
• 2
  • If $f:A\to B$ is injective, but not surjective:
  • We can't know, all we can say is $\left|A\right|\le \left|B\right|$
  • We can have an injective but not surjective map, with the same set.
    • $f:\mathbb{Z}\to \mathbb{R}$
  • To prove that $\left|A\right|<\left|B\right|$ we need to know that there is not a single surjection from $f:A\to B$, for any functions
• 3
  • What's countably infinite?:
    • The set of all atoms in the observsable universe
    • $P(A)$ where $A$ is the collection of all primes
      • $\left|A\right|$ is countably infinite
      • $A\subseteq \mathbb{Z}$
      • But the power set will be strictly bigger.
    • $\mathbb{R}\setminus \mathbb{Q}$
      • Irrational numbers are uncountably infinite.
      • Proof:
        • $\mathbb{R}\setminus \mathbb{Q}$ is uncountable
        • Contradiction
        • Suppose they're countable
        • This then means that the reals are countable
        • $\mathbb{R}=\mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q})$
        • So if $\mathbb{Q}$ is countable and $\mathbb{R}\setminus \mathbb{Q}$ is countable, then being a union of countable sets means that $\mathbb{R}$ is countable which isn't true.
    • $\{{\displaystyle \frac{a}{2^n}}:a\in \mathbb{Z},n\in \mathbb{N}\}$
      • This is it
      • Because we can count the integers and naturals.
      • Create a bijection
      • $f:\{{\displaystyle \frac{a}{2^n}}:a\in \mathbb{Z},n\in \mathbb{N}\}\hookrightarrow \mathbb{Z}\times \mathbb{N}$
      • $\frac{a}{2^n}\mapsto (a,n)$
      • $\mathbb{Z}\times \mathbb{N}$ is a countable union of countable sets
      • $\mathbb{Z}\times \mathbb{N}=\bigcup _{n=1}^{\mathrm{\infty }}\underset{\begin{array}{c}\text{This is countable}\\ \text{for a fixed }n\end{array}}{\underbrace{\{(z,n):z\in \mathbb{Z}\}}}$
      • Then you can count the union of the countable sets.
      • Then you can create a bijection.
      • You can also say that $\{{\displaystyle \frac{a}{2^n}}:a\in \mathbb{Z},n\in \mathbb{N}\}\subseteq \mathbb{Q}$.
    • If $\left|A\right|=\left|B\right|$ then $|P(A)|=|P(B)|$
    • #tk
• 4
  • $\frac{1}{1-x}|{}_{x=1}$
  • $\frac{1}{1-1}|{}_{x=1}=\mathrm{\infty }$
  • $\frac{1}{1-0}|{}_{x=0}=1$
  • $\frac{1}{1--1}|{}_{x=-1}=\frac{1}{2}$
  • $\frac{1}{n+1}$
  • $f:(0,1]\to (0,1),f(x)=\left\{\begin{array}{cc}\frac{\pi }{4}& x=1\\ x^2& \text{otherwise}\end{array}\right\}$
    • $f\left(\sqrt{\frac{\pi }{4}}\right)=f(1)=\frac{\pi }{4}$
    • Not bijective
  • $f:(0,1]\to (0,1),f(x)=\left\{\begin{array}{c}\frac{1}{1-x}\end{array}\right\}$
    • This doesn't work because nothing maps to $0$.
    • It's not surjective
  • $f:(0,1]\to (0,1),f(x)=\left\{\begin{array}{cc}x& x\ne \frac{1}{2}\\ 1& x=\frac{1}{2}\end{array}\right\}$
    • Nothing maps to $\frac{1}{2}$
    • So it's not surjective
  • $f:(0,1]\to (0,1),f(x)=\left\{\begin{array}{cc}\frac{1}{n+1}& x=\frac{1}{n},n\in \mathbb{N}\\ x& \text{otherwise}\end{array}\right\}$
    • Hilbert's hotel
    • So ask elements of $\frac{1}{n}$ to move one down, ask $\frac{1}{2}\to \frac{1}{3}$ and $\frac{1}{3}\to \frac{1}{4}$, etc.
    • $f\left(\frac{1}{2}\right)=\frac{1}{3}$
    • $f\left(\frac{1}{3}\right)=\frac{1}{4}$
    • $f\left(\frac{1}{4}\right)=\frac{1}{5}$
    • $f(1)=\frac{1}{2}$
  • To make it work for $[0,1]$
  • $f:[0,1]\to (0,1),f(x)=\left\{\begin{array}{cc}\frac{1}{n+2}& x=\frac{1}{n},n\in \mathbb{N}\\ x& \text{otherwise}\end{array}\right\}$