Соединение Галуа

редактировать

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

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

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

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

Содержание

  • 1 Определения
    • 1.1 (Монотонное) Соединение Галуа
    • 1.2 Антитонное соединение Галуа
  • 2 Примеры
    • 2.1 Монотонные соединения Галуа
      • 2.1.1 Блок питания; импликация и соединение
      • 2.1.2 Решетки
      • 2.1.3 Переходные групповые действия
      • 2.1.4 Изображение и обратное изображение
      • 2.1.5 Размах и закрытие
      • 2.1.6 Синтаксис и семантика
    • 2.2 Антитонные связи Галуа
      • 2.2.1 Теория Галуа
      • 2.2.2 Алгебраическая топология: накрывающие пространства
      • 2.2.3 Линейная алгебра: аннигиляторы и ортогональные дополнения
      • 2.2.4 Алгебраическая геометрия
      • 2.2.5 Связи на множествах мощности, возникающие из бинарных отношений
  • 3 Свойства
  • 4 Операторы замыкания и связи Галуа
  • 5 Существование и единственность связей Галуа
  • 6 Связи Галуа как морфизмы
  • 7 Связь с теорией категорий
  • 8 Приложения в теории программирования
  • 9 Примечания
  • 10 Ссылки

Определения

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

Пусть (A, ≤) и (B, ≤) быть двумя частично упорядоченными наборами. Монотонная связь Галуа между этими множествами состоит из двух монотонных функций : F: A → B и G: B → A, таких, что для всех a в A и b в B мы иметь

F (a) ≤ b тогда и только тогда, когда a ≤ G (b).

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

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

F (a) - наименьший элемент ~ b с a ≤ G (~ b), и
G (b) является наибольшим элементом ~ a с F (~ a) ≤ b.

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

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

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

Антитон-Галуа-соединение

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

b ≤ F (a), если и только если a ≤ G (b).

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

