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

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

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

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

$1:=a\to a$,

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

$\mathrm{\neg }a:=a\to 0$.

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

Класс алгебр Гейтинга может быть задан как многообразие алгебраических систем типа $⟨L;0,\wedge ,\vee ,\to ⟩$ (с сигнатурой $⟨0,2,2,2⟩$) конечным числом тождеств.

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

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

Свойства

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

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

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

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

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

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

$\mathrm{\neg }\bigwedge A⩽\bigwedge \mathrm{\neg }A$

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

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

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

$\mathrm{\neg }(a\vee b)=\mathrm{\neg }a\wedge \mathrm{\neg }b$,

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

$\mathrm{\neg }(a\wedge b)=\mathrm{\neg }\mathrm{\neg }(\mathrm{\neg }a\vee \mathrm{\neg }b)$.

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

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

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

Литература

• Шаблон:Из
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга