伽罗瓦连接

维基百科,自由的百科全书
跳转至: 导航搜索

数学中,特别是在序理论中,伽罗瓦连接是在两个偏序集("poset")之间的特殊的对应。伽罗瓦连接一般化了伽罗瓦理论中在子群子域之间的对应。它们用于各种数学理论和编程理论中。

伽罗瓦连接要弱于在涉及到的两个偏序集之间的同构,但是所有的伽罗瓦连接都引发特定在两个子偏序集之间的同构。

定义[编辑]

假定 (A, ≤) 和 (B, <=) 是两个偏序集。在这些偏序集之间的伽罗瓦连接由两个单调[1]函数组成: F : A → BG : B → A, 使得对于所有的 A 中的 aB 中的 b,我们有

F(a) <= b 当且仅当 aG(b)。

在这种情况下,F 叫做 G下伴随,而 G 叫做 F上伴随。如下面详细讨论的那样,伽罗瓦连接每个部分唯一确定另外一个映射。把形成伽罗瓦连接的两个函数看作同一个对象的两个规定,把一对相应的下伴随和上伴随分别指示为 f f 是很方便的。注意在函数符号之上放置星号表示下伴随。使用这种表示重写上述定义,伽罗瓦连接连接是 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 的所有子域的集合,并按包含 \subseteq 排序。如果 E 是这样一个子域,把保持 E 固定的 L 的域自同构的群写为 Gal(L /E)。设 B 是 Gal(L /K) 的子群的集合,并按包含 \subseteq 排序。对于这样的一个子群 G,定义 Fix(G) 为由被 G 的所有元素保持固定的所有的 L 元素组成的域。则映射 E \mapsto Gal(L /E) 和 G \mapsto Fix(G) 形成了反序伽罗瓦连接。

序理论[编辑]

幂集[编辑]

给出序理论的一个例子,设 U 是某个集合,并设 AB 是按包含排序的 U幂集。选出 U 的一个固定子集 L。则映射 FG,这里的 F(M) 是 LM交集,而 G(N) 是 N差集 (U \ L) 的并集,形成了一个单调伽罗瓦连接,带有 F 是下伴随。在任何 Heyting代数中能找到其下伴随由(下确界)运算给出的类似的伽罗瓦连接。特别是,它存在于任何布尔代数中,这里的两个映射可以描述为 F(x) = (a \wedge x) 和 G(y) = (y \vee \neg a) = (a \Rightarrow y)。用逻辑术语说:“蕴涵是合取的上伴随”。

[编辑]

更有趣的伽罗瓦连接例子是在完备性性质文章中描述的伽罗瓦连接。它展示了平常的函数 \vee\wedge 是在两个合适的伽罗瓦连接中的伴随。对于从一个元素集合中指出一个偏序下的最小元素和最大元素的映射同样如此。进一步的说,甚至完全格可以用存在合适的伴随作为其特征。这些思考给出了伽罗瓦连接在序理论中无处不在的印象。

二元关系和零化子[编辑]

假设 XY 是任意集合并给出在 XY 之上的二元关系 R。对于任何 X 的子集 M,我们定义 F(M) = { y\in Y : mRy 对于所有 m\in M}。类似的,对于任何 Y 的子集 N,我们定义 G(N) = { x\in X : xRn 对于所有 n\in N}。则 FG 生成在 XY 的幂集之间的一个反序伽罗瓦连接,这两个集合都用集合包含 \subseteq 来排序。

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

像和逆像[编辑]

如果f : XY 是个函数,则对于任何 X 的子集 M 我们可以形成 F(M) = f(M) = {f(m) : m\in M},和对于任何 Y 的子集 N 我们可以形成逆像 G(N) = f -1(N) = {x\in X : f(x)\in N}。则 FG 形成了在 X 的幂集和 Y 的幂集之间的单调伽罗瓦连接,二者都用集合包含 \subseteq 来排序。在这种情况可有一个进一步的伴随对: 对于 X 的一个子集 M,定义 H(M) = {y\in Y : f -1({y}) \subseteq M}。则 GH 形成了在 Y 的幂集和 X 的幂集之间的单调伽罗瓦连接。在第一个伽罗瓦连接中,G 是上伴随,而在第二个伽罗瓦连接中它是下伴随。

