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

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

В математике - алгебра Гейтинга (также известная как псевдо- Булева алгебра ) представляет собой ограниченную решетку (с операциями соединения и встречи, записанными ∨ и ∧, с наименьшим 0 и наибольшим элементом 1), снабженной бинарной операцией импликации a → b такой, что (c ∧ а) ≤ 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, что соответствует интуиции, что любое предложение следует из противоречия 0. Хотя операция отрицания ¬a не является частью, ее можно определить как a → 0. Интуитивным содержанием ¬a утверждение, что предположение привело бы к противоречию. Из определения следует, что a ¬a = 0. Далее можно показать, что a ≤ ¬¬a, хотя обратное, ¬¬a ≤ a, в общем случае неверно, то есть исключение двойного отрицания вообще не выполнено в алгебре Гейтинга.

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

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

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

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

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

Содержание

1 Формальное определение
2 Альтернативные определения
- 2.1 Теоретико-категориальное определение
- 2.2 Теоретико-решеточные определения
- 2.3 Ограниченная решетка с операционной импликацией
- 2.4 Характеристика с использованием аксиом интуиционистской логики
3 Примеры
4 Свойства
- 4.1 Общие свойства
- 4.2 Доказываемые тождества
- 4.3 Дистрибутивность
- 4.4 Регулярные и дополнительные элементы
- 4.5 Законы Де Моргана в алгебре Гейтинга
5 Морфизмы алгебры Гейтинга
- 5.1 Определение
- 5.2 Свойства
- 5.3 Примеры
6 показателей
7 Универсальные конструкции
- 7.1 Алгебра Гейтинга пропозициональных формул от n с точностью до интуиционистской эквивалентности
- 7.2 Fr ee Алгебра Гейтинга на произвольном наборе образующих
- 7.3 Алгебра Гейтинга формул, эквивалентных по отношению к теории T
- 7.4 Сравнение с алгебрами Линденбаума
8 Алгебры Гейтинга в применении к интуиционистской логике
9 Проблемы принятия решений
10 Примечания
11 См. Также
12 Ссылки
13 Внешние ссылки

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

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

a ∧ x ≤ b. {\ displaystyle a \ wedge x \ leq b.}

a \ клин x \ le b.

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

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

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

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

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

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

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

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

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

(- ∧ Y): H ⊤ ⟵ ⟶ H: (Y ⇒ -) {\ displaystyle (- \ wedge Y): H {\ stackrel {\ longrightarrow} {\ underset {\ longleftarrow} {\ top}}} H: (Y \ Rightarrow -)}

{\ displaystyle (- \ wedge Y): H {\ stackrel {\ longrightarrow} {\ underset {\ longleftarrow} {\ top}}} H: (Y \ Стрелка вправо -)}

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

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

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

\ begin {cases} f_a \ двоеточие H \ к H \\ f_a (х) = а \ клин х \ конец {случаи}

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

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

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

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

$a → a = 1 {\ displaystyle a \ to a = 1}$ $a \ to a = 1$
$a ∧ (a → b) = a ∧ b {\ displaystyle a \ wedge (от a \ to b) = a \ клин b}$ $a \ клин (от a \ до b) = a \ wedge b$
$б ∧ (a → b) знак равно b {\ displaystyle b \ wedge (a \ to b) = b}$ $b \ wedge (от a \ to b) = b$
$a → (b ∧ c) = (a → b) ∧ (a → c) {\ displaystyle a \ to (b \ wedge c) = (a \ to b) \ wedge (a \ to c)}$ $a \ to (b \ wedge c) = (a \ to b) \ клин (от a \ до с)$

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

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

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

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

