FANDOM

10,619 Pages

Finite promise games are a family of four closely related two-player games defined by Harvey Friedman.[1] From three of these games arise some fast-growing functions that eventually dominate all recursive functions provably total in an extension of ZFC known as SMAH, but are provably total in a stronger theory known as SMAH+.

Overview

As the name implies, each of games is finite, and its length is actually predetermined. At each turn, one of the players (which we will call Nathan) chooses an integer or a number of integers (an offering) and the other player (which we will call Wojtek) has to make one of two kinds of promises restricting his future possible moves. Wojtek wins if and only if he can keep all the promises until the end of the game.

Throughout the following sections, three major axiomatic systems are referenced. RCA0 consists of the axioms of Robinson arithmetic, $$\Sigma_1^0$$-induction, and $$\Delta_1^0$$-comprehension (see Second-order arithmetic). SMAH refers to ZFC, plus the infinite family of axioms "there exists a strongly $$k$$-Mahlo cardinal" for all positive integers $$k$$. SMAH+ refers to ZFC, plus "for all $$k$$, there exists a strongly $$k$$-Mahlo cardinal." The distinction between the two latter theories is that SMAH can only refer to finitely many of its axioms, and thus is incapable of assembling infinitely many of them to prove SMAH+'s sentence.

Finite piecewise linear copy/invert games

Call a function $$T: \mathbb{N}^k \mapsto \mathbb{N}$$ piecewise linear iff it can be expressed using finitely many affine functions, using inequalities with integer coefficients to separate the function's pieces. Given a piecewise linear function $$T$$, we say that a vector $$\mathbf{y} \in \mathbb{N}^k$$ is a $$T$$-inversion of $$x$$ iff $$T(\mathbf{y}) = x$$.

Given a piecewise linear function $$T: \mathbb{N}^k \mapsto \mathbb{N}$$ and two positive integers $$n$$ and $$s$$, we define the finite piecewise linear copy/invert game $$G(T, n, s)$$ as follows. $$G(T, n, s)$$ is a two-player game alternating between Nathan and Wojtek, with $$n$$ rounds in total. Nathan goes first.

On his turn, Nathan selects a number $$x \in [0, s]$$, either of the form $$w!$$ or $$y + z$$, where $$y$$ and $$z$$ were previously played by Wojtek. $$x$$ is called his offer. Wojtek either has the choice of accepting or rejecting the offer:

• By accepting, he plays $$x$$, and promises that none of the integers he ever plays will contain a $$T$$ inversion of $$x$$.
• By rejecting, he plays a $$T$$ inversion of $$x$$ of his choice, and promises that none of the integers that he ever plays are $$x$$.

If Wojtek ever breaks one of his promises, he loses the game. If Wojtek lasts the entire $$n$$ rounds without ever breaking a promise, he wins. (Promises apply to all past, present, and future plays within the game.)

Wojtek always has a winning strategy for any given FPLCI game. This is provable in RCA0.

He can still win even if we restrict the offers that he is allowed to reject. Consider the modified game $$G_m(T, n, s)$$ where Wojtek is forced to accept all factorial numbers greater than $$m$$. Wojtek can win $$G_m(T, n, s)$$ for all $$T$$ and $$n$$ and sufficiently large $$m$$ and $$s$$ (a fact provable in SMAH+, but not in any consistent fragment of SMAH).

Let $$FPLCI(a)$$ be the minimal $$N$$ such that Wojtek can win $$G_N(T, n, N)$$ where all the following are less than $$a$$:

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

Finite polynomial copy/invert games

All polynomials discussed in this section have the signature $$\mathbb{Z}^k \mapsto \mathbb{Z}$$ (for a fixed $$k$$) and have only integer coefficients.

Given a polynomial $$P$$, we say that a vector $$\mathbf{y}$$ is a special $$P$$-inversion of $$x$$ iff $$P(\mathbf{y}) = x$$ and every component of $$\mathbf{y}$$ is strictly between 0 and $$x/2$$.

Given two polynomials $$P$$ and $$Q$$ and two positive integers $$n$$ and $$s$$, we define the finite polynomial copy/invert game $$G(P, Q, n, s)$$ as follows. $$G(P, Q, n, s)$$ is a two-player game alternating between Nathan and Wojtek, with $$n$$ rounds in total. Nathan goes first.

On his turn, Nathan selects a number $$x \in [-s, s]$$, of the form $$(w!)!$$[2] or $$P(\mathbf{y})$$ or $$Q(\mathbf{y})$$, where $$\mathbf{y}$$ is a vector in $$\mathbb{Z}^k$$ whose components were all integers previously played by Wojtek. $$x$$ is called his offer. Wojtek either has the choice of accepting or rejecting the offer:

• By accepting, he plays $$x$$, and promises that the integers he plays never contain the complete components of a special $$P$$ or $$Q$$ inversion of $$x$$.
• By rejecting, he plays a special $$P$$ or $$Q$$ inversion of $$x$$ of his choice, and promises that none of the integers that he ever plays are $$x$$.

If Wojtek ever breaks one of his promises, he loses the game. If Wojtek lasts the entire $$n$$ rounds without ever breaking a promise, he wins. (Promises apply to all past, present, and future plays within the game.)

Wojtek always has a winning strategy for any given FPCI game. This is provable in RCA0.

In fact, he can still win even if we restrict the offers that he is allowed to reject. Consider the modified game $$G_m(P, Q, n, s)$$ where Wojtek is forced to accept all factorial numbers greater than $$m$$. Wojtek can win $$G_m(P, Q, n, s)$$ for all $$P,Q,n$$ and sufficiently large $$m$$ and $$s$$ (a fact provable in SMAH+, but not in any consistent fragment of SMAH).

