# several replies re: chains vs. directed sets

• To: types
• Subject: several replies re: chains vs. directed sets
• From: meyer@theory.lcs.mit.edu (Albert R. Meyer)
• Date: Tue, 26 Nov 91 17:55:40 EST
• In-Reply-To: John C. Mitchell's message of Mon, 25 Nov 91 19:24:11 EST <199111260024.AA18568@stork.lcs.mit.edu>

```Date: Mon, 25 Nov 91 20:04:15 -0500
To: jcm@cs.stanford.edu

Chains are usually (at least often) all you really need to provide the
desired fixed points.  Directed completeness is a more mathematically
elegant condition; it is particularly useful when one is working with
compact elements.

--- carl gunter

-------
Date: Mon, 25 Nov 91 21:59:14 -0500
From: bard@cs.cornell.edu (Bard Bloom)

>
> This is a technical question about domain theory:
> What are the main reasons to prefer chains over directed set,
> or vice versa?

I thought that the difference was a technical convenience for
Scottery. The isolated (aka finite, compact, basic) elements which
approximate x form a directed set, but not generally a chain.
So, you will need the concepts of "supremum of a directed set" at some

-- Bard

Return-Path: <bard@cs.cornell.edu>
Date: Mon, 25 Nov 91 21:59:14 -0500
From: bard@cs.cornell.edu (Bard Bloom)
To: jcm@cs.stanford.edu
Cc: types@theory.lcs.mit.edu
In-Reply-To: John C. Mitchell's message of Mon, 25 Nov 91 19:24:11 EST <199111260024.AA18568@stork.lcs.mit.edu>
Subject: chains vs. directed sets

>
> This is a technical question about domain theory:
> What are the main reasons to prefer chains over directed set,
> or vice versa?

I thought that the difference was a technical convenience for
Scottery. The isolated (aka finite, compact, basic) elements which
approximate x form a directed set, but not generally a chain.
So, you will need the concepts of "supremum of a directed set" at some

-- Bard

----------
Date: Tue, 26 Nov 91 10:40:05 GMT+0100
From: curien%FRULM63.BITNET@mitvma.mit.edu (Pierre-Louis Curien)

In reply to John Mitchell's query; chains versus directed sets,

I had the occasion to read in some detail, and with delight, Achim
Jung's thesis for the purpose of illustrating the mathematical
subtelties of domain theory to our PhD students, and I found in his
work striking illustrations of the interest of chains.
If you want to prove by contradiction that a partial order is not a
directed-complete partial order, the difficulty is already much cut
down if you know that you can assume that a chain (actually a
WELL-ORDERED chain, by the result of Markovsky), rather than an
arbitrary directed set makes it fail to be directed complete.

------------
Date:  Tue, 26 Nov 1991 11:03:23 -0500
From: gqz@zip.eecs.umich.edu

directed sets or vice versa.

I think the advantage of chains is  its conceptual simplicity:  it is a
linear order. On the other hand, directed sets are much less clumsy to
describe.

Plotkin in his `Pisa  Notes'  indicated that for omega-algebraic  cpos
chains and directed sets are interchangeable.

Moreover,  a weaker  condition   makes  it also   work  for continuous
functions.   Here  is a  little   result (from my   book on  `Logic of
Domains'):

Let D be an omega-algebraic cpo, and E ANY cpo.
A function f: D --> E is continuous (in terms
of directed sets) if and only if it is chain
continuous.

Guo-Qiang Zhang

```