path: root/info/examples/mil3/sampartb.tex

% Sample file: sampartb.tex
% The sample article for the amsart document class with BibTeX 
% Typeset with LaTeX format 

\documentclass{amsart}
\usepackage{amssymb,latexsym}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem*{main}{Main~Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}

\theoremstyle{definition}
\newtheorem{definition}{Definition}

\theoremstyle{remark}
\newtheorem*{notation}{Notation}

\numberwithin{equation}{section}

\begin{document}
\title[Complete-simple distributive lattices]
      {A construction of complete-simple\\  
       distributive lattices}
\author{George~A. Menuhin}
\address{Computer Science Department\\
         University of Winnebago\\
         Winnebago, MN 53714} 
\email{menuhin@ccw.uwinnebago.edu}
\urladdr{http://math.uwinnebago.edu/homepages/menuhin/}
\thanks{Research supported by the NSF under grant number
23466.}  
\keywords{Complete lattice, distributive lattice,
   complete congruence, congruence lattice} 
\subjclass[2000]{Primary: 06B10; Secondary: 06D05}
\date{March 15, 1999}
\begin{abstract}
   In this note we prove that there exist \emph{complete-simple distributive
   lattices,} that is, complete distributive lattices in which there are 
   only two complete congruences. 
\end{abstract}

\maketitle

\section{Introduction}\label{S:intro} 
In this note we prove the following result:

\begin{main} 
   There exists an infinite complete distributive lattice~$K$ with only 
   the two trivial complete congruence relations.
\end{main}

\section{The $D^{\langle 2 \rangle}$ construction}\label{S:Ds} 
For the basic notation in lattice theory and universal algebra, see Ferenc~R.
Richardson~\cite{fR82} and George~A. Menuhin~\cite{gM68}.  We start with some
definitions:

\begin{definition}\label{D:prime}
   Let $V$ be a complete lattice, and let $\mathfrak{p} = [u, v]$ be
   an interval of $V$.  Then $\mathfrak{p}$ is called 
   \emph{complete-prime} if the following three conditions are satisfied:
   \begin{enumerate}
      \item $u$ is meet-irreducible but $u$ is \emph{not}
         completely meet-irreducible;
      \item $v$ is join-irreducible but $v$ is \emph{not} 
         completely join-irreducible;
      \item $[u, v]$ is a complete-simple lattice.
   \end{enumerate}
\end{definition}

Now we prove the following result:

\begin{lemma}\label{L:ds} 
   Let $D$ be a complete distributive lattice satisfying 
   conditions \textup{(1)} and~\textup{(2)}.  Then 
   $D^{\langle 2 \rangle}$ is a sublattice of $D^{2}$; 
   hence $D^{\langle 2 \rangle}$ is a lattice, and 
   $D^{\langle 2 \rangle}$ is a complete distributive 
   lattice satisfying condition \textup{(1)} and~\textup{(2)}. 
\end{lemma}

\begin{proof} 
   By conditions (1) and~(2), $D^{\langle 2 \rangle}$ is a sublattice 
   of $D^{2}$.  Hence, $D^{\langle 2 \rangle}$ is a lattice.

   Since $D^{\langle 2 \rangle}$ is a sublattice of a distributive
   lattice, $D^{\langle 2 \rangle}$ is a distributive lattice.  Using 
   the characterization of standard ideals in Ernest~T. Moynahan~\cite{eM57},
   $D^{\langle 2 \rangle}$ has a zero and a unit element,
   namely, $\langle 0, 0 \rangle$ and $\langle 1, 1 \rangle$. 
   To show that $D^{\langle 2 \rangle}$ is complete, let 
   $\varnothing \ne A \subseteq D^{\langle 2 \rangle}$, and let 
   $a = \bigvee A$ in $D^{2}$.  If 
   $a \in D^{\langle 2 \rangle}$, then 
   $a = \bigvee A$ in $D^{\langle 2 \rangle}$; otherwise, $a$ 
   is of the form $\langle b, 1 \rangle$ for some 
   $b \in D$ with $b < 1$.  Now $\bigvee A = \langle 1, 1\rangle$ 
   in $D^{2}$ and the dual argument shows that $\bigwedge A$ also 
   exists in $D^{2}$.  Hence $D$ is complete. Condition (1) 
   and~(2) are obvious for $D^{\langle 2 \rangle}$.
\end{proof}

\begin{corollary}\label{C:prime}
   If $D$ is complete-prime, then so is $D^{\langle 2 \rangle}$.
\end{corollary}

The motivation for the following result comes from Soo-Key Foo~\cite{sF90}.

\begin{lemma}\label{L:ccr} 
   Let $\Theta$ be a complete congruence relation of 
   $D^{\langle 2 \rangle}$ such that 
   \begin{equation}\label{E:rigid} 
      \langle 1, d \rangle \equiv \langle 1, 1 \rangle \pmod{\Theta}, 
   \end{equation} 
   for some $d \in D$ with $d < 1$. Then $\Theta = \iota$.
\end{lemma}

\begin{proof}
   Let $\Theta$ be a complete congruence relation of 
   $D^{\langle 2 \rangle}$ satisfying \eqref{E:rigid}. Then $\Theta = \iota$. 
\end{proof}

\section{The $\Pi^{*}$ construction}\label{S:P*} 
The following construction is crucial to our proof of the Main Theorem:

\begin{definition}\label{D:P*} 
   Let $D_{i}$, for $i \in I$, be complete distributive lattices 
   satisfying condition~\textup{(2)}.  Their $\Pi^{*}$ product is defined as 
   follows:
   \[
      \Pi^{*} ( D_{i} \mid i \in I ) = \Pi ( D_{i}^{-} \mid i \in I ) + 1;
   \]
   that is, $\Pi^{*} ( D_{i} \mid i \in I )$ is $\Pi ( D_{i}^{-} \mid 
   i \in I )$ with a new unit element. 
\end{definition}

\begin{notation} 
   If $i \in I$ and $d \in D_{i}^{-}$, then
   \[
      \langle \dots, 0, \dots, \overset{i}{d}, \dots, 0, \dots \rangle
   \]
   is the element of $\Pi^{*} ( D_{i} \mid i \in I )$ whose $i$-th 
   component is $d$ and all the other components are $0$.
\end{notation}

See also Ernest~T. Moynahan \cite{eM57a}.  Next we verify:

\begin{theorem}\label{T:P*} 
   Let $D_{i}$, for $i \in I$, be complete distributive lattices 
   satisfying condition~\textup{(2)}.  Let $\Theta$ be a complete congruence
   relation on $\Pi^{*} ( D_{i} \mid i \in I )$.  If there exist  
   $i \in I$ and $d \in D_{i}$ with $d < 1_{i}$ such that for
   all $d \leq c < 1_{i}$, 
   \begin{equation}\label{E:cong1} 
      \langle \dots, 0, \dots,\overset{i}{d},
      \dots, 0, \dots \rangle \equiv \langle \dots, 0, \dots,
      \overset{i}{c}, \dots, 0, \dots \rangle \pmod{\Theta}, 
   \end{equation}
   then $\Theta = \iota$.
\end{theorem}

\begin{proof} 
   Since 
   \begin{equation}\label{E:cong2}
      \langle \dots, 0, \dots, \overset{i}{d}, \dots, 0, 
         \dots \rangle \equiv \langle \dots, 0, \dots, 
         \overset{i}{c}, \dots, 0, \dots \rangle \pmod{\Theta}, 
   \end{equation}
   and $\Theta$ is a complete congruence relation, it follows from 
   condition~(3) that
   \begin{equation}\label{E:cong}
   \begin{split}
       &\langle \dots, \overset{i}{d}, \dots, 0,
          \dots \rangle\\
       &\equiv \bigvee ( \langle \dots, 0, \dots, 
         \overset{i}{c}, \dots, 0, \dots \rangle \mid d \leq c < 1 ) 
         \equiv 1 \pmod{\Theta}. 
   \end{split}
   \end{equation}

   Let $j \in I$ for $j \neq i$, and let $a \in D_{j}^{-}$. 
   Meeting both sides of the congruence \eqref{E:cong2} with 
   $\langle \dots, 0, \dots, \overset{j}{a}, \dots, 0, \dots \rangle$, 
   we obtain
 \begin{equation}\label{E:comp}
   \begin{split}
      0 &= \langle \dots, 0, \dots, \overset{i}{d}, \dots, 0, \dots 
         \rangle \wedge \langle \dots, 0, \dots, \overset{j}{a}, \dots, 0, 
         \dots \rangle\\
          &\equiv \langle \dots, 0, \dots, \overset{j}{a}, \dots, 0, \dots 
         \rangle \pmod{\Theta}. 
   \end{split}
  \end{equation}
   Using the completeness of $\Theta$ and \eqref{E:comp}, we get:
   \[
      0 \equiv \bigvee ( \langle \dots, 0, \dots, \overset{j}{a}, 
      \dots, 0, \dots \rangle \mid a \in D_{j}^{-} ) = 1 \pmod{\Theta}, 
   \]
   hence $\Theta = \iota$.
\end{proof}

\begin{theorem}\label{T:P*a} 
   Let $D_{i}$, for $i \in I$, be complete distributive lattices
   satisfying conditions \textup{(2)} and~\textup{(3)}.  Then 
   $\Pi^{*} ( D_{i} \mid i \in I )$ also satisfies conditions \textup{(2)}
    and~\textup{(3)}. 
\end{theorem}

\begin{proof}
   Let $\Theta$ be a complete congruence on 
   $\Pi^{*} ( D_{i} \mid i \in I )$. Let $i \in I$.  Define 
   \[
      \widehat{D}_{i} = \{ \langle \dots, 0, \dots, \overset{i}{d},
      \dots, 0, \dots \rangle \mid d \in D_{i}^{-} \} \cup \{ 1 \}.
   \]
   Then $\widehat{D}_{i}$ is a complete sublattice of 
   $\Pi^{*} ( D_{i} \mid i \in I )$, and $\widehat{D}_{i}$ is
   isomorphic to $D_{i}$.  Let $\Theta_{i}$ be the restriction of 
   $\Theta$ to $\widehat{D}_{i}$.  

   Since $D_{i}\) is complete-simple, so is $\widehat{D}_{i}$, and
   hence $\Theta_{i}$ is $\omega$ or $\iota$.  If 
   $\Theta_{i} = \rho$ for all $i \in I$, then 
   $\Theta = \omega$.  If there is an $i \in I$, such that 
   $\Theta_{i} = \iota$, then $0 \equiv 1 \pmod{\Theta}$, hence 
   $\Theta = \iota$.
\end{proof}

The Main Theorem follows easily from Theorems \ref{T:P*} and~\ref{T:P*a}.

\bibliographystyle{amsplain}
\bibliography{sampartb}
\end{document}