Связь Галуа - Galois connection

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

Связь Галуа довольно слабая по сравнению с изоморфизм порядка между задействованными подмножествами, но каждая связь Галуа приводит к изоморфизму определенных подмножеств, как будет объяснено ниже.

В литературе встречаются два тесно связанных понятия «связь Галуа». В этой статье мы проведем различие между ними, обозначив первый как (монотонно) Связь Галуа а ко второму как антитонная связь Галуа.

Период, термин Переписка Галуа иногда используется для обозначения биективный Связь Галуа; это просто изоморфизм порядка (или изоморфизм двойственного порядка, в зависимости от того, возьмем ли мы монотонные или антитонные связи Галуа).

Определения

(Монотонный) Связь Галуа

Позволять (А, ≤) и (B, ≤) быть двумя частично упорядоченные наборы. А монотонная связь Галуа между этими посетами состоит из двух монотонный[1] функции: F : А → B и г : B → А, так что для всех а в А и б в B, у нас есть

F(а) ≤ б если и только если а ≤ г(б).

В этой ситуации, F называется нижний примыкающий из г и г называется верхний прилегающий из F. Мнемонически верхняя / нижняя терминология относится к тому, где приложение функции отображается относительно ≤.[2] Термин «сопряженный» относится к тому факту, что монотонные связности Галуа являются частными случаями пар присоединенные функторы в теория категорий как обсуждается ниже. Другая встречающаяся здесь терминология левый смежный (соответственно правый смежный) для нижнего (соответственно верхнего) сопряженного.

Существенным свойством связности Галуа является то, что верхний / нижний сопряженный к связности Галуа однозначно определяет другое:

F(а) наименьший элемент ~б с участием а ≤ г(~б), и
г(б) это самый большой элемент ~а с участием F(~а) ≤ б.

Следствием этого является то, что если F или г является обратимый, то каждый является обратный другого, т.е. F = г −1 .

Учитывая связь Галуа с нижним сопряженным F и верхний прилегающий г, можно рассматривать составы GF : А → А, известный как связанный оператор закрытия, и FG : B → B, известный как связанный оператор ядра. Оба монотонны и идемпотентны, и мы имеем а ≤ GF(а) для всех а в А и FG(б) ≤ б для всех б в B.

А Вставка Галуа из B в А является связностью Галуа, в которой оператор ядра FG это личность на B, и, следовательно г является изоморфизмом порядка B на закрытые множества GF[А] из А.[3]

Антитоне Галуа связь

Вышеприведенное определение сегодня широко используется во многих приложениях и заметно в решетка и теория предметной области. Однако исходное понятие в теории Галуа немного отличается. В этом альтернативном определении связь Галуа - это пара антитон, то есть с изменением порядка, функции F : А → B и г : B → А между двумя посетами А и B, так что

б ≤ F(а) если и только если а ≤ г(б).

Симметрия F и г в этой версии стирается различие между верхним и нижним, и затем вызываются две функции полярности а не примыкает.[4] Каждая полярность однозначно определяет другую, поскольку

F(а) это самый большой элемент б с участием а ≤ г(б), и
г(б) это самый большой элемент а с участием б ≤ F(а).

Композиции GF : А → А и FG : B → B - ассоциированные операторы замыкания; они являются монотонными идемпотентными отображениями со свойством а ≤ GF(а) для всех а в А и б ≤ FG(б) для всех б в B.

Смыслы двух определений связей Галуа очень похожи, поскольку антитонная связь Галуа между А и B это просто монотонная связь Галуа между А и заказ двойной Bop из B. Таким образом, все приведенные ниже утверждения о связях Галуа можно легко преобразовать в утверждения о антитонных связях Галуа.

Примеры

Монотонные связи Галуа

Силовой набор; импликация и союз

Для примера теории порядка пусть U быть некоторыми набор, и разреши А и B оба будут набор мощности из U, заказанный включением. Выберите фиксированное подмножество L из U. Тогда карты F и г, где F(M) = L ∩ M, и г(N) = N ∪ (U \ L), образуют монотонную связь Галуа, с F будучи нижним сопряженным. Аналогичную связность Галуа, нижнее сопряжение которой задается операцией встречи (инфимума), можно найти в любом Алгебра Гейтинга. Тем более, что он присутствует в любом Булева алгебра, где два отображения можно описать как F(Икс) = (а ∧ Икс) и г(у) = (у ∨ ¬а) = (а ⇒ у). Говоря логически: "следствие из а"является верхним соединением" в сочетании с а".

Решетки

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

Переходные групповые действия

Позволять г действовать переходно на Икс и выберите какую-нибудь точку Икс в Икс. Рассматривать

набор блоки содержащий Икс. Далее, пусть состоят из подгрупп г содержащий стабилизатор из Икс.

Тогда переписка :

является монотонной взаимно однозначной связностью Галуа.[5] Как следствие, можно установить, что двояко-транзитивные действия не имеют блоков, кроме тривиальных (одиночных или целых Икс): это следует из того, что стабилизаторы максимальны по г в этом случае. Увидеть дважды транзитивная группа для дальнейшего обсуждения.

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

Если  ж  : Икс → Y это функция, то для любого подмножества M из Икс мы можем сформировать изображение F(M) =  ж (M) = {ж(м) | м ∈ M} и для любого подмножества N из Y мы можем сформировать обратное изображение г(N) =  ж −1(N) = {Икс ∈ Икс |  ж (Икс) ∈ N}. потом F и г образуют монотонную связь Галуа между степенным набором Икс и набор мощности Y, оба упорядочены включением ⊆. В этой ситуации есть еще одна сопряженная пара: для подмножества M из Икс, определить ЧАС(M) = {у ∈ Y |  ж −1({у}) ⊆ M}. потом г и ЧАС образуют монотонную связь Галуа между степенным набором Y и набор мощности Икс. В первой связи Галуа г является верхним сопряженным, а во второй связности Галуа - нижним сопряженным.

В случае факторная карта между алгебраическими объектами (например, группами) эта связь называется решеточная теорема: подгруппы г подключаться к подгруппам г/N, а оператор замыкания на подгруппах г дан кем-то ЧАС = HN.

Пролет и закрытие

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

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

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

Связи Antitone Galois

Теория Галуа

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

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

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

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

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

Учитывая векторное пространство V и подмножество Икс из V мы можем определить его аннигилятор F(Икс), состоящий из всех элементов двойное пространство V ∗ из V которые исчезают на Икс. Аналогично, учитывая подмножество Y из V ∗, определим его аннигилятор г(Y) = {Икс ∈ V | φ(Икс) = 0 ∀φ ∈ Y}. Это дает антитонную связь Галуа между подмножествами V и подмножества V ∗.

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

В алгебраическая геометрия, связь между множествами многочлены и их нулевые множества являются антитонной связностью Галуа.

Исправить натуральное число п и поле K и разреши А - множество всех подмножеств кольцо многочленов K[Икс1, ..., Иксп] упорядочен по включению ⊆, и пусть B - множество всех подмножеств Kп упорядочено включением ⊆. Если S набор многочленов, определим разнообразие нулей как

множество общих нулей многочленов от S. Если U это подмножество Kп, определить я(U) как идеал многочленов, исчезающих на U, это

потом V и я образуют антитонную связь Галуа.

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

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

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

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

Предположим Икс и Y произвольные множества и a бинарное отношение р над Икс и Y дано. Для любого подмножества M из Икс, мы определяем F(M) = {у ∈ Y | мРу ∀м ∈ M}. Аналогично для любого подмножества N из Y, определить г(N) = {Икс ∈ Икс | xRn ∀п ∈ N}. потом F и г дают антитонную связь Галуа между наборами власти Икс и Y, оба упорядочены включением ⊆. [7]

С точностью до изоморфизма все Таким образом возникают антитонные связи Галуа между наборами власти. Это следует из «Основной теоремы о решетках понятий».[8] Теория и приложения связностей Галуа, возникающих из бинарных отношений, изучаются в формальный анализ концепции. Это поле использует связи Галуа для математического анализа данных. Многие алгоритмы для соединений Галуа можно найти в соответствующей литературе, например, в.[9]

Свойства

