コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

利用者:I.hidekazu/完備束

完備束(complete lattice)とは、任意の部分集合について最小上界及び最大下界を持つ束 <C ; ∧ , ∨> または半順序集合 <C ; ≦> を言う。

定義

[編集]

完備束(complete lattice)

[編集]

半順序集合 <C ; ≦> の任意の部分集合 S ⊆ C に対して、最小上界 ∨(S) ∈ C と最大下界 ∧(S) ∈ C が存在するとき、<C ; ≦, ∨, ∧> を完備束(complete lattice)と呼ぶ。 すなわち、半順序集合が∨完備かつ∧完備であるとき、完備束と呼ぶ。

σ完備束(σ-complete lattice)

[編集]

半順序集合 <C ; ≦> の任意の高々可算個の元からなる部分集合 D ⊆ P について最小上界 ∨(D) ∈ C 及び最大下界 ∧(D) ∈ C が存在するとき、<C ; ≦, ∨, ∧> をσ完備束(σ-complete lattice)と呼ぶ。

連続束(continuous lattice)

[編集]

完備性を用いた不動点定理

[編集]

半順序集合を <P ; ≦> とし、自身に戻る単調写像を f : P → P とする。このとき、f(a) = a を満たす P の元 a ∈ P を f の不動点(fixedpoint, fixpoint)と呼ぶ。

最大不動点(greatest fixed-point)と最小不動点(least fixed-point)

f の不動点の集合を

Fix(f) = { a ∈ P | f(a) = a }

とする。Fix(f) が最大元を持つときその最大元を最大不動点(greatest fixed-point)、最小元を持つときその最小元を最小不動点(least fixed-point)と呼び、それぞれ g.f.p.(f)、l.f.p.(f) と表す[1]

クナスター・タルスキの定理(Knaster-Tarski theorem)

[編集]

脚注

[編集]
  1. ^ g.f.p.(f)、l.f.p.(f) は定義から当然以下
    任意の x ∈ Fix(f) に対して、x ≦ g.f.p.(f) 及び l.f.p.(f) ≦ x
    を満たす。

参考文献

[編集]