From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/4015 Path: news.gmane.org!not-for-mail From: "Marta Bunge" Newsgroups: gmane.science.mathematics.categories Subject: RE: connectedness Date: Sun, 14 Oct 2007 19:44:37 -0400 Message-ID: NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; format=flowed X-Trace: ger.gmane.org 1241019661 11320 80.91.229.2 (29 Apr 2009 15:41:01 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:41:01 +0000 (UTC) To: categories@mta.ca Original-X-From: rrosebru@mta.ca Mon Oct 15 10:12:37 2007 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Mon, 15 Oct 2007 10:12:37 -0300 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1IhPf8-0006mO-7y for categories-list@mta.ca; Mon, 15 Oct 2007 10:07:14 -0300 Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 72 Original-Lines: 206 Xref: news.gmane.org gmane.science.mathematics.categories:4015 Archived-At: Dear Paul, In the following (private) response to Vaughan, I cleared up a couple of points from my previous posting. I reproduce it here publicly since those points may be relevant to some of the things you wrote. But I really have nothing else to say (at the moment) so no need to reply. Best regards, Marta >From: "Marta Bunge" >Reply-To: marta.bunge@mcgill.ca >To: rrosebrugh@mta.ca >CC: pratt@cs.stanford.edu >Subject: On the connectedness condition >Date: Fri, 12 Oct 2007 06:16:49 -0400 > >Dear Robert, > >I think that I have expanded enough in my response to Vaughan that you >already posted. There was a slight hitch in it, but on the whole is what I >intended to say. I would leave it at that. In any case I am sending this >cc. to Vaughan. > >The hitch is that only in the `at most' part in the definition of >`abstractly exclusively unary >' can one reduce the case to coproducts of 1 (should a terminal exist), but >the `at least' part refers to arbitrary coproducts and does *not* reduce to >coproducts of 1. > > >So, A is `abstractly exclusively unary' if HOM(A,-):E---> SET preserves >coproducts, and it is an `atom' if HOM(A,-):E---> SET preserves colimits. >What Vaughan calls `connected' is what I have called `abstractly unary' >but, more appropriately, `connected' should mean `abstractly exclusively >unary' (the factorization through the injections should be exactly one and >not just at least one). The case of abstractly exclusively unary wrt binary >coproducts of 1 is what Freyd-Scedrov (and all topologists) call connected. > >It would not be inappropriate to equate `connected' with `abstracly >exclusively unary', but not with just `abstractly unary' as Vaughan does. >In other words, = rather than just >, or full and faithful rather than >just full. I think that this was the real issue in Vaughan's question. >This is all there is to it. > > >Best regards, >Marta > >From: Paul Taylor >To: categories@mta.ca >Subject: categories: connectedness >Date: Fri, 12 Oct 2007 14:53:39 +0100 > >Vaughan Pratt's original enquiry was actually in the context of >graph theory (as I suspected at the time, and he subsequently >confirmed), but I would like to add something from the point of >view of constructive real analysis. > >First, though, I would like to underline something that Steve Lack >(almost) said, namely that the category in which you index your >components, and therefore also the one in which you define >connectedness, need to be EXTENSIVE, ie their coproducts should >be disjoint, and stable under pullback, and the initial object strict. > >Maybe we've over-done philology recently, but "component" means >"putting together", where we expect the parts to cover the whole >(coproduct), without overlapping (disjoint), to be distinguishable >(like disjoint union, but unlike addition and disjunction). >The modern notion of extensivity, in which Steve had a part, >captures this idea very neatly. The equivalence between definitions >of connectedness based on 1+1 and on X+Y surely depends on stability >under pullback, and the requirement that the choice between left >and right be unique surely requires disjointness. Maybe a close >study of Marta Bunge's work on abstract connectedness would clarify >this. > >Vaughan originally asked about various categories of algebras, >and Steve mentioned commutative rings, but quietly turned their >arrows around. Stone duality would suggest to me that one should >look for connectedness of algebras in their OPPOSITE category of >"spaces", which I understand in a generic sense that includes >sets, graphs, predomains, locales and affive varieties. > >Turning to constructive analysis, let me call the categorical >definitions above that involve coproducts "binary" and >"infinitary classical connectedness". > >In (almost) traditional topological language, a space X has the >binary classical connectedness property if, for any two open >subspaces U and V of X, > IF they cover and are disjoint and inhabited THEN false. > >The definition of connectedness that is used in constructive >analysis moves one of the hypotheses to the conclusion: > IF they cover and are inhabited THEN their intersection is inhabited. > >>From this definition we immediately obtain an APPROXIMATE INTERMEDIATE >VALUE THEOREM: IF a function f:X->R on a connected space takes both >positive (greater than -epsilon is enough) and negative (less than >+epsilon) values, say on inhabited open spaces U and V, then, as >U and V cover, they must intersect, ie the function takes values >within epsilon of zero. > >There are well known examples of spaces that pass the classical >definition of connectedness, whilst intuitively being made up of >two or more parts (for example the graph of sin(1/x) together with >the y-axis). Fewer spaces are connected in the constructive sense, >but I can't see any examples in which this might fix the classical >mis-definition. > >There are other ways of permuting the hypotheses and conclusions of >this definition. In particular, when the space X is compact, the >notion of covering it with opens can be internalised using the >universal quantifier or necessity operator []. Similarly, if it >is overt, habitation can be internalised using the existential >quantifier or possibility operator <>. > >Pushing these conditions across the implication can only be done >over an intuitionistic set theory at the cost of double negation. >However, in ASD, where open and closed subspaces are related via >continuous functions, and not set-theoretic complementation, the >Phoa principle allows this switch to be made without the not-not. > >In the case of a compact overt space such as the interval [0,1], >the classical, constructive, compact and over definitions of >connectedness agree. > >For a space that is either not compact or not overt, one of the >hypotheses must remain as an equation on the left of |-. > >Then constructive and overt connectedness agree: > U cup V = X |- <>U and <>V implies <>(U cap V) > >Compact connectedness is > U cap V = 0 |- [](U cup V) implies []U or []V. > >The latter gives rise to another approximate intermediate value >theorem: if f:K->R takes values >=0 and <=0 on OCCUPIED >subspaces, then its space of zeroes is also occupied. > >Here, OCCUPIED is the name that I propose for compact spaces whose >terminal projection is a proper surjection, just as an INHABITED >space is an overt one with an open surjection to 1. An occupied >space need not have any points. > >So far, I have only mentioned BINARY notions of connectedness, >but if we want to talk about families of connected COMPONENTS >then we must also consider INFINITARY connectedness (as Marta >stressed). Here the results for the constructive real line are >somewhat surprising. > >In order to avoid dependent types, I have found it more convenient >to discuss infinitary connectedness in terms of equivalence relations. > >In classical analysis, any OPEN EQUIVALENCE RELATION on [0,1], >ie any open subspace of the square that includes the diagonal, >is symmetric in it and has the transitivity property, is >INDISCRIMINATE - it relates 0 to 1 and indeed any point to any >other. > >This is not the case in Bishop's or Russian Recursive Analysis. >There is an open equivalence relation on [0,1] with infinitely >many equivalence classes, ie the interval fails the infinite >connectedness condition. The quotient by this equivalence >relation, ie the space that indexes the components, is discrete >but not Hausdorff, ie it admits an equality relation that is >not decidable. > >This one of the reasons why, at variance with many constructive >analysts, I believe that the HEINE--BOREL theorem is a necessary >part of analysis. > >In ASD, which obeys Heine--Borel, any open equivalence relation >on [0,1] or R is indiscriminate, as in the classical situation, >and the line and interval are connected in the infinitary senses. >Moreover, any open subspace of R is the disjoint union of countably >many open intervals, where each of these words needs careful >constructive re-definition. > >These results are in my paper "A lambda calculus for real analysis", >which was presented at CCA 2005 and you can obtain from > www.PaulTaylor.EU/ASD >I should point out that I am at the moment re-writing part of this >paper, to include a "need to know" introduction to continuous lattices, >cf my recent posting on this. However, the results that I have >discussed above are in the "stable" part of the text. > >Paul Taylor > > > _________________________________________________________________ Express yourself with free Messenger emoticons. Check out freemessengeremoticons.ca