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

В математике , А алгебра гейтингова (также известный как псевдо-Булева алгебра ^[1] ) является ограниченной решеткой (с присоединяться и встречаются операции написаны ∨ и ∧ и с наименьшим элементом 0 и наибольшим элементом 1) , снабженный бинарной операцией → б из импликации , что ( с ∧ ) ≤ б эквивалентно C ≤ ( в → б ). С логической точки зрения, 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] или даже Brouwer решетки , ^[4] , хотя последний термин может обозначать двойное определение, ^[5] или имеет немного более общее значение. ^[6]

Формальное определение [ править ]

Алгебра Гейтинга 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 (-\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}}}$

для некоторого фиксированного в 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} (рассматриваемая как решетка), что дает следующие операции:

  ${\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 a\lor b}$ б а 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 ^[7] (но они не являются MV-алгебрами для n ≥ 5 ^[8] ).

Свойства [ править ]

Общие свойства [ править ]

Упорядочение на гейтинговых алгебру 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(a_{1},a_{2},\ldots ,a_{n})=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 и${\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}$G доказуемо эквивалентны, так как ≤ - отношение порядка.${\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(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\}}$

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

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

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

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

Морфизмы алгебры Гейтинга [ править ]

Определение [ править ]

Учитывая две гейтингова алгебры H ₁ и H ₂ и отображение F  : H ₁ → 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 ₂ тоже . Это следует из характеристики алгебр Гейтинга как ограниченных решеток (рассматриваемых как алгебраические структуры, а не частично упорядоченные множества) с операцией →, удовлетворяющей определенным тождествам.

Свойства [ править ]

Тождественное отображение 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 ₀ . Он свободен в том смысле , что для любой гейтингова алгебры H даются вместе с семейством его элементов < _я : я ∈ I >, существует единственный морфизм F : H ₀ → H , удовлетворяющие е ([ _я]) = а _я . Единственность 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 (< A _I >) в 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 г. как разрешимая. ^[2] Точная вычислительная сложность задачи была установлена ​​Р. Статманом в 1979 г., который показал, что она является PSPACE-полной. ^[11] и, следовательно, по крайней мере так же сложно, как решающие уравнения булевой алгебры (показанные как CoNP-полные в 1971 году С. Куком) ^[12], и предполагалось, что это значительно сложнее. Элементарная теория или теория первого порядка алгебр Гейтинга неразрешима. ^[13] Остается открытым , разрешима ли универсальная теория Хорна алгебр Гейтинга или проблема слов . ^[14] Помимо проблемы слов известно, что алгебры Гейтинга не являются локально конечными (никакая алгебра Гейтинга, порожденная конечным непустым множеством, не конечна), в отличие от булевых алгебр, которые локально конечны и проблема слов которых разрешима. Неизвестно, существуют ли свободные полные алгебры Гейтинга, за исключением случая с одним образующим, когда свободная алгебра Гейтинга на одном образующем тривиально дополняется путем присоединения новой вершины.

Заметки [ править ]

См. Также [ править ]

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

Ссылки [ править ]

• Резерфорд, Дэниел Эдвин (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

Внешние ссылки [ править ]

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