$Если x ≤ y и y ≤ x, то x = y, {\ displaystyle {\ t_dv {If}} x \ leq y {\ t_dv {and}} y \ leq x {\ t_dv {then}} x = y,}$ $\ t_dv {Если} x \ le y \ t_dv {и} y \ le x \ t_dv {тогда} x знак равно y,$
$Если ⊤ ≤ y, то y = ⊤, {\ displaystyle {\ t_dv {If}} \ top \ leq y, {\ t_dv {then}} y = \ top,}$ ${\ displaystyle {\ t_dv {If}} \ top \ leq y, {\ t_dv {then}} y = \ top,}$
$x ≤ y → x, {\ displaystyle x \ leq y \ к x,}$ $x \ le y \ to x,$
$x → (y → z) ≤ (x → y) → (x → z), {\ displaystyle x \ to (y \ to z) \ leq (x \ to y) \ to (икс \ к Z),}$ $x \ to (y \ to z) \ le (x \ to y) \ to (x \ to z),$
$Икс ∧ Y ≤ Икс, {\ Displaystyle х \ земля у \ Leq х,}$ ${\ displaystyle x \ земля y \ leq x,}$
$х ∧ у ≤ Y, {\ Displaystyle х \ земля у \ Leq у,}$ ${\ displaystyle x \ land y \ leq y,}$
$Икс ≤ Y → (Икс ∧ Y), {\ Стиль отображения х \ Leq Y \ К (х \ земля у),}$ ${\ displaystyle x \ leq y \ to (x \ land y),}$
$х ≤ х ∨ Y, {\ Displaysty ле Икс \ Leq Икс \ Lor Y,}$ ${\ displaystyle x \ leq x \ lor y,}$
$Y ≤ Икс ∨ Y, {\ Displaystyle Y \ Leq X \ LOR Y,}$ ${\ displaystyle y \ l eq x \ lor y,}$
$X → Z ≤ (Y → Z) → (x ∨ Y → Z), {\ Displaystyle х \ к Z \ Leq (у \ к г) \ к (х \ лор у \ к г),}$ ${\ displaystyle x \ to z \ leq (y \ to z) \ to (x \ lor y \ to z),}$
$⊥ ≤ х. {\ displaystyle \ bot \ leq x.}$ ${\ displaystyle \ bot \ leq x.}$

Наконец, мы определяем ¬x как x → $⊥ {\ displaystyle \ bot}$ $\ 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} (рассматриваемое как решетка), дающее операцию:
$a ∧ b {\ displaystyle a \ land b}$ $a \ land b$
ba 0 ½ 1
0 0 0 0
½ 0 ½ ½
1 0 ½ 1
$a ∨ b {\ displaystyle a \ lor b}$ $a \ lor b$
ba 0 ½ 1
0 0 ½ 1
½ ½ ½ 1
1 1 1 1
a → b
ba 0 ½ 1
0 1 1 1
½ 0 1 1
1 0 ½ 1
a ¬a
0 1
½ 0
1 0
В этом примере ½∨¬½ = ½∨ (½ → 0) = ½∨0 = ½ фальсифицирует закон исключенного третьего.
Каждая топология предоставляет полную алгебру Гейтинга в виде своей решетки большого числа. В этом случае элемент A → B является внутренним объединением A и B, где A обозначает дополнение к открытому множеству A. Не все полные алгебры Гейтинга имеют такую форму. Эти вопросы изучаются в бессмысленной топологии, где полные алгебры Гейтинга также называются фреймами или локали .
каждая внутренняя алгебра использует алгебру Гейтинга в форме его решетки из открытых элементов. Каждая алгебра Гейтинга имеет эту форму, как алгебра Гейтинга может быть дополнена до булевой алгебры, затем взять ее свободное булево расширение как ограниченную дистрибутивную решетку и рассматривать его как обобщенную топологию в булевой алгебре.
Алгебра Линденбаума пропозициональной интуиционистской логики - это алгебра Гейтинга.
глобальные элементы классификатора подобъектов Ω элементарных топосов образуют алгебру Гейтинга; это алгебра Гейтинга истинностных значений интуиционистской логики порядка, индуцированной топосами.
Алгебры Лукасевича - Мойсила (LM n) также являются алгебрами Гейтинга для любого n (но они не являются MV-алгебрами для n ≥ 5).