F (a) является наибольшим элементом b с a ≤ G (b), а
G (b) является наибольшим элементом a с b ≤ F (a

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

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

Примеры

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

Набор мощности; импликация и конъюнкция

Для примера теории порядка, пусть U будет некоторым набором, и пусть A и B оба будут набором мощности U, упорядоченным по включению. Выберем фиксированное подмножество L в U. Тогда отображения F и G, где F (M) = L, M и G (N) = N ∪ (U \ L), образуют монотонную связность Галуа, где F является нижним прилегающий. Похожую связность Галуа, нижнее сопряжение которой задается операцией встречи (инфимума), можно найти в любой алгебре Гейтинга. В частности, он присутствует в любой булевой алгебре, где два отображения могут быть описаны как F (x) = (a ∧ x) и G (y) = (y ∨ ¬a) = (a ⇒ у). Говоря логически: «импликация из а» - это верхнее присоединение к «соединению с а».

Решетки

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

Действия транзитивной группы

Пусть G действует транзитивно на X и выбирает некоторую точку x в X. Рассмотрим

B = {B ⊆ X: x ∈ B; ∀ g ∈ G, г B знак равно B org B ∩ B = ∅}, {\ displaystyle {\ mathcal {B}} = \ {B \ substeq X: x \ in B; \ forall g \ in G, gB = B \ \ mathrm {или} \ gB \ cap B = \ emptyset \},}{\ mathcal {B}} = \ {B \ substeq X: x \ in B; \ forall g \ in G, gB = B \ \ mathrm {или} \ gB \ cap B = \ emptyset \},

набор блоков, содержащих x. Далее, пусть G {\ displaystyle {\ mathcal {G}}}{\ mathcal {G}} состоит из подгрупп группы G, содержащих стабилизатор x.

Тогда соответствие B → G {\ displaystyle {\ mathcal {B}} \ to {\ mathcal {G}}}{\ mathcal {B}} \ to {\ mathcal {G}} :

B ↦ HB = {g ∈ G: gx ∈ B} {\ displaystyle B \ mapsto H_ {B} = \ {g \ in G: gx \ in B \}}B \ mapsto H_ {B} = \ {g \ in G: gx \ in B \}

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

Изображение и инверсное изображение

Если f: X → Y является функцией, то для любого подмножества M X мы можем сформировать изображение F (M) = f (M) = {f (m) | m ∈ M} и для любого подмножества N множества Y мы можем сформировать прообраз G (N) = f (N) = {x ∈ X | f (x) ∈ N}. Тогда F и G образуют монотонную связь Галуа между множеством степеней X и множеством степеней Y, оба упорядоченные по включению ⊆. В этой ситуации есть еще одна сопряженная пара: для подмножества M в X положим H (M) = {y ∈ Y | f ({y}) ⊆ M}. Тогда G и H образуют монотонную связь Галуа между множеством степеней Y и множеством степеней X. В первом соединении Галуа G является верхним сопряженным соединением, а во втором соединении Галуа оно служит нижним сопряженным соединением.

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

Диапазон и замыкание

Выберите некоторый математический объект X, имеющий базовый набор, например, group, ring, векторное пространство и т. Д. Для любого подмножества 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 пусть F (T) - множество всех структур, удовлетворяющих аксиомам T; для набора математических структур S ∈ B, пусть G (S) будет минимумом аксиоматизаций, которые аппроксимируют S. Тогда мы можем сказать, что F (T) является подмножеством S тогда и только тогда, когда T логически влечет G (S) : «семантический функтор» F и «синтаксический функтор» G образуют монотонную связь Галуа с семантикой, являющейся нижним сопряженным соединением.

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

Теория Галуа

Мотивирующий пример взят из теории Галуа: предположим, что L / K является расширением поля. Пусть A - множество всех подполей L, содержащих K, упорядоченное по включению ⊆. Если E - такое подполе, через Gal (L / E) обозначим группу полевых автоморфизмов поля L, для которых E фиксировано. Пусть B - множество подгрупп группы Gal (L / K), упорядоченных по включению ⊆. Для такой подгруппы G определим Fix (G) как поле, состоящее из всех элементов L, которые фиксируются всеми элементами группы G.Тогда отображения E ↦ Gal (L / E) и G ↦ Fix (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, мы определяем его аннулятор G (Y) = {x ∈ V | φ (x) = 0 ∀φ ∈ Y}. Это дает антитонную связь Галуа между подмножествами V и подмножествами V.

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

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

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

V (S) = {x ∈ K n: f (x) = 0 для всех f ∈ S}, {\ displaystyle V (S) = \ {x \ in K ^ {n}: f (x) = 0 {\ t_dv {для всех}} f \ in S \},}V (S) = \ {x \ in K ^ {n}: f (x) = 0 {\ t_dv {для всех}} f \ in S \},

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

I (U) = {f ∈ K [X 1, ⋯, X n]: f ( x) = 0 для всех x ∈ U}. {\ Displaystyle I (U) = \ {е \ in K [X_ {1}, \ cdots, X_ {n}]: f (x) = 0 {\ t_dv {для всех}} x \ in U \}. }I (U) = \ {f \ in K [X_ {1}, \ cdots, X_ {n}]: f (x) = 0 {\ t_dv {для всех}} x \ в U \}.

Тогда V и я образуют антитонную связь Галуа.

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

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

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

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

Предположим, что X и Y - произвольные множества и задано бинарное отношение R над X и Y. Для любого подмножества M в X определим F (M) = {y ∈ Y | mRy ∀m ∈ M}. Аналогично, для любого подмножества N в Y определим G (N) = {x ∈ X | xRn ∀n ∈ N}. Тогда F и G образуют антитонную связь Галуа между степенными множествами X и Y, оба упорядоченные по включению ⊆.

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

Свойства

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

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

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

f∗(f (f ∗ (x))) ≥ f ∗ (x).

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

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

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

f (f ∗ (f (f ∗ (x)))) = f (f ∗ (x))

и

f∗(f (f ∗ (f (x)))) = f ∗ (f (x))

т.е., f ∘ f ∗ и f ∗ ∘ f являются идемпотентными.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Ссылки

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

  • Брайан А. Дэйви и Хилари А. Пристли: Введение в решетки и порядок, Cambridge University Press, 2002.
  • Герхард Гирц, Карл Х. Хофманн, Клаус Кеймель, Джимми Д. Лоусон, Майкл В. Мислав, Дана С. Скотт: непрерывные решетки и домены, Cambridge University Press, 2003.
  • Марсель Эрне, Юрген Кословски, Остин Мелтон, Джордж Э. Стрекер, Учебник по связям Галуа, в: Материалы Летней конференции 1991 года по общей топологии и приложениям в честь Мэри Эллен Рудин и ее работ, Анналы Нью-Йорка Академия наук, Vol. 704, 1993, с. 103–125. (Свободно доступный в Интернете в различных форматах файлов PS.GZ PS, он содержит множество примеров и результатов, а также примечания к различным обозначениям и определениям, возникшим в этой области.)

В некоторых публикациях используется оригинал (антитонное) определение:

  • Mac Lane, Saunders (сентябрь 1998 г.). Категории для рабочего математика (Второе изд.). Springer. ISBN 0-387-98403-8.
  • Томас Скотт Блит, Решетки и упорядоченные алгебраические структуры, Springer, 2005, ISBN 1-85233 -905-5.
  • Николаос Галатос, Питер Йипсен, Томаш Ковальски и Хироакира Оно (2007), Остаточные решетки. Алгебраический взгляд на субструктурную логику, Elsevier, ISBN 978-0-444-52141-5.
  • Гарретт Биркгоф: теория решеток, Amer. Математика. Soc. Coll. Pub., Vol 25, 1940
  • Ore, Øystein (1944), «Galois Connexions», Труды Американского математического общества, 55(3): 493–513, doi : 10.2307 / 1990305, JSTOR 1990305
Последняя правка сделана 2021-05-21 10:56:52
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте