再帰的定義

コッホ雪片の構築には4つの段階があります。他の多くのフラクタルと同様に、これらの段階は再帰的な定義によって得られます。

数学やコンピュータサイエンスでは、再帰的定義、または帰納的定義は、集合内の要素を集合内の他の要素を用いて定義するために使用されます（ Aczel 1977:740ff）。再帰的に定義可能なオブジェクトの例としては、階乗、自然数、フィボナッチ数列、カントール三項集合などがあります。

関数の再帰的定義は、ある入力に対する関数の値を、他の（通常はより小さい）入力に対する同じ関数の値を用いて定義します。たとえば、階乗関数 $n$ $!$ は次の規則で定義されます。

{\begin{aligned}&0!=1.\\&(n+1)!=(n+1)\cdot n!.\end{aligned}}

$この定義は、すべての自然数n$ に対して有効です。なぜなら、再帰処理は最終的に基本ケースである 0 に到達するからです。この定義は、 $n$ $= 0$ から始めて $n$ $= 1、2、3$ などと順に関数 $n$ $!$ の値を計算する手順を示すものと考えることもできます。

再帰定理は、そのような定義が確かに一意の関数を定義することを述べている。証明には数学的帰納法が用いられる。^{[ 1 ]}

集合の帰納的定義は、集合内の要素を集合内の他の要素を用いて記述する。例えば、集合の定義の一つは、 $\mathbb {N}$ 自然数の⁠は:

0は $\mathbb {N} .$ ⁠
要素nがにある場合 $\mathbb {N}$ ⁠すると $n + 1$ は⁠ $\mathbb {N} .$ ⁠
⁠ $\mathbb {N}$ は、（1）と（2）を満たす最小の集合です。

（1）と（2）を満たす集合は多数存在する。例えば、集合 ${0, 1, 1.649, 2, 2.649, 3, 3.649, \dots}は$ 定義を満たす。しかし、条件（3）は、余分な要素を含む集合を除外することで、自然数の集合を指定する。

再帰的に定義された関数や集合の性質は、再帰的定義に従う帰納法の原理によって証明できる場合が多い。例えば、ここで提示する自然数の定義は、自然数に関する数学的帰納法の原理を直接的に示唆している。すなわち、ある性質が自然数 0 (または 1) で成り立ち、その性質が $n$ で成り立つときはいつでも $n + 1$ でも成り立つならば、その性質はすべての自然数で成り立つ（Aczel 1977:742）。

再帰的定義の形式

ほとんどの再帰的定義は、基本ケース（基礎）と帰納節という2つの基盤から成り立っています。

循環定義と再帰定義の違いは、再帰定義には必ず基本ケース（定義自体では定義されていないが定義を満たすケース）が存在し、帰納節の他のすべてのインスタンスは、何らかの意味で「小さい」（つまり、再帰を終了させる基本ケースに近い）必要があるという点である。これは「より単純なケースでのみ再帰する」という規則としても知られている。^{[ 2 ]}

対照的に、循環定義には基本ケースが存在しない場合があり、関数の値を他の値ではなく、その値自体によって定義してしまうことさえあります。このような状況は無限後退につながります。

再帰的定義が有効であること、つまり再帰的定義が一意の関数を特定することは、集合論の再帰定理として知られる定理であり、その証明は自明ではない。^{[ 3 ]}関数の定義域が自然数である場合、定義が有効であるための十分条件は、 $f (0)$ の値（つまり基本ケース）が与えられ、 $n > 0の場合、$ $n$ に関して $f (n)$ を決定するアルゴリズムが与えられていることである。 $f(0),f(1),\dots ,f(n-1)$ （つまり、帰納的節）

より一般的には、定義域が整列集合である場合は、超限再帰の原理を用いて関数の再帰的定義を行うことができる。有効な再帰的定義を構成する形式的な基準は、一般的な場合の方が複雑である。一般的な証明と基準の概要は、James MunkresのTopologyに記載されている。ただし、一般的な再帰的定義の特定の場合 (定義域が任意の整列集合ではなく正の整数に限定されている場合) については、以下に示す。^{[ 4 ]}