在代数对象(比如群)之间的商映射的情况下,这种连接叫做格定理: G 的子群连接到 G/N 的子群,并且在 G 的子群上闭包运算给出为 \bar H = HN

扩张和闭包[编辑]

选取某个有底层集合的数学对象 X,比如、环、向量空间等。对于任何 X 的子集 S,设 F(S) 是 X 的包含 S 的最小子对象,就是说 S 所生成的子群子环子空间。对于任何 X 的子对象 U,设 G(U) 是 U 的底层集合。(我们甚至可以采用 X拓扑空间,设 F(S) 是 S闭包,并采用“X 的子对象”为 X 的闭合子集。) 现在 FG 形成单调伽罗瓦连接,如果集合和子对象按包含来排序。F 是下伴随。

性质[编辑]

下面我们考虑(单调)伽罗瓦连接连接 f = (f , f ),这里的 f : AB 是上面介绍的下伴随。可以立即得出一些有用处和有指导性的性质。通过伽罗瓦连接的定义性质,f (x) ≤ f (x) 等价于 xf ( f (x)),对于所有 A 中的 x。通过类似的推理(或简单的应用序理论的对偶性原理),可以得到 f ( f (y)) ≤ y,对于所有 B 中的 y。这些性质可以描述为复合的 f \circf 是“紧缩”的,而 f \circf 是“膨胀”的(或“扩张”的)。

现在如果考虑 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 \circf 是膨胀的。类似的,因为 f \circf 是紧缩的,可以发现

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

它等价于

f (f (f (x))) ≤ f (x).

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

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

就是说 f \circf 是幂等的。

闭包算子和伽罗瓦连接[编辑]

上述发现可总结如下: 对于伽罗瓦连接,复合的 f \circf 是单调的(因为是单调函数的复合),膨胀的,和幂等的。这声称了 f \circf 事实上是 A 上的闭包算子。对偶的说,f \circf 是单调的,紧缩的,和幂等的。这种映射有时叫做内核算子。在 frames 和 locales 的上下文中,复合的 f \circf 叫做 f 诱发的核子。核子诱发 frame 同态;locale 的子集叫做 sublocale 如果它给出自一个核子。

反过来说,在某个偏序集合 A 上的任何闭包算子 c 都引发一个伽罗瓦连接,其下伴随为 f ,它就是 cc 的像的陪限制(corestriction)(就是说作为满射映射闭包系统 c(A))。 上伴随 f 给出自包含 c(A) 到 A 之中,它映射每个闭合元素到自身,被当作 A 的一个元素。在这种方式下,闭包算子和伽罗瓦连接被看作是密切关联的,每个都指定另一个的实例。类似的结论对于核心算子也成立。

上述思考还证明了 A 的闭合元素(元素 x 带有 f (f (x)) = x)被映射到在核心算子 f \circ f 值域内的一个元素,反之亦然。

伽罗瓦连接的存在性和唯一性[编辑]

伽罗瓦连接的另一个重要性质是下伴随保持在它们的定义域内存在的所有上确界。对偶的说,上伴随保持所有存在的下确界。从这些性质,我们可立即推论出伴随的单调性。伴随函子定理声称在特定情况下反蕴涵也是有效的: 特别是,在完全格之间的任何保持所有上确界的映射都是伽罗瓦连接的下伴随。

在这种情况下,伽罗瓦连接的一个重要特征就是一个伴随唯一的确定另一个。因此我们可以强化上述陈述来保证在完全格之间的任何保持上确界的映射都是一个唯一的伽罗瓦连接的下伴随。导出这个唯一性的主要性质为如下: 对于所有 Axf (x) 是 B 中最小的元素 y 使得 xf (y)。对偶的说,对于所有 B 中的 yf (y) 是 A 中最大的元素 x 使得 f (x) ≤ y。特定伽罗瓦连接的存在升年个现在分别蕴涵了最小和最大元素的存在性,不管对应的偏序集合是否满足任何完备性性质。因此,在给出一个伽罗瓦连接的一个伴随,另一个可以通过这个性质来定义。换句话说,某个任意函数 f 是下 伴随,当且仅当 形如 { x in A | 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