伽羅瓦連接

兩個部分有序集合(偏序集)之間的特定對應關係(通常)

數學中,特別是在序理論中,伽羅瓦連接是在兩個偏序集("poset")之間的特殊的對應。伽羅瓦連接一般化了伽羅瓦理論中在子群子體之間的對應。它們用於各種數學理論和編程理論中。

伽羅瓦連接要弱於在涉及到的兩個偏序集之間的同構,但是所有的伽羅瓦連接都引發特定在兩個子偏序集之間的同構。

定義

編輯

假定(A, ≤)和(B, <=)是兩個偏序集。在這些偏序集之間的伽羅瓦連接由兩個單調[1]函數組成:F : A → BG : B → A,使得對於所有的A中的aB中的b,我們有

F(a)<= b當且僅當aG(b)。

在這種情況下,F叫做G下伴隨,而G叫做F上伴隨。如下面詳細討論的那樣,伽羅瓦連接每個部分唯一確定另外一個映射。把形成伽羅瓦連接的兩個函數看作同一個物件的兩個規定,把一對相應的下伴隨和上伴隨分別指示為ff是很方便的。注意在函數符號之上放置星號表示下伴隨。使用這種表示重寫上述定義,伽羅瓦連接是f =(f, f),使得對於所有的A中的aB中的b,我們有

f(a)<= b當且僅當af(b)。

可供選擇的定義

編輯

上述定義常用於很多今天的應用中,特別是在格理論域理論中。最初從伽羅瓦理論中引出的是一個稍微不同的概念。在這個可供選擇的定義中,伽羅瓦連接是在兩個偏序集合AB之間的一對反序(就是說次序倒轉)函數F : A → BG : B → A,使得

bF(a) 當且僅當aG(b)。

伽羅瓦連接的這兩個概念都存在於文獻中。在這裏,術語(單調)伽羅瓦連接將總是稱謂前者意義的伽羅瓦連接。在應用這個可供選擇的定義,則使用術語反序伽羅瓦連接次序倒轉伽羅瓦連接

兩個定義的蘊涵在事實上是非常類似的,因為在AB之間的反序伽羅瓦連接就是在AB序對偶Bop之間的單調伽羅瓦連接。在後面關於伽羅瓦連接的陳述都可以輕易的轉換成關於反序伽羅瓦連接的稱述。

但是要注意對於反序伽羅瓦連接,談論下伴隨和上伴隨是沒有意義的:情況是完全對稱的。

例子

編輯

伽羅瓦理論

編輯

激發伽羅瓦連接的例子來自伽羅瓦理論:假設L /K體擴張。設AL的包含K的所有子體的集合,並按包含 排序。如果E是這樣一個子體,把保持E固定的L的域自同構的群寫為Gal(L /E)。設B是Gal(L /K)的子群的集合,並按包含 排序。對於這樣的一個子群G,定義Fix(G)為由被G的所有元素保持固定的所有的L元素組成的域。則映射E   Gal(L /E)和G   Fix(G)形成了反序伽羅瓦連接。

序理論

編輯

冪集

編輯

給出序理論的一個例子,設U是某個集合,並設AB是按包含排序的U冪集。選出U的一個固定子集L。則映射FG,這裏的F(M)是LM交集,而G(N)是N差集(U \ L)的併集,形成了一個單調伽羅瓦連接,帶有F是下伴隨。在任何Heyting代數中能找到其下伴隨由下確界)運算給出的類似的伽羅瓦連接。特別是,它存在於任何布林代數中,這裏的兩個映射可以描述為F(x) =(a   x)和G(y) =(y     a) =(a   y)。用邏輯術語說:「蘊涵是合取的上伴隨」。

更有趣的伽羅瓦連接例子是在完備性性質文章中描述的伽羅瓦連接。它展示了平常的函數  是在兩個合適的伽羅瓦連接中的伴隨。對於從一個元素集合中指出一個偏序下的最小元素和最大元素的映射同樣如此。進一步的說,甚至完全格可以用存在合適的伴隨作為其特徵。這些思考給出了伽羅瓦連接在序理論中無處不在的印象。

