伽罗瓦连接

数学中,特别是在序理论中,伽罗瓦连接是在两个偏序集("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) = { yY : mRy对于所有mM}。类似的,对于任何Y的子集N,我们定义G(N) = { xX : xRn对于所有nN}。则FG生成在XY的幂集之间的一个反序伽罗瓦连接,这两个集合都用集合包含来排序。

线性代数中的一个重要的特殊情况是零化子(annihilator),它包括了正交补作为特殊情况。

像和逆像

如果f : XY是个函数,则对于任何X的子集M我们可以形成F(M) = f(M) = {f(m) : mM},和对于任何Y的子集N我们可以形成逆像G(N) = f -1(N) = {xX : f(x)N}。则FG形成了在X的幂集和Y的幂集之间的单调伽罗瓦连接,二者都用集合包含来排序。在这种情况可有一个进一步的伴随对:对于X的一个子集M,定义H(M) = {yY : 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。这些性质可以描述为复合的ff是“紧缩”的,而ff是“膨胀”的(或“扩张”的)。

现在如果考虑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)

因为ff是膨胀的。类似的,因为ff是紧缩的,可以发现

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

它等价于

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

这证明了想要的相等性。进一步的,我们使用这个性质推论出

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

就是说ff是幂等的。

闭包算子和伽罗瓦连接

上述发现可总结如下:对于伽罗瓦连接,复合的ff是单调的(因为是单调函数的复合),膨胀的,和幂等的。这声称了ff事实上是A上的闭包算子。对偶的说,ff是单调的,紧缩的,和幂等的。这种映射有时叫做内核算子。在frames和locales的上下文中,复合的ff叫做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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.