Discrete math

John

2008-06-10 1:32 pm

Let f be a one-to-one function from X={1,2,3,...,n} onto X (so f is a bijection).

Show that there are distinct positive integers i and j such that

f^i (x) = f^j (x) for all x in X

(i and j here means compositional power, not numerical power)

and that for some positive integer k,

f^k (x) = x for all x in X

回答 (1)

[匿名]

2008-06-10 7:28 pm

✔ 最佳答案

我之前沒有讀過 discrete math
所以可以有些 theorem 沒有應用到
不過希望可以解答到啦

由於我地 f 的 domain 同 range 係 finite set (還要是同一個 set)
而 f 又是 bijective
所以 X->X 的 bijective function 亦只有 finite number
即在 X -> X 只有有限個 bijective function
而 natural number set 為無限個
所以必存在 f^i(x) = f^j(x) for all x in X, i, j are distinct

f is bijective
=> f inverse exist
W.L.O.G., let i > j
f^i(x) = f^j(x)
=> f^(i-j) (x) = f^(j-j)(x)
=> f^k (x) = x for all x in X

👍 0 👎 0