\documentclass{article} \usepackage{amssymb} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{graphicx} \usepackage{amsmath} %TCIDATA{OutputFilter=LATEX.DLL} %TCIDATA{Created=Wed Jun 30 19:35:08 1999} %TCIDATA{LastRevised=Wed Oct 13 16:54:05 1999} %TCIDATA{} %TCIDATA{} %TCIDATA{CSTFile=LaTeX article (bright).cst} \newtheorem{theorem}{Theorem} \newtheorem{acknowledgement}[theorem]{Acknowledgement} \newtheorem{algorithm}[theorem]{Algorithm} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{case}[theorem]{Case} \newtheorem{claim}[theorem]{Claim} \newtheorem{conclusion}[theorem]{Conclusion} \newtheorem{condition}[theorem]{Condition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{criterion}[theorem]{Criterion} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{notation}[theorem]{Notation} \newtheorem{problem}[theorem]{Problem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{remark}[theorem]{Remark} \newtheorem{solution}[theorem]{Solution} \newtheorem{summary}[theorem]{Summary} \newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \input{tcilatex} \begin{document} \title{The Zorn condition: a characterization of algebraic closure systems.} \author{A.Bujosa (*) and R.Criado (**)\thanks{% This work was partially supported by the Comunidad Aut\'{o}noma de Madrid, with project no. 07T/0036/98.} \and \smallskip \and (*) D.M.A.T.I. (U.P.M.) (**) E.S.C.E.T. (U.R.J.C.)} \maketitle \begin{abstract} The purpose of this paper is to establish that a closure system $\mathbf{C}$ is algebraic if and only if every chain $\mathcal{C}$ of non void sets of $% \mathbf{C}$ satisfies that $\cup \mathcal{C\in }\mathbf{C.}$ \end{abstract} \section{Introduction, Preliminaries and Basic Notions} Applications of closure and algebraic closure concepts are well known in the algebraic world, model theory, formal systems specification and several other fields of logic and universal algebra. Thus, in the literature we can find the concepts of closure operator (see for example [1]), closure system ([5]), formal system ([2]) and algebraic closure ([3] and [4]). First, we recall several definitions and properties that we need in order to establish the main result. \begin{definition} ([5]) Let X be a set (called the universe). A set $\mathbf{C}$ of subsets of X is called a closure system over X if the following conditions are satisfied: \begin{equation*} \left\{ \begin{tabular}{ll} (cs1) & $X\in \mathbf{C}$ \\ (cs2) & $\forall B(B\subset \mathbf{C}\Rightarrow \cap B\in \mathbf{C})$% \end{tabular} \right. \end{equation*} \end{definition} If $\mathbf{C}$ is a closure system over a set $X$, the elements of $\mathbf{% C}$ are called closed sets. Given a subset $A$ of $X,$ the least closed set containing $A$ is called the \textit{closure} of $A$, denoted by $cl_{% \mathbf{C}}(A).$ In fact, \begin{equation*} cl_{C}(A)=\cap \{B\left| B\in \mathbf{C}\right. \wedge A\subset B\}. \end{equation*} In [3],[4] and [5] we can find many examples of collections of sets sharing properties (cs1) and (cs2). It is not difficult to obtain the following result: \begin{proposition} If $\mathcal{P}(X)$ is the power set of $X,$ we have that \begin{equation*} \mathcal{C}(X)=\{S\subset \mathcal{P}(X)\left| S\right. ~is~a~closure~system~over~X\} \end{equation*} is a closure system over $\mathcal{P}(X).$ \end{proposition} The following useful properties are easily checked: \begin{proposition} If $\mathbf{C}$ is a closure system over $X$, the following properties are satisfied: \begin{equation*} \left\{ \begin{tabular}{ll} 1. & $\forall A\subset X$ $((A\in \mathbf{C}\Leftrightarrow cl_{\mathbf{C}% }(A)=A)\wedge (cl_{\mathbf{C}}(A)=A\Leftrightarrow cl_{\mathbf{C}}(A)\subset A)).$ \\ 2. & $\forall A\subset X$ $\left( cl_{\mathbf{C}}(cl_{\mathbf{C}}(A))=cl_{% \mathbf{C}}(A)\right) .$ \\ 3. & $\forall A,B\subset X\left( B\subset A\Rightarrow cl_{\mathbf{C}% }(B)\subset cl_{\mathbf{C}}(A)\right) .$ \\ 4. & $\forall A,B\subset X\left( cl_{\mathbf{C}}(A)\subset cl_{\mathbf{C}% }(B)\Leftrightarrow A\subset cl_{\mathbf{C}}(B)\right) .$ \\ 5. & $\forall \mathcal{A}\subset \mathcal{P}(X)~(cl_{\mathbf{C}}(\cup \mathcal{A})=cl_{\mathbf{C}}\left( \cup \{cl_{\mathbf{C}}(A)\left| ~A\in \mathcal{A}\right. \}\right) ).$ \\ 6. & $\forall A\subset X~$ $\forall x\in X~\left( x\in cl_{\mathbf{C}% }(A)\Leftrightarrow (\forall S\in \mathbf{C}~(A\subset S\Rightarrow x\in S))\right) .$% \end{tabular} \right. \end{equation*} \end{proposition} A signature is a set $\Sigma ,$ whose elements are called operation symbols, together with a mapping $ar:\Sigma \rightarrow \mathbb{N},$ called the arity function, assigning to each operation symbol its finite arity. A realization of an $n$-ary operation symbol in a set $A$ is an $n$-ary operation on $A.$ Given a signature $\Sigma ,$ a $\Sigma -$algebra $\mathbf{A}$ is a pair $% \mathbf{A=}(A,\Sigma ^{A})$ consisting of a set $A$ (called the carrier of $% \mathbf{A}$) and a family $\Sigma ^{A}=\{\sigma ^{A}\left| \sigma \in \Sigma \right. \}$ of realizations $\sigma ^{A}$ of operation symbols $\sigma $ from $\Sigma .$ In the following we simply speak of an algebra instead of a $% \Sigma -$algebra. If $\mathbf{A}$ is an algebra, a subset $B$ of $A$ is said to be closed (under the operations of $\mathbf{A)}$ if, for each $n$-ary operation symbol $\sigma \in \Sigma $ and all $x_{1},...,x_{n}$ in $A,$ \begin{equation*} x_{1},...,x_{n}\in B\Rightarrow \sigma ^{A}(x_{1},...,x_{n})\in B. \end{equation*} Restricting the operations on $A$ to a closed subset $B$ we get an algebra $% \mathbf{B}$ with $B$ as its carrier. $\mathbf{B}$ is called a \textit{% subalgebra} of $\mathbf{A.}$ \begin{definition} ([5]) A closure system $\mathbf{C}$ is called algebraic if there is an algebra such that $\mathbf{C}$ is equal to the set of all its subalgebras. \end{definition} The main target of this paper is to obtain a characterization of algebraic closure systems. The well known Birkhoff-Frink theorem establishes a characterization of algebraic closure systems in the following terms: \begin{theorem} (Birkhoff-Frink)([5]) A closure system $\mathbf{C}$ over $X$ is algebraic if and only if its closure operator satisfies the following finiteness condition: \begin{equation*} cl_{\mathbf{C}}(A)=\cup \{cl_{\mathbf{C}}(B)\left| ~B\subset A~\wedge ~B~is~finite\right. \} \end{equation*} for all subsets $A$ of $X.$ \end{theorem} \section{The Zorn condition} \begin{definition} We say that a closure system $\mathbf{C}$ satisfies the Zorn condition if for all non empty chain $\mathcal{C}$ of subsets of $\mathbf{C}$ we have that $\cup \mathcal{C}\in \mathbf{C}.$ \end{definition} It is not difficult to obtain the following result: \begin{proposition} Every algebraic closure system $\mathbf{C}$ over a set $X$ satisfies the Zorn condition. \end{proposition} In order to obtain the reciprocal, first we need to establish a lemma. \begin{notation} Given an arbitrary well-order $\leq $ over a set $A$, if $B$ is a finite subset of $A$ and $x\in A,$ then we use the following notation: \begin{equation*} B_{x}=B\cup \{y\in A\left| ~y\leq x\right. \}. \end{equation*} \end{notation} It is not difficult to obtain the following result, reasoning by transfinite induction: \begin{lemma} If $\mathbf{C}$ is a closure system over a set $X$, and $A$ is a subset of $% X,$ we have that \begin{equation*} \forall x\in A,\forall B\subset A\left( B\text{ finite }\Rightarrow cl_{% \mathbf{C}}(B_{x})=\cup \{cl_{\mathbf{C}}(D)\left| ~D\subset B_{x}\right. \wedge ~D~finite\}\right) \end{equation*} \end{lemma} Now we can prove the main theorem: \begin{theorem} If $\mathbf{C}$ is a closure system over $X,$ the following conditions are equivalent: \begin{equation*} \left\{ \begin{tabular}{ll} i) & $\mathbf{C}$ is an algebraic closure system. \\ ii) & $\mathbf{C}$ satisfies the Zorn condition. \end{tabular} \right. \end{equation*} \end{theorem} \textbf{Sketch of proof. }It suffices to show that $ii)\Rightarrow i).$ If $A$ is an infinite subset of $X,$ we consider the chain of elements of $% \mathbf{C}$ \begin{equation*} \left\{ cl_{\mathbf{C}}((\emptyset )_{x})\left| ~x\in A\right. \right\} , \end{equation*} and, since $\mathbf{C}$ satisfies the Zorn condition, we have that \begin{equation*} \cup \left\{ cl_{\mathbf{C}}((\emptyset )_{x})\left| ~x\in A\right. \right\} \in \mathbf{C.} \end{equation*} On the other hand, since \begin{equation*} A=\cup \left\{ (\emptyset )_{x}\left| ~x\in A\right. \right\} , \end{equation*} we can obtain that \begin{eqnarray*} cl_{\mathbf{C}}(A) &=&cl_{\mathbf{C}}(\cup \left\{ (\emptyset )_{x}\left| ~x\in A\right. \right\} )= \\ &=&\cup \left\{ cl_{\mathbf{C}}((\emptyset )_{x})\left| ~x\in A\right. \right\} . \end{eqnarray*} In order to conclude the proof, it suffices to show that \begin{equation*} \cup \left\{ cl_{\mathbf{C}}((\emptyset )_{x})\left| ~x\in A\right. \right\} =\cup \{cl_{\mathbf{C}}(B)\left| ~B\subset A~\wedge ~B~is~finite\right. \}.\square \end{equation*} We will proceed to give an application of this theorem. Given a set $X$ and $\mathcal{R}\subset \mathcal{P}(X)\times X,$ it is not difficult to check that \begin{equation*} \mathbf{C}_{\mathcal{R}}=\{A\subset X\left| \forall (R,x)\in \mathcal{R~}% (R\subset A\Rightarrow x\in A)\right. \} \end{equation*} is a closure system over $X$ (the closure system induced by $\mathcal{R}$)$.$ On the other hand, if $\mathbf{C}$ is a closure system over $X,$ and \begin{equation*} \mathcal{R}_{\mathbf{C}}=\{(A,x)\in \mathcal{P}(X)\times X\left| \mathcal{~}% x\in cl_{\mathbf{C}}(A)\right. \} \end{equation*} then $\mathbf{C}=\mathbf{C}_{\mathcal{R}_{\mathbf{C}}}.$ So, if we consider the following closure system over $\mathcal{P}(X)$ \begin{equation*} \mathcal{C}_{A}(X)=\{S\subset \mathcal{P}(X)\left| S\right. ~\text{% is~an~algebraic~closure~system~over~}X\}, \end{equation*} we can use the preceding theorem of this paper to obtain a new way to look at $\mathcal{C}_{A}(X):$ If $\mathbf{C}$ is a closure system over $X$ and \begin{equation*} \mathcal{R}_{A_{\mathbf{C}}}=\{(A,x)\in \mathcal{P}(X)\times X\left| \mathcal{~}A\mathcal{~}\text{is finite}\wedge x\in cl_{\mathbf{C}}(A)\right. \}, \end{equation*} we have that \begin{equation*} cl_{\mathcal{C}_{A}(X)}(\mathbf{C})=\mathbf{C}_{\mathcal{R}_{A_{\mathbf{C}% }}}, \end{equation*} and therefore the closure system $\mathcal{C}_{A}(X)$ is the closure system induced by $\mathcal{R}=\mathcal{R}_{S}\cup \mathcal{R}_{C},$ where \begin{equation*} \mathcal{R}_{S}=\{(\emptyset ,X)\}\cup \{(\mathcal{B},\cap \mathcal{B}% )\left| \mathcal{~B}\subset \mathcal{P}(X)\right. \wedge \mathcal{~B}\neq \emptyset \} \end{equation*} and \begin{equation*} \mathcal{R}_{C}=\{(\mathcal{B},\cup \mathcal{B})\left| \mathcal{~B}\subset \mathcal{P}(X)\right. \wedge \mathcal{~B}\neq \emptyset \wedge \mathcal{B~}% \text{is a chain}\}. \end{equation*} \begin{center} {\large References} \end{center} \begin{enumerate} \item Barnes D.W. and Mack J.M., \textit{An Algebraic Introduction to Mathematical Logic, }Springer Verlag, 1975. \item Cohen B. et al, \textit{The Specification of Complex Systems,} Addison Wesley, 1986 \item Gr\"{a}tzer G., \textit{General Lattice Theory}, second edition,Birkh\"{a}user, 1998. \item Hodges W., \textit{Model Theory}, Encyclopedia of Mathematics and its Applications 42, Cambridge University Press, 1993. \item Wechler W., \textit{Universal Algebra for Computer Scientists, }% Springer Verlag, Berlin-Heidelberg, 1992. \end{enumerate} \end{document}