%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Lattices}

{\bf Definition:} A lattice is a partial order in which every two-element set has a least upper bound and a greatest lower bound (so, we have $\sqcap$ and $\sqcup$ as well-defined binary operations).

%Note: if you know that you have least upper bounds for all sets, it follows that you also have greatest lower bounds.
%
%{\bf Proof:} by taking the least upper bound of the lower bounds. Converse also holds, dually.
%\vspace{10pt}\\
{\bf Lemma:} In every lattice, $x \sqcup (x \sqcap y) = x$.
\vspace{10pt}\\

\pause
{\bf Proof:} \\
We trivially have $x \sqsubseteq x \sqcup (x \sqcap y)$.\\
Let's prove that $x \sqcup (x \sqcap y) \sqsubseteq x$:\\
$x$ is an upper bound of $x$ and $x \sqcap y$, $x \sqcup (x \sqcap y)$ is the least upper bound of $x$ and $x \sqcap y$, thus $x \sqcup (x \sqcap y) \sqsubseteq x $.

{\bf Definition:} A lattice is \emph{distributive} iff
\[
\begin{array}{l}
    x \sqcap (y \sqcup z) = (x \sqcap y) \sqcup (x \sqcap z) \\
    x \sqcup (y \sqcap z) = (x \sqcup y) \sqcap (x \sqcup z)
\end{array}
\]

Lattice of all subsets of a set is distributive.  Linear order is a distributive lattice.
\end{frame}

%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Products of Lattices}
{\bf Note:} for $n=2$ a function $f : \{1,2\} \to (L_1 \cup L_2)$ with $f(1) \in L_1$, $f(2) \in L_2$ is isomorphic to an ordered pair $(f(1),f(2))$. We denote the product by
$(L_1,\le_1) \times (L_2,\le_2)$.

{\bf Example:} Let $R=\{a,b,c,d\}$ denote set of values. Let $A_1 = A_2 = 2^R$. Let
\[
   s_1 \leq_1 s_2 \iff  s_1 \subseteq s_2
\]
and let
\[
   t_1 \leq_2 t_2 \iff  t_1 \supseteq t_2
\]
Then we can define the product $(A_1,\le_1)\times (A_2,\le_2)$. In this product, $(s_1,t_1) \le (s_2,t_2)$ iff: $s_1 \subseteq s_2$ and $t_1 \supseteq t_2$. The original partial orders were lattices, so the product is also a lattice. For example, we have
\[
    (\{a,b,c\},\{a,b,d\}) \sqcap (\{b,c,d\},\{c,d\}) = (\{b,c\}, \{a,b,c,d\})
\]
\end{frame}


\begin{frame}
\frametitle{Products of Lattices}
Lattice elements can be combined into finite or infinite-dimensional vectors, and the result is again a lattice.

{\bf Lemma:} Let $(A_1,\le_1), \ldots, (A_n, \le_n)$ be partial orders. Define $(L,\le)$ by
\[
    A = \{ f \mid  f : \{1,\ldots,n\} \to (A_1 \cup \ldots \cup A_n) \mbox{ where } \forall i. f(i) \in A_i \}
\]
For $f,g\in A$ define
\[
    f \leq g   \iff   \forall i. f(i) \le_i g(i)
\]
Then $(A,\le)$ is a partial order. We denote $(A,\le)$ by
\[
   \prod_{i=1}^n (L_i,\le_i)
\]
Moreover, if for each $i$, $(A_i,\le_i)$ is a lattice, then $(A,\le)$ is also a lattice.

Note: this is a special case of Feferman-Vaught theorem (Feferman was a student of Tarski and wrote
a very interesting biography of Tarski).
\end{frame}



%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Properties of $\sqcap S$ and $\sqcup S$}

Consider a partial order $(A,\sqsubseteq)$.
\begin{itemize}
\item Suppose $S_1 \subseteq S_2 \subseteq A$ and $\sqcup S_1$ and $\sqcup S_2$ exist.
In what relationship are these two elements?
\item Suppose $S_1 \subseteq S_2 \subseteq A$ and $\sqcap S_1$ and $\sqcap S_2$ exist.
In what relationship are these two elements?
\item Suppose $\sqcup \emptyset$ exists. Describe this element.
\item Suppose $\sqcap \emptyset$ exists. Describe this element.
\end{itemize}

\pause
$\sqcup \emptyset = \bot$ and $\sqcap \emptyset = \top$. This is because every element is an upper bound and a lower bound of $\emptyset$ : $\forall x. \forall y \in \emptyset. y \sqsubseteq x$ is valid, as well as $\forall x. \forall y \in \emptyset. y \sqsupseteq x$.

\end{frame}



\begin{frame}
\frametitle{Complete Semilattice is a Complete Lattice}

If we have all $\sqcap$-s we then also have all $\sqcup$-s:

\textbf{Theorem:}
Let $(A,\sqsubseteq)$ be a partial order such that every set $S \subseteq A$ has the greatest lower bound ($\sqcap$). Prove that then every set $S \subseteq A$ has the least upper bound ($\sqcup$).

\end{frame}

\begin{frame}
\frametitle{Example: Application of the Previous Theorem}

Let $U$ be a set and $A \subseteq U \times U$ 
the set of all \textbf{equivalence relations} on this set. Consider the partial order 
$(A,\subseteq)$.

\ \\

\begin{lemma}
If $I \subseteq A$ is a set of equivalence relations, then $\cap I$ is also an equivalence relation.
\end{lemma}

\ \\

\textbf{Consequence:} Given $I \subseteq A$ there exists the least equivalence relation containing every
relation from $I$ (equivalence closure of relations in $I$).

\ \\

Note: \textbf{congruence} is equivalence relation that agrees with some operations. For example,
$x \sim x'$ and $y \sim y'$ implies $(x+y) \sim (x' + y')$. The analogous properties hold
for congruence relations.

\end{frame}

%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Complete Lattices}
{\bf Definition:} A {\bf complete} lattice is a lattice where for every set $S$ (including empty set and infinite sets) there exist $\sqcup S$ and $\sqcap S$.

\end{frame}


%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Monotonic functions}
Given two partial orders $(C,\le)$ and $(A,\sqsubseteq)$, we call a function $\alpha : C \to A$
 {\em monotonic} iff for all $x, y \in C$,
\begin{equation*}
  x \leq y\ \rightarrow\ \alpha (x) \sqsubseteq \alpha (y)
\end{equation*}
\end{frame}

