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

Question

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.

Answer 1

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.

Answer 2

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).