Псевдодополнение

Псевдодополнение в теории решёток — бинарная операция в решётке, определяемая для элементов решётки ${\displaystyle a}$ и ${\displaystyle b}$ как наибольший элемент ${\displaystyle c}$ такой, что ${\displaystyle a\land c\leqslant b}$; обозначение — ${\displaystyle a\to b}$, прочтение — «псевдодополнение ${\displaystyle a}$ относительно ${\displaystyle b}$». Импликативная решётка (или брауэрова решётка) — решётка, в которой для каждых двух элементов существует псевдодополнение.

Аксиоматически, импликативная решётка получается присоединением к аксиомам решётки следующих соотношений:

${\displaystyle \forall a,b:a\land (a\to b)\leqslant b}$,

${\displaystyle \forall a,b,c:a\land c\leqslant b\Rightarrow c\leqslant (a\to b)}$.

Для импликативных решёток с нулём вводится также унарная операция (абсолютного) псевдодополнения: ${\displaystyle ^{\sim }a=a\to 0}$; в этом случае, бинарное псевдодополнение называется относительным псевдодополнением.

Импликативные решётки образуют многообразие. Важнейшие специальные классы импликативных решёток — алгебры Гейтинга и булевы алгебры, используемые в качестве моделей интуиционистского и классического исчисления высказываний соответственно.

Импликативные решётки являются полугруппами с делением, в которых левому и правому делению ${\displaystyle a\backslash b}$ и ${\displaystyle b/a}$ соответствует одна операция ${\displaystyle a\to b}$.

Всякая импликативная решётка дистрибутивна; каждая конечная дистрибутивная решётка — импликативна.

Во всякой импликативной решётке имеется максимальный элемент (${\displaystyle a\to a}$), обычно обозначаемый как 1; минимальный элемент в общем случае может не существовать, если он существует — то импликативная решётка образует алгебру Гейтинга.

Для всех элементов ${\displaystyle a}$, ${\displaystyle b}$ и ${\displaystyle c}$ всякой импликативной решётки верны следующие утверждения:

${\displaystyle a\leqslant b\Rightarrow b\to c\leqslant a\to c}$;

${\displaystyle a\leqslant b\Rightarrow c\to a\leqslant c\to b}$;

${\displaystyle a\leqslant b\to c\Rightarrow a\land b\leqslant c}$;

${\displaystyle a\to b=1\Leftrightarrow a\leqslant b}$;

${\displaystyle b\leqslant a\to b}$;

${\displaystyle a\to b\leqslant ((a\to (b\to c))\to (a\to c))}$;

${\displaystyle a\leqslant b\to a\land b}$;

${\displaystyle a\to c\leqslant (b\to c)\to (a\lor b\to c)}$.

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

Подмножество ${\displaystyle \nabla }$ импликативной решётки ${\displaystyle A}$ является её фильтром тогда и только тогда, когда ${\displaystyle 1\in \nabla }$ и ${\displaystyle (a\in \nabla ,a\to b\in \nabla )\Rightarrow b\in \nabla }$; если ${\displaystyle \nabla }$ — фильтр, то факторрешётка ${\displaystyle A/\nabla }$ импликативна, а класс ${\displaystyle \nabla }$ — её максимальный элемент.

• В. Е. Плиско, В. Х. Хаханян. Интуиционистская логика. — М.: Изд-во при мех.-мат. ф-те МГУ, 2009. — 159 с.