Алгебра Гейтинга - Heyting algebra

В математике , А алгебра гейтингова (также известный как псевдо-алгебре ) является ограниченной решеткой (с присоединяться и встречаются операции написаны ∨ и ∧ и с наименьшим элементом 0 и наибольшим элементом 1) , снабженный бинарной операцией → б о причастности такого что ( c ∧ a ) ≤ b эквивалентно c ≤ ( a → b ). С логической точки зрения, A → B по этому определению является самым слабым утверждением, для которого modus ponens , правило вывода A → B , A ⊢ B , является правильным. Как и булевы алгебры , алгебры Гейтинга образуют многообразие, аксиоматизируемое конечным числом уравнений. Алгебры Гейтинга были введены Арендом Хейтингом  ( 1930 ) для формализации интуиционистской логики .

Как решетки, алгебры Гейтинга дистрибутивны . Каждая булева алгебра является алгеброй Гейтинга, когда a → b определяется, как обычно, как ¬ a ∨ b , как и любая полная дистрибутивная решетка, удовлетворяющая одностороннему бесконечному дистрибутивному закону, когда a → b берется за верхнюю грань множества всех c, для которого c ∧ a ≤ b . В конечном случае любая непустая дистрибутивная решетка, в частности каждая непустая конечная цепь , автоматически является полной и полностью дистрибутивной и, следовательно, является алгеброй Гейтинга.

Из определения следует, что 1 ≤ 0 → a , что соответствует интуиции, что любое предложение a следует из противоречия 0. Хотя операция отрицания ¬ a не является частью определения, она определима как a → 0. Интуитивное Содержание ¬ a - это утверждение, что предположение a привело бы к противоречию. Из определения следует, что a ¬ a = 0. Далее можно показать, что a ≤ ¬¬ a , хотя обратное, ¬¬ a ≤ a , в общем случае неверно, то есть исключение двойного отрицания в общем случае не выполняется. в алгебре Гейтинга.

Алгебры Гейтинга обобщают булевы алгебры в том смысле, что алгебра Гейтинга, удовлетворяющая a ¬ a = 1 ( исключая середину ), что эквивалентно ¬¬ a = a ( исключение двойного отрицания ), является булевой алгеброй. Эти элементы алгебры Гейтинга H вида ¬ a составляют булеву решетку, но в общем случае это не подалгебра в H (см. Ниже ).

Алгебры Гейтинга служат алгебраическими моделями интуиционистской логики высказываний точно так же, как булевы алгебры моделируют классическую логику высказываний . Внутренняя логика элементарного топоса основана на алгебре гейтинговой из подобъектов в клеммном объекте 1 упорядочены по включению, что эквивалентно морфизмы от 1 до подобъекта классификаторов Ом.

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

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

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

Формальное определение

Алгебра Гейтинга H - это такая ограниченная решетка , что для всех a и b в H существует наибольший элемент x из H такой, что

${\ Displaystyle а \ клин х \ leq b.}$

Этот элемент является относительным псевдодополнением элемента a по отношению к b и обозначается a → b . Мы пишем 1 и 0 для наибольшего и наименьшего элемента H соответственно.

В любой алгебре Гейтинга можно определить псевдодополнение ¬ a любого элемента a , положив ¬ a = ( a → 0). По определению ,, и ¬ a - самый большой элемент, обладающий этим свойством. Однако в целом неверно, что , таким образом, ¬ является лишь псевдодополнением, а не истинным дополнением , как это было бы в случае булевой алгебры. ${\ Displaystyle а \ клин \ lnot а = 0}$${\ displaystyle a \ vee \ lnot a = 1}$

Полная гейтингова алгебра является алгеброй гейтингова , что является полной решеткой .

Подалгебра из гейтинговой алгебры H является подмножество Н ₁ из Н , содержащего 0 и 1 и замкнуто относительно операций ∧, ∨ и →. Отсюда следует, что он также закрыт под ¬. Подалгебра превращается в алгебру Гейтинга индуцированными операциями.

Альтернативные определения

Теоретико-категориальное определение

Алгебра Гейтинга - это ограниченная решетка, в которой есть все экспоненциальные объекты . ${\ displaystyle H}$

Решетка рассматривается как категория, где встречаются,, является продуктом . Экспоненциальное условие означает, что для любых объектов и в экспоненте однозначно существует как объект в . ${\ displaystyle H}$${\ Displaystyle \ клин}$${\ displaystyle Y}$${\ displaystyle Z}$${\ displaystyle H}$${\ Displaystyle Z ^ {Y}}$${\ displaystyle H}$

