整礎関係 - 暇つぶしWikipedia

整礎関係

数学において、二項関係が整礎（せいそ、英: well-founded）であるとは、真の無限降下列をもたないことである。
定義

集合あるいはクラス X 上の二項関係 R が整礎であるとは、X の空でない任意の部分集合 S が R に関する極小元を持つことをいう [1]。（関係 R がさらに集合的であることを仮定する著者もいる [2]。X が集合であればこれは自動的に成り立つ。）つまり、S の元 m であって、S の任意の元 s に対して対 (s, m) は R に属さないようなものが存在する。式で書けば ∀ S ⊆ X ( S ≠ ∅ → ∃ m ∈ S ∀ s ∈ S ( s , m ) ∉ R ) . {\displaystyle \forall S\subseteq X\;\,(S\neq \varnothing \to \exists m\in S\;\;\forall s\in S\;\,(s,m)\notin R).}

X が集合であるとき、従属選択公理（これは選択公理よりも真に弱く可算選択公理よりも真に強い）を仮定すれば、同値な定義として、関係が整礎であることを可算無限降下列が存在しないこととして定められる [3]。つまり、X の元の無限列 x0, x1, x2, ... で、どんな n についても xn+1 R xn となるようなものはとれない。

順序集合論（英語版）では、半順序に対応する真の順序 (strict partial order) が整礎関係となるとき、その半順序を整礎（整礎半順序）と呼ぶ。全順序がこの意味で整礎であるとき、整列順序と呼ぶ。

集合 x が整礎的集合 (well-founded set) であることは、∈ が x の推移閉包上で整礎関係となることと同値である。ZF における公理のひとつである正則性の公理は、全ての集合が整礎であることを要請するものである。

関係 R が X 上で逆整礎 (converse well-founded) または上方整礎 (upwards well-founded) であるとは、R の逆関係 R−1 が X 上の整礎関係であるときにいう。このとき R は昇鎖条件を満たすという。
帰納法と再帰

整礎関係が興味深い重要な理由は、それによって超限帰納法の一種が考えられることにある。すなわち (X, R) が整礎関係で P(x) が X の元に関する何らかの性質であるときに、 P(x) が X の「すべての」元に対して満たされることを示すには、以下を示せば十分である。x を X の元とするとき、y R x なる全ての y に対して P(y) が真であるならば P(x) は必ず真である。つまり、 ( ∀ x ∈ X ) [ ( ( ∀ y ∈ X ) ( ( y R x ) → P ( y ) ) ) → P ( x ) ] → ( ∀ x ∈ X ) ( P ( x ) ) {\displaystyle (\forall x\in X)\,[((\forall y\in X)\,((y\,R\,x)\to P(y)))\to P(x)]\to (\forall x\in X)\,(P(x))}

が成り立つ。このような整礎帰納法 (well-founded induction) は、エミー・ネーターにちなんでネーター帰納法 (Noetherian induction) とも呼ばれることがある [4]。

帰納法と同様に、整礎関係は超限再帰による対象の構成も保証する。(X, R) が集合的整礎関係で F が X の元 x と X の始切片 {y 。y R x} 上の函数 g の組に対して対象 F(x, g) を割り当てる函数とすると、函数 G が一意的に存在して、任意の x ∈ X に対して G ( x ) = F ( x , G 。 { y ∣ y R x } ) {\displaystyle G(x)=F(x,G\vert _{\{y\mid yRx\}})}

が満たされる。つまり、X 上の函数 G を構成しようとするとき、G(x) を y R x なる y に対する値 G(y) を利用して定義することができる。

例として、整礎関係 (N, S) を考える。ここで N は自然数全体のなす集合で、S は後者函数 x → x + 1 のグラフとする。S 上の帰納法は通常の数学的帰納法であり、S 上の再帰は原始再帰を与える。順序関係 (N, <) からは完全帰納法 (complete induction) と累積帰納法 (course-of-values recursion) が得られる。 (N, <) が整礎関係であるという言明は整列原理としても知られる。

