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

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

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

$\mathrm{\forall }a,b:a\wedge (a\to b)⩽b$,

$\mathrm{\forall }a,b,c:a\wedge c⩽b\Rightarrow c⩽(a\to b)$.

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

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

Свойства

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

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

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

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

$a⩽b\Rightarrow b\to c⩽a\to c$;

$a⩽b\Rightarrow c\to a⩽c\to b$;

$a⩽b\to c\Rightarrow a\wedge b⩽c$;

$a\to b=1\iff a⩽b$;

$b⩽a\to b$;

$a\to b⩽((a\to (b\to c))\to (a\to c))$;

$a⩽b\to a\wedge b$;

$a\to c⩽(b\to c)\to (a\vee b\to c)$.

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

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

Литература

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