Галуа-связи: теория и приложения в теории порядка

Введение

Особое соответствие между двумя частично упорядоченными множествами
В математике, особенно в теории порядка, связь Галуа — это особое соответствие (как правило) между двумя частично упорядоченными множествами (посетами). Связи Галуа находят применение в различных математических теориях. Они обобщают фундаментальную теорему теории Галуа о соответствии между подгруппами и подполями, открытую французским математиком Эваристом Галуа. Связь Галуа также может быть определена для предварительно упорядоченных множеств или классов; в данной статье рассматривается общий случай посет. В литературе существует два тесно связанных понятия "связи Галуа". В этой статье мы будем обозначать их как (монотонные) связи Галуа и антитонные связи Галуа. Связь Галуа является относительно слабой по сравнению с изоморфизмом порядка между рассматриваемыми посетами, но каждая связь Галуа порождает изоморфизм определенных подпосетов, что будет объяснено ниже. Термин "соответствие Галуа" иногда используется для обозначения биективной связи Галуа; это просто изоморфизм порядка (или двойной изоморфизм порядка, в зависимости от того, используются монотонные или антитонные связи Галуа).

Пристрастия

Биекция между парой функций и их взаимно обратными формирует (тривиальное) галуа-сопряжение, а именно: поскольку отношение равенства рефлексивно, транзитивно и антисимметрично, оно тривиально является отношением частичного порядка, что делает и частично упорядоченными множествами. Поскольку если и только если , мы имеем галуа-сопряжение.

Набор мощности; последствия и сочетание

Для примера из теории порядка, пусть U – некоторое множество, а A и B – оба являющиеся множеством степеней U, упорядоченными по включению. Выберем фиксированное подмножество L из U. Тогда отображения F и G, где , и , образуют монотонное галуа-сопряжение, при этом F является нижним сопряженным. Аналогичное галуа-сопряжение, нижний сопряженный которого задается операцией meet (инфимум), можно найти в любой алгебре Гейтинга. В частности, оно присутствует в любой булевой алгебре, где эти два отображения можно описать как и . В логических терминах: "импликация из a" является верхним сопряженным "конъюнкции с a".

Решетки

Другие интересные примеры соединений Галуа описаны в статье о свойствах полноты. Грубо говоря, оказывается, что обычные функции ∨ и ∧ являются нижним и верхним сопряженными к диагональному отображению X → X × X. Наименьший и наибольший элементы частичного порядка задаются нижним и верхним сопряженными к единственной функции X → {1}. Более того, даже полные решетки можно характеризовать существованием подходящих сопряженных. Эти соображения дают представление об универсальности соединений Галуа в теории порядка.

Изображение и обратное изображение

Если f : X → Y — функция, то для любого подмножества M из X можно сформировать образ, а для любого подмножества N из Y — прообраз. Тогда F и G образуют монотонное галуа-сопряжение между множеством степеней X и множеством степеней Y, упорядоченных включением ⊆. В этой ситуации существует еще одна сопряженная пара: для подмножества M из X определим . Тогда G и H образуют монотонное галуа-сопряжение между множеством степеней Y и множеством степеней X. В первом галуа-сопряжении G является верхним сопряженным, а во втором — нижним сопряженным. В случае факторного отображения между алгебраическими объектами (такими как группы) это сопряжение называется теоремой о решетке: подгруппы G сопоставляются с подгруппами G/N, а оператор замыкания для подгрупп G задается .

Размах и закрытие

Выберите какой-нибудь математический объект X, имеющий базовое множество, например группу, кольцо, векторное пространство и т.д. Для любого подмножества S из X, пусть F(S) будет наименьшим подобъектом X, содержащим S, то есть подгруппой, подкольцом или подпространством, порожденным S. Для любого подобъекта U из X, пусть G(U) будет базовым множеством U. (Можно даже взять X за топологическое пространство, определить F(S) как замыкание S и считать "подобъектами X" замкнутыми подмножествами X.) Тогда F и G образуют монотонное галуа-сопряжение между подмножествами X и подобъектами X, если оба упорядочены по включению. F является нижним сопряжением.

Синтаксис и семантика

