Heyting代数

在數學裡，**海廷代數**（Heyting algebra）是一特殊的偏序集，經由廣義化布爾代數而成，得名於阿蘭德・海廷。海廷代數是作為直覺主義邏輯的模型而產生的，是一種排中律不總是成立的邏輯。完全海廷代數是無點拓撲學的核心。

## 形式定義

海廷代數 _H_ 為一有界格，滿足如下條件：對於在 _H_ 中的所有 _a_ 和 _b_，存在一屬於 _H_ 的最大元素 _x_，使得

　
: $a\wedge x\leq b$ 。

元素 _x_ 被稱為 _a_ 對應於 _b_ 的**相對偽補元**(relative pseudo-complement)，並標記為 $a\rightarrow b$ 。_H_ 中最大和最小元素分別寫成 1 和 0。

任一海廷代數，皆可定義出任一元素 _x_ 的**偽補元** ¬_x_ 為 ¬_x_ = (_x_ → 0)。依定義，_a_ ∧ ¬_a_ = 0,，且 ¬_a_ 是具有此一性質的最大元素。不過，因為 _a_ ∨ ¬_a_ = 1, 並不總是真的，所以 ¬ 只是一個偽補運算，而不是像在布爾代數中所見真正的補元。

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

海廷代數 _H_ 的**子代數**是指 _H_ 的子集 _H_1，包含 0 和 1，並在∧、∨和→等運算下是封閉的。這表示在 ¬ 下也是封閉的。

## 其他等價的定義

### 格理論的定義

海廷代數的等價定義可由如下對映給出：對於 _H_ 中的某些固定元素 _a_，

　
: $f_{a}:H\to H$ 定義為 $f_{a}(x)=a\wedge x$ ，

有界格 _H_ 是海廷代數，若且唯若所有的對映 _fa_ 都是單調伽羅瓦連接的下伴隨 (lower adjoint)。在這種情況下，其相對應的上伴隨 $g_{a}$ 是由 $g_{a}(x)=a\rightarrow x$ 給出的，其中的 $\rightarrow $ 定義同上。

## 性質

海廷代數總是符合分配律。就是說，給定格 _A_ 和二元運算 $\rightarrow $ 它們形成一個海廷代數，若且唯若如下成立：

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

這有時被陳述為公理，但實際上可以從相對偽補元的存在性得到。道理是作為伽羅瓦連接的下伴隨， $\wedge $ 保持所有現存的上確界。所以分配律就是 $\wedge $ 對二元最小上界的保持。

進一步的，通過類似的論證，下列無限分配律在任何完全海廷代數中都成立：

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

對於任何 _H_ 中的元素 _x_ 和任何 _H_ 的子集 _Y_。

不是所有海廷代數都滿足兩個德・摩根定律。但是，對於所有海廷代數 _H_ 下列陳述都是等價的：

1. _H_ 滿足兩個德・摩根定律。
2. $\lnot (x\wedge y)=\lnot x\vee \lnot y$ ，對於所有 _H_ 中的 _x_ _y_。
3. $\lnot x\vee \lnot \lnot x=1$ ，對於所有 _H_ 中的 _x_。
4. $\lnot \lnot (x\vee y)=\lnot \lnot x\vee \lnot \lnot y$ ，對於所有 _H_ 中的 _x_ _y_。

_H_ 的一個元素 _x_ 的偽補元是集合 $\{y:y\wedge x=0\}$ 的上確界，並且屬於這個集合 (就是說， $x\wedge \lnot x=0$ 成立)。

海廷代數 _H_ 的一個元素 _x_ 叫做**正規的**，如果如下等價條件之一成立：

 1. $x=\lnot \lnot x$ 。
2. $x=\lnot y$ ，對於 _H_ 的某個元素 _y_。

海廷代數 _H_ 是布林代數，如果下列等價條件之一成立的：

1. 所有 H 中的 _x_ 都是正規的。
2. $x\vee \lnot x=1$ ，對於所有 H 中的 _x_。在這種情況下，元素 $a\rightarrow b$ 等價於 $\lnot a\vee b$ 。

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

任何海廷代數的正規元素都構成一個布林代數。除非海廷代數的所有元素都是正規的，這個布林代數都不會是這個海廷代數的子格，因為並運算將是不同的。

## 例子

* 所有是有界格的全序集合也是海廷代數，在這裡對於不是 0 的所有 _a_ 有 $\lnot 0=1$ 和 $\lnot a=0$ 。
* 不是布林代數的最簡單的海廷代數是線性有序集合 {0, ½, 1} 帶有如下運算：

　
: 注意 ½ $\lor \neg $ ½ = ½ $\lor $ (½ $\rightarrow $ 0) = ½ $\lor $ 0 = ½ 不滿足排中律。

* 所有的拓撲結構都以它的開集格的形式提供完全海廷代數。在這種情況下，元素 $A\Rightarrow B$ 是 $A_{c}$ 和 _B_ 的並的內部，這裡的 $A_{c}$ 指示開集 _A_ 的補。不是所有完全海廷代數都有這種形式。這些問題在無點拓撲學中研究，這裡完全海廷代數也叫做 **frame** 或 **locale**。
* 命題直覺主義邏輯的林登鮑姆 - 塔斯基代數是海廷代數。它被定義為所有命題邏輯公式的集合，並通過邏輯蘊涵來排序：對於任何兩個公式 _F_ 和 _G_ 我們有 $F\leq G$ ，若且唯若 $F\models G$ 。在這個階段 $\leq $ 只是誘發海廷代數所需要的偏序的預序。
* 若兩圖有圖同態 $G\to H$ ，則稱 $G\leq H$ ，於是 $\leq $ 是其等價類之間的偏序（ $G\leq H$ 且 $H\leq G$ 則屬同一等價類 $[G]=[H]$ ），此為海廷代數。其交 $[G]\land [H]$ 由圖張量積 $[G\times H]$ 給出。蘊涵 $[G]\Rightarrow [H]$ 則是指數圖 $[H^{G}]$ 。（見圖同態 § 同態的結構）

## 應用於直覺主義邏輯的海廷代數

阿蘭德・海廷 (1898 年－1980 年) 自己感興趣於以這種類型的結構來澄清直覺主義邏輯的基礎地位。皮爾士定律的案例說明了海廷代數的語意角色，並給出皮爾士定律不能從直覺主義邏輯的基本定律中推導出來的最簡單的已知證明。

如果用海廷代數的術語解釋直覺主義命題邏輯的公理，則對於任何值到公式變數的指派下的任何海廷代數，它們將求值得到最大元素 1。例如，通過偽補元的定義， $(P\land Q)\rightarrow P$ 是最大元素 _x_ 使得 $P\land Q\land x\leq P$ 。這個不等式對任何 _x_ 都滿足，所以最大的這種 _x_ 是 1。

進一步的，肯定前件規則允許從公式 P 和 P → Q 匯出公式 Q。在任何海廷代數中，如果 P 有值 1，並且 P → Q 有值 1，因為它意味著 $P\land 1\leq Q$ ，所以 $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 - 代數
* 格
* 布林代數主題列表

## 註

## 參照

## 外部連結