3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ THe base case is pretty pretty much always with $n=1$. In this case $X$ would be a finite set with 1 element. $\endgroup$ – Eleven-Eleven Apr 19 '13 at 4:41
  • 1
    $\begingroup$ 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... $\endgroup$ – Eleven-Eleven Apr 19 '13 at 4:44
  • $\begingroup$ Hm..I wonder if I can actually use Pidgeon Hole for this...thanks for the help getting started Christopher! $\endgroup$ – K. Barresi Apr 19 '13 at 4:49
  • $\begingroup$ 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. $\endgroup$ – Eleven-Eleven Apr 19 '13 at 4:56
5
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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