利用者: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)
[編集]脚注
[編集]- ^ g.f.p.(f)、l.f.p.(f) は定義から当然以下
- 任意の x ∈ Fix(f) に対して、x ≦ g.f.p.(f) 及び l.f.p.(f) ≦ x
参考文献
[編集]- ガーレット・バーコフ, ソンダース・マクレーン『現代代数学概論』(改訂第3版)白水社、1967年。
- 前田 周一郎『束論と量子論理』槙書店、1980年。
- Garrett Birkhoff (1979). Lattice Theory (3rd ed.). American Mathematical Society
- G.Birkhoff, O.Frink (1948), “Representations of lattices by sets”, Trans. Amer. Math. Soc. 64
- 山崎 進『計算論理に基づく推論ソフトウェア論』コロナ社、2000年。
- Alfred Tarski (1955), A lattice-theoretical fixpoint theorem and its applications
- Dana Scott (1976), Data types as lattices
- Dana Scott (1972), “Continuous lattices”, Lecture Notes in Mathematics Volume 274
- G.Gierz, K. H. Hofmann, K.Keimel, J. D. Lawson, M.W. Mislove and D.S. Scott (2003). Continuous lattices and domains. Encyclopedia of Mathematics and its Applications. Cambridge press
- Joseph E. Stoy (1977). Denotational Semantics: The Scott-Strachey Approach to Programming Language Semantics. MIT Press
- 竹之内 脩『ルベーグ積分』培風館〈現代数学レクチャーズ〉、1980年。