Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!ux1.cso.uiuc.edu!midway!msuinfo!netnews.upenn.edu!saul.cis.upenn.edu!libkin From: libkin@saul.cis.upenn.edu (Leonid Libkin) Newsgroups: comp.theory Subject: Re: Novice question about monotonic/continuous functions Message-ID: <44752@netnews.upenn.edu> Date: 17 Jun 91 16:15:44 GMT References: Sender: news@netnews.upenn.edu Reply-To: libkin@saul.cis.upenn.edu (Leonid Libkin) Distribution: comp Organization: University of Pennsylvania Lines: 30 Nntp-Posting-Host: saul.cis.upenn.edu In article 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