束 (束論)
数学における束(そく、英語: lattice)は、任意の二元集合が一意的な上限(最小上界、二元の結びとも呼ばれる)および下限(最大下界、二元の交わりとも呼ばれる)を持つ半順序集合である。それと同時に、ある種の公理的恒等式を満足する代数的構造としても定義できる。二つの定義が同値であることにより、束論は順序集合と普遍代数学の双方の領域に属することとなる。さらに、半束 (semilattice) の概念は束の概念を含み、さらにハイティング代数やブール代数の概念も含む。これら束に関連する構造は全て順序集合としても代数系としても記述することができるという特徴を持つ。
定義
[編集]半順序集合として
[編集]半順序集合 (L, ≤) が束であるとは、以下の二条件が満足されるときに言う。
- 二元の結びの存在
- L の任意の二元 a, b に対して、二元集合 {a, b} が結び(上限、最小上界、和) a ∨ b を持つ。
- 二元の交わりの存在
- L の任意の二元 a, b に対して、二元集合 {a, b} が交わり(下限、最大下界、積) a ∧ b を持つ。
これにより、∨ および ∧ は L 上の二項演算となる。最初の条件は L が結び半束 (join-semilattice) となることを主張するものであり、後の条件は L が交わり半束 (meet-semilattice) となることをいうものである。二つの演算はその順序に関して単調である。すなわち、a1 ≤ a2 かつ b1 ≤ b2 ならば
がともに成り立つ。
このとき、帰納的に、束の任意の空でない有限集合に対して、その結び(上限)および交わり(下限)の存在が示せる。さらに仮定を増やせば、もっといろいろなことが言える場合もある。完備性 (順序集合論)等を参照。そういった文脈では、上記の定義をもっと別の方法、例えば適当なガロワ接続の存在によって定義することもできる(これは束に対するある種のガロワ理論的な手法である)[要出典]。
有界束 (bounded lattice) は 1 で表される最大元 (greatest element, maximum, top (⊤)) および 0 で表される最小元 (least element, minimum, bottom (⊥)) を持つ束である。任意の束は最大元と最小元を付加することにより有界束とすることができる。また、空でない任意の有限束は有界である(全ての元の結びおよび交わりが最大元及び最小元を与える)。すなわち、A = {a1, …, an} ならば
が成り立つ。
半順序集合が束となる必要十分条件は、任意の有限部分集合(零元集合としての空集合を含む意味で言う)が結びおよび交わりを持つことである。ここで、空集合に関する結びは最小元、空集合に関する交わりは最大元となるものと約束する。
この規約は、結びおよび交わりの結合性および可換性に整合性を持たせるためのものである。すなわち、有限集合の族の和集合の結びはそれらの集合の結びの結びに一致し、双対的に、有限集合の族の和集合の交わりがそれらの集合の交わりの交わりとなる。これは、具体的に束 L の有限部分集合を A, B とすると、
がともに成り立つという意味である。ここで B として空集合を取ると
となり、これは A ∪ ∅ = A であるという事実と整合する。
代数的構造として
[編集]集合 L および L 上の二項演算 ∨, ∧ からなる代数的構造 (L, ∨, ∧) が束であるとは、L の任意の元 a, b, c に対して以下の公理的な恒等式を満足するときに言う。
可換律 | 結合律 | 吸収律 |
---|---|---|
さらに以下の二つの恒等式を公理として仮定することも多いが、実際には吸収律を二度使うことで導くことが可能である[* 1]
これらの公理は (L, ∨) および (L, ∧) がともに半束となることを要請するものである。また吸収律は(公理のうちこれだけが条件式に結びと交わりの両方が現れているので)、これによって束が、単にかってな半束の対ということではなく、対となる二つの半束のあいだに適切な相互関係があることを仮定するものとなっている。特に、互いの半束の間に双対性が見て取れる。
代数的な意味での有界束とは代数的構造 (L, ∨, ∧, 1, 0) であって、(L, ∨, ∧) は束であり、(束の最小元となるべき)0 が結び ∨ に関する単位元で、(束の最大元となるべき)1 が交わり ∧ に関する単位元となるものをいう。さらなる詳細は半束の項に譲る。
束はある種の群に似た代数的構造と関連がある。実際、交わりも結びも結合的かつ可換なので、束を台を共有するふたつの可換半群の対と看做すことができる。有界束ならば、この二つの半群は実際には可換モノイドになる。吸収律だけが、束論に特有の定義式である。
可換性と結合性により、結びや交わりを二項ではなく空でない任意の有限集合上の演算として考えることもできる。有界束の場合には、空集合に関する結び(空和)と空集合に関する交わり(空積)をそれぞれ 0 と 1 として定義することができる。このことは、有界束がある意味で一般の束よりも自然であるという見方を与えるものであって、しばしば、単に束といえば有界束のことを意味するという文献があるので注意が必要である。
このような束の代数的な解釈は普遍代数学において本質的な役割を果たす。
定義の同値性
[編集]順序集合論的な束は二つの二項演算 ∨, ∧ を生じ、その可換性、結合性、吸収性から (L, ∨, ∧) が代数的な意味での束を定めることを確かめることは難しくない。このとき、もとの順序関係は、こうしてえられた代数的構造からすぐに回復することができる。すなわち
と定めて得られた順序 ≤ は、もとの束の順序関係に一致する。
逆に、代数的に定義された束 (L, ∨, ∧) に対し、L 上の半順序 ≤ を、L の各元 a, b に対して
または
で定めれば順序集合論的な意味の束が得られる。吸収律はいずれの定義に関しても同値である。そうして、この方法で定めた順序関係 ≤ が導く結びと交わりがもともとの代数的な意味での束の演算 ∨, ∧ に一致することも確かめられる。
このように束の二つの定義は同値であるから、必要と目的に応じて束の二つの側面を自由に選んで使うことができる。
例
[編集]- 任意の集合 A に対して、A の部分集合全体からなる族(A の冪集合)は包含関係の定める順序に関して束となる。これは A 自身を最大元、空集合を最小元とする有界束である。交わりおよび結びは共通部分および和集合によってそれぞれ与えられる。
- 任意の集合 A に対して、A の有限部分集合全体の成す族に包含関係で順序を入れたものはやはり束になる。この束が有界となるのは A 自身が有限であるときであり、かつそのときに限る。
- 任意の集合 A に対して、A の分割全体の成す族に分割の細分によって順序を入れれば束となる。
- 自然数全体の成す集合(ただし、0 を含む)N に対し、通常の大小関係を考えたものは "min" および "max" を演算として束を成す。この場合、自然数 0 は最小元だが、最大元は存在しない。
- 自然数全体の成す集合のデカルト積 N × N に対して、順序 ≤ をで定めると、自然数の対 (0, 0) が最小元で最大元は無い。
- 自然数全体の成す集合 N に整除関係 | を順序とし、演算として最大公約数 gcd および最小公倍数 lcm を考えれば、やはり束が得られる。この場合、自然数 1 が最小元で、自然数 0 が最大元となる。
- 任意の完備束(後述)は特殊な有界束である。実際に現れる束のかなり広範な部分が、このクラスに属する束となっている。
- 完備算術束のコンパクト元全体の成す集合は、最小元を持つ束となる。束演算はもとの算術束の各演算を制限することにより得られる。これは算術束を代数束と区別する特別な性質である(代数束ならばコンパクト元の全体は結び半束にしかならない)。これらの束は領域理論において研究される。
ほとんどの半順序集合は束を成さない。例えば以下のようなものは束にならない。
- 離散的半順序集合、すなわち x ≤ y ならば x = y となるような半順序集合が束となるのは、それが高々ひとつしか元を持たないときであり、かつそのときに限る。特に二元からなる離散的半順序集合は束ではない。
- 集合 {1, 2, 3, 6} に整除関係で順序を入れたものは束となるが、集合 {1, 2, 3} に同じ順序をいれたものは束にならない。実際、2 と 3 の対に対して結びが無く、{2, 3, 6} には交わりが無い。
- 集合 {1, 2, 3, 12, 18, 36} に整除関係で順序を入れたものも束にはならない。実際、どの二つの元に対しても上界と下界があるが、2 と 3 の対の 12, 18, 36 という三つの上界の中に整除関係に関して最小となるものが存在しない(12 と 18 は互いに他方を割り切らない)。同様に、12 と 18 の対には 1, 2, 3 という三つの下界があるが、それらの中に整除関係に関して最大となるものは存在しない(2 と 3 は互いに他を割り切らない)。
更なる例については、追加の条件ごとに分けて後述する。
束準同型
[編集]二つの束の間の射(あるいは準同型)としてどのようなものを考えるべきかは、代数的構造としての定義を使えば容易にわかる。二つの束 (L, ∨L, ∧L) および (M, ∨M, ∧M) が与えられたとき、束の射あるいは束準同型とは、写像 f: L → M で
をともに満たすものを言う。つまり f は下敷きとなる二つの半束の双方に関して準同型写像となるものである。ただし、束に対してさらに追加の構造を考えている場合には、準同型としてそれらの付加構造に関しても整合的であるようなものを考えるのが普通である。従って例えば、準同型 f が二つの有界束 L, M の間で考えるものであれば、
も同時に満たすべき条件であるとみなされる。これを順序集合論的に定式化するならば、これらの条件は単に、束準同型というのは二元の交わりと結びを保つ写像であると言っているに過ぎない。有界束の場合に最大元と最小元も保つことは、空集合に関する結びと交わりを保つことで言える。
任意の束準同型は付随する順序関係に関して単調である必要があるが、逆は真ではない。つまり、単調性は結びや交わりを保存することを保証しない[2]。一方、順序を保つ全単射が束準同型となるのは、その逆写像がやはり向きを保つときである。
同型写像に関して、それが可逆な準同型であるという意味の標準的な定義に従えば、束同型は単に全単射な束準同型を考えればよく、同様に、束自己準同型は束からその束自身への束準同型であり、また束自己同型は全単射な束自己準同型である。束の全体を対象とし、束準同型を射としてひとつの圏が定まる。
束のクラス
[編集]以下、いくつか意味のある束のクラスを定めるさまざまに重要な束の性質について述べる。なお、そのうちの一つ、有界性についてはすでに述べてあることを注記する。
完備性
[編集]半順序集合が完備束 (complete lattice) であるとは、その任意の部分集合が交わりと結びを持つときに言う。特に任意の完備束は有界束である。有限束の準同型は有限な交わりおよび結びしか保存しないが、完備束の準同型では任意濃度の交わりと結びを保つことを要請する。
任意の半順序集合はそれが完備半束であるならば完備束となる。この事実に関する面白い現象として、このクラスの半順序集合に対しては、いくつもの準同型を同時並行的に考えることができるということが挙げられる(つまり、それを完備束とみるか、完備結び半束とみるか、完備交わり半束とみるか、結び完備束とみるか交わり完備束とみるか、それぞれの意味での準同型を考えうる)。
条件付き完備性
[編集]条件付き完備束 (conditionally complete lattice) とは任意の空でなく上に有界な部分集合が結び(最小上界)を持つことをいう。このような束は実数全体の集合に対する完備性公理を最も直接に一般化するものである。条件付き完備束は、完備束か、完備束から最大元 1 を除いたものか、完備束から最小元 0 を除いたものか、あるいは完備束から最大元と最小元の両方を取り除いたものかのいずれかである。
分配性
[編集]束には二項演算がふたつあることから、一方が他方に対して分配的かということを考えるのは自然な問いである。すなわち、束 L の各元 a, b, c に対して、互いに双対的な次の等式
- ∨ の ∧ に対する分配性
- a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c).
- ∧ の ∨ に対する分配性
- a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c).
が成り立つかということを考える。これらは等式
- (a ∧ b) ∨ (b ∧ c) ∨ (c ∧ a) = (a ∨ b) ∧ (b ∨ c) ∧ (c ∨ a)
が成り立つこととも同値である[3]。束が最初の等式を(従って、束にとって同値な後の等式も)満足するならば、分配束 (distributive lattice) と呼ばれる。束が分配的である必要十分条件は M3 もしくは N5 (右図)と同型な部分束を含まないことである[4][5]。集合束(ring of sets)は分配的であり、逆に任意の分配束は集合束と同型である(Birkhoffの表現定理[6])。
完備束に対して相性のよい分配性の狭義の概念というものを考えれば、完備ハイティング代数や完備分配束といったもっと特別のクラスを定義することができる。
モジュラー性
[編集]応用に際して、分配性条件は強すぎる制約となることがあり、次のようなより弱い性質を考えると便利なことがよくある。束 (L, ∨, ∧) がモジュラー (modular) であるとは L の各元 a, b, c に対して
- モジュラー恒等式
- (a ∧ c) ∨ (b ∧ c) = [(a ∧ c) ∨ b] ∧ c
が成立するときにいう。この条件は次の条件と同値である。
- モジュラー律
- a ≤ c ならば a ∨ (b ∧ c) = (a ∨ b) ∧ c.
束がモジュラーである必要十分条件は N5(右図)と同型な部分束を含まないことである[7][8]。分配束はモジュラーだが、分配束とは限らないモジュラー束の例として、加群の部分加群全体の成す束や、群の正規部分群全体の成す束が挙げられる。
半モジュラー性
[編集]モジュラー性でも強すぎるときに(上)半モジュラーと呼ばれる次のような性質を課すことがある。 束 L が (上)半モジュラー ((upper)semimodular) であるとは
- 半モジュラー律
- a ∧ b <: a ならば b <: a ∨ b。
が成立するときにいう。ただしここで a <: b とは b が a を被覆する、すなわち a < b であり a < c < b となるような c が存在しないこと。
上半モジュラーの双対概念を下半モジュラーという。 モジュラー束は上及び下半モジュラーだが逆は一般には成立しない。しかし有限束などでは両者は一致する。
半モジュラーの更なる一般化として 弱半モジュラー (weakly semimodular) 又はバーコフ条件と言われる以下の条件がある
- バーコフ条件
- a ∧ b <: a かつ a ∧ b <: b ならば a <: a ∨ b かつ b <: a ∨ b。
任意の半モジュラー束は弱半モジュラー束である。
連続束と代数束
[編集]領域理論において、半順序集合の元を「より単純な」元によって近似することを考えるのは自然である。それによって、任意の元がその元のずっと下にある元の成す有向集合の上限として得られるような半順序集合からなる連続的半順序集合のクラスが導かれる。ここでさらに有向集合を得るのに使える元をコンパクト元に制限することを考えるならば、代数的半順序集合が得られる。これらの概念を束に対しても考えれば、
- 連続束 (continuous lattice): 半順序集合として連続的な完備束
- 代数束 (algebraic lattice): 半順序集合として代数的な完備束
のクラスが得られるが、これらはいずれも興味深い性質を持つクラスである。例えば連続束は、ある種の恒等式を満足する(項数有限な)演算をもつ代数的構造として特徴付けられる。一方、代数束の同じような特徴づけは知られていないが、「統語論的」("syntactical") には、Scott information systemを通じて記述できる。
補元と擬補元
[編集]L が最大元 1 と最小元 0 を持つ有界束とする。L の二元 x および y が互いに他の補元 (complements) であるとは
- and
が成り立つことをいう。特に補元が一意に定まる場合、これを ¬x = y および ¬y = x で表す。任意の元が補元を持つ有界束は可補束 (complemented lattice) と呼ばれ、補元が一意に定まる場合、 L 上の単項演算 ¬ は補演算あるいは補化 (complementation) と呼ばれる。これは論理否定の束論における類似物として導入された。一般に補元は一意である必要も、L 上で可能な全ての単項演算のなかで特別なものであるわけでもない。可補束がさらに分配的でもあるならば、それはブール代数である。分配束に対しては、補元は存在すれば一意である。
ハイティング代数は、その元が必ずしも補元を持つとは限らない分配束の例である。しかし、ハイティング代数の各元 x は擬補元 (pseudo-complement) と呼ばれる、やはり ¬x で表される元を必ず持つ。この擬補元は x ∧ y = 0 となるような y の中で最大のものである。ハイティング代数の各元が持つ擬補元が、実際には補元であるとき、そのハイティング代数は実はブール代数である。
部分束
[編集]束 L の部分束 (sublattice) とは、L の空でない部分集合であって、L と同じ交わりと結びによって再び束となるようなものをいう。つまり、L が束で、L の部分集合 M ≠ ∅ を考えるとき、M の元の任意の対 a, b に対して a ∨ b と a ∧ b がともに M に属するならば、M は L の部分束である[9]。
束 L の部分束 M が L の凸部分束 (convex sublattice) であるとは、L の各元 x, y, z に対して、x ≤ z ≤ y かつ x, y ∈ M ならば z ∈ M となるときにいう。
自由束
[編集]任意の集合 X に対して、それが生成する自由半束 FX を考えることができる。すなわち、FX は X の有限部分集合全体に通常の集合の和を考えて得られる半束として定義される。自由半束は普遍性を持つ。
束論の重要概念
[編集]以下、束論において重要な、順序集合論的概念をいくつか定義する。以下、x はある束 L の元を表すものとし、L が最小元 0 を持つ場合には x ≠ 0 であることも要求することがある。 x が
- 結び既約元 (Join irreducible)
- であるとは、x = a ∨ b ならば x = a または x = b が L の各元 a, b について成り立つことをいう[注釈 1]。
- この最初の条件を任意個の結び に一般化した場合は x は完全結び既約 (completely join irreducible or ∨-irreducible) であるという。結び既約性の双対概念は交わり既約性 (meet irreducibility or ∧-irreducible) である。
- 結び素元 (Join prime)
- であるとは x ≤ a ∨ b ならば x ≤ a または x ≤ b が成り立つことをいう[10]。
- これも同様に一般化して完全結び素元 (completely join prime) の概念が得られる。結び素元の双対概念は交わり素元 (meet prime) である。任意の結び素元は結び既約であり、任意の交わり素元は交わり既約である。逆は、L が分配的ならば正しい。
束 L が最小元 0 を持つとし、L のある元 x が分解不能元(あるいは原子元)であるとは、0 < x かつ 0 < y < x となるような L の元 y が存在しないことをいう。さらに束 L が
- 原子的あるいは分解不能 (Atomic)
- であるとは、L の最小元 0 と異なる任意の元 x に対して、a ≤ x となるような L の分解不能元 a が存在するときに言う。
- 原子論的 (Atomistic)
- であるとは、L の任意の元が分解不能元の上限として得られるときに言う。すなわち、L の なる任意の元 a, b に対して x ≤ a かつ となるような L の分解不能元 x が存在する。
任意の半順序集合に対して、互いに双対なイデアルおよびフィルターの概念をある種の部分集合族として考えることができるが、もちろん半順序集合である束の理論においてもそれはやはり重要な概念であるが、詳細はそれぞれの項に譲る。
脚注
[編集]注釈
[編集]- ^ Grätzer (2009, p. 60) は x ≠ 0 を要求しないが、Davey & Priestley (2002, p. 53) は x ≠ 0 を要求している。
出典
[編集]- ^ Dedekind, Richard (1897), “Ueber Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler”, Braunschweiger Festschrift: 1–40
- ^ Davey & Priestley 2002, p. 43, Examples 2.18.
- ^ Grätzer 2009, p. 37.
- ^ Davey & Priestley 2002, p. 89, Theorem 4.10(ii).
- ^ Grätzer 2009, p. 70, Theorem 1.
- ^ Grätzer 2009, p. 75, Theorem 19.
- ^ Davey & Priestley 2002, p. 89, Theorem 4.10(i).
- ^ Grätzer 2009, p. 70, Theorem 2(i).
- ^ Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 3-540-90578-2.
- ^ Nation, p. 66, Exercise 6 for Chapter 6
参考文献
[編集]Monographs available free online:
- Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 3-540-90578-2.
- Jipsen, Peter, and Henry Rose, Varieties of Lattices, Lecture Notes in Mathematics 1533, Springer Verlag, 1992. ISBN 0-387-56314-8.
- Nation, J. B., Notes on Lattice Theory. Chapters 1-6. Chapters 7-12; Appendices 1-3.
Elementary texts recommended for those with limited mathematical maturity:
- Donnellan, Thomas, 1968. Lattice Theory. Pergamon.
- Grätzer, G. (2009) [1971], Lattice Theory: First Concepts and Distributive Lattices, Dover, ISBN 978-0-486-47173-0, MR0321817, Zbl 0232.06001
The standard contemporary introductory text, somewhat harder than the above:
- Davey, B.A.; Priestley, H. A. (2002), Introduction to Lattices and Order (Second ed.), Cambridge University Press, ISBN 978-0-521-78451-1, MR1902334, Zbl 1002.06001 知能と情報 Vol.19 No.2 p.148
Advanced monographs:
- Garrett Birkhoff, 1967. Lattice Theory, 3rd ed. Vol. 25 of AMS Colloquium Publications. American Mathematical Society.
- Robert P. Dilworth and Crawley, Peter, 1973. Algebraic Theory of Lattices. Prentice-Hall. ISBN 9780130222695.
On free lattices:
- R. Freese, J. Jezek, and J. B. Nation, 1985. "Free Lattices". Mathematical Surveys and Monographs Vol. 42. Mathematical Association of America.
- Johnstone, P.T., 1982. Stone spaces. Cambridge Studies in Advanced Mathematics 3. Cambridge University Press.
関連項目
[編集]外部リンク
[編集]- Weisstein, Eric W. "Lattice". mathworld.wolfram.com (英語).
- J.B. Nation, Notes on Lattice Theory, unpublished course notes available as two PDF files.
- Ralph Freese, "Lattice Theory Homepage".