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

03-03

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

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

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

經典著作：

Birkhoff: Lattice Theory（進階，較為陳舊，但仍為最佳）
Crawley and Dilworth: The Algebraic Theory of Lattices
Balbes and Dwinger: Distributive Lattices
Davey and Priestley: Introduction to Lattices and Order

格論（lattice theory，束論）在眾多領域都有著重要的應用，如代數、分析、拓撲、邏輯、計算機科學、組合數學、線性代數、幾何學、範疇論、概率論等。

定義1（偏序集，partial order, 半順序集合）

偏序集，或雲 poset，是一個有著二元關係 $le$ 的集合 $P$ ，對於 $x,y,zin P$ ，滿足下列條件：

自反性（reflexive，反射関係）： $xle x$
反對稱性（anti-symmetric，反対稱関係）： $xle y$ 且 $yle x$ $Rightarrow x = y$
傳遞性（transitive，推移関係）： $xle y$ 且 $yle zRightarrow xle z$

倘若該集合還滿足「 $xle y$ 或 $yle x$ 」（完全性，totality，完全律），那麼這個偏序集被稱為線性順序集合（linear order，線型順序集合）或鏈（chain，鎖）。

哈斯圖（Hasse diagram，ハッセ図）

以 $P$ 的元素為點，以其 $le$ 為邊（以上為尊，以下為卑），可以繪製哈斯圖。例如：

哈斯圖

對於有限偏序集合，哈斯圖較為好畫。對於某些無限集合，如 $mathbb{N}$ ，問題也不大。但哈斯圖難以表現有理數集 $mathbb{Q}$ 和實數集 $mathbb{R}$ 。

一些術語：

零（zero/bottom，零） $0$ / $ot$ ： $P$ 中的最小值，如果存在的話

一（one/top，一） $1$ / $op$ ： $P$ 中的最大值，如果存在的話

界（bounds，界）： $0$ 和 $1$

包含（cover）：如果 $a<b$ 且不存在 $c>a,c<b$ ，那麼我們稱 $b$ 包含 $a$

原子（atom）：包含 $0$ 的元素

陪原子/余原子（coatom）：被 $1$ 包含的元素

對偶序（order dual）：將 $P$ 反置的偏序集合

陪原子、對偶序為筆者自創譯名。

對於 $Asubseteq P$ ，我們有：

$x$ 為 $A$ 的極大元（maximal），如果 $xin A$ 且不存在 $yin A, x < y$

$x$ 為 $A$ 的最大元（maximum），如果 $xin A$ 且對於所有 $yin A$ ，都有 $yle x$

$A$ 的上界集合（upper bounds） $U(A)$ ：對於所有 $xin A,$ $xle u$ 的 $u$ 的集合

$A$ 的下界集合（lower bounds） $L(A)$ ：對於所有 $xin A,$ $vle x$ 的 $v$ 的集合

最小上界（least upper bound） $igvee A$ ： $U(A)$ 的最小元

最大下界（greatest lower bound） $igwedge A$ ： $L(A)$ 的最大元

定義2（格，lattice，束）

如果一個偏序集 $L$ 的任意兩個元素的集合 ${a,b}$ 都有一個最小上界 $avee b$ 和一個最大下界 $awedge b$ ，那麼它是一個格。如果每一個子集 $Asubseteq L$ 都有一個最小上界 $igvee A$ 和最大下界 $igwedge A$ ，那麼我們稱該格為完全格（complete lattice，完備束）。