Импликация Гейтинга (часто написанная с использованием или во избежание недоразумений, таких как использование для обозначения функтора ) является просто экспоненциальной: это альтернативное обозначение для . Из определения экспонент следует, что импликация ( ) сопряжена справа с meet ( ). Это присоединение может быть записано как или более полно: ${\ displaystyle \ Rightarrow}$${\ displaystyle \ multimap}$${\ displaystyle \ to}$${\ displaystyle Y \ Rightarrow Z}$${\ Displaystyle Z ^ {Y}}$${\ displaystyle \ Rightarrow: H \ times H \ to H}$${\ displaystyle \ wedge: H \ times H \ to H}$${\ Displaystyle (- \ клин Y) \ dashv (Y \ Rightarrow -)}$

Теоретико-решеточные определения

Эквивалентное определение алгебр Гейтинга можно дать, рассматривая отображения:

${\ displaystyle {\ begin {cases} f_ {a} \ двоеточие H \ to H \\ f_ {a} (x) = a \ wedge x \ end {cases}}}$

для некоторого фиксированного в H . Ограниченная решетка H является алгеброй Гейтинга тогда и только тогда, когда каждое отображение f _a является нижним сопряженным элементом монотонной связности Галуа . В этом случае соответствующий верхний сопряженный элемент g _a задается формулой g _a ( x ) = a → x , где → определяется, как указано выше.

Еще одно определение - решетка с делениями, моноидная операция которой. Тогда единицей моноида должен быть верхний элемент 1. Коммутативность этого моноида означает, что две невязки совпадают при a → b .

Ограниченная решетка с операцией импликации

Для ограниченной решетки A с наибольшим и наименьшим элементами 1 и 0 и бинарной операции → они вместе образуют алгебру Гейтинга тогда и только тогда, когда выполняется следующее:

1. ${\ Displaystyle от а \ до а = 1}$
2. ${\ Displaystyle а \ клин (от \ до b) = а \ клин b}$
3. ${\ Displaystyle б \ клин (от \ до b) = Ь}$
4. ${\ Displaystyle а \ к (б \ клин с) = (а \ к б) \ клин (а \ к с)}$

где 4 - закон распределения при →.

Характеристика с использованием аксиом интуиционистской логики

Эта характеризация алгебр Гейтинга делает доказательство основных фактов, касающихся отношений между интуиционистским исчислением высказываний и алгебрами Гейтинга, непосредственным. (Эти факты см. В разделах « Подтверждаемые тождества » и « Универсальные конструкции ».) Следует думать об элементе как о значении, интуитивно «доказуемо истинном». Сравните с аксиомами из раздела «Интуиционистская логика # Аксиоматизация» ). ${\ displaystyle \ top}$

Для множества A с тремя бинарными операциями →, ∧ и ∨ и двумя выделенными элементами и , тогда A является алгеброй Гейтинга для этих операций (и отношение ≤ определяется условием, что при a → b = ) тогда и только тогда, когда для любых элементов x , y и z из A выполняются следующие условия : ${\ displaystyle \ bot}$${\ displaystyle \ top}$${\ displaystyle a \ leq b}$${\ displaystyle \ top}$

1. ${\ displaystyle {\ mbox {If}} x \ leq y {\ mbox {and}} y \ leq x {\ mbox {then}} x = y,}$
2. ${\ displaystyle {\ mbox {If}} \ top \ leq y, {\ mbox {then}} y = \ top,}$
3. ${\ Displaystyle х \ leq у \ к х,}$
4. ${\ Displaystyle х \ к (у \ к г) \ Leq (х \ к у) \ к (х \ к г),}$
5. ${\ Displaystyle х \ земля у \ leq х,}$
6. ${\ Displaystyle х \ земля у \ leq у,}$
7. ${\ Displaystyle х \ Leq у \ к (х \ земля у),}$
8. ${\ Displaystyle х \ Leq х \ лор у,}$
9. ${\ Displaystyle у \ Leq х \ лор у,}$
10. ${\ Displaystyle х \ к г \ Leq (у \ к г) \ к (х \ лор у \ к г),}$
11. ${\ displaystyle \ bot \ leq x.}$

Наконец, мы определяем ¬ x как x → . ${\ displaystyle \ bot}$

Условие 1 гласит, что необходимо определить эквивалентные формулы. Условие 2 говорит, что доказуемо истинные формулы замкнуты по modus ponens . Тогда условия 3 и 4 являются условиями. Условие 5, 6 и 7 и условия. Условия 8, 9 и 10 являются или условиями. Условие 11 - ложное .

Конечно, если бы для логики был выбран другой набор аксиом, мы могли бы соответствующим образом изменить нашу.

Примеры

