- #1

Mathmellow

- 7

- 0

I am struggling to understand the induction proof of the pigeonhole principle in my textbook. The theorem and the proof, from Biggs

The statement is true when \(\displaystyle n=1\), since \(\displaystyle 1\leq m\) for any natural number

The induction hypothesis is that the statement is true when

Suppose that \(\displaystyle j:\Bbb{N}_{k+1}\to\Bbb{N}_m\) is an injection. Since \(\displaystyle k+1\geq 2\), it follows (from the definition of an injection) that

There are two cases.

Then \(\displaystyle j(k+1)=y\), where (since

It is easy to check that \(\displaystyle j^*\) is an injection.

View attachment 8180

*Discrete Mathematics*, is pasted below, and I will explain further (see bold text) what I am having trouble with.**Theorem.**Let*m*be a natural number. Then the following statement is true for every natural number*n*: if there is an injection from \(\displaystyle \Bbb{N}_n\) to \(\displaystyle \Bbb{N}_m\), then \(\displaystyle n\leq m\).**Proof.**We use the principle of induction.The statement is true when \(\displaystyle n=1\), since \(\displaystyle 1\leq m\) for any natural number

*m*.The induction hypothesis is that the statement is true when

*n*takes a specific value \(\displaystyle k\ge 1\). We have to deduce that it is true when \(\displaystyle n=k+1\).Suppose that \(\displaystyle j:\Bbb{N}_{k+1}\to\Bbb{N}_m\) is an injection. Since \(\displaystyle k+1\geq 2\), it follows (from the definition of an injection) that

*m*cannot be 1. So \(\displaystyle m=s+1\), for some natural number*s*. In order to show that \(\displaystyle k+1\leq m=s+1\), we construct an injection \(\displaystyle j^*:\Bbb{N}_k\to\Bbb{N}_s\), and use the induction hypothesis to conclude that \(\displaystyle k\leq s\).There are two cases.

*Case 1:*Suppose that \(\displaystyle j(x)\neq s+1\) for all \(\displaystyle x\in \Bbb{N}_k\). Then we let \(\displaystyle j^*\) be the injection defined by \(\displaystyle j^*(x)=j(x)\), for all \(\displaystyle x\in\Bbb{N}_k\).**What do they mean by this step? What are they accomplishing by defining the injection \(\displaystyle j^*(x)=j(x)\), and what exactly do they mean by \(\displaystyle j(x)\neq s+1\)?***Case 2:*(See figure below) Suppose that there is an \(\displaystyle x\in\Bbb{N}_k\) such that \(\displaystyle j(x)=s+1\).Then \(\displaystyle j(k+1)=y\), where (since

*j*is an injection) \(\displaystyle y\neq s+1\). In this case define \(\displaystyle j^*\) as follows: \(\displaystyle j^*(x)=y,\quad j^*(z)=j(z) (z\neq x)\).It is easy to check that \(\displaystyle j^*\) is an injection.

View attachment 8180

**Again, I am having problems understanding this case. I would appreciate if someone could explain this, as well as the previous step more thoroughly.**

Thanks in advance!Thanks in advance!