再帰的定義の原理

$A を$ 集合とし、a $0 を A$ $の$ 要素とする。ρ $が$ 、正の整数の空でない部分を $A$ に写像する各関数 $fに$ $A$ の要素を割り当てる関数である場合、一意の関数が存在する。 $h:\mathbb {Z} _{+}\to A$ そのため

{\begin{aligned}h(1)&=a_{0}\\h(i)&=\rho \left(h|_{\{1,2,\ldots ,i-1\}}\right){\text{ for }}i>1.\end{aligned}}

再帰的定義の例

基本関数

加算は、数えることに基づいて再帰的に定義されます。

{\begin{aligned}&0+a=a,\\&(1+n)+a=1+(n+a).\end{aligned}}

乗算は再帰的に次のように定義される。

{\begin{aligned}&0\cdot a=0,\\&(1+n)\cdot a=a+n\cdot a.\end{aligned}}

指数関数は次のように再帰的に定義される。

{\begin{aligned}&a^{0}=1,\\&a^{1+n}=a\cdot a^{n}.\end{aligned}}

二項係数は次のように再帰的に定義できます。

{\begin{aligned}&{\binom {a}{0}}=1,\\&{\binom {1+a}{1+n}}={\frac {(1+a){\binom {a}{n}}}{1+n}}.\end{aligned}}

素数

素数の集合は、以下の条件を満たす正の整数の唯一の集合として定義できる。

2は素数です。
その他の正の整数は、それ自身より小さいどの素数でも割り切れない場合に限り、素数である。

整数 2 の素数性は基本ケースです。この定義によって、2 より大きい任意の整数 $Xの素数性を確認するには、2 から$ $X$ までのすべての整数の素数性を知る必要がありますが、これはこの定義によって明確に定義されています。最後の点は $X$ に関する帰納法によって証明できますが、そのためには第 2 節が「～の場合に限る」と書かれていることが不可欠です。もし単に「～の場合」と書かれていたら、例えば数 4 の素数性は明確ではなく、第 2 節をさらに適用することは不可能になります。

非負の偶数

偶数は、

0は非負の偶数の集合 $Eに含まれる（基底節）、$
集合 $E$ の任意の要素 $x$ に対して、 $x$ $+ 2は$ $E$ に含まれる(帰納的節)、
基礎節と帰納節（極値節）から得られるもの以外は、 $E$ には含まれない。

整った公式

命題論理における整式（wff）の概念は、以下の3つの規則を満たす最小の集合として再帰的に定義される。

$p$ が命題変数である場合、 $p$ は論理式である。
$\neg pは、$ $p$ が wff である場合に wff である。
$(p • q)は、$ $p$ と $q$ が wff であり、• が論理結合子 ∨、∧、→、または ↔ のいずれかである場合に wff です。

この定義は、特定の記号列がwffであるかどうかを判断するために使用できます。

$(p \land q)$ は論理式です。なぜなら、命題変数 $p$ と $q$ は論理式であり、 $\land は$ 論理結合子だからです。

$\neg (p \land q)$ は wff です。なぜなら $(p \land q)$ は wff だからです。

$(\neg p \land \neg q)$ は論理式です。なぜなら $、\neg p$ と $\neg q$ は論理式であり、 $\land$ は論理結合子だからです。

論理プログラムとしての再帰的定義

論理プログラムは、再帰的定義の集合として理解できます。^{[ 5 ]}^{[ 6 ]}例えば、偶数の再帰的定義は、次の論理プログラムとして記述できます。

even ( 0 ). even ( s ( s ( X ))) :- even ( X ).

ここではの場合:-を表し、はの後継者、すなわち、ペアノ算術におけるを表します。s(X)XX+1