• Каждая булева алгебра является алгеброй Гейтинга, где p → q задается формулой ¬ p ∨ q .
• Каждое полностью упорядоченное множество , имеющее наименьший элемент 0 и наибольший элемент 1, является алгеброй Гейтинга (если рассматривать ее как решетку). В этом случае p → q равно 1, если p≤q , и q в противном случае.
• Простейшая алгебра Гейтинга, которая еще не является булевой алгеброй, - это полностью упорядоченное множество {0, 1/2, 1} (рассматриваемая как решетка), что дает следующие операции:

  ${\ displaystyle a \ land b}$ б а 0 1/2 1 0 0 0 0 1/2 0 1/2 1/2 1 0 1/2 1

  ${\ Displaystyle а \ лор б}$ б а 0 1/2 1 0 0 1/2 1 1/2 1/2 1/2 1 1 1 1 1

  а → б б а 0 1/2 1 0 1 1 1 1/2 0 1 1 1 0 1/2 1

  а ¬ а 0 1 1/2 0 1 0

  В этом примере это 1/2∨¬1/2 знак равно 1/2∨ (1/2 → 0) = 1/2∨0 = 1/2 фальсифицирует закон исключенного третьего.

• Каждая топология обеспечивает полную алгебру Гейтинга в виде открытой решетки множеств . В этом случае элемент → B является внутренняя объединения A ^с и B , где ^с обозначает дополнение из открытого множества A . Не все полные алгебры Гейтинга имеют такую ​​форму. Эти вопросы изучаются в бессмысленной топологии , где полные алгебры Гейтинга также называются фреймами или локали .
• Каждая внутренняя алгебра предоставляет алгебру Гейтинга в виде своей решетки открытых элементов. Каждая алгебра Гейтинга имеет такую ​​форму, поскольку алгебра Гейтинга может быть дополнена до булевой алгебры, взяв ее свободное булево расширение как ограниченную дистрибутивную решетку, а затем рассматривая его как обобщенную топологию в этой булевой алгебре.
• Lindenbaum алгебра высказываний интуиционистской логики является алгеброй гейтингова.
• В глобальных элементах по субобъекту классификатор П А. Н. элементарного топоса образуют алгебру Гейтингова; это алгебра Гейтинга значений истинности интуиционистской логики высшего порядка, индуцированной топосом.
• Алгебры Лукасевича – Мойсила (LM _n ) также являются гейтинговыми алгебрами для любого n (но они не являются MV-алгебрами для n ≥ 5).

Характеристики

Общие свойства

Упорядочение на гейтинговых алгебру H может быть извлечено из операции → следующим образом : для любых элементов через , б из Н , тогда и только тогда , когда в → б = 1. ${\ displaystyle \ leq}$${\ displaystyle a \ leq b}$

В отличие от некоторых многозначных логик , алгебры Гейтинга разделяют следующее свойство с булевыми алгебрами: если отрицание имеет фиксированную точку (т.е. ¬ a = a для некоторого a ), то алгебра Гейтинга является тривиальной одноэлементной алгеброй Гейтинга.

Подтверждаемые личности

Учитывая формулу исчисления высказываний (с использованием, помимо переменных, связок и констант 0 и 1), это факт, доказанный на ранней стадии любого исследования алгебр Гейтинга, что следующие два условия эквивалентны: ${\ Displaystyle F (A_ {1}, A_ {2}, \ ldots, A_ {n})}$${\ displaystyle \ land, \ lor, \ lnot, \ to}$

1. Формула F доказуемо верна в интуиционистском исчислении высказываний.
2. Тождество верно для любой алгебры Гейтинга H и любых элементов .${\ Displaystyle F (а_ {1}, а_ {2}, \ ldots, а_ {п}) = 1}$${\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {n} \ in H}$

Метаимпликация 1 ⇒ 2 чрезвычайно полезна и является основным практическим методом доказательства тождеств в алгебрах Гейтинга. На практике в таких доказательствах часто используется теорема дедукции .

Так как для любого а и б в гейтингова алгебре Н мы имеем тогда и только тогда , когда → Ь = 1, то из 1 ⇒ 2 , что всякий раз , когда формула F → G доказуемо правда, мы имеем для любого гейтинговых алгебры Н , и любой элементы . (Из теоремы дедукции следует, что F → G доказуемо [из ничего] тогда и только тогда, когда G доказуемо из F , то есть если G является доказуемым следствием F. ) В частности, если F и G доказуемо эквивалентны , то , поскольку ≤ - отношение порядка. ${\ displaystyle a \ leq b}$${\ Displaystyle F (a_ {1}, a_ {2}, \ ldots, a_ {n}) \ leq G (a_ {1}, a_ {2}, \ ldots, a_ {n})}$${\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {n} \ in H}$${\ Displaystyle F (a_ {1}, a_ {2}, \ ldots, a_ {n}) = G (a_ {1}, a_ {2}, \ ldots, a_ {n})}$

1 ⇒ 2 можно доказать, исследуя логические аксиомы системы доказательства и проверяя, что их значение равно 1 в любой алгебре Гейтинга, а затем проверяя, что применение правил вывода к выражениям со значением 1 в алгебре Гейтинга приводит к выражения со значением 1. Например, давайте выберем систему доказательства, имеющую modus ponens в качестве единственного правила вывода, и чьи аксиомы являются аксиомами гильбертовского стиля, приведенными в разделе « Интуиционистская логика # Аксиоматизация» . Тогда факты, подлежащие проверке, немедленно вытекают из аксиомного определения алгебр Гейтинга, данного выше.

