Skip to content

7 Cardinality

999027873 Shi Yue

Basic_concepts__Copy_.pdf

Exercise 1. (30 points) Recall that a set \(C\) is infinite if \(C\) is not finite. Prove the following statements:

  1. Let \(C, D\) be sets. If \(C\) is infinite and \(C \subseteq D\), then \(D\) is infinite.

    Proof

    Use contrapositive, then we need to prove if \(D\) is finite, then \(C\nsubseteq D\) or \(C\) is finite

    Since \(D\) is finite, then assume \(D\) has \(k\) elements. That is \(\exists f:D\rightarrow [k]\) is bijective.

    Then for another set \(C\), we have two cases

    • \(C\subseteq D\), then we need to prove \(C\) is finite

    Since \(C\subseteq D\), then \(|D|=k\), then by theorem \(C\) is finite and \(|C|\leq |D|\)​ - \(C\nsubseteq D\), we are done

    Thus the contrapositive of this proposition is true, then this proposition is also true

  2. If \(C\) is an infinite set and \(C = A \cup B\), then at least one of the sets \(A\) or \(B\) is infinite.

    Proof

    Use contrapositive, then we need to prove if set \(A\) and \(B\) are all finite, then \(C\) is finite set or \(C\neq A\cup B\)​

    Since \(A\) and \(B\) are finite, then assume \(|A|=a,|B|=b\)​

    Then for set \(C\), we have two cases

    • \(C\neq A\cup B\), then we are done
    • \(C=A\cup B\), then we need to prove \(C\) is finite

    Since \(|A|=a,|B|=b\) and \(A\) and \(B\) are finite, then \(|A\cup B|=|A|+|B|-|A\cap B|\leq a+b\)​

    Then \(\exists m\in \N :m\leq a+b,|A\cup B|=m\), then \(A\cup B\) is finite

    Thus the contrapositive holds, then the proposition holds.

  3. Suppose \(A\) is a set and \(p\) is an object not in \(A\). If \(A\approx A\cup\{p\}\), then \(A\) is infinite.

    Proof

    Use contrapositive: We need to prove If \(A\) is finite, then \(A\cancel{\approx}A\cup\left\lbrace p\right\rbrace\)

    Assume \(|A|=m\), then there is a bijection \(f:A\rightarrow\left\lbrack m\right\rbrack\) where \(f(a_1)=1,f\left(a_2\right)=2,\ldots,f\left(a_{m}\right)=m\) where \(A=\{a_1,...,a_m\}\)​

    Then consider \(g:A\cup\{p\}\rightarrow\left\lbrack m+1\right\rbrack,g\left(x\right)=\begin{cases}f\left(x\right),x\in A\\m+1,x=p\end{cases}\) is also bijection

    Then \(|A\cup \{p\}|=m+1\) but \(|A|=m\), thus \(A\cancel{\approx}A\cup\left\lbrace p\right\rbrace\)​

  4. Prove that if \(A\) is finite and \(B\) is infinite, then \(B - A\) is infinite.

    Proof

    Use contrapositive: If \(B-A\) is finite, then \(A\) is infinite or \(B\) is finite

    Assume \(|B-A|=m\)​

    Use contradiction, suppose \(A\) is finite and \(B\) is infinite, then \(|A|=n\)

    But we know \(|B-A|=m\), then \(|B|-|A|=m\), then \(|B|=m+n\)​

    Contradiction, then \(A\) is infinite or \(B\) is finite

    Thus the contrapositive is true, then the proposition is also true

