Prove that there exists some positive integer $X_m=X_0$ given that a function is injective

Let $A$ be a finite set. Let $f:A\to A$ be an injective function from the set $A$ to itself and let $x_0$ be an element of $A$. Let $x_n$ be defined for all positive integers $n$ so that $x_n=f(x_{n-1})$ for all positive integers $n$. Prove that there exists some positive integer $m$ such that $x_m=x_0$.

Now a function is said to be injective when there is a one to one mapping. When $f : A \to A$, it means that for any element $x$ in $A$, it maps to a distinct element $y$ in $A$.

Now applying the function $x_n=f(x_{n-1})$ if $n =1$, then the function would give a result $x_0$.

The question is how do i prove this even thou i have show that there exists some positive integer which in this case is $1$

-
@Brian ..A is a finite set .I have updated it.I am not sure if my prove is good enough –  Jack welch Jan 7 '13 at 2:42
–  MJD Jan 7 '13 at 2:48
No, you don’t necessarily get $f(x_1)=x_0$; you get $x_1=f(x_0)$. –  Brian M. Scott Jan 7 '13 at 2:48

1 Answer

Here’s an outline of the proof.

You start with $x_0\in A$ and keep applying the function $f$ to get $x_1=f(x_0)$, $x_2=f(x_1)=f\big(f(x_0)\big)$, and so on. This generates a sequence $\langle x_0,x_1,x_2,\dots\rangle$ of elements of $A$.

Now prove by induction on $n$ that if $x_0,x_1,x_2,\dots,x_n$ are all distinct elements of $A$, then $$x_{n+1}=f(x_n)\notin\{x_1,\dots,x_n\}\;;$$ use the fact that $f$ is injective. From this you can conclude that either $x_{n+1}=x_0$, in which case you’re done, or $x_0,x_1,x_2,\dots,x_n,x_{n+1}$ are all distinct elements of $A$, and the induction can continue. Since $A$ is finite, it must stop at some point, and at that point you have your desired $m$.

-
{"extraction_info": {"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, "math_score": 0.9556624293327332, "perplexity": 66.06446246305651}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2014-41/segments/1410657127503.54/warc/CC-MAIN-20140914011207-00164-ip-10-196-40-205.us-west-1.compute.internal.warc.gz"}