海廷代数

在数学里，海廷代数（Heyting algebra）是一特殊的偏序集，经由广义化布尔代数而成，得名于阿兰德·海廷。海廷代数是作为直觉主义逻辑的模型而产生的，是一种排中律不总是成立的逻辑。完全海廷代数是无点拓扑学的核心。

形式定义

海廷代数H为一有界格，满足如下条件：对于在H中的所有a和b，存在一属于H的最大元素x，使得

${\displaystyle a\wedge x\leq b}$。

元素x被称为a对应于b的相对伪补元(relative pseudo-complement)，并标记为${\displaystyle a\rightarrow b}$。H中最大和最小元素分别写成1和0。

任一海廷代数，皆可定义出任一元素x的伪补元¬x为¬x = (x → 0)。依定义，a ∧ ¬a = 0,，且¬a是具有此一性质的最大元素。不过，因为a ∨ ¬a = 1,并不总是真的，所以¬只是一个伪补运算，而不是像在布尔代数中所见真正的补元。

完全海廷代数是指具有完全格的海廷代数。

海廷代数H的子代数是指H的子集H₁，包含0和1，并在∧、∨和→等运算下是封闭的。这表示在¬下也是封闭的。

其他等价的定义

格理论的定义

海廷代数的等价定义可由如下映射给出：对于H中的某些固定元素a，

${\displaystyle f_{a}:H\to H}$定义为${\displaystyle f_{a}(x)=a\wedge x}$，

有界格H是海廷代数，当且仅当所有的映射f_a都是单调伽罗瓦连接的下伴随(lower adjoint)。在这种情况下，其相对应的上伴随${\displaystyle g_{a}}$是由${\displaystyle g_{a}(x)=a\rightarrow x}$给出的，其中的${\displaystyle \rightarrow }$定义同上。

性质

海廷代数总是符合分配律。就是说，给定格A和二元运算${\displaystyle \rightarrow }$它们形成一个海廷代数，当且仅当如下成立：

1. ${\displaystyle a\rightarrow a=1}$
2. ${\displaystyle a\wedge (a\rightarrow b)=a\wedge b}$
3. ${\displaystyle b\wedge (a\rightarrow b)=b}$
4. ${\displaystyle a\rightarrow (b\wedge c)=(a\rightarrow b)\wedge (a\rightarrow c)}$ (分配律)

这有时被陈述为公理，但实际上可以从相对伪补元的存在性得到。道理是作为伽罗瓦连接的下伴随，${\displaystyle \wedge }$保持所有现存的上确界。所以分配律就是${\displaystyle \wedge }$对二元最小上界的保持。

进一步的，通过类似的论证，下列无限分配律在任何完全海廷代数中都成立：

${\displaystyle x\wedge \bigvee Y=\bigvee \{x\wedge y:y\in Y\}}$

对于任何H中的元素x和任何H的子集Y。

不是所有海廷代数都满足两个德·摩根定律。但是，对于所有海廷代数H下列陈述都是等价的：

1. H满足两个德·摩根定律。
2. ${\displaystyle \lnot (x\wedge y)=\lnot x\vee \lnot y}$，对于所有H中的x y。
3. ${\displaystyle \lnot x\vee \lnot \lnot x=1}$，对于所有H中的x。
4. ${\displaystyle \lnot \lnot (x\vee y)=\lnot \lnot x\vee \lnot \lnot y}$，对于所有H中的x y。

H的一个元素x的伪补元是集合${\displaystyle \{y:y\wedge x=0\}}$的上确界，并且属于这个集合(就是说，${\displaystyle x\wedge \lnot x=0}$成立)。

海廷代数H的一个元素x叫做正规的，如果如下等价条件之一成立：

1. ${\displaystyle x=\lnot \lnot x}$。
2. ${\displaystyle x=\lnot y}$，对于H的某个元素y。

海廷代数H是布尔代数，如果下列等价条件之一成立的：

1. 所有H中的x都是正规的。
2. ${\displaystyle x\vee \lnot x=1}$，对于所有H中的x。在这种情况下，元素${\displaystyle a\rightarrow b}$等价于${\displaystyle \lnot a\vee b}$。

在任何海廷代数中，最小0和最大元素1都是正规的。

任何海廷代数的正规元素都构成一个布尔代数。除非海廷代数的所有元素都是正规的，这个布尔代数都不会是这个海廷代数的子格，因为并运算将是不同的。

例子

• 所有是有界格的全序集合也是海廷代数，在这里对于不是0的所有a有${\displaystyle \lnot 0=1}$和${\displaystyle \lnot a=0}$。
• 不是布尔代数的最简单的海廷代数是线性有序集合{0, ½, 1}带有如下运算：

${\displaystyle a\land b}$ b a 0 ½ 1 0 0 0 0 ½ 0 ½ ½ 1 0 ½ 1

${\displaystyle a\lor b}$ b a 0 ½ 1 0 0 ½ 1 ½ ½ ½ 1 1 1 1 1

${\displaystyle a\rightarrow b}$ b a 0 ½ 1 0 1 1 1 ½ 0 1 1 1 0 ½ 1