1 ⇒ 2 также предоставляет метод доказательства того, что определенные пропозициональные формулы, хотя и тавтологии в классической логике, не могут быть доказаны в интуиционистской логике высказываний. Чтобы доказать, что некоторая формула недоказуема, достаточно показать алгебру Гейтинга H и такие элементы , что . ${\ Displaystyle F (A_ {1}, A_ {2}, \ ldots, A_ {n})}$${\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {n} \ in H}$${\ Displaystyle F (а_ {1}, а_ {2}, \ ldots, а_ {п}) \ neq 1}$

Если кто-то хочет избежать упоминания логики, то на практике становится необходимым доказать в виде леммы версию теоремы дедукции, справедливую для алгебр Гейтинга: для любых элементов a , b и c алгебры Гейтинга H мы имеем . ${\ Displaystyle (а \ земля Ь) \ к с = а \ к (б \ к с)}$

Подробнее о метаимпликации 2 ⇒ 1 см. Ниже в разделе « Универсальные конструкции ».

Распределительность

Алгебры Гейтинга всегда дистрибутивны . В частности, у нас всегда есть личности

1. ${\ Displaystyle а \ клин (б \ ви с) = (а \ клин б) \ ви (а \ клин с)}$
2. ${\ Displaystyle а \ ви (б \ клин с) = (а \ ви б) \ клин (а \ ви с)}$

Закон распределения иногда формулируется как аксиома, но на самом деле он следует из существования относительных псевдодополнений. Причина в том, что, будучи нижним сопряженным к связи Галуа , сохраняет все существующие супремы . Дистрибутивность, в свою очередь, - это просто сохранение бинарной супремы по . ${\ Displaystyle \ клин}$ ${\ Displaystyle \ клин}$

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

${\ Displaystyle х \ клин \ bigvee Y = \ bigvee \ {х \ клин у \ середина у \ в Y \}}$

для любого элемента х в H и любого подмножества Y из H . И наоборот, любая полная решетка, удовлетворяющая указанному выше бесконечному закону распределения, является полной алгеброй Гейтинга с

${\ displaystyle a \ to b = \ bigvee \ {c \ mid a \ land c \ leq b \}}$

является его относительной операцией псевдодополнения.

Обычные и дополненные элементы

Элемент x алгебры Гейтинга H называется регулярным, если выполняется одно из следующих эквивалентных условий:

1. х = ¬¬ х .
2. х = ¬ у для некоторого у в Н .

Эквивалентность этих условий может быть пересчитана просто как тождество ¬¬¬ х = ¬ х , справедливо для всех х в Н .

Элементы x и y алгебры Гейтинга H называются дополняющими друг друга, если x ∧ y = 0 и x ∨ y = 1. Если он существует, любой такой y уникален и фактически должен быть равен ¬ x . Назовем элемент x дополняемым, если он допускает дополнение. Верно, что если x дополняется, то также ¬ x , и тогда x и ¬ x дополняют друг друга. Однако, что сбивает с толку, даже если x не дополняется, ¬ x, тем не менее, может иметь дополнение (не равное x ). В любой алгебре Гейтинга элементы 0 и 1 дополняют друг друга. Например, возможно, что ¬ x равно 0 для каждого x, отличного от 0, и 1, если x = 0, и в этом случае 0 и 1 являются единственными регулярными элементами.

Любой дополняемый элемент алгебры Гейтинга является регулярным, хотя в общем случае обратное неверно. В частности, 0 и 1 всегда регулярны.

Для любой алгебры Гейтинга H следующие условия эквивалентны:

1. H - булева алгебра ;
2. каждый x в H регулярен;
3. каждый x в H дополняем.

В этом случае элемент a → b равен ¬ a ∨ b .

Регулярные (соответственно дополняемые) элементы любой алгебры Гейтинга H составляют булеву алгебру H _reg (соответственно H _comp ), в которой операции ∧, ¬ и →, а также константы 0 и 1 совпадают с таковыми в H . В случае H _комп , операция ∨ также одинакова, следовательно , Н _комп является подалгеброй H . Однако в общем случае H _reg не будет подалгеброй H , потому что его операция соединения ∨ _reg может отличаться от ∨. Для х , у ∈ Н _р , мы имеем х ∨ _р у = ¬ (¬ х ∧ ¬ у ). Ниже приведены необходимые и достаточные условия для совпадения ∨ _reg с ∨.

Законы Де Моргана в алгебре Гейтинга

В любой алгебре Гейтинга выполняется один из двух законов Де Моргана , а именно

${\ displaystyle \ forall x, y \ in H: \ qquad \ lnot (x \ vee y) = \ lnot x \ wedge \ lnot y.}$

