Skip to content

3.3 Counting

Finite set and structures on them

  1. enumeration (counting)

  2. existence of structures with specified proofs

  3. construction of system with specified properties

  4. optimization

Count means establishing a bijection between the set in question and some model set

We have to be sure that the counting procedure is well-defined

How to construct model sets?

We construct natural numbers \(\N\), we start from \(0\)

\(0\leftrightarrow\emptyset,1\leftrightarrow\left\lbrace\emptyset\right\rbrace,2\leftrightarrow \left\lbrace\emptyset,\left\lbrace\emptyset\right\rbrace\right\rbrace,\ldots,n\leftrightarrow A_{n},n+1\leftrightarrow A_{n}\cup\left\lbrace A_{n}\right\rbrace,...\)​

Finite Sets

Theorem

Every set \(s\) admissible in ZFC model is either in bijection with exactly one of the sets \(A_n\)(\(a_n\) is a finite set then) or is not in bijection with any of \(A_n's\) (in this case \(S\) is infinite)

Explanation

The statement is a precise way of expressing the finite-infinite dichotomy in ZFC set theory(ZFC stands for Zermelo-Fraenkel set theory with the Axiom of Choice):

  • If \(s\) is finite, it has some natural number \(n\) as its cardinality and is in bijection with exactly one \(A_n\) (where \(|A_n| = n\)), reflecting its size uniquely among the \(A_n\).
  • If \(s\) is infinite, it cannot be in bijection with any finite \(A_n\), and thus has no match among them.

Basic counting methods

  1. Addition principle

    Let \(A,B\) be disjoint finite sets, then \(|A\cup B|=\left|A\right|+\left|B\right|\) (same with \(\#(A\cup B)\)​)

    Illustration:

    1. Let \(A\) be a set of students in GTIIT and \(B\) be a set of professors in GTIIT. Here \(A\cap B=\empty\)

      Thus the number of students and professors equals the sum of these numbers 2. Let \(A\) be a set of students who had rice at lunch and \(B\) be a set of students who had noodles at lunch. Here \(A\cap B\neq\emptyset\)

      Thus we can not use addition principle

    Generalized version: Let \(A_1,...,A_k\) be a finite collection of disjoint finite sets, then \(|A_1\cup ...\cup A_k|=|A_1|\cup ...\cup |A_k|=\sum^k_{i=1}|A_i|\) (induction)

    Example: Consider birthdays classified by birth month.

  2. Subtraction principle

    Let \(A\) be a finite set and \(B\subseteq A\) (same with \(B\subset A\) in this courses)\, then \(|A\setminus B|=\left|A\right|-\left|B\right|\) (same with \(\#(A\setminus B)\))

    Proof

    Consider \(A=(A\setminus B)\cup B\) and \(A\setminus B\) is disjoint from \(B\) by the definition of \(\setminus\), then \(|A|=|A\setminus B|+|B|\)​

    Example

    1. Count the number of positive integers \(<1000\), that have at least \(2\) different digits

      Let \(A\) be set of positive integers \(<1000\) and \(B\) be set of positive integers \(<1000\) that don't have at least \(2\) different digits

      \(|A|=999,B=\{1,2,...,9,11,22,...,99,111,222,...,999\}\Rightarrow |B|=27\)

      Thus the answer is \(|A|-|B|=972\) 2. Let \(A\) be set of positive integers \(<10\) divisible by \(2\) where \(A=\{2,4,6,8\}\)​

      Let \(B\) be set of positive integers \(<10\) divisible by \(3\) where \(B=\{3,6,9\}\)

      The number of positive integers \(<10\) divisible by \(2\) but not divisible by \(3\) is \(|A\setminus B|=|A|-|B|=1\) error!!! since \(B\nsubseteq A\)​

      However, \(|A\setminus\left(A\cap B\right)|=|A|-|A\cap B|=4-1=3\) works!!! since \(A\cap B\subseteq A\)

  3. Product principle

    Let \(A,B\) be two finite sets, then \(|A\times B|=|A|\cdot |B|\) where \(A\times B=\{(a,b):a\in A,b\in B\}\)

    Proof

    Let \(A=\{a_{1},...,a_{k}\},B=\{b_{1},...,b_{l}\}\), then \(A\times B= \begin{pmatrix} \left(a_{1},b_{1}\right) & \left(a_{2},b_{1}\right) & \cdots & \left(a_{k},b_{1}\right) \\ \left(a_{1},b_{2}\right) & \left(a_{2},b_{2}\right) & \cdots & \left(a_{k},b_{2}\right) \\ \vdots & \vdots & \ddots & \vdots \\ \left(a_{1},b_{l}\right) & \left(a_{2},b_{l}\right) & \cdots & \left(a_{k},b_{l}\right) \end{pmatrix}\)

    Then use addition principle, we get the answer

    Example: Playing cards

    Types: 2,3,...,10,J,Q,K,A --13 types

    suits:♠️♣️♦️♥️ --4 variations

    Deck=Types\(\times\)Suits, then \(|\text{Deck}|=4\times13=52\)​

    Generalized version: \(A_1,...,A_k\) be finite collection of finite sets

    Then \(|A_{1}\times...\times A_{k}|=\prod_{i=1}^{k}\left|A_{i}\right|\)​

  4. Division principle

    Let \(A,B\) be finite sets and \(f:A\to B\) surjective function such that \(\forall b_1,b_2\in B\), \(|f^{-1}\left(\left\lbrace b_{1}\right\rbrace\right)|=|f^{-1}\left(\left\lbrace b _{2}\right\rbrace\right)|=d\), then \(|B|=\frac{|A|}{d}\)

    Proof?

    Corollary of the product principle

    Consider \(C=\{1,...,d\}\) and \(D=B\), NTP: \(|B|=\frac{|A|}{|C|}\;\iff \;|D|=\frac{|A|}{|C|}\)

    We define \(|A|=|C\times B|\) since \(|C\times B|=|C|\times |B|=d\times |B|\)

    Then \(\frac{|A|}{|C|}=\frac{|C\times B|}{|C|}=\left|B\right|=\left|D\right|\), thus \(|B|=\frac{|A|}{|C|}\;\)​

    Illustration

    \(A=\{1,2,...,10\}\) and \(B=\{0,1,2,3,4\}\) and \(f:A\to B\) where \(a\mapsto \text{remainder of a mod 5}\)​

    image Then \(|B|=\frac{|A|}{2}=5\)​

    Note: \(A=\{1,2,...,6\}\) and \(B=\{0,1,2,3,4\}\) we still has surjective function but it doesn't work since \(|f^{-1}\left(\left\lbrace b_{i}\right\rbrace\right)|=|f^{-1}\left(\left\lbrace b _{j}\right\rbrace\right)|\) doesn't hold always.