Heyting代数

维基百科，自由的百科全书

在数学中，Heyting 代数是构成对布尔代数的推广的特殊的偏序集。Heyting 代数为直觉逻辑而提出，它是在其中排中律一般不成立的逻辑。完全Heyting代数是无点拓扑学研究的中心对象。

[编辑] 形式定义

Heyting 代数 H 是满足如下条件的有界格，对于在 H 中的所有 a 和 b 有最大的 H 元素 x 使得

$a \wedge x \le b$ 。

这个元素 x 是 a 关于 b 的相对伪补元(pseudo-complement)，并指示为 $a \Rightarrow b$ (或 $a \rightarrow b$ )。

可以通过如下映射给出等价定义：对于 H 中某个固定的 a，

$f_a: H \to H$ 定义为 $f_a(x)=a\wedge x$ 。

有界格 H 是 Heyting 代数，当且仅当所有映射 $f a$ 都是单调的伽罗瓦连接的下共轭(adjoint)。在这种情况下各自的上共轭 $g a$ 通过 $g_a(x)= (a \Rightarrow x)$ 给出，这里的 $\Rightarrow$ 定义同上。

完全Heyting代数是是完全格的 Heyting 代数。

在任何 Heyting 代数中，你可以通过设立 $\lnot x = (x \Rightarrow 0)$ 定义某个元素 x 的伪补元 $\lnot x$ ，这里的 0 是 Heyting 代数的最小元素。

Heyting 代数的一个元素 x 叫做正规的，如果 $x=\lnot\lnot x$ 。元素 x 是正规的，当且仅当对于 Heyting 代数的某个元素 y 有 $x=\lnot y$ 。

[编辑] 性质

Heyting 代数总是符合分配律。这有时被陈述为公理，但实际上可以从相对伪补元的存在性得到。道理是作为伽罗瓦连接的下共轭， $\wedge$ 保持所有现存的上确界。所以分配律就是 $\wedge$ 对二元最小上界的保持。

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

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

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

不是所有 Heyting 代数都满足两个De Morgan 定律。但是，对于所有 Heyting 代数 H 下列陈述都是等价的:

H 满足两个 De Morgan 定律。
对于 H 中的所有 x y 有 $\lnot(x \wedge y)=\lnot x \vee \lnot y$ 。
对于 H 中的所有 x 有 $\lnot x \vee \lnot\lnot x = 1$ 。
对于 H 中的所有 x y 有 $\lnot\lnot (x \vee y) = \lnot\lnot x \vee \lnot\lnot y$ 。

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

布尔代数准确的是如下成立的 Heyting 代数：对于所有 x 有 $x = \lnot\lnot x$ ，或等价的说，布尔代数准确的是如下成立的 Heyting 代数：对于所有 x 有 $x\vee\lnot x=1$ 。在这种情况下，元素 $a \Rightarrow b$ 等价于 $\lnot a \vee b$ 。

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

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

[编辑] 例子

所有是有界格的全序集合也是 Heyting 代数，在这里对于不是 0 的所有 a 有 $\lnot 0 = 1$ 和 $\lnot a = 0$ 。

所有的拓扑都以它的开集格的形式提供完全 Heyting 代数。在这种情况下，元素 $A \Rightarrow B$ 是 $A c$ 和 B 的并的内部，这里的 $A c$ 指示开集 A 的补。不是所有完全 Heyting 代数都有这种形式。这些问题在无点拓扑学中研究，这里完全 Heyting 代数也叫做 frame 或 locale。

命题直觉逻辑的Lindenbaum 代数是 Heyting 代数。它被定义为所有命题逻辑公式的集合，并通过逻辑蕴涵来排序: 对于任何两个公式 F 和 G 我们有 $F \le G$ ，当且仅当 $F \models G$ 。在这个阶段 $\le$ 只是诱发 Heyting 代数所需要的偏序的预序。

[编辑] 应用于直觉逻辑的 Heyting 代数

Arend Heyting (1898年-1980年)自己感兴趣于以这种类型的结构来澄清直觉逻辑的基础地位。Peirce 定律的案例说明了 Heyting 代数的语义角色。没有简单的证明能证明 Peirce 定律不能从直觉逻辑的基本定律中推导出来。

Heyting 代数，从逻辑的立场来说，本质上是普通真值系统的一般化。同其他性质一起，最大元素，在逻辑中叫做 $\top$ ，是'真'的同义词，普通二值逻辑系统是 Heyting 代数的最简单的例子，在这个代数中两个元素是 $\top$ (真)和 $\bot$ (假)。用抽象的术语说，两元素布尔代数也是 Heyting 代数。

经典有效的公式是在这种布尔代数中在对公式的变量的任意可能的真假指派下有 $\top$ 值的公式 — 就是说，它们是在普通真值表意义上的重言式。直觉有效的公式是在任何 Heyting 代数中在对公式变量的值的任何指派下有 $\top$ 值的公式。

你可以构造在其中 Peirce 定律不总是 $\top$ 的 Heyting 代数。考虑 Sierpinski 空间的开集(不是布尔代数的 Heyting 代数的最简单的例子)，并观察如果我们释义 P 为 {1}、Q 为 $\varnothing$ ，则 Peirce 定律 ((P → Q) → P) → P 的释义是 $\{1\}\ne \{0,1\} = \top$ 。从我们刚才所说的，这不能是直觉推导出来的。详情参见Curry-Howard同构和类型论。

[编辑] 参见

[编辑] 引用

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.

来自“http://zh.wikipedia.org../../../h/e/y/Heyting%E4%BB%A3%E6%95%B0.html”

页面分类: 序理论