12.23

Today: \(X, Y\)

\(\quad \Rightarrow X \times Y\)

\(\quad \Rightarrow \text{Fun}(X, Y) = \{f : X \to Y \, \text{functions}\}\)

\(\quad \Rightarrow \text{Inj}(X, Y) = \{f : X \to Y \, \text{injective}\}\)

\(\quad\Rightarrow\text{Bij}(X,Y)=\dots\)

Proposition

Suppose \(X\approx X^{\prime},Y\approx Y'\)

1. If \(X\cap Y=\emptyset\wedge X^{\prime}\cap Y^{\prime}=\emptyset,\) then \(X\cup Y\approx X'\cup Y'\)​

   Define \(h:X\cup Y\rightarrow X'\cup Y'\) where \(h=\begin{cases}f\left(a\right)\text{ if }a\in X\\g\left(a\right)\text{ if }a\in Y\end{cases}\)​

   Let's check it's bijective

   • Injective

   Three cases

   • \(a_1,a_2\in X\)​
   • \(a_1,a_2\in Y\)​

   • \(a_1\in X,a_2\in Y\)​

     Consider \(h(a_1)=h(a_2)\Rightarrow f(a_1)=g(a_2)\Rightarrow\) Since \(f(a_1)\in X',g(a_2)\in Y'\) and \(X'\cap Y'=\empty\), then \(f(a_1)\) can never equal to \(g(a_2)\)​

     Thus if \(a_1\in X,a_2\in Y\), \(h(a_1)\neq h(a_2)\)​ * Surjective

   • \(y\in X'\)​

     Choose \(f(a)\)​ * \(y\in Y'\)​

     Choose \(g(a)\)​

2. \(X\times Y\approx X'\times Y'\)​

   Define \(h:X\times Y\rightarrow X^{\prime}\times Y^{\prime}\) where \(h\left(x,y\right)=\left(x^{\prime},y^{\prime}\right)\) where \(x\in X,x'\in X'\) and \(y\in Y,y'\in Y'\)​

   Then we need to check it's bijective

   1. Injective

      Take \(h(x_1,y_1)=h(x_2,y_2)\), then \(\left(x_1^{\prime},y_1^{\prime}\right)=\left(x_2^{\prime},y_2^{\prime}\right)\Rightarrow x_1^{\prime}=x_2^{\prime},y_1^{\prime}=y_2^{\prime}\)​

      Then since \(f(x')=x,g(y')=y\) are bijective, then we have \(x_1=x_2,y_1=y_2\) 2. Surjective

      For any \((x',y')\), there exists \(f(x')=x,g(y')=y\), such that \(h(x,y)=(x',y')\)

3. \(\text{Fun}(X,Y)\approx \text{Fun}(X',Y')\)

   \(~~~X\quad\quad\quad~Y\\\approx~\downarrow~\alpha\quad\approx~\downarrow~\beta\\~~~X^{\prime}\quad\quad\quad Y^{\prime}\)​

   \(\Phi:\text{Fun}(X,Y)\rightarrow\text{Fun}(X^{\prime},Y^{\prime})\)​

   Given \(f:X\rightarrow Y\) we define \(\Phi(f):X'\rightarrow Y'\) as \(\Phi(f)=\beta\circ f\circ\alpha^{-1}\)​

   Let's check it is bijective

   • Injective

   Choose \(\Phi(f_1)=\Phi(f_2)\), then \(\beta\circ f_1\circ\alpha^{-1}=\beta\circ f_2\circ\alpha^{-1}\Rightarrow f_1\circ\alpha^{-1}=f_2\circ\alpha^{-1}\Rightarrow f_1=f_2\)​ * Surjective

   For any \(f':X'\to Y'\), there exists \(f=\beta^{-1}\circ f^{\prime}\circ\alpha\) such that \(\Phi(f)=\beta\circ f\circ\alpha^{-1}\)​

4. \(\text{Inj}(X,Y)\approx \text{Inj}(X',Y')\)

   Similarly we define \(\Phi(f)=\beta\circ f\circ\alpha^{-1}\), then an extra step is to check it is injective

   Take \(\Phi(f)\left(x_1\right)=\Phi(f)\left(x_2\right)\Rightarrow\beta\circ f_1\circ\alpha^{-1}\left(x_1\right)=\beta\circ f_2\circ\alpha^{-1}\left(x_2\right)\)

   Since \(\beta\) and \(f\) and \(\alpha^{-1}\) are injective, then \(x_1=x_2\)​

Proposition

If \(|X|=m,|Y|=n\), then \(X\times Y\) is finite \(|X\times Y|=mn\)

Proof

We have \(|X|\approx[m],Y\approx[n]\), then \(X\times Y\approx [m]\times[n]\)

Since this, then we know \([m]\times[n]=[mn]\). Thus \(|X\times Y|=mn\)

Corollary

If \(X_1,...,X_r\) are finite sets, \(|X_1\times X_2\times...\times X_{r}|=\left|X_1\right|\left|X_2\right|\cdot\ldots\cdot\left|X_{r}\right|\)

Proof

Use proposition and induction on \(r\)​

On \(\text{Fun}(X,Y)\)

Suppose \(X=[n]\), then \(\text{Fun}([n],Y)\approx\left\lbrace\left(y_1,\ldots,y_{n}\right):y_{i}\in Y\right\rbrace=Y^{n}\)

Example:

If \(Y = \{a, b\}\) and \(n = 3\), then \(\text{Fun}([3], Y) = \{ (y_1, y_2, y_3) : y_1, y_2, y_3 \in \{a, b\} \} = \{(a, a, a), (a, a, b), (a, b, a), (a, b, b), (b, a, a), (b, a, b), (b, b, a), (b, b, b)\}.\)

In particular

Proposition

If \(|X|=n,|Y|=m\), then \(\text{Fun}(X,Y)\) is finite and \(|\text{Fun}(X,Y)|=m^n\)

Proof

Since \(\text{Fun}(X,Y)\approx\text{Fun}(\left\lbrack n\right\rbrack,Y)\approx Y^{n}\), then \(\text{Fun}(X,Y)\) is finite and \(\text{Fun}(X,Y)=\left|Y\right|^{n}=m^{n}\)​

Example

Let \(X\) be any set and \(Y=\{0,1\}\) be any finite set, then \(\text{Fun}(X,\left\lbrace0,1\right\rbrace)=2^{\left|X\right|}=|\mathcal{P}(X)|\)

Proof

1. Define a map \(\Phi : \mathcal{P}(X) \to \mathrm{Fun}(X, \{0,1\})\) such that \(A\mapsto\chi_{A}\)

   Then \(\chi_A : X \to \{0,1\}, \quad \chi_A(x) \;=\; \begin{cases} 1, & \text{if } x \in A,\\ 0, & \text{if } x \notin A. \end{cases}\)​

2. Injectivity of \(\Phi\)​ . Suppose \(\Phi(A) = \Phi(B)\). That means \(\chi_A = \chi_B\). Then for every \(x\in X\),
   \(\chi_A(x) = \chi_B(x).\)

   • If \(x \in A\), then \(\chi_A(x) = 1\). By equality, \(\chi_B(x)=1\), so \(x\in B\).
   • If \(x \in B\), the same argument shows \(x \in A\).

   Hence \(A = B\). Therefore \(\Phi\) is injective.

3. Surjectivity of \(\Phi\)​ . Take any function \(f \in \mathrm{Fun}(X, \{0,1\})\). Define \(A_f \;=\; \{\,x \in X : f(x) = 1\}.\)

   Observe that \(\Phi(A_f)\) is exactly \(f\), because for each \(x \in X\), \(\chi_{A_f}(x) \;=\; \begin{cases} 1, & x \in A_f \text{ (i.e.\ }f(x)=1),\\ 0, & x \notin A_f \text{ (i.e.\ }f(x)=0). \end{cases}\)​

   Hence \(\chi_{A_f} = f\). This shows every function \(f\) in \(\mathrm{Fun}(X,\{0,1\})\) is hit by \(\Phi\), so \(\Phi\) is surjective.

4. Conclusion. Since \(\Phi\) is both injective and surjective, it is a bijection. Therefore, \(\bigl|\mathcal{P}(X)\bigr| \;=\; \bigl|\mathrm{Fun}(X,\{0,1\})\bigr| \;=\; 2^{\,|X|}.\)​

On \(\text{Inj}(X,Y)\)

If \(X=[r]\), then \(\text{Inj}([r],Y)\approx\left\lbrace\left(y_1,\ldots,y_{r}\right)\in Y^{r}:y_{i}\neq y_{j}\quad\forall i\neq j\right\rbrace\)

Useful in combinatories

Example

\(Y=\) set of 10 people

Choose a list with 1 president, 1 vice-president, 1 vocal, 1 secretory

How many different lists are there?

Function: (1.president, 2.vice-president, 3.vocal, 4.secretory) \(\rightarrow\) (10 people)

We want to count \(|\text{Inj}([4],[10])|\)

Proposition

If \(|X|=r,|Y|=n\), then \(|\text{Inj}(X,Y)|=\frac{n!}{\left(n-r\right)!}\)

Proof

We can assume \(X=[r]\). So, \(\text{Inj}(X,Y)=\left\lbrace\left(y_1,\ldots,y_{r}\right)\in Y^{r}:y_{i}\neq y_{j}\quad\forall i\neq j\right\rbrace\)​

Induction on \(r\)

Let \(r\in \N\). If \(n\geq r\) and \(|Y|=n\), then \(|\text{Inj}(X,Y)|=\frac{n!}{\left(n-r\right)!}\)

Case: \(r = 1\):

\(\text{Inj}([1],Y)=\{y\in Y\}=Y\) \(\Rightarrow |\text{Inj}([1], Y)| = |Y| = n = \frac{n!}{(n-1)!}\)

Let \(r \geq 1\) and assume that the result is true for \(r\).
We want to prove it for \(r+1\).

Given \(n \geq r+1\) and \(Y\) with \(|Y| = n\).

\(\text{Inj}([r+1],Y)\approx\{(y_1,\ldots,y_{r+1})\in Y^{r+1}:y_{i}\neq y_{j}\,\forall i\neq j\}\)

\(=\bigcup_{y\in Y}\{(y_1,\ldots,y_{r},y)\in Y^{r+1}:y_{i}\neq y_{j}\,\forall i\neq j,1\leq i,j\leq r,y_{i}\neq y,\forall i\}\)

\(=\bigcup_{y\in Y}\{(y_1,\ldots,y_{r})\in\left(Y-\left\lbrace y\right\rbrace\right)^{r}:y_{i}\neq y_{j}\,\forall i\neq j\}\)

\(\approx\bigcup_{y\in Y}\text{Inj}([r],Y-\{y\})\)

So \(|\text{Inj}([r+1],Y)|=\sum_{y\in Y}|\text{Inj}([r],Y-\{y\})|=\) H.I. \(\sum_{y\in Y}\frac{(n-1)!}{(n-1-r)!}\) \(= n \cdot \frac{(n-1)!}{(n-1-r)!}\)

\(=\frac{n!}{(n-(1+r))!}\)

So the result is true for \(r+1\) too. Hence the result is true \(\forall r \in \mathbb{N}\) by PMI.

Example

\(\text{Inj}([10],Y)=\{f:\{1,2,\dots,10\}\to Y\}\approx\{(y_1,y_2,\dots,y_{10}):y_{i}\neq y_{j}\,\forall i\neq j\}\) where \(f\mapsto\left(f(1),f(2),\ldots,f(10)\right)\)

Less formal proof

\(\text{Inj}([r],Y)=\{(y_1,...,y_r)\in Y^r:y_i\neq y_j,\forall i\neq j\}\)

There are \(n\) possibilities for \(y_1\). Once \(y_1\) is chosen, there are \(n-1\) possibilities for \(y_2\)

Once \(y_1,y_2\) are chosen, there are \(n-2\) possibilities for \(y_3\) and so on.......

Thus the total number is \(n\left(n-1\right)\left(n-2\right)\ldots\left(n-\left(r+1\right)\right)=\frac{n!}{\left(n-r\right)!}\)

Counting Permutations(Bijections)

Definition of Permutations

A permutation for \(X\) is a bijection \(\sigma:X\rightarrow X\). The set of all permutations is denoted \(S_X\). If \(X=[n]\), \(S_{[n]}\) is denoted \(S_n\)

Exercise

If \(X\approx X'\), then \(S_X\approx S_{X'}\)

Problem: \(|S_x|\) whom \(|X|=n=|X'|\)​

Recall this, thus \(|S_{x}|=|\text{Inj}(X,X)|=\frac{n!}{\left(n-n\right)!}=n!\) the same as \(|S_{X'}|\)

Thus \(S_X\approx S_{X'}\)

Example

\(X=[3]\Rightarrow\left|S_{X}\right|=3!=6\)

\(x\)	\(\sigma_1(x)\)	\(\sigma_2(x)\)	\(\sigma_3(x)\)	\(\sigma_4(x)\)	\(\sigma_5(x)\)	\(\sigma_6(x)\)
1	1	1	2	2	3	3
2	2	3	1	3	1	2
3	3	2	3	1	2	1

Example

How many different ways can we organize 10 people in a row?

\(p_1,p_2,p_3,p_4,p_5,p_6,p_7,p_8,p_9,p_{10}\)

The answer is \(10!\)

Just use injective function cardinality

On the number of subsets of size \(r\)

\(|X|=n\), \(r\leq n\). \(\mathcal{P}_{r}\left(X\right)=\left\lbrace A\subseteq X:|A|=r\right\rbrace\subseteq \mathcal{P}(X)\)

Exercise: \(X\approx X^{\prime}\Rightarrow\mathcal{P}_{r}\left(X\right)\approx\mathcal{P}_{r}\left(X^{\prime}\right)\)

Definition of binomial

\(\binom{n}{r}:=|\mathcal{P}_r(X)|\) if \(|X|=n\)

Proposition

\(\binom{n}{r}=\frac{n!}{r!\left(n-r\right)!}\)

Proof

N.T.P. \(\binom{n}{r}=\frac{n!}{r!\left(n-r\right)!}\), that means we need to prove \(|\mathcal{P}_{r}(X)|=\frac{n!}{r!\left(n-r\right)!}\)

We want use the fact, then we need to express \(\mathcal{P}_{r}(X)\) as an injection

Since \(\mathcal{P}_{r}\left(X\right)=\left\lbrace A\subseteq X:|A|=r\right\rbrace\subseteq \mathcal{P}(X)\), then define \(\pi:\text{Inj}(\left\lbrack r\right\rbrack,X)\rightarrow \mathcal{P}_{r}(X)\) where \((x_1,...,x_r)\mapsto \{x_1,...,x_r\}\)

But this is not bijective, and the cardinality is not same since the left hand has order but right hand does not have

Then we define \(\pi:\text{Inj}(\left\lbrack r\right\rbrack,X)\rightarrow S_{\mathcal{P}_{r}(X)}\) where \((x_1,...,x_{r})\mapsto\text{ the permutations of }\{x_1,...,x_{r}\}\)

This is bijective! (proof?)

\(f\to(f(1),f(2),...,f(r))\)

‍

‍

Then let \(|X|=n\), we know \(|\text{Inj}(\left\lbrack r\right\rbrack,X)|=\frac{n!}{\left(n-r\right)!}\approx\) \(\left|S_{\mathcal{P}_{r}(X)}\right|=r!\left|\mathcal{P}_{r}(X)\right|\)

Thus \(\left|\mathcal{P}_{r}(X)\right|=\frac{n!}{r!\left(n-r\right)!}\)​