整礎関係のソースを表示

[[数学]]において、[[二項関係]]が'''整礎'''（せいそ、{{lang-en-short|''well-founded''}}）であるとは、真の無限[[降下列]]をもたないことである。

== 定義 ==
[[集合]]あるいは[[クラス (数学)|クラス]] ''X'' 上の[[二項関係]] ''R'' が'''整礎'''であるとは、''X'' の[[空集合|空]]でない任意の[[部分集合]] ''S'' が ''R'' に関する[[極小元]]を持つことをいう{{sfn|Kanovei|Reeken|2004|p=16|loc=Definition 1.1.4}}。（関係 ''R'' がさらに[[二項関係|集合的]]であることを仮定する著者もいる{{sfn|Jech|2003|loc={{google books quote|id=CZb-CAAAQBAJ|page=67|Definition 6.8}}}}。''X'' が集合であればこれは自動的に成り立つ。）つまり、''S'' の元 ''m'' であって、''S'' の任意の元 ''s'' に対して対 (''s'', ''m'')  (=''s'' ''R'' ''m'' のこと)は ''R'' に属さないようなものが存在する。式で書けば
:<math>\forall S \subseteq X \;\, (S \neq \varnothing \to \exists m \in S \;\; \forall s \in S \;\, (s, m) \notin R).</math>
（無限降下列との関係は下記）

''X'' が集合であるとき、[[従属選択公理]]（これは[[選択公理]]よりも真に弱く[[可算選択公理]]よりも真に強い）を仮定すれば、同値な定義として、関係が整礎であることを可算無限降下列が存在しないこととして定められる{{sfn|Jech|2003|loc={{google books quote|id=CZb-CAAAQBAJ|page=50|Lemma 5.5}}}}。つまり、''X'' の元の無限列 ''x''<sub>0</sub>, ''x''<sub>1</sub>, ''x''<sub>2</sub>, ... で、どんな ''n'' についても ''x''<sub>''n''+1</sub> ''R'' ''x''<sub>''n''</sub> となるようなものはとれない。

{{仮リンク|順序集合論|en|order theory|preserve=1}}では、[[半順序]]に対応する真の順序 (strict partial order) が整礎関係となるとき、その半順序を整礎（整礎半順序）と呼ぶ。[[全順序]]がこの意味で整礎であるとき、[[整列順序]]と呼ぶ。

