格論學習筆記2：格的基本性質

03-02

目錄：類型論驛站寫作計劃

前一篇：格論學習筆記1：基礎概念

後一篇：格論學習筆記3：分配格

學習資料: ESSLLI 2017 -- Lattice Theory home page (John Harding)

定義1（標記/標誌/標識/類型，type）

一個標記 $au$ 包括一個集合，稱為指標集（indexing set），以及一個映射 $au:I o mathbb{N}$ 。當 $au$ 可以從上下文推出時，我們將 $au(i)$ 記為 $n_i$ 。

這裡的 type 和類型論的 type不一樣，在類型論和邏輯中對應的概念是signature（標識簽）。在代數和泛代數里，type 是 similarity type （相似性標記）的簡稱。為避免混淆，我把泛代數里的 type 譯為「標記」。

定義2

標記為 $au$ 的代數是一個對子 $(A,(f_i)_I)$ ，其中：

$A$ 是一個集合
$f_i:A^{n_i} o A$

如果 $n_i=0$ ，由於 $A^0$ 是一個一元集合， $f_i$ 是由它的像（image）決定的，所以 $f_i$ 選取 $A$ 中的一個元素。我們稱 $f_i$ 為零元運算（nullary operation）或常量/常數（constant）。

例如，群 $(G,cdot,^{-1}, e)$ 是一個標記為 $2,1,0$ 的代數；環 $(R,+,cdot,-,0,1)$ 是一個標記為 $2,2,1,0,0$ 的代數。

格對應著標記為 $2,2$ 的代數 $(L,wedge, vee)$ ，有界格（bounded lattices）對應著標記為 $2,2,0,0$ 的代數 $(L,wedge,vee,0,1)$ 。

命題1（格的基本性質）

對於任意格 $L$ ，代數 $(L,wedge,vee)$ 滿足下列性質

$xwedge x=x$
$xvee x = x$
$xwedge y = ywedge x$
$xvee y = y vee x$
$(xwedge y )wedge z=xwedge (ywedge z)$
$(xvee y )vee z = x vee (y vee z)$
$xwedge (x vee y) = x = x vee (x wedge y)$ （absorption，吸收律，吸収法則）

命題2

對於任何滿足命題1的7個性質的的代數 $(L,wedge,vee)$ ，都存在一個 $L$ 上的偏序： $xle y ext{iff} x wedge y = x$ .

有了這個偏序， $L$ 可以視為一個格，其中 $xwedge y$ 是 $x,y$ 的最大下界， $xvee y$ 則是它們的最小上界。

在考慮有限並和交的情況下，將格視為代數更為有用，而如果考慮任何無限並和交的情況時，序論視角更為有用。

定義3（格同態，lattice homomorphism，束準同型）

格同態是一個滿足下列條件的映射 $f:L o M$ ：

$f(xwedge y) = f(x)wedge f(y)$
$f(xvee y) = f(x)vee f(y)$

對於標記是 $2,2,0,0$ 的有界格來說， $f(0)=0, f(1)=1$

定義4（格嵌入，lattice embedding，束埋め込み）

格嵌入式一個單射格同態。

習題

對於一個格，證明 $xle y ext{iff} f(x) le f(y)$ .

子代數（subalgebra，部分代數）是一個代數結構在運算下閉合的子集。

定義5（子格，sublattice）

格 $L$ 的子格是一個滿足下列條件的子集 $Ssubseteq L$ ：

$x,yin SRightarrow xwedge y in S$
$x,y in SRightarrow xvee y in S$

對於有界格，我們有 $0in S, 1in S$

定義6（格積，product of lattices）

格 $L,M$ 的積是集合 $L imes M={(x,y) : xin L, yin M}$ ，其並（join，結び）和交（meet，交わり）定義如下：

$(x_1,y_1)wedge(x_2,y_2) = (x_1wedge x_2, y_1wedge y_2)\ (x_1,y_1)vee(x_2,y_2) = (x_1vee x_2, y_1vee y_2)$

格積/積格可以用哈斯圖表示：

設2為二元素格，我們可以描述它的有限冪格：

當然，無限積也是可以定義的：

定義7

對於 $jin J$ 的格 $L_j$ 來說，它們的積是集合

$prod_J L_j = {alpha mid alpha: J o igcup_J L_j, 其中對於任意j in J, alpha(j)in L_j}$

再加上按組成成分進行的（componentwise）運算，所以我們有 $(alphawedge eta)(j)=(alpha(j))wedge (eta(j))$ .

定義8（格同餘，lattice congruence）

格 $L$ 上的同餘關係 $approx$ 是滿足下列條件的等價關係：

$xapprox u 且 yapprox vRightarrow xwedge y approx u wedge v$
$xapprox u 且 yapprox vRightarrow xvee y approx u vee v$

