Игры с конечными обещаниями и последовательности жадных клик

Игры с конечным обещанием — это набор математических игр, разработанных американским математиком Харви Фридманом в 2009 году, которые используются для разработки семейства быстрорастущих функций. $FPLCI(k)$, $FPCI(k)$ и $FLCI(k)$. Последовательность жадной клики — это концепция теории графов , также разработанная Фридманом в 2010 году и используемая для разработки быстрорастущих функций. $USGCS(k)$, $USGDCS(k)$ и $USGDCS_{2}(k)$.

${\mathsf {SMAH}}$ представляет собой теорию ZFC plus, бесконечного семейства аксиом: «существует сильное $k$- Кардинал Мало для всех положительных целых чисел $k$. и ${\mathsf {SMAH^{+}}}$ представляет собой теорию ZFC плюс «для каждого $k$, есть сильно $k$-Махло кардинал». ${\mathsf {SRP}}$ представляет теорию ZFC plus, для каждого $k$, "есть $k$- стационарный кардинал Рамсея ", и ${\mathsf {SRP^{+}}}$ представляет собой теорию ZFC плюс «для каждого $k$, есть сильно $k$-стационарный кардинал Рамсея». ${\mathsf {HUGE}}$ представляет теорию ZFC plus, для каждого $k$, "есть $k$- огромный кардинал », и ${\mathsf {HUGE^{+}}}$ представляет собой теорию ZFC плюс «для каждого $k$, есть сильно $k$-огромный кардинал».

Игры с конечными обещаниями

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

Конечные кусочно-линейные игры копирования/инвертирования

Здесь, $\mathbb {Z}$ представляет собой набор целых чисел, а $\mathbb {N}$ представляет собой набор неотрицательных целых чисел. Здесь все буквы представляют собой целые числа. Мы говорим, что карта $T:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ является кусочно-линейным, если $T$ может быть определен различными аффинными функциями с целыми коэффициентами на каждой из конечного числа частей, где каждая часть определяется конечным набором линейных неравенств с целыми коэффициентами. Для некоторого кусочно-линейного отображения $T:\mathbb {N} ^{k}\rightarrow \mathbb {N}$, а $T$-инверсия $x$ это какой-то $y_{1},\ldots ,y_{k}<x$ такой, что $T(y_{1},\ldots ,y_{k})=x$. Затем мы определяем игру $G(T,n,s)$ для ненулевого $n,s$.

$G(T,n,s)$ имеет $n$ раунды и чередуются между Алисой и Бобом. На каждом этапе игры Алисе необходимо играть $x\in [0,s]$, называется ее подношением , которое имеет любую из форм $y+z$ или $w!$, где $y$ и $z$ являются целыми числами, ранее сыгранными Бобом. Затем Бобу необходимо либо:

• Принимать $x$, тем самым играя $x$ и обещая , что не будет $T$-инверсия $x$ среди целых чисел, когда-либо разыгранных Бобом. Это обещание распространяется на все прошлые, настоящие и будущие ходы игры.
• Отклонять $x$, тем самым играя $T$-инверсия $x$ и обещая это $x$ никогда не играет Боб.

В RCA ₀ можно доказать, что у Боба всегда есть выигрышная стратегия для любой игры. Игра $G_{m}(T,n,s)$ представляет собой модифицированную версию, в которой Боб вынужден принимать все факториальные предложения Алисы. $>m$. У Боба всегда есть выигрышная стратегия $G_{m}(T,n,s)$ для достаточно большого $m,s$, хотя это не может быть доказано ни в одном последовательном фрагменте ${\mathsf {SMAH}}$и только ${\mathsf {SMAH^{+}}}$. Функция $FPLCI(a)$ самый маленький $N$ так что Боб может выиграть $G_{m}(T,n,s)$ для любого $(m,T,n,s)$ такой, что $m$ и $s$ больше или равны $N$ и все следующие значения меньше $a$:

• $n$
• $k$ (домен $T$ является $\mathbb {N} ^{k}$)
• количество штук $T$
• абсолютные значения коэффициентов неравенств в $T$
• абсолютные значения коэффициентов аффинных функций в $T$

Конечные полиномиальные игры копирования/инвертирования

