用户: 上埜久/泛代数初步

1关于集论符号的说明

在 MK 中, 有属于关系 $A\in B$, 等于关系是与任何性质相容的等价关系

定义 1.1 (子类). 子类 $A\subseteq B⟺(\forall x\in A)x\in B$

引理 1.2. $A\subseteq A$ 且 $A\subseteq B\subseteq C⟹A\subseteq C$

证明.

证明. 显然

$\square$

类外延公理

$$A\subseteq B\wedge B\subseteq A⟹A=B$$

注 1.3. 换句话说, 子类关系是偏序关系.

定义 1.4 (集与真类). 某类的元素称为集. 不为集的类称为真类 (proper class).

在 MK 中对每个关于类 $X$ 性质 $P(X)$ 有 classifier 类 $\{X\mid P(X)\}$

classification 公理模式

$$x\in \{X\mid P(X)\}⟺P(x)成立$$

引理 1.5 (Russell 悖论). 类 $R=\{X\mid X\notin X\}$ 真类. 特别地, 类 $\{X\mid P(X)\}$ 不必为集.

证明.

证明. 注意到 $R\in R⟹R\notin R$, 若 $R$ 是集则 $R\notin R⟹R\in R$ 矛盾!

$\square$

定义 1.6 (空类与全类). 空类 $0:=\varnothing :=\{X\mid X\ne X\}$, 全类 $V:=\{X\mid X=X\}$

注 1.7. 显然 $X\in V$ 当且仅当的 $X$ 是集.

子集公理

$$(\forall A\in V)(\exists B\in V)P\left(A\right)\subseteq B$$

并, 交, 无序对, 幂类与中学别无二致, 只需注意空交为全类.

幂类亦称布尔类

定义 1.8 (宇宙集). 若一个传递集 $U$ 对幂集, 无序对合任意并封闭, 则称为一个宇宙集

宇宙公理

每个集是某个宇宙集的元素

定义 1.9 (归纳集). 若 $N\subseteq U$ 满足 $\varnothing \in N$ 和 $X\in N⟹X+1:=X\cup \{X\}\in N$ 则称为归纳集.

显然宇宙集是归纳集.

定义 1.10 (自然数集). 令 $\mathbb{N}=\bigcap \{N\subseteq U\mid N是归纳集\}$

注 1.11. 显然自然数集是最小的归纳集, 而归纳原理显然易证. 显然 $n\in \mathbb{N}⟹n+1\ne 0$

注 1.12. $n,m\in \mathbb{N}⟹n\in m⟹n\subseteq m$

证明.

证明. 令 $M=\{m\in \mathbb{N}\mid (\forall n\in \mathbb{N})(n\in m⟹n\subset m)\}$, 显然 $0\in M$. 若 $m\in M$ 且 $n\in m+1$, 则 $n\in m\vee n=m$, 从而总有 $n\subseteq m\subseteq m+1$.

$\square$

注 1.13. $n+1\subseteq m+1⟹n\subseteq m$

证明.

证明. 由 $n\in n+1$ 知 $n\in m\vee n=m$, 从而 $n\subseteq m$.

$\square$

引理 1.14. $n+1=m+1⟹n=m$

证明.

证明. 自证不难.

$\square$

引理 1.15 (自然数无穷). 对任意 $n\in \mathbb{N}$ 不存在满射 $n\to \mathbb{N}$.

证明一.

证明一. 令 $M=\{n\in \mathbb{N}\mid 不存在满射n\to \mathbb{N}\}$, 显然 $0\in M$. 设 $n\in M$ 且 $n+1\notin M$, 则有满射 $f:n+1\to \mathbb{N}$. 定义 $g:n\to \mathbb{N}$ 如下: 若 $f(k)\subseteq f(n)$ 则 $g(k)=f(k)$, 否则 $g(k)=f(k)-1$

$\square$

证明二.

证明二. 依 Peano 公理不存在最大自然数.

$\square$

推论 1.16. 非空宇宙集无穷

定义 1.17 (部分良序集与良序集). 若偏序集满足任意非空子集的极小元集非空有限 (resp. 单元素集), 则称为部分良序集 (resp. 良序集)

定理 1.18 (Newman 定理). 设预序集 $A$ 满足

1.	对每个 $a\in A$ 存在 $k\in {\mathbb{N}}^{+}$ 使得每个从 $a$ 开始的无穷递降列至多 $k$ 个不等式严格
2.	若 $b,c$ 是 $A_{<a}$ 的两个极大元则 $\{b,c\}$ 在 $A$ 中有下界

则 $A$ 的连通分量与 $A$ 的极小元集等势.

证明.

证明. 若 $a\le b\le a$ 则必然 $a=b$ 否则与 (1) 矛盾, 因此 $A$ 是偏序集. 设 $C$ 是 $A$ 的一个连通分量, 若没有极小元则与 (1) 矛盾, 因此每个连通分量 $C$ 有极小元 $m(C)$. 由连通分量定义知 $m(C)$ 也是 $A$ 的极小元. ...

