Collection of mathematical games
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
,
and
. The greedy clique sequence is a graph theory concept, also developed by Friedman in 2010, which are used to develop fast-growing functions
,
and
.
represents the theory of ZFC plus, the infinite family of axioms "there exists a strongly
-Mahlo cardinal for all positive integers
. and
represents the theory of ZFC plus "for each
, there is a strongly
-Mahlo cardinal".
represents the theory of ZFC plus, for each
, "there is a
-stationary Ramsey cardinal", and
represents the theory of ZFC plus "for each
, there is a strongly
-stationary Ramsey cardinal".
represents the theory of ZFC plus, for each
, "there is a
-huge cardinal", and
represents the theory of ZFC plus "for each
, there is a strongly
-huge cardinal".
Finite promise games
[edit]
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
[edit]
Here,
is the set of integers, and
is the set of non-negative integers. Here, all letters represent integers. We say that a map
is piecewise linear if
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
, a
-inversion of
is some
such that
. We then define the game
for nonzero
.
has
rounds, and alternates between Alice and Bob. At every stage of the game, Alice is required to play
, called her offering, which is either of the form
or
, where
and
are integers previously played by Bob. Bob is then required to either:
- Accept
, thereby playing
and promising that there will be no
-inversion of
among the integers ever played by Bob. This promise applies to all past, present and future plays in the game.
- Reject
, thereby play a
-inversion of
and promising that
is never played by Bob.
In RCA0, it can be proven that Bob always has a winning strategy for any given game. The game
is a modified version where Bob is forced to accept all factorial offers by Alice
. Bob always has a winning strategy for
for sufficiently large
, although this cannot be proven in any given consistent fragment of
, and only
. The function
is the smallest
such that Bob can win
for any
such that
and
are greater than or equal to
and all the following values are less than
:
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
(the domain of
is
)
- the number of pieces of
![{\displaystyle T}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
- the absolute values of the coefficients of the inequalities in
![{\displaystyle T}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
- the absolute values of the coefficients of the affine functions in
![{\displaystyle T}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0)
Finite polynomial copy/invert games
[edit]
Let
be a polynomial with integer coefficients. A special
-inversion at
in
consists of
such that
. We now define the game
for nonzero
, where
are polynomials with integer coefficients.
consists of
alternating plays by Alice and Bob. At every stage of the game, Alice is required to play
of the form
,
or
, where
is a
-tuple of integers previously played by Bob. Bob is then required to either:
- Accept
, thereby playing
and promising that there will be no special
- or
-inversion of
among the integers ever played by Bob. This promise applies to all past, present and future plays in the game.
- Reject
, thereby playing a special
- or
-inversion of
and promising that
is never played by Bob.
Let
be polynomials with integer coefficients. In RCA0, it can be proven that Bob always has a winning strategy for any given game. If
are sufficiently large then Bob wins
, which is
where Bob is forced to accept all double factorials
offered by Alice. However, once again, this cannot be proven in any given consistent fragment of
, and only
. The function
is the smallest
such that Bob can win
for any
such that
and
are greater than or equal to
and all the following values are less than
:
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
(the domain of the polynomials is
)
- the degrees of
and ![{\displaystyle Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed)
- the absolute values of the coefficients of
and ![{\displaystyle Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed)
Finite linear copy/invert games
[edit]
We say that
are additively equivalent if and only if
. For nonzero integers
and
, we define the game
which consists of
alternating rounds between Alice and Bob. At every stage of the game, Alice is required to play an integer
of the form
or
, where
are integers previously played by Bob. Bob is then required to either:
- Accept
, thereby playing
and promising that
cannot be written as
, where
is additively equivalent to some
, and
are integers played by Bob at various times.
- Reject
, thereby playing
, where
and
is additively equivalent to some
, and promises that
is never played by Bob.
Let
. In RCA0, it can be proven that Bob always has a winning strategy for any given game. Let
. If
is sufficiently large, then Bob wins
, where Bob accepts all factorials
offered by Alice. However, once again, this cannot be proven in any given consistent fragment of
, and only
. The function
is the smallest
such that Bob can win
for any
such that
is greater than or equal to
,
are positive and all the following values are less than
:
![{\displaystyle k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
![{\displaystyle p}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
- the number of components of each vector in
![{\displaystyle v}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
As shown by Friedman, the three functions
,
and
are extremely fast-growing, eventually dominating any functions provably recursive in any consistent fragment of
(one of these is ZFC), but they are computable and provably total in
.
Greedy clique sequences
[edit]
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.
. Given
, we define the upper shift of
, denoted
to be the result of adding 1 to all its nonnegative components. Given
, we say that
and
.
are called order equivalent if and only if they have the same length and for all
,
iff
. A set
is order invariant iff for all order equivalent
and
,
.
Let
be a graph with vertices in
. Let
be the set defined as follows: for every edge
in
, their concatenation
is in
. Then if
is order invariant, we say that
is order invariant. When
is order invariant,
has infinite edges. We are given
,
, and a simple graph
(or a digraph in the case of upper shift greedy down clique sequences) with vertices in
. We define a sequence
as a nonempty tuple
where
. This is not a tuple but rather a tuple of tuples. When
,
is said to be an upper shift greedy clique sequence in
if it satisfies the following:
consists only of zeroes.
- Let
be an integer such that
, or a positive integer if we allow infinite sequences.
and let
. Then,
,
is not an edge of
, and
.
is a clique in
, i.e.
contains as an edge every pair of vertices in
.
When
,
is said to be an upper shift down greedy clique sequence in
if it satisfies the following:
consists only of zeroes.
- Let
be an integer such that
, or a positive integer if we allow infinite sequences.
and let
. Then,
or
and
is not an edge of
; and
.
is a down clique in
, i.e. for all
and
,
is an edge of
.
When
,
is said to be an extreme upper shift down greedy clique sequence in
if it satisfies the following:
consists only of zeroes.
- Let
be an integer such that
, or a positive integer if we allow infinite sequences.
and let
. Then,
or
and
is not an edge of
; and
.
- If
, then
.
- If
, then
.
- If
and
, then ![{\displaystyle x_{2m+1}={\textrm {us}}^{-1}(z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13cad79fcf936174c6a3f870a3ba0f8ac07cf358)
is a down clique in ![{\displaystyle G}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b)
The thread of
is a subsequence
defined inductively like so:
![{\displaystyle u_{1}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53b719bbf38dcbfe590bccc532c62cc50e24a857)
![{\displaystyle u_{i+1}={\textrm {max}}(j\in [u_{i},2^{u_{1}}]:x_{j}\prec x_{u_{i}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e548cba2ce98cb1f9a4bc303b6d7d0ba2bda309)
Given a thread
, we say that is open if
. Using this Harvey Friedman defined three very powerful functions:
is the smallest
such that every simple, order invariant graph
has an upper shift greedy clique sequence in
of length at most
with an open thread.
is the smallest
such that every order invariant digraph
has an upper shift greedy down clique sequence in
of length at most
with an open thread.
is the smallest
such that every order invariant digraph
has an extreme upper shift greedy down clique sequence in
of length at most
with an open thread.
and
eventually dominate all functions provably recursive in
, but are themselves provably recursive in
.
eventually dominates all functions provably recursive in
, but is itself provably total in
.