# A one-to-one function from a finite set to itself is onto - how to prove by induction?

I'm not sure if I can do this without knowing what f actually is?

Let $X$ be a finite set with $n$ elements and $f: X \rightarrow X$ a one-to-one function. Prove by induction that $f$ is an onto function.

Any pointers? I don't even know how to make a base case for this.

• THe base case is pretty pretty much always with $n=1$. In this case $X$ would be a finite set with 1 element. – Eleven-Eleven Apr 19 '13 at 4:41
• From there, Let X is a finite set with k elements and f:X->X a one to one function and assume that f is an onto function. What does that mean? Apply that assumption to the set with n+1 elements... – Eleven-Eleven Apr 19 '13 at 4:44
• Hm..I wonder if I can actually use Pidgeon Hole for this...thanks for the help getting started Christopher! – K. Barresi Apr 19 '13 at 4:49
• no pigeonhole here. You have to use definitions of 1-1 and onto functions. Pigeonhole implies a counting problem. This is not a counting problem. This is an induction argument using known definitions. You anchor your base case and you make an assumption on k and then try to show it holds for k+1 effectively causing a "chain reaction" proof on all values that n can take on. – Eleven-Eleven Apr 19 '13 at 4:56

Induct on $|X|$. The base case $|X|=1$ is obvious since then there is only one function $X\rightarrow X$.

Now, suppose inductively that $|E|\leq n$ implies that every injective $E\rightarrow E$ is surjective. Suppose $|X|=n+1$ and let $f:X\rightarrow X$ be injective. Seeking a contradiction, suppose $f$ is not surjective so $|f(X)|\leq n$. Then $g:f(X)\rightarrow f(X)$ given by $g(t)=f(t)$ is injective and the inductive hypothesis implies $g$ is surjective. That is, $g(f(X))=f(X)$ so for every $y\in X$ there exists an $x\in X$ such that $f(f(x))=f(y)\Rightarrow f(x)=y$. Thus $f$ is surjective, a contradiction. Hence $f$ is surjective and this closes the induction.

• Thanks Brian. The $E$ threw me off for a second, but I read through a few times and that cleared it up. – K. Barresi Apr 19 '13 at 4:53
• Of course the base case $|X|=0$ would be "even more obvious". ;) – Hagen von Eitzen Apr 19 '13 at 5:21
• I altered the proof to make it a bit nicer. Hagen--I agree! – Brian Fitzpatrick Apr 19 '13 at 5:32
• The last line is kind of hard to understand, you get a contradiction because $f$ is surjective therefore $f$ is surjective... – shinzou Jan 14 '15 at 20:45
• Is this true for infinite set also? – blue boy Aug 25 '17 at 23:22

An alternative, non-inductive approach. Makes use of the definition of Dedekind-infinite/finite.

Suppose we have injective (1-1) function $f: X\rightarrow X$

Using proof by contrapositive, suppose that $f$ is not surjective (onto).

Let $X'=f(X)$. Show $X'$ is a proper subset of $X$.

Construct $f': X'\rightarrow X$, the inverse of $f$ on $X'$.

Show $f'$ is both injective and surjective. By definition, $X$ would then be infinite.

Taking the contrapositive, if $X$ is finite then $f$ is surjective (onto).