1

Bit confused on this proof:

enter image description here

I thought we needed to create a bijection from $\{{1,..,m-1}\}$ to $\{1,...,n\}$. So how does this proof work exactly?

helios321
  • 1,495

1 Answers1

3

The claim proven by induction, as a function of $m$, is that no suitable $n>m$ exists. We assume a minimal counterexample, i.e. a minimal $m$ for which some suitable $n>m$ exists. Let's call it $n_m$. But we show that for any such $m$ we can do the same thing with $m-1$ too. In other words, some suitable $n>m-1$ exists, albeit this time it's a different value of $n$ (in fact, $n_{m-1}=n_m-1$).

J.G.
  • 115,835
  • Quick aside: how does this kind of proof relate to induction exactly? It logically the same as 'mathematical induction'? – helios321 Nov 10 '19 at 11:23
  • 1
    Proving that from one counterexample you can always generate a smaller counterexample, so the set of counterexamples can't have a smallest element and therefore must be empty, is the contrapositive form of a proof by more traditional forms of induction. – Robert Shore Nov 10 '19 at 11:29
  • @hellos321 Yes. – J.G. Nov 10 '19 at 11:30