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

Псевдодополнение в теории решёток — бинарная операция в решётке, определяемая для элементов решётки $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 с.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.