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

В математике решётка называется импликативной, если для каждых двух элементов a и b существует псевдодополнение a относительно b (обозначение: $a\to b$), определяемое следующим образом:

$a\to b=\max\{c:a\cdot c\leqslant b\}$.

Формальное определение

Множество с заданными бинарными операциями $\cdot$, $+$, $\to$ и бинарным отношением $\leqslant$ называется импликативной решеткой, если выполнены аксиомы:

1. $\forall a(a\leqslant a)$
2. $\forall a,b(a\leqslant b\land a\leqslant a\Rightarrow a=b)$
3. $\forall a,b,c(a\leqslant b\land b\leqslant c\Rightarrow a\leqslant c)$
4. $\forall a,b(a\leqslant a+b)$
5. $\forall a,b(b\leqslant a+b)$
6. $\forall a,b,c(a\leqslant c\land b\leqslant c\Rightarrow a+b\leqslant c)$
7. $\forall a,b(a\cdot b\leqslant a)$
8. $\forall a,b(a\cdot b\leqslant b)$
9. $\forall a,b,c(c\leqslant a\land c\leqslant b\Rightarrow c\leqslant a\cdot b)$
10. $\forall a,b(a\cdot (a\to b)\leqslant b)$
11. $\forall a,b,c(a\cdot c\leqslant b\Rightarrow c\leqslant (a\to b))$.

Импликативная решётка получается из обычной решетки присоединением двух последних аксиом.

Свойства

• Всякая импликативная решётка являются полугруппой с делением, в которой левому и правому делению $a\backslash b$ и $b/a$ соответствует одна операция $a\to b$.
• Всякая импликативная решётка дистрибутивна.
• Во всякой импликативной решётке имеется максимальный элемент ($a\to a$), обычно обозначаемый как 1.
• Если в импликативной решетке есть наименьший элемент, обычно обозначаемый как 0, то такая решетка называется алгеброй Гейтинга или псевдобулевой алгеброй.
• Для всех элементов $a$, $b$ и $c$ всякой импликативной решётки верны следующие утверждения:

1. $a\leqslant b\Rightarrow b\to c\leqslant a\to c$;
2. $a\leqslant b\Rightarrow c\to a\leqslant c\to b$;
3. $a\leqslant b\to c\Rightarrow a\cdot b\leqslant c$;
4. $a\to b=1\Leftrightarrow a\leqslant b$;
5. $b\leqslant a\to b$;
6. $a\to b\leqslant ((a\to (b\to c))\to (a\to c))$;
7. $a\leqslant b\to a\cdot b$;
8. $a\to c\leqslant (b\to c)\to (a+b\to c)$.

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

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

См. также

• булева алгебра
• алгебра Гейтинга
• решётка

Литература

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