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

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

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

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

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

Свойства

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

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

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

В алгебрах Гейтинга действует закон тройного отрицания: $\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)$.

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

Литература

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