What is the right abstract definition of "connected"?
I'd like to say that "connected" is defined on objects of any category C having an object 1+1 (coproduct of two final objects). X is connected just when C(X,1+1) <= 2. If this definition appears in print somewhere I can just cite it. If not is there a better or more standard generally applicable definition I can use? If C(X,1+1) = 2 is citable but not <= 2, have the proponents of =2 taken into account that no Boolean algebra is connected according to the =2 definition? This is because 1+1 ~ 1 in Bool, CABA, DLat, StoneDLat, etc. (dual to 0x0 ~ 0 in Set, Pos, etc.), forcing C(X,1+1) = 1. Boolean algebras and distributive lattices fail the =2 test not because they are disconnected in any natural sense but rather because they are hyperconnected. It seems unreasonable to say that hyperconnected objects are not connected. There is also the question of the object of connected components of an object. In Set and Grph, if X has k connected components then C(X,1+1) = 2^k for all X, a set (C being ordinary, i.e. enriched in Set). In Stone (Stone spaces) however this only holds for finite X, with k = X. For infinite X Stone(X,1+1) is the set of clopen sets of X, which can be countably infinite and hence not 2^k for any k. If we read 2^k as Stone(k,2), taking k = X and 2 the Sierpinski space this doesn't help. However Stone(k,1+1) is ideal: instead of treating the object of connected components of a Stone space k = X as a set we can treat them as a Boolean algebra, namely that of the clopen sets of X. These examples are worth bearing in mind when considering the appropriate general definition of number of connected components of an object, and whether even to treat it as a number (cardinal) or a more general object. Connectedness seems somehow more basic than finiteness because we can easily draw examples of connected and disconnected objects, whereas it requires a vivid imagination to see the boundary between finite and infinite objects one might try to draw on paper. This motivates making connectedness prior to finiteness. Another familiar and easily visualized notion with small examples is that of path. Define a *path* to be a connected directed graph having one vertex each of degree (0,1) and (1,0), and all others (1,1). (The degree (m,n) specifies the in-degree as m and the out-degree as n.) We can then define a finite set to be one in bijection with the set of vertices of some path. This seems more natural than defining it to be one such that every injection on itself is a surjection, because there are a lot of injections to worry about and how do you convince yourself that surjective injections don't kick in until omega? Those who are already wedded to some other definition of finite will want to check that this path-based definition draws the boundary in the same place as theirs. For what definitions of "finite" can this not be shown? And are any of them more palatable than the path-based definition? Vaughan
Vaughan Pratt wrote:
I'd like to say that "connected" is defined on objects of any category C having an object 1+1 (coproduct of two final objects). X is connected just when C(X,1+1) <= 2.
Dear Vaughan, There's a big reason (there are also some little reasons, but I'll mention them later) why this doesn't match some accepted categorical definitions, and it's to do with the elements of C(1, 1+1). The topological condition is often stated differently: that every map X -> 1+1 factors via 1. Thus C(X,1+1) <= C(1,1+1). I think in most contexts you would want to say that, if anything is connected, 1 is, but you can easily find C(1,1+1) > 2. A simple example is with C = Set^2, where C(1,1+1) = 4 (two coproduct injections, and two more mixed morphisms). Then with this C, the alternative definition gives a useful notion of "fibrewise connectedness" for spaces over 2 and it's really just connectedness in the internal mathematics of (the topos) Set^2. Your definition is external. I would say don't persevere with your definition unless you really don't mind if 1 is disconnected. The different definition of "every map to 1+1 factors via 1" has been quite successful. That was the big reason. The little reasons I alluded to are that it is often useful to require every map to 0 also to factor via 1. That excludes 0 itself from connectedness. This is similar to saying 1 is not prime. Once you have the 0 and 2 cases for X, then for every finite n (= 1 + ... + 1) you have all maps X -> n factor via 1 - at least, if coproduct is well enough behaved w.r.t. limits. In constructive locale theory the standard definition is stronger and requires that for every discrete I, every map X -> I must factor via 1. This allows "infinite n". (Classically this can be deduced from the 0 and 2 cases.) All the best, Steve.
One suggestion is to say that an object X in a category C (with products) is connected relative to a functor F:B-->C if passing from maps m:b-->b' in B to maps XxF(b)-->F(b') (by composing the projection XxF(b)-->F(b) with F(m) ) is a bijection for every b,b' (or possibly just onto, not bijection, could be stipulated, but I don't know how inappropriate that would be). If pullbacks exist X*: C-->C/X, then this is equivalent to X*F full and faithful (or just full). If say b=1=terminal of B (and F(1)=1), then it is as if to say that if X is connected (relative to F), then elements of any b' are in bijection with (or at least onto) maps X --> F(b'): every such map is thus `constant'. For example, in this sense we may speak of a connected object X in a topos E-->S relative to Delta: S--->E. Jonathon ----- Original Message ----- From: "Vaughan Pratt" <pratt@cs.stanford.edu> To: "categories list" <categories@mta.ca> Sent: Monday, October 08, 2007 4:18 PM Subject: categories: What is the right abstract definition of "connected"?
I'd like to say that "connected" is defined on objects of any category C having an object 1+1 (coproduct of two final objects). X is connected just when C(X,1+1) <= 2.
If this definition appears in print somewhere I can just cite it. If not is there a better or more standard generally applicable definition I can use?
If C(X,1+1) = 2 is citable but not <= 2, have the proponents of =2 taken into account that no Boolean algebra is connected according to the =2 definition? This is because 1+1 ~ 1 in Bool, CABA, DLat, StoneDLat, etc. (dual to 0x0 ~ 0 in Set, Pos, etc.), forcing C(X,1+1) = 1. Boolean algebras and distributive lattices fail the =2 test not because they are disconnected in any natural sense but rather because they are hyperconnected. It seems unreasonable to say that hyperconnected objects are not connected.
There is also the question of the object of connected components of an object. In Set and Grph, if X has k connected components then C(X,1+1) = 2^k for all X, a set (C being ordinary, i.e. enriched in Set). In Stone (Stone spaces) however this only holds for finite X, with k = X. For infinite X Stone(X,1+1) is the set of clopen sets of X, which can be countably infinite and hence not 2^k for any k.
If we read 2^k as Stone(k,2), taking k = X and 2 the Sierpinski space this doesn't help. However Stone(k,1+1) is ideal: instead of treating the object of connected components of a Stone space k = X as a set we can treat them as a Boolean algebra, namely that of the clopen sets of X.
These examples are worth bearing in mind when considering the appropriate general definition of number of connected components of an object, and whether even to treat it as a number (cardinal) or a more general object.
Connectedness seems somehow more basic than finiteness because we can easily draw examples of connected and disconnected objects, whereas it requires a vivid imagination to see the boundary between finite and infinite objects one might try to draw on paper.
This motivates making connectedness prior to finiteness.
Another familiar and easily visualized notion with small examples is that of path. Define a *path* to be a connected directed graph having one vertex each of degree (0,1) and (1,0), and all others (1,1). (The degree (m,n) specifies the in-degree as m and the out-degree as n.)
We can then define a finite set to be one in bijection with the set of vertices of some path. This seems more natural than defining it to be one such that every injection on itself is a surjection, because there are a lot of injections to worry about and how do you convince yourself that surjective injections don't kick in until omega?
Those who are already wedded to some other definition of finite will want to check that this path-based definition draws the boundary in the same place as theirs. For what definitions of "finite" can this not be shown? And are any of them more palatable than the path-based definition?
Vaughan
Dear Vaugham,
I'd like to say that "connected" is defined on objects of any category C having an object 1+1 (coproduct of two final objects). X is connected just when C(X,1+1) <= 2.
If this definition appears in print somewhere I can just cite it. If not is there a better or more standard generally applicable definition I can use?
In Categories and Alligators (1.733, pg 124), an object in a pre-logos is called CONNECTED if it has exactly two complemented subobjects. They observe that in Sh(Y), the terminator is connected iff Y is a connected space. A PRE-LOGOS (pag 98) is a regular category in which Sub(A) is a lattice (not just a semi-lattice) for each A, and in which f#:Sub(B)---> Sub(A) is a lattice homomorphism for each f:A--->B. For a Grothendieck topos e:E---> S (over an arbitrary base S), this definition admits a generalization with "complemented subobject" replaced by "definable subobject", that is, subobjects classified by <e^*Omega_S, true> which, in case S is Boolean, agrees with the Freyd-Scedrov definition. I do not know if this is the sort of abstraction you want. Now for something (not) entirely different: A related notion to the one above is the notion of "abstractly (exclusively) unary" introduced in my thesis (Categories of Set-Valued Functors, University of Pennsylvania, 1966) as part of the definition of an "atom". An object A in a "regular category" X (in the sense of my thesis, which, modulo the stability assumptions is the same as Barr exact) is "abstractly (exclusively) unary" if every A---> \Sum {X_i} in C factors through one (and only one) injection. (The difference with connected is that arbitrary coproducts must be considered and, unlike what I assert in Proposition 11.8, finiteness does not imply this --incorrect use of Zorn's lemma. ) An object A is an "atom" in a "regular category" X if HOM(A,-):X--->Set preserves colimits, thus also the coproducts which exist in X. In particular, A is abstractly (exclusively) unary. More in particular, every A---> B + C factors uniquely trhough one of the injections. The latter is itself equivalent in this context to every A---> 1 + 1 factors uniquely through one of the injections. Just for completeness I state what is shown in my thesis. A "regular" category X is said to be "atomic" is the class of atoms in it is a set and is generating for X. (The funny thing is that almost all the terminology from my thesis was subsequently abandoned -- "atom" was relaced by "A.T.O." (provided exponentiation exists), and "atomic" had a quite different meaning. ) In any case, my theorem reads (all terminology as in my thesis): THM. (Characterization theorem) Let X be any cocomplete atomic regular category. Then there exists a small category C and a functor X--> S^{C^op} which is an equivalence of categories. Conversely every category of set-valued functors S^{C^op} is cocomplete regular atomic. Note: the terminology introduced in my thesis was motivated by the intended theorem which is of the sort "every complete atomic Boolean algebra is isomorphic to a field of sets" (meaning the "field" of all subsets of its set of atoms). There is no published version of my thesis except for microfilms something. The relative version (relative to a monoidal category V) of this characterization theorem is published in Marta Bunge, Relatived Functor Categories and Categories of Algebras, J. Algebra 11 (1), January 1969, 63-101 (communicated by Saunders MacLane). I am sure that I have expanded way more than you would have wanted. Apologies are in order. Cordially, Marta
Steve Vickers wrote:
The topological condition is often stated differently: that every map X -> 1+1 factors via 1. Thus C(X,1+1) <= C(1,1+1). I think in most contexts you would want to say that, if anything is connected, 1 is, but you can easily find C(1,1+1) > 2.
Thanks, Steve, this is great. I didn't want to go out on a limb with C(X,1+1) <= 2 (or = 2) if it was buggy, good to know about the C(1,1+1)
2 problem.
This also takes care of my concern about situations where 1+1 = 1, since your definition as stated makes Boolean algebras etc. connected. Presumably my taking the anarchist side (no unity) in the definition of locally cartesian closed obligates me to ask for the right formulation of "connected" in the absence of 1. How about the following? ================================================================= An object of a category is *connected* when its every morphism to a nonempty coproduct factors through an inclusion thereof. ================================================================= This eliminates all assumptions about the category -- if there are no nontrivial coproducts every object is connected by default (any morphism to a trivial coproduct factors through its one inclusion), reasonable when there is no recognizable (by the coproduct test) example of disconnectedness in the category to compare with. It also accomodates:
In constructive locale theory the standard definition is stronger and requires that for every discrete I, every map X -> I must factor via 1. This allows "infinite n".
with the same benefits - constructive I suppose (how is that judged exactly?), and allows infinite comparisons. If necessary one could qualify "coproduct" with "small" but methodologically it would seem preferable to let such size limits be set by a larger context. The effect of
The little reasons I alluded to are that it is often useful to require every map to 0 also to factor via 1. That excludes 0 itself from connectedness.
can be had by omitting "nonempty" from the definition. While this might seem a very natural omission, my concern with it is not so much 0 itself as the objects with morphisms to 0, e.g. all Boolean algebras except 1, which this definition would therefore make not connected. Stone spaces being totally disconnected, it just seems plain wrong to have their duals not connected either when they are so obviously connected, like totally (except 1, which is, like, connected but not totally, being dual to the empty Stone space, which is, like, disconnected but not totally). In the geometric duality of points and lines in the plane, two points are disconnected unless they coincide, while two lines are connected unless they are parallel. And an undirected graph and its complement either both contain an N or neither do, and in the latter case you can ask Google the following. Is an N-free graph connected if and only if its complement is disconnected? Google will confirm that it is, no need to click on any of the links it returns. (You may have to read several of Google's "answers" though since Google isn't yet smart enough to just say yes, or even to give the most direct "answer" first.) Graphs with an N are the undirected graph counterpart of the empty Stone space and the one-element Boolean algebra, being neither totally connected nor totally disconnected. Incidentally it's amazing just how many questions Google "knows" the answer to. Like all oracles though it tends to be a little erratic on questions involving future events. Google's staggering R&D budget notwithstanding, asking it whether Hillary will win the election is about as useful as asking the 8-ball: you're way better off asking the people who place sub-Google-sized ($100) bets on such questions. And asking NSF for funding for your research into questions you propose to answer by asking Google has even lower odds than asking Google. Vaughan
Dear Marta and Jonathan, As it turns out I really only needed the definition for categories of directed graphs, where "An object of a category is *connected* when its every morphism to a nonempty coproduct factors through an inclusion thereof" does exactly what I wanted there (if I haven't messed up my generalization of Steve Vickers' definition). This raises the interesting question however of whether the definitions you both mentioned differ from the above in the categories to which they apply, and if so which notion is preferable in those categories and why? What about Cat&Al's Sh(Y) for example? You both may have such examples; if not then I would argue that my definition has the advantages of generality and simplicity. Best, Vaughan Jonathan Funk wrote:
One suggestion is to say that an object X in a category C (with products) is connected relative to a functor F:B-->C if passing from maps m:b-->b' in B to maps XxF(b)-->F(b') (by composing the projection XxF(b)-->F(b) with F(m) ) is a bijection for every b,b' (or possibly just onto, not bijection, could be stipulated, but I don't know how inappropriate that would be).
If pullbacks exist X*: C-->C/X, then this is equivalent to X*F full and faithful (or just full).
Dear Vaughan ============================================================== An object of a category is *connected* when its every morphism to a nonempty coproduct factors through an inclusion thereof. ============================================================== Your proposed definition above is precisely the notion of *abstractly unary* from my J.Algebra '69 paper. It was so termed (instead of *connected*) since it does not need a terminal object to state it (precisely your motivation) and since one does not want to restrict to binary coproducts. When there is a terminal object, and when the coproducts considered are just the binary ones, it is enough to consider morphisms into the coproducts 1+1 (as I show in my thesis) and, in that case, it should be simply called *connected*. In another guise, this is the definition of *connected* given in Cats and Alligators, and it is the one directly inspired by topology. I see no reason to change the terminology. In short, your connected objects I have called abstractly unary. They came about in connection with atoms. An object A in a cocomplete (concrete) category E is an *atom* if HOM(A,-):E--->Set preserves colimits. More objectively, if E has exponentiation, Lawvere uses the notion of an *A.T.O.* instead, meaning that the functor (-)^A : E---> E has a right adjoint (the "amazing right adjoint"). I hope this helps, Cordially, Marta
Dear Vaughan, Lawvere and Janelidze have each argued for many years (in somewhat different contexts) that notions of connectedness and cohesion should be understood as relative. This impacts on both your questions: how should connectedness be defined, and what sort of answers should be allowed to the question ``how many connected components does X have?'' --- the second question becomes ``what is the codomain of the pi_0 functor?'' Steve Vickers mentioned the example Set^2. He said that the terminal object (1,1) is obviously connected. But it is equally obviously not connected: (1,1)=(1,0)+(0,1). The latter point of view comes from thinking of Set^2 as a Set-topos, where the connected components functor becomes the functor Set^2-->Set given by homming out of (1,1). The former point of view comes from thinking of Set^2 as defined over itself; then, as Steve says, (1,1) becomes almost tautologically connected, since pi_0 is just the identity functor Set^2-->Set^2. If crng is the category of finitely presentable commutative rings with no non-trivial nilpotents, then there is a lovely pi_0:crng^op-->set_f. For in this case every ring R splits as R_1 x R_2 x ... x R_n, where the R_i have no non-trivial idempotents. It is these R_i which are your connected components. For a larger category of commutative rings, you have to expand your notion of connected component to something like Stone spaces. For a locally connected topos E, defined over S, the inverse image functor e^*:S-->E has not just a right adjoint e_* but also a left adjoint e_!, which serves as pi_0. But one can describe just in terms of e_! -| e^* (i.e. without mention of e_*, and without all of the topos structure) the sorts of abstract properties needed for a good pi_0. This is the starting point for Janelidze's Galois theory. If E is infinitarily extensive (small coproducts, which are stable under pullback and disjoint), then a good notion of connectedness of an object X is that the hom-functor E(X,-):E-->Set preserves coproducts. This includes the locally connected topos case, which in turn includes your case of directed graphs. The case of crng is a finitary version. Regards, Steve Lack.
participants (5)
-
Jonathon Funk -
Marta Bunge -
Stephen Lack -
Steve Vickers -
Vaughan Pratt