查看“︁海廷代数”︁的源代码

{{NoteTA
|G1 = IT
|G2 = Math
}}
在[[数学]]裡，'''海廷代数'''（Heyting algebra）是一特殊的[[偏序集]]，經由廣義化[[布爾代數]]而成，得名於[[阿蘭德·海廷]]。海廷代数是作为[[直觉主义逻辑]]的模型而產生的，是一種[[排中律]]不總是成立的逻辑。[[完全海廷代数]]是[[无点拓扑学]]的核心。

== 形式定义 ==

海廷代数''H''為一[[有界格]]，滿足如下條件：对于在''H''中的所有''a''和''b''，存在一屬於''H''的最大元素''x''，使得

:<math> a \wedge x \le b</math>。

元素''x''被稱為''a''對應于''b''的'''相对伪补元'''(relative pseudo-complement)，并標記为<math>a \rightarrow b</math>。''H''中最大和最小元素分別寫成1和0。

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

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

海廷代數''H''的'''子代數'''是指''H''的子集''H''<sub>1</sub>，包含0和1，並在∧、∨和→等運算下是封閉的。這表示在¬下也是封閉的。

== 其他等價的定義 ==

=== 格理論的定義 ===

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

:<math>f_a: H \to H</math>定义为<math>f_a(x)=a\wedge x</math>，

有界格''H''是海廷代数，[[当且仅当]]所有的映射''f<sub>a''</sub>都是单调[[伽罗瓦连接]]的下伴随(lower adjoint)。在这种情况下，其相對應的上伴随<math>g_a</math>是由<math>g_a(x)= a \rightarrow x</math>给出的，其中的<math>\rightarrow</math>定义同上。

== 性质 ==

海廷代数总是符合[[分配律]]。就是说，给定格''A''和二元运算<math>\rightarrow</math>它们形成一个海廷代数，当且仅当如下成立：
#<math>a\rightarrow a = 1</math>
#<math>a\wedge(a\rightarrow b)=a\wedge b</math>
#<math>b\wedge(a\rightarrow b)= b</math>
#<math>a\rightarrow (b\wedge c)= (a\rightarrow b)\wedge (a\rightarrow c)</math>  (分配律)

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

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

<math>x\wedge\bigvee Y = \bigvee \{x\wedge y : y \in Y\}</math>

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

不是所有海廷代数都满足两个[[德·摩根定律]]。但是，对于所有海廷代数''H''下列陈述都是等价的：
# ''H''满足两个德·摩根定律。
# <math>\lnot(x \wedge y)=\lnot x \vee \lnot y</math>，对于所有''H''中的''x'' ''y''。
# <math>\lnot x \vee \lnot\lnot x = 1</math>，对于所有''H''中的''x''。
# <math>\lnot\lnot (x \vee y) = \lnot\lnot x \vee \lnot\lnot y</math>，对于所有''H''中的''x'' ''y''。

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

海廷代数''H''的一个元素''x''叫做'''正规的'''，如果如下等价条件之一成立：
# <math>x=\lnot\lnot x</math>。
# <math>x=\lnot y</math>，对于''H''的某个元素''y''。

海廷代数''H''是布尔代数，如果下列等价条件之一成立的：
# 所有H中的''x''都是正规的。
# <math>x\vee\lnot x=1</math>，对于所有H中的''x''。在这种情况下，元素<math>a \rightarrow b</math>等价于<math>\lnot a \vee b</math>。

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

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

== 例子 ==

