Игра с многочленами

[nikov]

Обозначим через $P$ наименьшее множество функций одной переменной $n$, принимающей целые положительные значения, содержащее константную функцию $1$ и замкнутое относительно возведения в степень по основанию $n$ и сложения, т.е. множество всех "многоэтажных многочленов" с целыми положительными коэффициентами, например $n^{n^{n^2}+n}+n^{2n+1}+n^3+4=n^{n^{n^{1+1}}+n^1}+n^{n^1+n^1+1}+n^{1+1+1}+1+1+1+1.$

Рассмотрим игру с одним игроком, которая происходит по следующим правилам. Первым ходом игрок выбирает по своему усмотрению любую функцию из множества $P$ (она становится текущей) и любой положительный целый аргумент. Каждым следующим ходом игрок выбирает любой положительный целый аргумент (но не меньший, чем на предыдущем ходе) и заменяет текущую функцию на любую функцию из множества $P$, имеющую меньшее значение для этого аргумента, чем текущая функция. Если игрок не может сделать ход, он проигрывает.

Верно ли, что игрок проигрывает при любой игре?

[Null]

Это задача на вполне упорядоченные множества или меня глючит и есть пример бесконечной игры?

[nikov]

Если бы я сказал, то это была бы подсказка.

[Dave]

Игрок проигрывает при любой игре. Заметим, что игрок не может бесконечно долго "оставаться на одном и том же аргументе", т.к. тогда значение каждой следующей функции на этом аргументе должно быть меньше предыдущего, а все эти значения - натуральные числа. Значит аргумент должен увеличиваться до бесконечности, причём на каждом аргументе происходит только конечное количество уменьшений функции. Для каждого аргумента, нас интересуют только две крайние функции - "вход" с меньшего аргумента и "выход" на больший аргумент. Т.е., не ограничивая общности, можно считать, что есть возрастающая последовательность аргументов

$$a_1<a_2<a_3<\dots$$

и последовательность функций $\eta_0, \eta_1, \eta_2, \dots$ из $P$, такая, что

$$\eta_0(a_1)>\eta_1(a_1), \; \eta_1(a_2)>\eta_2(a_2), \; \eta_2(a_3)>\eta_3(a_3), \; \dots,$$

и нужно доказать, что такая последовательность не может быть бесконечной ни при какой игре игрока. Идея состоит в том, чтобы параллельно с "многочленами" $\eta_i$ рассматривать приведённые "многочлены", в которых коэффициенты всегда меньше текущего аргумента, но которые, в отличие от исходных "многочленов", будут обязательно убывать в соответствии с некоторым определённым на $P$ порядком, превращающим его во вполне упорядоченное множество. Т.к. в этой последовательности найдётся наименьший элемент, то он же будет в ней и последним, т.е. сама последовательность на нём обрывается и обязана быть конечной.

Более строго это выглядит так. Пусть $\mathbb{N}^0$ - множество неотрицательных целых чисел. Определим рекурсивно следующие множества с заданным на каждом из них линейным порядком:
1) $S_0=\{\varnothing\}$ - множество состоит из единственного элемента, являющегося пустым множеством. Будем также обозначать этот элемент знаком $\Lambda$.
2) Для любого $n \in \mathbb{N}$, если $S_i$ вместе с порядком $\prec$ определены для всех $i<n$, то определим $S_{n}$ как множество конечных упорядоченных наборов

$$S_{n}=\{\gamma_1 \succcurlyeq \gamma_2 \succcurlyeq \dots \succcurlyeq \gamma_m \mid m \in \mathbb{N}^0, \; \gamma_1, \gamma_2, \dots,\gamma_m \in S_{n-1}\}.$$

