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

Диаграмма Хассе, состоящая из 4 элементов: $a$ и $a$, максимального элемента $a\vee b$, минимального элемента $a\wedge b$

Алгебра Гейтинга (псевдобулева алгебра) — ограниченная решётка (с операциями взятия наименьшей верхней грани $\lor$, наибольшей нижней грани $\land$, с наименьшим элементом $0$, наибольшим элементом $1$ и бинарной операцией $a\rightarrow b$ импликации, такой, что $(c\land a)\leqslant b$ эквивалентно $c\leqslant (a\rightarrow b)$.

Впервые решётки с относительным псевдодополнением, в том числе с минимальным элементом, изучил Скулем в 1919 году; широкое применение получили после того, как Аренд Гейтинг в 1930 году формализовал их средствами интуиционистскую логику высказываний. С логической точки зрения, $A\rightarrow B$ в рамках такого определения — слабейшее высказывание, для которого имеет modus ponens (из $A\rightarrow B$ и следует, что из $A$ выводится $B$).

Алгебра Гейтинга является дистрибутивной решёткой. Каждая булева алгебра является алгеброй Гейтинга, когда $a\rightarrow b$ определяется как $\neg a\lor b$, как и каждая полная дистрибутивная решётка, удовлетворяющая одностороннему бесконечному дистрибутивному закону, когда $a\rightarrow b$ принимается за максимум множества всех $c$, для которых $c\land a\leqslant b$. В конечномерном случае каждая непустая дистрибутивная решётка, в частности, каждая непустая конечная цепочка, автоматически является полной и полностью дистрибутивной, а значит, алгеброй Гейтинга.

Из определения следует, что $1\leqslant 0\rightarrow a$, что соответствует интуиции, согласно которой из любого предложения а следует противоречие $0$. Хотя операция отрицания $\neg a$ не входит в определение, её можно определить как $a\rightarrow 0$. Интуитивное содержание $\neg a$ состоит в том, что предположение $a$ приводит к противоречию. Определение подразумевает, что $a\land \neg a=0$. Далее можно показать, что $a\leqslant \neg \neg a$, в общем случае не верно, то есть устранение двойного отрицания в алгебре Гейтинга вообще не выполняется.

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

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

Как и булевы алгебры, алгебры Гейтинга образуют аксиоматизируемое многообразие с конечным числом уравнений.

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

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

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

Алгебра Гейтинга $H$ — это ограниченная решётка, такая, что для всех $a$ и $b$ в $H$ существует наибольший элемент $x$ из $H$, такой, что $$a\land x\leqslant b$$Этот элемент является относительным псевдодополнением $a$ относительно $b$ и обозначается $a\rightarrow b$. Мы пишем 1 и 0 для самого большого и самого маленького элемента $H$, соответственно.

В любой алгебре Гейтинга можно определить псевдодополнение $\neg a$ любого элемента $a$, задав $\neg a=(a\rightarrow 0)$. По определению, $a\land \neg a=0$ и $\neg a$ — наибольший элемент, обладающий этим свойством. Однако в общем случае неверно, что $a\lor \neg a=1$, поэтому $\neg$ является лишь псевдодополнением, а не истинным дополнением, как это было бы в булевой алгебре.

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

Подалгеброй алгебры Гейтинга $H$ называется подмножество $H_{1}$ из $H$, содержащее 0 и 1, и замкнутое по операциям $\land$, $\lor$ и $\rightarrow$. Отсюда следует, что оно также замкнуто под $\neg$. Подалгебра преобразуется в алгебру Гейтинга с помощью индуцированных операций.

Литература

• Псевдобулева алгебра — статья из Математической энциклопедии. В. Н. Гришин
• Драгалин А. Г. Математический интуиционизм. Введение в теорию доказательств. — М.: Наука, 1979. — 256 с. — (Математическая логика и основания математики).