反復推論 – 定義

帰納法による推論は数学的推論の形式であり、その目的はすべての自然整数、より一般的には無限の自然整数の性質を実証することです。プロパティを任意の整数で検証するには、次のようにすれば十分であると述べています。

• 0 であることが検証されること。
• それは「次の整数に進む」ということです。整数に対して検証されると、その後に続く整数に対しても検証されます。

全体的に同じことが言えます。

自然数のセットに 0 が含まれ、その各要素の後続値が含まれる場合、このセットにはすべての自然数が含まれます。

帰納法による推論は、自然整数の集合であるNの順序特性と密接に関連しています。

空でない自然数の集合にはすべて最小の要素があります。

この推論の特定の形式は、当然、適切な無限次数にも一般化されます。次に、超限回帰、順序回帰について話します (すべての適切な順序は順序数と同型です)。誘導という用語もこの文脈でよく使用されます。帰納法による推論は、最終的には十分に根拠のある関係に一般化することができます。論理やコンピューターサイエンスなどの特定の文脈では、ツリー構造の構造について、構造的回帰について話します。

単純な再発

自然数に対して定義されたプロパティP ( n ) がすべての自然数に対して真であることを証明するには、次のことを証明すれば十分です。

• P (0)
• (任意の整数nの場合) (
  $$ {P(n) \Rightarrow P(n+1))} $$

最初のプロパティは初期化と呼ばれ、 2 番目のプロパティは継承と呼ばれます。

特定のランクn ₀のみからP ( n ) を表示するには、以下を表示すれば十分であるとすぐに推測できます。

• P ( n0 ₎
• (全員にとって
  $$ {n\geq n_0} $$
  ) (
  $$ {P(n) \Rightarrow P(n+1))} $$

これは、 pの帰納法によってP ( n ₀ + p ) を示すか、加算を参照したくない場合は、 nの帰納法によってプロパティ ” n < n ₀またはP ( n )” を示すことによって行われます。

反復は、集合の方法で表現することもできます。それは、理解における集合の定義のバリエーションにすぎません。プロパティとそれを検証する自然数のセットを関連付け、自然数のセットと関連付けられたメンバーシップ プロパティを関連付けます。次に、再発は次のように同等の方法で再記述されます。

次の場合、 E をNの部分集合とします。

• 0 ∈ E
• n ∈ E ⇒ n+1 ∈ E (すべてのn ∈ Nについて)

するとE = Nとなります。

例

例1

最初のn個の整数1 + 2 + … + nの合計が次と等しいことを示します。

• このプロパティは、 n = 1 の場合に当てはまります。
  $$ {1 = {1 \times 2 \over 2}} $$
  。
• どちらか
  $$ {n\in\mathbb{N}} $$
  。次のように仮定します。
  $$ {1 + 2 + … + n = {n(n+1)\over 2}} $$
  。それで ：

$$ {= {n(n+1) + 2(n+1) \over 2}} $$

$$ {= {(n+1)(n+2) \over 2}} $$

確かに財産は世襲です。

例 2

帰納法によって証明するには

すべてのために

$$ {n \geq 3} $$

, 3 ^{2 n} − 2 ^{n − 3}は 7 の倍数です。

十分です

• n = 3 の場合、 3 ⁶ − 2 ⁰が実際に 7 の倍数であることを検証します (728 は実際に 7 の倍数です)。
• それを証明するために（すべての人にとって）
  $$ {n \geq 3} $$
  ) 3 ^{2 n} − 2 ^{n − 3}が 7 の倍数の場合、 3 ^{2 n + 2} − 2 ^{n − 2}は 7 の倍数です。

$$ {3^{2n+2} – 2^{n – 2} = 9\times 3^{2n} – 2 \times 2^{n – 3}} $$

。

$$ {3^{2n+2} – 2^{n – 2} = (7+2)\times 3^{2n} – 2 \times 2^{n – 3}} $$

。

$$ {3^{2n+2} – 2^{n – 2} = 7\times 3^{2n} +2\times 3^{2n} – 2 \times 2^{n – 3}} $$

