Scholarlink

<p>We investigate posets that have an atomic Boolean lattice completion such that finite meets and joins are preserved by the embedding and the image of the poset under the embedding generates the Boolean lattice using complete lattice operations. It is shown that for a poset to have the above property it is necessary and sufficient for it to have a set of prime filters that separate points and such that the prime filters are pairwise incomparable. A description is given of the sets of ideals and filters used in the construction of a canonical extension of a poset for it to be an atomic Boolean lattice. Posets for which the MacNeille completion is an atomic Boolean lattice are also described. It is shown that the problem of determining if a finite poset is embeddable into a Boolean lattice such that the image of the poset generates the Boolean lattice is <Emphasis FontCategory="SansSerif">NP</Emphasis>-complete, whereas, determining if the MacNeille completion of a finite poset is a Boolean lattice can be done in polynomial time.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Atomic Boolean Lattice Completions of Ordered Sets

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月1日

查看全文
  • Wilmari Morton,
  • Clint J. van Alten

摘要

We investigate posets that have an atomic Boolean lattice completion such that finite meets and joins are preserved by the embedding and the image of the poset under the embedding generates the Boolean lattice using complete lattice operations. It is shown that for a poset to have the above property it is necessary and sufficient for it to have a set of prime filters that separate points and such that the prime filters are pairwise incomparable. A description is given of the sets of ideals and filters used in the construction of a canonical extension of a poset for it to be an atomic Boolean lattice. Posets for which the MacNeille completion is an atomic Boolean lattice are also described. It is shown that the problem of determining if a finite poset is embeddable into a Boolean lattice such that the image of the poset generates the Boolean lattice is NP-complete, whereas, determining if the MacNeille completion of a finite poset is a Boolean lattice can be done in polynomial time.