algebraic posetとは 意味・読み方・使い方

名詞

algebraic poset (複数形 algebraic posets)

1. (algebra, order theory) A partially ordered set (poset) in which every element is the supremum of the compact elements below it.
   • 1985 October, Rudolf-E. Hoffmann, The Injective Hull and the ${\displaystyle {\mathcal {CL}}}$-Compactification of a Continuous Poset, Canadian Journal of Mathematics, 37:5, Canadian Mathematical Society, page 833,

     A poset ${\displaystyle (P,\leq )}$ is said to be algebraic if and only if

     i) ${\displaystyle P}$ is up-complete, i.e., for every non-empty up-directed subset ${\displaystyle }$D, the supremum ${\displaystyle \operatorname {sup} \ d}$ exists,

     ii) for every ${\displaystyle x\in P}$, the set

     ${\displaystyle K_{X}:=\left\{y\in P\vert \ y{\text{ compact}},y\leq x\right\}}$

     is non-empty and up-directed, and

     ${\displaystyle x=\operatorname {sup} K_{x}}$.

     A poset ${\displaystyle P}$ is an algebraic poset if and only if it is a continuous poset in which, for every ${\displaystyle x,y\in P,x\ll y}$ (if and) only if ${\displaystyle x\leq c\leq y}$ for some compact element ${\displaystyle c}$ of ${\displaystyle P}$.

     Concerning the definition of an algebraic poset, a caveat may be in order (which, mutatis mutandis, applies to continuous posets): it may happen that all of the axioms for an algebraic poset are satisfied except that the sets ${\displaystyle K_{x}}$ fail to be up-directed ([50], 4.2 または [49], 4.5). Even when "enough" compact sets are readily available, it sometimes remains a delicate problem to verify the up-directedness of the sets ${\displaystyle K_{x}}$.

     The concept of an algebraic poset arose in theoretical computer science ([50], [54], cf. also [14]). It is a natural extension of he familiar notion of a (complete) "algebraic lattice" (cf. [9], [20], I-4).

   • 1988, Karel Hrbacek, A Powerdomain Construction, Michael Main, Austin Melton, Michael Mislove, David Schmidt (editors), Mathematical Foundations of Programming Language Semantics: 3rd Workshop, Proceedings, Springer, page 202,

     ALG is the category whose objects are algebraic posets and whose morphisms are continuous functions.

     A structure ${\displaystyle (D,\leq _{D},\cup _{D})}$ where ${\displaystyle (D,\leq _{D})}$ is an algebraic poset and ${\displaystyle \cup _{D}}$ is a binary operation on ${\displaystyle D}$ which is continuous (in both variables), commutative, associative and absorptive (i.e., ${\displaystyle d\cup _{D}d=d}$ for all ${\displaystyle d\in D}$) will be called a nondeterministic algebraic poset.

   • 1992, Stephen D. Brookes, et al., (editors), Mathematical Foundations of Programming Semantics: 7th International Conference, Proceedings, Springer, page 88,

     It is important to note that we have not assumed an algebraic poset is a cpo. The canonical example of an algebraic poset is ${\displaystyle {A^{*}\cup A^{*}}^{\sqrt {}}}$ in the prefix order; this poset enjoys the added condition that every element is compact.

   • 1997, Michael W. Shields, Semantics of Parallelism: Non-Interleaving Representation of Behaviour, Springer, page 41,

     The correspondence between primes and occurrences suggests that given an abstract prime algebraic poset, we may construct a behavioural presentation from it.

参考

• complete partial order
• up-complete poset
• up-directed

Further reading

• Compact element on Wikipedia.
  • Compact element#Algebraic posets on Wikipedia.
• Complete partial order on Wikipedia.
• Complete lattice on Wikipedia.
• Directed set on Wikipedia.
• Domain theory#Way-below relation on Wikipedia.
• Algebraic lattice on Encyclopedia of Mathematics