數學中,(英語:Lattice)是其非空有限子集都有一個上確界(稱為)和一個下確界(稱為)的偏序集合(poset)。格也可以特徵化為滿足特定公理恆等式代數結構。因為兩個定義是等價的,格理論從序理論泛代數二者提取內容。半格包括了格,依次包括海廷代數布林代數。這些"格樣式"的結構都允許序理論和抽象代數的描述。

Thumb
術語來源於描述這種次序的哈斯圖的形狀。

需要注意的是,本條目介紹的是序理論中的「格」,並非幾何與群論中的「格(群論)」(點陣),兩者的英文均為「lattice」。雖然在繼承自平面的次序中,每個點陣都是格,但是許多格不是點陣。[1]

序理論定義

考慮任意一個偏序集合L,≤),如果對集合L中的任意元素a,b,使得a,b在L中存在最大下界和最小上界,則(L,≤)是一個格。(從此定義可看出,其並不要求如全序集合般的每二元素可比性,但仍要求每二元素有最大下界和最小上界)

這裏對於取a,b的最大下界的操作用表示;

對於取a,b的最小上界操作用 表示。

有界格有一個最大元素和一個最小元素,按慣例分別指示為1和0(也叫做)。任何格都可以通過增加一個最大元素和最小元素而轉換成有界格。

使用容易的歸納論證,你可以演繹出任何格的所有非空有限子集的上確界(併)和下確界(交)的存在。一個很重要的格的種類是完全格。一個格是完全的,如果它的所有子集都有一個交和一個併,這對比於上述格的定義,這裏只要求所有非空有限子集的交和併的存在。

抽象代數定義

另一種定義格的方式是將格定義為一種代數結構。一個是一個代數結構,其中是定義在集合上的二元運算,且對於所有的滿足:

交換律
結合律
吸收律

從上述三個公理恆等式可以得出重要的:

冪等律

這些公理斷言了(L,)和(L,)都是半格。吸收律是唯一交和併都出現了的公理,把格同一對半格區別開來並確保這兩個半格正確的交互。特別是,每個半格都是另一個半格的對偶。「有界格」要求交和併都有一個零(neutral)元素,分別習慣叫做1和0。參見半格條目。

格與廣群家族有一些聯繫。因為交和併都符合交換律和結合律。格可以看作由有相同的承載者的兩個交換半群組成的。如果格是有界的,這些半群也是交換么半群吸收律是特定于格理論的唯一定義恆等式。

L 閉包於交和併之下,通過歸納,蘊涵了L的任何有限子集的交和併的存在性,有着一個例外:空集的交和併分別是最大元素和最小元素。所以格只在它是有界的條件下包含所有有限(包含空)交和併。為此有些作者定義格的時候要求0和1是L的成員。而以這種方式定義格不損失一般性,因為任何格都可以被嵌入一個有界格中,這裏不併受這種定義。

格的代數解釋在泛代數中扮演根本性角色。

兩個定義的等價性

格的代數定義蘊涵了序理論的定義,反之亦然。

明顯的,序理論的格引發了兩個二元運算。容易看出這些運算使(L, , )變成代數意義上的格。反之亦真:考慮代數定義的格(M, , )。現在定義在M上的偏序≤如下,對於M中的元素xy

xy 當且僅當x = xy

或等價的

xy當且僅當y = xy

吸收律確保了兩個定義實際上是等價的。你現在可以檢查以這種方式介入的關係≤定義了在其中二元交和併是通過最初運算而給出的一個偏序。反過來,由得出自上述序理論公式的代數定義的格(L, , )引發的次序一致於L的最初次序。

因為格的兩個定義是等價的,你可以隨意調用任何定義的適合你用的方面。

例子

  • 對於任何集合AA的所有子集的搜集(叫做A冪集)可以通過子集包含的次序獲得一個以A自身和空集為上下界的格。集合的交集併集分別解釋為交(meet)和併(join)。
  • 對於任何集合AA的所有有限子集的搜集,通過包含次序也是格,並且將是有界的當且僅當A是有限的。
  • 自然數(包括0)在「極小值」(min)和「極大值」(max)運算下,按照通常次序形成格。0是底,沒有頂。
  • 自然數的笛卡爾平方,按有隨後定義的≤排序是格,(a,b)≤(c,d)↔(ac) &(bd)。(0,0)是底;沒有頂。
  • 正整數在採用最大公因數最小公倍數運算之下,用整除作為次序關係也形成一個格:ab如果a整除b。底是1;沒有頂。
  • 任何完全格都是(非常特殊的)有界格。這個類別引出了大量實際例子。

格的態射

在兩個格之間的適當的態射概念可以輕易的同上述代數定義得出。給定兩個格(L, , )和(M, , ),格的同態是一個函數f : LM使得

f(xy) = f(x) f(y),
f(xy) = f(x) f(y)。

所以f是兩個底層半格同態。當考慮帶有更多結構的格的時候,這個態射也應當注意這個額外結構。所以在兩個有界格LM之間的態射f還有下列性質:

f(0L) = 0M
f(1L) = 1M

在序理論公式中,這些條件只聲稱格的同態是保持二元交和併的一個函數。對於有界格,最小和最大元素的保持只是空集的併和交的保持。

格的任何同態必然關於相關的次序關係是單調的;參見極限的保持。反過來當然不是真的:單調性決不蘊涵要求的保持性質。

假定同構作為可逆態射的標準定義,格的同構就是對射格同態。格和它們的態射形成了一個範疇

子格

L的子格是L的非空子集,它是帶有同L一樣的交和併運算的格。就是說,如果L是一個格,而ML的子集使得對於M中的所有元素對a, bababM中,則ML的子格。[2]

L的子格ML的凸子格,如果x ≤ z ≤ yx, yM中蘊涵了z屬於M,對於在L中的所有元素x, y, z

對偶原理

是含有格中的元素以及符號的邏輯命題,令是將中的替換為,將替換為,將替換為,將替換為後所得到的命題。則稱對偶命題

是含有格中的元素以及符號的邏輯命題,若對於一切格為真,則的對偶命題也對於一切格為真。

引用

可在線免費獲得的專著:

Elementary texts recommended for those with limited mathematical maturity:

  • Donnellan, Thomas, 1968. Lattice Theory. Pergamon.
  • Grätzer, G., 1971. Lattice Theory: First concepts and distributive lattices. W. H. Freeman.

The standard contemporary introductory text:

  • Davey, B.A., and H. A. Priestley, 2002. Introduction to Lattices and Order. Cambridge University Press.

The classic advanced monograph:

  • Garrett Birkhoff,1967. Lattice Theory, 3rd ed. Vol. 25 of American Mathematical Society Colloquium Publications. American Mathematical Society.

Free lattices are discussed in the following title, not primarily devoted to lattice theory:

  • Johnstone, P.T., 1982. Stone spaces. Cambridge Studies in Advanced Mathematics 3. Cambridge University Press.

The standard textbook on free lattices:

  • R. Freese, J. Jezek, and J. B. Nation, 1985. "Free Lattices". Mathematical Surveys and Monographs Volume: 42, American Mathematical Association.

參考文獻

參見

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.