$X$ を集合とします。例えば $X$ は特定の文字のみからなる文字列の集合などです。今回説明するのは、$X$ の部分集合などを再帰的に定義する際の数学特有の言い回しです。

例えば $X$ の要素 $c$ と非負整数 $n_0,m_0,n_1,m_1$ と写像 $F_0 \colon X^{n_0} \times X^{m_0} \to X$ と $F_1 \colon X^{n_1} \times X^{m_1} \to X$ を用いて次のような書き方をすることがあります：

$X$ の部分集合 $A$ を以下のように再帰的に定める：

• $c \in A$ である。
• 任意の $(a,t) \in A^{n_0} \times X^{m_0}$ に対し、$F_0(a,t) \in A$ である。
• 任意の $(a,t) \in A^{n_1} \times X^{m_1}$ に対し、$F_1(a,t) \in A$ である。

これはあくまで例であって、今回は $3$ つの条件としましたが一般には $3$ つとは限りませんし、写像を用いるのではなく関係を用いることもあります。再帰的定義の一般の定式化^{[1] 6.1.1 Definition}はかなり抽象的なので、今回はこの問題を解く上で必要な例のみを考えることにします。

ここで重要なのは、この定義文は $A$ が単に $3$ つの条件を全て満たす $X$ の任意の部分集合であるという意味を持つのではなく、次の定義文を表すということです：^{[1] 6.1.2 Definitionおよびその直後の段落参照}

$X$ の部分集合 $A$ を、以下の $3$ 条件を全て満たす $X$ の部分集合 $B$ 全体の共通部分と定める：

• $c \in B$ である。
• 任意の $(a,t) \in B^{n_0} \times X^{m_0}$ に対し、$F_0(a,t) \in B$ である。
• 任意の $(a,t) \in B^{n_1} \times X^{m_1}$ に対し、$F_1(a,t) \in B$ である。

$B = X$ とすると確かに上の $3$ 条件を満たすので、条件を満たす $B$ 全体の集合は空でなく共通部分が定義されます。そして $A$ は $3$ 条件を満たす $B$ のうち最小のものである、ということが結果的に従います。

このように、部分集合の再帰的定義はただの条件の列挙ではなく最小性も含意するよう約束されていることに注意しましょう。ただしこれはあくまで再帰的定義に限った約束であり、通常の定義では最小性はもちろん含意されませんし、そもそも再帰的定義のような自己言及を通常の定義で行うと多くの場合循環論法となり定義が破綻します。

さて、$X$ 上の $1$ 項関係は $X$ の部分集合と等価であるため、$X$ 上の $1$ 項関係の再帰的定義においても同様の規則が適用されます。具体的には、

$X$ の要素が良い項であるということを以下のように再帰的に定める：

• $c$ は良い項である。
• 任意の $(a,t) \in X^{n_0} \times X^{m_0}$ に対し、$a$ の任意の成分が良い項であるならば、$F_0(a,t)$ も良い項である。
• 任意の $(a,t) \in X^{n_1} \times X^{m_1}$ に対し、$a$ の任意の成分が良い項であるならば、$F_1(a,t)$ も良い項である。

のように「良い項である」という $1$ 項関係の再帰的定義を書いた場合、これは「良い項である」という述語が $3$ 条件を満たす任意の $1$ 項関係を表すという意味ではありません。上の定義文は次の定義文と等価なものになります：

$X$ の要素 $x$ が良い項であるということを、以下の $3$ 条件を全て満たす $X$ の任意の部分集合 $B$ に対し $x \in B$ が成り立つということと定める：

• $c \in B$ である。
• 任意の $(a,t) \in B^{n_0} \times X^{m_0}$ に対し、$F_0(a,t) \in B$ である。
• 任意の $(a,t) \in B^{n_1} \times X^{m_1}$ に対し、$F_1(a,t) \in B$ である。

以上を踏まえると、今回のヒドラの再帰的定義は次の定義文と等価です：

$2$ 種類の文字(と)のみからなる文字列 $h$ がヒドラであるということを、(と)のみからなる文字列のみからなる任意の集合 $B$ に対し $B$ が以下の $3$ 条件を全て満たすならば $h \in B$ が成り立つということと定める：

• 空文字列は $B$ の要素である。
• $B$ の任意の要素 $h_0$ と $h_1$ に対し、$h_0$ と $h_1$ をこの順に結合した文字列は $B$ の要素である。
• $B$ の任意の要素 $h$ に対し、(と $h$ と) をこの順に結合した文字列は $B$ の要素である。

元の言い回しと比べてだいぶ複雑な言い回しとなりましたね。このような複雑な言い回しを避けるために、数学では今回紹介した簡潔な言い回しが定義され採用されているわけです。

例えば後で参考文献として挙げる

• [1] における$1$ 項関係「be an $\mathcal{L}$-term」や「be an $\mathcal{L}$-formula」の再帰的定義など
• [2] における集合 $T$ および $1$ 項関係「be a principal term」の再帰的定義など
• [3] における集合 $B(\alpha,\beta)$ や $\textrm{K}_{\kappa}(\gamma)$ の再帰的定義など

で実際にそういった言い回しが採用されています。

例えば $h$ が(((())()()))である時、$n = 1,2,3,4,5,6,7,8,9,10$ に対する $h[n]$ は次のように表されます：

$h[1] =$ (((())()))
$h[2] =$ (((())())((())()))
$h[3] =$ (((())())((())())((())()))
$h[4] =$ (((())())((())())((())())((())()))
$h[5] =$ (((())())((())())((())())((())())((())()))
$h[6] =$ (((())())((())())((())())((())())((())())((())()))
$h[7] =$ (((())())((())())((())())((())())((())())((())())((())()))
$h[8] =$ (((())())((())())((())())((())())((())())((())())((())())((())()))
$h[9] =$ (((())())((())())((())())((())())((())())((())())((())())((())())((())()))
$h[10] =$ (((())())((())())((())())((())())((())())((())())((())())((())())((())())((())()))