WikiSort.ru - Не сортированное

Псевдодополнение в теории решёток — бинарная операция в решётке, определяемая для элементов решётки ${\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}$ ; в этом случае, бинарное псевдодополнение называется относительным псевдодополнением.

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

Свойства

Импликативные решётки являются полугруппами с делением, в которых левому и правому делению ${\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 с.