Очень общий комментарий Уильяма Лоувера заключается в том, что синтаксис и семантика являются сопряженными: пусть A – множество всех логических теорий (аксиоматизаций), упорядоченное в обратном порядке по силе, а B – булеан (или степенное) множество множества всех математических структур. Для теории T ∈ A обозначим Mod(T) множество всех структур, удовлетворяющих аксиомам T; для множества математических структур S ∈ B обозначим Th(S) минимальную аксиоматизацию, аппроксимирующую S (в логике первого порядка это множество предложений, истинных во всех структурах из S). Тогда можно сказать, что S является подмножеством Mod(T) тогда и только тогда, когда Th(S) логически влечет T: "семантический функтор" Mod и "синтаксический функтор" Th образуют монотонное галуа-сопряжение, при этом семантика является верхним сопряжением.

Теория Галуа

Мотивирующий пример взят из теории Галуа: предположим, что L/K – расширение полей. Пусть A – множество всех подполей L, содержащих K, упорядоченное по включению ⊆. Если E – такое подполе, обозначим Gal(L/E) группой полевых автоморфизмов L, фиксирующих E. Пусть B – множество подгрупп Gal(L/K), упорядоченное по включению ⊆. Для такой подгруппы G определим Fix(G) как поле, состоящее из всех элементов L, фиксируемых всеми элементами G. Тогда отображения и образуют антитоновую связь Галуа.

Алгебраическая топология: охватывает пространства

Аналогично, для связного по пути топологического пространства X существует антитональное соответствие Галуа между подгруппами фундаментальной группы π1(X) и связными по пути накрывающими пространствами X. В частности, если X полулокально односвязно, то для каждой подгруппы G группы π1(X) существует накрывающее пространство, фундаментальной группой которого является G.

Линейная алгебра: аннигиляторы и ортогональные комплементы

Для заданного пространства с внутренним произведением V можно построить ортогональное дополнение F(X) любого подпространства X пространства V. Это определяет антитоновую связь Галуа между множеством подпространств V и самим собой, упорядоченным по включению, причём обе полярности равны F.

Для заданного векторного пространства V и подмножества X пространства V можно определить его аннигилятор F(X), состоящий из всех элементов двойственного пространства V* пространства V, которые обращаются в нуль на X. Аналогично, для заданного подмножества Y пространства V* можно определить его аннигилятор. Это определяет антитоновую связь Галуа между подмножествами V и подмножествами V*.

Алгебраическая геометрия

В алгебраической геометрии связь между множествами многочленов и их множествами нулей является антитоновой связью Галуа. Зафиксируем натуральное число n и поле K, и пусть A будет множеством всех подмножеств кольца многочленов K[X1, …, Xn], упорядоченных включением ⊆, а B – множеством всех подмножеств Kⁿ, также упорядоченных включением ⊆. Если S – множество многочленов, определим множество нулей как множество общих нулей многочленов из S. Если U – подмножество Kⁿ, определим I(U) как идеал многочленов, обращающихся в нуль на U, то есть

Тогда V и I образуют антитоновую связь Галуа. Замыкание на Kⁿ является замыканием в топологии Зариски, и если поле K алгебраически замкнуто, то замыкание на кольце многочленов является радикалом идеала, порожденного S.

В более общем случае, для коммутативного кольца R (не обязательно кольца многочленов), существует антитоновая связь Галуа между радикальными идеалами в кольце и замкнутыми подмножествами Зариски аффинного многообразия. В еще более общем случае, существует антитоновая связь Галуа между идеалами в кольце и подсхемами соответствующего аффинного многообразия.

Соединения на наборах мощностей, возникающие из бинарных отношений

Предположим, что X и Y – произвольные множества, и задано бинарное отношение R между X и Y. Для любого подмножества M множества X мы определяем Аналогично, для любого подмножества N множества Y мы определяем Тогда F и G образуют антитоновую связь Галуа между множествами степеней X и Y, упорядоченными включением ⊆. С точностью до изоморфизма все антитоновые связи Галуа между множествами степеней возникают таким образом. Это следует из "Основной теоремы о концептуальных решетках". Теория и применение связей Галуа, возникающих из бинарных отношений, изучаются в формальном концептуальном анализе. Эта область использует связи Галуа для математического анализа данных. Многие алгоритмы для связей Галуа можно найти в соответствующей литературе, например, в. Общая концептуальная решетка в своей первоначальной версии включает в себя как монотонные, так и антитоновые связи Галуа для определения верхней и нижней границ узлов концептуальной решетки соответственно.

Операторы закрытия и соединения Galois

