Что это за теорема (про периодичность)?

[A'Y]

Как называется следующая теорема? Где можно посмотреть её доказательство?

Теорема. Если $M$ - конечное множество и $f$ - функция из $M$ в $M$. Тогда для любого $x\in M$ последовательность $x$, $f(x)$, $f(f(x))$, ... будет периодична.

[Aritaborian]

Разве доказательство не очевидно?
Как называется, не знаю. А формулировка, по-моему, другая: последовательность $x$, $f(x)$, $f(f(x))$, ... будет периодична, начиная с некоторого члена.

[A'Y]

Aritaborian в сообщении #708444 писал(а):

Разве доказательство не очевидно?

Справедливость теоремы очевидна, само доказательство - нет.

Aritaborian в сообщении #708444 писал(а):

Как называется, не знаю.

А где его в учебнике посмотреть можно?

Aritaborian в сообщении #708444 писал(а):

будет периодична, начиная с некоторого члена

Да, именно "начиная с некоторого члена". Для этого понятие предпериода вводят.

[Cash]

Это следствие из принципа Дирихле.

[A'Y]

Можно более подробно, как именно следует?

[Cash]

В последовательности $x_0=x$, $x_k=f(x_{k-1})$ обязательно найдутся такие $m, n$, что $x_n=x_m$.

[bot]

A'Y в сообщении #708446 писал(а):

Справедливость теоремы очевидна, само доказательство - нет.

Такое бывает?

[A'Y]

Так речь про повторение только одного значения, т.е. прямо принцип Дирихле?
Я думал, что речь идёт о том, что начиная с некоторого члена всё поведение функции будет повторятся. Я ошибался?

[gris]

Так все последующие члены определяются единственным значением.
Как только некоторое число встретится раз и ещё раз, то этот кусок (без одного из крайних повтороц) и будет повторяться дальше и дальше.

[AGu]

A'Y в сообщении #708790 писал(а):

Так речь про повторение только одного значения, т.е. прямо принцип Дирихле?
Я думал, что речь идёт о том, что начиная с некоторого члена всё поведение функции будет повторятся. Я ошибался?

Если $x_n=x_m$, то $x_{n+1}=f(x_n)=f(x_m)=x_{m+1}$. По той же причине $x_{n+2}=x_{m+2}$ и т.д. Как видите, "поведение повторяется".

[Aritaborian]

Начиная с некоторой итерации, система впадёт в цикл, который будет повторяться бесконечно. Длина же этого цикла может варьироваться от $1$ (система станет стабильна) до $|M|$ (это значит, что система с самой первой итерации проявляет периодическое поведение).

[A'Y]

gris, AGu, спасибо!