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

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

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

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

$1:=a\rightarrow a$,

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

$\neg a:=a\rightarrow 0$.

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

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

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

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

Свойства

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

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

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

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

$\neg \bigvee A=\bigwedge \neg A$.

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

$\neg \bigwedge A\leqslant \bigwedge \neg A$

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

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

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

$\neg (a\lor b)=\neg a\land \neg b$,

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

$\neg (a\land b)=\neg \neg (\neg a\lor \neg b)$.

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

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

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

Литература

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