# Proving that an injective function is bijective

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.

-
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

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

-

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?

-

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

-

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?

-

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

-

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.

-
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
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
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://math.stackexchange.com/questions/343830/proving-that-an-injective-function-is-bijective/343840", "fetch_time": 1469795112000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2016-30/segments/1469257830066.95/warc/CC-MAIN-20160723071030-00242-ip-10-185-27-174.ec2.internal.warc.gz", "warc_record_offset": 166905468, "warc_record_length": 21164, "token_count": 980, "char_count": 3123, "score": 3.53125, "int_score": 4, "crawl": "CC-MAIN-2016-30", "snapshot_type": "latest", "language": "en", "language_score": 0.8955719470977783, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00006-of-00064.parquet"}