Свойства

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

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

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

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

По формуле $F (A 1, A 2,…, A n) {\ displaystyle F (A_ {1}, A_ {2}, \ ldots, A_ {n})}$ $F (A_1, A_2, \ ldots, A_n)$ исчисления высказываний (с использованием, окружной переменной, связок $∧, ∨, ¬, → {\ displaystyle \ land, \ lor, \ lnot, \ to}$ $\ land, \ lor, \ lnot, \ to$ и константы 0 и 1), это факт, доказанный на раннем этапе любого исследования алгебр Гейтинга, что два условия эквивалентны:

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

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

алгеб для любых a и b вре Гейтинга H мы имеем $a ≤ b {\ displaystyle a \ leq b}$ $a \ le b$ тогда и только тогда, когда a → b = 1, Из 1 ⇒ 2 следует, что всякий раз, когда формула F → G доказуемо верна, мы имеем $F (a 1, a 2,…, an) ≤ G (a 1, a 2,…, an) {\ стиль отображения F (a_ {1}, a_ {2}, \ ldots, a_ {n}) \ leq G (a_ {1}, a_ {2}, \ ldots, a_ {n})}$ $F (a_1, a_2, \ ldots, a_n) \ le G (a_1, a_2, \ ldots, a_n)$ для любого Алгебра Гейтинга H и любые элементы $a 1, a 2,…, an ∈ H {\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {n} \ in H}$ $a_1, a_2, \ ldots, a_n \ in H$ . (Из теоремы дедукции следует, что F → G доказуемо [из ничего] тогда и только тогда, когда G доказуемо из F, то есть если G доказуемым следствием F.) В частности, если F и G доказуемо эквивалентны, то $F (a 1, a 2,…, an) = G (a 1, a 2,…, an) {\ displaystyle F (a_ {1}, a_ {2}, \ ldots, a_ {n}) = G (a_ {1}, a_ {2}, \ ldots, a_ {n})}$ $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 также обеспечивает метод доказательства, что положительные формулы, хотя и тавтологии в классической логике, не могут быть доказаны в интуиционистской логике высказываний. Чтобы доказать, что некоторая формула $F (A 1, A 2,…, A n) {\ displaystyle F (A_ {1}, A_ {2}, \ ldots, A_ {n})}$ $F (A_1, A_2, \ ldots, A_n)$ не доказуемо, достаточно показать алгебру Гейтинга H и элементы $a 1, a 2,…, an ∈ H {\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {n} \ in H}$ $a_1, a_2, \ ldots, a_n \ in H$ такой, что $F (a 1, a 2,…, an) ≠ 1 {\ displaystyle F (a_ {1}, a_ {2}, \ ldots, a_ {n}) \ neq 1}$ $F (a_1, a_2, \ ldots, a_n) \ ne 1$ .

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

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

Дистрибутивность

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

$a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) {\ displaystyle a \ wedge (b \ vee c) = (a \ wedge b) \ vee (a \ клин c)}$ $a \ wedge (b \ vee c) = (a \ wedge b) \ vee (a \ wedge c)$
$a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) {\ displaystyle a \ vee (b \ wedge c) = (a \ vee b) \ клин (a \ vee c)}$ $a \ vee (b \ wedge c) = (a \ vee b) \ клин (a \ vee c)$

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

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

x ∧ ⋁ Y знак равно ⋁ {x ∧ y ∣ y ∈ Y} {\ displaystyle x \ wedge \ bigvee Y = \ bigvee \ {x \ wedge y \ mid y \ in Y \}}

x \ wedge \ bigvee Y = \ bigvee \ {x \ wedge y \ mid y \ в Y \}

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

