🔥

【小ネタ】Scott領域の3つの定義の同値性

2025/01/26に公開

はじめに

はじめまして。記事を開いていただきありがとうございます。

有界完備な代数的cpo[1]をScott領域といいます。
ただし、poset P有界完備とは、任意の部分集合X\subseteq Pに対し、Xが有界[2] (\exists p\in P, \forall x\in X, x\le p)ならばXPに上限を持つことを指します。)

代数的cpoについてはぜび私の記事をご覧ください。
(ただし、代数的cpoの定義を知らなくてもこの記事は読めます。)
https://zenn.dev/mineel5/articles/d6bc627587b72b

また、Scott領域についても以下の記事の前提知識パートでもう少し詳しく説明しております。
https://zenn.dev/mineel5/articles/c3b5c13f52cd62

この記事では、cpoにおける有界完備性について3つの同値な定義を紹介しようと思います。
(以前ある方に教えていただいた内容をそのまま紹介する形になります。)

よろしくお願いします。

3つの定義の同値性

この記事では、有向上限(=有向集合のみを定義域とする上限)を\sqcupで表し、通常の上限を\veeで表します。


定理1: cpoにおける有界完備性の同値性

Dをcpoとする。このとき、以下はすべて同値である。
\subseteq_\mathrm{fin}で有限部分集合を表すとする。)

  1. \forall A\subseteq D, Aが有界ならばADに上限を持つ
  2. \forall A\subseteq_\mathrm{fin}D, Aが有界ならばADに上限を持つ
  3. \forall A\subseteq D, A\not=\emptysetならばADに下限を持つ

Proof.

(1)\implies(2)\implies(3)\implies(1)の流れで証明をする。
(1)\implies(2)は明らかである。

(2)\implies(3)について

\emptyset\not=A\subseteq Dを固定し、Aの下界の集合を\mathrm{Lb}(A)\coloneqq\{d\in D\mid\forall a\in A, d\le a\}とする。Dは最小元\botを持つため、\mathrm{Lb}(A)\not=\emptysetに注意。このとき、\mathrm{Lb}(A)が最大値を持つことを示す。

B=\{\vee F\mid F\subseteq_\mathrm{fin}\mathrm{Lb}(A)\}が有向集合であることを示す。各F\mathrm{Lb}(A)の定義より有界なためDに上限\vee Fを持つことに注意。

まず、\mathrm{Lb}(A)\not=\emptysetより、B\not=\emptysetである。また、\vee F_1, \vee F_2\in Bに対して、\vee (F_1\cup F_2)が上界になっている。[3]
故に、Bは有向集合であり、上限\sqcup Bを持つ。

今、上限とは最小上界のことであり、各F\subseteq_\mathrm{fin}\mathrm{Lb}(A)に対してAFの上界の集合なので、\vee F\in\mathrm{Lb}(A)が成り立つ。
故に、B\subseteq\mathrm{Lb}(A)となり、同様の理由で\sqcup B\in\mathrm{Lb}(A)

さらに、任意のd\in\mathrm{Lb}(A)に対して、d=\vee\{d\}\in Bより、d\le\sqcup Bとなる。
すなわち、\sqcup Bは下界の集合\mathrm{Lb}(A)の最大値となっているため、Aは下限を持つ。

(3)\implies(1)について

有界なA\subseteq Dを固定する。上界の集合を\mathrm{Ub}(A)\coloneqq\{d\in D\mid\forall a\in A, a\le d\}とすると、Aの有界性より、\mathrm{Ub}(A)\not=\emptysetである。

よって、下限\wedge\mathrm{Ub}(A)\in DDに存在する。
さらに、\mathrm{Ub}(A)の定義よりAの元はすべて\mathrm{Ub}(A)の下界であるため、\forall a\in A, a\le\wedge\mathrm{Ub}(A)となる。(下限 = 最大下界)

つまり、\wedge\mathrm{Ub}(A)Aの上界であるため、\wedge\mathrm{Ub}(A)\in\mathrm{Ub}(A)である。
すなわち、\wedge\mathrm{Ub}(A)は上限集合\mathrm{Ub}(A)の最小値(=Aの最小上界)となるため、Aは上限を持つ。
\square


よって、Scott領域を定義する際は、有界完備性について3つのどの定義を採用しても同値となります。

Scott領域の身近な例として、環論におけるイデアルは無限個の共通部分に閉じているため、ある環上のイデアルの集合はScott領域をなします。
(イデアルは和集合に閉じていませんが、有向和集合には閉じています。また、無限のmeetを持つため完備束をなしますが、その際の上限演算は和集合ではなく\mathcal I_1+\mathcal I_2であることにも注意してください。)

おわりに

お疲れ様でした。ここまで読んでいただきありがとうございました。

有界完備性が無限集合と有限集合で同値になるのも、それらが無限のmeetを持つのと同値になるのもかなり非自明な性質で面白いですね。

ただし、これらはcpoの有向完備性に強く依存しているため、一般のposetにおいては成り立たないことに注意してください。

改めて、本当にありがとうございました。

脚注
  1. この記事では、最小元を持つ有界完備半順序集合をcpoと呼びます。 ↩︎

  2. 定義より、poset P\not=\emptysetなら空集合は常に有界です。 ↩︎

  3. 上限の性質より、poset P上の上限を持つA, B\subseteq Pに対してA\subseteq B\implies \vee A\le\vee B ↩︎

Discussion