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

Алгебра Гейтинга (псевдобулева алгебра) — импликативная решётка с наименьшим элементом ${\displaystyle 0}$.

Наряду с другими подклассами импликативных решёток впервые отмечены Скулемом в 1919 году^[1]; широкое применение получили после того, как Гейтинг в 1930 году предложил их как модель интуиционистского исчисления высказываний (так же, как булева алгебра является моделью классического исчисления высказываний). С точки зрения логики высказываний, относительное псевдодополнение ${\displaystyle a\rightarrow b}$ в решётке Гейтинга — слабейшее высказывание, для которого имеет правило вывода modus ponens (то есть ${\displaystyle (a\land (a\rightarrow b))\leqslant b}$.

Как и во всякой импликативной решётке в алгебре Гейтинга однозначно вводятся наибольший элемент:

${\displaystyle 1:=a\rightarrow a}$,

и унарная операция абсолютного псевдодополнения:

${\displaystyle \neg a:=a\rightarrow 0}$.

Булева алгебра — алгебра Гейтинга, в которой абсолютное псевдодополнение является абсолютным дополнением: ${\displaystyle a\lor \neg a=1}$ (исключённое третье) или, что эквивалентно, ${\displaystyle \neg \neg a=a}$ (двойное отрицание).

Класс алгебр Гейтинга может быть задан как многообразие алгебраических систем типа ${\displaystyle \langle L;0,\land ,\lor ,\rightarrow \rangle }$ (с сигнатурой ${\displaystyle \langle 0,2,2,2\rangle }$) конечным числом тождеств.

Пример алгебры Гейтинга — единичный отрезок ${\displaystyle [0,1]}$ с ${\displaystyle \lor =\max }$ и ${\displaystyle \land =\min }$ и относительным псевдодополнением, определяемым следующим образом: ${\displaystyle a\rightarrow b=1}$, если ${\displaystyle a\leqslant b}$ и ${\displaystyle a\rightarrow b=b}$ в ином случае. Другой важный пример — семейство подмножеств заданного множества ${\displaystyle M}$, упорядоченное по включению, оно образует полную алгебру Гейтинга; всякая её подалгебра будет топологией на ${\displaystyle M}$, кроме того, всякая топология на ${\displaystyle M}$ образует полную алгебру Гейтинга, в связи с этим полные алгебры Гейтинга играют ключевую роль в бесточечной топологии^[англ.].

Внутренняя логика элементарного топоса основана на гейтинговой алгебре подобъектов терминального объекта ${\displaystyle 1}$, упорядоченных по включению (или, эквивалентно, алгебре морфизмов из ${\displaystyle 1}$ в классификатор подобъектов).

Свойства

В алгебрах Гейтинга выполняется свойство бесконечной дистрибутивности:

${\displaystyle a\land \bigvee B=\bigvee \{a\land b\mid b\in B\}}$,

где ${\displaystyle B}$ — подмножество носителя алгебры, имеющее верхнюю грань. Если дистрибутивная решётка полна (то есть верхняя грань ${\displaystyle B}$ существует), то из выполнения свойства бесконечной дистрибутивности следует, что она является алгеброй Гейтинга. Каждая конечная дистрибутивная решётка полна, таким образом, является алгеброй Гейтинга.

Если в алгебре Гейтинга верхняя грань ${\displaystyle \bigvee A}$ существует, то выполняется тождество:

${\displaystyle \neg \bigvee A=\bigwedge \neg A}$.

Также имеет место соотношение:

${\displaystyle \neg \bigwedge A\leqslant \bigwedge \neg A}$

при условии, что соответствующие грани существуют.

В алгебрах Гейтинга действует закон тройного отрицания: ${\displaystyle \neg \neg \neg a=\neg a}$. Элемент, для которого снимается двойное отрицание (${\displaystyle \neg \neg a=a}$) называется регулярным; соответственно, алгебра Гейтинга, все элементы которой регулярны — булева.

В гейтинговых алгебрах имеет место один закон де Моргана:

${\displaystyle \neg (a\lor b)=\neg a\land \neg b}$,

вместо второго закона де Моргана выполняется более слабое соотношение:

${\displaystyle \neg (a\land b)=\neg \neg (\neg a\lor \neg b)}$.

Алгебра Гейтинга, в которой выполняются оба закона де Моргана, моделирует логику Янкова — логику из класса промежуточных логик^[англ.].

Подрешётка ${\displaystyle H_{g}}$ алгебры Гейтинга ${\displaystyle H}$, образованная всеми элементами, предшествующими ${\displaystyle g}$ (${\displaystyle H_{g}=\{a\mid a\leqslant g\}}$) является алгеброй Гейтинга с абсолютным псведодополнением ${\displaystyle \neg _{g}a=g\land \neg a}$ и относительным псевдодополнением ${\displaystyle a\rightarrow _{g}b=g\land (a\rightarrow b)}$; ${\displaystyle a\mapsto g\land a}$ является гомоморфизмом из ${\displaystyle H\rightarrow H_{g}}$, сохраняющим верхние и нижние грани (в том числе для бесконечных подмножеств).

Для всякой гейтинговой алгебры ${\displaystyle H}$ существует изоморфная ей полная алгебра Гейтинга ${\displaystyle H^{\star }}$.

Примечания

1. Thoralf Skolem, Jens Erik Fenstad. Selected works in logic. — Oslo: Universitetsforlaget, 1970. — 732 p. — ISBN 9788200061274.

Литература

• Псевдобулева алгебра — статья из Математической энциклопедии. Гришин В. Н.
• Драгалин А. Г. Математический интуиционизм. Введение в теорию доказательств. — М.: Наука, 1979. — 256 с. — (Математическая логика и основания математики).
• Плиско В. Е., Хаханян В. Х. Интуиционистская логика. — М.: Мехмат МГУ, 2009. — 159 с.
• Расёва Е., Сикорский Р. IV. Псевдобулевы алгебры // Математика метаматематики. — М.: Наука, 1972. — С. 147—170.