a → b = ⋁ {c ∣ a ∧ c ≤ b} {\ displaystyle a \ to b = \ bigvee \ {c \ mid a \ land c \ leq b \}}

a \ to b = \ bigvee \ {c \ mid a \ land c \ le b \}

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

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

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

x = ¬¬x.
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 следующие условия эквивалентны:

H является булевой алгеброй ;
каждый x в H регулярен;
каждый x в H является дополнено.

В этом случае элемент 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 с ∨.

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

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

∀ x, y ∈ H: ¬ ( х ∨ у) = ¬ х ∧ ¬ у. {\ displaystyle \ forall x, y \ in H: \ qquad \ lnot (x \ vee y) = \ lnot x \ wedge \ lnot y.}

\ forall x, y \ in H: \ qquad \ lnot (x \ vee y) = \ lnot x \ клин \ lnot y.

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

∀ x, y ∈ H: ¬ (x ∧ y) = ¬ ¬ (¬ x ∨ ¬ y). {\ displaystyle \ forall x, y \ in H: \ qquad \ lnot (x \ wedge y) = \ lnot \ lnot (\ lnot x \ vee \ lnot y).}

\ forall x, y \ in H: \ qquad \ lnot (x \ wedge y) = \ lnot \ lnot (\ lnot x \ vee \ lno ty).

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

H удовлетворяет обоим законам Де Моргана,
$¬ (x ∧ y) = ¬ x ∨ ¬ y для всех x, y ∈ H, {\ displaystyle \ lnot (x \ wedge y) = \ lnot x \ vee \ lnot y {\ t_dv {для всех}} x, y \ in H,}$ $\ lnot ( x \ wedge y) = \ lnot x \ vee \ lnot y \ t_dv {для всех} x, y \ в H,$
$¬ (x ∧ y) = ¬ x ∨ ¬ y для всех регулярных x, y ∈ H, {\ displaystyle \ lnot ( x \ wedge y) = \ lnot x \ vee \ lnot y {\ t_dv {для всех обычных}} x, y \ in H,}$ $\ lnot (x \ wedge y) = \ lnot x \ vee \ lnot y \ t_dv {для всех обычных} x, y \ в H,$
$¬ ¬ (x ∨ y) = ¬ ¬ x ∨ ¬ ¬ y для всех Икс, Y ∈ H, {\ Displaystyle \ lnot \ lnot (х \ vee y) = \ lnot \ lnot x \ vee \ lnot \ lnot y {\ t_dv {для всех}} x, y \ in H,}$ $\ lnot \ lnot (x \ vee y) = \ lnot \ lnot x \ vee \ lnot \ lnot y \ t_dv {для всех} x, y \ in H,$
$¬ ¬ (x ∨ y) = x ∨ y для всех обычных x, y ∈ H, {\ displaystyle \ lnot \ lnot (x \ vee y) = x \ vee y {\ t_dv {для всех обычных}} x, y \ in H,}$ $\ lnot \ lnot (x \ vee y) = x \ vee y \ t_dv {для всех обычных} x, y \ в H,$
$¬ (¬ x ∧ ¬ y) = x ∨ y для всех регулярных x, y ∈ H, {\ displaystyle \ lnot (\ lnot x \ wedge \ lnot y) = x \ vee y {\ t_dv {для всех регулярных}} x, y \ in H,}$ $\ lnot (\ lnot x \ wedge \ lnot y) = x \ vee y \ t_dv {для всех обычных} x, y \ в H,$
$¬ x ∨ ¬ ¬ x = 1 для всех x ∈ H. {\ displaystyle \ lnot x \ vee \ lnot \ lnot x = 1 {\ t_dv {для всех}} x \ in H.}$ $\ lnot x \ vee \ lnot \ lnot x = 1 \ t_dv {для всех } 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.

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

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

Определение

Даны две алгебры Гейтинга H 1 и H 2 и отображение f: H 1 → H 2, мы говорим, что ƒ морфизмом алгебр Гейтинга, если для любых элементов x и y в H 1, имеем:

$е (0) = 0, {\ displaystyle f (0) = 0,}$ $f (0) = 0,$
$f (x ∧ y) = f (x) ∧ f (y), {\ Displaystyle е (х \ земля у) = е (х) \ земля е (у),}$ ${\ displaystyle f (x \ land y) = f (x) \ land f (y),}$
$е (х ∨ у) = е (х) ∨ е (у), {\ Displaystyle f (х \ л или у) знак равно е (х) \ лор е (у),}$ ${\ displaystyle f (x \ lor y) = f (x) \ lor f (y),}$
$е (х → у) = е (х) → е (у), {\ Displaystyle е (х \ к у) = е (х) \ to f (y),}$ $е (x \ к y) = е (x) \ к f (y),$

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

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

Свойства

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

Примеры

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

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

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

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

$1 ∈ F, {\ displaystyle 1 \ in F,}$ $1 \ in F,$
$Если x, y ∈ F, тогда x ∧ y ∈ F, {\ displaystyle {\ t_dv {If}} x, y \ in F {\ t_dv {then}} x \ land y \ in F,}$ ${\ displaystyle {\ t_dv {If}} x, y \ in F {\ t_dv {then}} x \ land y \ in F,}$
$Если x ∈ F, y ∈ H и x ≤ y, то y ∈ F. {\ displaystyle {\ t_dv {If}} x \ in F, \ y \ in H, \ {\ t_dv {and}} x \ leq y {\ t_dv {then}} y \ in F.}$ $\ t_dv {Если} x \ in F, \ y \ in H, \ \ t_dv {и} x \ le y \ t_dv {then} y \ in F.$

пересечение любого набора фильтров на H снова является фильтром. Следовательно, для любого подмножества S из H существует наименьший фильтр, содержащий S. Мы называем его фильтром, порожденным с помощью S. Если Sо, F = {1}. В противном случае F равно множеству x в H таких, что существуют y 1, y 2,…, y n ∈ S с y 1 ∧ y 2 ∧… ∧ 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: H 1 → H 2 - морфизм алгебр Гейтинга. Ядро функции f, обозначаемое как ker f, - это набор f [{1}]. Это фильтр на H 1. (Следует проявлять осторожность, потому что это определение, если применить его к морфизму булевых алгебр, двойственно тому, что можно было бы назвать ядром морфизма, рассматриваемым как морфизм колец.) Согласно вышеизложенному, f индуцирует морфизм f ': H 1 / (ker f) → H 2. Это изоморфизм H 1 / (ker f) на подалгебру f [H 1 ] в H 2.

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

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

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

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

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

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

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

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

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

Алгебру Гейтинга H T, которую мы только что определили, можно рассматривать как частное от свободной алгебры Гейтинга H 0 на том же наборе переменных, применяя универсальное свойство H 0 по отношению к 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 1 - это множество всех формул вида ¬¬F → F, поскольку дополнительные аксиомы T 1 - единственные, которые нужно добавить, чтобы сделать все классические тавтологии доказуемо.

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

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

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

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

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

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

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

Примечания

См.

Ссылки

Резерфорд, Дэниел Эдвин (1965). Введение в теорию решеток. Оливер и Бойд. OCLC 224572.
F. Борсё, Справочник по категориальной алгебре 3, Энциклопедия математики и ее приложений, Vol. 53, Cambridge University Press, 1994. ISBN 0-521-44180-3 OCLC 52238554
G. Gierz, K.H. Хоффманн, К. Кеймель, Дж. Д. Лоусон, М. Мислав и Д. С. Скотт, Непрерывные решетки и области, В Энциклопедии математики и ее приложений, Том. 93, Cambridge University Press, 2003.
S. Гиларди. Свободные гейтинговые алгебры как бигейтинговые алгебры, Math. Rep. Acad. Sci. Canada 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.org.