。

$$ {3^{2n+2} – 2^{n – 2} = 7\times 3^{2n} +2( 3^{2n} -2^{n – 3})} $$

。

したがって、 3 ^{2 n + 2} − 2 ^{n − 2}は 2 つの 7 の倍数の合計であり、実際には 7 の倍数です。

大学の最初のサイクルで、数学の学生は、7 を法とする2 と 3 の累乗の計算を使用した直接的なデモンストレーションに遭遇します。上記の計算の利点は、コストがかからないだけでなく、反復計算ができることです。商uを求める方法n of 3 ^{2 n} − 2 ^{n − 3} by 7。実際、シーケンスu は漸化関係を検証します。

u _{n + 1} = 3 ^{2 n} + 2 u _nおよびu ₃ = 104 。

帰納法による新しい議論により、次のことがわかります。

$$ {u_n=2^{n-3}.104+\sum_{k=3}^{n-1}3^{2n-k-2}.2^{k-3}} $$

。

取るべき注意事項

• 初期化を忘れてはいけません。前の例に戻ると、「 3 ^{2 n} − 2 ^{n − 2}は 7 の倍数である」というプロパティは遺伝的であることが証明できますが、それにもかかわらず、初期化できないため偽です。
• 継承は、プロパティが直接実証された (初期化) 最後のn ₀以上の整数nについて実証されなければなりません。

たとえば次のような場合

$$ {u_n = \frac{n^2 – n + 1}{n^2}} $$

、このシーケンスが n = 2 から増加していることが観察できます。

$$ {u_{n+1} – u_n = \frac{n^2 – n – 1}{n^2(n+1)^2} width=} $$

0″>。

それを証明しようとすると、

$$ {u_n \geq 1} $$

すべてのために

$$ {n \geq 1} $$

、

u ₁ = 1 であるため、初期化は簡単に証明できます。

遺伝もあり、配列が増加しているため、

$$ {u_n \geq 1} $$

それで

$$ {u_{n+1} \geq 1} $$

。

ただし、この不等式は n = 1 の場合にのみ当てはまります。実際には、遺伝は n が 2 以上の場合にのみ証明されており、n が 1 以上の場合には証明されていません。

原理の証拠は？

回帰の原則を正当化する次のような文章をよく見かけます。

この原則は実際には明白です。漸化則に必要な 2 つのプロパティにより、任意の整数値のプロパティ P を簡単に実証できます。たとえば、P が両方のプロパティを満たし、P が 2 に対して真であることを証明したいとします。P は 0 に対して真なので、後続の 1 に対しても真です。しかし、P は 1 に対して真であるため、後続の 1 に対しても真です。したがって、2 についても当てはまります。この推論が、事前に固定された任意の整数について問題なく継続されることは明らかです。 (CAML 言語、Weis と Leroy – InterEditions 1993)。

ただし、そのような議論は漸化則そのものの実証を構成することはできません。P( n ) がすべてのnに対して真であることを示すには、P( n ) と P( n +1 の間の含意をすべて記述する必要があるからです) ）そしてこれには無限の数の影響が必要になります。しかし、デモは終わらせなければなりません。したがって、そのような証明は、事前に固定された整数nに対してのみ有効です。再発仮説を使用すると、理論的には、任意の大きな整数に対する証明を「機械的に」書くことができ、想像力の努力は必要ありません。しかし、漸化原理がなければ、有限個の整数についてのみこれらの証明を書くことができます。回帰の原理により、単一の (有限な) デモンストレーション、つまり各整数に 1 つずつ対応する無限のデモンストレーションの形で「集まる」ことが可能になります。

したがって、漸化式の原理は本質的に純粋に論理的なものではなく、基本的に自然整数の集合の性質に関連しており、集合論における定義をほぼ提供します。

他の形式の繰り返し、同等のステートメント

注文 2 の再発

遺伝の場合、 P ( n + 1) を証明する場合、前の 2 つのランク、つまりnだけでなくn -1の特性を仮定する必要がある場合があります。次の漸化則を使用することになります。