Позволять $P:\mathbb {Z} ^{k}\rightarrow Z$ быть многочленом с целыми коэффициентами. Специальный $P$-инверсия в $x$ в $\mathbb {Z}$ состоит из $0<y_{1},\ldots ,y_{n}<{\frac {x}{2}}$ такой, что $P(y_{1},\ldots ,y_{n})=x$. Теперь мы определяем игру $G(P,Q,n,s)$ для ненулевого $n,s$, где $P,Q:\mathbb {Z} ^{k}\rightarrow \mathbb {Z}$ являются полиномами с целыми коэффициентами. $G(P,Q,n,s)$ состоит из $n$ чередующиеся пьесы Алисы и Боба. На каждом этапе игры Алисе необходимо играть $x\in [-s,s]$ формы $P(y)$, $Q(y)$ или $(z!)!$, где $y$ это $k$-кортеж целых чисел, ранее сыгранных Бобом. Затем Бобу необходимо либо:

• Принимать $x$, тем самым играя $x$ и обещая , что особого не будет $P$- или $Q$-инверсия $x$ среди целых чисел, когда-либо разыгранных Бобом. Это обещание распространяется на все прошлые, настоящие и будущие ходы игры.
• Отклонять $x$, тем самым играя особую $P$- или $Q$-инверсия $x$ и обещая это $x$ никогда не играет Боб.

Позволять $P,Q:\mathbb {Z} ^{k}\rightarrow \mathbb {Z}$ быть полиномами с целыми коэффициентами. В RCA ₀ можно доказать, что у Боба всегда есть выигрышная стратегия для любой игры. Если $m,s$ достаточно велики, то Боб выигрывает $G_{m}(P,Q,n,s)$, что $G(P,Q,n,s)$ где Боб вынужден принять все двойные факториалы $>m$ предложила Алиса. Однако, повторюсь, это не может быть доказано ни в одном последовательном фрагменте ${\mathsf {SMAH}}$и только ${\mathsf {SMAH^{+}}}$. Функция $FPCI(a)$ самый маленький $N$ так что Боб может выиграть $G_{m}(P,Q,n,s)$ для любого $(m,P,Q,n,s)$ такой, что $m$ и $s$ больше или равны $N$ и все следующие значения меньше $a$:

• $n$
• $k$ (область определения полиномов равна $\mathbb {Z} ^{k}$)
• степени $P$ и $Q$
• абсолютные значения коэффициентов $P$ и $Q$

Конечные линейные игры копирования/инвертирования

Мы говорим, что $x,y\in \mathbb {N} ^{k}$ тогда аддитивно эквивалентны и только тогда, когда $\sum _{q=1}^{i}x_{q}=\sum _{q=1}^{j}x_{q}\implies \sum _{q=1}^{i}y_{q}=\sum _{q=1}^{j}y_{q}$. Для ненулевых целых чисел $p,n,s$ и $v_{1},\ldots ,v_{p}\in \mathbb {N} ^{k}$, мы определяем игру $G(v_{1},\ldots ,v_{p};n,s)$ который состоит из $n$ чередование раундов между Алисой и Бобом. На каждом этапе игры Алисе необходимо разыграть целое число. $x\in [0,s]$ формы $y+z$ или $w!$, где $y,z$ являются целыми числами, ранее сыгранными Бобом. Затем Бобу необходимо либо:

• Принимать $x$, тем самым играя $x$ и обещая это $x$ нельзя записать как $\sum _{q=1}^{k}y_{q}$, где $(y_{1},\ldots ,y_{k})$ аддитивно эквивалентен некоторому $v_{j}$, и $y_{1},\ldots ,y_{k}$ — целые числа, в которые Боб играл в разное время.
• Отклонять $x$, тем самым играя $y_{1},\ldots ,y_{k}$, где $x=\sum _{q=1}^{k}y_{q}$ и $(y_{1},\ldots ,y_{k})$ аддитивно эквивалентен некоторому $v_{j}$и обещает , что $x$ никогда не играет Боб.

Позволять $v_{1},\ldots ,v_{p}\in \mathbb {N} ^{k}$. В RCA ₀ можно доказать, что у Боба всегда есть выигрышная стратегия для любой игры. Позволять $v_{1},\ldots ,v_{p}\in \mathbb {N} ^{k}$. Если $m$ достаточно велико, то Боб выигрывает $G_{m}(v_{1},\ldots ,v_{p};n,s)$, где Боб принимает все факториалы $>m$ предложила Алиса. Однако, повторюсь, это не может быть доказано ни в одном последовательном фрагменте ${\mathsf {SMAH}}$и только ${\mathsf {SMAH^{+}}}$. Функция $FLCI(a)$ самый маленький $N$ так что Боб может выиграть $G_{m}(v_{1},\ldots ,v_{p};n,s)$ для любого $(m,v_{1},\ldots ,v_{p};n,s)$ такой, что $m$ больше или равно $N$, $n,s$ положительны, и все следующие значения меньше $a$:

