diff options
Diffstat (limited to 'Master/texmf-dist/doc/latex/mil3/sampart.tex')
| -rw-r--r-- | Master/texmf-dist/doc/latex/mil3/sampart.tex | 262 |
1 files changed, 262 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/latex/mil3/sampart.tex b/Master/texmf-dist/doc/latex/mil3/sampart.tex new file mode 100644 index 00000000000..70bbd3f8509 --- /dev/null +++ b/Master/texmf-dist/doc/latex/mil3/sampart.tex @@ -0,0 +1,262 @@ +% Sample file: sampart.tex +% The sample article for the amsart document class +% 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;\label{m-i} + \item $v$ is join-irreducible but $v$ is \emph{not} + completely join-irreducible;\label{j-i} + \item $[u, v]$ is a complete-simple lattice.\label{c-s} + \end{enumerate} +\end{definition} + +Now we prove the following result: + +\begin{lemma}\label{L:ds} + Let $D$ be a complete distributive lattice satisfying + conditions \eqref{m-i} and~\eqref{j-i}. 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 conditions \eqref{m-i} and~\eqref{j-i}. +\end{lemma} + +\begin{proof} + By conditions~\eqref{m-i} and \eqref{j-i}, + $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. Conditions \eqref{m-i} + and~\eqref{j-i} 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~\eqref{j-i}. 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~\eqref{j-i}. 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~\eqref{c-s} 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 \eqref{j-i} and~\eqref{c-s}. Then + $\Pi^{*} ( D_{i} \mid i \in I )$ also satisfies + conditions~\eqref{j-i} and \eqref{c-s}. +\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}. + +\begin{thebibliography}{9} + + \bibitem{sF90} + Soo-Key Foo, \emph{Lattice Constructions}, Ph.D. thesis, University + of Winnebago, Winnebago, MN, December, 1990. + + \bibitem{gM68} + George~A. Menuhin, \emph{Universal algebra}, D.~van Nostrand, + Princeton, 1968. + + \bibitem{eM57} + Ernest~T. Moynahan, \emph{On a problem of M. Stone}, Acta Math. + Acad. Sci. Hungar. \textbf{8} (1957), 455--460. + + \bibitem{eM57a} + \bysame, \emph{Ideals and congruence relations in lattices}. II, + Magyar Tud. Akad. Mat. Fiz. Oszt. K\"{o}zl. \textbf{9} (1957), + 417--434 (Hungarian). + + \bibitem{fR82} + Ferenc~R. Richardson, \emph{General lattice theory}, Mir, Moscow, + expanded and revised ed., 1982 (Russian). + +\end{thebibliography} +\end{document} + |