Однако другой закон Де Моргана не всегда выполняется. Вместо этого у нас есть слабый закон де Моргана:

${\ displaystyle \ forall x, y \ in H: \ qquad \ lnot (x \ wedge y) = \ lnot \ lnot (\ lnot x \ vee \ lnot y).}$

Следующие утверждения эквивалентны для всех алгебр Гейтинга H :

1. H удовлетворяет обоим законам Де Моргана,
2. ${\ displaystyle \ lnot (x \ wedge y) = \ lnot x \ vee \ lnot y {\ mbox {для всех}} x, y \ in H,}$
3. ${\ displaystyle \ lnot (x \ wedge y) = \ lnot x \ vee \ lnot y {\ mbox {для всех обычных}} x, y \ in H,}$
4. ${\ displaystyle \ lnot \ lnot (x \ vee y) = \ lnot \ lnot x \ vee \ lnot \ lnot \ lnot y {\ mbox {для всех}} x, y \ in H,}$
5. ${\ displaystyle \ lnot \ lnot (x \ vee y) = x \ vee y {\ mbox {для всех обычных}} x, y \ in H,}$
6. ${\ displaystyle \ lnot (\ lnot x \ wedge \ lnot y) = x \ vee y {\ mbox {для всех обычных}} x, y \ in H,}$
7. ${\ displaystyle \ lnot x \ vee \ lnot \ lnot x = 1 {\ mbox {для всех}} x \ in H.}$

Условие 2 - это другой закон Де Моргана. Состояние 6 говорит о том , что присоединиться к операции ∨ _рег на булевой алгебре Н _рег регулярных элементов H совпадает с операцией ∨ из H . Условие 7 утверждает, что каждый регулярный элемент дополняется, т. _Е. H _reg = H _comp .

Докажем эквивалентность. Ясно, что метаимпликации 1 ⇒ 2, 2 ⇒ 3 и 4 ⇒ 5 тривиальны. Кроме того, 3 4 и 5 ⇔ 6 являются просто результатом первого закона Де Моргана и определения регулярных элементов. Мы покажем, что 6 ⇒ 7 , взяв ¬ x и ¬¬ x вместо x и y в 6 и используя тождество a ∧ ¬ a = 0. Отметим, что 2 ⇒ 1 следует из первого закона Де Моргана, а 7 ⇒ 6. вытекает из того факта, что операция соединения ∨ на подалгебре H _comp является просто ограничением ∨ на H _comp с учетом данной нами характеризации условий 6 и 7. Метаимпликация 5 ⇒ 2 является тривиальным следствием слабого Закон Де Моргана, взяв ¬ x и ¬ y вместо x и y в 5.

Алгебры Гейтинга, удовлетворяющие указанным выше свойствам, связаны с логикой Де Моргана так же, как алгебры Гейтинга в целом связаны с интуиционистской логикой.

Морфизмы алгебры Гейтинга

Определение

Учитывая две гейтингова алгебры H ₁ и H ₂ и отображение F  : H ₁ → H ₂ , мы говорим , что ƒ является морфизм гейтинговых алгебр , если для любых элементов х и у в Н ₁ , мы имеем:

1. ${\ displaystyle f (0) = 0,}$
2. ${\ Displaystyle е (х \ земля у) = е (х) \ земля е (у),}$
3. ${\ Displaystyle е (х \ лор у) = е (х) \ лор е (у),}$
4. ${\ Displaystyle е (х \ к у) = е (х) \ к е (у),}$

Из любого из трех последних условий (2, 3 или 4) следует, что f - возрастающая функция, то есть f ( x ) ≤ f ( y ) всякий раз, когда x ≤ y .

Предположим, что H ₁ и H ₂ - это структуры с операциями →, ∧, ∨ (и, возможно, ¬) и константами 0 и 1, а f - сюръективное отображение из H ₁ в H ₂ со свойствами с 1 по 4 выше. Тогда если H ₁ - алгебра Гейтинга, то H ₂ тоже . Это следует из характеристики алгебр Гейтинга как ограниченных решеток (рассматриваемых как алгебраические структуры, а не частично упорядоченные множества) с операцией →, удовлетворяющей определенным тождествам.

Характеристики

Тождественное отображение f ( x ) = x любой алгебры Гейтинга в себя является морфизмом, а композиция g ∘ f любых двух морфизмов f и g является морфизмом. Следовательно, алгебры Гейтинга образуют категорию .

Примеры

Для алгебры Гейтинга H и любой подалгебры H ₁ отображение включения i  : H ₁ → H является морфизмом.

Для любой алгебры Гейтинга H отображение x ↦ ¬¬ x определяет морфизм из H на булеву алгебру своих регулярных элементов H _reg . Это не в общем морфизм из Н к самому себе, так как присоединиться к операции Н _рег может отличаться от такового H .

