完全偏序：修订间差异

删除的内容添加的内容

行内

2016年5月20日 (五) 07:09的最新版本

在数学中，有向完全偏序和完全偏序是两种特殊的偏序集合，分别简写为 dcpo 和 cpo。它们特征化自特定的完备性性质。dcpos 和 cpos 是序理论的概念，主要应用于理论计算机科学和指称语义。

定义

一个偏序集合是有向完全偏序(dcpo)，如果它的每个有向子集都有上确界。完全偏序(cpo)是带有最小元素的 dcpo。在文献中，dcpos 有时分类为 sup-完全偏序集合，或在不会造成歧义的情况下简称为“cpo”。带有最小元素的 dcpo 有时叫做尖角(pointed) dcpo 或尖角 cpo。

要求有向上确界的存在的动机来自把有向集合看作一般化的逼近序列，把上确界看作各自(逼近)计算的极限。关于在指称语义的上下文中这种直觉的详情请参见域理论。

有向完全偏序集合的对偶概念叫做过滤完全偏序。但是这个概念在实践中不常用，因为通常可以明确地在这个对偶的次序上工作。

性质

有序集合 P 是 cpo，当且仅当所有全序子集都有在 P 中的上确界。可作为替代，有序集合 P 是 cpo，当且仅当所有 P 的序保持自映射都有最小不动点。所有集合 S 都可以变成 cpo，通过增加一个最小元素 ⊥ 并介入一个平坦次序，带有 ⊥ ≤ s 对于所有 s ∈ S，并没有其他次序关系。

连续函数和不动点

在两个 dcpos P 和 Q 之间的函数 f 被称为连续的，如果它把有向集合映射到有向集合，并保持它们的上确界:

$f(D)\subseteq Q$ 是有向的，对有所有有向的 $D\subseteq P$ 。
$f(\sup D)=\sup f(D)$ 对于所有有向的 $D\subseteq P$ 。

在两个 cpos (P, ⊥_P) 和 (Q, ⊥_Q) 之间的函数 f 被称为是连续的，如果它进一步保持最小元素:

$f(\bot _{P})=\bot _{Q}$

这种连续性的概念等价于Scott拓扑引发的概念。

在两个 dcpos P 和 Q 之间的所有连续函数的集合被指示为 [P → Q]。配备了逐点(pointwise)次序，这是 dcpo，并是 cpo 只要 Q 是 cpo。

在 cpos 之间的所有连续函数是序保持的但反之不然。所有 cpo (P, ⊥) 的序保持的自映射 f 有最小不动点。如果 f 是连续的，则这个不动点等于 ⊥ 的迭代 (⊥, f(⊥), f(f(⊥)), … fⁿ(⊥), …) 的上确界。

有关文章

有向完全性以各种方式关联于其他完备性概念。这在完全性 (序理论)中讨论。有向完全性自身在其他序理论研究中是经常出现的非常基本的性质。例如，涉及有向完全性的定理可以在连续偏序集合、代数偏序集合和Scott拓扑文章中讨论。在 dcpos 之间的函数经常要求是单调的甚至是Scott连续性的。

例子

对于任何偏序集合，所有非空滤子的集合，用子集包含排序，是 dcpo，甚至是 cpo 如果这个偏序集合有最大元素。与空滤子在一起它也保证是 cpo。如果次序是交半格(甚至是格)，则这个构造(包括空滤子)实际上生成一个完全格。

考虑在某个集合 S 上所有偏函数的集合，偏函数是只在(它的域) S 的某些子集上有定义的函数。对于两个这种函数 f 和 g，定义 f ≤ g 当且仅当，f 的域是 g 的域的子集，并且 f 和 g 的值在对两个函数都有定义的所有输出上一致。在这种情况下，我们称 g 扩展了 f。这个次序是 cpo，这里的最小元素是无处定义函数(有空域)。事实上，≤ 也是有界完全性的。这个例子还展示了为什么不总是自然的有一个最大元素。

sober空间的特殊化次序是 dcpo。

所有有限偏序集合都是有向完全的，所有带有最小元素的有限偏序集合都是 cpo。

所有完全格都是有向完全的并因此为 dcpos 提供了众多例子。

引用

Davey, B.A., and Priestley, H. A. Introduction to Lattices and Order Second Edition. Cambridge University Press. 2002. ISBN 978-0-521-78451-1.

