Proving the predicate $\forall n \in \mathbb{N} , n \geq 2$ using the Pigeonhole principle

Question

The version of the pigeonhole principle we’ll look at is the following: “For all natural numbers $n$ greater than $1$, and all subsets $S, T$ of $\mathbb{N}$ where $|S| = n$ and $|T| = n − 1$, there does not exist a one-to-one function from $S$ to $T$.”

We define the predicate $PHP(n)$:

$$∀S, T ⊆ \mathbb{N}, |S| = n ∧ |T| = n − 1 ⇒ (∀f : S → T, ∃s_{1}, s_{2} ∈ S, s_{1} \neq s_{2} ∧ f(s_{1}) = f(s_{2}))$$

How do we prove that $∀n ∈ N, n ≥ 2 ⇒ PHP(n)$.

I'm having a very hard time with this proof and don't even know where to begin with.

Answer 1

We have $PHP(n)$: \begin{align*} \forall S,T \subseteq N,|S| = n \land |T| = n-1 \implies (\forall f: S \mapsto T,\exists s_1,s_2\in S, s_1 \neq s_2 \land f(s_1) = f(s_2)) \end{align*} We need to prove this for $\forall n \in \mathbb{N}, n \geq 2 \implies PHP(n)$.

The base case $P(2)$, for $n=2$:

Let $S,T\subseteq \mathbb{N}$, assuming $|S|=2$ and $|T|=1$(as given by the above predicate). Letting $f:S \mapsto T$, we observe that there are $2$ elements in $S$ and only $1$ element in $T$ and so, in this case, both of the elements of $S$ are mapped to the only element in $T$.

$\therefore s_1 \neq s_2 \land f(s_1) =f(s_2)$ and, henceforth, $PHP(2)$ is true.

Now, we let $k \in \mathbb{N}$. Assuming $P(k)$: \begin{align*} \forall S,T \subseteq N,|S| = k \land |T| = k-1 \implies (\forall f: S \mapsto T,\exists s_1,s_2\in S, s_1 \neq s_2 \land f(s_1) = f(s_2)) \end{align*} We will try to show $P(k+1)$: \begin{align*} \forall S,T \subseteq N,|S| = k+1 \land |T| = (k+1)-1=k \implies (\forall f: S \mapsto T,\exists s_1,s_2\in S, s_1 \neq s_2 \land f(s_1) = f(s_2)) \end{align*} Now, If we look at the first part of the statement $\forall S,T \subseteq N,|S| = k+1 \land |T| =k$, it is similar the base case, $PHP(2)$. Whereas the original statement comprised of $\forall S,T \subseteq N,|S| = k \land |T| = k-1$.

We observe from $PHP(k)$ that it relates to $PHP(k+1)$ in the following manner: \begin{align*} \forall S,T \subseteq N,|S| = k \land |T| = k-1\\ \implies |S| = k+1 \land |T| = (k+1)-1 \\ \implies |S| = k+1 \land |T| = k \end{align*} which is equivalent to the statement from $P(k+1)$. Also, similar to $PHP(k)$, $|S|>|T|$ in $PHP(k+1)$. And since we know that $PHP(2)$ is true, and that the domain, $|S|$, will always be $1$ greater than the range, $|T|$, as $k+1>k$ showing that there does not exist a function that is one-to-one from $S$ to $T$.

$\therefore$ We have shown $P(k+1)$ to be true.