par-alg-rep.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                         BIBLIOGRAPHY FILE                                 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% The `filecontents` command will crete a file in the inputs directory called 
%% refs.bib containing the references in the document, in case this file does 
%% not exist already.
%% If you want to add a BibTeX entry, please don't add it directly to the
%% refs.bib file.  Instead, add it in this file between the
%% \begin{filecontents*}{refs.bib} and \end{filecontents*} lines
%% then delete the existing refs.bib file so it will be automatically generated 
%% again with your new entry the next time you run pdfaltex.
\begin{filecontents*}{inputs/refs.bib}
@book {MR2455216,
    AUTHOR = {Gr{\"a}tzer, George},
     TITLE = {Universal algebra},
   EDITION = {second},
      NOTE = {With appendices by Gr{\"a}tzer, Bjarni J{\'o}nsson, Walter
              Taylor, Robert W. Quackenbush, G{\"u}nter H. Wenzel, and
              Gr{\"a}tzer and W. A. Lampe},
 PUBLISHER = {Springer, New York},
      YEAR = {2008},
     PAGES = {xx+586},
      ISBN = {978-0-387-77486-2},
   MRCLASS = {08-02},
  MRNUMBER = {2455216},
       DOI = {10.1007/978-0-387-77487-9},
       URL = {http://dx.doi.org/10.1007/978-0-387-77487-9},
}
@article {MR0237401,
    AUTHOR = {Gr{\"a}tzer, G. and Wenzel, G. H.},
     TITLE = {On the concept of congruence relation in partial algebras},
   JOURNAL = {Math. Scand.},
  FJOURNAL = {Mathematica Scandinavica},
    VOLUME = {20},
      YEAR = {1967},
     PAGES = {275--280},
      ISSN = {0025-5521},
   MRCLASS = {08.30},
  MRNUMBER = {0237401},
MRREVIEWER = {B. H. Neumann},
}
@article {MR0309833,
    AUTHOR = {Berman, Joel},
     TITLE = {On the congruence lattices of unary algebras},
   JOURNAL = {Proc. Amer. Math. Soc.},
  FJOURNAL = {Proceedings of the American Mathematical Society},
    VOLUME = {36},
      YEAR = {1972},
     PAGES = {34--38},
      ISSN = {0002-9939},
   MRCLASS = {08A15},
  MRNUMBER = {0309833},
MRREVIEWER = {I. Petrescu},
}
		
@article {MR0308011,
    AUTHOR = {Berman, Joel},
     TITLE = {Strong congruence lattices of finite partial algebras},
   JOURNAL = {Algebra Universalis},
  FJOURNAL = {Algebra Universalis},
    VOLUME = {1},
      YEAR = {1971/72},
     PAGES = {133--135},
      ISSN = {0002-5240},
   MRCLASS = {08A25},
  MRNUMBER = {0308011},
MRREVIEWER = {M. Kolibiar},
}
		
@book {MR2619731,
    AUTHOR = {Berman, Joel},
     TITLE = {{C}ongruence {L}attices of {F}inite {U}niversal {A}lgebras},
      NOTE = {Thesis (Ph.D.)--University of Washington},
 PUBLISHER = {ProQuest LLC, Ann Arbor, MI},
      YEAR = {1970},
     PAGES = {64},
   MRCLASS = {Thesis},
  MRNUMBER = {2619731},
       URL = {https://dl.dropboxusercontent.com/u/17739547/diss/berman-phd-thesis.pdf}
}
@COMMENT {http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:7100941},
@misc{Lampe:20161017,
  author        = "Bill Lampe",
  howpublished  = "personal communication",
  note          = "October 17",
  year          = "2016"
}
@article {MR552159,
    AUTHOR = {Pudl{\'a}k, Pavel and T{\.u}ma, Ji{\v{r}}{\'{\i}}},
     TITLE = {Every finite lattice can be embedded in a finite partition
              lattice},
   JOURNAL = {Algebra Universalis},
  FJOURNAL = {Algebra Universalis},
    VOLUME = {10},
      YEAR = {1980},
    NUMBER = {1},
     PAGES = {74--95},
      ISSN = {0002-5240},
   MRCLASS = {06B15 (05C99)},
  MRNUMBER = {552159},
MRREVIEWER = {James W. Lea, Jr.},
       DOI = {10.1007/BF02482893},
       URL = {http://dx.doi.org/10.1007/BF02482893},
}
@article {MR3076179,
    AUTHOR = {Kearnes, Keith A. and Kiss, Emil W.},
     TITLE = {The shape of congruence lattices},
   JOURNAL = {Mem. Amer. Math. Soc.},
  FJOURNAL = {Memoirs of the American Mathematical Society},
    VOLUME = {222},
      YEAR = {2013},
    NUMBER = {1046},
     PAGES = {viii+169},
      ISSN = {0065-9266},
      ISBN = {978-0-8218-8323-5},
   MRCLASS = {08B05 (08B10)},
  MRNUMBER = {3076179},
MRREVIEWER = {James B. Nation},
       DOI = {10.1090/S0065-9266-2012-00667-8},
       URL = {http://dx.doi.org/10.1090/S0065-9266-2012-00667-8},
}
@unpublished{Nation-notes,
author = {J. B. Nation},
title = {Notes on Lattice Theory},
note = {Unpublished notes},
year = {2007, 2016},
URL = {http://www.math.hawaii.edu/~jb/}
}
\end{filecontents*}
\documentclass[12pt]{amsart}
% The following \documentclass options may be useful:
% preprint      Remove this option only once the paper is in final form.
% 10pt          To set in 10-point type instead of 9-point.
% 11pt          To set in 11-point type instead of 9-point.
% numbers       To obtain numeric citation style instead of author/year.

%% \usepackage{setspace}\onehalfspacing

\usepackage{amsmath}
\usepackage{amscd,amssymb,amsthm} %, amsmath are included by default
\usepackage{latexsym,stmaryrd,mathrsfs,enumerate,scalefnt,ifthen}
\usepackage{mathtools}
\usepackage[mathcal]{euscript}
\usepackage[colorlinks=true,urlcolor=black,linkcolor=black,citecolor=black]{hyperref}
\usepackage{url}
\usepackage{scalefnt}
\usepackage{tikz}
\usepackage{color}
\usepackage[margin=1in]{geometry}
\usepackage{scrextend}

%%////////////////////////////////////////////////////////////////////////////////
%% Theorem styles
\numberwithin{equation}{section}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{prop}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{Fact}[theorem]{Fact}
\newtheorem*{fact}{Fact}
\newtheorem{example}[theorem]{Example}
\newtheorem{examples}[theorem]{Examples}
\newtheorem{exercise}{Exercise}
\newtheorem*{lem}{Lemma}
\newtheorem*{cor}{Corollary}
\newtheorem*{remark}{Remark}
\newtheorem*{remarks}{Remarks}
\newtheorem*{obs}{Observation}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Acronyms
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% \usepackage[acronym, shortcuts]{glossaries}
%\usepackage[smaller]{acro}
\usepackage[smaller]{acronym}
\usepackage{xspace}

%% \acs{CSP} -- short version of the acronym\\
%% \acl{CSP} -- expanded acronym without mentioning the acronym.\\
%% \acp{CSP} -- plurals.\\
%% \acfp{CSP} -- long forms into plurals.\\
%% \acsp{CSP} -- short form into a plural.\\
%% \aclp{CSP} -- long form into a plural.\\
%% \acfi{CSP} -- Full Name acronym in italics and abbreviated form in upshape.\\
%% \acsu{CSP} -- short form of the acronym and marks it as used.\\
%% \aclu{CSP} -- Prints the long form of the acronym and marks it as used.\\

\acrodef{lics}[LICS]{Logic in Computer Science}
\acrodef{sat}[SAT]{satisfiability}
\acrodef{nae}[NAE]{not-all-equal}
\acrodef{ctb}[CTB]{cube term blocker}
\acrodef{tct}[TCT]{tame congruence theory}
\acrodef{wnu}[WNU]{weak near-unanimity}
\acrodef{CSP}[CSP]{constraint satisfaction problem}
\acrodef{MAS}[MAS]{minimal absorbing subuniverse}
\acrodef{MA}[MA]{minimal absorbing}
\acrodef{cib}[CIB]{commutative idempotent binar}
\acrodef{sd}[SD]{semidistributive}
\acrodef{NP}[NP]{nondeterministic polynomial time}
\acrodef{P}[P]{polynomial time}
\acrodef{PeqNP}[P $ = $ NP]{P is NP}
\acrodef{PneqNP}[P $ \neq $ NP]{P is not NP}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{inputs/proof-dashed}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Put new macros in the macros.sty file
\usepackage{inputs/macros}

\usepackage[backend=bibtex]{biblatex}
\bibliography{inputs/refs.bib}

\begin{document}

\title[Congruences of Partial Algebras]{Congruences of Partial and Total Algebras}
\date{24 October 2016}
\author[W.~DeMeo]{William DeMeo}
\address{University of Hawaii}
\email{williamdemeo@gmail.com}

\maketitle

%% \begin{abstract}\end{abstract}

\section{Introduction}
\label{sec:introduction}
Section~\ref{sec:simple-proof-well} gives a straight-forward proof that every finite
lattice is the congruence lattice of a finite partial algebra.
Bill Lampe~\cite{Lampe:20161017} pointed out
that this result has been known for a long time, and in
Section~\ref{sec:more-gener-appr}
we give some background about closure operators and 
begin to develop the framework in which the original result was presented.
We also recall a theorem from Berman's thesis that relates congruence lattices of
partial algebras with those of total algebras.

This is a mash-up of notations, definitions, and theorems
for the Universal Algebra and Lattice Theory Seminar
in Hawaii, Fall Semester 2016. 
The notes are unfinished and far from perfect.
Nonetheless, they might stimulate discussion
in the seminar and elicit some criticism
that we can use to improve them.
So far most, if not all, of what appears below is known.
See, for example, \cite{MR2619731, MR0308011, MR0237401, MR2455216}.


\section{A well known result}
\label{sec:simple-proof-well}
In this section we give a straight-forward proof of the fact that every finite
lattice is the congruence lattice of a finite partial algebra.


\begin{lemma}
Let $X$ be a finite set, and let $\Eq(X)$ denote the lattice of equivalence
relations on $X$. If $L\leq \Eq(X)$ is a 0-1-sublattice,
and $\rho \in \Eq(X)$ and $\rho \notin L$, then for some $k < \omega$ there exists a partial
operation $f\colon X^k \rightharpoonup X$ that is compatible with $L$ and
incompatible with $\rho$.
\end{lemma}
\begin{proof}
  First we focus on the relations in $L$ that are above $\rho$.
  Let $\rho^\uparrow \cap L = \{\gamma \in L \mid \gamma \geq \rho\}$.
  Since $\rho\notin L$, we have $\gamma > \rho$ for all $\gamma \in \rho^\uparrow \cap L$.
  Now, $\rho^\uparrow \cap L$ has a least element
  $\rho^* = \Meet (\rho^\uparrow \cap L)$.  Clearly
  $\rho^*\geq \rho$ and since $\rho^* \in L$ we have
  $\rho^*\neq \rho$, so
  $\rho^* > \rho$.  Therefore, there exists $(u,v) \in \rho^* - \rho$.

  Next consider the elements of $L$ that are not above $\rho$. For each such
  $\alpha_i \in L - \rho^\uparrow$ there exists $(x_i, y_i) \in \rho -\alpha_i$.
  Let $(x_1, y_1), \dots, (x_k, y_k)$ be the list of all unique such pairs
  (i.e., each pair appears in the list exactly once).
  Define the partial function $f\colon X^k \rightharpoonup X$ at only two points of $X^k$; specifically, let
  \[ f(x_1, \dots, x_k) = u \quad \text{ and } \quad f(y_1, \dots, y_k) = v. \]
  Then, since $(\forall i)(x_i, y_i) \in \rho$ and $(u,v) \notin \rho$, 
  $f$ is incompatible with $\rho$.  On the other hand,
  $(u,v) \in  \rho^* = \Meet (\rho^\uparrow \cap L)$, so
  $(u,v) \in \gamma$  for every $\gamma \in \rho^\uparrow \cap L$, so
  $f$ is compatible with every $\gamma \in \rho^\uparrow \cap L$.
  
  
  Finally, for each $\alpha_i\in L$ not above $\rho$ there is at least one pair
  $(x_i, y_i)\notin \alpha_i$.  Therefore, it is impossible for $f$ to be
  incompatible with any such $\alpha_i$. 
\end{proof}

\begin{theorem}
Let $X$ be a finite set and let $L\leq \Eq(X)$ be a 0-1-sublattice.
Then there exists a finite partial algebra
$\mathbb X = \< X, F\>$ with $\Con(\mathbb X) =  L$.
\end{theorem}

\begin{proof}
  By the lemma, for each $\rho \in \Eq(X) - L$, there exists $k< \omega$ and
  $f_\rho \colon  X^k \rightharpoonup X$ such that $f_\rho$ is compatible with every relation in
  $L$ and incompatible with $\rho$.  Let $\mathcal{R}$ be the set $\Eq(X) - L$ of
  all equivalence relations on $X$ that do not belong to $L$.  Define,
  $F = \{f_\rho \mid \rho \in \mathcal{R}\}$.  Evidently, $\Con \<X, F\> = L$.
\end{proof}

\section{Closure Systems and Moore Families}
\label{sec:more-gener-appr}

\subsection{Closure systems and operators}
%% \footnote{See J. B. Nation's notes~\cite{Nation-notes} for more details.}
A \defn{closure system} on a set $X$ is a collection $\sC$
of subsets of $X$ that is closed under arbitrary intersection (including the empty 
intersection, so $\bigcap \emptyset = X \in \sC$). 
Thus a closure system is a complete meet semilattice with respect to subset
inclusion ordering. 
Since every complete meet semilattice is automatically a complete lattice
(see \cite[Theorem 2.5]{Nation-notes}), 
the closed sets of a closure system form a complete lattice. 
%% The sets in $\sC$ are called \defn{closed sets}. 

Examples of closure systems that are especially relevant for our work are the following:
\begin{itemize}
\item order ideals of an ordered set
\item subalgebras of an algebra 
\item equivalence relations on a set
\item congruence relations of an algebra
\end{itemize}

\newcommand{\cl}{\ensuremath{\operatorname{\sansC}}}

Let $\bP = \<P, \leq \>$ be a poset.
An function $\cl \colon P \to P$ is called a \defn{closure operator} on $\bP$
if it satisfies the following axioms for all $x, y\in P$.
\begin{enumerate}
\item $x \leq \cl x$ (extensivity) 
\item $x \leq y$ implies $\cl x \leq \cl y$ (monotonicity) 
\item $\cl \cl x = \cl x$ (idempotence) 
\end{enumerate}
Thus, a closure operator is an extensive idempotent poset endomorphism,
and the definition above is equivalent to the single axiom
$(\forall\, x, y \in P) (x \leq \cl y \, \longleftrightarrow  \, \cl x \leq  \cl y)$.

\begin{example}
Let $X$ be a set and let $Y \subseteq X$.
Define $\cl_Y\colon \sP(X) \to \sP(X)$ by $\cl_Y (W) = W \cup Y$.
Then $\cl_Y$ is a closure operator on $\<\sP(X), \subseteq\>$.
\end{example}


A \defn{fixed point} of a
function $\cl \colon  P \to P$ is an $x\in P$ satisfying $\cl x = x$.
A fixed point of a closure operator is called \defn{closed}.
%% A \defn{closure operator} on a set $X$ is a map $\sansc  \colon \sP(X) \to \sP(X)$ 
%% satisfying, for all $A, B \in \sP(X)$,
%% \begin{enumerate}[(a)]
%% \item $A \subseteq \sansC A$ (extensivity) 
%% \item $A \subseteq B$ implies $\sansC A \subseteq \sansC B$ (monotonicity) 
%% \item $\sansC  \sansC A = \sansC A$ (idempotence) 
%% \end{enumerate}
%% A fixpoint of a closure operator is called a \defn{closed set}.
If the poset $\bP = \<P, \leq\>$ happens to be a complete lattice,
then by extensivity the largest element $\top = \Join P$ is
a fixed point of every closure operator on $\bP$.
Also, the collection of fixed points of a closure operator is closed under arbitrary meets.
(Proof: If $\sA$ is a set of fixed points of $\cl$ and  
$a \in \sA$, then $\Meet \sA \leq a$, so by monotonicity
$\cl \bigl( \Meet \sA \bigr) \leq \cl a = a$. 
Since $a$ was arbitrary,
$\cl \bigl( \Meet \sA \bigr) \leq  \Meet \sA$.
By extensivity,
$\Meet \sA \leq \cl \bigl( \Meet \sA\bigr)$. % \subseteq \bigcap \sA$,
Therefore, $\cl \bigl( \Meet \sA \bigr) =  \Meet \sA$.)
%% ; that is,  $\Meet \sA$ is a fixpoint of $\cl$.)
The set of closure operators on $\bP$
themselves form a complete lattice under the pointwise
order: $\cl_1 \leq  \cl_2$ iff $\cl_1 x \leq  \cl_2 x$ for all $x \in P$. 

Some of these observations can be restated as follows:
if $\bP = \<P, \leq\>$ is a complete lattice,
then the set $\sC \subseteq P$ of fixed points of a closure operator
is a \defn{Moore family} on $\bP$---that is, 
%% A subset $\sM \subseteq P$ is called a \defn{Moore family} if
$\Join P \in \sC$ and every nonempty subset of $\sC$ is closed under arbitrary meets.
%% If $\bL = \<L, \join, \meet\>$ is a complete lattice with top $\top = \Join L$, then
%% That is, if $\emptyset \neq S \subseteq \sM$, then $\Meet S \in S$.
%% If $\bL = \<L, \join, \meet\>$ is a complete lattice, then a


Conversely, if we are given a Moore family $\sC$ on $\bP$, and if we define 
$\cl \colon P \to P$ by
\[
\cl a = \Meet \{b \in \sC \mid a\leq b\},
\]
then $\cl$ satisfies conditions (1)--(3)
above, making it a closure operator.
To summarize, $\sC \subseteq P$ is the set of fixed points (i.e., closed elements)
of a closure operator on
$\bP$ if and only if $\sC$ is a Moore family on $\bP$.

Every Moore family on $\bP$ is itself the universe of a complete lattice with the order inherited
from $\bP$, though the join may differ from the join of $\bP$.

\subsubsection{More Moore families}
The name ``closure system'' is typically reserved for the special case
in which $\bP$ happens to be the powerset Boolean
algebra of a set $X$---that is, $\bP = \<\sP(X), \subseteq\>$; in that case, a Moore family on $\bP$ 
is called a closure system on $X$. 

\begin{example}
  Let $X$ be a set,
  let $\sansR(X) = \bigcup_{n<\omega}\sP(X^n)$ be the set of all finitary
  relations on $X$, and let
  %% let $\Eq(X)$ denote the lattice of equivalence relations on $X$, and let
  $\sansO(X) = \bigcup_{n< \omega} X^{X^n}$ be the set of all finitary operations on $X$.
  Define $F \colon  \sP(\sansR(X)) \to \sP(\sansO(X))$
  and $G \colon \sP(\sansO(X)) \to \sP(\sansR(X))$ as follows:
  if $A \subseteq\sansR(X)$ and $B \subseteq \sansO(X)$, then
  %% \sF_n(S) = \{f \in \sansO(X)X^{X^n} \mid f \text{ is compatible with every $s\in S$}\}
  %% \[  \sF(S) = \bigcup \sF_n(S)  \]
  \[
  F(A) = \{f \in \sansO(X) \mid f \text{ is compatible with every relation in $A$}\},
  \]
  \[
  G(B) = \{\rho \in \sansR(X) \mid \rho \text{ is compatible with every operation in $B$}\}.
  \]
  Then $G \circ F$ is a closure operator on the lattice % $\<\sansR(X), \subseteq\>$
  of all relations on $X$.
\end{example}

\begin{example}
  Let $X$ be a set,
  let $\Eq(X)$ denote the lattice of equivalence relations on $X$, and let
  $X^X$ be the set of all unary operations on $X$.
  Define $F_1 \colon  \sP(\Eq(X)) \to \sP(X^X)$
  and $G_1 \colon \sP(X^X) \to \sP(\Eq(X))$ as follows:
  if $A \subseteq\Eq(X)$ and $B \subseteq X^X$, then
  %% \sF_n(S) = \{f \in \sansO(X)X^{X^n} \mid f \text{ is compatible with every $s\in S$}\}
  %% \[  \sF(S) = \bigcup \sF_n(S)  \]
  \[
  F_1(A) = \{f \in X^X\mid f \text{ is compatible with every relation in $A$}\},
  \]
  \[
  G_1(B) = \{\rho \in \Eq(X) \mid \rho \text{ is compatible with every operation in $B$}\}.
  \]
  Then $G_1 \circ F_1$ is a closure operator on the lattice $\Eq(X)$
  of all equivalence relations on $X$.
\end{example}
\newcommand{\Luv}{\ensuremath{L_{u,v}}}
\newcommand{\bLuv}{\ensuremath{\mathbf{L}_{u,v}}}
\newcommand{\juv}{\ensuremath{\vee_{u,v}}}
\newcommand{\suv}{\ensuremath{\sigma_{u,v}}}
\begin{example}[Pudl{\'a}k-T{\.u}ma~\cite{MR552159}]
  Let $\bL = \<L, \join, \meet\>$ be a lattice, $u, v \in L$, and $u\leq v$.
  Define a subset $\Luv$ of $L$ by
  $\Luv =\{x\in L \mid v\leq x \text{ or } u \nleq x\}$.
  The partial order relation of the lattice $\bL$ induces a lattice order on
  $\Luv$. Denote the resulting lattice by $\bLuv$.
  Then the meet of $\bLuv$ is that of $\bL$, whereas the join of $\bLuv$ is
  \[
  x \juv y = 
  \begin{cases}
    x \join y, & \text{ if $u \nleq x \join y$,}\\
    x \join y \join v, & \text{ if $u \leq x \join y$.}
  \end{cases}
  \]
  Define a mapping $\suv \colon L \to \Luv$ as follows:
  \[
  \suv (x)  = 
  \begin{cases}
    x, & \text{ if $u \nleq x$,}\\
    x \join v, & \text{ if $u \leq x$.}
  \end{cases}
  \]
  Then $\suv$ is a surjective join-homomorphism. In fact, every
  join-homomorphism $\phi \colon L \to K$ satisfying $\phi(u) = \phi(v)$ splits as
  $\phi =  \psi \circ \suv$ for some $\psi \colon \Luv \to K$.
  (See the commutative diagram in Figure~\ref{fig:splitting}.)
  As a mapping from $\bL$ to itself, $\suv$ does not preserve joins. However,
  $\suv \colon L \to L$ is a closure operator and 
  $\Luv$ is the set of fixed points of $\suv$ (the closed sets).

  \begin{center}
    \begin{figure}[h]
      \begin{tikzpicture}[node distance=2cm, scale=3]
        \node (10) at (1,0)  {$\Luv$};
        \node (21) at (2,1)  {$K$};
        \node (01) at (0,1)  {$L$};
        \node (middle) at (1,0.6)  {$\circlearrowleft$};
        \draw[->,thick] (01) -- (21)  node[pos=.5,above] {$\phi$};
        \draw[->,thick] (01) -- (10)  node[pos=.5,left] {$\suv$};
        \draw[->,dashed,thick] (10) -- (21)  node[pos=.5,right] {$\exists \,\psi$};
      \end{tikzpicture}
      \caption{Every join-homomorphism collapsing $u$ and $v$ is divisible by $\suv$.}
      \label{fig:splitting}
    \end{figure}
  \end{center}

  
\end{example}


\section{Algebraic Closure Systems}
A subset $D$ of an ordered set $P$ is called \defn{up-directed}
if for every $x, y \in D$ there exists $z \in D$ such that
$x \leq z$ and $y \leq z$. 
A closure operator $\cl\colon \sP(X) \to \sP(X)$ is called \defn{algebraic} provided,
for all $A\subseteq X$, 
\[
\cl A = \bigcup \{\cl F \mid F \subseteq A \text{ and } F \text{ finite } \}.
\]
The collection $\sC$ of closed sets of an algebraic closure operator is called an
\defn{algebraic closure system}.
\begin{theorem}[cf.~\cite{Nation-notes} Thm 3.1]
  Let $\sC$ be the closure system of fixed points of the closure operator $\cl\colon \sP(X) \to \sP(X)$.
  The following are equivalent:
\begin{enumerate}
\item $\cl$ is an algebraic closure operator
\item $\sC$ is an algebraic closure system
\item If $D\subseteq \sC$ is up-directed and $C\subseteq D$ is a chain, then $\bigcup C$ is closed.
\item If $D\subseteq \sC$ is up-directed, then $\bigcup D$ is closed.
\item If $C\subseteq \sC$ is a chain, then $\bigcup C$ is closed.
\end{enumerate}
\end{theorem}

\subsection{Algebraic closure systems are subalgebra lattices}
For an algebra $\bA$, the subalgebra generation operator $\Sg^{\bA}$ is an algebraic
closure operator (on the poset $\<\sP(A), \subseteq\>$) whose fixed points are the
subalgebras of $\bA$.
Thus the lattice $\<\Sub(\bA), \join, \meet\>$ of subalgebras of $\bA$ is an algebraic closure
system.
Conversely, given an algebraic closure system $\sS$, we can construct an algebra
$\bA =\<A, F\>$ so that $\sS = \Sub(\bA)$.
Here is how: let $\cl_{\sS}$ denote the corresponding closure operator.
For each $a_0, a_1, \dots, a_{n-1}, b \in A$ such that
$b \in \cl_{\sS} \bigl(\{a_0, a_1, \dots, a_{n-1}\}\bigr)$, define the $n$-ary operation
$f_{\ba, b}$ so that $f_{\ba, b}(a_0, a_1, \dots, a_{n-1}) = b$ and
for all other tuples $f_{\ba, b}(c_0, c_1, \dots, c_{n-1}) = c_0$.
%% Do this for each $\ba = (a_0, a_1, \dots, a_{n-1})$. 
Then define
\[
F = \{f_{\ba, b} \mid  n< \omega, \, \ba \in A^n,  \, b \in \cl_{\sS} \ba\}.
\]
Every subalgebra is the union of its finitely generated subsubalgebras...
{\it (to be continued)}

\subsection{Congruence lattices}
Start with an algebraic closure system $\sS$ of equivalence relations on a set
$A$ and let $\cl_{\sS}$ be the associated closure operator.
Let $(a_0, b_0)$, $(a_1, b_1)$, $\dots$, $(a_{n-1},b_{n-1})$, and $(c_0,
c_1)$ belong to $A\times A$,
and suppose 
$(c_0,c_1) \in \cl_{\sS}\bigl(\{(a_0, b_0), (a_1, b_1), \dots,
(a_{n-1},b_{n-1})\}\bigr)$.
Define $f_{\ba, \bb, \bc}\colon (A\times A)^n \to A\times A$ 
so that
$f_{\ba, \bb, \bc}\bigl((a_0, b_0), (a_1, b_1), \dots, (a_{n-1},b_{n-1})\bigr) =(c_0,c_1)$.
Do this for each triple $\ba$, $\bb$, $\bc$...
{\it (to be continued)}


\section{Strong Congruence Relations}
We use bold letters like $\bx$ to denote tuples like $(x_0, \dots, x_{n-1})$,
where the value $n$ will be clear from context.
Let $\theta$ be an equivalence relation on a set $A$ and suppose
$f\colon A^n \rightharpoonup A$ is a partial function.
We call $\theta$ and $f$
\begin{itemize}
\item \defn{weakly compatible} provided that, for all $(a_i, b_i) \in \theta$,
if $f(\ba)$ and $f(\bb)$ are both defined, then $f(\ba) \mathrel{\theta} f(\bb)$.
\item \defn{strongly compatible} provided that, for all $(a_i, b_i) \in \theta$,
if $f(\ba)$ is defined, then $f(\bb)$ is defined and $f(\ba) \mathrel{\theta} f(\bb)$.
\end{itemize}

Let $\A = \<A, F\>$ be a partial algebra and $\theta$ an equivalence relation on $A$.
We call $\theta$ a \defn{strong} (resp., \defn{weak}) \defn{congruence} of $\A$
if $\theta$ is strongly (resp., weakly) compatible with every $f\in F$.
Denote by $\SCon(\A)$ (resp., $\WCon(\A)$) the set of strong (resp., weak)
congruences of $\A$.
%% If $\A = \<A, F\>$ is a (partial) algebra then a \defn{(strong) congruence relation} of $\A$ is
%% an equivalence relation on $A$ that is (strongly) compatible with every $f\in F$.

Here are some elementary observations about strong and weak congruences.
(See Berman's thesis~\cite{MR2619731} and paper~\cite{MR0308011} for more details and proofs.)
If $\A = \<A, F\>$ is a partial algebra then the set $\SCon(\A)$ of strong congruence relations of
$\A$ forms a sublattice of $\Eq(A)$.
The set $\WCon(\A)$ of weak congruences also forms a lattice, but it is not a sublattice of $\Eq(A)$
since there may be pairs of relations whose join in $\Eq(A)$ is strictly below
their join in $\WCon(\A)$. We will see examples below.

A \emph{total algebra}---an algebra for which all operations are defined everywhere---is
a special case of a partial algebra. In case a partial algebra is not total,
we may refer to it as a \emph{proper partial algebra}.
This simply means that there is at least one operation that is not defined everywhere.
It should be obvious that for total algebras strong and weak congruences reduce to the usual
definition of congruence relation on an algebra.
In particular, if $\A$ is total, then the largest strong congruence of $\A$ is $1_A := A\times A$.
%% Let $\theta$ be a strong congruence of the partial algebra

The converse of the last sentence in the previous paragraph is also true.
That is, if the largest strong congruence of $\A$ is $1_A$, then $\A$ is total.
To see this, suppose $f \in F$ is an $n$-ary partial operation and 
denote by $\dom(f)$ the subset of $A^n$ on which $f$ is defined.
Let $\theta$ be a strong congruence of $\A$.
Then the following implication holds:
\[ (a_0, a_1, \dots, a_{n-1})\in \dom(f) \;  \Longrightarrow \;
   [a_0]_\theta \times [a_1]_\theta \times \cdots \times [a_{n-1}]_\theta \subseteq \dom(f).
   \]
That is, if $f$ is defined at an $n$-tuple,
%% $\ba = (a_0, a_1, \dots, a_{n-1})$,
then $f$ must also be defined on the whole Cartesian product of $\theta$-blocks containing the
coordinates of that tuple.
In particular, if $1_A$ is a strong congruence of $\A$, then every operation of
$\A$ must be total, while if $\A = \<A, F\>$ is a \emph{proper partial algebra},
then the largest strong congruence of $\A$
must be strictly below $1_A$.

To summarize, $\A$ is a total algebra iff $\Join \SCon(\A) = 1_A$.

\begin{theorem}[Berman's Thesis~\cite{MR2619731} Thm~1.18]
  \label{thm:berman-1-18}
  Let $\A$ be a finite partial algebra and $\SCon(\A)$ the lattice of strong
  congruence relations of $\A$.  Then there exists a finite algebra $\bA$
  such that $\Con(\bA) = \SCon(\A)$.
\end{theorem}
\begin{remarks}\
  \begin{enumerate}
  \item  Either one or both of the algebras in Theorem~\ref{thm:berman-1-18} can be
    taken to be unary.
  \item It follows easily from Theorem~\ref{thm:berman-1-18} that the class
    of lattices isomorphic to strong congruence lattices of finite
    partial algebras is equal to the class of lattices isomorphic to
    congruence lattices of finite partial algebras.
    (This is~\cite[Thm~1.19]{MR2619731}.)
  \end{enumerate}
\end{remarks}

\section*{Acknowledgments}
The author would like to thank Peter Jipsen
and Bill Lampe for many helpful discussions.


%% \appendix
%% \section{Appendix Title}
%% This is the text of the appendix, if you need one.

%\bibliographystyle{amsplain} %% or amsalpha
%% \bibliographystyle{plain-url}
\printbibliography


\end{document}