• $k$
• $p$
• количество компонентов каждого вектора в $v$

Функции

Как показал Фридман, три функции $FPLCI(a)$, $FPCI(a)$ и $FLCI(a)$ чрезвычайно быстро растут и в конечном итоге доминируют над любыми доказуемо рекурсивными функциями в любом последовательном фрагменте ${\mathsf {SMAH}}$ (одним из них является ZFC), но они вычислимы и доказуемо полны в ${\mathsf {SMAH^{+}}}$.

Последовательности жадных клик

$\mathbb {Q} ^{*}$ обозначает множество всех кортежей рациональных чисел. Мы используем индексы для обозначения индексов кортежей (начиная с 1) и угловые скобки для обозначения конкатенации кортежей, например $\langle (0,1),(2,3)\rangle =(0,1,2,3)$. Данный $a\in \mathbb {Q} ^{*}$, мы определяем сдвиг верхний $a$, обозначенный ${\textrm {us}}(a)$ быть результатом добавления 1 ко всем его неотрицательным компонентам. Данный $a,b\in \mathbb {Q} ^{*}$, мы говорим, что $a\preceq b\iff {\textrm {max}}(a)\leq {\textrm {max}}(b)$ и $a\prec b\iff {\textrm {max}}(a)<{\textrm {max}}(b)$.  $a,b\in \mathbb {Q} ^{*}$ называются порядково эквивалентными тогда и только тогда, когда они имеют одинаковую длину и для всех $i,j$,  $a_{i}<a_{j}$ если только $b_{i}<b_{j}$. Набор $E\subseteq \mathbb {Q} ^{*}$ является порядковым инвариантом тогда и только тогда, когда для всех порядковых эквивалентов $x$ и $y$, $x\in E\iff y\in E$.

Позволять $H$ быть графом с вершинами в $\mathbb {Q} ^{*}$. Позволять $E$ — множество, определенное следующим образом: для каждого ребра $(x,y)$ в $H$, их объединение $\langle x,y\rangle$ находится в $E$. Тогда, если $E$ является инвариантным порядком, мы говорим, что $H$ является инвариантом порядка. Когда $H$ является инвариантом порядка, $H$ имеет бесконечные ребра. Нам дано $k\in \mathbb {N}$, $S\subseteq \mathbb {Q} ^{*}$и простой график $G$ (или орграф в случае жадных последовательностей клик вниз с верхним сдвигом) с вершинами в $S$. Определим последовательность $x$ как непустой кортеж $(x_{1},\ldots ,x_{n})$ где $x_{i}\in S$. Это не кортеж, а скорее кортеж кортежей. Когда $S=\mathbb {Q} ^{k}$, $x$ называется последовательностью жадной клики с верхним сдвигом в $\mathbb {Q} ^{k}$ если он удовлетворяет следующему:

• $x_{1}$ состоит только из нулей.
• Позволять $m$ быть целым числом таким, что $2\leq 2m\leq k-1$или положительное целое число, если мы допускаем бесконечные последовательности. $Y=\langle x_{1},\ldots ,x_{2m-1}\rangle$ и пусть $y=(Y_{m},\ldots ,Y_{m+k-1})$. Затем, $x_{2m}\preceq y$, $(y,x_{2m})$ это не край $G$, и $x_{2m+1}={\textrm {us}}(x_{2m})$.
• $\{x_{2},\ldots ,x_{n}\}$ это клика в $G$, то есть $G$ содержит в качестве ребра каждую пару вершин из $\{x_{2},\ldots ,x_{n}\}$.

Когда $S=\mathbb {Q} ^{k}$, $x$ называется последовательностью жадной клики со сдвигом сверху вниз в $\mathbb {Q} ^{k}$ если он удовлетворяет следующему:

