# What's a proof that a set of disjoint cycles is a bijection?

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.

-
$f$ has finite order, so it has an inverse. –  Qiaochu Yuan Dec 8 '12 at 2:01

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

-

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.

-
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

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

-

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

-
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

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.

-
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