@@ 第1行： / 第1行： @@
+在[[数学]]中，'''有向完全偏序'''和'''完全偏序'''是两种特殊的[[偏序集合]]，分别简写为 '''dcpo''' 和 '''cpo。'''它们特征化自特定的[[完备性|完备性性质]]。dcpos 和 cpos 是[[序理论]]的概念，主要应用于[[理论计算机科学]]和[[指称语义]]。
-{{translation}}
-在[[数学]]中，'''有向完全偏序'''和'''完全偏序'''是特殊种类的[[偏序集合]]。分别简写为 '''dcpo''' 和 '''cpo'''，它们特征化自特定特定[[完备性|完备性性质]]。dcpos 和 cpos 在[[序理论]]中考虑并主要应用于[[理论计算机科学]]和[[指称语义]]。
 == 定义 ==
-一个偏序集合是'''有向完全偏序'''('''dcpo''')，如果它的每个[[有向集合|有向子集]]都有[[上确界]]。'''完全偏序'''('''cpo''')是带有[[最小元素]]的 dcpo。在文献中，dcpos 有时分类为 '''sup-完全偏序集合'''，或混淆为“cpo”。带有最小元素的 dcpo 有时叫做'''尖角'''(pointed) dcpo 或尖角 cpo。
+一个偏序集合是'''有向完全偏序'''('''dcpo''')，如果它的每个[[有向集合|有向子集]]都有[[上确界]]。'''完全偏序'''('''cpo''')是带有[[最小元素]]的 dcpo。在文献中，dcpos 有时分类为 '''sup-完全偏序集合'''，或在不会造成歧义的情况下简称为“cpo”。带有最小元素的 dcpo 有时叫做'''尖角'''(pointed) dcpo 或尖角 cpo。
-要求有向上确界的存在可能推动自把有向集合看作一般化的逼近序列把上确界看作各自(逼近)计算的极限。关于在指称语义的上下文中这种直觉的详情请参见[[域理论]]。
+要求有向上确界的存在的动机来自把有向集合看作一般化的逼近序列，把上确界看作各自(逼近)计算的极限。关于在指称语义的上下文中这种直觉的详情请参见[[域理论]]。
-有向完全偏序集合的[[格 (数学)|对偶]]概念叫做'''过滤完全偏序'''。但是这个概念在实践中不常用，因为你通常可以明确的在这个对偶的次序上工作。
+有向完全偏序集合的[[格 (数学)|对偶]]概念叫做'''过滤完全偏序'''。但是这个概念在实践中不常用，因为通常可以明确地在这个对偶的次序上工作。
-==性质和有关文章==
+== 性质 ==
+有序集合 ''P'' 是 cpo，当且仅当所有[[全序关系|全序子集]]都有在 ''P'' 中的上确界。可作为替代，有序集合 ''P'' 是 cpo，当且仅当所有 ''P'' 的[[单调函数|序保持]]自映射都有[[最小不动点]]。所有集合 ''S'' 都可以变成 cpo，通过增加一个最小元素 ⊥ 并介入一个平坦次序，带有 ⊥&nbsp;≤&nbsp;''s'' 对于所有 ''s''&nbsp;∈&nbsp;''S''，并没有其他次序关系。
-Directed completeness relates in various ways to other completeness notions. This is documented in the article on [[completeness (order theory)]]. Directed completeness alone is quite a basic property that occurs often in other order theoretic investigations. For instance, theorems involving directed completeness (and characterizations thereof) are to be found in the articles on [[continuous poset]]s, [[algebraic poset]]s, and the [[Scott topology]]. Functions between dcpos are often required to be [[monotonic function|monotone]] or even [[Scott continuous]].
+== 连续函数和不动点 ==
+在两个 dcpos ''P'' 和 ''Q'' 之间的函数 ''f'' 被称为'''连续的'''，如果它把有向集合映射到有向集合，并保持它们的上确界:
+* <math>f(D) \subseteq Q</math> 是有向的，对有所有有向的 <math>D \subseteq P</math>。
+* <math>f(\sup D) = \sup f(D)</math> 对于所有有向的 <math>D \subseteq P</math>。
+在两个 cpos (''P'', ⊥<sub>''P''</sub>) 和 (''Q'', ⊥<sub>''Q''</sub>) 之间的函数 ''f'' 被称为是'''连续的'''，如果它进一步保持最小元素:
+* <math>f(\bot_P) = \bot_Q</math>
+这种连续性的概念等价于[[Scott拓扑]]引发的概念。
+在两个 dcpos ''P'' 和 ''Q'' 之间的所有连续函数的集合被指示为 <nowiki>[</nowiki>''P''&nbsp;→&nbsp;''Q''<nowiki>]</nowiki>。配备了逐点(pointwise)次序，这是 dcpo，并是 cpo 只要 ''Q'' 是 cpo。
+在 cpos 之间的所有连续函数是序保持的但反之不然。所有 cpo (''P'', ⊥) 的序保持的自映射 ''f'' 有最小不动点。如果 ''f'' 是连续的，则这个不动点等于 ⊥ 的[[迭代函数|迭代]] (⊥, ''f''(⊥), ''f''(''f''(⊥)), … ''f''<sup>''n''</sup>(⊥), …) 的上确界。
+== 有关文章 ==
+有向完全性以各种方式关联于其他完备性概念。这在[[完全性 (序理论)]]中讨论。有向完全性自身在其他序理论研究中是经常出现的非常基本的性质。例如，涉及有向完全性的定理可以在[[连续偏序集合]]、[[代数偏序集合]]和[[Scott拓扑]]文章中讨论。在 dcpos 之间的函数经常要求是[[单调函数|单调的]]甚至是[[Scott连续性]]的。
 == 例子 ==
