汇编

汇编是一种定义具现意象的工具, 可以理解为集合带上一组具现子, 这些具现子取值于某个固定的部分组合代数, 扮演了这个集合的某种计算方面的解释的角色.

1定义

定义 1.1. 令 $A$ 为部分组合代数, 则一个汇编 $X$ 由如下数据组成:

•

集合 $|X|$,

•	集合映射 $[-{]}_X:|X|\to {\mathcal{P}}_{\ge 1}(A)$, 其中 ${\mathcal{P}}_{\ge 1}(A)$ 是有元素的 $A$ 的子集的集合.

集合 $[x{]}_X$ 中的元素对应了具现子.

定义 1.2. 若映射 $[-{]}_X$ 的取值均为单点集, 那么该汇编是划分的.

定义 1.3. 同一个部分组合代数 $A$ 上的汇编 $X,Y$ 之间的态射 $f:X\to Y$ 为集合映射 $f:|X|\to |Y|$ 加上如下条件:

存在 $a\in A$ 使得对于任意 $x\in |X|$ 和 $b\in [x{]}_X$, 满足 $(a\cdot b)\in [f(x){]}_Y$ (这隐含了该表达式在 $A$ 中有定义). 在这种情况下, 称 $a$ 追踪了映射 $f:|X|\to |Y|$.

注 1.4. 该定义中使用的是 $a$ 的存在性, 而不是 $a$ 本身. 换言之, 若存在多个不同的 $a$ 都追踪了 $f$, 这不意味着存在多个不同的态射.

定义 1.5. 部分组合代数 $A$ 上的汇编构成一个范畴, 记作 $\mathrm{Asm}(A)$. 其中, 划分的汇编构成的范畴记作 $\mathrm{PAsm}(A)$.

定理 1.6. $\mathrm{Asm}(A)$ 是局部积闭范畴.

(... 构造还没找到)

2例子

$\omega$-集

定义 2.1. 令 ${\mathcal{K}}_1$ 为 Kleene 第一代数, 则其上的汇编叫做 $\mathbf{\omega }$-集, 记 $\mathrm{Asm}({\mathcal{K}}_1)$ 为 $\omega \text{-}\mathsf{Set}$.

定理 2.2. $\omega \text{-}\mathsf{Set}$ 是积闭范畴.

证明. 考虑单射 $⟨-,-⟩:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ 可得积的构造. 幂对象 $Y^X$ 定义如下:

•	$|Y^X|$ 为被追踪的映射 $f:X\to Y$ 的集合.
•	$[f{]}_{Y^X}$ 为追踪 $f$ 的自然数的集合.

$\square$

定理 2.3. 遗忘具现子的函子 $U:\omega \text{-}\mathsf{Set}\to \mathsf{Set}$ 存在一全忠实右伴随 $U⊣\nabla$, 其中 $\nabla$ 将 ${\mathcal{K}}_1$ 全体元素视为任意集合的具现子.

证明. 该函子全忠实是因为任何集合映射都可以由任何自然数追踪. 该函子为右伴随是因为对于汇编 $X$ 和集合 $Y$, 由 1.4 可知如下两命题逻辑等价: $$f:X\to \nabla Y⟺f:|X|\to Y$$

$\square$

立方汇编

(...)

术语翻译

汇编 • 英文 assembly

划分 • 英文 partition

追踪 • 英文 track