алгебра Гейтинга

Алгебраическая структура, используемая в логике

В математике алгебра Гейтинга (также известная как псевдобулева алгебра ^[1] ) представляет собой ограниченную решетку (с операциями соединения и встречи, обозначаемыми ∨ и ∧, и с наименьшим элементом 0 и наибольшим элементом 1), снабженную бинарной операцией a → b, называемой импликацией, такой, что ( 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 в классификатор подобъектов Ω.

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

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

Алгебры Гейтинга реже называют псевдобулевыми алгебрами [ ^3] или даже решетками Брауэра ^[4], хотя последний термин может обозначать двойственное определение ^[5] или иметь несколько более общее значение ^{[6] .}

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

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

${\displaystyle a\wedge x\leq b.}$

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

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

Полная алгебра Гейтинга — это алгебра Гейтинга, представляющая собой полную решетку .

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

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

Категориально-теоретическое определение

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

Решетка рассматривается как категория , где meet, , является произведением . Экспоненциальное условие означает, что для любых объектов и в экспоненциальном существует единственный объект в . ${\displaystyle H}$ ${\displaystyle \wedge }$ ${\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 (-\wedge Y)\dashv (Y\Rightarrow -)}$ $${\displaystyle (-\wedge Y):H{\stackrel {\longrightarrow }{\underset {\longleftarrow }{\top }}}H:(Y\Rightarrow -)}$$

Определения теории решеток

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

${\displaystyle {\begin{cases}f_{a}\colon H\to H\\f_{a}(x)=a\wedge x\end{cases}}}$

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

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

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

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

1. ${\displaystyle a\to a=1}$
2. ${\displaystyle a\wedge (a\to b)=a\wedge b}$
3. ${\displaystyle b\wedge (a\to b)=b}$
4. ${\displaystyle a\to (b\wedge c)=(a\to b)\wedge (a\to c)}$

где уравнение 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 x\leq y\to x,}$
4. ${\displaystyle x\to (y\to z)\leq (x\to y)\to (x\to z),}$
5. ${\displaystyle x\land y\leq x,}$
6. ${\displaystyle x\land y\leq y,}$
7. ${\displaystyle x\leq y\to (x\land y),}$
8. ${\displaystyle x\leq x\lor y,}$
9. ${\displaystyle y\leq x\lor y,}$
10. ${\displaystyle x\to z\leq (y\to z)\to (x\lor y\to z),}$
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} (рассматриваемая как решетка), что дает операции:

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

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

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

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

Порядок на алгебре Гейтинга H может быть восстановлен из операции → следующим образом: для любых элементов a , b из H , тогда и только тогда, когда a → b = 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(a_{1},a_{2},\ldots ,a_{n})=1}$ ${\displaystyle a_{1},a_{2},\ldots ,a_{n}\in H}$

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

Так как для любых a и b в алгебре Гейтинга H мы имеем тогда и только тогда, когда a → b = 1, то из 1 ⇒ 2 следует , что всякий раз, когда формула F → G доказуемо истинна, мы имеем для любой алгебры Гейтинга H и любых элементов . (Из теоремы о дедукции следует, что 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 в качестве единственного правила вывода, и аксиомы которой являются аксиомами Гильберта, приведенными в Intuitionistic logic#Axiomatization . Тогда факты, которые нужно проверить, немедленно вытекают из аксиомоподобного определения алгебр Гейтинга, данного выше.

1 ⇒ 2 также предоставляет метод доказательства того, что некоторые пропозициональные формулы, хотя и являются тавтологиями в классической логике, не могут быть доказаны в интуиционистской пропозициональной логике. Для того, чтобы доказать, что некоторая формула недоказуема, достаточно указать алгебру Гейтинга H и элементы такие, что . ${\displaystyle F(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})\neq 1}$

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

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

Распределяемость

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

1. ${\displaystyle a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)}$
2. ${\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)}$

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

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

${\displaystyle x\wedge \bigvee Y=\bigvee \{x\wedge y\mid y\in Y\}}$

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

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

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

Регулярные и дополнительные элементы

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

1. х = ¬¬ х .
2. x = ¬ y для некоторого y из H .

Эквивалентность этих условий можно просто переформулировать как тождество ¬¬¬ x = ¬ x , справедливое для всех x из H .

Элементы 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 является регулярным; ^[9]
3. каждый x в H дополняется. ^[10]

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

