海廷代数

维基百科,自由的百科全书
跳转至: 导航搜索

数学裡,海廷代数是一特殊的偏序集,經由廣義化布爾代數而成,得名於阿蘭德·海廷。海廷代数是作为直觉主义逻辑的模型而產生的,是一種排中律不總是成立的逻辑。完全海廷代数无点拓扑学的核心。

形式定义[编辑]

海廷代数 H 為一有界格,滿足如下條件:对于在 H 中的所有 ab ,存在一屬於 H 的最大元素 x ,使得

 a \wedge x \le b

元素 x 被稱為 a 對應于 b相对伪补元(relative pseudo-complement),并標記为 a \rightarrow bH 中最大和最小元素分別寫成 1 和 0 。

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

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

海廷代數 H子代數是指 H 的子集 H1 ,包含 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} 带有如下运算:
a \land b
b

a
0 ½ 1
0 0 0 0
½ 0 ½ ½
1 0 ½ 1
 
a \lor b
b

a
0 ½ 1
0 0 ½ 1
½ ½ ½ 1
1 1 1 1
 
a \rightarrow b
b

a
0 ½ 1
0 1 1 1
½ 0 1 1
1 0 ½ 1
注意 ½ \lor\neg ½ = ½ \lor\rightarrow0) = ½ \lor0 = ½ 不满足排中律。
  • 所有的拓扑都以它的开集格的形式提供完全海廷代数。在这种情况下,元素 A \Rightarrow BA_cB 的并的内部,这里的 A_c 指示开集 A 的补。不是所有完全海廷代数都有这种形式。这些问题在无点拓扑学中研究,这里完全海廷代数也叫做 framelocale
  • 命题直觉主义逻辑林登鲍姆-塔斯基代数是海廷代数。它被定义为所有命题逻辑公式的集合,并通过逻辑蕴涵来排序: 对于任何两个公式 FG 我们有 F \le G ,当且仅当 F \models G。在这个阶段 \le 只是诱发海廷代数所需要的偏序的预序

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

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

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

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

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

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

参见[编辑]

引用[编辑]

  • 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.

外部連結[编辑]