5
$\begingroup$

In a poset $(D, \sqsubseteq)$, a compact element is an element $d \in D$ such that for every directed set $A$ which happens to have a supremum $\bigsqcup A \in D$ with $d \sqsubseteq \bigsqcup A$, it is $d \sqsubseteq a$ for some $a \in A$ (e.g., Definition I-4.1 of [Gierz et al 2003]).

My (elementary) question. Suppose $d$ is compact and $c \sqsubseteq d$. What are typical extra impositions on the poset, that ensure that $c$ must also be compact?

$\endgroup$
  • $\begingroup$ (hmm, now that I think of it, it might have been better to ask this in math.se...) $\endgroup$ – Basil Feb 12 '15 at 13:55
  • $\begingroup$ I added some more tags, using only "domain-theory" may have limited the number of people viewing the question. $\endgroup$ – Damiano Mazza Feb 13 '15 at 13:04
6
$\begingroup$

The only natural condition I can think of is Berry's "I condition" ([1], Sect. 12.3):

(I) each compact element dominates finitely many elements.

The above condition is the defining property of Berry's dI-domains, which are distributive (that's what the "d" stands for) algebraic domains satisfying condition I. This is a widely known and well studied class of domains, which served as the basis for what is known as "stable" semantics (an attempt to capture the sequential behavior of the $\lambda$-calculus). Girard's coherence spaces [2] give a particularly simple and useful example of dI-domains. A coherence space may be seen as the set of cliques of a reflexive graph, ordered by inclusion. The compact elements are the finite cliques, which obviously satisfy your requirement.

I don't know if generalizations of the I condition have been studied. A counterexample to your property is given by the ordinal $\omega+2$ ($\omega+1$ is compact but $\omega$ is not), so certainly generalizing "finite" to "well-founded+no infinite antichains" does not work.

[1] Roberto Amadio and Pierre-Louis Curien. Domains and Lambda-Calculi. Cambridge Tracts in Theoretical Computer Science, 1998.

[2] Jean-Yves Girard, Yves Lafont and Paul Taylor. Proofs and Types. Cambridge Tracts in Theoretical Computer Science, 1989.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.