海廷代數

在數學裏，海廷代數（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)