Введение

В математике алгебра Хейтинга (также известная как псевдобулева алгебра) — это ограниченная решетка (с операциями объединения и пересечения, записываемыми ∨ и ∧, с наименьшим элементом 0 и наибольшим элементом 1), снабженная бинарной операцией a → b импликации, такой что (c ∧ a) ≤ b эквивалентно c ≤ (a → b). С логической точки зрения, A → B по этому определению является самым слабым утверждением, для которого modus ponens, правило вывода A → B, A ⊢ B, является корректным. Как и булевы алгебры, алгебры Хейтинга образуют многообразие, аксиоматизируемое конечным числом уравнений. Алгебры Хейтинга были введены для формализации интуиционистской логики. Алгебры Хейтинга являются дистрибутивными решетками. Каждая булева алгебра является алгеброй Хейтинга, когда 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 в классификатор субобъектов Ω. Открытые множества любого топологического пространства образуют полную алгебру Хейтинга. Таким образом, полные алгебры Хейтинга становятся центральным объектом изучения в бесточечной топологии. Каждая алгебра Хейтинга, множество негоризонтальных элементов которой имеет наибольший элемент (и образует другую алгебру Хейтинга), является субдиректно неприводимой, следовательно, каждая алгебра Хейтинга может быть сделана субдиректно неприводимой путем присоединения нового наибольшего элемента. Из этого следует, что даже среди конечных алгебр Хейтинга существует бесконечно много субдиректно неприводимых, ни у одной из которых нет одной и той же теории уравнений. Следовательно, ни одно конечное множество конечных алгебр Хейтинга не может предоставить все контрпримеры к не законам алгебры Хейтинга. Это резко контрастирует с булевыми алгебрами, единственной субдиректно неприводимой из которых является двухэлементная, которая сама по себе достаточна для всех контрпримеров к не законам булевой алгебры, что является основой для простого метода таблицы истинности. Тем не менее, можно решить, выполняется ли уравнение для всех алгебр Хейтинга. Алгебры Хейтинга реже называют псевдобулевыми алгебрами или даже решетками Брауэра, хотя последний термин может обозначать двойное определение или иметь немного более общее значение.

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

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

Свойства

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

Примеры

При заданной алгебре Хейтинга H и любой её субальгебре H1, отображение включения 1=i : H1 → H является морфизмом. Для любой алгебры Хейтинга H отображение 1=x ↦ ¬¬x определяет морфизм из H на булеву алгебру своих регулярных элементов Hreg. В общем случае это не морфизм из H в себя, поскольку операция объединения в Hreg может отличаться от операции объединения в H.

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

Пусть H – алгебра Гейтинга, и пусть 1=F ⊆ H. Мы называем F фильтром на H, если он удовлетворяет следующим свойствам: пересечение любого множества фильтров на H снова является фильтром. Следовательно, для любого подмножества S из H существует наименьший фильтр, содержащий S. Мы называем его фильтром, порожденным S. Если S пусто, то 1=F = {1}. В противном случае F равно множеству x в H, такому что существуют 1=y1, y2, …, yn ∈ S, с условием 1=y1 ∧ y2 ∧ … ∧ yn ≤ x. Если H – алгебра Гейтинга и F – фильтр на H, мы определяем отношение ~ на H следующим образом: мы пишем 1=x ~ y, когда 1=x → y и 1=y → x оба принадлежат F. Тогда ~ является отношением эквивалентности; мы пишем 1=H/F для фактормножества. Существует единственная структура алгебры Гейтинга на 1=H/F, такая что каноническая сюръекция 1=pF : H → H/F становится морфизмом алгебры Гейтинга. Мы называем алгебру Гейтинга 1=H/F фактор-алгеброй H по F.

Пусть S – подмножество алгебры Гейтинга H, и пусть F – фильтр, порожденный S. Тогда H/F удовлетворяет следующему универсальному свойству: для любого морфизма алгебр Гейтинга f, удовлетворяющего условию 1=f(y) = 1 для каждого 1=y ∈ S, f однозначно факторизуется через каноническую сюръекцию 1=pF : H → H/F. То есть, существует единственный морфизм g, такой что f = g ∘ pF. Морфизм g называется индуцированным f.

Пусть 1=f : H1 → H2 – морфизм алгебр Гейтинга. Ядро f, обозначаемое ker f, – это множество 1=f−1[{1}]. Это фильтр на H1. (Следует быть осторожным, поскольку это определение, применительно к морфизму булевых алгебр, двойственно тому, что называется ядром морфизма, рассматриваемого как морфизм колец.) В силу вышесказанного, f индуцирует морфизм g, который является изоморфизмом 1=H1/(ker f) на подалгебру f[H1] в H2.

