4

Prove the following implication by induction on $m$:

If there exists an injection $N_m \rightarrow N_n$, then $m \le n$.

$N_n$ and $N_m$ are sets with $n$ and $m$ elements, respectively.

I know how to do proofs by induction, I'm just struggling with the inductive step. So far I have the predicate P(n) = If there exists an injection $N_m \rightarrow N_n$, then $m \le n$.

I proved the base case "P(1) = If there exists an injection $N_1 \rightarrow N_n$, then $1 \le n$" sloppily by saying no element in $N_n$ could be assigned to more than one element of $N_1$ because there is only a single element in $N_1$. There must at least one element in $N_n$ in order for it to be a function, so $1 \le n$.

So I know the inductive hypothesis is P(k) = If there exists an injection $N_k \rightarrow N_n$, then $k \le n$. Now I need to prove P(k+1) = If there exists an injection $N_{k+1} \rightarrow N_n$, then $k+1 \le n$, but I'm clueless about how to do this step.

amWhy
  • 209,954
user1356910
  • 41
  • 1
    I'm curious as to what you've tried. Perhaps start with providing definitions for what being an injection means, and what "base case" you can use. Also, please clarify whether you are struggling with the notion of an injective function, or how to proceed with a proof by induction on $m$, or both... – amWhy Nov 04 '12 at 01:55
  • Sorry amWhy, I edited the post with what I've tried. – user1356910 Nov 04 '12 at 02:10
  • 1
    Great! That helps us help you! Thanks for being responsive to suggestions! – amWhy Nov 04 '12 at 02:18
  • Yes, you're correct. You need to establish that, assuming P(k) is true, then P(k+1) is true. Just a typo perhaps, but you need to show that if there exists an injection $N_{k+1} \to N_n$ then $k+1 \leq n$. (I say that because what you've got in your edit is $N_k + 1 \to N_n$. For subscripting more than one character, you need to include, all characters in { }, like this $N_{k+1} \to N_n$.) Note that you can use take as given that P(k) is true. You need only rely on the definition of an injection... – amWhy Nov 04 '12 at 02:25

2 Answers2

5

For any $f: N_m \rightarrow N_n$, if $m > n$ then by the Pigeonhole Principle (at least) two elements of $N_m$ must be sent to the same element of $N_n$. Then $f$ is not injective. Now take the contrapositive.

Factoid: (which I think is not well-known?) the Pigeonhole Principle is very similar to the Principle of Mathematical Induction. See, for example, this article. However, criticisms can be found here as well as in The complexity of the Pigeonhole Principle by M. Ajtai, in which PHP is shown to be (in some sense) stronger than PMI.

Glorfindel
  • 3,955
Benjamin Dickman
  • 14,451
  • 1
    Well I certainly didn't know that fact. Thank you for sharing! – EuYu Nov 04 '12 at 02:29
  • @EuYu: My sense is that very few are aware of this equivalence; so few that I should probably give that article (which I rooted out some time ago) a careful re-reading/scrutinizing... – Benjamin Dickman Nov 04 '12 at 02:46
  • Sadly I can't access that article. :( – EuYu Nov 04 '12 at 02:48
  • Indeed, I think my worries are founded. See, for example, http://mathforum.org/kb/message.jspa?messageID=125747 – Benjamin Dickman Nov 05 '12 at 19:42
  • Hmm, very interesting. It seems that problem is deeper than it appears. – EuYu Nov 05 '12 at 20:02
  • The link to mathforum.org is broken. Perhaps you could take a look, whenever possible... – The Amplitwist Jun 03 '22 at 07:07
  • @Glorfindel It might be a good idea to avoid updating links to mathforum.org through your script, since these links now redirect to the homepage of nctm.org, but the original forum posts are not saved at the new website. – The Amplitwist Sep 01 '22 at 04:16
  • 2
    @TheAmplitwist thanks for catching that. I'll have the script try to find Wayback Machine copies instead, though some bad things can happen there too: https://web.archive.org/web/20210515120239/https://mathforum.org/kb/message.jspa?messageID=5488111 – Glorfindel Sep 01 '22 at 18:52
2

The statement is true for $m=1$: If there is a map $f:\{1\}\to N_n$ then necessarily $n\geq1$.

Assume that the statement is true for $m\geq1$ and that we are given an injective map $f:\ [m+1]\to [n]$. We have to prove that $m+1\leq n$. We distinguish two cases:

(a) $\quad f(r)\ne n$ for all $r\in[m]$.

In this case restricting $f$ to $[m]$ provides an injective map $f':\ [m]\to[n-1]$. By the induction hypothesis it follows that $m\leq n-1$. Therefore we have $m+1\leq n$ in this case.

(b) $\quad f(r)=n$ for a unique $r\in[m]$.

In this case $f(m+1)<n$. Therefore the new function $$f'(k):=\cases{f(k) &$k\in[m], \ k\ne r$\cr f(m+1) &$(k=r)$\cr}$$ is an injective function $f':\ [m]\to[n-1]$. By the induction hypothesis it again follows that $m\leq n-1$, or $m+1\leq n$.

Christian Blatter
  • 226,825
  • I need some clarification. Why is it necessary to distinguish the two cases? Is the function $f$ referenced in the two cases actually $f:[m+1]\rightarrow [n]$? If yes, then why is the domain only restricted to $[m]$? should'nt it be $r \in [m+1]$? Thank you in advance for your clarification. – mauna Jul 24 '14 at 07:29
  • 1
    @mauna: Given is an arbitrary injective $f:>[m+1]\to[n]$. In order to make the induction work we have to fabricate some $f':>[m]\to[n-1]$, to which the induction hypothesis can be applied. – Christian Blatter Jul 24 '14 at 12:22
  • I don't understand why is it necessary to manipulate the given injective $f$, into $f'$ such that the domain of $f'$ matches the domain in the induction hypothesis before we can apply the induction hypothesis. Why is it wrong to say immediately say given the injection $f$, $m+1<n$ by the induction hypothesis? – mauna Jul 24 '14 at 18:33