定義9（商格，quotient lattice）

如果 $approx$ 是 $L$ 上的一個同餘關係，那麼 $L/approx$ 是一個滿足下列條件的格：

$(x/approx) wedge (y/approx) = (xwedge y)/approx$
$(x/approx) vee (y/approx) = (xvee y)/approx$

此外，函數 $f:L o L/approx$ 是一個滿射格同態。

我們可以用哈斯圖來表示商格：

定義10（簇，variety）

一類代數 $V$ 構成一個簇，如果其中的所有代數都有著同一個標記，且滿足一些方程集合。

例如，群，阿貝爾群，環，交換環，實向量空間，以及格，都是簇。

定理3（[泛代數]伯克霍夫定理，Birkhoffs theorem）

一類代數構成簇當且僅當這些代數在HSP（同態像 homomorphic images, 子代數 subalgebras, 積 products）下是閉合的。

格有著無限多的子簇。但兩個子簇有著特別重要的意義

定義11（分配格，distributive lattices）

對於一個格 $L$ 來說，下面兩個條件是等價的：

對於所有 $x,y,z$ ，我們有 $xwedge (yvee z) = (xwedge y) vee (x wedge z)$
對於所有 $x,y,z$ ，我們有 $xvee (ywedge z) = (xvee y) wedge (x vee z)$

滿足上述條件的格貝稱為分配格。分配格構成一個簇。

定義12（模格，modular lattice）

對於一個格 $L$ 來說，下面的條件是等價的：對於所有 $x,y,z$ ,

$zle x Rightarrow x wedge (y vee z) = (xwedge y)vee (xwedge z)$
$xle z Rightarrow x vee (y wedge z) = (xvee y )wedge (x vee z)$
$(xvee z)wedge (y vee z)=((xvee z)wedge y)vee z$
$(xwedge z)vee (y wedge z) = ((xwedge z)vee y)wedge z$

滿足上述條件的格貝稱為模格。模格構成一個簇。

模律（modularity）的意思是當 $x,y,z$ 可以比較時，它們之間的運算滿足分配率。

分配格對應著邏輯和集合論，模格對應著代數、組合數學和幾何學。如果再給格添加一些其他運算，就會形成一些有趣的代數。

George Boole, 英國數學家 1815-1864

定義13（布爾代數，Boolean algebra）

如果滿足下列條件，代數 $(B,wedge, vee,,0,1)$ 是一個布爾代數：

$(B,wedge, vee, 0,1)$ 是一個有界格
$(B,wedge, vee)$ 是一個分配格
$xwedge x = 0$
$xvee x =1$

布爾代數構成一個簇。布爾代數可以為經典邏輯提供語義詮釋。

Arend Heyting，荷蘭數學家、邏輯學家 1898 - 1980

定義14（海廷代數，Heyting algebra）

如果滿足下列條件，代數 $(B,wedge, vee, o,0,1)$ 是一個海廷代數：

$(B,wedge, vee, 0,1)$ 是一個有界格
$(B,wedge, vee)$ 是一個分配格
$x o x =1$
$xwedge (x o y)=xwedge y$
$ywedge (x o y) = y$
$x o (ywedge z) = (x o y)wedge (x o z)$

海廷代數構成一個簇。海廷代數可以為直覺主義邏輯提供語義詮釋。

定義15（模態代數，modal algebra）

如果滿足下列條件，代數 $(B,diamond, wedge, vee, ,0,1)$ 是一個模態代數：

$(B,wedge, vee,,0,1)$ 是一個布爾代數
$diamond(xvee y) = diamond x vee diamond y$
$diamond 0 = 0$

模態代數構成一個簇。模態代數可以為（經典）模態邏輯提供語義詮釋。

定義16（關係代數，relation algebra）

如果滿足下列條件，代數 $(B,circ, ^smile, riangle, wedge, vee, ,0,1)$ 是一個關係代數：

$(B,wedge, vee,,0,1)$ 是一個布爾代數
$xcirc (ycirc z) = (x circ y )circ z$
$xcirc riangle = x = riangle circ x$
$(xvee y)circ z = (x circ z)vee (ycirc z)$
$(xcirc y)^smile = y^smile circ x^smile$
$(xvee y)^smile = x^smile vee y^smile$
$(x^smile circ (xcirc y))vee y = y$

關係代數構成一個簇。

集合 $X$ 上二元關係是一個子集 $Rsubseteq X imes X$ 。所有 $R$ 的集合是冪集 $B=mathcal{P}(X imes X)$ 。使用 $circ$ 進行關係的複合（composition），使用 $^smile$ 定義逆關係（converse relation），使用 $riangle$ 定義單位關係（identity relation）。

目錄：類型論驛站寫作計劃

前一篇：格論學習筆記1：基礎概念

後一篇：格論學習筆記3：分配格