RE: connectedness

RE: connectedness

[Marta Bunge]

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

RE: connectedness

[Marta Bunge]

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

Re: connectedness

[wlawvere]

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

...

connectedness

[Paul Taylor]

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