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.
Suppose, towards a contradiction, that there is some integer $n \geq 2$ such that the Pigeonhole Principle is violated. Then there is some one-to-one function $f\colon S \to T$. Now consider the cardinality of our sets.
Since $f$ is one-to-one and the (co-)restriction $f^*\colon S \to f(S)$ defined by $f^*(s) = f(s)$ is trivially onto, we know that $f^*$ is a one-to-one correspondence so that $|S| = |f(S)|$. But since $f(S) \subseteq T$, we know that $|f(S)| \leq |T|$. Hence, it follows that: $$ n = |S| = |f(S)| \leq |T| = n - 1 $$ a contradiction. Thus, we conclude that the Pigeonhole Principle holds for all integers $n \geq 2$, as desired. $~~\blacksquare$