二元關係和零化子

編輯

假設XY是任意集合併給出在XY之上的二元關係R。對於任何X的子集M,我們定義F(M) = { y Y : mRy對於所有m M}。類似的,對於任何Y的子集N,我們定義G(N) = { x X : xRn對於所有n N}。則FG生成在XY的冪集之間的一個反序伽羅瓦連接,這兩個集合都用集合包含 來排序。

線性代數中的一個重要的特殊情況是零化子(annihilator),它包括了正交補餘作為特殊情況。

像和逆像

編輯

如果f : XY是個函數,則對於任何X的子集M我們可以形成F(M) = f(M) = {f(m) : m M},和對於任何Y的子集N我們可以形成逆像G(N) = f -1(N) = {x X : f(x) N}。則FG形成了在X的冪集和Y的冪集之間的單調伽羅瓦連接,二者都用集合包含 來排序。在這種情況可有一個進一步的伴隨對:對於X的一個子集M,定義H(M) = {y Y : f -1({y})   M}。則GH形成了在Y的冪集和X的冪集之間的單調伽羅瓦連接。在第一個伽羅瓦連接中,G是上伴隨,而在第二個伽羅瓦連接中它是下伴隨。

在代數物件(比如群)之間的商映射的情況下,這種連接叫做格定理G的子群連接到G/N的子群,並且在G的子群上閉包運算給出為 

擴張和閉包

編輯

選取某個有底層集合的數學物件X,比如、環、向量空間等。對於任何X的子集S,設F(S)是X的包含S的最小子物件,就是說S所生成的子群子環子空間。對於任何X的子物件U,設G(U)是U的底層集合。(我們甚至可以採用X拓撲空間,設F(S)是S閉包,並採用「X的子物件」為X的閉合子集。)現在FG形成單調伽羅瓦連接,如果集合和子物件按包含來排序。F是下伴隨。

覆疊空間

編輯

代數拓撲學中,一個路徑連通的空間X若有路徑連通的覆疊空間U,則U基本群 會是X的基本群 的子群。因此由X的所有覆疊空間所形成的偏序集,與X的基本群的所有子群形成的偏序集之間,形成了反序伽羅瓦連接。更進一步的,對於X的萬有覆疊空間,其基本群必為 

性質

編輯

下面我們考慮(單調)伽羅瓦連接連接f =(f, f),這裏的f: AB是上面介紹的下伴隨。可以立即得出一些有用處和有指導性的性質。通過伽羅瓦連接的定義性質,f(x)≤ f(x)等價於xf(f(x)),對於所有A中的x。通過類似的推理(或簡單的應用序理論的對偶性原理),可以得到f(f(y)) ≤ y,對於所有B中的y。這些性質可以描述為複合的f f是「緊縮」的,而f f是「膨脹」的(或「擴張」的)。

現在如果考慮A的任何元素xy使得xy,則可以明確的上述性質來得到 xf(f(y))。應用伽羅瓦連接的基本性質,可以推論出f(x)≤ f(y)。但是這隻證明了f保持了任何兩個元素的次序,就是說它是單調的。還有,類似的推理產生了f的單調性。所以單調性不必須明確的包含在定義中。但是提及單調性有助於避免混淆伽羅瓦連接的兩個可選擇的定義。

伽羅瓦連接的另一個基本形式是f(f(f(x))) = f(x),對於所有B中的x。我們明顯的可發現

f(f(f(x))) ≥ f(x)

因為f f是膨脹的。類似的,因為f f是緊縮的,可以發現

f f f f(x) ≤ f f(x)≤ x,

它等價於

f(f(f(x))) ≤ f(x)。

這證明了想要的相等性。進一步的,我們使用這個性質推論出

f(f(f(f(x)))) = f(f(x)),

就是說f f是冪等的。

閉包算子和伽羅瓦連接

編輯