$\square$

定义 1.19 ().

定义 1.20 ().

定义 1.21 ().

定义 1.22 ().

2通用代数

通用代数 (universal algebra) 亦称泛代数或万有代数, 其概念在代数、几何、逻辑与语言学中亦译名多变, 常仅择其一者.

定义 2.1 (算子区域). 一个算子区域的资料如下

1.	一个集合 $\Omega$, 称为算子集、运算符号集
2.	一个映射 $\alpha :\Omega \to \mathbb{N}$, 称为 arity 或 weight 函数

算子区域简称算子区, 常滥用记号以基础集 $\Omega$ 记之.

定义 2.2 (通用代数). 设 $\Omega$ 是一个算子区, 则一个 $\Omega$(通用) 代数资料如下:

1.	一个集合 $X$, 称为变量集
2.	一族映射 ${\left({\mathrm{act}}_{\omega }^X:X^{\alpha (\omega )}\to X\right)}_{\omega \in \Omega }$, 称为作用函数或外运算

常滥用记号 ${\omega }_X={\mathrm{act}}_{\omega }^X$

注 2.3. 算子 ${\omega }_X$ 作用在变量序列上的值常用 Jan Lukasiewicz 的波兰前缀记号 (polish prefix notation)

定义 2.4 (代数同态). 设 $\Omega$ 是一个算子区且 $X$ 和 $Y$ 是两个 $\Omega$ 代数, 则一个 $\Omega$ 代数同态 $f:X\to Y$ 是一个满足下列条件的映射: 对每个 $\omega \in \Omega$ 下列图表交换

定理 2.5 (代数范畴). $\Omega$ 是一个算子区, 则 $\Omega$ 代数与 $\Omega$ 代数同态组成一个范畴 ${\mathsf{Alg}}_{\Omega }$, 称为 $\Omega$ 代数范畴

证明.

证明. 由交换图易证

$\square$

定义 2.6 (子代数). 设 $\Omega$ 是一个算子区且 $X$ 和 $Y$ 是两个 $\Omega$ 代数. 若 $X\subseteq Y$ 且含入映射 $ı:X\to Y$ 是一个 $\Omega$ 代数同态, 则称 $X$ 是 $Y$ 的一个子代数, 滥用符号记为 $X\le Y$

定义 2.7 (容许子集). 设 $\Omega$ 是一个算子区且 $Y$ 是一个 $\Omega$ 代数. 若 $X\subseteq Y$ 且对每个 $\omega \in \Omega$ 有 ${\omega }_Y⟨X^{\alpha (\omega )}⟩\subseteq X$ 则称 $X$ 是 $Y$ 的一个 $\Omega$ 容许子集

引理 2.8 (子代数与容许子集一一对应). 设 $\Omega$ 是一个算子区且 $Y$ 是一个 $\Omega$ 代数. 若 $X\subseteq Y$, 则 $X$ 是 $Y$ 的一个容许子集当且仅当存在唯一 $X$ 上作用函数使得 $X\le Y$. 换句话说, 下列映射$$\Phi :{\mathrm{Adm}}_{\Omega }(Y)\ni X\mapsto \left(X,({\omega }_Y{|}_{X^{\alpha (\omega )}}^X{)}_{\omega \in \Omega }\right)\in {\mathrm{Subalg}}_{\Omega }(Y)$$有逆映射$$\Psi :{\mathrm{Subalg}}_{\Omega }(Y)\ni \left(X,({\omega }_X{)}_{\omega \in \Omega }\right)\mapsto X\in {\mathrm{Adm}}_{\Omega }(Y)$$

证明.

证明. 若 $X$ 是 $Y$ 的一个容许子集, 则令 ${\omega }_X={\omega }_Y{|}_{X^{\alpha (\omega )}}^X$, 从而 $X\le Y$. 反之, 若存在 $X$ 上作用函数 $({\omega }_X{)}_{\omega \in \Omega }$ 使得 $X\le Y$, 则 ${\omega }_Y⟨X^{\alpha (\omega )}⟩={\omega }_X⟨X^{\alpha (\omega )}⟩\subseteq X$, 且 ${\omega }_X={\omega }_Y{|}_{X^{\alpha (\omega )}}^X$.

$\square$

注 2.9. 因此也常滥用记号 $X\le Y$ 表示 “$X$ 是 $Y$ 的一个容许子集”.

引理 2.10 (容许子集族 Moore). 容许子集族 ${\mathrm{Adm}}_{\Omega }(Y)$ 是 Moore 族, 即对任意交封闭

证明.

证明. 由集论知识显然

$\square$