При этом $m=0$ соответствует пустой набор, т.е. $\Lambda$ также включается в $S_{n}$. Для любых элементов $\alpha, \beta \in S_{n}$, если $\alpha = (\gamma_1',\gamma_2',\dots,\gamma_{m'}')$, $\beta = (\gamma_1'',\gamma_2'',\dots,\gamma_{m''}'')$ и различие в этих последовательностях начинается с $i$-го элемента, то порядок между $\alpha$ и $\beta$ определяется таким же, как и между $\gamma_i'$ и $\gamma_i''$; в случае отсутствия $i$-го элемента в наборе, задающем один из элементов, он (элемент) считается меньшим. В частности, $\Lambda$ - наименьший элемент $S_{n}$. Для определённости стоит отметить, что элемент, определяемый набором из одного элемента $\gamma_1$ при $m=1$ - это не то же самое, что этот элемент сам по себе, так же, как и $\varnothing$ не то же самое, что $\{\varnothing\}$. В частности, $S_1$ можно считать по сути дела эквивалентом $\mathbb{N}^0$ и в нём, наряду с $\Lambda$, будет присутствовать также элемент $\{\Lambda\}$, соответствующий единице в $\mathbb{N}^0$.
По индукции доказывается, что:
1) $S_0 \subset S_1 \subset S_2 \subset \dots$ ;
2) Порядок на каждом следующем множестве совпадает с порядком на предыдущем;
3) Порядок на каждом множестве является полным.
После этого можно естественным образом определить упорядоченное множество $S=\bigcup\limits_{i=0}^{\infty} S_i,$ которое будет вполне упорядоченным.
Теперь каждому элементу из $S$ можно поставить в соответствие некоторую функцию $f \colon \mathbb{N} \to \mathbb{N}^0$, также рекурсивным образом:
1) Элементу $\Lambda$ из $S_0$ ставится в соответствие функция $f_{\Lambda}(x) \equiv 0$.
2) Для любого $n \in \mathbb{N}$, если каждому $\gamma \in S_{n-1}$ уже поставлена в соответствие некоторая функция $f_{\gamma}(x) \colon \mathbb{N} \to \mathbb{N}^0$, то для любого $\alpha = (\gamma_1,\gamma_2,\dots,\gamma_m) \in S_{n}$ положим $f_{\alpha}(x) \equiv \sum\limits_{i=1}^m {x^{f_{\gamma_i}(x)}}$.
По индукции доказывается, что при таком сопоставлении каждому элементу из $S_{n-1}$ в $S_{n}$ будет сопоставлена та же функция, что и в $S_{n-1}$.
Если $F_n$ - множество функций, соответствующих всем элементам из $S_n$, а $F=\bigcup\limits_{n=0}^{\infty} F_n$ - множество функций, соответствующих всем элементам из $S$, то тогда можно показать, что $F \setminus F_0$ есть множество $P$, фигурирующее в условии задачи.
Для любого натурального $m \geqslant 2$ также определим множество $S^{(m)}$ аналогично $S$, но с той разницей, что на каждом шаге в определении $S_n^{(m)}$ будем требовать, чтобы ни один элемент $\gamma \in S_{n-1}^{(m)}$ не входил в набор, задающий определяемый в $S_{n}^{(m)}$ элемент, $m$ (или больше) раз. Очевидно, $S^{(2)} \subset S^{(3)} \subset S^{(4)} \subset \dots$ и $S=\bigcup\limits_{m=2}^{\infty} S^{(m)}$.
Можно определить операцию "увеличения на единицу" $+1 \colon S \to S$ так: если $\alpha \in S_n$, $n \geqslant 1$, то $\alpha + 1$ определяется как набор (опять же из $S_n$), задаваемый дописыванием $\Lambda$ справа к набору, определяющему $\alpha$. Очевидно, тогда для любого $\alpha \in S$ и для любого натурального $m$: $f_{\alpha+1}(m)=f_{\alpha}(m)+1$. Кроме этого, приведением к общему шагу определения $S_n$ легко доказать, что $\beta \succ \alpha \Rightarrow \beta \succcurlyeq \alpha +1$.

Утверждение 1. Если $\alpha, \beta \in S^{(m)}$, $m \geqslant 2$ и $\alpha \prec \beta$, то $f_{\alpha}(m) < f_{\beta}(m)$.
Можно доказать индукцией по шагу построения $n$ при каждом фиксированном $m$, с использованием вышеуказанных свойств "прибавления единицы" и определения функции $f$, постепенно производя свёртку "хвоста" последовательности, задающей $\alpha$, начиная с самого меньшего элемента.

