Skip to content

12.16 Cardinality

CARDINALITY

\(X\) set → \(|X|\) = cardinality of \(X\).

\(X = \{\pi, \#, ?, !\}\)

\(\downarrow ~ \downarrow ~~\downarrow ~ \downarrow\)

\(1 \,\, 2 \,\, 3 \,\, 4\)

\(\exists\) bijection \(X \to \{1, 2, 3, 4\}\)

Definition

Cardinality

A set \(X\) has \(k\) elements if there is a bijection \(X \to [k]\), for some \(k \in \mathbb{N}\).

Note: We say that \(\emptyset\) has \(0\) elements.

Notation: \([k] = \{1, 2, 3, \dots, k\}\)

Finite

A set \(X\) is finite if it has \(k\) elements for some \(k = 0, 1, 2, \dots\) If \(X\) is not finite, then it is infinite.

Is the number of elements well-defined?

If \(X\) has \(k\) elements and \(X\) has \(r\) elements \(\implies k = r\).

Equivalent

\(X, Y\) are equivalent if \(\exists\) bijection \(X \to Y\). Notation: \(X \approx Y\)

Example: \(X\) has \(k\) elements if \(X \approx [k]\).

Proposition

\(\approx\) is an equivalence relation.

Proof

  1. \(X \approx X\) because \(\text{id}_X: X \to X\) is bijective.

  2. If \(X \approx Y\), then \(\exists f: X \to Y\) bijective. Then \(f^{-1}: Y \to X\) is bijective, so \(Y \approx X\).

  3. If \(X \approx Y, Y \approx Z\), then \(f: X \to Y\), \(g: Y \to Z\), both bijective. Then \(g \circ f: X \to Z\) is bijective, so \(X \approx Z\).

Lemma

\([n] - \{r\} \approx [n-1]\)

Proof

Let \(f: [n] - \{r\} \to [n-1]\) be: $ f(x) = \begin{cases} x & \text{if } x < r \ x-1 & \text{if } x > r \end{cases} $​

Diagram

For \(n = 6\): \(\begin{array}{c|c|c|c|c|c}1 & 2 & 3 & 4 & 5 & 6\\ 1 & 2 & & 3 & 4 & 5\end{array}\)​

Exercise: \(f\) is bijective. Since \(f\) is injective by three cases and surjective by choose \(x=y/x=y+1\) satisfied

Theorem (Pigeonhole principle)

Let \(f: [m] \to [n]\) be a function. If \(m > n\), then \(f\) is not injective. (There are \(r_1 \ne r_2\) in \([m]\) such that \(f(r_1) = f(r_2)\).)

For example: If 21 pigeons return to the pigeonhole, which has only 20 holes, then there are at least 2 pigeons in the same hole. \(f: \{P_1, \dots, P_{21}\} \to \{H_1, H_2, \dots, H_{20}\}\)

Same with this

Let \(m,n\in\N\) with \(m>n\) then there is no one injection \(f:\N_m\rightarrow\N_n\)

Proof:

Let \(S=\{m\in\N:\exists\text {an injection }f:\N_m\rightarrow\N_n\text{ for some }n<m\}\)

If we prove \(S\) is empty, then we can prove theorem

Suppose \(S\neq \emptyset\), as \(S\) is bounded below then by WOP

We have \(S\) has a first element \(m_0\) and there exists an injection \(f:\N_{m_0}\rightarrow\N_n\)

Now if we consider the function \(f\circ l_{N_{m_{0}-1}}:\N_{m_{0}-1}\rightarrow\N_n\) this is injective since \(f\) and \(l_{N_{m_{0}-1}}\) are injective which is a contradiction

Because \(m_0-1<m_0\) and \(m_0\) is the first element.

Therefore \(S\neq \emptyset\) and thus there is no injection \(f:\N_m\rightarrow\N_n~for~some~n<m\)

Example

If in a group of \(n\) people, each one shakes hands with at least one person in the group, then there are at least 2 persons that shake hands with the same number of people.

Proof

Let \(P = \{P_1, P_2, \dots, P_n\} = [n]\) be the set of people.

Let \(f: P \to [n-1]\), where \(f(P_i) = \# \{\text{persons that shake hands with } P_i\}\)

By the Pigeonhole Principle, \(f\) is not injective, so \(\exists \, i \ne j \text{ such that } f(P_i) = f(P_j)\).

Corollary

If \([n] \approx [m]\) then \(n = m\)

Proof Let \(f: [n] \to [m]\) be a bijective function. By the Pigeonhole theorem, \(n \leq m\). Since \([m] \approx [n]\), we also get \(m \leq n\). Therefore \(m = n\).

Corollary

If \(X \approx [m]\) and \(X \approx [n]\), then \(m = n\).

Proof By transitivity & symmetry, \([m] \approx [n]\), so \(m = n\) by the above corollary

Definition

We write \(|X| = m\) if \(X \approx [m]\), and this is called the number of elements of \(X\).

Theorem

If \(X, Y\) are finite sets, then \(X \approx Y \iff |X| = |Y|\).

Proof \(\Rightarrow\)) If \(X \approx Y\) and \(Y \approx [n]\), then \(X \approx [n]\), so \(|X| = n = |Y|\).

\(\Leftarrow\)) If \(|X| = |Y| = n\), then \(X \approx [n]\), \(Y \approx [n]\), so \(X \approx Y\).

Theorem

Let \(n \in \mathbb{N}\). If \(|Y| = n\) and \(X \subseteq Y\), then \(X\) is finite and \(|X| \leq |Y|\).

Proof: Induction on \(n\).

If \(n = 1\), then \(|Y| = 1\) and \(X = \emptyset\) or \(X = Y\), so the result is clear.

Let \(n \geq 1\), and assume that the result is true for \(n\). We want to prove it for \(n+1\).

Given \(Y\) with \(|Y| = n+1\) and \(X \subseteq Y\), there are two cases:

Case 1: \(X = Y\), so \(X\) is finite and \(|X| = |Y| \leq |Y|\).

Case 2: \(X \subsetneq Y\), so \(\exists y \in Y - X\). Let \(Y' = Y - \{y\}\).
Note that \(X \subseteq Y'\). Now since \(Y \approx [n + 1]\), so \(\exists f: Y \to [n + 1]\) bijective.

Then, by restriction, we obtain a bijective function \(f: Y' \to [n + 1] - \{f(y)\}\)

so \(Y' \approx [n + 1] - \{f(y)\} \approx [n], \text{ so } Y' \approx [n]\) and \(|Y'| = n\).

By the induction hypothesis, \(X\) is a finite set and \(|X|\leq|Y^{\prime}\left|=n\leq|Y|=n+1\right.\)

So the result is true for \(n + 1\). Thus the result is true for \(\forall n\).

Lemma:

If \(X\) and \(Y\) are finite sets and \(X \cap Y = \emptyset\), then \(X \cup Y\) is finite and \(|X \cup Y| = |X| + |Y|.\)

Proof:

Let \(|X| = [m]\), \(|Y| \approx [n]\), so \(\exists f: X \to [m]\) and \(g: Y \to [n]\), both bijective.

Now we define: \(h: X \cup Y \to [m+n]\) where \(h(a) = \begin{cases} f(a) & \text{if } a \in X \\ g(a) + m & \text{if } a \in Y \end{cases}\)

\(h\) is bijective (Exercise).

Thus, \(X \cup Y\) is finite and \(|X \cup Y| = m + n = |X| + |Y|.\)

Exercise:

If \(X_1, \ldots, X_n\) are sets such that \(X_i \cap X_j = \emptyset \, \forall i \neq j\), then \(X_1 \cup \ldots \cup X_n\) is finite and \(|X_1 \cup \ldots \cup X_n| = |X_1| + \ldots + |X_n|.\)

Use induction

Key part: Assume it is true for \(n\), then \(|X_1\cup\ldots\cup X_{n}|=[X_1]+...+[X_{n}]=\left\lbrack m\right\rbrack\) and \(|X_{n+1}|\approx[n]\), so \(\exists f:X_1\cup\ldots\cup X_{n}\to[m]\) and \(g:X_{n+1}\to[n]\) are bijective

Consider \(h:\left(X_1\cup\ldots\cup X_{n}\right)\cup X_{n+1}\to[m+n]\) where \(h(a)=\begin{cases}f(a) & \text{if }a\in\left(X_1\cup\ldots\cup X_{n}\right)\\ g(a)+m & \text{if }a\in X_{n+1}\end{cases}\)

\(h\) is bijective....

Theorem:

If \(X\) and \(Y\) are finite sets, then \(|X \cup Y| = |X| + |Y| - |X \cap Y|.\)

Main idea: Try to construct the the expression of \(X\) or \(Y\) or \(X\cap Y\) or \(X\cup Y\) which is disjoint and apply the lemma

Proof:

We apply the lemma to \(Y = (Y - (X \cap Y)) \cup (Y \cap X).\)

We obtain: \(|Y| = |Y - (X \cap Y)| + |Y \cap X|,\) so \(|Y - (X \cap Y)| = |Y| - |Y \cap X|.\)(*)

We now apply the lemma to \(X \cup Y = X \cup (Y - (X \cap Y))\)

So \(X\cup Y\) is finite and \(|X \cup Y| = |X| + |Y| - |Y - (X \cap Y)|.\)

Then using (*), thus, \(|X \cup Y| = |X| + |Y| - |X \cap Y|.\)

Exercises:

  1. If \(f: X \to Y\) is a function between finite sets, then \(|X| = \sum_{y \in Y} |f^{-1}(y)|\)

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

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

Corollary:

If \(X\) and \(Y\) are finite sets with \(|X| = |Y|\) and \(f: X \to Y\) is a function, then \(f \text{ injective } \iff f \text{ bijective } \iff f \text{ surjective}.\)

Follow by above