Коэффициенты

Пусть H является гейтингова алгебра, и пусть F ⊆ H . Мы называем F фильтра на H , если она удовлетворяет следующие свойства:

1. ${\ displaystyle 1 \ in F,}$
2. ${\ displaystyle {\ mbox {If}} x, y \ in F {\ mbox {then}} x \ land y \ in F,}$
3. ${\ displaystyle {\ mbox {If}} x \ in F, \ y \ in H, \ {\ mbox {and}} x \ leq y {\ mbox {then}} y \ in F.}$

Пересечение любого набора фильтров на H снова является фильтром. Поэтому, учитывая любое подмножество S из Н имеется наименьший фильтр , содержащий S . Мы называем это фильтр генерируется с помощью S . Если S пусто, F = {1}. В противном случае, Р равно множеству х в Н таких , что существует у ₁ , у ₂ , ..., у _п ∈ S с у ₁ ∧ у ₂ ∧ ... ∧ у _п ≤ х .

Если Н есть алгебра гейтингова и F фильтр в Н , определит отношение \ на Н следующим образом : мы пишем х \ у , когда х → у и у → х и принадлежит F . Тогда ∼ - отношение эквивалентности ; мы пишем H / F для фактормножества . На H / F существует уникальная структура алгебры Гейтинга, такая что каноническая сюръекция p _F  : H → H / F становится морфизмом гейтинга. Мы называем Гейтингова алгеброй H / F фактор из H на F .

Пусть S подмножество гейтинговой алгебры H , и пусть F быть фильтр , порожденный S . Тогда H / F удовлетворяет следующему универсальному свойству:

Учитывая , любой морфизм гейтингова алгебры F  : H → H ' , удовлетворяющий п ( у ) = 1 для каждого у ∈ S , ф факторов однозначно через канонический сюръекции р _F  : H → H / F . То есть, существует единственный морфизм F '  : Н / Р → Н' , удовлетворяющих f'p _F = F . Морфизм F ' называется индуцированной с помощью F .

Пусть f  : H ₁ → H ₂ - морфизм гейтинговых алгебр. Ядро из F , написанный кег е , является множество F ^-1 [{1}]. Это фильтр на H ₁ . (Следует проявлять осторожность, потому что это определение, если применить его к морфизму булевых алгебр, двойственно тому, что можно было бы назвать ядром морфизма, рассматриваемого как морфизм колец.) Согласно вышеизложенному, f индуцирует морфизм f ′  : H ₁ / (кег F ) → H ₂ . Это изоморфизм H ₁ / (ker f ) на подалгебру f [ H ₁ ] в H ₂ .

Универсальные конструкции

Алгебра Гейтинга пропозициональных формул от n переменных с точностью до интуиционистской эквивалентности

Метаимпликация 2 ⇒ 1 в разделе « Доказуемые тождества » доказывается, показывая, что результат следующей конструкции сам является алгеброй Гейтинга:

1. Рассмотрим множество L пропозициональных формул от переменных A ₁ , A ₂ , ..., A _n .
2. Наделите L с предпорядке ≼ путем определения F ≼ G , если G является (интуиционист) логическое следствие из F , то есть, если G выводим из F . Совершенно очевидно, что ≼ является предварительным заказом.
3. Рассмотрим отношение эквивалентности F ∼ G, индуцированное предпорядком F≼G. (Оно определяется как F ∼ G тогда и только тогда, когда F ≼ G и G ≼ F. Фактически, ∼ является отношением (интуиционистской) логической эквивалентности.)
4. Пусть H ₀ - фактормножество L / ∼. Это будет желанная алгебра Гейтинга.
5. Обозначим через [ F ] для класса эквивалентности формулы F . Операции →, ∧, ∨ и ¬ определены на L очевидным образом . Убедитесь, что для заданных формул F и G классы эквивалентности [ F → G ], [ F ∧ G ], [ F ∨ G ] и [¬ F ] зависят только от [ F ] и [ G ]. Это определяет операции →, ∧, ∨ и ¬ на фактормножестве H ₀ = L / ∼. Далее определим 1 как класс доказуемо истинных утверждений и положим 0 = [⊥].
6. Убедитесь, что H ₀ вместе с этими операциями является алгеброй Гейтинга. Мы делаем это, используя аксиомное определение алгебр Гейтинга. H ₀ удовлетворяет условиям THEN-1 - FALSE, потому что все формулы данных форм являются аксиомами интуиционистской логики. MODUS-PONENS следует из того факта, что если формула ⊤ → F доказуемо истинна, где ⊤ доказуемо истинна, то F доказуемо истинно (с применением правила вывода modus ponens). Наконец, EQUIV следует из того факта, что если F → G и G → F доказуемо истинны, то F и G доказуемы друг из друга (с применением правила вывода modus ponens), следовательно, [ F ] = [ G ] .

