Document

3. 束
五島 正裕
DATE
:
代数系 (algebraic system)
 集合 S といくつかの演算を合わせたものを
S を台集合とする代数系(代数構造,algebraic structure)という
 抽象代数学 (abstract algebra)
 個別の集合や演算ではなく,代数系としての性質についてのみ着目
演算一つ
 半群 (semigroup)
 結合律: (a ◦ b) ◦ c = a ◦ (b ◦ c) = a ◦ b ◦ c
 単位半群 (unitary semigroup, monoid)
 半群 + 単位元
 単位元: a ◦ e = e ◦ a = a なる e
 例)文字列の連接,単位元は空文字列
 群 (group)
 単位半群 + 逆元
 逆元: x −1 ◦ x = x ◦ x −1 = e なる x −1
 可換群 (commutative group),アーベル群 (Abelian group)
 交換律: x ◦ y = y ◦ x
 例)整数上の加法
演算二つ (加法と乗法)
 環 (ring)
 加法について可換群
 乗法について半群
 可換環 (commutative ring)
 乗法についても可換
 非可換環 (non-commutative group)
 乗法について非可換
 体 (field)
 可換環 + 分配律
 分配律: x ∙ (y + z) = x ∙ y + x ∙ z
 例)実数体,複素数体
束 (lattice)
束の代数的定義
1. 交換律 (commutative law)
x ・ y = y ・ x
x + y = y + x
4. べき等律 (idempotent law)
(他の3つから導かれる)
x ・ x = x
x + x = x
2. 結合律 (associative law)
 x ・ (y ・ z) = (x ・ y) ・ z
 x + (y + z) = (x + y) + z
3. 吸収律 (absorptive law)
 x ・ (x + y) = x
 x + (x ・ y) = x
吸収律 → べき等律
 吸収律が成り立つなら,べき等律も成り立つ
吸収律 x = x ・ (x + y) において,y = (x ・ x) とおくと
x = x ・ (x + (x ・ x)) .... ①
ここで,吸収律 x + (x ・ y) = x は,y = x としても成り立つので,
x + (x ・ x) = x. ... ②
したがって,①,② より
x = x ・ (x + (x ・ x)) ... ①
= x ・ (x)
= x ・ x.
∵ ① の下線部は ② の左辺
束の半順序集合による定義
 束 L = (S, +, ・)
 半順序集合 S の任意の 2要素 x, y に対し,
{x, y} の上限,下限が共に存在する
 結び と 交わり
 x + y :{x, y} の上限:結び (join)
 x ・ y :{x, y} の下限:交わり (meet)
極大元,上界,最大元,上限
 極大元
 「X の中にそれより大きい要素がないもの.X の要素」
 上界
 「X のどの要素『以上』であるもの.X の要素であってもなくてもよ
い」
 最大元
 「X のどの要素『以上』であるもの.X の要素」
 上限
 上界(の集合)の最小元
例
x+y
x+y
x+y
x
x
y
y
x・y
x
x・y
x・y
y
束の例 (1/3)
 ブール代数(ブール束)
元
:0,1
A + B
:論理和
A ・ B
:論理積
A ≦ B
:0 ≦ 1
1
0
束の例 (2/3)
 集合演算
{a, b, c}
 元 :集合
A + B
:集合和
A ・ B
:集合積
A ≦ B
:A ⊂ B
{a, b}
{a, c}
{b, c}
{a}
{b}
{c}
 例)
 集合 A = {a, b, c} の巾集合 2A
{}
束の例 (3/3)
 因数
元
:自然数
A + B
:A, B の最小公倍数
A ・ B
:A, B の最大公約数
A ≦ B
:「A は B の因数」
12
4
6
2
 例)
 12 の因数
3
1
束にならない半順序集合
T
 {a, b} の下限はない
 {c, d} の上限はない
 a・b ?
a
b
c
d
 c+d ?
⊥
束 と 半順序集合
束 と 半順序集合
 半順序集合 → 束
半順序集合 S の任意の2元 x,y について
x ≤ y
⇔
x ・ y = x かつ x + y = y
と定義すれば,L = (S, +, ・) は束
 束 → 半順序集合
束 L = (S, +, ・) の S の任意の2元 x,y について
x ・ y = x かつ x + y = y ⇔
x ≤ y
と定義すれば,S は ≤ についての半順序集合
束 → 半順序集合 の 証明

束の定義
1.
交換律:
x・y = y・x
x+y=y+x
2.
結合律:
x・(y ・z) = (x・y)・z
x + (y + z) = (x + y) + z
3.
吸収律:
x・(x + y) = x
x + (x・y) = x
4.
べき等律:
x・x = x
x+x=x

前提条件
1.

x ・ y = x かつ x + y = y ⇔
x ≤ y
順序関係の定義
x≤x
1.
反射律:
2.
反対称律:x ≤ y and y ≤ x ⇒ x = y
3.
推移律:
x ≤ y and y ≤ z ⇒ x ≤ z
証明 (1/3)
 反射律: x ≤ x の証明
x ≤ y ⇔
x ・ y = x かつ x + y = y
を用いて x ≤ x を書き下すと
x ≤ x ⇔
x ・ x = x かつ x + x = x .
べき等則より,これは成り立つ.
証明 (2/3)
 反対称律: x ≤ y かつ y ≤ x ⇒ x = y の証明
x ≤ y ⇔
x ・ y = x かつ x + y = y
を用いて反対象律を書き下すと
x ・ y = x, x + y = y, y ・ x = y, y + x = x ⇒
これらから,
x = x ・ y = y ・ x = y . ∵ 交換律
x=y.
証明 (3/3)
 推移律: x ≤ y かつ y ≤ z ⇒ x ≤ z の証明
x ≤ y ⇔
x ・ y = x かつ x + y = y
を用いて推移律を書き下すと
x ・ y = x, x+y = y, y ・ z = y, y+z = z ⇒ x ・ z = x, x + z = z .
これらから,
x ・ z = (x ・ y) ・ z = x ・ (y ・ z) = x ・ y = x . ∵ 結合律
x + z = x + (y + z) = (x + y) +z = y + z = z .
まとめ
 代数系 (algebraic system)
 集合 S といくつかの演算を合わせたもの
 束 L = (S, +, ・)
1.
交換律
2.
結合律
3.
吸収律
4.
べき等律
 束 と 半順序集合
来週
 ブール束 = ブール代数