海廷代数

在数学裡，海廷代数（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)