Как всегда в аксиомном определении алгебр Гейтинга, мы определяем ≤ на H ₀ условием, что x ≤ y тогда и только тогда, когда x → y = 1. Поскольку по теореме дедукции формула F → G доказуемо истинна тогда и только тогда, когда G доказуема из F , отсюда следует, что [ F ] ≤ [ G ] тогда и только тогда, когда F≼G. Другими словами, это ≤ отношение порядка на L / ~ индуцированное предпорядке ≼ на L .

Свободная алгебра Гейтинга на произвольном множестве образующих

Фактически, предыдущее построение может быть выполнено для любого набора переменных { A _i  : i ∈ I } (возможно, бесконечного). Таким образом получается свободная алгебра Гейтинга от переменных { A _i }, которую мы снова обозначим через H ₀ . Он свободен в том смысле , что при любом гейтингова алгебра Н дается вместе с семейством его элементов < _я : я ∈ I >, существует единственный морфизм F : Н ₀ → Н , удовлетворяющая е ([ _я ]) = _я . Единственность f нетрудно увидеть, и его существование, по существу, является следствием метаимпликации 1 ⇒ 2 раздела « Доказуемые тождества » выше в форме его следствия, что всякий раз, когда F и G являются доказуемо эквивалентными формулами, F (〈a _я >) = G (< _я >) для любого семейства элементов < в _I > в H .

Алгебра Гейтинга формул, эквивалентных теории T

Учитывая набор формул T в переменных { A _i }, рассматриваемых как аксиомы, такое же построение можно было бы провести в отношении отношения F ≼ G, определенного на L, чтобы означать, что G является доказуемым следствием F и множества аксиом Т . Обозначим полученную алгебру Гейтинга через H _T. Тогда Н _Т удовлетворяет тем же универсальное свойство , как H ₀ выше, но по отношению к Гейтингу алгебры H и семейство элементов < в _I > , удовлетворяющие то свойство , что J (< _я >) = 1 для любой аксиомы J (< _я > ) в T . (Заметим, что H _T , взятая вместе с семейством его элементов 〈[ A _i ]〉, сама удовлетворяет этому свойству.) Существование и единственность морфизма доказывается так же, как и для H ₀ , за исключением того, что необходимо изменить метаимпликация 1 ⇒ 2 в « Доказываемых тождествах », так что 1 читается «доказуемо истинно из T », а 2 читается «любые элементы a ₁ , a ₂ , ..., a _n в H, удовлетворяющие формулам T ».

Алгебру Гейтинга H _T, которую мы только что определили, можно рассматривать как фактор свободной алгебры Гейтинга H ₀ на том же наборе переменных, применяя универсальное свойство H ₀ относительно H _T и семейства ее элементов 〈[ A _i ]〉.

Каждая алгебра гейтингова изоморфна одной формы Н _Т . Чтобы увидеть это, пусть Н быть любой гейтингова алгебра, и пусть < _я : я ∈I> семейство элементов , порождающих H (например, любой сюръективны семьи). Рассмотрим теперь множество Т формул J (< _я >) в переменных < _я : я ∈I> такое , что J (< _я >) = 1. Тогда мы получаем морфизм f : H _T → H по универсальному свойству H _T , который, очевидно, сюръективен. Нетрудно показать, что f инъективно.

Сравнение с алгебрами Линденбаума

Приведенные конструкции играют совершенно аналогичную роль в отношении алгебр Гейтинга, что и алгебры Линденбаума в отношении булевых алгебр . Фактически, алгебра Линденбаума B _T в переменных { A _i } относительно аксиом T - это просто наша H _{T ∪ T 1} , где T ₁ - это множество всех формул вида ¬¬ F → F , поскольку дополнительные аксиомы T ₁ - единственные, которые нужно добавить, чтобы сделать все классические тавтологии доказуемыми.

Алгебры Гейтинга в применении к интуиционистской логике

Если интерпретировать аксиомы интуиционистской логики высказываний как термины алгебры Гейтинга, то они будут вычислять наибольший элемент, 1, в любой алгебре Гейтинга при любом присвоении значений переменным формулы. Например, ( P ∧ Q ) → P по определению псевдодополнения является наибольшим элементом x такой, что . Это неравенство выполняется для любого x , поэтому наибольшее такое x равно 1. ${\ displaystyle P \ land Q \ land x \ leq P}$

Кроме того, правило модус поненс позволяет вывести формулу Q из формул P и P → Q . Но в любой алгебре Гейтинга, если P имеет значение 1, а P → Q имеет значение 1, то это означает, что и так ; может быть только Q имеет значение 1. ${\ displaystyle P \ land 1 \ leq Q}$${\ displaystyle 1 \ land 1 \ leq Q}$