Утверждение 2. Если $m \geqslant 3$, то для любого $\alpha \in S \setminus S^{(m)}$ существует такой элемент $\alpha_1 \in S$, что:
а) $f_{\alpha_1}(2) < f_{\alpha}(2)$ ;
б) $f_{\alpha_1}(m) = f_{\alpha}(m)$ ;
в) $f_{\alpha_1}(t) > f_{\alpha}(t)$ при всех $t>m$.
Доказывается также индукцией по шагу построения $n$ при каждом фиксированном $m$. Если $\alpha =(\gamma_1',\gamma_2',\dots,\gamma_{m'}')$, то либо какой-то элемент $\gamma_i$ не принадлежит $S^{(m)}$ и мы заменяем его на $\alpha_1'$, найденный для $\gamma_i$ и существующий в силу индуктивного предположения, либо какой-то элемент $\gamma_i$ встречается в последовательности (минимум) $m$ раз и тогда мы выбрасываем эту группу из $m$ элементов (оставляя остальные вхождения $\gamma_i$, если они есть) и заменяем её на единственный элемент $\gamma_i+1$. Полученный ряд, упорядоченный соответствующим образом, и определит $\alpha_1$. При определении $\alpha_1$, возможно, придётся повысить шаг $n$, но это не нарушит логики индукции, ибо мы использовали доказываемое утверждение только для $\gamma_i$ (и то только в первом случае).

Взяв какой-либо исходный элемент $\alpha \notin S^{(m)}$ и многократно применяя утверждение 2, получим некоторую последовательность $\alpha_0 = \alpha, \alpha_1, \alpha_2, \dots$ элементов $S$, такую, что для любого $i \geqslant 0$
а) $f_{\alpha_{i+1}}(2) < f_{\alpha_{i}}(2)$ ;
б) $f_{\alpha_{i+1}}(m) = f_{\alpha_{i}}(m)$ ;
в) $f_{\alpha_{i+1}}(t) > f_{\alpha_{i}}(t)$ при всех $t>m$.
В силу свойства a), эта последовательность не может быть бесконечной и мы рано или поздно придём к элементу из $S^{(m)}$. Поэтому, в силу свойств б) и в), верно
Утверждение 3. Если $m \geqslant 3$, $\alpha \in S \setminus S^{(m)}$, то найдётся такой элемент $\beta \in S^{(m)}$, что:
а) $f_{\alpha}(m) = f_{\beta}(m)$ ;
б) $f_{\alpha}(t) < f_{\beta}(t)$ при всех $t>m$.

Возвращаясь к задаче, будем считать, не ограничивая общности, что $a_1 \geqslant 3$. По каждой функции $\eta_i(x)$, $i \geqslant 1$, построим элемент $\tau_i \in S^{(a_i)}$ вместе с соответствующей функцией $\eta_{\tau_i}(x)$, следующим образом. Как было сказано выше, $\eta_i(x) \in F \setminus F_0$, поэтому $\eta_i(x) \equiv f_{\alpha}(x)$ для некоторого $\alpha \in S$. Если $\alpha \in S^{(a_i)}$, то полагаем $\tau_i=\alpha$, иначе используем утверждение 3 и положим $\tau_i=\beta$, найденному из этого утверждения. В любом случае, $\eta_i(a_i)=f_{\tau_i}(a_i)$, а $\eta_i(a_{i+1}) \leqslant f_{\tau_i}(a_{i+1})$. Учитывая, что $\eta_i(a_{i+1})>\eta_{i+1}(a_{i+1})=f_{\tau_{i+1}}(a_{i+1})$, при любом $i \geqslant 1$ получим:

$$f_{\tau_i}(a_{i+1}) > f_{\tau_{i+1}}(a_{i+1}) \eqno(*)$$

Но $\tau_i \in S^{(a_i)} \subset S^{(a_{i+1})}$ и $\tau_{i+1} \in S^{(a_{i+1})}$, поэтому из $(*)$ и из утверждения 1 получаем, что $\tau_i \succ \tau_{i+1}$. Значит последовательность $\{\tau_i\}$ - убывающая во вполне упорядоченном множестве $S$ а, стало быть, конечна. $\blacksquare$

Доказанное утверждение есть обобщение теоремы Гудстейна, которую, как известно, невозможно доказать, исходя только из аксиом Пеано. "Игра", которая фигурирует в теореме Гудстейна, ограничена тем, что там обязано чередоваться увеличение аргумента ровно на единицу с уменьшением значения функции тоже ровно на единицу, причём коэффициенты у всех частей вновь выбираемой функции должны быть меньше текущего аргумента, т.е. там "игра" по сути дела детерминирована и состоит только из выбора начального значения. Здесь же, благодаря автору задачи, появилось некоторое разнообразие.