Exercise 2. (20 points) In each of the following cases, write a bijective function \(f : A \to B\) and its inverse \(g : B \to A\). Verify that \(g\) is indeed the inverse of \(f\).

  1. \(A = [n] \times [m]\) and \(B = [mn]\).

    \(f:A\rightarrow B\) where \(f(a,b)=\begin{cases}b,\text{ if }a=1,b\in\left\lbrack m\right\rbrack\\ b+m,\text{ if }a=2,b\in\left\lbrack m\right\rbrack\\ \ldots\\ b+\left(n-1\right)m,\text{ if }a=n,b\in\left\lbrack m\right\rbrack\end{cases}=b+\left(a-1\right)m\)​

    \(g:B\rightarrow A\) where \(g\left(k\right)=\left(\lfloor\frac{k-1}{m}\rfloor+1,k-m\lfloor\frac{k-1}{m}\rfloor\right)\)

    Let's check \(f\circ g\left(k\right)=f\left(g\left(k\right)\right)=f\left(\lfloor\frac{k-1}{m}\rfloor,k-m\lfloor\frac{k-1}{m}\rfloor\right)=k-m\lfloor\frac{k-1}{m}\rfloor+\left(\lfloor\frac{k-1}{m}\rfloor+1-1\right)m=k\)​

    Then, \(g\circ f(a,b)=g\left(f\left(a,b\right)\right)=g\left(b+\left(a-1\right)m\right)=\left(\lfloor\frac{b+\left(a-1\right)m-1}{m}\rfloor+1,b+\left(a-1\right)m-m\lfloor\frac{b+\left(a-1\right)m-1}{m}\rfloor\right)=\left(a-1+1,b+\left(a-1\right)m-m\left(a-1\right)\right)=\left(a,b\right)\)​

  2. \(A = [9]_0 \times [9]_0 \times [9]_0\) and \(B = [999]_0\). Here \([n]_0 := [n] \cup \{0\}\).

    \(f:A\rightarrow B\) where \(f(a,b,c)=100a+10b+c\)

    \(g:B\rightarrow A\) where \(g\left(k\right)=\left(\left(\frac{\left(\frac{k_{\text{mod 10}}}{10}\right)_{\text{mod 10}}}{10}\right)_{\text{mod 10}},\left(\frac{k_{\text{mod 10}}}{10}\right)_{\text{mod 10}},k_{\text{mod 10}}\right)\)

    Let's check \(f\circ g\left(k\right)=f\left(g\left(k\right)\right)=f\left(\left(\frac{\left(\frac{k_{\text{mod 10}}}{10}\right)_{\text{mod 10}}}{10}\right)_{\text{mod 10}},\left(\frac{k_{\text{mod 10}}}{10}\right)_{\text{mod 10}},k_{\text{mod 10}}\right)=k_{\text{mod 10}}+10\left(\frac{k_{\text{mod 10}}}{10}\right)_{\text{mod 10}}+100\left(\frac{\left(\frac{k_{\text{mod 10}}}{10}\right)_{\text{mod 10}}}{10}\right)_{\text{mod 10}}=k\)

    Then, \(g\circ f(a,b,c)=g\left(f\left(a,b,c\right)\right)=g\left(100a+10b+c\right)=\left(a,b,c\right)\)

Exercise 3. (20 points) Let \(f : A \to B\) be a function between non-empty finite sets such that all the sets \(f^{-1}(b)\), for \(b \in B\), have the same cardinality. Prove that \(|B|\) divides \(|A|\)

Proof

Since all the sets \(f^{-1}(b)\), for \(b \in B\), have the same cardinality, then \(|f^{-1}(b)|=n\).

Since we have proved \(|A|=\sum_{b\in B}|f^{-1}(\{b\})|\), then \(|A|=n+n+...+n=nk\) where \(k=|B|\)

Then \(|A|=n|B|\), thus \(|B|\) divides \(|A|\)

Exercise 4. (30 points) Use the pigeonhole principle to prove the following facts:

  1. Among any 6 integers, at least two of them are congruent modulo 5.

    Define \(f:A\rightarrow B\) where \(A=\{a,b,c,d,e,f\}\) and \(B=\{0,1,2,3,4\}\) and \(f(x)=x_{\text{mod 5}}=m\) where \(x\in A,m\in B\)​

    Then we know \(|A|=6>\)​\(|B|=5\), then by PHP there is no injection from \(A\) to \(B\)​

    Which means at least two of them are congruent modulo 5.

  2. If we place 5 points inside a unit square, there are at least two of them whose distance is at most \(\frac{\sqrt{2}}{2}\).

    Proof

    Let consider four square whose length is \(\frac12\), then we need to put five points inside four squares. By php, there at least \(2\) points in the same square.

    Then the max distance is at most \(\sqrt{\frac14+\frac14}=\frac{\sqrt2}{2}\) since these two points are in the diagonal position.

    ‍

‍

‍