Proving the predicate $\forall n \in \mathbb{N} , n \geq 2$ using the Pigeonhole principle 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.
 A: 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.