論理プログラミング言語Prolog は、目標を解決し、クエリに答えるために逆推論を使用します。たとえば、クエリが与えられると、答えが生成されます。クエリが与えられると、答えが生成されます。?-even(s(s(0)))true?-even(s(0))false

このプログラムは、クエリが真であるかどうかを確認するだけでなく、真となる回答を生成するためにも使用できます。例えば、次のようになります。

?- even ( X ). X = 0 X = s ( s ( 0 )) X = s ( s ( s ( s ( 0 )))) X = s ( s ( s ( s ( s ( s ( 0 )))))) .....

論理プログラムは、否定条件の使用を含めることで再帰的な定義を大幅に拡張します。否定条件は、定義のように、失敗として否定することで実装されます。

even ( 0 ). even ( s ( X )) :- not ( even ( X )).

注記

↑ヘンキン、レオン( 1960)。「数学的帰納法について」。アメリカ数学月報。67 ( 4): 323–338。doi : 10.2307 /2308975。ISSN 0002-9890。JSTOR 2308975。
↑ 「再帰のすべて」。www.cis.upenn.edu 。2019年8月2日にオリジナルからアーカイブ済み。2019年10月24日に取得。
↑再帰定理の証明については、レオン・ヘンキン著『数学的帰納法について』（1960年）を参照のこと。
↑マンクレス、ジェームズ (1975).トポロジー入門（第1版）. ニュージャージー州：プレンティス・ホール. p. 68、演習問題10および12. ISBN 0-13-925495-1。
↑ Denecker, M., Ternovska, E.: 非単調帰納的定義の論理。ACM Trans. Comput. Log. 9(2), 14:1–14:52 (2008)
↑ Warren, DS および Denecker, M., 2023. Prolog のためのより良い論理意味論。Prolog: The Next 50 Years (pp. 82-92) に収録。Cham: Springer Nature Switzerland。

参考文献

ハルモス、ポール(1960)。素朴な集合論。ファン・ノストランド。OCLC 802530334。
Aczel, Peter ( 1977). 「帰納的定義入門」。Barwise, J. (編)『数理論理学ハンドブック』 、論理学と数学の基礎に関する研究、第 90巻、North-Holland 、 739–782頁。doi : 10.1016/S0049-237X(08) 71120-0。ISBN 0-444-86388-5。
ハイン、ジェームズ・L. (2010).離散構造、論理、計算可能性.ジョーンズ＆バートレット. ISBN 978-0-7637-7206-2OCLC 636352297

[1] ヘンキン、レオン( 1960)。「数学的帰納法について」。アメリカ数学月報。67 ( 4): 323–338。doi : 10.2307 /2308975。ISSN 0002-9890。JSTOR 2308975。

[2] 「再帰のすべて」。www.cis.upenn.edu 。2019年8月2日にオリジナルからアーカイブ済み。2019年10月24日に取得。

[3] 再帰定理の証明については、レオン・ヘンキン著『数学的帰納法について』（1960年）を参照のこと。

[Munkres-4] マンクレス、ジェームズ (1975).トポロジー入門（第1版）. ニュージャージー州：プレンティス・ホール. p. 68、演習問題10および12. ISBN 0-13-925495-1。

[5] Denecker, M., Ternovska, E.: 非単調帰納的定義の論理。ACM Trans. Comput. Log. 9(2), 14:1–14:52 (2008)

[6] Warren, DS および Denecker, M., 2023. Prolog のためのより良い論理意味論。Prolog: The Next 50 Years (pp. 82-92) に収録。Cham: Springer Nature Switzerland。

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

再帰的定義

再帰的定義の形式

再帰的定義の原理

再帰的定義の例

基本関数

素数

非負の偶数

整った公式

論理プログラムとしての再帰的定義

関連項目

注記

参考文献

関連するトピック

コッホ雪片

フラクタル

数学

コンピュータサイエンス