Регулярные (соответственно дополняемые) элементы любой алгебры Гейтинга H образуют булеву алгебру H _reg (соответственно H _comp ), в которой операции ∧, ¬ и →, а также константы 0 и 1 совпадают с таковыми в H . В случае H _comp операция ∨ также та же самая, поэтому H _comp является подалгеброй H . Однако в общем случае H _reg не будет подалгеброй H , поскольку ее операция соединения ∨ _reg может отличаться от ∨. Для x , y ∈ H _reg мы имеем x ∨ reg y = ¬(¬ x ∧ ¬ y ). Ниже приведены необходимые и достаточные условия для того, чтобы ∨ _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{ for all }}x,y\in H,}$
3. ${\displaystyle \lnot (x\wedge y)=\lnot x\vee \lnot y{\mbox{ for all regular }}x,y\in H,}$
4. ${\displaystyle \lnot \lnot (x\vee y)=\lnot \lnot x\vee \lnot \lnot y{\mbox{ for all }}x,y\in H,}$
5. ${\displaystyle \lnot \lnot (x\vee y)=x\vee y{\mbox{ for all regular }}x,y\in H,}$
6. ${\displaystyle \lnot (\lnot x\wedge \lnot y)=x\vee y{\mbox{ for all regular }}x,y\in H,}$
7. ${\displaystyle \lnot x\vee \lnot \lnot x=1{\mbox{ for all }}x\in H.}$

Условие 2 — это другой закон Де Моргана. Условие 6 гласит, что операция соединения ∨ _reg на булевой алгебре H _reg регулярных элементов 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 ₂ , то мы говорим, что ƒ является морфизмом алгебр Гейтинга, если для любых элементов x и y из H ₁ имеем:

1. ${\displaystyle f(0)=0,}$
2. ${\displaystyle f(x\land y)=f(x)\land f(y),}$
3. ${\displaystyle f(x\lor y)=f(x)\lor f(y),}$
4. ${\displaystyle f(x\to y)=f(x)\to f(y),}$

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

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

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

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

Примеры

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

Для любой алгебры Гейтинга H отображение x ↦ ¬¬ x определяет морфизм из H на булеву алгебру ее регулярных элементов H _reg . Это, вообще говоря, не морфизм из 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 из H существует наименьший фильтр, содержащий S . Мы называем его фильтром, сгенерированным S . Если S пусто , F = {1}. В противном случае F равен набору x в H, такому, что существуют y ₁ , y ₂ , ..., y _n ∈ S с y ₁ ∧ y ₂ ∧ ... ∧ y _n ≤ x .

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

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

Для любого морфизма алгебр Гейтинга f  : H → H ′ , удовлетворяющего f ( y ) = 1 для любого y ∈ S , f однозначно пропускается через каноническую сюръекцию p _F  : H → H / F . То есть, существует единственный морфизм f ′  : H / F → H ′ , удовлетворяющий f ′ p F ₌ f . Говорят , что морфизм f ′ индуцирован f .

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

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

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

Метаимпликация 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. Пусть H0 _— фактор-множество 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 ₀ . Она свободна в том смысле, что для любой алгебры Гейтинга H, заданной вместе с семейством ее элементов 〈a _i : i ∈ I〉, существует единственный морфизм f : H ₀ → H, удовлетворяющий f ([ A _i ])= a _i . Уникальность f нетрудно увидеть, и ее существование по сути вытекает из метаимпликации 1 ⇒ 2 раздела «Доказуемые тождества» выше в форме ее следствия, что всякий раз, когда F и G являются доказуемо эквивалентными формулами, F (〈a _i〉)= G (〈a _i〉) для любого семейства элементов 〈a _i〉в H .

Гейтинговая алгебра формул, эквивалентных относительно теорииТ

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

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

Каждая алгебра Гейтинга изоморфна одной из алгебр вида H _T . Чтобы увидеть это, пусть H — любая алгебра Гейтинга, и пусть 〈a _i : i ∈I〉 — семейство элементов, порождающее H (например, любое сюръективное семейство). Теперь рассмотрим множество T формул J (〈A _i〉) от переменных 〈A _i : i ∈I〉 таких, что J (〈a _i〉)=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}$

