Re: What is the right abstract definition of "connected"?

Re: What is the right abstract definition of "connected"?

[Jonathon Funk]

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
>
>
>

Re: What is the right abstract definition of "connected"?

[Stephen Lack]

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.

Re: What is the right abstract definition of "connected"?

[Marta Bunge]

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

Re: What is the right abstract definition of "connected"?

[Vaughan Pratt]

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).

Re: What is the right abstract definition of "connected"?

[Vaughan Pratt]

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

RE: What is the right abstract definition of "connected"?

[Marta Bunge]

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

Re: What is the right abstract definition of "connected"?

[Steve Vickers]

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.

What is the right abstract definition of "connected"?

[Vaughan Pratt]

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