Buchholz hydra

In mathematics, especially mathematical logic, graph theory and number theory, the Buchholz hydra game is a type of hydra game, which is a single-player game based on the idea of chopping pieces off a mathematical tree. The hydra game can be used to generate a rapidly growing function, B H ( n ) {\displaystyle BH(n)} , which eventually dominates all recursive functions that are provably total in " ID ν {\displaystyle {\textrm {ID}}_{\nu }} ", and it is not provable that all hydra games terminate in ( Π 1 1 -CA)+BI {\displaystyle {\textrm {(}}\Pi _{1}^{1}{\textrm {-CA)+BI}}} .

Rules The game is played on a hydra, a finite, rooted connected tree A {\displaystyle A} , with the following properties:

The root of A {\displaystyle A} has a special label, usually denoted + {\displaystyle +} . Any other node of A {\displaystyle A} has a label ν ≤ ω {\displaystyle \nu \leq \omega } . All nodes directly above the root of A {\displaystyle A} have a label 0 {\displaystyle 0} . If the player decides to remove the top node σ {\displaystyle \sigma } of A {\displaystyle A} , the hydra will then choose an arbitrary n ∈ N {\displaystyle n\in \mathbb {N} } , where n {\displaystyle n} is a current turn number, and then transform itself into a new hydra A ( σ , n ) {\displaystyle A(\sigma ,n)} as follows. Let τ {\displaystyle \tau } represent the parent of σ {\displaystyle \sigma } , and let A − {\displaystyle A^{-}} represent the part of the hydra which remains after σ {\displaystyle \sigma } has been removed. The definition of A ( σ , n ) {\displaystyle A(\sigma ,n)} depends on the label of σ {\displaystyle \sigma } :

If the label of σ {\displaystyle \sigma } is 0 and τ {\displaystyle \tau } is the root of A {\displaystyle A} , then A ( σ , n ) {\displaystyle A(\sigma ,n)} = A − {\displaystyle A^{-}} . If the label of σ {\displaystyle \sigma } is 0 but τ {\displaystyle \tau } is not the root of A {\displaystyle A} , n {\displaystyle n} copies of τ {\displaystyle \tau } and all its children are made, and edges between them and τ {\displaystyle \tau } 's parent are added. This new tree is A ( σ , n ) {\displaystyle A(\sigma ,n)} . If the label of σ {\displaystyle \sigma } is u {\displaystyle u} for some u ∈ N {\displaystyle u\in \mathbb {N} } , let ε {\displaystyle \varepsilon } be the first node below σ {\displaystyle \sigma } that has a label v < u {\displaystyle v<u} . Define B {\displaystyle B} as the subtree obtained by starting with A ε {\displaystyle A_{\varepsilon }} and replacing the label of ε {\displaystyle \varepsilon } with u − 1 {\displaystyle u-1} and σ {\displaystyle \sigma } with 0. A ( σ , n ) {\displaystyle A(\sigma ,n)} is then obtained by taking A {\displaystyle A} and replacing σ {\displaystyle \sigma } with B {\displaystyle B} . In this case, the value of n {\displaystyle n} does not matter. If the label of σ {\displaystyle \sigma } is ω {\displaystyle \omega } , A ( σ , n ) {\displaystyle A(\sigma ,n)} is obtained by replacing the label of σ {\displaystyle \sigma } with n + 1 {\displaystyle n+1} . If σ {\displaystyle \sigma } is the rightmost head of A {\displaystyle A} , A ( n ) {\displaystyle A(n)} is written. A series of moves is called a strategy. A strategy is called a winning strategy if, after a finite amount of moves, the hydra reduces to its root. This always terminates, even though the hydra can get taller by massive amounts.

Hydra theorem Buchholz's paper in 1987 showed that the canonical correspondence between a hydra and an infinitary well-founded tree (or the corresponding term in the notation system T {\displaystyle T} associated to Buchholz's function, which does not necessarily belong to the ordinal notation system O T ⊆ T {\displaystyle OT\subseteq T} ), preserves fundamental sequences of choosing the rightmost leaves and the ( n ) {\displaystyle (n)} operation on an infinitary well-founded tree or the [ n ] {\displaystyle [n]} operation on the corresponding term in T {\displaystyle T} . The hydra theorem for Buchholz hydra, stating that there are no losing strategies for any hydra, is unprovable in Π 1 1 − C A + B I {\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}} .

BH(n) Suppose a tree consists of just one branch with x {\displaystyle x} nodes, labelled + , 0 , ω , . . . , ω {\displaystyle +,0,\omega ,...,\omega } . Call such a tree R n {\displaystyle R^{n}} . It cannot be proven in Π 1 1 − C A + B I {\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}} that for all x {\displaystyle x} , there exists k {\displaystyle k} such that R x ( 1 ) ( 2 ) ( 3 ) . . . ( k ) {\displaystyle R_{x}(1)(2)(3)...(k)} is a winning strategy. (The latter expression means taking the tree R x {\displaystyle R_{x}} , then transforming it with n = 1 {\displaystyle n=1} , then n = 2 {\displaystyle n=2} , then n = 3 {\displaystyle n=3} , etc. up to n = k {\displaystyle n=k} .) Define B H ( x ) {\displaystyle BH(x)} as the smallest k {\displaystyle k} such that R x ( 1 ) ( 2 ) ( 3 ) . . . ( k ) {\displaystyle R_{x}(1)(2)(3)...(k)} as defined above is a winning strategy. By the hydra theorem, this function is well-defined, but its totality cannot be proven in Π 1 1 − C A + B I {\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}} .

Analysis

It is possible to make a one-to-one correspondence between some hydras and ordinals. To convert a tree or subtree to an ordinal:

Inductively convert all the immediate children of the node to ordinals. Add up those child ordinals. If there were no children, this will be 0. If the label of the node is not +, apply ψ α {\displaystyle \psi _{\alpha }} , where α {\displaystyle \alpha } is the label of the node, and ψ {\displaystyle \psi } is Buchholz's function. The resulting ordinal expression is only useful if it is in normal form. Some examples are:

Notes

References

Tags