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

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

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

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

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

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

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

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

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

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

Алгебра Гейтинга ЧАС это ограниченная решетка такой, что для всех а и б в ЧАС есть величайший элемент Икс из ЧАС такой, что

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

Этот элемент является относительный псевдодополнение из а относительно б, и обозначается а→б. Мы пишем 1 и 0 для наибольшего и наименьшего элемента ЧАС, соответственно.

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

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

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

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

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

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

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

Значение Гейтинга (часто пишется с использованием ${ 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 (- wedge Y): H { stackrel { longrightarrow} { underset { longleftarrow} { top}}} H: (Y Rightarrow -)}$$

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

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

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

для некоторых фиксированных а в ЧАС. Ограниченная решетка ЧАС алгебра Гейтинга если и только если каждое отображение ж_а является нижним сопряженным монотонным Связь Галуа. В этом случае соответствующий верхний сопряженный грамм_а дан кем-то грамм_а(Икс) = а→Икс, где → определено, как указано выше.

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

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

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

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

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

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

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

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

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.}$

Наконец, определим ¬Икс быть Икс→ ${ displaystyle bot}$.

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

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

Примеры

В свободный Алгебра Гейтинга над одним образующим (также известная как решетка Ригера – Нисимуры)

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

  ${ displaystyle a land b}$ б а 0 ½ 1 0 0 0 0 ½ 0 ½ ½ 1 0 ½ 1

  ${ Displaystyle а лор б}$ б а 0 ½ 1 0 0 ½ 1 ½ ½ ½ 1 1 1 1 1

  а→б б а 0 ½ 1 0 1 1 1 ½ 0 1 1 1 0 ½ 1

  а ¬а 0 1 ½ 0 1 0

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

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

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

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

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

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

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

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

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

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

Поскольку для любого а и б в алгебре Гейтинга ЧАС у нас есть ${ displaystyle a leq b}$ если и только если а→б = 1, из 1 ⇒ 2 что всякий раз, когда формула F→грамм доказуемо верно, у нас есть ${ 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}$. (Из теоремы дедукции следует, что F→грамм доказуемо [из ничего] тогда и только тогда, когда грамм можно доказать из F, то есть если грамм является доказуемым следствием F.) В частности, если F и грамм доказуемо эквивалентны, то ${ 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 также предоставляет метод доказательства того, что некоторые пропозициональные формулы, хотя тавтологии в классической логике, не можешь быть доказанным в интуиционистской логике высказываний. Чтобы доказать, что некоторая формула ${ 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}$.

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

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

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

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

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

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

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

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

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

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

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

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

Элемент Икс алгебры Гейтинга ЧАС называется обычный если выполнено одно из следующих эквивалентных условий:

1. Икс = ¬¬Икс.
2. Икс = ¬у для некоторых у в ЧАС.

Эквивалентность этих условий можно переформулировать просто как тождество ¬¬¬Икс = ¬Икс, действительно для всех Икс в ЧАС.

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

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

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

1. ЧАС это Булева алгебра;
2. каждый Икс в ЧАС регулярно;^[9]
3. каждый Икс в ЧАС дополняется.^[10]

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

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

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

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

${ 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).}$

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

1. ЧАС удовлетворяет обоим законам Де Моргана,
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 говорит, что операция соединения ∨_рег на булевой алгебре ЧАС_рег регулярных элементов ЧАС совпадает с операцией ∨ оператора ЧАС. Условие 7 гласит, что каждый регулярный элемент дополняется, т. Е. ЧАС_рег = ЧАС_комп.

Докажем эквивалентность. Ясно, что метаимпликации 1 ⇒ 2, 2 ⇒ 3 и 4 ⇒ 5 тривиальны. Более того, 3 ⇔ 4 и 5 ⇔ 6 просто результат первого закона Де Моргана и определения регулярных элементов. Мы показываем, что 6 ⇒ 7 взяв ¬Икс и ¬¬Икс на месте Икс и у в 6 и используя тождество а ∧ ¬а = 0. Заметь 2 ⇒ 1 следует из первого закона Де Моргана, а 7 ⇒ 6 следует из того факта, что операция соединения ∨ на подалгебре ЧАС_комп это просто ограничение ∨ на ЧАС_компс учетом данной характеризации условий 6 и 7. Метаимпликация 5 ⇒ 2 является тривиальным следствием слабого закона Де Моргана, принимая ¬Икс и ¬у на месте Икс и у в 5.

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

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

Определение

Учитывая две алгебры Гейтинга ЧАС₁ и ЧАС₂ и отображение ж : ЧАС₁ → ЧАС₂, мы говорим, что ƒ это морфизм алгебр Гейтинга, если для любых элементов Икс и у в ЧАС₁, у нас есть:

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

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

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

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

Карта идентичности ж(Икс) = Икс от любой алгебры Гейтинга к самой себе есть морфизм, а составное грамм ∘ ж любых двух морфизмов ж и грамм это морфизм. Следовательно, алгебры Гейтинга образуют категория.

Примеры

Учитывая алгебру Гейтинга ЧАС и любая подалгебра ЧАС₁отображение включения я : ЧАС₁ → ЧАС это морфизм.

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

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

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

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.}$

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

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