定义 2.11 (生成子代数). 设 $\Omega$ 是一个算子区且 $Y$ 是一个 $\Omega$ 代数. 若 $S\subseteq Y$, 则称 $\mathrm{Cl}\left(S\right):=\bigcap \{X\subseteq Y\mid S\subseteq X\in {\mathrm{Adm}}_{\Omega }(Y)\}$ 为子集 $S$ 生成的 $\Omega$ 容许子集, 其在 $\Phi$ 下的像为子集 $S$ 生成的子 $\Omega$ 代数.

引理 2.12. 滤过容许子集族的并 ${\bigcup }_{i\in I}{X}_i$ 是容许子集

证明.

证明. 因为 $\alpha (\omega )\in \mathbb{N}$, 由假设知存在 $k\in I$ 使得 ${\left({\bigcup }_{i\in I}{X}_i\right)}^{\alpha (\omega )}\subseteq X_k^{\alpha (\omega )}$, 从而$${\omega }_Y⟨\bigcup _{i\in I}{X}_i⟩\subseteq {\omega }_Y⟨X_k^{\alpha (\omega )}⟩\subseteq X_k\subseteq \bigcup _{i\in I}{X}_i$$

$\square$

引理 2.13. 设 $\Omega$ 是一个算子区且 $Y$ 是一个 $\Omega$ 代数. 若 $S\subseteq Y$, 递归定义 $A_0=S$, 及 $A_{n+1}=A_n\cup {\bigcup }_{\omega \in \Omega }{\omega }_Y⟨A_n^{\alpha (\omega )}⟩$, 则 ${\bigcup }_{n\in \mathbb{N}}{A}_n=\mathrm{Cl}\left(S\right)$.

证明.

证明. 显然有 $A_n\subseteq A_{n+1}$, 则 $\{A_n\mid n\in \mathbb{N}\}$ 滤过, 从而存在 $k\in I$ 使得 ${\left({\bigcup }_{n\in \mathbb{N}}{A}_n\right)}^{\alpha (\omega )}\subseteq A_k^{\alpha (\omega )}$, 因此$${\omega }_Y⟨{\left(\bigcup _{n\in \mathbb{N}}{A}_n\right)}^{\alpha (\omega )}⟩\subseteq {\omega }_Y⟨A_k^{\alpha (\omega )}⟩\subseteq A_{k+1}\subseteq \bigcup _{n\in \mathbb{N}}{A}_n$$于是 $S\subseteq {\bigcup }_{n\in \mathbb{N}}{A}_n\in {\mathrm{Adm}}_{\Omega }(Y)$. 另一方面, 若 $S\subseteq B\in {\mathrm{Adm}}_{\Omega }(Y)$, 则由数学归纳法易证 $(\forall n\in \mathbb{N})A_n\subseteq B$.

$\square$

注 2.14. 这说明生成容许子集确由生成集 $S$ 和 $\Omega$ 中的运算符号 “生成” 得到

定理 2.15 (代数范畴中积对象与等化子的典范构造). 令 $U:{\mathsf{Alg}}_{\Omega }\to \mathsf{Set}$ 表示遗忘函子.

•

设 $\{X_i\mid i\in I\}$ 是一族 $\Omega$ 代数, 对每个 $\omega \in \Omega$ 定义$${\omega }_{{\prod }_{i\in I}U(X_i)}:{\left(\prod _{i\in I}U(X_i)\right)}^{\alpha (\omega )}\ni x={\left({\left(x_{j,i}\right)}_{i\in I}\right)}_{j\in \alpha (\omega )}\mapsto {\left({\omega }_{A_i}{\left({\mathrm{pr}}_i(x_j)\right)}_{j\in \alpha (\omega )}\right)}_{i\in I}\in \prod _{i\in I}U(X_i)$$即对每个 $i\in I$ 投影 ${\mathrm{pr}}_i$ 都是代数同态, 则 ${\prod }_{i\in I}U(X_i)$ 连同上式定义的作用函数组成 ${\mathsf{Alg}}_{\Omega }$ 的一个典范积对象.

•

设 $f,g:X\to Y$ 是两个 $\Omega$ 代数同态, 在 $\mathsf{Set}$ 中的等化子 $\mathrm{equ}\left(f,g\right)$ 是 $X$ 的一个容许子集,

特别地, 代数范畴 ${\mathsf{Alg}}_{\Omega }$ 完备

证明.

证明.

•	由交换图, 两次使用 $\mathsf{Set}$ 中积对象的泛性质即可
•	注意到$$x\in (\mathrm{equ}\left(f,g\right){)}^{\alpha (\omega )}⟹f({\omega }_X(x))={\omega }_Y{\left(f(x_i)\right)}_{i\in \alpha (\omega )}={\omega }_Y{\left(g(x_i)\right)}_{i\in \alpha (\omega )}=g({\omega }_X(x))$$由交换图, 两次使用 $\mathsf{Set}$ 中等化子的泛性质即可

$\square$