bevan@cs.man.ac.uk (Stephen J Bevan) (06/17/91)
I'm currently reading a book on category theory, and in the initial chapters it goes through some mathematical structures that can be represented as categories such as :- semigroups, monoids, posets, ... etc. I have read about these in various guises before (courses on algebra, denotational semantics), but never fully understood them (I'm a poor CS type not a mathematical person :-), but I thought that as they are appearing yet again, I'd make a more concerted effort. 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') Now there must be some as every book I've read defines what a monotone function is and then goes on to define a continuous one. However, I've yet to see one that gives any decent examples! 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! Stephen J. Bevan bevan@cs.man.ac.uk PS. Just in case anybody is wondering :- this is not home/course work
libkin@saul.cis.upenn.edu (Leonid Libkin) (06/17/91)
In article <BEVAN.91Jun16180108@panda.cs.man.ac.uk> bevan@cs.man.ac.uk (Stephen J Bevan) writes: > >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. You can't find such an example unless your cpo has infinite ascending chains. If it has, the example is straightforward. Consider N (natural numbers) as a chain and add the top element T. Now, the function f: N union {T} ---> {0,1} (where 0 < 1, of course) given by f(n) = 0 if n \in N and f(T) = 1 is monotone (obvious) but not continuous: f(supN) = f(T) = 1, but supf(n) = 0. >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! I think Gunter and Scott's recent survey in the Handbook on theoretical comp sci has this example or somewhat similar. > >Stephen J. Bevan bevan@cs.man.ac.uk > >PS. Just in case anybody is wondering :- this is not home/course work Leonid libkin@saul.cis.upenn.edu
stark@sbstark (Eugene Stark) (06/21/91)
>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