Позволять S - подмножество алгебры Гейтинга ЧАС и разреши F быть фильтром, созданным S. потом ЧАС/F удовлетворяет следующему универсальному свойству:

Для любого морфизма алгебр Гейтинга ж : ЧАС → ЧАС' удовлетворение ж(у) = 1 для каждого у ∈ S, ж факторы уникально через каноническую сюръекцию п_F : ЧАС → ЧАС/F. То есть есть уникальный морфизм f ′ : ЧАС/F → ЧАС' удовлетворение f′p_F = ж. Морфизм f ′ как говорят индуцированный к ж.

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

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

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

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

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

Как всегда в аксиомном определении алгебр Гейтинга, мы определяем ≤ на ЧАС₀ при условии, что Икс≤у если и только если Икс→у= 1. Поскольку по теорема дедукции, формула F→грамм доказуемо верно тогда и только тогда, когда грамм можно доказать из F, следует, что [F]≤[грамм] тогда и только тогда, когда F≼G. Другими словами, ≤ - отношение порядка на L/ ∼ индуцировано предпорядком ≼ на L.

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

Фактически, предыдущее построение можно провести для любого набора переменных {А_я : я∈я} (возможно, бесконечно). Таким образом получается свободный Алгебра Гейтинга от переменных {А_я}, который мы снова обозначим через ЧАС₀. Это бесплатно в том смысле, что для любой алгебры Гейтинга ЧАС заданный вместе с семейством его элементов 〈а_я: я∈я 〉 Существует единственный морфизм ж:ЧАС₀→ЧАС удовлетворение ж([А_я])=а_я. Уникальность ж нетрудно увидеть, и его существование, по существу, является результатом метаимпликации 1 ⇒ 2 раздела "Подтверждаемые личности"выше, в виде его следствия, что всякий раз, когда F и грамм доказуемо эквивалентные формулы, F(〈а_я〉)=грамм(〈а_я〉) Для любого семейства элементов 〈а_я>в ЧАС.

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

Учитывая набор формул Т в переменных {А_я}, рассматриваемые как аксиомы, такое же построение могло быть выполнено в отношении отношения F≼грамм определено на L иметь в виду это грамм является доказуемым следствием F и набор аксиом Т. Обозначим через ЧАС_Т получилась алгебра Гейтинга. потом ЧАС_Т удовлетворяет тому же универсальному свойству, что и ЧАС₀ выше, но относительно алгебр Гейтинга ЧАС и семейства элементов 〈а_я〉 Удовлетворяющее свойству J(〈а_я〉) = 1 для любой аксиомы J(〈А_я>) в Т. (Отметим, что ЧАС_Т, взятый вместе с семейством его элементов 〈[А_я]〉, Сам удовлетворяет этому свойству.) Существование и единственность морфизма доказывается так же, как и для ЧАС₀, за исключением того, что нужно изменить метаимпликацию 1 ⇒ 2 в "Подтверждаемые личности"так что я читал" доказуемо верно от Т, "и 2 читает" любые элементы а₁, а₂,..., а_п в ЧАС удовлетворяющие формулам T."

Алгебра Гейтинга ЧАС_Т которое мы только что определили, можно рассматривать как фактор свободной алгебры Гейтинга ЧАС₀ от того же набора переменных, применяя универсальное свойство ЧАС₀ относительно ЧАС_Т, и семейство его элементов 〈[А_я]〉.

Каждая алгебра Гейтинга изоморфна одной из форм ЧАС_Т. Чтобы увидеть это, позвольте ЧАС - произвольная алгебра Гейтинга, и пусть 〈а_я: я∈I〉 - семейство элементов, порождающих ЧАС (например, любая сюръективная семья). Теперь рассмотрим множество Т формул J(〈А_я〉) В переменных 〈А_я: я∈I〉 такие, что J(〈а_я〉) = 1. Тогда мы получаем морфизм ж:ЧАС_Т→ЧАС универсальным свойством ЧАС_Т, что явно сюръективно. Нетрудно показать, что ж инъективно.

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

Приведенные нами конструкции играют в отношении алгебр Гейтинга роль, совершенно аналогичную роли алгебр Гейтинга. Алгебры Линденбаума относительно Булевы алгебры. Фактически, алгебра Линденбаума B_Т в переменных {А_я} относительно аксиом Т просто наш ЧАС_Т∪Т1, куда Т₁ - это множество всех формул вида ¬¬F→F, поскольку дополнительные аксиомы Т₁ являются единственными, которые необходимо добавить, чтобы сделать все классические тавтологии доказуемыми.

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

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

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

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

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

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

С. Крипке в 1965 г. показал, что проблема того, выполняется ли данное уравнение в каждой алгебре Гейтинга, разрешима.^[2] Точный вычислительная сложность Проблема была установлена ​​Р. Статманом в 1979 г., который показал, что это PSPACE-полный^[11] и, следовательно, по крайней мере так сложно, как решающие уравнения булевой алгебры (показан С. Куком в 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.
• С. Гиларди. Свободные гейтинговые алгебры как бигейтинговые алгебры, Математика. Rep. Acad. Sci. Канада 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

внешняя ссылка

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