Misplaced Pages

The finite promise games are a collection of mathematical games developed by American mathematician Harvey Friedman in 2009 which are used to develop a family of fast-growing functions ${\displaystyle FPLCI(k)}$, ${\displaystyle FPCI(k)}$ and ${\displaystyle FLCI(k)}$. The greedy clique sequence is a graph theory concept, also developed by Friedman in 2010, which are used to develop fast-growing functions ${\displaystyle USGCS(k)}$, ${\displaystyle USGDCS(k)}$ and ${\displaystyle USGDCS_{2}(k)}$.

${\displaystyle {\mathsf {SMAH}}}$ represents the theory of ZFC plus, the infinite family of axioms "there exists a strongly ${\displaystyle k}$-Mahlo cardinal for all positive integers ${\displaystyle k}$. and ${\displaystyle {\mathsf {SMAH^{+}}}}$ represents the theory of ZFC plus "for each ${\displaystyle k}$, there is a strongly ${\displaystyle k}$-Mahlo cardinal". ${\displaystyle {\mathsf {SRP}}}$ represents the theory of ZFC plus, for each ${\displaystyle k}$, "there is a ${\displaystyle k}$-stationary Ramsey cardinal", and ${\displaystyle {\mathsf {SRP^{+}}}}$ represents the theory of ZFC plus "for each ${\displaystyle k}$, there is a strongly ${\displaystyle k}$-stationary Ramsey cardinal". ${\displaystyle {\mathsf {HUGE}}}$ represents the theory of ZFC plus, for each ${\displaystyle k}$, "there is a ${\displaystyle k}$-huge cardinal", and ${\displaystyle {\mathsf {HUGE^{+}}}}$ represents the theory of ZFC plus "for each ${\displaystyle k}$, there is a strongly ${\displaystyle k}$-huge cardinal".

Finite promise games

Each of the games is finite, predetermined in length, and has two players (Alice and Bob). At each turn, Alice chooses an integer or a number of integers (an offering) and the Bob has to make one of two kinds of promises restricting his future possible moves. In all games, Bob wins if and only if Bob has kept all of his promises.

Finite piecewise linear copy/invert games

