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

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

Алгебра Гейтинга, также известная как псевдобулева алгебра — ограниченная решётка (с операциями соединения (англ.яз join) и встречи (англ.яз meet), записываемые как $\lor$ и $\land$, с наименьшим элементом $0$ и наибольшим элементом $1$) с бинарной операцией $a\rightarrow b$ импликации, такой, что $(c\land a)\leq b$ эквивалентно $c\leq (a\rightarrow b)$. С логической точки зрения, $A\rightarrow B$ — это, согласно этому определению, самая слабая пропозиция, для которой действует modus ponens, правило вывода $A\rightarrow B$, $A\vdash B$. Как и булевы алгебры, алгебры Гейтинга образуют аксиоматизируемое многообразие с конечным числом уравнений. Алгебры Гейтинга были введены Арендом Гейтингом (1930) для формализации интуиционистской логики.

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

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

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

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

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

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

Реже алгебры Гейтинга называют псевдобулевыми алгебрами или даже решетками Брувера, хотя последний термин может обозначать двойственное определение или иметь несколько более общее значение.

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

Алгебра Гейтинга $H$ — это ограниченная решётка, такая, что для всех $a$ и $b$ в $H$ существует наибольший элемент $x$ из $H$, такой, что $$a\land x\leq 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$. Подалгебра превращается в алгебру Гейтинга с помощью индуцированных операций.