MAT102 Lecture 24

• 2
  • a
    • Determine the Cardinality of the sets $X=\{f_1:[2]\to [3]\}$ and $Y=\{f_2:[3]\to [2]\}$
      • $[3]=\{0,1,2\}$
      • $[2]=\{0,1\}$
    • We don't know the function but we assign to $f_1:\{0,1\}\to \{0,1,2\}$
    • So we have $3^2$ options for $X$
      • $X=\{\begin{array}{lll}(0,0)& (0,1)& (0,2)\\ (1,0)& (1,1)& (1,2)\\ (2,0)& (2,1)& (2,2)\end{array}$
      • We have the $(2,\dots )$ cases here because even though $(2,\dots )$ isn't part of the input, it's part of the output, we don't know the function so we have to assume that it can potentially get mapped and create it out of thin air.
    • $|X|=9$
    • $f_2:\{0,1,2\}\to \{0,1\}$
    • So we have $2^3$ options for $Y$
    • $|Y|=8$

    ---

    • $f:[2]\to [3]$
      • $f(0)=3$
        • $0,1,2$
        • Those are our options
      • $f(1)=3$
        • $0,1,2$
      • Our pairs: $(f(0),f(1))=\left\{\begin{array}{ccc}(0,0),& (0,1),& (0,2)\\ (1,0),& (1,1),& (1,2)\\ \underbrace{(2,0)},& (2,1),& (2,2)\\ f(0)=2\\ f(1)=1\end{array}\right\}$
  • b
    • If we have $A$ and $B$ as sets.
    • The function is $B^A=\{f:A\to B\}$
    • We know from part 2a that if we have $f:[3]\to [2]$ that we have $2^3$ options in the set of these functions.
    • We also found that $f:[2]\to [3]$ has $3^2$ options in that set of functions.
    • So the pattern here is $|\text{output}{|}^{|\text{input}|}$
    • $[n{]}^{[m]}$ is $\{f:[m]\to [n]\}$. So we have $|[n]{|}^{|[m]|}$
    • So the Cardinality of $[n{]}^{[m]}$ is $|[n]{|}^{|[m]|}$

    ---

    • $m$ possible inputs, $\{\begin{array}{l}f(0)=n\\ f(1)=n\\ \dots \\ f(m-1)=n\end{array}$
  • c
    • Show that if $A$ is an arbitrary set, there is a bijection between $A^n=\begin{array}{c}\underbrace{A\times A\times \cdots \times A}\\ n\text{-times}\end{array}$ and $A^{[n]}$
    • $g:A^n\to A^{[n]}$
    • Let $X=A^n,Y=A^{[n]}$
    • $A^n=\{(a_1,a_2,a_3,\dots ,a_n):a_i\in A\}$
    • Injectivity:
      • If we have two outputs in $y_1,y_2\in Y$. This must mean that $x_0\in X$ produced these outputs.
        • By the axiom of choice, we choose two values from $Y$.
      • We have arbitrary $y_1,y_2$.
      • $x_0\in A\times A\times \cdots \times A$
        • $|A^n|=|A{|}^n$
        • Because we take the Cardinality of the set, then when we $\times$ them, it's multiplying the Cardinality, $n$ times.
      • $y_1\in A^{[n]}$
        • $|[n]|=|n|=n$
          • Cardinality of $[n]$ is just $n$
        • $|A^{|[n]|}|=|A^n|=|A{|}^n$
      • If $|X|\le |Y|$ then $X\to Y$ is injective.
      • The cardinalities are the same, so it's injective.
    • Surjectivity:
      • Let us have an arbitrary $y_0\in Y$, we need to find some $x\in X$ such that $g:A^n\to A^{[n]},x\in X$ gives us $y_0\in Y$.
      • I showed previously that $|X|=|Y|$, so this tells us it's surjective, because $|Y|\le |X|$.
      • So it's bijective.
    • $h:\{1,2,3\}\to \mathbb{R},h(x)=x$
      • $h(x)=x^2$
      • $h(x)\{\begin{array}{ll}1& 2\\ 2& 3\\ 3& 1\end{array}$
      • $h(x)\{\begin{array}{ll}0& 2\\ 2& 3\\ 3& 1\end{array}$
        • Here to get the outputs, we don't know what they are, so we can just put in the inputs.
    • Show that if $A$ is an arbitrary set, there is a bijection between $A^n=\begin{array}{c}\underbrace{A\times A\times \cdots \times A}\\ n\text{-times}\end{array}$ and $A^{[n]}$
    • We need to show that if we have $g:X\to Y$,

    ---

    • Every function from $[n]\to A$ is defined by the outputs from part A
    • Define $\mathrm{\Phi }:A^{[n]}\to A^n,\mathrm{\Phi }(f)=(f(0),f(1),\dots ,f(n-1))$
    • Define the inverse
    • ${\mathrm{\Phi }}^{-1}:A^n\to A^{[n]}$ as ${\mathrm{\Phi }}^{-1}(\hat{a})=f_{\hat{a}}$
    • where $\hat{a}=(a_0,\dots ,a_{n-1})$ and $f_{\hat{a}}(k)=a_k$
    • $\mathrm{\Phi }({\mathrm{\Phi }}^{-1}(a))=\mathrm{\Phi }(f_{\hat{a}})=(f_{\hat{a}}(0),f_{\hat{a}}(1),\dots ,f_{\hat{a}}(n-1))=(a_0,a_1,\dots ,a_{n-1})=\hat{a}$
    • ${\mathrm{\Phi }}^{-1}(\mathrm{\Phi }(f))={\mathrm{\Phi }}^{-1}(f(0),\dots ,f(n-1))=f_{(f(0),f(1),\dots ,f(n-1))}$
    • Let $k\in \{0,1,\dots ,n-1\}$ be arbitrary, then $f_{(f(0),..,f(n-1))}(k)=f(k)$