Here, ${\displaystyle \mathbb {Z} }$ is the set of integers, and ${\displaystyle \mathbb {N} }$ is the set of non-negative integers. Here, all letters represent integers. We say that a map ${\displaystyle T:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$ is piecewise linear if ${\displaystyle T}$ can be defined by various affine functions with integer coefficients on each of finitely many pieces, where each piece is defined by a finite set of linear inequalities with integer coefficients. For some piecewise linear map ${\displaystyle T:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$, a ${\displaystyle T}$-inversion of ${\displaystyle x}$ is some ${\displaystyle y_{1},\ldots ,y_{k}<x}$ such that ${\displaystyle T(y_{1},\ldots ,y_{k})=x}$. We then define the game ${\displaystyle G(T,n,s)}$ for nonzero ${\displaystyle n,s}$.

${\displaystyle G(T,n,s)}$ has ${\displaystyle n}$ rounds, and alternates between Alice and Bob. At every stage of the game, Alice is required to play ${\displaystyle x\in }$, called her offering, which is either of the form ${\displaystyle y+z}$ or ${\displaystyle w!}$, where ${\displaystyle y}$ and ${\displaystyle z}$ are integers previously played by Bob. Bob is then required to either:

• Accept ${\displaystyle x}$, thereby playing ${\displaystyle x}$ and promising that there will be no ${\displaystyle T}$-inversion of ${\displaystyle x}$ among the integers ever played by Bob. This promise applies to all past, present and future plays in the game.
• Reject ${\displaystyle x}$, thereby play a ${\displaystyle T}$-inversion of ${\displaystyle x}$ and promising that ${\displaystyle x}$ is never played by Bob.

In RCA₀, it can be proven that Bob always has a winning strategy for any given game. The game ${\displaystyle G_{m}(T,n,s)}$ is a modified version where Bob is forced to accept all factorial offers by Alice ${\displaystyle >m}$. Bob always has a winning strategy for ${\displaystyle G_{m}(T,n,s)}$ for sufficiently large ${\displaystyle m,s}$, although this cannot be proven in any given consistent fragment of ${\displaystyle {\mathsf {SMAH}}}$, and only ${\displaystyle {\mathsf {SMAH^{+}}}}$. The function ${\displaystyle FPLCI(a)}$ is the smallest ${\displaystyle N}$ such that Bob can win ${\displaystyle G_{m}(T,n,s)}$ for any ${\displaystyle (m,T,n,s)}$ such that ${\displaystyle m}$ and ${\displaystyle s}$ are greater than or equal to ${\displaystyle N}$ and all the following values are less than ${\displaystyle a}$:

• ${\displaystyle n}$
• ${\displaystyle k}$ (the domain of ${\displaystyle T}$ is ${\displaystyle \mathbb {N} ^{k}}$)
• the number of pieces of ${\displaystyle T}$
• the absolute values of the coefficients of the inequalities in ${\displaystyle T}$
• the absolute values of the coefficients of the affine functions in ${\displaystyle T}$

Finite polynomial copy/invert games

Let ${\displaystyle P:\mathbb {Z} ^{k}\rightarrow Z}$ be a polynomial with integer coefficients. A special ${\displaystyle P}$-inversion at ${\displaystyle x}$ in ${\displaystyle \mathbb {Z} }$ consists of ${\displaystyle 0<y_{1},\ldots ,y_{n}<{\frac {x}{2}}}$ such that ${\displaystyle P(y_{1},\ldots ,y_{n})=x}$. We now define the game ${\displaystyle G(P,Q,n,s)}$ for nonzero ${\displaystyle n,s}$, where ${\displaystyle P,Q:\mathbb {Z} ^{k}\rightarrow \mathbb {Z} }$ are polynomials with integer coefficients. ${\displaystyle G(P,Q,n,s)}$ consists of ${\displaystyle n}$ alternating plays by Alice and Bob. At every stage of the game, Alice is required to play ${\displaystyle x\in }$ of the form ${\displaystyle P(y)}$, ${\displaystyle Q(y)}$ or ${\displaystyle (z!)!}$, where ${\displaystyle y}$ is a ${\displaystyle k}$-tuple of integers previously played by Bob. Bob is then required to either:

• Accept ${\displaystyle x}$, thereby playing ${\displaystyle x}$ and promising that there will be no special ${\displaystyle P}$- or ${\displaystyle Q}$-inversion of ${\displaystyle x}$ among the integers ever played by Bob. This promise applies to all past, present and future plays in the game.
• Reject ${\displaystyle x}$, thereby playing a special ${\displaystyle P}$- or ${\displaystyle Q}$-inversion of ${\displaystyle x}$ and promising that ${\displaystyle x}$ is never played by Bob.

Let ${\displaystyle P,Q:\mathbb {Z} ^{k}\rightarrow \mathbb {Z} }$ be polynomials with integer coefficients. In RCA₀, it can be proven that Bob always has a winning strategy for any given game. If ${\displaystyle m,s}$ are sufficiently large then Bob wins ${\displaystyle G_{m}(P,Q,n,s)}$, which is ${\displaystyle G(P,Q,n,s)}$ where Bob is forced to accept all double factorials ${\displaystyle >m}$ offered by Alice. However, once again, this cannot be proven in any given consistent fragment of ${\displaystyle {\mathsf {SMAH}}}$, and only ${\displaystyle {\mathsf {SMAH^{+}}}}$. The function ${\displaystyle FPCI(a)}$ is the smallest ${\displaystyle N}$ such that Bob can win ${\displaystyle G_{m}(P,Q,n,s)}$ for any ${\displaystyle (m,P,Q,n,s)}$ such that ${\displaystyle m}$ and ${\displaystyle s}$ are greater than or equal to ${\displaystyle N}$ and all the following values are less than ${\displaystyle a}$:

• ${\displaystyle n}$
• ${\displaystyle k}$ (the domain of the polynomials is ${\displaystyle \mathbb {Z} ^{k}}$)
• the degrees of ${\displaystyle P}$ and ${\displaystyle Q}$
• the absolute values of the coefficients of ${\displaystyle P}$ and ${\displaystyle Q}$

Finite linear copy/invert games

We say that ${\displaystyle x,y\in \mathbb {N} ^{k}}$ are additively equivalent if and only if ${\displaystyle \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}}$. For nonzero integers ${\displaystyle p,n,s}$ and ${\displaystyle v_{1},\ldots ,v_{p}\in \mathbb {N} ^{k}}$, we define the game ${\displaystyle G(v_{1},\ldots ,v_{p};n,s)}$ which consists of ${\displaystyle n}$ alternating rounds between Alice and Bob. At every stage of the game, Alice is required to play an integer ${\displaystyle x\in }$ of the form ${\displaystyle y+z}$ or ${\displaystyle w!}$, where ${\displaystyle y,z}$ are integers previously played by Bob. Bob is then required to either:

• Accept ${\displaystyle x}$, thereby playing ${\displaystyle x}$ and promising that ${\displaystyle x}$ cannot be written as ${\displaystyle \sum _{q=1}^{k}y_{q}}$, where ${\displaystyle (y_{1},\ldots ,y_{k})}$ is additively equivalent to some ${\displaystyle v_{j}}$, and ${\displaystyle y_{1},\ldots ,y_{k}}$ are integers played by Bob at various times.
• Reject ${\displaystyle x}$, thereby playing ${\displaystyle y_{1},\ldots ,y_{k}}$, where ${\displaystyle x=\sum _{q=1}^{k}y_{q}}$ and ${\displaystyle (y_{1},\ldots ,y_{k})}$ is additively equivalent to some ${\displaystyle v_{j}}$, and promises that ${\displaystyle x}$ is never played by Bob.

Let ${\displaystyle v_{1},\ldots ,v_{p}\in \mathbb {N} ^{k}}$. In RCA₀, it can be proven that Bob always has a winning strategy for any given game. Let ${\displaystyle v_{1},\ldots ,v_{p}\in \mathbb {N} ^{k}}$. If ${\displaystyle m}$ is sufficiently large, then Bob wins ${\displaystyle G_{m}(v_{1},\ldots ,v_{p};n,s)}$, where Bob accepts all factorials ${\displaystyle >m}$ offered by Alice. However, once again, this cannot be proven in any given consistent fragment of ${\displaystyle {\mathsf {SMAH}}}$, and only ${\displaystyle {\mathsf {SMAH^{+}}}}$. The function ${\displaystyle FLCI(a)}$ is the smallest ${\displaystyle N}$ such that Bob can win ${\displaystyle G_{m}(v_{1},\ldots ,v_{p};n,s)}$ for any ${\displaystyle (m,v_{1},\ldots ,v_{p};n,s)}$ such that ${\displaystyle m}$ is greater than or equal to ${\displaystyle N}$, ${\displaystyle n,s}$ are positive and all the following values are less than ${\displaystyle a}$:

• ${\displaystyle k}$
• ${\displaystyle p}$
• the number of components of each vector in ${\displaystyle v}$

Functions

As shown by Friedman, the three functions ${\displaystyle FPLCI(a)}$, ${\displaystyle FPCI(a)}$ and ${\displaystyle FLCI(a)}$ are extremely fast-growing, eventually dominating any functions provably recursive in any consistent fragment of ${\displaystyle {\mathsf {SMAH}}}$ (one of these is ZFC), but they are computable and provably total in ${\displaystyle {\mathsf {SMAH^{+}}}}$.

Greedy clique sequences

${\displaystyle \mathbb {Q} ^{*}}$ denotes the set of all tuples of rational numbers. We use subscripts to denote indexes into tuples (starting at 1) and angle brackets to denote concatenation of tuples, e.g. ${\displaystyle \langle (0,1),(2,3)\rangle =(0,1,2,3)}$. Given ${\displaystyle a\in \mathbb {Q} ^{*}}$, we define the upper shift of ${\displaystyle a}$, denoted ${\displaystyle {\textrm {us}}(a)}$ to be the result of adding 1 to all its nonnegative components. Given ${\displaystyle a,b\in \mathbb {Q} ^{*}}$, we say that ${\displaystyle a\preceq b\iff {\textrm {max}}(a)\leq {\textrm {max}}(b)}$ and ${\displaystyle a\prec b\iff {\textrm {max}}(a)<{\textrm {max}}(b)}$. ${\displaystyle a,b\in \mathbb {Q} ^{*}}$ are called order equivalent if and only if they have the same length and for all ${\displaystyle i,j}$, ${\displaystyle a_{i}<a_{j}}$ iff ${\displaystyle b_{i}<b_{j}}$. A set ${\displaystyle E\subseteq \mathbb {Q} ^{*}}$ is order invariant iff for all order equivalent ${\displaystyle x}$ and ${\displaystyle y}$, ${\displaystyle x\in E\iff y\in E}$.

Let ${\displaystyle H}$ be a graph with vertices in ${\displaystyle \mathbb {Q} ^{*}}$. Let ${\displaystyle E}$ be the set defined as follows: for every edge ${\displaystyle (x,y)}$ in ${\displaystyle H}$, their concatenation ${\displaystyle \langle x,y\rangle }$ is in ${\displaystyle E}$. Then if ${\displaystyle E}$ is order invariant, we say that ${\displaystyle H}$ is order invariant. When ${\displaystyle H}$ is order invariant, ${\displaystyle H}$ has infinite edges. We are given ${\displaystyle k\in \mathbb {N} }$, ${\displaystyle S\subseteq \mathbb {Q} ^{*}}$, and a simple graph ${\displaystyle G}$ (or a digraph in the case of upper shift greedy down clique sequences) with vertices in ${\displaystyle S}$. We define a sequence ${\displaystyle x}$ as a nonempty tuple ${\displaystyle (x_{1},\ldots ,x_{n})}$ where ${\displaystyle x_{i}\in S}$. This is not a tuple but rather a tuple of tuples. When ${\displaystyle S=\mathbb {Q} ^{k}}$, ${\displaystyle x}$ is said to be an upper shift greedy clique sequence in ${\displaystyle \mathbb {Q} ^{k}}$ if it satisfies the following:

• ${\displaystyle x_{1}}$ consists only of zeroes.
• Let ${\displaystyle m}$ be an integer such that ${\displaystyle 2\leq 2m\leq k-1}$, or a positive integer if we allow infinite sequences. ${\displaystyle Y=\langle x_{1},\ldots ,x_{2m-1}\rangle }$ and let ${\displaystyle y=(Y_{m},\ldots ,Y_{m+k-1})}$. Then, ${\displaystyle x_{2m}\preceq y}$, ${\displaystyle (y,x_{2m})}$ is not an edge of ${\displaystyle G}$, and ${\displaystyle x_{2m+1}={\textrm {us}}(x_{2m})}$.
• ${\displaystyle \{x_{2},\ldots ,x_{n}\}}$ is a clique in ${\displaystyle G}$, i.e. ${\displaystyle G}$ contains as an edge every pair of vertices in ${\displaystyle \{x_{2},\ldots ,x_{n}\}}$.

When ${\displaystyle S=\mathbb {Q} ^{k}}$, ${\displaystyle x}$ is said to be an upper shift down greedy clique sequence in ${\displaystyle \mathbb {Q} ^{k}}$ if it satisfies the following:

• ${\displaystyle x_{1}}$ consists only of zeroes.
• Let ${\displaystyle m}$ be an integer such that ${\displaystyle 2\leq 2m\leq k-1}$, or a positive integer if we allow infinite sequences. ${\displaystyle Y=\langle x_{1},\ldots ,x_{2m-1}\rangle }$ and let ${\displaystyle y=(Y_{m},\ldots ,Y_{m+k-1})}$. Then, ${\displaystyle x_{2m}=y}$ or ${\displaystyle x_{2m}\prec y}$ and ${\displaystyle (y,x_{2m})}$ is not an edge of ${\displaystyle G}$; and ${\displaystyle x_{2m+1}={\textrm {us}}(x_{2m})}$.
• ${\displaystyle \{x_{2},\ldots ,x_{n}\}}$ is a down clique in ${\displaystyle G}$, i.e. for all ${\displaystyle f,g\in \{x_{2},\ldots ,x_{n}\}}$ and ${\displaystyle g\prec f}$, ${\displaystyle (f,g)}$ is an edge of ${\displaystyle G}$.

When ${\displaystyle S=\mathbb {Q} ^{k}\cup \mathbb {Q} ^{k+1}}$, ${\displaystyle x}$ is said to be an extreme upper shift down greedy clique sequence in ${\displaystyle \mathbb {Q} ^{k}\cup \mathbb {Q} ^{k+1}}$ if it satisfies the following:

• ${\displaystyle x_{1}}$ consists only of zeroes.
• Let ${\displaystyle m}$ be an integer such that ${\displaystyle 2\leq 2m\leq k-1}$, or a positive integer if we allow infinite sequences. ${\displaystyle Y=\langle x_{1},\ldots ,x_{2m-1}\rangle }$ and let ${\displaystyle y=(Y_{m},\ldots ,Y_{m+k-1})}$. Then, ${\displaystyle x_{2m}=y}$ or ${\displaystyle x_{2m}\prec y}$ and ${\displaystyle (y,x_{2m})}$ is not an edge of ${\displaystyle G}$; and ${\displaystyle x_{2m+1}={\textrm {us}}(x_{2m})}$.
• If ${\displaystyle x_{2m}\in ^{k}}$, then ${\displaystyle x_{2m+1}=(k+{\frac {1}{2}},{\textrm {us}}(x_{2m}))}$.
• If ${\displaystyle x_{2m}\in \mathbb {Q} ^{k}\smallsetminus ^{k}}$, then ${\displaystyle x_{2m+1}={\textrm {us}}(x_{2m})}$.
• If ${\displaystyle x_{2m}=(k+{\frac {1}{2}},z)}$ and ${\displaystyle x_{2m}\in \mathbb {Q} ^{k+1}}$, then ${\displaystyle x_{2m+1}={\textrm {us}}^{-1}(z)}$
• ${\displaystyle \{x_{2},\ldots ,x_{n}\}}$ is a down clique in ${\displaystyle G}$

The thread of ${\displaystyle x}$ is a subsequence ${\displaystyle (u_{1},\ldots ,u_{r})\in }$ defined inductively like so:

• ${\displaystyle u_{1}=1}$
• ${\displaystyle u_{i+1}={\textrm {max}}(j\in :x_{j}\prec x_{u_{i}})}$

Given a thread ${\displaystyle u}$, we say that is open if ${\displaystyle 2^{u_{r}}\leq n}$. Using this Harvey Friedman defined three very powerful functions:

• ${\displaystyle USGCS(k)}$ is the smallest ${\displaystyle N}$ such that every simple, order invariant graph ${\displaystyle G}$ has an upper shift greedy clique sequence in ${\displaystyle \mathbb {Q} ^{k}}$ of length at most ${\displaystyle N}$ with an open thread.
• ${\displaystyle USGDCS(k)}$ is the smallest ${\displaystyle N}$ such that every order invariant digraph ${\displaystyle G}$ has an upper shift greedy down clique sequence in ${\displaystyle \mathbb {Q} ^{k}}$ of length at most ${\displaystyle N}$ with an open thread.
• ${\displaystyle USGDCS_{2}(k)}$ is the smallest ${\displaystyle N}$ such that every order invariant digraph ${\displaystyle G}$ has an extreme upper shift greedy down clique sequence in ${\displaystyle \mathbb {Q} ^{k}\cup \mathbb {Q} ^{k+1}}$ of length at most ${\displaystyle N}$ with an open thread.

${\displaystyle USGCS}$ and ${\displaystyle USGDCS}$ eventually dominate all functions provably recursive in ${\displaystyle {\mathsf {SRP}}}$, but are themselves provably recursive in ${\displaystyle {\mathsf {SRP^{+}}}}$. ${\displaystyle USGDCS_{2}}$ eventually dominates all functions provably recursive in ${\displaystyle {\mathsf {HUGE}}}$, but is itself provably total in ${\displaystyle {\mathsf {HUGE^{+}}}}$.

References

• Friedman, Harvey (2009-09-02). "Finite Promise Games". New York University. Retrieved 2021-10-02.
• Friedman, Harvey (2009-12-30). "Upper Shift Greedy Clique Sequences and Large Cardinals 1". New York University. Retrieved 2021-10-02.
• Friedman, Harvey (2010-01-01). "Terrifically and Extremely Long Finite Sequences". New York University. Retrieved 2021-10-02.

• Mathematical games
• Graph theory