集合 ''x'' が'''整礎的集合''' {{lang|en|(''well-founded set'')}} であることは、[[元 (数学)|&isin;]] が ''x'' の[[推移閉包]]上で整礎関係となることと同値である。[[公理的集合論#ツェルメロ＝フレンケル集合論（ZF公理系）|ZF]] における公理のひとつである[[正則性公理|正則性の公理]]は、全ての集合が整礎であることを要請するものである。

関係 ''R'' が ''X'' 上で'''逆整礎''' {{lang|en|(''converse well-founded'')}} または'''上方整礎''' {{lang|en|(''upwards well-founded'')}} であるとは、''R'' の[[逆関係]] ''R''<sup>&minus;1</sup> が ''X'' 上の整礎関係であるときにいう。このとき ''R'' は[[昇鎖条件]]を満たすという。

== 帰納法と再帰 ==
整礎関係が興味深い重要な理由は、それによって[[超限帰納法]]の拡張が考えられることにある。すなわち (''X'', ''R'') が整礎関係で P(''x'') が ''X'' の元に関する何らかの性質であるときに、 P(''x'') が ''X'' の「すべての」元に対して満たされることを示すには、以下を示せば十分である。
: ''x'' を ''X'' の元とするとき、''y R x'' なる全ての ''y'' に対して P(''y'') が真であるならば P(''x'') は必ず真である。つまり、
::<math>(\forall x \in X)\,[((\forall y\in X)\,((y\,R\,x) \to P(y))) \to P(x)] \to (\forall x\in X)\,(P(x))</math>
が成り立つ。
このような'''整礎帰納法''' (''{{lang|en|well-founded induction}}'') は、[[エミー・ネーター]]にちなんで'''ネーター帰納法''' (''{{lang|en|Noetherian induction}}'') とも呼ばれることがある<ref>Bourbaki, N. (1972) ''Elements of mathematics. Commutative algebra'', Addison-Wesley.</ref>。

帰納法と同様に、整礎関係は[[超限再帰]]による対象の構成も保証する。(''X'', ''R'') が[[二項関係|集合的]]整礎関係で ''F'' が ''X'' の元 ''x'' と ''X'' の[[始切片]] {''y'' | ''y R x''} 上の函数 ''g'' の組に対して対象 ''F''(''x'', ''g'') を割り当てる函数とすると、函数 ''G'' が一意的に存在して、任意の ''x'' ∈ ''X'' に対して
:<math>G(x)=F(x,G\vert_{\{y\mid yRx\}})</math>
が満たされる。つまり、''X'' 上の函数 ''G'' を構成しようとするとき、''G''(''x'') を ''y R x'' なる ''y'' に対する値 ''G''(''y'') を利用して定義することができる。

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

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

== 例 ==
全順序でない整礎関係の例。
* 正[[整数]]全体 {1, 2, 3, ...} に ''a'' &lt; ''b'' [[必要十分条件|&hArr;]] [''a'' は ''b'' を[[除法|割り切る]] かつ ''a'' ≠ ''b''] となる順序を入れたもの。
* 固定された文字集合上の有限[[文字列]]全体に ''s'' &lt; ''t'' &hArr; ''s'' は ''t'' の真の部分文字列である、で定まる順序。
* 自然数の順序対全体の集合 '''N''' × '''N''' 上の、(''n''<sub>1</sub>, ''n''<sub>2</sub>) &lt; (''m''<sub>1</sub>, ''m''<sub>2</sub>) &hArr; ''n''<sub>1</sub> &lt; ''m''<sub>1</sub> かつ ''n''<sub>2</sub> &lt; ''m''<sub>2</sub> となる順序。
* 固定された文字集合上の[[正規表現]]全体の成す集合に、''s'' &lt; ''t'' &hArr; ''s'' は ''t'' の真の部分表現であるとして定義される関係。
* 集合を要素とする任意のクラスの集合要素関係 &isin; 。これは[[正則性公理]]そのものである。
* 任意の有限[[有向非輪状グラフ]]のノード全体の、''a R b'' &hArr; ''a'' から ''b'' へいく辺があるとして定義される関係。
整礎でない関係の例。
* 負整数全体 {−1, −2, −3, …} の通常の順序。任意の非有界部分集合が最小元を持たない。
* 有限文字集合上の文字列全体の成す集合上の、通常の順序関係（[[辞書式順序]]）。列 "B" &gt; "AB" &gt; "AAB" &gt; "AAAB" &gt; &#x22EF;<!--&cellip;--> は無限降鎖になる。この関係は、全体集合が最小元（つまり[[空文字列]]）を持ったとしても整礎ではない。
* [[有理数]]全体（または[[実数]]全体）の標準的な順序（大小関係）。たとえば、正の有理数（または正の実数）全体は最小元を持たない。

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

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

== 反射関係の整礎性 ==

関係 ''R'' が[[反射関係|反射律]]を満たすとは、''R'' の始域の任意の元 ''a'' に対して ''a R a'' が満たされることである。任意の定値列は（広義の）降鎖であるから、始域が空でない任意の反射関係は無限降鎖をもつ。例えば、自然数の全体に通常の大小関係による順序 &le; を考えれば 1 &ge; 1 &ge; 1 &ge; &#x22EF;<!--&cellip;--> は無限降鎖になる。反射関係 ''R'' を扱う際には、この手の自明な降下列を取り除くために、普通は（しばしば陰伏的に）
: ''a'' ''R''&prime; ''b'' &hArr; ''a R b'' かつ ''a'' ≠ ''b''
で定義される関係 ''R''&prime; を代わりに利用する。先ほどの自然数の例で言えば、反射的順序関係 &le; を考える代わりに、整礎関係となる &lt; を用いるということである。文献によっては、整礎関係の定義として、本項におけるものの代わりに、このような規約を設けることによって反射関係をも含めるものもあるので注意を要する。

== 整礎性の遺伝 ==

整礎集合の定義でその集合の[[推移閉包]]に言及されているので、ある集合が整礎ならば、その集合の各元も整礎であり、各元のそのまた各元も整礎であり、そのまた各元も……と以下同様に続くことになる。これを、整礎集合は'''遺伝的整礎''' {{lang|en|(''hereditarily well-founded'')}} であるということがある。

== 関連項目 ==
* [[整礎的集合]]

== 脚注 ==
{{Reflist}}

== 参考文献 ==
{{参照方法|date=2016年1月}}
* {{cite book
|last1      = Jech
|first1     = Thomas
|year       = 2003
|title      = Set theory
|edition    = The third millennium edition, revised and expanded
|series     = Springer Monographs in Mathematics
|url        = {{google books|CZb-CAAAQBAJ|plainurl=yes}}
|publisher  = Springer-Verlag
|isbn       = 3-540-44085-2 
|mr         = 1940513
|ref        = harv
}}
* {{cite book
 | last = Just
 | first = Winfried
 | last2 = Weese
 | first2 = Martin
 | year = 1998
 | title = Discovering Modern Set theory. I: The Basics
 | series = Graduate Studies in Mathematics
 | volume = 8
 | place = USA
 | publisher = American Mathematical Society
 | isbn = 0-8218-0266-6
 | ref = harv
}}
* {{cite book
 | last1 = Kanovei 
 | first1 = Vladimir
 | last2 = Reeken
 | first2 = Michael 
 | year = 2004
 | title = Nonstandard Analysis, Axiomatically
 | series = Springer Monographs in Mathematics
 | place = Germany
 | publisher = Springer
 | isbn = 3-540-22243-X
 | ref = harv
}}
* {{cite book
 | last = Taylor
 | first = Paul
 | year = 1999
 | title = Practical Foundations of Mathematics
 | series = Cambridge studies in advanced mathematics
 | volume = 59
 | place = UK
 | publisher = Cambridge University Press
 | isbn = 0-521-63107-6
 | ref = harv
}}

{{DEFAULTSORT:せいそかんけい}}
[[Category:数学的関係]]
[[Category:整礎性|*]]
[[Category:数学に関する記事]]
{{Settheory-stub}}