次の場合、 P ( n ) をNに対して定義されたプロパティとします。

• P (0)
• P (1)
• [ P ( n ) およびP ( n +1)] ⇒ P (n+2) (すべてのn ∈ Nについて)

次に、すべてのn ∈ Nに対してP ( n ) を計算します。

この性質は、自由に使える追加の仮説があるため、単純な漸化式よりも強力であるように見えますが、単純な帰納法によって [ P ( n ) およびP ( n +1) ] を証明することになるため、実際にはそれと同等です。たとえば、フィボナッチ数列の記事では、この漸化則の適用例を示します。

もちろん、3、4 などに一般化することもできます。しかし、これらの原則はすべて、強い再発とも呼ばれる、次の再発原則の特殊なケースとして現れます。

強い再発

帰納法による推論では、遺伝に対してより強力なバージョンを使用する必要がある場合があります。

次の場合、 P ( n ) をNに対して定義されたプロパティとします。

• P (0)
• [∀ k ≤ n P ( k )] ⇒ P ( n +1) (すべてのn ∈ Nについて)

次に、任意の整数n ∈ Nに対してP ( n ) を計算します。

つまり、次のランクの特性を証明するには、それが下位のランクすべてに当てはまると仮定できます。

繰り返しますが、この特性は単純な再帰よりも明らかに強力ですが、これは単純な再帰によって特性 “∀ k ≤ n P ( k )” を実証することになるため、実際にはそれと同等です。

この繰り返しも、単純な繰り返しとまったく同様に、特定のランクからシフトする可能性があります。

使用例

2 以上の自然数には素約数があることを証明します。

• 2 にはそれ自体である素約数があることを示します。
• n を2 以上の整数とし、2 からnまでのすべての整数d には素約数があると仮定し、同じことがn + 1 にも当てはまることを証明しようとします。

または、 n + 1 が素数の場合、それ自体が素数になります。

または、 n + 1 が合成され、2 とnの間に 2 つの整数dとd’ が存在し、 n + 1 = dd’ になります。この場合、 dとd’ は素数を持ち、それらはn + 1の約数でもあります。

優れた基礎

この原則は、整数 0 と、順序関係のみを優先してn+1をnに関連付ける後続関数への参照を排除するような方法で言い換えることができます。実際、2 つの再発仮説は 1 つに結合できます。

次の場合、 P ( n ) をNに対して定義されたプロパティとします。

• [∀ k < n P ( k )] ⇒ P ( n ) (すべてのn ∈ Nについて)

次に、任意の整数n ∈ Nに対してP ( n ) を計算します。

( n = 0 の場合、仮説は空です)。

正しい順序と（十分に根拠のある順序を）直接一般化するのは、この形式の回帰による推論です。

フェルマーの無限降下原理

再発、特に強い再発の代わりに、ピエール フェルマーによって説明された無限降下の原理を使用できます。これには、適切な順序プロパティ ( Nの空でないすべてのサブセットには最小の要素があります) を直接使用することが含まれます。これも繰り返しプロパティと同等です。実際、前の段落で示した順序のみに依存する最後の反復特性が、良好な順序の特性を定式化する別の方法であることを示します。

実際、すべてのn ∈ Nに対して、プロパティPについて次のように言えます。

[ ∀k <nP ( k )] ⇒P ( n )

これは、対比的に次のことを意味します。

P ( n ) がない ⇒ ∃ k < n P ( k ) がない

つまり、その特性セットの補数 — C _P = { n ∈ N | no P ( n )} — 最小要素がありません。

さらに、すべてのn ∈ Nについて真であるとPについて言うことは、上でそれに関連付けられた集合C _Pが空であると言うのと同じです。 Nの任意の部分集合A 、プロパティP ( n )、つまりn ∉ A をA = C _Pとなるように関連付けることができるため、最後の形式の漸化式ステートメントと次のステートメントの間には等価性があります。

最小の要素を持たないNのサブセットAは空です

それは秩序の性質の対比にほかなりません。

公理化

下書き

ペアノの公理を参照してください。