谓词范畴

谓词范畴是由集合配上一个子集 (作为 “满足谓词” 的表示) 作为对象的范畴, 它到集合范畴的遗忘函子存在一个简单的纤维范畴.

谓词范畴中借助集合论的各种操作 (如 Descartes 积, 无交并等) 即可定义各种 Boole 代数里的逻辑连词.

谓词范畴中还可以定义经典的谓词, 包括全称, 存在和相等, 前两者分别是依值积和依值和的特殊情况. 除此之外, 谓词范畴中还可以定义 “商”, 见二元谓词范畴. 如上四个定义和纤维范畴中的诱导函子都有伴随关系.

1定义

定义 1.1 (谓词范畴). 谓词范畴 Pred 由如下数据组成:

•	对象: 为形如 $(I,X)$ 的二元组, 其中 $I,X$ 都是集合, 且 $X\subseteq I$.
•	态射: 对于对象 $(I,X),(J,Y)$, 若函数 $f:I\to J$ 满足$$\forall i\in I,(i\in X⟹f(i)\in Y)$$那么 $f$ 为一个 $(I,X)$ 到 $(J,Y)$ 的态射. 该关系可以被视为如下交换图中的虚线态射的唯一存在性: $$XYIJf$$

定义 1.2. 从谓词范畴到集合范畴间存在遗忘函子 $U:\mathsf{Pred}\to \mathsf{Set}$, 将 $(I,X)$ 映射到 $I$、态射不变.

定理 1.3. 在 1.2 中定义的函子是纤维范畴. 其中, 对于 $I\in \mathsf{Set}$, 它的纤维记作 $P(I)$, 是对象形如 $(I,X)$ (其中 $X$ 任意)、态射被 $U$ 映射到恒同态射的 Pred 的子范畴.

证明. 对于映射 $f:I\to J$, 可以诱导出函子 $f^{\ast }$: $$\begin{array}{rl}P(J)& \to P(I)\\ (J,Y)& \mapsto (I,\{i\mid f(i)\in Y\})\end{array}$$验证函子律: 若 $Y\subseteq Y^{\prime }$, 考虑 $(I,X)=f^{\ast }(J,Y)$, $(I,X^{\prime })=f^{\ast }(J,Y^{\prime })$, 根据 Pred 的定义, 显然有 $X\subseteq X^{\prime }$.

$\square$

简洁起见, 当 $(I,X)$ 中的 $I$ 显然时, 我们直接用 $X$ 代替之. 比如讨论 $P(I)$ 中的对象时, 就只用子集 $X$ 来代指二元组 $(I,X)$.

诱导函子

定义 1.4 (弱化). 集合范畴中的积 $I\times J$ 及其投影 $\pi :I\times J\to I$ 诱导的态射 ${\pi }^{\ast }$ 叫做弱化函子: $$\begin{array}{rl}P(I)& \to P(I\times J)\\ X& \mapsto \{(i,j)\mid i\in X,j\in J\}\end{array}$$这个函子本质上就是把 $i\in X$ 变成一个二元组 $(i,j)\in X\times J$, 其中 $j$ 是任意的.

定义 1.5 (收缩). 集合范畴中的对角映射 $\Delta :I\to I\times I$ 诱导的态射 ${\Delta }^{\ast }$ 叫做收缩函子: $$\begin{array}{rl}P(I\times I)& \to P(I)\\ X& \mapsto \{i\in I\mid (i,i)\in X\}\end{array}$$这个函子接收 $I$ 的两个子集构成的积 $X$, 给出这两个子集的交集.

逻辑函子

定义 1.6 (全称与存在). 对于 $(I\times J,Y)\in \mathsf{Pred}$, 定义如下两函子: $$\begin{array}{rl}\forall ,\exists & :P(I\times J)\to P(I)\\ \forall Y& =\{i\in I\mid \forall j\in J,(i,j)\in Y\}\\ \exists Y& =\{i\in I\mid \exists j\in J,(i,j)\in Y\}\end{array}$$容易验证函子律.

定义 1.7 (相等). 对于 $(I,X)\in \mathsf{Pred}$, 定义函子 $E$: $$\begin{array}{rl}P(I)& \to P(I\times I)\\ X& \mapsto \{(i,i)\mid i\in X\}\end{array}$$容易验证函子律.

2性质

命题 2.1. 在 1.3 中的纤维 $P(I)$ 正好是 $I$ 的子集由包含关系作为态射构成的范畴.

伴随关系

定理 2.2. 对于 1.6,1.4 中提到的函子, 有如下三连伴随关系: $$\exists ⊣{\pi }^{\ast }⊣\forall$$

证明. 考虑 $Y\subseteq I\times J$, $X\subseteq I$.

对于 $\exists ⊣{\pi }^{\ast }$, 展开伴随的定义可知这是在说如下两命题等价: $$\exists Y\subseteq X⟺Y\subseteq {\pi }^{\ast }(X)$$对于 ${\pi }^{\ast }⊣\forall$, 对应的则是如下两命题等价: $${\pi }^{\ast }(X)\subseteq Y⟺X\subseteq \forall Y$$这两个等价关系都很容易验证.

$\square$

定理 2.3. 对于 1.7 和 1.5 中提到的函子, 有: $$E⊣{\Delta }^{\ast }$$

证明. 考虑 $X\subseteq I,Y\subseteq I\times I$, 展开伴随的定义可知这是在说如下两命题等价: $$E(X)\subseteq Y⟺X\subseteq {\Delta }^{\ast }(Y)$$容易验证以上命题.

$\square$

3相关概念

•

二元谓词范畴