[Prev][Next][Index][Thread]
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

InReplyTo: 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
point in the theory anyways, so why not start with it?
 Bard
ReturnPath: <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
InReplyTo: 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
point in the theory anyways, so why not start with it?
 Bard

Date: Tue, 26 Nov 91 10:40:05 GMT+0100
From: curien%FRULM63.BITNET@mitvma.mit.edu (PierreLouis 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
directedcomplete partial order, the difficulty is already much cut
down if you know that you can assume that a chain (actually a
WELLORDERED 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
John Mitchell asks about the main reasons to prefer chains over
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 omegaalgebraic 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 omegaalgebraic 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.
GuoQiang Zhang