• $x_{1}$ состоит только из нулей.
• Позволять $m$ быть целым числом таким, что $2\leq 2m\leq k-1$или положительное целое число, если мы допускаем бесконечные последовательности. $Y=\langle x_{1},\ldots ,x_{2m-1}\rangle$ и пусть $y=(Y_{m},\ldots ,Y_{m+k-1})$. Затем, $x_{2m}=y$ или $x_{2m}\prec y$ и $(y,x_{2m})$ это не край $G$; и $x_{2m+1}={\textrm {us}}(x_{2m})$.
• $\{x_{2},\ldots ,x_{n}\}$ это даун-клика в $G$, то есть для всех $f,g\in \{x_{2},\ldots ,x_{n}\}$ и $g\prec f$, $(f,g)$ является краем $G$.

Когда $S=\mathbb {Q} ^{k}\cup \mathbb {Q} ^{k+1}$, $x$ Говорят, что это крайняя последовательность жадной клики с верхним сдвигом вниз в $\mathbb {Q} ^{k}\cup \mathbb {Q} ^{k+1}$ если он удовлетворяет следующему:

• $x_{1}$ состоит только из нулей.
• Позволять $m$ быть целым числом таким, что $2\leq 2m\leq k-1$или положительное целое число, если мы допускаем бесконечные последовательности. $Y=\langle x_{1},\ldots ,x_{2m-1}\rangle$ и пусть $y=(Y_{m},\ldots ,Y_{m+k-1})$. Затем, $x_{2m}=y$ или $x_{2m}\prec y$ и $(y,x_{2m})$ это не край $G$; и $x_{2m+1}={\textrm {us}}(x_{2m})$.
• Если $x_{2m}\in [0,k]^{k}$, затем $x_{2m+1}=(k+{\frac {1}{2}},{\textrm {us}}(x_{2m}))$.
• Если $x_{2m}\in \mathbb {Q} ^{k}\smallsetminus [0,k]^{k}$, затем $x_{2m+1}={\textrm {us}}(x_{2m})$.
• Если $x_{2m}=(k+{\frac {1}{2}},z)$ и $x_{2m}\in \mathbb {Q} ^{k+1}$, затем $x_{2m+1}={\textrm {us}}^{-1}(z)$
• $\{x_{2},\ldots ,x_{n}\}$ это даун-клика в $G$

Нить $x$ является подпоследовательностью $(u_{1},\ldots ,u_{r})\in [1,n]$ определяется индуктивно следующим образом:

• $u_{1}=1$
• $u_{i+1}={\textrm {max}}(j\in [u_{i},2^{u_{1}}]:x_{j}\prec x_{u_{i}})$

Учитывая ветку $u$, мы говорим, что открыто, если $2^{u_{r}}\leq n$. Используя это, Харви Фридман определил три очень мощные функции:

• $USGCS(k)$ самый маленький $N$ такой, что любой простой порядково-инвариантный граф $G$ имеет последовательность жадной клики с верхним сдвигом в $\mathbb {Q} ^{k}$ длины не более $N$ с открытой резьбой.
• $USGDCS(k)$ самый маленький $N$ такой, что каждый порядковый инвариантный орграф $G$ имеет верхнюю смену жадной последовательности клики вниз в $\mathbb {Q} ^{k}$ длины не более $N$ с открытой резьбой.
• $USGDCS_{2}(k)$ самый маленький $N$ такой, что каждый порядковый инвариантный орграф $G$ имеет крайнюю последовательность кликов с верхним сдвигом и жадной вниз в $\mathbb {Q} ^{k}\cup \mathbb {Q} ^{k+1}$ длины не более $N$ с открытой резьбой.

$USGCS$ и $USGDCS$ в конечном итоге доминируют над всеми функциями, доказуемо рекурсивными в ${\mathsf {SRP}}$, но сами доказуемо рекурсивны в ${\mathsf {SRP^{+}}}$. $USGDCS_{2}$ в конечном итоге доминирует над всеми функциями, доказуемо рекурсивными в ${\mathsf {HUGE}}$, но сам по себе доказуемо тотален в ${\mathsf {HUGE^{+}}}$.

Ссылки

• Фридман, Харви (2 сентября 2009 г.). «Игры с конечными обещаниями» . Нью-Йоркский университет . Проверено 2 октября 2021 г.
• Фридман, Харви (30 декабря 2009 г.). «Последовательности жадной клики верхнего сдвига и большие кардиналы 1» . Нью-Йоркский университет . Проверено 2 октября 2021 г.
• Фридман, Харви (1 января 2010 г.). «Ужасно и чрезвычайно длинные конечные последовательности» . Нью-Йоркский университет . Проверено 2 октября 2021 г.