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 Bunga'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
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" <martabunge@hotmail.com> 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 <pt07@PaulTaylor.EU> 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
Paul's remarks are quite cogent. Indeed, when Steve Schanuel and I introduced the notion of Extensive category, one of the main motivations was the recognition that a rational theory of connectedness requires a condition on the category of not-necessarily connected things, and moreover that a category like (K-rigs)^op satisfies this condition even though it is not exact. (Also there was the realization of a need for an algebraic geometry for some cases where K is not a ring, indeed where it may satisfy 1+1=1). When C^op is an algebraic theory, i.e., C has finite coproducts, then the algebras form a topos iff those coproducts satisfy extensivity (because then the attempt to consider "finite disjoint covers" actually succeeds to satisfy Grothendieck's condition for a"topology"). But a non-trivial dual question is "almost" stated by Paul: For which algebraic categories is the opposite extensive ? Obvious extensions of K-rigs are M-K-rigs, where the given monoid M acts by K-rig homomorphism, and an infinitesimal version of that where M is a Lie algebra acting by derivations. A special case of the question is, given an algebraic category that is coextensive, which varieties in it are also ? (Here I take "variety" in the original Birkhoff spirit, i.e., a full subcategory that is also algebraic for the special reason that it is defined by a quotient theory and is thus closed wrt subalgebras, which a general full reflective algebraic subcategory would not be). A sufficient condition is that the inclusion functor is also COREFLECTIVE. Call these "core varieties". Proposition : A core variety in a coextensive algebraic category is also coextensive in its own right. Hence any core variety is a candidate to serve as the algebras for an algebraic geometry. (Extensivity was the only distinctive feature of rings mentioned in Gaeta's notes on Grothendieck's Buffalo Lectures 1973, and indeed you can verify that the basic construction of a corresponding topos of spaces works, in particular that the algebras become algebras of functions on these). For single-sorted theories, a core variety is defined by the imposition of further identities in one variable having the rare property that the elements satisfying them form a subalgebra. For example ( )^p=id in algebras of characteristic p. Already for K=2, there are nontrivial core varieties in K-rigs. The best known is the category of distributive lattices, the corresponding topos of spaces being generated by the category of finite posets. The core of any 2-rig is the DL defined by two equations, one of which is idempotence of the multiplication. But the other equation, taken alone, defines a larger core variety whose spaces look like intervals, cubes,etc ; it is intimately related to a less systematic subject burdened with the odd name "tropical". Bill On Fri Oct 12 9:53 , Paul Taylor sent:
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 Bunga'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.
...
Dear Paul,
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.
In my now obsolete 1966 thesis, the context was that of a category with finite limits and finite coproducts, but I had not assumed therein that coproducts should be disjoint and universal. With these assumptions, the definitions of `abstractly unary' for arbitrary binary products (factors through AT LEAST one of the injections) and of `abstractly exclusively unary' (factors through exactly one of the injections) are equivalent by the disjointness part, and are equivalent also to the same notions with binary coproducts of 1 instead of arbitrary binary coproducts (by the universal or stability part). So, *any* of those in this context should mean `connected'. Without those conditions, but with just a terminal object and binary coproducts, then the `at least' part does not reduce to that of coproducts of 1, but the `at most' part does. In that case, the notions correspond to `abstractly unary' and `abstractly exclusively unary', and they are not equivalent. So it all depends on the ambient category.
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.
I still have to digest your disquisitions on constructive analysis, which seem most interesting, but on the above point, I emphasize that inded one must keep the disctinction between connectedness wirt binary coproducts and connectedness wrt arbitrary coproducts (indexed externally, e.g. by a set in a Grothendieck topos E-->SET, or by an object of S in the cae of a bounded topos E-->S. Whether the terminology must make that distinction I am not sure of, or maybe we could say `connected' for the binary case (which is also intrinsic), and `S-connected' for the case of S-indexed coproducts. Once again, under enough hypotheses as I szaid above and was also mentioned by Steve Lack. I am not sure of which hypotheses Vaughan wants to make but, if the minimal possible, then he might need the detailed analysis that I proposed and, in that case, reserve `connected' in the binary case for `abstractly exclusively unary', not simply `abstractly unary', and `connected' when only the binary coproduct considered is 1+1. But if his categories ae categories of graphs, I don't see his problem. With best regards, Marta
participants (3)
-
Marta Bunge -
Paul Taylor -
wlawvere＠buffalo.edu