4 CPO

4.1

CPOの連続関数が最小不動点を持つことを証明せよ。

4.2

集合の部分集合全体の集合に、次のように大小関係を入れる ()。

1. 
2. 

どちらの場合にもがCPOになることを証明せよ。

4.3

Herbrand BaseとHerbrand Universeとは何かを説明しなさい。

4.4

Pure Prologのプログラムを一つ固定し、そのHerbrand Universeを とする。に対し、を、がすべて成り立つと仮定した 時ににより推論できるの元全体の集合とする。

1. が上の連続関数となることを証明せよ。
2. の最小不動点はどのような集合か。Prolog Programの挙動と対比して 説明せよ。

4.5

1. 集合Sについての以下のような3つの性質を考える．
   1. Sは半順序集合であり，Sの任意の2元について， それらの上限(最小上界)と下限(最大下界)が存在する.
   2. Sは半順序集合であり，Sの空でない任意の有限部分集合について，それらの上限と下限が存在する.
   3. 集合Sに2つの二項演算∧,∨が定義されていて, x,y,z∈Sについて以下が成り立つ.
      x∧x = x, x∧y = y∧x, x∧(y∧z) = (x∧y)∧z,
      x∨x = x, x∨y = y∨x, x∨(y∨z) = (x∨y)∨z,
      (x∧y)∨x = x, (x∨y)∧x = x
      
   このとき，以下の問に答えよ．
   1. 最初の2つの性質が同等であることを示せ．
   2. 最初の性質が成り立つとき，Sに二項演算∧,∨が定義できて， 最後の性質が成り立ち， x≦y <-> x∧y = x <-> x∨y = y(x,y∈S)が成り立つようにできることを示せ．
   3. 最後の性質が成り立つとき，Sに関係≦をx≦y <-> x∧y = x または<-> x∨y = xとして定義するとこれが半順序関係になることを示せ．
2. 半順序集合Lのすべての部分集合に上限が存在するとき， Lは上記の性質を満たすことを示せ．

4.6

半順序集合Lで，以下の条件を満たすものの例を挙げよ．
(1) Lのω-chainが必ず上限を持つ.
(2) 上限が存在しないようなLの有向部分集合が存在する.
Lが半順序集合であることと(1)を証明するだけでなく，(2)の例も示せ.
(ヒント:Lが可算集合であれば，(1),(2)を同時に満たすことはできない． また，選択公理を仮定してよい．)

4.7

すべてのcpoの集まりをCPOと書く．このとき以下を示せ．
(1) CPOは，対象を個々のcpo，射をそれらの間の連続関数としてカテゴリーとなっている.
(2) CPOには(カテゴリーの)直和が一般には存在しない.

最小元0のある束Lの元aが， a≠0 ∧ L-{0}で極小 であるときaはLのatomであるという． ∀x∈L-{0} ∃a∈L a:atom ∧ a≦x のとき，Lをatomicという． また，∀x∈L-{0} ¬∃a∈L a:atom ∧ a≦x のとき，Lをatomlessという．

束Lが完備であるとは，X⊂LであればXの上限がLの中に存在することをいう.

束Lがσ完備であるとは，X⊂Lで，Xの濃度が高々可算無限であればXの上限が 存在することをいう．完備であればσ完備である． 束Lが可算かつσ完備であれば完備である． 有限な束Lは完備である．

4.8

次の条件を満たすatomicなブール束の例を挙げ，例になっていることを示しなさい．
(1) σ完備でない．
(2) σ完備だが完備でない．
(3) 完備である．

4.9

次の条件を満たすatomlessなブール束の例を挙げ，例になっていることを示しなさい．
(1) σ完備でない．
(2) σ完備だが完備でない．
(3) 完備である．

4.10

古典命題計算(命題変数は可算無限個とする)のリンデンバウム代数が完備でないことを示せ．

4.11

古典一階述語計算のリンデンバウム代数が完備にならないための (関数記号の集合，定数記号の集合，述語記号の集合の濃度と種類についての) 十分条件を求めよ．また，もしあれば，完備になるための十分条件を求めよ (十分条件は，それを満たす関数記号，関数記号の集合，定数記号の集合， 述語記号の集合の具体例があるものであればよい. ただし，実質的に古典命題計算と同等になるもののみが条件を満たす場合は除く． 除かれる例: 引数0個の述語記号無限個から成るような集合が述語記号の集合の場合)．

---

Takashi SAKURAGAWA
Wed Nov 8 12:44:37 JST 1995