Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!ncar!gatech!udel!sbcs.sunysb.edu!usenet
From: stark@sbstark (Eugene Stark)
Newsgroups: comp.theory
Subject: Re: Novice question about monotonic/continuous functions
Message-ID: <1991Jun21.131019.22018@sbcs.sunysb.edu>
Date: 21 Jun 91 13:10:19 GMT
References: <BEVAN.91Jun16180108@panda.cs.man.ac.uk>
Sender: usenet@sbcs.sunysb.edu (Usenet poster)
Reply-To: stark@sbstark (Eugene Stark)
Distribution: comp
Organization: SUNY at Stony Brook Computer Science Dept.
Lines: 30
In-Reply-To: bevan@cs.man.ac.uk (Stephen J Bevan)

>Anyway, my problem (for today :-) is that I can't think of a function
>on a CPO (complete partial order) that is monotonic but is _not_
>continuous.  (I once asked this question to the person teaching the
>denotational semantics course and was told `Er, um, see me next time')

Perhaps part of the problem is that every monotone function to a finite
partial order is automatically continuous.  Thus, you need to think about
infinite examples.  Try the following:  Let N = {0, 1, 2, ... } be the
natural numbers (with the usual ordering), let N+ denote N u {t}, where
"t" is a new element ("top"), which we make greater than all the elements
of N.  Also, let N++ denote N+ u {t'}, where "t'" is a new top element
added in the same way.  Diagramatically:

	N+:  0 <= 1 <= 2 <= ... <= t
	N++: 0 <= 1 <= 2 <= ... <= t <= t'

Both N+ and N++ (but not N) are CPO's.  Consider the function f: N+ -> N++
that takes an ordinary natural number n to itself, but takes "t" to "t'".
Then f is monotone, but it is not continuous.

>So, can anybody help me with my (hopefully simple) question and also
>point me at a book/report/paper that explains these sorts of things
>and actually has some examples to go along with the (dry) definitions!

An old, but still good book is "Denotational Semantics" by J. Stoy, published
by MIT press.  Or, try "Denotational Semantics" by D. Schmidt (I forget the
publisher at the moment).  Or, "Foundations of Program Verification" by
J. Loeckx and K. Sieber.

							- Gene Stark