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.

Consider a function $f : D \to D$ (where $D$ is a finite set) so that for every $d \in D$, there is an integer $n$ so that $f(f(...(n\text{ times})...f(d)...) = d$.

  1. Prove that $f$ is a bijection.
  2. Prove that if $f : D \to D$ (where $D$ is a finite set) is a bijection, then for every $d \in D$, there is an integer $n$ so that $f(f(...(n\text{ times})...f(d)...) = d$.

I know this proposition is true (because a bijection over a finite set is just a permutation which is always representable using cycles), I'm just having a hard time formulating a proof for it that a first-year algebra student could understand.

share|improve this question
    
$f$ has finite order, so it has an inverse. –  Qiaochu Yuan Dec 8 '12 at 2:01
add comment

5 Answers

up vote 2 down vote accepted

If you want to use a minimum of machinery, I don’t think that you can get too much simpler than these:

(2) Fix $d\in D$ and consider the sequence $\langle d,f(d),f^2(d),f^3(d),\dots\rangle$; $D$ is finite, so there must be distinct $i,k\in\Bbb N$ such that $i<k$ and $f^i(d)=f^k(d)$. Since $f$ is a bijection, it has an inverse $g$. Let $n=k-i$, so that $f^k(d)=f^i\big(f^n(d)\big)$. Then $$d=g^i\big(f^i(d)\big)=g^i\big(f^k(d)\big)=g^i\big(f^i\big(f^n(d)\big)\big)=f^n(d)\;.$$

(1) To show that $f$ is injective, suppose that $f(d)=f(e)$ for some $d,e\in D$. There are positive integers $m$ and $n$ such that $f^m(d)=d$ and $f^n(e)=e$. But then by an easy induction $f^{km}(d)=d$ and $f^{kn}(e)=e$ for all $k\in\Bbb N$, and therefore $d=f^{mn}(d)=f^{mn}(e)=e$.

To show that $f$ is surjective, merely observe that if $d\in D$, then there is $n\in\Bbb Z^+$ such that $d=f^n(d)=f\big(f^{n-1}(d)\big)\in\operatorname{ran}f$.

share|improve this answer
add comment

For the "prove $f$ is a bijection" part (i.e. #1): We first show $f$ is injective. So, suppose $f(a) = f(b)$, where $a, b \in D$. Now, for $a$ and $b$ there exist positive integers $n$ and $m$ such that $f^n(a) = a$ and $f^m(b) = b$ (where $f^n$ is the standard notation for iteration: $f^n = f \circ f \circ f \circ \cdots \circ f\ (n\ \mathrm{times})$, and $f^0 = \mathrm{id}$, the identity function.). These equations give $f^{n-1}(f(a)) = a$ and $f^{m-1}(f(b)) = b$. Now, since $f(a) = f(b)$, we have $f^{m-1}(f(a)) = b$. That is, $f^m(a) = b$. Now also, $f^{n-1}(f(b)) = a$ thus $f^n(b) = a$. What $f^m(a) = b$ shows is that the cycle containing $a$ also contains $b$, thus the two cycles are not disjoint, and are in fact the same cycle. Thus, $f^n(b) = b$ as well (note that a period of one point in a cycle is a period of every point), and so $a = b$.

Now to show $f$ is surjective. Suppose $a$ is an element of $D$. Then, we want to find a $b$ for which $f(b) = a$. Since $f^n(a) = a$ for some $n$, we have $f(f^{n-1}(a)) = a$, and so $b = f^{n-1}(a)$ will work.

So, $f$ is both injective and surjective. Thus, $f$ is bijective.

For the "converse" part (i.e. #2): Suppose $f$ is bijective. Now, consider $f^n(a)$ for some $a \in D$ and positive integers $n$. Now, there are only finitely many possibilities for $f^n(a)$, so there must be some n for which $f^n(a) = f^m(a)$ for some m <= n. Then, since $f$ is bijective, it is invertible, and we have the existence of the negative iterate $f^{-m} = (f^{-1})^m$, which is the inverse of $f^m$, and we can apply that to both sides to get $f^{n-m}(a) = a$.

Q. E. D.

share|improve this answer
    
Your answer is the closest thing to what I was thinking of when I was trying to write a proof. Thanks. –  Joe Z. Dec 8 '12 at 2:52
add comment

(1) First we prove that $f$ is surjective.

let $d \in A$. We know that $f[ f(f...f(d)))]=d$. Let $y=$inside of the $[ ...]$ then $f(y)=d$.

Now we prove that any surjection $f:A \to A$ is also injective.

Assume by contradiction that $f(a)=f(b)$ for some $a,b$. Let $n$ be the number of elements of $A$, then $A \backslash \{ a, b\}$ has $n-2$ elements.

Thus $f(A \backslash \{ a, b\} )$ has at most $n-2$ elements. Thus $f(A)=f(A \backslash \{ a, b\} ) \cup \{ f(a) \}$ has at most $n-1$ elements, which contradicts the fact that $f$ is onto.

2 Look at $f^n(d)$. Then, there exists two elements $n <m$ so that

$$f^n(d)=f^m(d) \,.$$

Thus

$$f^n(d)= f^n(f^{m-n}(d)) \,.$$

Since $f^n$ is injective, we get $d=f^{m-n}(d)$.

share|improve this answer
add comment

1)Clearly, $f$ is a surjection. Now we will verify that $f$ is injective. First we note that if $f^{n}(x)$ then for any positive integer $k$ ,$f^{kn}(x)=x$.

Let $f(d_1)=f(d_2)$. We find that there exists $m,n$ such that $f^{m}(d_1)=d_1,f^{n}(d_2)=d_2$ Thus, $f^{mn}(d_1)=d_1,f^{mn}(d_2)=d_2$. Since $f(d_!)=f(d_2)$, therefore $f^{mn}(d_1)=f^{mn-1}(f(d_1))=f^{mn-1}(f(d_2))=f^{mn}(d_2)$

share|improve this answer
    
How is it clear that $f$ is a surjection? On mappings of finite domains to themselves, injection and surjection imply each other. –  Joe Z. Dec 8 '12 at 0:54
add comment

For (1), it's easier to prove that if $f$ is not injective then neither is $f^{n}$ and if $f$ is not surjective then neither is $f^n$, for any $n \ge 1$. You know that $f^n$ is bijective, and hence so must $f$ be.

For (2), note that the bijections on a set form a group under composition, and that if $D$ is finite then this group is finite, so all its elements have finite order.

share|improve this answer
    
You’re given an $n_d$ for each $d\in D$; to use your argument for (1) you’d have to start by taking the lcm $n$ of these $n_d$’s. –  Brian M. Scott Dec 8 '12 at 0:10
    
@BrianM.Scott that's acceptable. This is one part of a large question, and one of the parts of the question was to show that the LCM of all $n_d$ would turn $f$ into the identity. –  Joe Z. Dec 8 '12 at 0:41
    
@CliveNewstead I was hoping not to have to use the word "group" or "order", because I'm writing the proof for first-year algebra students who haven't learned about such things. –  Joe Z. Dec 8 '12 at 0:43
add comment

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.