12.18 Cardinality

Exercise 2

If \(E\) and \(F\) are two nonempty finite sets, then \(\mathcal{F}(E, F)\) is a finite set and \(\text{Card} \, \mathcal{F}(E, F) = \text{Card} \, F^{\text{Card} \, E}\)

Proof

Take \(|E| = n\), \(|F| = m\),
Take \(f \in \mathcal{F}(E, F)\), then \(f\) is determined by: \(f(x_i)\), where \(E = \{x_1, \dots, x_n\}\).

Take \(f(x_1)\in F=\left\lbrace y_1,\ldots,y_{m}\right\rbrace\), so we have \(m\) choices. The same with \(f(x_2)\in F=\left\lbrace y_1,\ldots,y_{m}\right\rbrace\) .......

So we have \(m^n\) functions, in other words:\(|\mathcal{F}(E, F)| = m^n = |F|^{|E|}.\)

Exercise 4

Let \(E_n\) be the set of polynomials of degree less than or equal to \(n \in \mathbb{N}\) and whose coefficients are \(0\) or \(1\). Compute \(\text{Card} \, E_n\).

Solution

We know \(E_{n}=\left\lbrace a_0+a_1x+a_2x^2+\cdots+a_{n}x^{n}:a_0,\ldots,a_{n}\in\left\lbrace0,1\right\rbrace\right\rbrace\approx\text{Fun}([n+1],{\left\lbrace0,1\right\rbrace})\)

Since \(\text{Fun}([n+1],{\left\lbrace0,1\right\rbrace})\approx2^{n+1}\), then \(\text{Card} \, E_n=2^{n+1}\).

Exercise 5

Let \(E\) be a finite set and \(A\) be a subset of \(E\), notice we have the following: \(\text{Card} \, A = \sum_{x \in E} \mathbf{1}_A(x)\)

Show that if \(E\) is a finite set and \(A \subset E\) then \(\text{Card} \, A \leq \text{Card} \, E\).

NTP: \(\sum_{x\in E}\mathbf{1}_{A}(x)\leq\sum_{x\in E}\mathbf{1}_{E}(x)\), since \(A \subset E\), then there exists at least one \(a\in E\) such that \(a\notin A\), then \(\mathbf{1}_{E}(a)=1,\mathbf{1}_{A}(a)=0\)

If there is only one such \(a\), then \(\sum_{x\in E}\mathbf{1}_{A}(x)+1=\sum_{x\in E}\mathbf{1}_{E}(x)\Rightarrow\sum_{x\in E}\mathbf{1}_{A}(x)\leq\sum_{x\in E}\mathbf{1}_{E}(x)\)

If there is more than one \(a\), then \(\sum_{x\in E}\mathbf{1}_{A}(x)+1<\sum_{x\in E}\mathbf{1}_{E}(x)\Rightarrow\sum_{x\in E}\mathbf{1}_{A}(x)<\sum_{x\in E}\mathbf{1}_{E}(x)\)

Thus we finish the proof
Show \(\text{Card} \, A = \text{Card} \, E \iff A = E\).

\(\Rightarrow\)) If \(\text{Card}\,A=\text{Card}\,E\), then \(\sum_{x\in E}\mathbf{1}_{A}(x)=\sum_{x\in E}\mathbf{1}_{E}(x)\)

Since \(\mathbf{1}_{E}(x)=1,\forall x\in E\), then \(\mathbf{1}_{A}(x)=1,\forall x\in E\Rightarrow x\in A,\forall x\in E\Rightarrow A\supseteq E\)

Since \(A\) is a subset, then \(A=E\)

\(\Leftarrow\)) Since \(A=E\), then in particular \(A\supseteq E\), then \(\forall x\in E,x\in A\Rightarrow\mathbf{1}_{A}(x)=1,\forall x\in E\)

Since \(\mathbf{1}_{E}(x)=1,\forall x\in E\), then \(\sum_{x\in E}\mathbf{1}_{A}(x)=\sum_{x\in E}\mathbf{1}_{E}(x)\). Then \(\text{Card}\,A=\text{Card}\,E\)

Exercise 6

If \(E\) and \(F\) are two finite sets, then \(E \times F\) is finite and \(\text{Card}(E \times F) = \text{Card} \, E \, \text{Card} \, F\)

Proof

Assume \(E=\{x_1,\ldots,x_{n}\}\) and \(F=\{y_1,\ldots,y_{m}\}\) where \(|E|=n,|F|=m\)

Take \((x_1,y)\in E\times F\) where \(y\in\{y_1,\ldots,y_{m}\}\). Since \(x_1\) is fixed, then \(|\left\lbrace x_1\right\rbrace\times F|=\left|F\right|=m\)

