Counting

Based on 21-127 Concepts of Mathematics

We’re talking about counting how many things are in a set. Not to be confused with counting with finders.

Note $[n]$ for some $n \in \mathbb{N}$ denotes ${ i \in \mathbb{Z}^+ \mid i\leq n } = {1, 2, 3, \dots, n}$. (Note $[0] = \varnothing$)

A set $X$ is finite if we can find a bijection between $[n]$ for some $n \in \mathbb{N}$ and $X$. Think of it as assigning a number to each element of $X$. This number assignment is known as an enumeration of $X$.

A consequence is that this number $n$ is unique and is equal to the size of $X$. We can write $|X| = n$. $|X|$ is called the size or cardinality of $X$.

Let $m, n \in \mathbb{N}$

• If an injective $f: [m] \to [n]$ exists, then $m\leq n$
• If a surjective $f: [m] \to [n]$ exists, then $m \geq n$
• A bijective $f: [m] \to [n]$ iff $m = n$

Since we can biject $[m]$ with set $X$ with $|X| = m$ and $[n]$ with set $Y$ with $|Y| = n$, we can tweak the previous statement to conclude:

• If $Y$ finite and an injective $f: X \to N$ exists, then $X$ finite and $|X| \leq |Y|$
• If $X$ finite and a surjective $f: X \to N$ exists, then $Y$ finite and $|X| \geq |Y|$
• Suppose $X$ or $Y$ finite, then a bijective $f: X \to N$ exists iff $|X| = |Y|$

Let $X, Y$ be finite sets. We have that:

• $X \cap Y$ finite and $|X \cap Y| \leq \mathrm{min}(|X|, |Y|)$
• $X \cup Y$ finite and $|X \cup Y| \geq \mathrm{max}(|X|, |Y|)$ and $|X \cup Y| = |X| + |Y| - |X \cap Y|$.
• $X \times Y$ finite and $|X \times Y| = |X| \cdot |Y|$

A finite partition divides a finite set into subsets that are pairwise disjoint and union to the larger set.

• pairwise disjoint means the intersection between any two set in the partition is empty.
• union to the larger set just means all the element in the larger set can be found in one of sets in the partition.

Take finite set $X$ and suppose ${A_{1}, A_{2}, \dots, A_{n}}$ is a finite partition of $X$, then $\displaystyle |X| = \sum_{i=1}^{n}|A_{i}|$.

Omitted….

The multiplication principle allows us to count the number of elements in a finite set $X$ by specifying a procedure to specify elements in $X$ uniquely. When done correctly, $|X|$ will equal the product of the number of choices at each step.

Example:

Let $X$ be the set of all subsets of $[3] = { 1,2,3 }$. Then we can specify an element of $X$ by the following procedure:

1. Decide if $1$ is in the set — 2 choices
2. Decide if $2$ is in the set — 2 choices
3. Decide if $3$ is in the set — 2 choices
   So $|X| = 2^3$.

The bionomial coefficient $\displaystyle \binom{n}{k}$ for any $n, k \in \mathbb{N}$ is defined by $\displaystyle \binom{n}{k} = |{ U \subseteq [n] \mid |U|=k }|$. It can be understood as the number of subsets of a set of size $n$ that have size $k$.

We can derive that (can be done by counting!):
$$\left(\begin{array}{l}n \\ k\end{array}\right)= \begin{cases}\frac{n !}{k !(n-k) !} & \text { if } k \leqslant n \\ 0 & \text { if } k>n\end{cases}$$

Instead of defining factorial recursively, we can define it by counting!

Let $n \in \mathbb{N}$, then $n!$ is defined as:

• The number of bijections $f: [n] \to [n]$
• The number of ways to list $n$ things in an order so that each thing appear exactly once
• The number of ways to arrange $n$ things in order
• …

This is kind of nice isn’t it?

To prove two expressions are equal, we can define a set $X$ in a way that we can count $|X|$ one way to get the RHS expression and another way to get the LHS expression.

Other than a set being finite (which obviously makes it countable), we can have:

• A set $A$ being countably infinite if we can find a bijection $f: \mathbb{N} \to A$

• A set $B$ being countable if it’s finite or countably infinite

• A set $C$ being uncountable if it’s not countable

• Known countable sets:

  • $\mathbb{N}$ (of course it bijects itself!)
  • $\mathbb{Z}$ (by doing some trick with number assignments, like $0, 1, -1, 2, -2, \dots$)
  • $\mathbb{N}^2$ (we can list things diagonally)
  • $\mathbb{Q}$ (we can define surjection $f: \mathbb{Z} \times(\mathbb{Z} \setminus {0}) \to \mathbb{Q}$ via $f(a,b)=\frac{a}{b}$)

• Known uncountable:

  • $\mathscr{P}(\mathbb{N})$
  • $\mathbb{R}$

Given a set $C$ which is countable:

• If an injective $f: X \to C$ exists, then $X$ countable. Think of it as $X$ being not bigger than a countable set.
• If an surjective $f: C \to X$ exists, then $X$ countable. Think of it as a countable set being not smaller than $X$.

We can prove that:

• Cartesian product of finitely many countable sets is countable (imagine going in diagonally in high dimensions where each axis is one component of the cartesian product)
• Union of countably many countable sets is countable. (imagine putting sets in grid and listing elements diagonally)

This is how we can prove a set is uncountable. To prove $X$ uncountable, we do:

1. Let there be function $f: \mathbb{N} \to X$. WTS this function cannot be surjective (and thus not bijective)
2. Construct some bad element $b \in X$ in terms of $f$ in a way that $b$ and $f(n)$ disagrees on something for all $n \in \mathbb{N}$
3. Then show $b \neq f(n)$ for any $n \in \mathbb{N}$. This implies not all $b \in X$ can be mapped from $\mathbb{N}$, hence making $f$ not surjective.

The cardinality of set $X$, denoted $|X|$, is a measure of the “size” of $X$ in terms of how well $X$ can inject or surject with other sets.

Let $X, Y$ be sets.

• If there is bijection $f:X\to Y$, then $|X|=|Y|$
• If there is injection $f:X\to Y$, then $|X| \leq |Y|$
• If there is injection $f:X\to Y$ but no surjection $g:X\to Y$, then $|X| < |Y|$.

It can be easily proven that the cardinality $\leq$ relation is reflexive and transitive.

It says $\leq$ is antisymmetric on cardinalities. Therefor, for all sets $X, Y$, if there exists injection $f : X \to Y$ and injection $g : Y \to X$, we will have $|X| \leq |Y|$ and $|X| \geq |Y|$, which will imply $|X| = |Y|$.

Says that the power set of all sets have strictly greater cardinality than the set itself viz. $\forall X \in \mathscr{U}, |X|<|\mathscr{P}(X)|$.

Proof: we want some injection $I : X \to \mathscr{P}(X)$ but no surjection $S : \mathscr{P}(X) \to X$.
Well, $I(x) = {x}$ for all $x \in X$ is surjective.
Suppose there is a surjection $S : \mathscr{P}(X) \to X$
Let $B = {x \in X \mid x \notin S(x)} \in \mathscr{P}(X)$.
So $B \neq F(x)$ for any $x \in X$. So $S$ not surjective.

Fun fact—this statement is provably unprovable: “$\exists X \in \mathscr{U}, |\mathbb{N}| < |X| < |\mathbb{R}|$?”