summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/latex/mil3/sampartb.tex
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/doc/latex/mil3/sampartb.tex')
-rw-r--r--Master/texmf-dist/doc/latex/mil3/sampartb.tex236
1 files changed, 236 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/latex/mil3/sampartb.tex b/Master/texmf-dist/doc/latex/mil3/sampartb.tex
new file mode 100644
index 00000000000..6515da73e05
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/mil3/sampartb.tex
@@ -0,0 +1,236 @@
+% 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}
+