Again take \((x_2,y)\in E\times F\) where \(y\in\{y_1,\ldots,y_{m}\}\). Since \(x_2\) is fixed, then \(|\left\lbrace x_2\right\rbrace\times F|=\left|F\right|=m\)

......

Then \(|E\times F|=\left|\{x_1\}\times F\cup\{x_2\}\times F\cup\ldots\cup\{x_{n}\}\times F\right|=m+m+\cdots+m=mn\)

Exercise 7

Let \(E\) and \(F\) be two finite sets, \(f \in \mathcal{F}(E, F)\). Show the following:

\(\text{Card} \, E \geq \text{Card} \, f(E)\)

Define \(h:E\to f(E)\), then by definition \(h\) is surjective

Then we have two cases
- \(h\) is injective
Then \(h\) is bijective, then \(|E|=|f(E)|\) * \(h\) is not injective

Then by pigeon hole principle, \(|f(E)|<\left|E\right|\)

Thus \(\text{Card} \, E \geq \text{Card} \, f(E)\)
\(\text{Card} \, E = \text{Card} \, f(E) \iff f\) is injective.

Exercise 8

Let \(A_1, A_2, \dots, A_n\) be \(n\) sets (not necessarily disjoint). Prove that we have the following equality of cardinals:

\[ \left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k+1} \left( \sum_{1 \leq i_1 < \cdots < i_k \leq n} |A_{i_1} \cap \dots \cap A_{i_k}| \right) \]

Induction

\(\left|\bigcup_{i=1}^{n+1}A_{i}\right|=\left|\left(\bigcup_{i=1}^{n}A_{i}\right)\cup A_{n+1}\right|=\left|\bigcup_{i=1}^{n}A_{i}\right|+\left|A_{n+1}\right|-\left|\left(\bigcup_{i=1}^{n}A_{i}\right)\cap A_{n+1}\right|\)

Let's focus on \(\left|\left(\bigcup_{i=1}^{n}A_{i}\right)\cap A_{n+1}\right|=\left|\bigcup_{i=1}^{n}\left(A_{i}\cap A_{n+1}\right)\right|\)

\[ =\sum_{k=1}^{n}(-1)^{k+1}\left(\sum_{1\leq i_1<\cdots<i_{k}\leq n}|A_{i_1}\cap\dots\cap A_{i_{k}}|\right)+\left|A_{n+1}\right|-\left|\bigcup_{i=1}^{n}\left(A_{i}\cap A_{n+1}\right)\right| \]

\[ =\sum_{k=1}^{n}(-1)^{k+1}\left(\sum_{1\leq i_1<\cdots<i_{k}\leq n}|A_{i_1}\cap\dots\cap A_{i_{k}}|\right)+\left|A_{n+1}\right|-\sum_{k=1}^{n}(-1)^{k+1}\left(\sum_{1\leq i_1<\cdots<i_{k}\leq n}|A_{i_1}\cap\dots\cap A_{i_{k}}\cap A_{n+1}|\right) \]

\[ =\sum_{k=1}^{n}(-1)^{k+1}\left(\sum_{1\leq i_1<\cdots<i_{k}\leq n}|A_{i_1}\cap\dots\cap A_{i_{k}}|\right)+\left(-1\right)^{1+1}\left|A_{n+1}\right|-\sum_{k=1}^{n}\left(-1\right)^{k+1}\left(\sum_{1\leq i_1<\cdots<i_{k}\leq n}|A_{i_1}\cap\dots\cap A_{i_{k}}\cap A_{n+1}|\right) \]

\[ =\underbrace{\sum_{k=1}^{n}(-1)^{k+1}\left(\sum_{1\leq i_1<\cdots<i_{k}\leq n}|A_{i_1}\cap\dots\cap A_{i_{k}}|\right)}_{\text{Not invovled }A_{n+1}}+\underbrace{\left(-1\right)^{1+1}\left|A_{n+1}\right|-\sum_{k=1}^{n}\left(-1\right)^{k+1}\left(\sum_{1\leq i_1<\cdots<i_{k}\leq n}|A_{i_1}\cap\dots\cap A_{i_{k}}\cap A_{n+1}|\right)}_{\text{Invovled }A_{n+1}} \]

\[ =\sum_{k=1}^{n+1}(-1)^{k+1}\left(\sum_{1\leq i_1<\cdots<i_{k}\leq n+1}|A_{i_1}\cap\dots\cap A_{i_{k}}|\right) \]

Exercise 9 \((\star)\)

Let \(X\) be a set. Construct an injection from \(X\) to \(\mathcal{P}(X)\). Can we have a bijection between \(X\) and \(\mathcal{P}(X)\)?

Example: \(X=\{1,2,3\}\) and \(\mathcal{P}(X)=\{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}\)

Then define \(f:X\to \mathcal{P}(X)\) where \(f(x)=\{x\}\) which is injective

We cannot construct a bijection