上述發現可總結如下:對於伽羅瓦連接,複合的f f是單調的(因為是單調函數的複合),膨脹的,和冪等的。這聲稱了f f事實上是A上的閉包算子。對偶的說,f f是單調的,緊縮的,和冪等的。這種映射有時叫做內核算子。在frames和locales的上下文中,複合的f f叫做f誘發的核子。核子誘發frame同態;locale的子集叫做sublocale如果它給出自一個核子。

反過來說,在某個偏序集合A上的任何閉包算子c都引發一個伽羅瓦連接,其下伴隨為f,它就是cc的像的陪限制(corestriction,就是說作為滿射映射閉包系統c(A))。上伴隨f給出自包含c(A)到A之中,它映射每個閉合元素到自身,被當作A的一個元素。在這種方式下,閉包算子和伽羅瓦連接被看作是密切關聯的,每個都指定另一個的實例。類似的結論對於核心算子也成立。

上述思考還證明了A的閉合元素(元素x帶有f(f(x)) = x)被映射到在核心算子f   f值域內的一個元素,反之亦然。

伽羅瓦連接的存在性和唯一性

編輯

伽羅瓦連接的另一個重要性質是下伴隨保持在它們的定義域內存在的所有上確界。對偶的說,上伴隨保持所有存在的下確界。從這些性質,我們可立即推論出伴隨的單調性。伴隨函子定理聲稱在特定情況下反蘊涵也是有效的:特別是,在完全格之間的任何保持所有上確界的映射都是伽羅瓦連接的下伴隨。

在這種情況下,伽羅瓦連接的一個重要特徵就是一個伴隨唯一的確定另一個。因此我們可以強化上述陳述來保證在完全格之間的任何保持上確界的映射都是一個唯一的伽羅瓦連接的下伴隨。導出這個唯一性的主要性質為如下:對於所有Axf(x)是B中最小的元素y使得xf(y)。對偶的說,對於所有B中的yf(y)是A中最大的元素x使得f(x)≤ y。特定伽羅瓦連接的存在升年個現在分別蘊涵了最小和最大元素的存在性,不管對應的偏序集合是否滿足任何完備性性質。因此,在給出一個伽羅瓦連接的一個伴隨,另一個可以通過這個性質來定義。換句話說,某個任意函數f是下伴隨,當且僅當形如{ xA | f(x)≤ b, bB}的每個集合都包含最大元素。還有,這可對偶化到上伴隨。

在編程理論中的應用

編輯

伽羅瓦連接在程式語言抽象釋義理論中可被用於描述多種形式的抽象。

註釋

編輯
  1. ^ 單調性可以從下面的條件得出。參見性質章節的討論。明確出現在定義中是為了區別於可供選擇的「反序」定義。你還可以定義伽羅瓦連接為滿足如下鬆散條件的一對單調函數,對於所有A中x有x ≤ g(f (x))並且對於所有B中的y有f(g (y)) ≤ y。

引用

編輯

A freely available introduction to Galois connections, presenting many examples and results. Also includes notes on the different notations and definitions that arose in this area:

  • M. Erné, J. Koslowski, A. Melton, G. E. Strecker, A primer on Galois connections, in: Proceedings of the 1991 Summer Conference on General Topology and Applications in Honor of Mary Ellen Rudin and Her Work, Annals of the New York Academy of Sciences, Vol. 704, 1993, pp. 103-125. Available online in various file formats: PS.GZ頁面存檔備份,存於互聯網檔案館PS頁面存檔備份,存於互聯網檔案館

The following standard reference books also include Galois connections using modern notation and definitions:

  • B. A. Davey and H. A. Priestley: Introduction to lattices and Order, Cambridge University Press, 2002.
  • G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, D. S. Scott: Continuous Lattices and Domains, Cambridge University Press, 2003.

Finally, some publications using the original (antitone) definition:

  • Garrett Birkhoff: Lattice Theory, Amer. Math. Soc. Coll. Pub., Vol 25, 1940
  • Oystein Ore: Galois Connexions, Transactions of the American Mathematical Society 55 (1944), pp. 493-513