Вышеуказанные выводы можно суммировать следующим образом: для связи Галуа композиция f∗∘f^(∗) является монотонной (как композиция монотонных функций), инфляционной и идемпотентной. Это означает, что f∗∘f^(∗) фактически является оператором замыкания на A. Двойственно, f^(∗)∘f∗ является монотонной, дефляционной и идемпотентной. Такие отображения иногда называют операторами ядра. В контексте фреймов и локалей композиция f∗∘f^(∗) называется ядром, индуцированным f. Ядра индуцируют гомоморфизмы фреймов; подмножество локали называется сублокалью, если оно задается ядром. И наоборот, любой оператор замыкания c на некотором частично упорядоченном множестве A порождает связь Галуа, при которой нижнее сопряжение f^(∗) является просто ограничением c к образу c (то есть как сюръективное отображение системы замыканий c(A)). Верхнее сопряжение f∗ тогда задается включением c(A) в A, которое отображает каждый замкнутый элемент в самого себя, рассматриваемый как элемент A. Таким образом, операторы замыкания и связи Галуа тесно связаны, каждый из которых определяет конкретный случай другого. Аналогичные заключения справедливы и для операторов ядра. Вышесказанное также показывает, что замкнутые элементы A (элементы x с ) отображаются в элементы в области значений оператора ядра f^(∗)∘f∗, и наоборот.

Существование и уникальность связей Галуа

Еще одно важное свойство галлоисовских связей заключается в том, что нижние адъюнкты сохраняют все супремумы, существующие в их области определения. Двойственно, верхние адъюнкты сохраняют все существующие инфимумы. Из этих свойств непосредственно следует монотонность адъюнктов. Теорема о присоединенных функторах в теории порядка утверждает, что обратное утверждение также верно в определенных случаях: в частности, любое отображение между полными решетками, сохраняющее все супремумы, является нижним адъюнктом связи Галуа. В этой ситуации важной особенностью связей Галуа является то, что один адъюнкт однозначно определяет другой. Следовательно, можно усилить вышеуказанное утверждение, гарантируя, что любое сохраняющее супремум отображение между полными решетками является нижним адъюнктом единственной связи Галуа. Основное свойство, обеспечивающее эту единственность, заключается в следующем: для каждого x из A, f*(x) является наименьшим элементом y из B, таким что x ≤ f(y). Двойственно, для каждого y из B, f(y) является наибольшим элементом x из A, таким что f*(x) ≤ y. Существование определенной связи Галуа теперь подразумевает существование соответствующих наименьших или наибольших элементов, независимо от того, обладают ли соответствующие частично упорядоченные множества какими-либо свойствами полноты. Таким образом, если задан один верхний адъюнкт связи Галуа, то другой верхний адъюнкт можно определить, используя это же свойство. С другой стороны, монотонная функция f является нижним адъюнктом тогда и только тогда, когда для каждого b из B множество {x | f(x) ≤ b} содержит наибольший элемент. Аналогично, это можно двойственно сформулировать для верхнего адъюнкта.

Связи Галуа как морфизмы

Соединения Галуа также предоставляют интересный класс отображений между частично упорядоченными множествами, которые можно использовать для получения категорий частично упорядоченных множеств. В частности, можно композировать соединения Галуа: даны соединения Галуа (f^(∗), f∗) между частично упорядоченными множествами A и B и (g^(∗), g∗) между B и C, композиция (g^(∗) ∘ f^(∗), f∗ ∘ g∗) также является соединением Галуа. При рассмотрении категорий полных решеток это можно упростить до рассмотрения только отображений, сохраняющих все супремумы (или, альтернативно, инфимумы). Отображая полные решетки в их дуальные, эти категории демонстрируют автодуальность, которая является фундаментальной для получения других теорем о дуальности. Более специальные типы морфизмов, индуцирующих сопряженные отображения в обратном направлении, обычно рассматриваются для фреймов (или локалей).

Связь с теорией категорий

Каждое частично упорядоченное множество можно естественным образом рассматривать как категорию: существует единственный морфизм из x в y тогда и только тогда, когда x ≤ y. Монотонное соответствие Галуа, таким образом, является лишь парой сопряженных функторов между двумя категориями, порожденными частично упорядоченными множествами. В этом контексте верхнее сопряжение является правым сопряжением, а нижнее сопряжение – левым сопряжением. Однако эта терминология избегается применительно к соответствиям Галуа, поскольку в прошлом позиты преобразовывались в категории двойственным образом, то есть морфизмы были направлены в противоположную сторону. Это привело к дополнительной нотации для левых и правых сопряжений, которая сегодня является неоднозначной.

Применение в теории программирования

Связи Галуа могут быть использованы для описания различных форм абстракции в теории абстрактной интерпретации языков программирования.