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.

I am having a lot of trouble starting this proof. I would greatly appreciate any help I can get here. Thanks.

Let $n\in \mathbb{N}$. Prove that any injective function from $\{1,2,\ldots,n\}$ to $\{1,2,\ldots,n\}$ is bijective.

share|improve this question
    
This is often taken to be the definition of a finite set. –  Baby Dragon Mar 27 '13 at 17:37
    
@BabyDragon: That defines a so-called Dedekind-finite set. This concept is equivalent to finiteness in the presence of the Axiom of Choice, but not otherwise. –  Henning Makholm Mar 27 '13 at 18:44
    
@HenningMakholm Thank you. That is interesting. –  Baby Dragon Mar 27 '13 at 18:45
    
@BabyDragon: There are several different ways of characterizing finiteness, and many of them are not equivalent without (some of) the axiom of choice –  Asaf Karagila Mar 27 '13 at 18:49
    
@AsafKaragila HenningMakholm This means that their are models of ZF such that their are sets that are Dedekind finite but fail to be finite in some other (obvious) way? –  Baby Dragon Mar 27 '13 at 18:56

6 Answers 6

up vote 3 down vote accepted

define a new function

$$ g: \operatorname{Im}{f} \rightarrow \{1, \cdots, n\} $$

by setting $g(y)$ as that $x$ such that $f(x)=y$ (well-defined because each $y$ is an image and $f$ is injective). note that $f\circ g$ is the identity on $\operatorname{Im}{f}$, hence g must be injective; likewise, $g\circ f$ is the identity on $\{1, \cdots, n\}$, hence g must be surjective. we have just proved that g is a bijection, i.e. a permutation of $1, \cdots, n$.

the concept of cardinality is just shorthand for 'there exists a bijection'...

share|improve this answer

Another hint: Prove it by induction. It’s clear for $n=1$. Otherwise if the statement holds for some $n$, take an injective map $σ \colon \{1, …, n+1\} → \{1, …, n+1\}$. Assume $σ(n+1) = n+1$ – why can you do this? What follows?

share|improve this answer

Hint: Let $f : [n] \to [n]$ be injective. What is the cardinality of the image of $f$?

share|improve this answer

Hint: If $f:[n]\rightarrow [n]$ is injective (where $[n]= \{1,2,\dots,n\}$), all that remains to be shown is that $f$ is surjective. So, suppose it's not. How does the size of the image compare to the size of the domain, and what does this say about injectivity?

share|improve this answer

What if $f$ would not be bijective? Then one number would not be in the image of $f$. How can that be?

share|improve this answer

Suppose $f : \{1,\ldots, n\}\to\{1,\ldots, n\}$ is injective. Then $a\neq b\implies f(a)\neq f(b)$, so $\left|\,\operatorname{Im}f\,\right| = \left|\{1,\ldots, n\}\right| = n$. As $\{1,\ldots,n\}$ is the codomain, what can we say?

Since $\{1,\ldots, n\}$ is the codomain and $\left|\{1,\ldots, n\}\right| = n$, everything in the codomain must be hit.

share|improve this answer
    
Is there a way to do this without referenece to cardinality? I ask this since here [in this section] I have not yet read/introduced the concept and the source I am using (Analysis I - Escher) has this proof before discussing cardinality. Thanks. –  Michael Dykes Mar 27 '13 at 16:33
1  
I think if you try to avoid it, you'll just work with it in a roundabout way. You can just use the pidgeonhole principle to show that the claims made about cardinality are true. –  Stahl Mar 27 '13 at 18:18

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.