* 所有是有界格的[[全序关系|全序集合]]也是海廷代数，在这里对于不是0的所有''a''有<math>\lnot 0 = 1</math>和<math>\lnot a = 0</math>。
* 不是布尔代数的最简单的海廷代数是线性有序集合{0, ½, 1}带有如下运算：
{|
|
<div>
{| class="prettytable"
| colspan="4" align="center" | <math>a \land b</math>
|-
| width="40" | <div style="float:right">b</div><br/><div style="align:left">a</div>
| bgcolor="white" width="30" align="center" | 0
| bgcolor="white" width="30" align="center" | ½
| bgcolor="white" width="30" align="center" | 1
|-
| bgcolor="white" align="center" | 0
| align="center" | 0
| align="center" | 0
| align="center" | 0
|-
| bgcolor="white" align="center" | ½
| align="center" | 0
| align="center" | ½
| align="center" | ½
|-
| bgcolor="white" align="center" | 1
| align="center" | 0
| align="center" | ½
| align="center" | 1
|}
</div>
| width="30" |  
|
<div>
{| class="prettytable"
|  colspan="4" align="center" | <math>a \lor b</math>
|-
| width="40" | <div style="float:right">b</div><br/><div style="align:left">a</div>
| bgcolor="white" width="30" align="center" | 0
| bgcolor="white" width="30" align="center" | ½
| bgcolor="white" width="30" align="center" | 1
|-
| bgcolor="white" align="center" | 0
| align="center" | 0
| align="center" | ½
| align="center" | 1
|-
| bgcolor="white" align="center" | ½
| align="center" | ½
| align="center" | ½
| align="center" | 1
|-
| bgcolor="white" align="center" | 1
| align="center" | 1
| align="center" | 1
| align="center" | 1
|}
</div>
| width="30" |  
|
<div>
{| class="prettytable"
|  colspan="4" align="center" | <math>a \rightarrow b</math>
|-
| width="40" | <div style="float:right">b</div><br/><div style="align:left">a</div>
| bgcolor="white" width="30" align="center" | 0
| bgcolor="white" width="30" align="center" | ½
| bgcolor="white" width="30" align="center" | 1
|-
| bgcolor="white" align="center" | 0
| align="center" | 1
| align="center" | 1
| align="center" | 1
|-
| bgcolor="white" align="center" | ½
| align="center" | 0
| align="center" | 1
| align="center" | 1
|-
| bgcolor="white" align="center" | 1
| align="center" | 0
| align="center" | ½
| align="center" | 1
|}
</div>
|}
: 注意½ <math>\lor\neg</math> ½ = ½ <math>\lor</math> (½ <math>\rightarrow</math>0) = ½ <math>\lor</math>0 = ½不满足排中律。

* 所有的[[拓撲結構]]都以它的[[开集]]格的形式提供完全海廷代数。在这种情况下，元素<math>A \Rightarrow B</math>是<math>A_c</math>和''B''的并的[[内部]]，这里的<math>A_c</math>指示开集''A''的补。不是所有完全海廷代数都有这种形式。这些问题在[[无点拓扑学]]中研究，这里完全海廷代数也叫做'''frame'''或'''locale'''。
* 命题[[直觉主义逻辑]]的[[林登鲍姆-塔斯基代数]]是海廷代数。它被定义为所有命题逻辑公式的集合，并通过逻辑蕴涵来排序：对于任何两个公式''F''和''G''我们有<math>F \le G</math>，当且仅当<math>F \models G</math>。在这个阶段<math>\le</math>只是诱发海廷代数所需要的偏序的[[预序]]。
* 若兩[[圖 (數學)|圖]]有[[圖同態]]<math>G\to H</math>，則稱<math>G \le H</math>，於是<math>\le</math>是其等價類之間的偏序（<math>G \le H</math>且<math>H \le G</math>則屬同一等價類<math>[G] = [H]</math>），此為海廷代數。其交<math>[G] \land [H]</math>由{{le|圖張量積|tensor product of graphs}}<math>[G \times H]</math>給出。蘊涵<math>[G] \Rightarrow [H]</math>則是{{link-en|赫德米猜想|Hedetniemi's conjecture|指數圖}}<math>[H^G]</math>{{註|指數圖（{{lang|en|exponential graph}}）<math>H^G</math>的頂點是函數<math>f:V(G) \to V(H)</math>，兩頂點<math>f, g: V(G) \to V(H)</math>連邊當且僅當對<math>G</math>中任意兩個相鄰頂點<math>v, v'</math>，有<math>f(v)</math>與<math>g(v')</math>在<math>H</math>中相鄰。}}。<ref name="lattices">{{citation|first1=D.|last1=Dwight|first2=N.|last2=Sauer|title=Lattices arising in categorial investigations of Hedetniemi's conjecture|trans-title = 以範疇論研究赫德米猜想所得的格 |journal={{link-en|離散數學 (期刊)|Discrete Mathematics (journal)|Discrete Mathematics}}|volume=152|issue=1–3|year=1996|pages=125–139|doi=10.1016/0012-365X(94)00298-W|doi-access=free |language = en}}</ref>（見{{section link | 圖同態#同態的結構}}）

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

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

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

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

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

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

==参见==
* [[直觉主义逻辑]]
* [[布尔代数]]
* [[MV-代数]]
* [[格 (数学)|格]]
* [[布尔代数主题列表]]

== 註 ==
{{備註表}}

==引用==
{{reflist}}
<div class="references-small" style="-moz-column-count:2; column-count:2;">
* {{cite book | first = Daniel Edwin | last = Rutherford | year = 1965 | title = Introduction to Lattice Theory | publisher = Oliver and Boyd }}
* 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.
</div>

==外部連結==
{{refbegin}}
*[[PlanetMath:8734|Heyting algebra]] ([[GNU自由文档许可证|GFDL]]ed)
{{refend}}

[[Category:格理论]]
[[Category:代数逻辑]]