Далее мы рассматриваем (монотонную) связность Галуа  ж  = ( ж ∗,  ж∗), где  ж ∗ : А → B является нижним сопряженным, как введено выше. Некоторые полезные и поучительные основные свойства могут быть получены немедленно. По определяющему свойству связностей Галуа  ж ∗(Икс) ≤  ж ∗(Икс) эквивалентно Икс ≤  ж∗( ж ∗(Икс)), для всех Икс в А. По аналогичным соображениям (или просто применяя принцип двойственности для теории порядка ), оказывается, что  ж ∗( ж∗(у)) ≤ у, для всех у в B. Эти свойства можно описать, сказав составной  ж ∗ ∘  ж∗ является дефляционный, в то время как  ж∗ ∘  ж ∗ является инфляционный (или обширный).

Теперь рассмотрим Икс, у ∈ А такой, что Икс ≤ у, то, используя приведенный выше, получаем Икс ≤  ж∗( ж ∗(у)). Применяя основное свойство связности Галуа, теперь можно заключить, что  ж ∗(Икс) ≤  ж ∗(у). Но это просто показывает, что  ж ∗ сохраняет порядок любых двух элементов, т.е. является монотонным. Опять же, аналогичные рассуждения приводят к монотонности  ж∗. Таким образом, монотонность не обязательно должна включаться в определение явно. Однако упоминание о монотонности помогает избежать путаницы в отношении двух альтернативных понятий связи Галуа.

Еще одно основное свойство связности Галуа состоит в том, что  ж∗( ж ∗( ж∗(Икс))) =  ж∗(Икс), для всех Икс в B. Очевидно, мы находим, что

 ж∗( ж ∗( ж∗(Икс))) ≥  ж∗(Икс).

потому что  ж∗ ∘  ж ∗ является инфляционным, как показано выше. С другой стороны, поскольку  ж ∗ ∘  ж∗ является дефляционным, а  ж∗ монотонно, обнаруживается, что

 ж∗( ж ∗( ж∗(Икс))) ≤  ж∗(Икс).

Это показывает желаемое равенство. Кроме того, мы можем использовать это свойство, чтобы заключить, что

 ж ∗( ж∗( ж ∗( ж∗(Икс)))) =  ж ∗( ж∗(Икс))

и

 ж∗( ж ∗( ж∗( ж ∗(Икс)))) =  ж∗( ж ∗(Икс))

т.е.  ж ∗ ∘  ж∗ и  ж∗ ∘  ж ∗ находятся идемпотент.

Можно показать (см. Доказательства в Блит или Эрне), что функция  ж  является нижним (соответственно верхним) сопряженным тогда и только тогда, когда  ж  это остаточное отображение (соответственно остаточное отображение). Следовательно, понятия остаточного отображения и монотонной связности Галуа, по сути, одинаковы.

Операторы замыкания и связи Галуа

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

И наоборот, любой оператор замыкания c на какой-то позе А порождает связь Галуа с нижним сопряженным  ж ∗ быть просто основным ограничением c к образу c (т.е. как сюръективное отображение закрывающая система c(А)). Верхняя примыкающая  ж∗ тогда дается включением c(А) в А, который отображает каждый закрытый элемент на себя, рассматриваемый как элемент А. Таким образом, операторы замыкания и связи Галуа оказываются тесно связанными, каждый из которых задает экземпляр другого. Аналогичные выводы справедливы и для ядерных операторов.

Приведенные выше соображения также показывают, что замкнутые элементы А (элементы Икс с участием  ж∗( ж ∗(Икс)) = Икс) отображаются на элементы в пределах диапазона оператора ядра  ж ∗ ∘  ж∗, и наоборот.

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

Еще одно важное свойство связностей Галуа состоит в том, что нижние сопряжения сохранить все супрема которые существуют в их домен. Соответственно, верхние примыкания сохраняют все существующие инфима. Из этих свойств можно также сразу сделать вывод о монотонности сопряженных элементов. В теорема о сопряженном функторе для теории порядка утверждает, что обратная импликация также верна в определенных случаях: особенно, любое сопоставление между полные решетки который сохраняет все супремы, является нижним сопряженным элементом связности Галуа.

