8.22 Counting with natural numbers Tutorial

Theorem (The pigeonhole principle)

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~an~injection~f:\N_m\rightarrow\N_n~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\)

‍

Remark

The theorem implies that if \(m\) objects are distributed into \(n\) boxes with \(m>n\) then at least one box receives at least two objects

In other words, if there are \(m\) pigeons and \(n\) pigeonholes with \(m>n\) then there are at least two pigeons in the same pigeonhole

‍

Example

1. In any set of 13 or more people, there are at least two whose birthdays fall in the same month

‍

1. Show that if we select 151 distinct computer science courses numbered between 1 and 300 inclusive, at least two are consecutively numbered

   Solution

   Let the selected course numbers be

   \(c_1,c_2,...,c_{151}\) (1)

   and consider the numbers

   \(c_1+1,c_2+1,...,c_{151}+1\) (2)

   then we have 302 numbers. By pigeonhole principles, at least 2 numbers are the same

   Now as the numbers on the list (1) are all distinct then the numbers on the list (2) are all distinct.

   Hence, between list (1) and list (2) exist at least two numbers are the same

   \(c_i=c_j+1\) and the course \(c_i\) follows the course \(c_j\)​

   ‍

Corollary (From pigeonhole)

If \(|X|=|N_m|\) and \(|X|=|N_n|\), then \(m=n\)

Proof:

If \(|X|=|N_m|\) and \(|X|=|N_n|\) then there exist \(f:X\rightarrow \N_m\) and \(g:X\rightarrow \N_n\)bijections, then \(g\circ f^{-1}:\N_m\rightarrow \N_n\) is a bijection and by pigeonhole we have that \(n=m\)

‍

Finite

A set \(X\) is finite if \(|X|=|N_n|\) for some \(n\in \N\). In this case we denote\(|X|=n\) and say that the cardinality of \(X\) is \(n\)

If \(X\) is not finite, we say that X is infinite.

‍

Remark

If \(X=\mathbb{Q}\) this is consider a finite set with \(|\emptyset|=0\)

‍

Notation

If \(|X|=n\) we often write \(X=\{x_1,x_2,...,x_n\}\) to emphasize that there is a bijection \(f:\N_n\rightarrow X\) such that \(f(i)=x_i\)

‍

Exercise

If \(X\) is a finite set and \(|X|=|A|\) then \(A\) is finite

Suppose that \(X\) is finite, \(|X|=n,for~some~n\in\N\).

That is, there is a bijection \(f:X\rightarrow \N_n\)

Now as \(|A|=|X|\) there exists a bijection \(g:A\rightarrow X\)

Hence \(f\circ g:A\rightarrow \N_n\) is a bijection that is \(|A|=n\) and therefore A is finite

‍

no do that, cardinality indicates a bijection

Hence we can know \(|A|=n\), So, A is finite.

‍

‍