注意½ ${\displaystyle \lor \neg }$ ½ = ½ ${\displaystyle \lor }$ (½ ${\displaystyle \rightarrow }$0) = ½ ${\displaystyle \lor }$0 = ½不满足排中律。

• 所有的拓扑结构都以它的开集格的形式提供完全海廷代数。在这种情况下，元素${\displaystyle A\Rightarrow B}$是${\displaystyle A_{c}}$和B的并的内部，这里的${\displaystyle A_{c}}$指示开集A的补。不是所有完全海廷代数都有这种形式。这些问题在无点拓扑学中研究，这里完全海廷代数也叫做frame或locale。
• 命题直觉主义逻辑的林登鲍姆-塔斯基代数是海廷代数。它被定义为所有命题逻辑公式的集合，并通过逻辑蕴涵来排序：对于任何两个公式F和G我们有${\displaystyle F\leq G}$，当且仅当${\displaystyle F\models G}$。在这个阶段${\displaystyle \leq }$只是诱发海廷代数所需要的偏序的预序。
• 若两图有图同态${\displaystyle G\to H}$，则称${\displaystyle G\leq H}$，于是${\displaystyle \leq }$是其等价类之间的偏序（${\displaystyle G\leq H}$且${\displaystyle H\leq G}$则属同一等价类${\displaystyle [G]=[H]}$），此为海廷代数。其交${\displaystyle [G]\land [H]}$由图张量积（英语：tensor product of graphs）${\displaystyle [G\times H]}$给出。蕴涵${\displaystyle [G]\Rightarrow [H]}$则是指数图（英语：Hedetniemi's conjecture）${\displaystyle [H^{G}]}$^{[注 1]}。^[1]（见图同态 § 同态的结构）

应用于直觉主义逻辑的海廷代数

阿兰德·海廷(1898年－1980年)自己感兴趣于以这种类型的结构来澄清直觉主义逻辑的基础地位。皮尔士定律的案例说明了海廷代数的语义角色，并给出皮尔士定律不能从直觉主义逻辑的基本定律中推导出来的最简单的已知证明。

如果用海廷代数的术语解释直觉主义命题逻辑的公理，则对于任何值到公式变量的指派下的任何海廷代数，它们将求值得到最大元素1。例如，通过伪补元的定义，${\displaystyle (P\land Q)\rightarrow P}$是最大元素x使得${\displaystyle P\land Q\land x\leq P}$。这个不等式对任何x都满足，所以最大的这种x是1。

进一步的，肯定前件规则允许从公式P和P → Q导出公式Q。在任何海廷代数中，如果P有值1，并且P → Q有值1，因为它意味着${\displaystyle P\land 1\leq Q}$，所以${\displaystyle 1\land 1\leq Q}$；因此Q只能有值1。

这意味着如果一个公式可以从直觉主义逻辑中演绎出来，即从它的公理通过肯定前件推导出来，则在任何值到公式变量的指派下的任何海廷代数中，它总是有值1。但是你可以一个海廷代数在其中皮尔士定律的值不总是1。考虑上面给出的三元素代数{0,½,1}。如果我们指派½到P并指派0到Q，则皮尔士定律 ((P → Q) → P) → P的值是½。这得出了皮尔士定律是不能直觉主义逻辑推导的。这在类型论中的蕴涵详情请参见柯里-霍华德同构。

反过来也是可证明的：如果一个公式总是有值1，则它是可以从直觉主义逻辑的公理系统演绎出来的，所以“直觉主义有效”的公式严格的是永远有值1的公式。这类似于“经典有效”公式是在两元素布尔代数中在对公式变量的任何可能真和假指派下永远有值1的公式，它们在通常的真值表意义上是重言式。从逻辑的立场，海廷代数是普通真值系统的推广，它的最大元素1可比拟于真。平常的二值逻辑系统是海廷代数的特殊情况，和最小的非平凡的系统，在其中仅有的代数元素是1(真)和0 (假)。

参见

• 直觉主义逻辑
• 布尔代数
• MV-代数
• 格
• 布尔代数主题列表

注

1. 指数图（exponential graph）${\displaystyle H^{G}}$的顶点是函数${\displaystyle f:V(G)\to V(H)}$，两顶点${\displaystyle f,g:V(G)\to V(H)}$连边当且仅当对${\displaystyle G}$中任意两个相邻顶点${\displaystyle v,v'}$，有${\displaystyle f(v)}$与${\displaystyle g(v')}$在${\displaystyle H}$中相邻。

引用

1. Dwight, D.; Sauer, N., Lattices arising in categorial investigations of Hedetniemi's conjecture [以范畴论研究赫德米猜想所得的格], Discrete Mathematics（英语：Discrete Mathematics (journal)）, 1996, 152 (1–3): 125–139, doi:10.1016/0012-365X(94)00298-W  （英语）

• Rutherford, Daniel Edwin. Introduction to Lattice Theory. Oliver and Boyd. 1965.
• F. Borceux, Handbook of Categorical Algebra 3, In Encyclopedia of Mathematics and its Applications, Vol. 53, Cambridge University Press, 1994.
• G. Gierz, K.H. Hoffmann, K. Keimel, J. D. Lawson, M. Mislove and D. S. Scott, Continuous Lattices and Domains, In Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press, 2003.

外部链接

• Heyting algebra (GFDLed)