完全偏序：修订间差异
删除的内容 添加的内容
小 →性质和有关文章 |
小 →例子 |
||
| 第16行： | 第16行： | ||
== 例子 == |
== 例子 == |
||
* 对于任何偏序集合，所有[[非空集合|非空]][[滤子]]的集合，用子集包含排序，是 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]]. |
|||
* 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'' ≤ ''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, ≤ is also [[bounded complete]]. This example also demonstrates why it is not always natural to have a greatest element. |
* 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'' ≤ ''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, ≤ is also [[bounded complete]]. This example also demonstrates why it is not always natural to have a greatest element. |
||
2006年9月6日 (三) 02:39的版本
 | 模板参数错误！（代码36）
|
在数学中，有向完全偏序和完全偏序是特殊种类的偏序集合。分别简写为 dcpo 和 cpo，它们特征化自特定特定完备性性质。dcpos 和 cpos 在序理论中考虑并主要应用于理论计算机科学和指称语义。
定义
一个偏序集合是有向完全偏序(dcpo)，如果它的每个有向子集都有上确界。完全偏序(cpo)是带有最小元素的 dcpo。在文献中，dcpos 有时分类为 sup-完全偏序集合，或混淆为“cpo”。带有最小元素的 dcpo 有时叫做尖角(pointed) dcpo 或尖角 cpo。
要求有向上确界的存在可能推动自把有向集合看作一般化的逼近序列把上确界看作各自(逼近)计算的极限。关于在指称语义的上下文中这种直觉的详情请参见域理论。
有向完全偏序集合的对偶概念叫做过滤完全偏序。但是这个概念在实践中不常用，因为你通常可以明确的在这个对偶的次序上工作。
性质和有关文章
有向完全性以各种方式关联于其他完备性概念。这在完备性 (序理论)中讨论。有向完全性自身在其他序理论研究中是经常出现的非常基本的性质。例如，涉及有向完全性的定理可以在连续偏序集合、代数偏序集合和Scott拓扑文章中讨论。在 dcpos 之间的函数经常要求是单调的甚至是Scott连续性的。
例子
- 对于任何偏序集合，所有非空滤子的集合，用子集包含排序，是 dcpo，甚至是 cpo 如果这个片许集合有最大元素。与空滤子在一起它也保证是 cpo。如果次序是交半格(甚至是格)，则这个构造(包括空滤子)实际上生成一个完全格。
- Consider the set of all partial functions 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 ≤ 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, ≤ is also bounded complete. This example also demonstrates why it is not always natural to have a greatest element.
- 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.
- All complete lattices are of course also directed complete and thus provide numerous (though not particularly instructive) examples for dcpos.