19
$\begingroup$

We define $A$ to be a finite set if there is a bijection between $A$ and a set of the form $\{0,\ldots,n-1\}$ for some $n\in\mathbb N$.

How can we prove that a subset of a finite set is finite? It is of course sufficient to show that for a subset of $\{0,\ldots,n-1\}$. But how do I do that?

  • 6
    I wrote this answer to a now-deleted question. I realized that I don't recall many proofs of the pigeonhole principle (anywhere) which are longer than "obviously true.", so I decided to post the question with an answer.2012-11-18
  • 5
    I welcome other people to write answers as well.2012-11-18

4 Answers 4