В этой ситуации важной особенностью связностей Галуа является то, что одно сопряженное однозначно определяет другое. Следовательно, можно усилить приведенное выше утверждение, чтобы гарантировать, что любое сохраняющее супремум отображение между полными решетками является нижним сопряженным элементом единственной связности Галуа. Основное свойство, обеспечивающее эту уникальность, заключается в следующем: для каждого Икс в А,  ж ∗(Икс) наименьший элемент у из B такой, что Икс ≤  ж∗(у). В два раза за каждые у в B,  ж∗(у) величайший Икс в А такой, что  ж ∗(Икс) ≤ у. Существование определенной связи Галуа теперь подразумевает существование соответствующих наименьших или наибольших элементов, независимо от того, удовлетворяют ли соответствующие множества каким-либо свойства полноты. Таким образом, когда задан один верхний сопряженный элемент связности Галуа, другой верхний сопряженный элемент может быть определен через это же свойство.

С другой стороны, некоторая монотонная функция  ж  является нижним сопряженным если и только если каждый набор формы {Икс ∈ А |  ж (Икс) ≤ б}, для б в B, содержит наибольший элемент. Опять же, это может быть дуализировано для верхнего сопряженного.

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

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

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

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

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

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

Заметки

  1. ^ Монотонность следует из следующего условия. См. Обсуждение свойства. Это только явное определение в определении, чтобы отличить его от альтернативы. антитон определение. Связности Галуа также можно определить как пару монотонных функций, удовлетворяющих условию более слабого, что для всех Икс в А, Икс ≤ г( ж (Икс)) и для всех y в B, f (g (y)) ≤ y.
  2. ^ Gierz, p. 23
  3. ^ Бистарелли, Стефано (2004). Полукольца для решения и программирования мягких ограничений. Конспект лекций по информатике. 2962. Springer-Verlag. п. 102. Дои:10.1007/978-3-540-25925-1_8. ISBN  3-540-21181-0. ISSN  0302-9743.
  4. ^ Галатос, стр. 145
  5. ^ См. Альперин, Белл, Группы и представления (GTM 162), стр. 32
  6. ^ Уильям Ловер, Сопряженность в основаниях, Диалектика, 1969, доступно здесь. Обозначения теперь другие; более легкое введение Питера Смита в этих конспектах лекций, которые также приписывают эту концепцию цитируемой статье.
  7. ^ Биркгоф, 1-е издание (1940): §32, 3-е издание (1967): гл. V, §7 и §8
  8. ^ Гантер, Б. и Вилле, Р. Формальный анализ понятий - математические основы, Springer (1999), ISBN  978-3-540-627715
  9. ^ Гантер Б. и Обьедков С. Концептуальное исследование, Springer (2016), ISBN  978-3-662-49290-1
  10. ^ Патрик Кузо; Радия Кузо (январь 1977 г.). «Абстрактная интерпретация: модель единой решетки для статического анализа программ путем построения или аппроксимации фиксированных точек» (PDF). Proc. 4-й ACM Symp. по принципам языков программирования (POPL). С. 238–252.
    Контрпример к ложной теореме из раздела 7 (стр. 243 вверху справа) см .: Йохен Бургхардт; Флориан Каммюллер; Джефф В. Сандерс (декабрь 2000 г.). Изоморфизм вложений Галуа (Технический отчет). GMD. п. 73. ISSN  1435-2702. 122.
  11. ^ Патрик Кузо; Радия Кузо (январь 1979 г.). «Систематическое проектирование рамок анализа программ» (PDF). Proc. 6-й ACM Symp. по принципам языков программирования (POPL). ACM Press. С. 269–282.

использованная литература

Следующие книги и обзорные статьи включают соединения Галуа с использованием монотонного определения:

  • Брайан А. Дэйви и Хилари А. Пристли: Введение в решетки и порядок, Издательство Кембриджского университета, 2002.
  • Герхард Гирц, Карл Х. Хофманн, Клаус Кеймель, Джимми Д. Лоусон, Майкл В. Мислав, Дана С. Скотт: Непрерывные решетки и домены, Издательство Кембриджского университета, 2003.
  • Марсель Эрне, Юрген Кословски, Остин Мелтон, Джордж Э. Стрекер, Праймер по связям Галуа, 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, с. 103–125. (Бесплатно доступны в Интернете в различных форматах файлов. PS.GZ PS, в нем представлено множество примеров и результатов, а также примечания к различным обозначениям и определениям, возникшим в этой области.)

Некоторые публикации, использующие исходное (антитонное) определение: