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

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

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

• $\forall a,b:a\land (a\to b)\leqslant b$,
• $\forall a,b,c:a\land c\leqslant b\Rightarrow c\leqslant (a\to b)$.

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

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

Свойства

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

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

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

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

• $a\leqslant b\Rightarrow b\to c\leqslant a\to c$;
• $a\leqslant b\Rightarrow c\to a\leqslant c\to b$;
• $a\leqslant b\to c\Rightarrow a\land b\leqslant c$;
• $a\to b=1\Leftrightarrow a\leqslant b$;
• $b\leqslant a\to b$;
• $a\to b\leqslant ((a\to (b\to c))\to (a\to c))$;
• $a\leqslant b\to a\land b$;
• $a\to c\leqslant (b\to c)\to (a\lor b\to c)$.

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

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

Литература

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