Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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. –  Asaf Karagila Nov 18 '12 at 1:40
2  
I welcome other people to write answers as well. –  Asaf Karagila Nov 18 '12 at 1:58

2 Answers 2

The proof is essentially the pigeonhole principle, and it is proved by induction.

Let us denote $[n]=\{0,\ldots,n-1\}$. What we want to prove is in two parts:

  1. If $A\subseteq[n]$ then either $A=[n]$ or there is a bijection between $A$ and $[m]$ for some $m<n$.

  2. If $m<n$ then there is no bijection from $[n]$ into $[m]$. Equivalently we want to prove that if $f\colon[n]\to[n]$ is injective then it is a surjective. Also we may want to prove that if $f\colon[n]\to[m]$ then $f$ is not injective, or $f\colon[m]\to[n]$ then $f$ is not surjective.

The first part is not very difficult, we define by induction $f(0)=\min A$; and $f(k+1)=\min A\setminus\{f(0),\ldots,f(k)\}$. Either $f$ is a bijection between $A$ and $[n]$ or the induction had to stop before and $f$ is a bijection between $[m]$ and $A$ for some $m<n$. Note that this is not begging the question because $A$ is a set of natural numbers, and it is a subset of $[n]$ so it cannot contain more elements than $[n]$ (more in the actual sense, not in the sense of cardinality).

The second part is tricky because it seems so obvious. This is where the pigeonhole principle is actually proved.

We prove this part by induction. For $n=0$ this is obvious because $[0]=\varnothing$.

Assume that for $[n]$ it is true that if $f\colon[n]\to[n]$ is injective then it is surjective. We want to show this is also true for $[n+1]$.

Let $f\colon[n+1]\to[n+1]$ be an injective function. There are two cases:

  1. If $f(k)\neq n$ for all $k<n$ then restricting $f$ to $[n]$ is an injective function from $[n]$ into $[n]$. By the induction hypothesis we have to have that the restriction of $f$ to $[n]$ is surjective, therefore $f(n)\notin[n]$ (otherwise $f$ is not injective) and therefore $f(n)=n$ and so $f$ is surjective as well.

  2. If $f(k)=n$ for some $k<n$, by injectivity this $k$ is unique. We define $g$ as follows: $$g(x)\begin{cases} f(n) & x=k\\ n & x=n\\ f(x) & x\neq k,n\end{cases}$$ It follows that $g$ is also injective, and for all $k< n$ we have to have $g(k)\neq n$ (because $g(n)=n$ and $g$ is injective). Therefore by the previous case we know that $g$ is surjective. It follows that $f$ is also surjective, as wanted.


A word on the axiom of choice and finiteness. The above proof shows that finite sets are Dedekind-finite. There are other ways of defining finiteness, all which are true for finite sets, but may also be true for infinite sets. For example "every surjection is a bijection" might fail for infinite Dedekind-finite sets; or "every linearly ordered partition is finite"; etc.

Assuming the axiom of choice, or actually the axiom of countable choice, is enough to conclude, however, that all Dedekind-finite sets are finite. Therefore the above forms of finiteness are equivalent once more. (The reverse implication is false, by the way, it is consistent that the axiom of countable choice fails, but every Dedekind-finite set is finite.)

share|improve this answer
1  
There is another proof in my mind. Am I allowed to write it here Sir? –  Babak S. Nov 18 '12 at 2:07
    
@Babak: See my second comment on the question. :-) –  Asaf Karagila Nov 18 '12 at 2:09
    
Techically, the question seems to ask only for 1. –  Michael Greinecker Nov 18 '12 at 2:17
    
@Michael: True, but it simpler to prove this using th second point. At least if you want a full proof. :-) –  Asaf Karagila Nov 18 '12 at 2:19
    
Please have a look at it, I don't want it to be duplicate. I use this fact that if $A$ is finite and $B\subset A$, a proper subset, then $B$ is finite as well. We can do this by induction on $|A|$. If $|A|=0$ then clearly we havee $A=\emptyset$ and since the empty set has no proper subset so our claim is trure. Now, assume that the claim is true for all finite sets with $|A|=n$ and want to show for $|A|=n+1, \; B\subset A$. We know there is an element $\alpha\in A$ such that $\beta\notin B$. –  Babak S. Nov 18 '12 at 2:48

Here is a slightly different proof of the pigeonhole principle:

Suppose $f:[n]\to[n]$ is an injection that is not surjective for $n>0$. We can assume without loss of generality that $n$ is not in the range of $f$. For if it is, we map the element that is mapped to $n$ to some element not in the range instead and get a new injection that is not surjective with $n$ not in the range. We now show that $f|[n-1]$ is injective, but not surjective. Trivially, the restriction of an injection is an injection. But $f(n)\in[n-1]$ is not in the range of $f|[n-1]$.

share|improve this answer
    
Note that this argument also uses induction. –  Asaf Karagila Nov 18 '12 at 2:20
2  
@Asaf Of course, the natural numbers are essentially defined by an indctive property. –  Michael Greinecker Nov 18 '12 at 2:22
    
Yes, I just made this remark because the induction is not very apparent in your proof, and one could think that the proof is not inductive. :-) –  Asaf Karagila Nov 19 '12 at 0:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.