Let $$FPCI(a)$$ be the minimal $$N$$ such that Wojtek can win $$G_N(P, Q, n, N)$$ where all the following are less than $$a$$:

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

Finite order invariant copy/invert games

Let $$R : \mathbb{N}^{2k} \mapsto \{0, 1\}$$ be order invariant — that is, the order of its inputs does not affect its output. Given a vector $$\mathbf{x} \in \mathbb{N}^{k}$$, we say that a vector $$\mathbf{y} \in \mathbb{N}^{k}$$ is an R-inversion of $$\mathbf{x}$$ iff $$\max(\mathbf{y}) < \max(\mathbf{x})$$ and $$R(\mathbf{x}, \mathbf{y}) = 1$$ (where the components of the two vectors are concatenated into a vector with $$2k$$ components, which is the argument to R).

Given order-invariant $$R : \mathbb{N}^{2k} \mapsto \{0, 1\}$$ and two positive integers $$n$$ and $$s$$, we define the finite order invariant copy/invert game $$G(R, n, s)$$ as follows. $$G(R, n, s)$$ is a two-player game alternating between Nathan and Wojtek, with $$n$$ rounds in total. Nathan goes first.

On his turn, Nathan selects an integer vector $$\mathbf{x} \in [-s, s]^k$$, each component being of the form $$z$$ or $$z + 1$$ or $$w!$$, where $$z$$ is an integer previously played by Wojtek. $$\mathbf{x}$$ is called his offer. Wojtek either has the choice of accepting or rejecting the offer:

• By accepting, he plays $$\mathbf{x}$$, and promises that he never plays an $$R$$ inversion of $$\mathbf{x}$$.
• By rejecting, he plays an $$R$$ inversion of $$\mathbf{x}$$ of his choice, and promises that he will never play $$\mathbf{x}$$.

If Wojtek ever breaks one of his promises, he loses the game. If Wojtek lasts the entire $$n$$ rounds without ever breaking a promise, he wins. (Promises apply to all past, present, and future plays within the game.)

Wojtek always has a winning strategy for any given FOICI game. This is provable in RCA0.

Friedman does not specify any fast-growing functions derived from FOICI games, however.

Finite linear copy/invert games

Given two vectors $$\mathbf{x},\mathbf{y} \in \mathbb{N}^k$$, we say that they are additively equivalent iff, for all $$i, j \leq k$$, $$\sum^i \mathbf{x} < \sum^j \mathbf{x} \Rightarrow \sum^i \mathbf{y} < \sum^j \mathbf{y}$$ (where $$\sum^n \mathbf{v}$$ is the sum of the first $$n$$ components in $$\mathbf{v}$$).

Let $$V$$ be a finite tuple of vectors in $$\mathbb{N}^k$$ and two positive integers $$n$$ and $$s$$, and define the finite linear copy/invert game $$G(V, n, s)$$ as follows. $$G(V, n, s)$$ is a two-player game alternating between Nathan and Wojtek, with $$n$$ rounds in total. Nathan goes first.

On his turn, Nathan selects a number $$x \in [0, s]$$, either of the form $$w!$$ or $$y + z$$, where $$y$$ and $$z$$ are integers previously played by Wojtek.[3] $$x$$ is called his offer. Wojtek either has the choice of accepting or rejecting the offer:

• By accepting, he plays $$x$$, and promises that $$x$$ can never be written as $$\sum \mathbf{y}$$, where all the components of $$\mathbf{y}$$ were played by Wojtek at any time and $$\mathbf{y}$$ is additively equivalent to a vector in $$V$$.
• By rejecting, he chooses a vector $$\mathbf{y} = (y_1,\ldots,y_k)$$ in $$\mathbb{N}^k$$ such that $$\sum \mathbf{y} = x$$ and $$\mathbf{y}$$ is additively equivalent to a vector in $$V$$, plays the natural numbers $$y_1,\ldots,y_k$$, and promises that he will never play $$x$$.

If Wojtek ever breaks one of his promises, he loses the game. If Wojtek lasts the entire $$n$$ rounds without ever breaking a promise, he wins. (Promises apply to all past, present, and future plays within the game.)

Wojtek always has a winning strategy for any given FLCI game. This is provable in RCA0.

In fact, he can still win even if we restrict the offers that he is allowed to reject. Consider the modified game $$G_m(V, n, s)$$ where Wojtek is forced to accept all factorial numbers greater than $$m$$. Wojtek can win $$G_m(V, n, s)$$ for all $$V,n,s$$ and sufficiently large $$m$$ (a fact provable in SMAH+, but not in any consistent fragment of SMAH).

Let $$FLCI(a)$$ be the minimal $$N$$ such that Wojtek can win $$G_N(V, n, s)$$ for all $$n, s \geq 1$$ where all the following are less than $$a$$:

• $$k$$
• the number of vectors in $$V$$
• the components of the vectors in $$V$$

Functions

As shown by Friedman, the three functions $$FPLCI(a)$$, $$FPCI(a)$$ and $$FLCI(a)$$ are extremely fast-growing, eventually dominating any functions provably recursive in a consistent fragment of SMAH. (Note that Friedman did not explicitly describe these three functions, but the definitions here have been directly inferred from his work.)

Computability

Since Friedman did not give explicit algorithms to compute those functions, their computability is unknown. At least, the well-definedness of each value itself is provable in arithmetic according to Friedman's statement without proofs.

Sources

1. http://cs.nyu.edu/pipermail/fom/2009-September/014007.html
2. Erroneously written $$w!!$$ in the original posting; confirmed by pers. comm.
3. In the original definition, Nathan (or Alice if we follow the original setting) is required to select a number "$$x \in [0,x]$$", but it is an obvious typo.