Свободная алгебра Хейтинга на произвольном наборе генераторов

В действительности, описанная выше конструкция может быть выполнена для любого множества переменных {Ai : i∈I} (возможно, бесконечного). Таким образом получается свободная алгебра Хейтинга над переменными {Ai}, которую мы снова обозначим как H0. Она является свободной в том смысле, что для любой алгебры Хейтинга H, заданной вместе с семейством её элементов 〈ai : i∈I〉, существует единственный морфизм f: H0 → H, удовлетворяющий условию f([Ai]) = ai. Уникальность f очевидна, а её существование по сути вытекает из метаимпликации 1 ⇒ 2 из раздела "Доказуемые тождества", представленной в виде её следствия: если формулы F и G доказуемо эквивалентны, то F(〈ai〉) = G(〈ai〉) для любого семейства элементов 〈ai〉 в H.

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

При наличии множества формул T в переменных {Ai}, рассматриваемых как аксиомы, та же конструкция могла быть выполнена в отношении отношения F≼G, определенного на L, означающего, что G является доказуемым следствием F и множества аксиом T. Обозначим HT алгеброй Гейтинга, полученной таким образом. Тогда HT удовлетворяет тому же универсальному свойству, что и H0, но в отношении алгебр Гейтинга H и семейств элементов 〈ai〉, удовлетворяющих свойству J(〈ai〉)=1 для любой аксиомы J(〈Ai〉) в T. (Отметим, что HT, рассматриваемый вместе с семейством своих элементов 〈[Ai]〉, сам удовлетворяет этому свойству.) Существование и единственность морфизма доказываются тем же способом, что и для H0, за исключением того, что необходимо изменить метаимпликацию 1 ⇒ 2 в разделе "Доказуемые тождества" так, чтобы 1 звучало как "доказуемо истинно из T", а 2 – как "любые элементы a1, a2, ..., an в H, удовлетворяющие формулам T".

Алгебра Гейтинга HT, которую мы только что определили, может рассматриваться как фактор-алгебра свободной алгебры Гейтинга H0 на том же наборе переменных, полученная путем применения универсального свойства H0 относительно HT и семейства ее элементов 〈[Ai]〉. Каждая алгебра Гейтинга изоморфна алгебре вида HT. Чтобы увидеть это, пусть H – произвольная алгебра Гейтинга, а 〈ai: i∈I〉 – семейство элементов, порождающих H (например, любое сюръективное семейство). Теперь рассмотрим множество T формул J(〈Ai〉) в переменных 〈Ai: i∈I〉, таких что J(〈ai〉)=1. Тогда, благодаря универсальному свойству HT, мы получаем морфизм f: HT→H, который явно сюръективен. Несложно показать, что f инъективен.

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

Конструкции, которые мы только что представили, играют совершенно аналогичную роль по отношению к алгебрам Хейтинга, какую алгебры Линденбаума играют по отношению к булевым алгебрам. Фактически, алгебра Линденбаума BT в переменных {Ai} относительно аксиом T является просто нашим HT∪T1, где T1 – множество всех формул вида ¬¬F→F, поскольку дополнительные аксиомы T1 – единственные, которые нужно добавить, чтобы все классические тавтологии стали доказуемыми.

Алгебры Хейтинга, применяемые к интуиционистской логике

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

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

Проблема о том, выполняется ли данное уравнение во всех алгебрах Хейтинга, была решена Соулом Крипке в 1965 году. Следовательно, она по крайней мере столь же сложна, как решение уравнений булевой алгебры (доказано, что она coNP-полна в 1971 году Стивеном Куком), и предполагается, что она значительно сложнее. Элементарная, или теория первого порядка, алгебр Хейтинга неразрешима. Остаётся открытым вопрос о том, является ли универсальная теория Хорна для алгебр Хейтинга, или проблема слов, разрешимой. Что касается проблемы слов, известно, что алгебры Хейтинга не локально конечны (нет алгебры Хейтинга, порождённой конечным непустым множеством, которая была бы конечной), в отличие от булевых алгебр, которые локально конечны и для которых проблема слов разрешима. Неизвестно, существуют ли свободные полные алгебры Хейтинга, за исключением случая единственного образующего, когда свободная алгебра Хейтинга с одним образующим тривиально дополняется до полной посредством добавления новой верхней границы.