ほかにも重要な整礎帰納法の特別の場合がある。整礎関係として順序数全体のなす類上の通常の順序を考えれば、超限帰納法 (transfinite induction) と呼ばれる手法が得られるし、整礎集合として再帰的に定義されるデータ構造からなる集合をとれば、構造的帰納法 (structural induction) が考えられる。あるいは普遍類上の帰属関係を整礎関係に選べば∈-帰納法として知られる帰納法が定まる（詳細は各項に譲る）。
例

全順序でない整礎関係の例。

正整数全体 {1, 2, 3, ...} に a < b ⇔ [a は b を割り切るかつ a ≠ b] となる順序を入れたもの。

固定された文字集合上の有限文字列全体に s < t ⇔ s は t の真の部分文字列である、で定まる順序。

自然数の順序対全体の集合 N × N 上の、(n1, n2) < (m1, m2) ⇔ n1 < m1 かつ n2 < m2 となる順序。

固定された文字集合上の正規表現全体の成す集合に、s < t ⇔ s は t の真の部分表現であるとして定義される関係。

集合を要素とする任意のクラスの集合要素関係 ∈ 。これは正則性公理そのものである。

任意の有限有向非輪状グラフのノード全体の、a R b ⇔ a から b へいく辺があるとして定義される関係。

整礎でない関係の例。

負整数全体 {?1, ?2, ?3, …} の通常の順序。任意の非有界部分集合が最小元を持たない。

有限文字集合上の文字列全体の成す集合上の、通常の順序関係（辞書式順序）。列 "B" > "AB" > "AAB" > "AAAB" > ⋯ は無限降鎖になる。この関係は、全体集合が最小元（つまり空文字列）を持ったとしても整礎ではない。

有理数全体（または実数全体）の標準的な順序（大小関係）。たとえば、正の有理数（または正の実数）全体は最小元を持たない。

その他の性質

(X, <) が整礎関係で x が X の元ならば、x から始まる降鎖列は必ず長さ有限だが、これはこのような降鎖の長さが有界であるということを意味しない。以下のような例を考えよう。X は正の整数全体の成す集合に、どの整数よりも大きな整数ではない新しい元 ω を付け加えた集合とする。このとき X は整礎だが、ω から始まる長さ有限の降鎖列でいくらでも長いものが取れる。なんとなれば、任意の正整数 n に対してω, n ? 1, n ? 2, ..., 2, 1

という鎖は長さ n を持つ。

モストウスキーの崩壊補題 (Mostowski collapse lemma) によれば、集合要素関係 (set membership) は普遍的な整礎関係である。つまり、クラス X 上の集合的な整礎関係 R に対し、クラス C が存在して、(X, R) が (C, ∈) に同型となる。
反射関係の整礎性

関係 R が反射律を満たすとは、R の始域の任意の元 a に対して a R a が満たされることである。任意の定値列は（広義の）降鎖であるから、始域が空でない任意の反射関係は無限降鎖をもつ。例えば、自然数の全体に通常の大小関係による順序 ≤ を考えれば 1 ≥ 1 ≥ 1 ≥ ⋯ は無限降鎖になる。反射関係 R を扱う際には、この手の自明な降下列を取り除くために、普通は（しばしば陰伏的に）a R′ b ⇔ a R b かつ a ≠ b

で定義される関係 R′ を代わりに利用する。先ほどの自然数の例で言えば、反射的順序関係 ≤ を考える代わりに、整礎関係となる < を用いるということである。文献によっては、整礎関係の定義として、本項におけるものの代わりに、このような規約を設けることによって反射関係をも含めるものもあるので注意を要する。
整礎性の遺伝

Size:22 KB
出典: フリー百科事典『ウィキペディア（Wikipedia）』
担当:undef