Задача за функции

[Гост]

Здравейте! Имам проблем с решаването на тази задача, понеже нищо не мога да разбера и ще съм много щастлив, ако някой има времето и желанието да я погледне и даде поне някакви насоки, понеже както казах въобще не знам как да я реша

Нека S e крайно множество u f : S [tex]\rightarrow[/tex] S e биекция. C [tex]f^{n }[/tex] означаваме (n — 1)-кратната композиция на[tex]f[/tex] със себе си. Индуктивната дефиниция е следната: [tex]f^{1 }[/tex](х) = [tex]f[/tex](х) ; [tex]f^{n }[/tex](х) = [tex]f[/tex]([tex]f^{n-1 }[/tex](х)) за n> 1
а) Докажете, че съществува n [tex]\in[/tex] N(естествените числа), такава че [tex]f^{-1 }[/tex] = [tex]f^{n }[/tex], където [tex]f^{-1 }[/tex] е обратната функция на f.
b) Дайте пример за биекция g: N [tex]\rightarrow[/tex] N, за която предното твърдение не е вярно.

[Davids]

а) Нека подходим така: Да положим за улеснение $n := |S| \in \mathbb{N}$, понеже $S$ е крайно множество.
За автоморфизъм (какъвто е $f$) можем да си мислим като функция, която на дадена пермутация (наредба) на крайното множество $S$ съпоставя друга такава (като реално всеки елемент на дадена позиция в аргумента е съпоставен на елемента на същата позиция в пермутацията образ). Обаче $S$ има точно $n!$ на брой пермутации, т.е. при ($n! + 1$)-кратна композиция на $f$ задължително ще повторим поне една от тях, което реално ни доказва задачата. Понеже за стартова пермутация можем да изберем именно повторената (тъй като подредбата на елементите няма значение за действието на $f$), то това значи, че $\exists k \in [1, n!] \subset \N$, за което $f^k = f^{-1}$.

б) Добър пример, за който се присетих на първо четене, е следната функция:
$f(n) := \begin{cases} n - 1, & n \equiv 0 (mod 2) \\ n + 2, & n \equiv 1 (mod 2) \end{cases}$
(ако по дефинция считаме, че $0 \notin \N$)
Ако искаме и 0-та в естествените числа, просто размени двете условия отдясно, така че нечетните числа да се намалят с 1, а четните (вкл. 0) да ги пращаме в следващото четно. Ключовото за този контрапример е, че $\N$ не е крайно.

[Гост]

а тази функция, която Davids e дал за пример, биекция ли е, защото f(4) = f(1) = 3

[Davids]

а тази функция, която Davids e дал за пример, биекция ли е, защото f(4) = f(1) = 3

Ама и ти си прав, не е никак биективна. Ще се реваншираме с друг пример, само да го измислим.

[grav]

Разбиваме [tex]\mathbb N[/tex] на подмножества, състоящите се от първите два, следващите три, следващите четери и т.н.

[tex]\mathbb N = \{(0,1),(2,3,4),(5,6,7,8),...\}[/tex]

Тогава биекцията на [tex]\mathbb N[/tex], която циклично пермутира елементите във всяка група, няма да е от краен ред.