Buchholz hydra

Template:Short description 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, $BH(n)$, which eventually dominates all recursive functions that are provably total in "${\text{ID}}_{\nu }$", and it is not provable that all hydra games terminate in $\text{(}{\mathrm{\Pi }}_1^1\text{-CA)+BI}$.Template:EfnTemplate:ClarifyTemplate:R

Rules

The game is played on a hydra, a finite, rooted connected tree $A$, with the following properties:

• The root of $A$ has a special label, usually denoted $+$.
• Any other node of $A$ has a label $\nu \le \omega$.
• All nodes directly above the root of $A$ have a label $0$.

If the player decides to remove the top node $\sigma$ of $A$, the hydra will then choose an arbitrary $n\in \mathbb{N}$, where $n$ is a current turn number, and then transform itself into a new hydra $A(\sigma ,n)$ as follows. Let $\tau$ represent the parent of $\sigma$, and let $A^{-}$ represent the part of the hydra which remains after $\sigma$ has been removed. The definition of $A(\sigma ,n)$ depends on the label of $\sigma$:

• If the label of $\sigma$ is 0 and $\tau$ is the root of $A$, then $A(\sigma ,n)$ = $A^{-}$.
• If the label of $\sigma$ is 0 but $\tau$ is not the root of $A$, $n$ copies of $\tau$ and all its children are made, and edges between them and $\tau$'s parent are added. This new tree is $A(\sigma ,n)$.
• If the label of $\sigma$ is $u$ for some $u\in \mathbb{N}$, let $\epsilon$ be the first node below $\sigma$ that has a label $v<u$. Define $B$ as the subtree obtained by starting with $A_{\epsilon }$ and replacing the label of $\epsilon$ with $u-1$ and $\sigma$ with 0. $A(\sigma ,n)$ is then obtained by taking $A$ and replacing $\sigma$ with $B$. In this case, the value of $n$ does not matter.
• If the label of $\sigma$ is $\omega$, $A(\sigma ,n)$ is obtained by replacing the label of $\sigma$ with $n+1$.

If $\sigma$ is the rightmost head of $A$, $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.Template:R

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$ associated to Buchholz's function, which does not necessarily belong to the ordinal notation system $OT\subseteq T$), preserves fundamental sequences of choosing the rightmost leaves and the $(n)$ operation on an infinitary well-founded tree or the $[n]$ operation on the corresponding term in $T$.Template:R

The hydra theorem for Buchholz hydra, stating that there are no losing strategies for any hydra, is unprovable in ${\Pi }_{\mathrm{𝟣}}^{\mathrm{𝟣}}\mathsf{-}𝖢𝖠\mathsf{+}𝖡𝖨$.Template:R

BH(n)

Suppose a tree consists of just one branch with $x$ nodes, labelled $+,0,\omega ,\mathrm{...},\omega$. Call such a tree $R^n$. It cannot be proven in ${\Pi }_{\mathrm{𝟣}}^{\mathrm{𝟣}}\mathsf{-}𝖢𝖠\mathsf{+}𝖡𝖨$ that for all $x$, there exists $k$ such that $R_x(1)(2)(3)\mathrm{...}(k)$ is a winning strategy. (The latter expression means taking the tree $R_x$, then transforming it with $n=1$, then $n=2$, then $n=3$, etc. up to $n=k$.)Template:R

Define $BH(x)$ as the smallest $k$ such that $R_x(1)(2)(3)\mathrm{...}(k)$ as defined above is a winning strategy. By the hydra theorem, this function is well-defined, but its totality cannot be proven in ${\Pi }_{\mathrm{𝟣}}^{\mathrm{𝟣}}\mathsf{-}𝖢𝖠\mathsf{+}𝖡𝖨$.

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 ${\psi }_{\alpha }$, where $\alpha$ is the label of the node, and $\psi$ is Buchholz's function.

The resulting ordinal expression is only useful if it is in normal form. Some examples are:

Conversion

Hydra	Ordinal
$+$	$0$
$+(0)$	${\psi }_0(0)=1$
$+(0)(0)$	$2$
$+(0(0))$	${\psi }_0(1)=\omega$
$+(0(0))(0)$	$\omega +1$
$+(0(0))(0(0))$	$\omega \cdot 2$
$+(0(0)(0))$	${\omega }^2$
$+(0(0(0)))$	${\omega }^{\omega }$
$+(0(1))$	${\epsilon }_0$
$+(0(1)(1))$	${\epsilon }_1$
$+(0(1(0)))$	${\epsilon }_{\omega }$
$+(0(1(1)))$	${\zeta }_0$
$+(0(1(1(1))))$	${\mathrm{\Gamma }}_0$
$+(0(1(1(1(0)))))$	SVO
$+(0(1(1(1(1)))))$	LVO
$+(0(2))$	BHO
$+(0(\omega ))$	BO

Further reading

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation

External links

• Template:Citation