整礎関係 例

ウィキペディア

整礎関係

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/01 10:09 UTC 版)

例

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

• 正整数全体 {1, 2, 3, ...} に a < b ⇔ [a は b を割り切る かつ a ≠ b] となる順序を入れたもの。
• 固定された文字集合上の有限文字列全体に s < t ⇔ s は t の真の部分文字列である、で定まる順序。
• 自然数の順序対全体の集合 N × N 上の、(n₁, n₂) < (m₁, m₂) ⇔ n₁ < m₁ かつ n₂ < m₂ となる順序。
• 固定された文字集合上の正規表現全体の成す集合に、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′ を代わりに利用する。先ほどの自然数の例で言えば、反射的順序関係 ≤ を考える代わりに、整礎関係となる < を用いるということである。文献によっては、整礎関係の定義として、本項におけるものの代わりに、このような規約を設けることによって反射関係をも含めるものもあるので注意を要する。