universal-algebra.tex

\documentclass{article}

\usepackage{ctex}
\usepackage{tikz}
\usetikzlibrary{cd}

\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}

%\usepackage{unicode-math}


\usepackage[textwidth=18cm]{geometry} % 设置页宽=18

\usepackage{blindtext}
\usepackage{bm}
\parindent=0pt
\setlength{\parindent}{2em} 
\usepackage{indentfirst}


\usepackage{xcolor}
\usepackage{titlesec}
\titleformat{\section}[block]{\color{blue}\Large\bfseries\filcenter}{}{1em}{}
\titleformat{\subsection}[hang]{\color{red}\Large\bfseries}{}{0em}{}
%\setcounter{secnumdepth}{1} %section 序号

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{exercise}{Exercise}[section]

\newcommand*{\xfunc}[4]{{#2}\colon{#3}{#1}{#4}}
\newcommand*{\func}[3]{\xfunc{\to}{#1}{#2}{#3}}

\newcommand\Set[2]{\{\,#1\mid#2\,\}} %集合
\newcommand\SET[2]{\Set{#1}{\text{#2}}} %


\newcommand\slattice{\mathcal{S}}
\newcommand\lattice{\mathcal{L}}

\newcommand\Sg{\text{Sg}}
\newcommand\algebra{\mathbf{A}}
\newcommand\Sub[1]{\text{Sub}(#1)}

\newcommand{\redt}[1]{\textcolor{red}{#1}}
\newcommand{\bluet}[1]{\textcolor{blue}{#1}}

\begin{document}
\title{Lattice}
\author{枫聆}
\maketitle
\tableofcontents
\newpage
\section{The Elements of Universal Algebra}
\subsection{Definition and Examples of Algebras}
{\color{red}
One of the aims of universal algebra is to extract, whenever possible, the common elements
of several seemingly different types of algebraic structures}.

\begin{definition}
\rm For $A$ a nonempty set and $n$ a nonnegative integer we define $A^{0} = \{\emptyset\}$，and，for $n > 0$，$A^n$ is the set of n-tuples of elements from $A$. An {\color{red} n-ary operation} (or function) on $A$ is any function $f$ from $A^n$ to $A$; n is the {\color{red} arity} (or rank) of $f$. A {\color{red} finitary operation} is an n-ary operation，for some n. The image of $\left< a_1, \cdots , a_n \right>$ under an n-ary operation $f$ is denoted by $f(a_1,\cdots,a_n)$. An operation $f$ on $A$ is called a {\color{red} nullary operation} (or constant) if its arity is zero; it is completely determinded by the image $f(\emptyset)$ in $A$ of the only element $\emptyset$ in $A^0$, and as such it is convenient to identify it with the element $f(\emptyset)$. Thus a nullary operation is thought of as an element of $A$. An operation $f$ on $A$ is {\color{red} unary, binary, or ternay} if its arity is 1,2, or 3, respectively.
\end{definition}


\begin{definition}
\rm A {\color{red} language} (or type) of algebras is a set $\mathcal{F}$ of function symbols such a nonnegative integer $n$ is assgined to each member $f$ of $\mathcal{F}$. This integer is called the arity (or rank) of $f$, and $f$ is said to be an n-ary function symbol. The subset of n-ary function symbols in $\mathcal{F}$ is denoted by $\mathcal{F}_n$.
\end{definition}

\bluet{the language of algebra 就是一堆$n$元操作，简称n-ary function}. 

\begin{definition}
\rm If $\mathcal{F}$ is a language of algebras then an {\color{red} algebra} $\mathbf{A}$ of type $\mathcal{F}$ is an ordered pair $\left<A,F\right>$ where $A$ is a {\color{red} nonempty set} and $F$ is a family of {\color{red} finitary operations} on A indexed by the language $\mathcal{F}$ such that corresponding to each n-ary function symbol $f$ in $\mathcal{F}$ there is an n-ary operation $f^\mathbf{A}$ on $A$. The set $A$ is called the {\color{red} universe} ({\color{blue} 全域}) (or underlying set) of $\mathbf{A} =\left<A,F\right>$, and the $f^\mathbf{A}$ ’s are called the {\color{red} fundamental operations} ({\color{blue}基本运算}) of $\mathbf{A}$. (In practice we prefer to write just $f$ for $f ^\mathbf{A}$ —this convention creates an ambiguity which seldom causes a problem. However, in this chapter we will be unusually careful.) If $\mathcal{F}$ is finite, say $\mathcal{F} = \{f_1,\cdots,f_k\}$, we often write $\left<A, f_1,\cdots,f_k\right>$ for $\left<A,F\right>$, usually adopting the convention:
$$
\text{arity}~f_1 \geq \cdots \geq \text{arity}~f_k.
$$
An algebra $\mathbf{A}$ is {\color{red} unary} if all of its operations are unary, and it is mono-unary if it has just one unary operation.
\end{definition}

{\color{blue} 抽象来说一个algebra就是一个集合和一堆finitary operations构成的,在目前已经学到的代数中operation的arity大多数不会超过2(够modern).}

\begin{example}
\rm $\mathbf{A}$ is a {\color{red} groupoid} if it has just one binary operation; this operation is usually denoted by $+$ or $\cdot$, and we write $a+b$ or $a \cdot b$ for the image of $\left<a,b\right>$ under this operation, and call it the sum or product of $a$ and $b$, respectively.
\end{example}

\begin{definition}
\rm An alegebra $\mathbf{A}$ is {\color{red} finite} if $|\mathbf{A}|$ is finite, and trivial if $|\mathbf{A}|=1$. 
\end{definition}

\begin{example}
\rm Some well-known algebras
\begin{itemize}
	\item Group
	\item Semigroup (半群) and Monoid (幺半群)
	\item ...
\end{itemize}
\end{example}

\newpage
\subsection{Isomorphic Algebras and Subalgebras}

\begin{definition}
\rm Let $\mathbf{A}$ and $\mathbf{B}$ be two algebras of the {\color{red} same type} $\mathcal{F}$. Then a function $\func{\alpha}{A}{B}$ is an {\color{red} isomorphism} from $\mathbf{A}$ to $\mathbf{B}$ if $\alpha$ is one-to-one and onto, and for every n-ary $f \in \mathbf{F}$, and for $a_1,\cdots,a_n \in A$, we have
$$
\alpha f^\mathbf{A}(a_1,\cdots,a_n) = f^\mathbf{B}(\alpha a_1,\cdots,\alpha a_n).
$$
We say $\mathbf{A}$ is isomorphic to $B$, if there is a isomorphism from $\mathbf{A}$ to $\mathbf{B}$. i.e. suppose $f$ is  $*$, $\alpha(a * b) = \alpha(a) * \alpha(b)$. 
\end{definition}

{\color{blue} 老样子元素上保持bijective，对应的运算结果也保持一致}.

\begin{definition}
\rm Let $\mathbf{A}$ and $\mathbf{B}$ be two algebras of the same type. Then $\mathbf{B}$ is a {\color{red} subalgebra} of $A$ if $B \subseteq A$ and every fundamental operation of $\mathbf{B}$ is the restriction of the corresponding operation of $\mathbf{A}$, i.e., for each function symbol $f$, $f^\mathbf{B}$ is $f^\mathbf{A}$ restricted to $B$; we write simply $\mathbf{B} \leq \mathbf{A}$.

A {\color{red} subuniverse} of $\mathbf{A}$ is a subset $B$ of $A$ which is closed under the fundamental operations of $\mathbf{A}$, i.e., if $f$ is a fundamental n-ary operation of $\mathbf{A}$ and $a_1,\cdots,a_n \in B$ we wound required $f(a_1,\cdots,a_n) \in B$. 
\end{definition}

{\color{blue} 这个restriction就是只对定义域做限制的意思，subalgebra是一种构造新代数的方法，后面会学到另外几种. subalgebra和subuniverse的联系是，subalgebra一定是subuniverse，但是subuniverse不是一定是subalgebra，i.e 如果一个algebra有一个nullary，那么empty set是一个subuniverse，但是它是不是subalgebra}.

\begin{definition}
\rm Let $\mathbf{A}$ and $\mathbf{B}$ be of the same type. A function $\func{\alpha}{A}{B}$ is an embedding of $\mathbf{A}$ into $\mathbf{B}$ if $\alpha$ is one-to-one and satisfies
$$
\alpha f^\mathbf{A}(a_1,\cdots,a_n) = f^\mathbf{B}(\alpha a_1,\cdots,\alpha a_n).
$$
Such an $\alpha$ is also called a monomorphism. We say $\mathbf{A}$ can be embedded in $\mathbf{B}$ if there is an embedding of $\mathbf{A}$ into $\mathbf{B}$.
\end{definition}

{\color{blue} 单纯地去掉surjective.}

\begin{theorem}
\rm If $\func{\alpha}{A}{B}$ is an embedding, then $\alpha(A)$ is a subuniverse of $\mathbb{B}$.
\end{theorem}

\begin{proof}
我们需要说明$\alpha(A)$在对应的n-ary operation下保持封闭. 因为$\alpha$是embedding，所以对应一个n-ary operation $f$和$a_1,\cdots,a_n \in A$有
$$
f^\mathbf{B}(\alpha a_1,\cdots,\alpha a_n) = \alpha f^\mathbf{A}(a_1,\cdots,c_n) \in \alpha(A).
$$
已经证毕.
\end{proof}

\newpage
\subsection{Algebraic Lattices and Subuniverses}

{\color{red} 这一章阐述algebraic lattice是如何自然地出现在了universe algebra里面}.

\begin{definition}
\rm Given an algebra $\mathbf{A}$ define, for every $X \subseteq A$,
$$
\Sg(X) = \bigcap \Set{B}{X \subseteq B\ \text{and}\ B\ \text{is a subuniverse of}\ \mathbf{A}}.
$$ 
We read $\Sg(X)$ as "{\color{red} the subuniverse generated by $X$}".
\end{definition}

\begin{definition}
\rm A closure operator $C$ on the set $A$ is an {\color{red} algebraic closure  operator} if for $X \subseteq A$
$$
C(X) = \bigcup\Set{C(Y)}{Y \subseteq X\ \text{and}\ Y\ \text{is finite}}.
$$
\end{definition}

\begin{theorem}
\rm If we are given an algebra $\mathbf{A}$, then {\color{red} $\Sg$ is an algebraic closure operator} on $A$.
\end{theorem}

\begin{proof}
很明显任意地subuniverses交还是一个subuniverse，所有的subuiverses构成了一个closure system，所以$\Sg$是一个closure operator. 对于任意的$X \subseteq A$我们定义
$$
E(X) = X \cup \Set{f(a_1,\cdots,a_n)}{f\ \text{is a fundamental $n$-ary operation on}\ A\ \text{and}\ a_1,\cdots,a_n \in X}. 
$$
然后定义它的$n$次复合$E^n(X)$为
$$
\begin{aligned}
E^0(X) &= X \\
E^{n+1}(X) &= E(E^n(X)).
\end{aligned}
$$
由于$A$上所有fundamental operation都是finitary,且有
$$
X \subseteq E(X) \subseteq \cdots \subseteq E^n(X).
$$
接下来我们来证明下面的式子
$$
{\color{red} \Sg(X) = X \cup E(X) \cup E^2(X) \cup \cdots}.
$$
思路是(1)$\Sg(X) \subseteq X \cup E(X) \cup E^2(X) \cup \cdots$和(2)$X \cup E(X) \cup E^2(X) \cup \cdots \subseteq \Sg(X)$. 

(1) 我们从$X \cup E(X) \cup E^2(X) \cup \cdots$这种构造出发，实际上这种构造得到的就是包含$X$的最小subuniverse. 考虑它的bound，可能存在某个最小的$k$使得$E^{k+1}(E^k(X)) = E^k(X)$，那么当$i > k$时都有$E^i(X) = E^k(X)$，无疑问现在$E^k(X)$是一个subuniverse并且包含$X$，这其实就说明了$\Sg(X) \subseteq E^k(X)$. 如果你不能找到这样的$k$，那么会有若$i>k$，那么$E^k(X) \subset E^i(X)$，但是它是bound by $A$，且$\Sg(A) = A$，这是显然地.

(2) 任取$x \in \Sg(X)$, 我们用$\{Z_i\}_{i \in I}$表示所有such that $X \subseteq Z$且$Z$是$\mathbf{A}$的一个subuniverse. 那么对任意的$i$，有$x \in Z_i$. 那么我们更有
$$
\Sg(X) = E^n(Z_1) \cap E^n(Z_2) \cap \cdots.
$$
对任意的$n$成立. 并且我们还有
$$
E^n(X) \subseteq E^n(Z_1) \cap E^n(Z_2) \cap \cdots.
$$
这是因为每一项都有$E^n(X) \subseteq E^n(Z_i)$. 那么我们把$n$取遍，就可以得到
$$
X \cup E(X) \cup E^2(X) \cup \cdots \subseteq \Sg(X).
$$
综上$\Sg(X) = X \cup E(X) \cup E^2(X) \cup \cdots.$

那么对于任意的$a \in \Sg(X)$，都有$a \in E^n(X)$其中$n < \omega$ (omega 表示无穷远它比任何的自然数都大). 那么存在finite $Y \subseteq X$，使得$a \in E^n(Y)$. 这个过程就是把生成$a$的哪些元素在$E^{n-1}(X)$里面挑出来，然后循环往复，$n$是finite的，所以$Y$也是有限的. 这就说明了$\Sg(X) = \bigcap \Sg(Y_i)$，因为每一个$a$都可以找到一个finite $Y$.

还是写一下严格的归纳假设吧，首先我们点出一个关系. 注意到$E^{\cdot}$是单调的，那么给定两个集合$X,Y$，因为$X \subseteq X \cup Y$和$Y \subseteq X \cup Y$，所以$E^k(X) \cup E^k(Y) \subseteq E^k(X \cup Y)$.

我们要证明(1)任意的$x \in E^k(X)$都有finite set $Y \subseteq X$使得$x \in E^k(Y)$.

那么当$k=0$时，
$$
a \in E^0(X) = X  \Rightarrow a \in E^0(\{a\}),
$$
所以这里可以取$Y = \{a\}$.

假设对任意$k < n$，都有命题(1)成立，那么当$k=n$时，
$$
\begin{aligned}
a \in E^n(X) \Leftrightarrow& a \in E(E^{n-1}(X))\\ &= E^{n-1}(X) \cup \Set{f(a_1,\cdots,a_n)}{f\ \text{is a fundamental $t$-ary operation on}\ A\ \text{and}\ a_1,\cdots,a_n \in X}\\ &= E^{n-1}(X) \cup B_n,
\end{aligned}
$$
要么$a \in E^{n-1}(X)$或者$a \in B_n$. 如果$a \in E^{n-1}(X)$，那么归纳假设就完成了. 如果$a \in B_n$，则$a \in E(\{a_1,\cdots,a_t\})$，其中$a_1,\cdots,a_t \in E^{n-1}(X)$ (这里用$t$是不想和这个上标$n$弄混)，那么根据假设有$a_i \in E^{n-1}(Y_i)$，其中finite set $Y_i \subseteq X$，再替换一下
$$
a \in E(\{a_1,\cdots,a_t\}) \subseteq  E(\bigcup\limits_{1}^{t} E^{n-1}(Y_i))  \subseteq E(E^{n-1}(\bigcup\limits_{1}^{t} Y_i)) = E^n(\bigcup\limits_{1}^{t} Y_i).
$$
所以这里取$Y = \bigcup\limits_{i=1}^{t} Y_i$，它确实是一个finite set.

%最后的证明不规范 https://math.stackexchange.com/questions/725150/operator-generating-subuniverse-generated-by-x-is-algebraic-closure-operator
\end{proof}

\begin{corollary}
\rm If $\mathbf{A}$ is an algebra then $\mathcal{L}_{\Sg}$, the lattice of subuniverses of $\mathbf{A}$, is an algebraic lattice.
\end{corollary}

\newpage
\begin{definition}
\rm Given an algebra $\algebra$, {\color{red} $\Sub{\algebra}$} denotes the set of subuniverses of $A$, and $\Sub{\algebra}$ is the corresponding algebraic lattice, the lattice of subuniverses of $\algebra$. For $X \subseteq A$ we say $X$ generates $\algebra$ if $\Sg(X) = A$. The algebra $\algebra$ is finitely generated if it has a finite set of generators.
\end{definition}

{\color{blue} 如果$A$有有限多个生成元，那么就说algebra $\algebra$是有限生成的}.


\begin{theorem}
\rm {\color{red} (closed sets对应某个algebra的universes)} Let $\Gamma$ be an algebraic closure operator on a set $X$. Then there is an $\algebra$ on the set $X$ such that the subuniverse of $\algebra$ are precisely the closed sets of $\Gamma$.
\end{theorem}

\begin{proof}
Basic: 我们要构造出来一个algebra $\algebra$，首先我们得确定在哪个集合上，再给定它的operations. 

我们的目标: 当前的前提是给定$X$上的algebraic closure operator $\Gamma$，以$X$为underlying set，构造其上的operations使得对应的algebra $\algebra$ 的universes都是$\Gamma$对应的closed set.

对任意的finite set $B \subseteq X$和任意的$b \in \Gamma(B)$，我们定义n-ary operation如下，其中$n = |B|$.
$$
f_{B,b}(a_1,\cdots,a_n) = \left\{
\begin{array}{ll} 
b \ & \text{if}\ B=\{a_1,\cdots,a_n\} \\ 
a_1\ & \text{otherwise}.  
\end{array}
\right.   
$$
接下来我们证明$\Gamma$对应的closed set $A$是一个在上面定义的operations下是封闭的. 这里明显地有
$$
f_{B,b}(a_1,\cdots,a_n) \subseteq \Gamma(\{a_1,\cdots,a_n\}).
$$
这里我们再利用一个结论（证明在lattice note里面），(1)$\Gamma$是algebraic closure operation，那么若$A \subseteq X$是一个closed set当且仅当$\Gamma(F) \subseteq A$对所有的finite set $F \subseteq A$成立. 那么任取对任意上述的operation，我们取$a_1,\cdots,a_n \in A$，那么
$$
f_{B,b}(a_1,\cdots,a_n) \subseteq \Gamma(\{a_1,\cdots,a_n\}) \subseteq A
$$
所以上述所有的operations在$A$下是封闭.

反过来我们还要证明一个universe $S$ 是closed set. 还是用(1)这个结论，我们证明所有的finite set $B \subseteq S$，$\Gamma(B) \subseteq S$，其中
$$
\Gamma(B) = \Set{f_{B,b}(a_1,\cdots,a_n)}{B={a_1,\cdots,a_n},b \in \Gamma(B)}.
$$
自然地，因为$f_{B,b}(a_1,\cdots,a_n)$在$S$下是封闭的，这个operation的构造就巧到这里，所以$\Gamma(B) \subseteq S$.
\end{proof}


\begin{theorem}
\rm {\color{red} (algebraic lattice同构于某个algebra的universes构成的lattice)} If $\lattice$ is an algebraic lattice, then $\lattice \cong \Sub{\algebra}$, for some algebra $\algebra$.
\end{theorem}

\begin{proof}
这个命题是上面命题的一个推论，这里的$\algebra$的underlying set可以设为$\lattice^c$即$\lattice$上所有的compact elements. 关于这一点去看lattice note里面$\lattice \cong \mathcal{C}_{\Delta}$部分. 那么接下来就是证明$\Sub{A} =  \mathcal{C}_{\Delta}$，这里有更比上面更简单的operations的构造方式. 对任意的$a \in \mathcal{C}_{\Delta}$, 定义一个unary operation
$$
f_{a}(x) = \left\{
\begin{array}{ll} 
a \ & \text{if}\ a \leq x \\ 
x\ & \text{otherwise}.  
\end{array}
\right.  
$$
把这样的unary operation作用到某个$x \subseteq \lattice^c$，它生成就是principle ideal $\downarrow x$，自然地到某个$A \subseteq lattice^c$，它就是$\Delta(A)$.
\end{proof}

\newpage
\subsection{The Irredundant Basis Theorem}

\begin{definition}
\rm Let $C$ be a closure operator on $A$. For $n < \omega$, let $C_n$ be the function definied on $\text{Su}(A)$ (power set) by 
$$
C_n(X) = \bigcup\Set{C(Y)}{Y \subseteq X,\ |Y| \leq n}.
$$
We say that $C$ is $n$-ary if 
$$
C(X) = C_n (X) \cup C_n^2(X) \cup \cdots,
$$
where 
$$
\begin{aligned}
C_n^1(X) &= C_n(X), \\
C_n^{k+1}(X) &= C_n(C_n^k(X)).
\end{aligned}
$$
也可以用$C(X) = C_n^{\omega}(X)$来表示，其中$\omega$表示基数最小infinite set的基数. Tarski原本$C_n$的definition里面去掉了$|Y| \leq n$中的等号，这个$n$也叫做the rank of $(A,C)$. 
\end{definition}
%https://pdf.sciencedirectassets.com/271536/1-s2.0-S0012365X00X02609/1-s2.0-0012365X75900333/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjEJ3%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLWVhc3QtMSJIMEYCIQDWjKUirhbVYtbBPzl18bAayuiamGcqjF4cCbt4l%2FqGswIhAIRpADqK85EmjFgXTJQa70PmJDOV4DYB0iRQ5vV%2BMDt2Kr0DCNX%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEQAxoMMDU5MDAzNTQ2ODY1IgxaBY6PwiSWwALol%2BgqkQNbGw6RJ0FfAR2LIdBE52bbJIPsfvJGAvfII6W%2FNsldi8Dpd0KeAs1ocLWPWu%2BhEF1s6nr8JoZqoXYj6vOHCDPkMTFzljMzKl54Onl%2BS4jhkA77aE5LztNlXhehZlIWKrSQhNr43bbrY9IVW239WldemfFVPOuLdBCMeefzDazqScmrnlNUy7AwEOHyNSlUDkZuz7GaoUNZvtJx5EoPAo%2BJxf4KNWhE6%2FK%2FiX6y1ZGPzQQrUxvZoc0ihSMqziC59shVnvZdhzGQwUhCoLhS4786syVNHZYe9%2BDbbbVAw2WQGS5ZWGjh0tjUg6JMUAmWqW%2Fd0Dn7zg6Stuctb3%2BEzzshy%2B8kblanPDRm9c4lTKkllta8Bz4tbDQ2QB%2BwTpImLccR6wG5w13mI8CxphT2d%2FjwVcS6YKs18s%2FFar1777yYnICU02eQ3UshS9fvWp7P366Cg2LAYtlPxi0fd6zK7XUyCF3ghUsCncUtRGJohk1MAzhACMGQJSt32%2BvGnWqg%2F8XZL4rHofp%2Fxc1acu69MRJ9rzCD1uyCBjrqAWUqtClc5LxtxcxhLBv1QrCJ0DlSTaGLpLfHIKTkAc365zT26tUaMfeh94JOg%2B1Ky4K%2F4Ha%2FJrywGQJeeUM9sXm0cNMwA%2FovVf2VzCHXXancu8rxL9MfEW%2FDJxjV9Ev3uj%2BY55POhuTxH5aGRxAT12QNJAc%2BSKdqpRvQ08j4H%2B1R%2FZRjOpP8iAiDRNTgo6JZA2CU0rCPLQrXCyoz01n1Ta6qtLhL4Iq5MXBt02%2FP%2FtFuUi6LKLBgqquQLSrK%2BAzb4pXciLwUv81UQbI66OnRf25sLwz9X%2Fvu6bQ9%2FmwAicxOu4JuJUJma8o7bg%3D%3D&X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Date=20210324T132857Z&X-Amz-SignedHeaders=host&X-Amz-Expires=300&X-Amz-Credential=ASIAQ3PHCVTYS6IXFU5I%2F20210324%2Fus-east-1%2Fs3%2Faws4_request&X-Amz-Signature=befd72904a96fb4310db932fb1448733eedd8419d0115911f15d28c5bb9e8d5b&hash=4acfc458cfe99335888ff2b376398155000dd6e9e3868490c2e55e316080af04&host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&pii=0012365X75900333&tid=spdf-d1eaed5e-918a-4bfd-af1c-59511093703f&sid=7d0d80a511ba8648b06beed4b4885ab20a62gxrqa&type=client


\begin{lemma}
\rm Let $\algebra$ be an algebra all of whose fundamental operations have arity at most $n$. Then $\Sg$ is an $n$-ary closure operator on $A$.
\end{lemma}

\begin{proof}
从Theorem 1.13我们得到
$$
 E(X) \subseteq (\Sg)_n(X) \subseteq \Sg(X),
$$
第一个$\subseteq$由$E(X)$的definition，第二个$\subseteq$由$\Sg$的definition. 因此
$$
\begin{aligned}
\Sg(X) &= X \cup E(X) \cup E^2(X) \cup \cdots \\
 &\subseteq (\Sg)_n(X) \cup (\Sg)_n^2(X) \cup \cdots \\
 &\subseteq \Sg(X).
\end{aligned}
$$
所以$\Sg(x) = (\Sg)_n(X) \cup (\Sg)_n^2(X) \cup \cdots . $
\end{proof}

\begin{theorem}
\rm Let $C$ be a closure operator on $A$. $A'$ is closed set such that $C(A') = A'$ and $C'$ is the restriction of $C$ to the family of subsets of $A'$. Then $C'$ is also a closure operator; if, moreover, $C$ is $n$-ary,then so is $C'$. 
\end{theorem}

\begin{proof}
$C'$是closure operator这是显然的，对于任意的$B' \subseteq A'$, $C'(B') = C(B')$，所以它们两个rank是相同的. 
\end{proof}


\begin{definition}
\rm The set $X$ is a {\color{red} minimal generating set} for $Y$ if $X$ generates $Y$ and no proper subset of $X$ generates $Y$.
\end{definition}

\begin{definition}
\rm Let $C$ be a closure operator on $S$. A set $X \subseteq S$ is called {\color{red} irredundant} if $y \notin C(X-\{y\})$ for every $y \in X$. 
\end{definition}

\begin{definition}
\rm Suppose $C$ is a $n$-ary closure operator on $S$. A minimal generating set of $S$ is called an {\color{red} irredundant basis}. Let $\text{IrB}(C) = \SET{n \leq \omega}{$S$ has an irredundant basis of n elements}.$
\end{definition}

\begin{proposition}
\rm If $S$ has a finite basis $B$, then it also has a finite irredundant basis $B'$, so $\text{IrB}(S)$ is not empty. 
\end{proposition}

\begin{proposition}
\rm If $C$ is finite ary, then every basis for $S$ includes a finite irredundant basis. So that no infinite basis of $S$ is irredundant. Thus $\text{IrB}(S)$ is the set of cardinalities of all irredundant basis for $S$.
\end{proposition}


\begin{theorem}
\rm If $C$ is an $n$-ary closure operator on $S$ with $n \geq 2$, and if $i < j$ with $i, j \in \text{IrB}(C)$ such that 
$$
\{i+1,\cdots,j-1\} \cap \text{IrB}(C) = \emptyset,
$$
then $j-i \leq n-1$. In particular, if $n=2$ then $\text{IrB}(C)$ is a convex subset of $\omega$, i.e., a sequence of consecutive numbers. 
\end{theorem}

\begin{proof}
让$B$是一个irreducible basis且$|B| = j$. 让$K$表示那些irreducible basis $A$且$|A| \leq i$构成的集合. 我们的策略是从$K$里面挑一个$A_0$出来，让这个$A_0 \subseteq C_n^{t+1}(B)$但是$A_0 \nsubseteq C_n^{t}(B)$，那么再取一点$a_0 \in C_n^{t+1}(B) - C_n^{t}(B)$，把这个$a_0$替换成$c_1,\cdots,c_m \in C_n^{t}(B)$，这样构成了一个新的base $A_1$，它里面是有一个irredundant basis $A_2$的，我们来探讨$A_2$存在性. 这是基本的想法，下面来阐述一下这个想法的细节。

\begin{center}
\includegraphics[scale=0.5]{./images/irredundant.png}
\end{center}


首先$B$是一个irreducible basis且$C$是一个$n$-ary closure operator，那么
$$
A \subseteq S = C(B) = C_n^{\omega}(B).
$$
我们由前面的命题可以知道$A$是一个finite set且是一个base，那么$A \nsubseteq B$. 且$C_n^{k+1} \supseteq C_n^{k}$，那么是可以找到某个$t$使得$A \subseteq C_n^{t+1}(B)$且$A \nsubseteq C_n^{t}(B)$的，这就是为什么可以找到上面$A_0$的原因. 并且如果我们找到这样的$A_0 \in K$，那么
$$
A_0 \nsubseteq C_n^t(B)\ \text{implies} \ A \nsubseteq C_n^{t}(B),
$$
对任意的$A \in K$成立. 假设不成立，会得到$A$不是irreducible的，这是矛盾的. 我们再考虑对于$A \in K$且$A\subseteq C_n^{t+1}(B)$，我们假设
$$
|A_0 \cap (C_n^{t+1}(B) - C_n^{t}(B))| \leq |A \cap (C_n^{t+1}(B) - C_n^{t}(B))|,
$$
我们让$A_0$更靠近$B$一点，就是指$C_n^{t+1}(B)$和$C_n^t(B)$中间这个环，包含更少一点$A_0$中的点. 这样做的目的就是让后面得到的新base的基数尽可能的小. 然后我们选择一点$a_0 A_0 \cap (C_n^{t+1}(B) - C_n^{t}(B))$. 那么肯定是存在$b_1,\cdots,b_m \in C_n^t(B)$，其中$m \leq n$，使得
$$
a_0 \in C_n({b_1,\cdots,b_m}).
$$
然后把$a_0$替换掉得到的新base $A_1 = (A - \{a_0\}) \cup \{b_1,\cdots,b_m\}$，那么$A_0 \subseteq C(A_1)$，所以
$$
C(A_0) \subseteq C(A_1).
$$
那么在$A_1$上我们是可以找到一个irredundant basis $A_2 \subseteq A_1$. 现在我们有$|A_2| < |A_0| + n$. 如果$|A_0| + n \leq j$，那么这个$A_2$会和我们选择的$A_0$造成矛盾，为什么呢？ 因为我们前提是$i$和$j$之间是没有irreducible basis的，那么$|A_2| \in K$, 同时$A_2 \subseteq C_n^{t+1}(B)$，就会造成
$$
|A_2 \cap (C_n^{t+1}(B) - C_n^{t}(B))| < |A_0 \cap (C_n^{t+1}(B) - C_n^{t}(B))|.
$$
所以这里$|A_0| + n \geq j$，其中$|A_0| \leq i$，那么就可以得到$j - i \leq n$.

我们来理一下关系，这个命题在讲如果两个irredundant basis的基数之间距离小到一定程度，你找不到一个irreducible basis的基数在它们之间. 这个距离如何描述呢？ $j-i < n$. 上面证明的方法是尝试在irreducible basis 基数小于$i$的basis的基础上构造一个新的irreducible basis出来，看它落在哪里. 

现在我们构造了出来了这个新的irreducible basis $A_2$，我们只知道$|A_2| < i + n$，并不知道它和$i$和$j$有什么关系. 

我们先来思考一下$|A_2|$和$i$的关系，我们先得思考一下$A_0$取法的特殊性，$A_0$ minimal condition这个性质可以让我们取出来$A_2$它不在$K$里面的，因为$A_0$ minimal condition是相对于整个$A \in K$且$A \subseteq C_n^{t+1}(B)$而言的，这是我们的假设。所以$|A_2| > i$.

那么$|A_2|$和$j$的关系如何呢？我们来比较$|A_2|$的upper bound和$j$的关系. 然后我们知道了这个upper bound不能小于等于$j$的，所以最后得到了我们想要的结论.
\end{proof}
\end{document}