+* 对于任何偏序集合，所有[[非空集合|非空]][[滤子 (数学)|滤子]]的集合，用子集包含排序，是 dcpo，甚至是 cpo 如果这个偏序集合有最大元素。与空滤子在一起它也保证是 cpo。如果次序是[[半格|交半格]](甚至是[[格 (数学)|格]])，则这个构造(包括空滤子)实际上生成一个[[完全格]]。
-* For any poset, the set of all [[non-empty]] [[filter (mathematics)|filters]], ordered by subset inclusion, is a dcpo, even a cpo if the poset has a greatest element. Together with the empty filter it is also guaranteed to be a cpo. If the order is a [[semilattice|meet-semilattice]] (or even a [[lattice (order)|lattice]]), then this construction (including the empty filter) actually yields a [[complete lattice]].
+* 考虑在某个集合 ''S'' 上所有[[偏函数]]的集合，偏函数是只在(它的[[定义域|域]]) ''S'' 的某些子集上有定义的函数。对于两个这种函数 ''f'' 和 ''g''，定义 ''f'' ≤ ''g'' [[当且仅当]]，''f'' 的域是 ''g'' 的域的子集，并且 ''f'' 和 ''g'' 的值在对两个函数都有定义的所有输出上一致。在这种情况下，我们称 ''g'' 扩展了 ''f''。这个次序是 cpo，这里的最小元素是无处定义函数(有空域)。事实上，≤ 也是[[有界完全性]]的。这个例子还展示了为什么不总是自然的有一个最大元素。
+* [[sober空间]]的[[特殊化次序]]是 dcpo。
+* 所有有限偏序集合都是有向完全的，所有带有最小元素的有限偏序集合都是 cpo。
-* Consider the set of all [[partial function]]s on some set ''S'', i.e. functions defined only on some subset (its ''domain'') of ''S''. For two such functions ''f'' and ''g'', define ''f'' &le; ''g'' [[iff]] the domain of ''f'' is a subset of the domain of ''g'' and the values of ''f'' and ''g'' agree on all inputs for which both functions are defined. In this case, we say that ''g'' extends ''f''. This order is a cpo, where the least element is the nowhere defined function (with empty domain). In fact, &le; is also [[bounded complete]]. This example also demonstrates why it is not always natural to have a greatest element.
+* 所有[[完全格]]都是有向完全的并因此为 dcpos 提供了众多例子。
-* The [[specialization order]] of any [[sober space]] is a dcpo.
+== 引用 ==
-* Every finite poset is directed complete, every finite poset with a least element is a cpo.
+* {{cite book
+ | author = Davey, B.A., and Priestley, H. A.
+ | year = 2002
+ | title = '''Introduction to Lattices and Order'''
+ | edition = Second Edition
+ | publisher = Cambridge University Press
+ | id = ISBN 978-0-521-78451-1
+}}
+[[Category:域理论]]
-* All [[complete lattice]]s are of course also directed complete and thus provide numerous (though not particularly instructive) examples for dcpos.
+[[ru:Частично упорядоченное множество#Полное частично упорядоченное множество]]
-[[Category:序理论]]
-[[en:Complete partial order]]