Skip to content

12.18 Cardinality

  1. Let \(S\) be a subset of \(\{1, 2, 3, \dots, 99\}\) that has 10 elements. Prove that there are two different subsets \(A, B \subseteq S\) such that the sum of the elements of \(A\) is equal to the sum of the elements of \(B\).

    Proof

    For example: \(S = \{2, 20, 24, 30, 40, 14, 3, 9, 92, 10\}\), then \(A = \{24\}, \, B = \{14, 10\}\)

    \(1+2+\dots+10\implies S_1=\{1,2,\dots,10\}\) and \(90+91+\dots+99\implies S_2=\{90,91,\dots,99\}\)

    We know \(S \subseteq \{1, 2, \dots, 99\}\)

    How many possibilities I have for the sum of the elements in \(S\). They can take the sum from the minimum (1) to the maximum (\(90+91+...+99\))

    Thus the possibility of the sum of a subset of \(S\) is equal to the maximum sum of \(S\) which is \(\sum_{k=90}^{99}k\)​

    Then \(\sum_{k=90}^{99} k = \sum_{k=1}^{99} k - \sum_{i=1}^{89} i\) \(= \frac{99 \cdot 100}{2} - \frac{89 \cdot 90}{2}\) \(= 99 \cdot 50 - 89 \cdot 45 = 89.50 + 10.50 - 89.45\) \(= \boxed{945}\)

    How many subsets of \(S\) do we have? \(2^{10} = \boxed{1024}\)

    1. N: Possible subsets of \(S\)
      ​\(1024\)
    2. M: Possible values for the sum of a subset of \(S\)
      ​\(945\)

    Because of Pigeonhole Principle (PHP), I know that there is no injection from \(N \rightarrow M\) because \(|N| > |M|\)

  2. Let \(f: X \to Y\) be a function between finite sets. Prove that \(|X| = \sum_{y \in Y} |f^{-1}(\{y\})|\)

    Remember:

    • \(A, B\) two finite sets such that \(A \cap B = \emptyset\), then \(|A \cup B| = |A| + |B|\)

    We can have a corollary: If \(A_1, A_2, \dots, A_n\) are pairwise disjoint finite sets, then \(\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n |A_i|\)

    Proof

    Base case: For \(n = 2\): \(\left| \bigcup_{i=1}^2 A_i \right| = |A_1 \cup A_2| = |A_1| + |A_2| \quad (\text{we saw in Lecture})\)

    Inductive Step: Assume \(P(n)\) is true. We prove for \(n+1\).

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

    Given \(\left( \bigcup_{i=1}^n A_i \right) \cap A_{n+1} = \emptyset\): \(\left| \bigcup_{i=1}^{n+1} A_i \right| = \left| \bigcup_{i=1}^n A_i \right| + |A_{n+1}|\)(Use base case)

    By the inductive hypothesis:\(\left| \bigcup_{i=1}^{n+1} A_i \right| = \sum_{i=1}^n |A_i| + |A_{n+1}| = \sum_{i=1}^{n+1} |A_i|\)​

    Thus, \(\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n |A_i|\) for all \(n\)​

    Proof

    Since \(f^{-1}(\{y\}) = \{ x \in X \mid f(x) = y \}\), we know \(f^{-1}(\{y\}) \cap f^{-1}(\{w\}) = \emptyset\) for \(\forall y, w \in Y\)

    Then using above proposition: \(\sum_{y\in Y}|f^{-1}(\{y\})|=\left|\bigcup_{y\in Y}f^{-1}(\{y\})\right|=\left|f^{-1}\left(\bigcup_{y\in Y}\{y\}\right)\right|=|f^{-1}(Y)|=|X|\)

  3. Let \(A, B, C\) be 3 finite sets. Find and prove a formula for \(|A \cup B \cup C|\).

    Proof

    In lecture we saw \(|A \cup B| = |A| + |B| - |A \cap B|\)

    Then \(|A \cup B \cup C| = |(A \cup B) \cup C|\) \(= |A \cup B| + |C| - |(A \cup B) \cap C|\)

    \(=|A|+|B|-|A\cap B|+|C|-|(A\cap C)\cup\left(B\cap C)|\right.\)

    \(=|A|+|B|-|A\cap B|+|C|-\left(|A\cap C|+|B\cap C|-|A\cap B\cap C|\right)\)​

    Thus \(|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\)

  4. \(|X| \geq |Y| \iff \exists f: X \to Y\) surjective.

    Proof

    find function/ use php after define injection

    \(\Rightarrow\)) Since \(|X| = m, |Y| = n \text{ where } m \geq n.\)

    Then \(g: X \to [m] \text{ bijective}\) and \(h:Y\to[n]\text{ bijective}\). Also \(\text{ }h^{-1}:[n]\to Y\text{ is bijective.}\)​

    Since \(m\geq n\), then define \(p:[m]\to[n]\text{ surjective where }\begin{cases}p(x)=x\text{ if }x\leq n\\ p\left(x\right)=n\text{ if }x>n\end{cases}\)

    \(\text{Then }f=h^{-1}\circ(p\circ g)\text{ is surjective where }f:X\to Y\)

    \(\Leftarrow\)) Suppose \(f:X\to Y\) is an surjection

    Then I have the following injection:\(g: Y \to X\) \(y \mapsto x \quad \text{s.t. } f(x) = y \quad (\text{I choose an } x)\)

    This function is well-defined because \(f\) is a surjection and because I choose one \(x\)."

    And \(g\) is injective.

    So by PHP (Pigeonhole Principle), since I have \(g: Y \to X\) injection, then \(|Y|\) cannot be bigger than \(|X|\).

    So \(|Y| \leq |X|.\)

  5. \(|X| \leq |Y| \iff \exists f: X \to Y\) injective.

    Proof

    \(\Rightarrow\)) Since \(|X|=m,|Y|=n\text{ where }m\leq n.\)

    Then \(g: X \to [m] \text{ bijective}\) and \(h:Y\to[n]\text{ bijective}\). Also \(\text{ }h^{-1}:[n]\to Y\text{ is bijective.}\)

    Since \(m\leq n\), then define \(p:[m]\to[n]\text{ injective where }p(x)=x\text{ if }x\leq m\)

    \(\text{Then }f=h^{-1}\circ(m\circ g)\text{ is injective where }f:X\to Y\)

    \(\Leftarrow\)) Suppose \(f:X\to Y\) is an injection

    So by PHP (Pigeonhole Principle), then \(|X|\) cannot be bigger than \(|Y|\).

    So \(|X|\leq|Y|\)

    ‍