grids.tex

\section{Решётки}

% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
% Материал законспектирован по лекции:                                                                  %
% https://www.youtube.com/watch?v=pTrT_0KqkbA&list=PLd7QXkfmSY7Zek3Zj2K0Knf-5ZqWUqTLw&index=4&t=1440s   %
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %


\textbf{Частичным порядком} называют транзитивное, рефлексивное и антисимметричное отношение. В дальнейшем будем записывать $a \leq b$ если $a$ и $b$ состоят в этом отношении.\\

\textit{Пример частично упорядоченного множества: комплексные числа, с порядком $a \leq b \Leftrightarrow |a| \leq |b|$. Таким образом числа, имеющий одинаковый модуль, не сравнимы между собой. Легко проверить, что свойства частичного порядка выполняются.}\\

\noindent\textbf{Линейным порядком} называют частичный порядок, который определён для любых $a$ и $b$, то есть $a \leq b \vee b \leq a$.\\

\noindent\textbf{Наименьший элемент $S$} "--- элемент $k \in S$, что если $x \in S$, то $k \leq x$.\\

\noindent\textbf{Минимальный элемент $S$} "--- элемент $k \in S$, что нет $x \in S$, отличного от $k$, что $x \leq k$.\\

\noindent Аналогичным образом определяются \textbf{наибольший} и \textbf{максимальный} элементы.\\

\noindent\textbf{Множеством верхних граней $a$ и $b$} называют $\left{\{}x | a \leq x \And b \leq x\right{\}}$. Аналогично определяется и \textbf{множество нижних граней}. \\

\noindent\textbf{Определение операций:}
\begin{itemize}
    \item $a + b$ "--- наименьший элемент множества верхних граней;
    \item $a \cdot b$ "--- наибольший элемент множества нижних граней.
\end{itemize}

Если представлять себе частичный порядок как дерево, идущее от наибольших элементов сверху вниз к наименьшим, то $a + b$ это \textit{наименьший общий предок (LCA)} $a$ и $b$, а $a \cdot b$ это \textit{наибольший общий потомок}.\\

\noindent\textbf{Решётка} это множество $A$ с определённым на нём частичным порядком $\leq$, такое, что для любых $a$ и $b$ определёно как значение $a+b$, так и значение $a \cdot b$.\\

\noindent\textbf{Дистрибутивная решётка} это решётка, для которой при любых $a$, $b$ и $c$ верно равенство $a \cdot (b + c) = a \cdot b + a \cdot c$.

\begin{lemma}{О дистрибутивных решётках}
В дистрибутивной решетке $a + b \cdot c = (a + b) \cdot (a + c)$
\end{lemma}

\noindent\textbf{Псевдодополнение} (записывается как $a\to b$) это такой наибольший элемент $c$, что верно $a \cdot c \leq b$.\\

\noindent\textbf{Импликативная решётка} "--- решётка, в которой для любых $a$ и $b$ определёно значение $a \to b$.\\

\noindent Обозначим как $0$ наименьший элемент решётки и как $1$ "--- наибольший элемент решётки.\\

\noindent\textbf{Псевдобулева алгебра}, чаще называемая \textbf{алгеброй Гейтинга} это импликативная решётка с $0$.\\

\noindent\textbf{Булева алгебра} это псевдобулева алгебра, в которой для любого $a$ выполнено $a + (a \to 0) = 1$.\\

\noindent\textit{Можно заметить, что псевдобулева алгебра является моделью для интуиционистской логики, а булева "--- для классической.}

\begin{lemma}{Об импликативной решётке}
В любой непустой импликативной решётке всегда есть $1$.
\end{lemma}

\begin{proof}
Решётка непустая, значит можно взять произвольный элемент $a$ и рассмотреть $b = a \to a$. По определению, $b$ является наибольшим элементом среди $x$, для которых истинно $a \cdot x \leq a$. Очевидно, что это истинно для любого $x \in A$, значит $b = 1$. Таким образом, $A$ имеет наибольший элемент, и он равен $a\to a$.
\end{proof}

\begin{theorem}
Любая алгебра Гейтинга "--- модель ИИВ.
\end{theorem}
\begin{theorem}
Любая булева алгебра "--- модель КИВ.
\end{theorem}

\noindent Упорядоченную пару $<X, \Omega>$, где $X$ "--- <<носитель>>, а $\Omega$ "--- подмножество множества всех подмножеств $X$ называют \textbf{топологией}, если выполнены следующие свойства:
\begin{enumerate}
    \item Для $v_i \in \Omega$ верно, что $\cup v_i \in \Omega$;
    \item Для $v_i \in \Omega$ верно, что $v_1 \cap v_2 \cap \ldots \cap v_n \in \Omega$;
    \item $\varnothing, X \in \Omega$.
\end{enumerate}

\noindent Операцией \textbf{взятия внутренности} для множества $x$ будем называть $x^{\circ}$, равную наибольшему по включению множеству $w$, такому что $w \subseteq x$ и $w \in \Omega$.

\begin{theorem}{Об эквивалентности топологии и алгебры Гейтинга}
Введём обозначения для топологии:
\begin{itemize}
    \item $a + b$ эквивалентно $a \cup b$;
    \item $a \cdot b$ эквивалентно $a \cap b$;
    \item $a \to b$ эквивалентно $\left( (X \setminus a) \cup b \right)^{\circ}$;
    \item $a \leq b$ эквивалентно $a \subseteq b$.
\end{itemize}

Тогда $<\Omega, \leq>$ является алгеброй Гейтинга.
\end{theorem}

\noindent\textbf{Алгеброй Линденбаума} называется алгебра Гейтинга на фактормножестве (\textit{напоминание: фактормножество это множество, состоящие из классов эквивалентности по заданному отношению эквивалентности}) всех формул интуиционистской логики по отношению $a \vdash b$ и $b \vdash a$, порядок на которых будет задано следующим образом: $a \leq b$ если $a \vdash b$.

\begin{theorem}
Алгебры Гейтинга "--- полная модель интуиционистской логики.

\textit{Замечание: важно обратить внимание на то, что именно совокупность всех алгебр Гейтинга является полной моделью интуиционистской логики.}
\end{theorem}

\begin{proof}
$\models a$ означает, что $a$ истинно в каждой алгебре Гейтинга. Раз оно истинно в любой алгебре Гейтинга, то истинно и в алгебре Линденбаума. Значит,\\ $\llbracket a \rrbracket = 1 = \llbracket A \to A \rrbracket$, то есть $a$ лежит в том же классе эквивалентности, что и $A \to A$, а значит, по определению, $A \to A \vdash a$. Отсюда несложно следует доказуемость $a$. 
\end{proof}