Это означает, что если формула выводима из законов интуиционистской логики и выводится из ее аксиом посредством правила modus ponens, то она всегда будет иметь значение 1 во всех алгебрах Гейтинга при любом присвоении значений переменным формулы. . Однако можно построить алгебру Гейтинга, в которой значение закона Пирса не всегда равно 1. Рассмотрим трехэлементную алгебру {0,1/2, 1}, как указано выше. Если мы назначим1/2в P и 0 в Q , то значение закона Пирса (( P → Q ) → P ) → P равно1/2. Отсюда следует, что закон Пирса нельзя вывести интуитивно. См. Изоморфизм Карри – Ховарда для получения общего контекста того, что это означает в теории типов .

Обратное также может быть доказано: если формула всегда имеет значение 1, то она выводится из законов интуиционистской логики, поэтому интуиционистски верные формулы - это именно те формулы, которые всегда имеют значение 1. Это похоже на понятие. что классически допустимые формулы - это те формулы, которые имеют значение 1 в двухэлементной булевой алгебре при любом возможном присвоении значений true и false переменным формулы, то есть они являются формулами, которые являются тавтологиями в обычном смысле таблицы истинности. Алгебра Гейтинга, с логической точки зрения, тогда является обобщением обычной системы значений истинности, и ее самый большой элемент 1 аналогичен «истинному». Обычная система двузначной логики - это частный случай алгебры Гейтинга и наименьший нетривиальный, в котором единственными элементами алгебры являются 1 (истина) и 0 (ложь).

Проблемы с решением

С. Крипке в 1965 году показал, что проблема того, выполняется ли данное уравнение в каждой алгебре Гейтинга, разрешима. Точная вычислительная сложность задачи была установлена ​​Р. Статманом в 1979 году, который показал, что она является PSPACE-полной и, следовательно, по меньшей мере так же сложно, как решить уравнения булевой алгебры (показанные как CoNP-полные в 1971 году С. Куком), и предполагалось, что это значительно сложнее. Элементарная теория или теория первого порядка алгебр Гейтинга неразрешима. Остается открытым , разрешима ли универсальная теория Хорна алгебр Гейтинга или проблема слов . Помимо проблемы слов известно, что алгебры Гейтинга не являются локально конечными (никакая алгебра Гейтинга, порожденная конечным непустым множеством, не конечна), в отличие от булевых алгебр, которые локально конечны и проблема слов которых разрешима. Неизвестно, существуют ли свободные полные алгебры Гейтинга, за исключением случая с одним образующим, когда свободная алгебра Гейтинга на одном образующем тривиально дополняется путем присоединения новой вершины.

Топологическое представление и теория двойственности

Каждая гейтингова алгебра H естественно изоморфна ограниченной подрешетки L открытых множеств топологического пространства X , где вывод из L задается внутренней части . Точнее, Х представляет собой спектральное пространство простых идеалов ограниченной решетки H и L является решетка открытых и квази-компактных подмножеств X . ${\ displaystyle U \ to V}$${\ Displaystyle (Х \ setminus U) \ чашка V}$

В более общем смысле категория гейтинговых алгебр двойственно эквивалентна категории гейтинговых пространств. Эту двойственность можно рассматривать как ограничение классической двойственности Стоуна ограниченных дистрибутивных решеток до (неполной) подкатегории алгебр Гейтинга.

С другой стороны, категория алгебр Гейтинга двойственно эквивалентна категории пространств Эсакии . Это называется двойственностью Эсакии .

Примечания

Смотрите также

• Топология Александрова
• Суперинтуиционистские (промежуточные) логики
• Список тем по булевой алгебре
• Алгебра Оккама

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

• Резерфорд, Дэниел Эдвин (1965). Введение в теорию решеток . Оливер и Бойд. OCLC  224572 .
• Ф. Борсё, Справочник по категориальной алгебре 3 , Энциклопедия математики и ее приложений , Vol. 53, Cambridge University Press, 1994. ISBN  0-521-44180-3 OCLC  52238554
• Г. Гирц, К. Х. Хоффманн, К. Кеймель, Дж. Д. Лоусон, М. Мислав и Д. С. Скотт, Непрерывные решетки и области , В энциклопедии математики и ее приложений , Vol. 93, Cambridge University Press, 2003.
• С. Гиларди. Свободные гейтинговые алгебры как бигейтинговые алгебры , Math. Rep. Acad. Sci. Канада XVI., 6: 240–244, 1992.
• Heyting, A. (1930), "Die formalen Regeln der intuitionistischen Logik. I, II, III", Sitzungsberichte Akad. Берлин : 42-56, 57-71, 158-169, JFM  56.0823.01
• Дикманн, Макс; Шварц, Нильс; Трессл, Маркус (2019). Спектральные пространства . Новые математические монографии. 35 . Кембридж: Издательство Кембриджского университета . DOI : 10.1017 / 9781316543870 . ISBN 9781107146723. S2CID  201542298 .

внешние ссылки

• Алгебра Гейтинга в PlanetMath .