Более того, правило modus ponens позволяет нам вывести формулу 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. Рассмотрим 3-элементную алгебру {0, ⁠1/2⁠ ,1} как указано выше. Если мы назначим ⁠1/2⁠ к P и 0 к Q , то значение закона Пирса (( P → Q )→ P )→ P равно ⁠1/2⁠ . Из этого следует, что закон Пирса не может быть выведен интуиционистски. См. изоморфизм Карри–Ховарда для общего контекста того, что это подразумевает в теории типов .

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

Проблемы с принятием решений

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

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

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

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

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

Примечания

1. «Псевдобулева алгебра — Энциклопедия математики».
2. Kripke, SA: 1965, «Семантический анализ интуиционистской логики I». В: JN Crossley и MAE Dummett (ред.): Formal Systems and Recursive Functions. Амстердам: North-Holland, стр. 92–130.
3. Хелена Расёва; Роман Сикорский (1963). Математика метаматематики . Państwowe Wydawnictwo Naukowe (PWN). стр. 54–62, 93–95, 123–130.
4. А.Г. Кусраев; Самсон Семенович Кутателадзе (1999). Булевозначный анализ. Спрингер. п. 12. ISBN 978-0-7923-5921-0.
5. Янков, В.А. (2001) [1994], «Решетка Брауэра», Математическая энциклопедия , EMS Press.
6. Томас Скотт Блит (2005). Решетки и упорядоченные алгебраические структуры. Springer. стр. 151. ISBN 978-1-85233-905-0.
7. Georgescu, G. (2006). "N-значные логики и алгебры Лукасевича–Моисила". Axiomathes . 16 (1–2): 123–136. doi :10.1007/s10516-005-4145-6. S2CID  121264473., Теорема 3.6
8. Иоргулеску, А.: Связи между MV _n -алгебрами и n -значными алгебрами Лукасевича–Моисила — I. Дискретная математика 181, 155–177 (1998) doi :10.1016/S0012-365X(97)00052-6
9. Резерфорд (1965), Th.26.2 стр.78.
10. Резерфорд (1965), Th.26.1 стр.78.
11. Статман, Р. (1979). «Интуиционистская пропозициональная логика полна в полиномиальном пространстве». Theoretical Comput. Sci . 9 : 67–72. doi :10.1016/0304-3975(79)90006-9. hdl : 2027.42/23534 .
12. Кук, С.А. (1971). «Сложность процедур доказательства теорем». Труды Третьего ежегодного симпозиума ACM по теории вычислений, ACM, Нью-Йорк . С. 151–158. doi : 10.1145/800157.805047 .
13. Гжегорчик, Анджей (1951). «Неразрешимость некоторых топологических теорий» (PDF) . Фундамента Математика . 38 : 137–52. дои : 10.4064/fm-38-1-137-152.
14. Питер Т. Джонстон, Stone Spaces , (1982) Cambridge University Press, Кембридж, ISBN 0-521-23893-5 . (См. параграф 4.11) 
15. см. раздел 8.3 в * Дикманн, Макс; Шварц, Нильс; Трессл, Маркус (2019). Спектральные пространства . Новые математические монографии. Том 35. Кембридж: Cambridge University Press . doi : 10.1017/9781316543870. ISBN 9781107146723. S2CID  201542298.

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

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

Ссылки

• Резерфорд, Дэниел Эдвин (1965). Введение в теорию решеток . Оливер и Бойд. OCLC  224572.
• Ф. Борсо, Справочник по категориальной алгебре 3 , в Энциклопедии математики и ее приложений , т. 53, Cambridge University Press, 1994. ISBN 0-521-44180-3 OCLC  52238554 
• G. Gierz, KH Hoffmann, K. Keimel, JD Lawson, M. Mislove и DS Scott , Непрерывные решетки и области , в Encyclopedia of Mathematics and its Applications , том 93, Cambridge University Press, 2003.
• S. Ghilardi. Free Heyting algebras as bi-Heyting algebras , Math. Rep. Acad. Sci. Canada XVI., 6:240–244, 1992.
• Хейтинг, А. (1930), "Die formalen Regeln der intuitionistischen Logik. I, II, III", Sitzungsberichte Akad. Берлин : 42–56, 57–71, 158–169, JFM  56.0823.01 .
• Дикманн, Макс; Шварц, Нильс; Трессл, Маркус (2019). Спектральные пространства . Новые математические монографии. Том 35. Кембридж: Cambridge University Press . doi : 10.1017/9781316543870. ISBN 9781107146723. S2CID  201542298.

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

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