Subobject Classifier Algorithm

Subobject Classifier Algorithm

[Ellis D. Cooper]

P.20 of Prof. Taylor's book briefly recounts the history of
"function" as a (rigorously formulated) expression for numerical
calculation using arithmetic and transcendental operations. More
generally, Cox et al in "Ideals, Varieties, and Algorithms" define
"algorithm" as a (rigorously formulated) set of instructions for
manipulating input expressions resulting in output expressions.
Algorithms may be presented in "pseudocode" as a prelude to
implementation in a particular computer programming language such as
Maple, or Haskell.

Mac Lane-Moerdijk define an elementary (Lawvere-Tierney) topos to be
a category with finite limits, finite colimits, exponentials, and a
subobject classifier. So to prove a category is a topos it is
necessary to prove that it has a subobject classifier.

My query was stimulated by Lawvere-Schanuel in "Conceptual
Mathematics" pp.340-341 proof that the category of directed graphs
has a subobject classifier. They give a finite list of the
possibilities for an element of a graph (dot or arrow) to belong to a
subgraph. It seems to me such a list could be generated by an
algorithm. Then there is a step explained by pictures leading to
Omega(DirectedGraph). To me this hints at an algorithm too.

Ellis D. Cooper



[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Subobject Classifier Algorithm

[Eduardo J. Dubuc]

I copy an old post in the list that may be of interest to the present matter
and that I had saved by curiosity but not acted upon afterwards.

________________________________________________________________________
this is to tell, or remind, readers about the Web-based interactive
category-theory demonstrations I have on my site. Perhaps of interest to
new students now an academic year is starting. They're at
http://www.j-paine.org/cgi-bin/webcats/webcats.php . After some preamble,
this page contains a form divided into sections. Each section generates a
particular construct in the category of finite sets: e.g. a colimit,
equaliser, or initial object. You can input sets and arrows, or let the
demo choose its own. The output includes a diagram, and text explaining
it.

Cheers,

Jocelyn Paine
http://www.j-paine.org
+44 (0)7768 534 091

Jocelyn's Cartoons:
http://www.j-paine.org/blog/jocelyns_cartoons/
_______________________________________________________________________

greetings  e.d.

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Ellis D. Cooper wrote:
> P.20 of Prof. Taylor's book briefly recounts the history of
> "function" as a (rigorously formulated) expression for numerical
> calculation using arithmetic and transcendental operations. More
> generally, Cox et al in "Ideals, Varieties, and Algorithms" define
> "algorithm" as a (rigorously formulated) set of instructions for
> manipulating input expressions resulting in output expressions.
> Algorithms may be presented in "pseudocode" as a prelude to
> implementation in a particular computer programming language such as
> Maple, or Haskell.
>
> Mac Lane-Moerdijk define an elementary (Lawvere-Tierney) topos to be
> a category with finite limits, finite colimits, exponentials, and a
> subobject classifier. So to prove a category is a topos it is
> necessary to prove that it has a subobject classifier.
>
> My query was stimulated by Lawvere-Schanuel in "Conceptual
> Mathematics" pp.340-341 proof that the category of directed graphs
> has a subobject classifier. They give a finite list of the
> possibilities for an element of a graph (dot or arrow) to belong to a
> subgraph. It seems to me such a list could be generated by an
> algorithm. Then there is a step explained by pictures leading to
> Omega(DirectedGraph). To me this hints at an algorithm too.
>
> Ellis D. Cooper
>
>

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Subobject classifier algorithm

[Venkata Rayudu Posina]

Dear All,

In continuation of the discussion we had sometime ago regarding
algorithms for finding truth value objects, I am wondering if the
following constitutes an algorithm for calculating subobject
classifiers.

The basic idea is to use the correspondence between parts of an object
and maps to truth value object from the object to find the truth value
object.

In general we start with an object (of "simplest" shape such as
initial and gradually going to less simple ones), enumerate its parts,
and then look for objects to which the number of maps from the object
is equal to the number of parts of the object.

In the case of the category of sets, we start with the initial object,
which has one part.  Since there is exactly one function from empty
set to every set, this doesn't help in identifying the truth value
set.  So we move to [the next] sigleton set, which has two parts.  The
set to which there are exactly two maps from the singleton set is a
two-element set, which we take as [candidate] truth value set.
Finally we verify that the two-element set is indeed the truth value
set by way of checking

parts of an object = maps to truth value object from the object

in the case of [the set after sigleton set] two-element set. (For now
I'm ignoring the question of how many more objects do we have to
check.)

The above method does give the correct truth value object in the
categories of maps, graphs, and dynamical systems in addition to the
aforementioned case of the category of sets.

In the category of [set] maps, we only have to look at two objects
before we get to the terminal object, which lets us identify the truth
value object

w: D --> C

where D = {false, u, true} and C = {false, true}
with w(false) = false, w(u) = true, w(true) = true (see Sets for
Mathematics, pp. 114 - 9).

To give one more illustration, in the case of graphs, we have to go
little beyond terminal object to the generic arrow, whose five parts
correspond to the five graph maps from the generic arrow to the truth
value object of graphs (please see bottom-left corner of the cover of
Conceptual Mathematics).

In all these case we begin with [the simplest] initial object and go
to next [less simple] object, and at each stage we use

number of parts of an object = number of maps to truth value object
from the object

to identify (and then verify) the truth value object.  All the more
important is that we have to examine the above correspondence at a few
simple shapes only (beginning with the initial object) to find the
truth value object.

Would you be kind enough to let me know if there's something wrong in
using the above method to find the truth value object (when there's
one) of a category in general.

Thanking you,
Yours sincerely,
posina

http://conceptualmathematics.wordpress.com/


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Subobject classifier algorithm

[Prof. Peter Johnstone]

Dear Posina,

What you're doing is essentially just using the Yoneda lemma.
If your category is a functor category [C,Set], then Yoneda
tells you that, for each object c of C, \Omega(c) must
correspond bijectively to the set of maps C(c,-) --> \Omega,
and hence to the set of subobjects of C(c,-). So you might as
well *define* it to be the latter set. [Note that I
said `set' rather than `number' as you did, since these sets
may very well be infinite.]

More generally, if your category is a Grothendieck topos E,
then it has a representation as the topos of sheaves on a
site (C,J) whose underlying category C can be taken to be
the full subcategory of E on a generating set of objects.
Then you can similarly conclude that \Omega is (isomorphic to)
the sheaf whose value at a member g of the generating set
is the set of subobjects of g in E. So the answer to your
question `how many objects do we have to check?' is `all the
objects in some generating set'.

Regards,
Peter Johnstone

On Sun, 20 Oct 2013, Venkata Rayudu Posina wrote:

> Dear All,
>
> In continuation of the discussion we had sometime ago regarding
> algorithms for finding truth value objects, I am wondering if the
> following constitutes an algorithm for calculating subobject
> classifiers.
>
> The basic idea is to use the correspondence between parts of an object
> and maps to truth value object from the object to find the truth value
> object.
>
> In general we start with an object (of "simplest" shape such as
> initial and gradually going to less simple ones), enumerate its parts,
> and then look for objects to which the number of maps from the object
> is equal to the number of parts of the object.
>
> In the case of the category of sets, we start with the initial object,
> which has one part.  Since there is exactly one function from empty
> set to every set, this doesn't help in identifying the truth value
> set.  So we move to [the next] sigleton set, which has two parts.  The
> set to which there are exactly two maps from the singleton set is a
> two-element set, which we take as [candidate] truth value set.
> Finally we verify that the two-element set is indeed the truth value
> set by way of checking
>
> parts of an object = maps to truth value object from the object
>
> in the case of [the set after sigleton set] two-element set. (For now
> I'm ignoring the question of how many more objects do we have to
> check.)
>
> The above method does give the correct truth value object in the
> categories of maps, graphs, and dynamical systems in addition to the
> aforementioned case of the category of sets.
>
> In the category of [set] maps, we only have to look at two objects
> before we get to the terminal object, which lets us identify the truth
> value object
>
> w: D --> C
>
> where D = {false, u, true} and C = {false, true}
> with w(false) = false, w(u) = true, w(true) = true (see Sets for
> Mathematics, pp. 114 - 9).
>
> To give one more illustration, in the case of graphs, we have to go
> little beyond terminal object to the generic arrow, whose five parts
> correspond to the five graph maps from the generic arrow to the truth
> value object of graphs (please see bottom-left corner of the cover of
> Conceptual Mathematics).
>
> In all these case we begin with [the simplest] initial object and go
> to next [less simple] object, and at each stage we use
>
> number of parts of an object = number of maps to truth value object
> from the object
>
> to identify (and then verify) the truth value object.  All the more
> important is that we have to examine the above correspondence at a few
> simple shapes only (beginning with the initial object) to find the
> truth value object.
>
> Would you be kind enough to let me know if there's something wrong in
> using the above method to find the truth value object (when there's
> one) of a category in general.
>
> Thanking you,
> Yours sincerely,
> posina
>
> http://conceptualmathematics.wordpress.com/


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Subobject Classifier Algorithm

[Fred E.J. Linton]

When "Ellis D. Cooper" <xtalv1@netropolis.net> asks,

> What are the general rules for calculating the sub-object classifier
> of a topos? Or, for what class of toposes is there an algorithm for
> calculating the sub-object classifier of its members?

I imagine the sort of response he hoped for is one like:

In a presheaf topos, the suboject classifier &Omega; can be unraveled,
from its universal property, by help of the Yoneda Lemma, as each of the 
various values &Omega;(X) that &Omega; must take at an object X "is" the 
set of natural transformations from hom(-, X) to &Omega;, which, in turn,  
"is" the set of subfunctors of the representable functor hom(-, X).

I'll let others formulate similarly "algorhythmic" proposals for 
other sorts of topoi (comonadic ones, sheaves, etc.).

Cheers, -- Fred



[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Subobject Classifier Algorithm

[Ellis D. Cooper]

What are the general rules for calculating the sub-object classifier
of a topos? Or, for what class of toposes is there an algorithm for
calculating the sub-object classifier of its members?

Ellis D. Cooper



[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

RE: Subobject Classifier Algorithm

[F. William Lawvere]

For sheaves on a finite site (which by a theorem of AGV in SGA4 vol 2 is the same as all presheaves on some smaller finite category C), take the category of all functors from C^op to bold 2. It is a finite poset, in fact, a Heyting algebra (indeed even  bi-Heyting) belying the old misconception that one deviates from Boole only for infinite sets. If for each given A  in C we do the same for C/A, we get the figures of shape A in the Omega of the topos. The adjoints to maps induced by A'->A give a concrete model of tense logic.
By the same AGV (not only these C/A' ->C/A but) any functor between finite categories induces a geometric morphism that is even "essential".
Actually, taking sheaves valued in the topos of finite sets would be interesting, providing a more objective version of number theorythan the abstract exponential rig traditionally called "natural".
Topos theory is bristling with potential examples that we "generalists" have been slow to take up.
Anyway, the above construction of Omega is manifestly exponential, hence an effort to find computable sub cases is clearly needed, as you suggest Ellis.
Bill



> Date: Wed, 23 Feb 2011 10:16:56 -0500
> To: categories@mta.ca
> From: xtalv1@netropolis.net
> Subject: categories: Subobject Classifier Algorithm
> 
> What are the general rules for calculating the sub-object classifier
> of a topos? Or, for what class of toposes is there an algorithm for
> calculating the sub-object classifier of its members?
> 
> Ellis D. Cooper
> 
> 

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Subobject Classifier Algorithm

[Paul Taylor]

Ellis Cooper asked,

> What are the general rules for calculating the sub-object classifier
> of a topos? Or, for what class of toposes is there an algorithm for
> calculating the sub-object classifier of its members?

Thanks to Bill and Fred for describing the constructions.

I would suggest, however, that it is rather stretching the meaning
of the word "algorithm" to describe them as such.   What kind of
machine might be able to perform these operations?

A propos of this question, it is well known both to new students
of category theory and to those who like to use the subject to
discuss Life, The Universe And Everything, that:

(1)   a topos is a cartesian closed category with
(2)   an internal Heyting algebra Omega,

so ehat is the least that we have to add to these correct but
incomplete statements to give a characterisation of a topos?

Obviously I do not mean just reciting the definition of a subobject
classifier.

We should begin by strengthening these two statements:

The term "cartesian closed" is ambigious in its usage.  In computer
science, it has come to require just products (and exponentials), whereas
it seems to be implicit in older mathematical literature that all finite
limits are needed, including EQUALISERS in particular.  I therefore
replace (1) by

(1') a category with all finite limits and exponentials.

Secondly, the Heyting algebra Omega is COMPLETE: there are morphisms

       some_X: PX = Omega^X --> Omega   and   PX = all_X: Omega^X --> X

whose properties are easy to state.   So (2) becomes

(2') an object Omega with  some_X  and  all_X  for every object X.

Let's try to prove some things from this:

In order to avoid towers of exponentials, which are difficult enough
in LaTeX but quite illegible in ASCII, I will write PX for Omega^X,
but use the lambda calculus for exponentials.

Since Omega is a Heyting algebra it also has an internal equality:

        equals_Omega : Omega x Omega --> Omega

Using completeness, we can define an equality for all objects:

        equals_X : X x X --> Omega

where   equals_X (x, y)  is

        all_PX (lambda phi:PX.  equals_Omega(phi x, phi y)

so that a morphism   i:X-->Y  is mono iff

        equals_Y (i x, i x')   =   equals_X (x, x').

Given such a mono we can also define    I : PX --> PY  by

        I phi == lambda y. some_X (lambda x. phi x /\  equals_Y (i x, y))

and I would like to show that     I phi (i x) = i x.

However, to do this we need another assumption, the Frobenius law
for  some_X, specifically

        some x'X.  (phi x /\ x=x')    ==    phi x  /\  some x'.x=x'

where I have replaced the earlier notation with a friendlier one.

Instead of asserting the Frobenius law, I prefer a more general
property of Omega itself that I call the EUCLIDEAN PRINCIPLE:

(3)     omega  /\  F (omega)  ==  omega /\ F (T)

for all  omega:Omega  and  F:Omega^Omega,  which is to be interpreted
in either the lambda calculus or using generalised elements, ie

        omega : X --> Omega    and    F : X x Omega --> Omega.

We're not quite there.  None of the operations that we have introduced
so far yields elements of a general type  X.  So the final hypothesis is

(4)    every object  X   is SOBER

by which I mean that the diagram   X ->> PPX  ==>  PPPP X  involving
units of the monad  (PP, eta, mu = P eta P)   is an equaliser, or

(4')   every object X  admits definition by description.

Under these hypotheses, any mono i:X-->Y is uniquely classified
by some psi:Y-->Omega  and the category is a topos.

More detail of these ideas is to be found in my papers

     geohol:  Geometric and Higher Order Logic   (TAC 2000)
     foufct:  Foundations for Computable Topology
              (shortly to appear in a collection of papers about
              foundations of mathematics edited by Giovanni Sommaruga)
     equitop: Equideductive Topology  (see my previous posting)

all of which are available from my website

     www.PaulTaylor.EU/ASD/

followed by the acronym above.

Paul





[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

RE: Subobject Classifier Algorithm

[F. William Lawvere]

Of course the initial responses  given by Fred and me were notthemselves algorithmic, but why can they not be a prelude to such?Fred recalled the sequence of UMPs that defines Omega and I recalled what results in the case of a finite site. The hope is that experts in Maple and the like will be able to solve the sort of problem needed to generate displays. That is, given a finite presentation of a category C,find a presentation of the resulting Heyting algebra with the action ofC on it. Of course as stated this includes the Burnside problem , the Post problem etc . Hence the need for recognizing solvable subproblems.Even  for the class of graphic monoids, where the structure is finite, it growsexponentially , which has been used in the past by other computer scientists as an excuse not to consider it.  But if we are given a few fixed finite C, we can consider the class of categories discretely fiberedover them (equivalent to objects of the toposes) and try to see whetherOmega is computable in the above sense for them.
I  said contravariant 2-valued functors and of course these factor through the poset reflection. Calculating that poset reflection is a search problem  wrt 
the underlying graph, but actually wrt composition as well since we have todo it for the slice categories C/A.Bill> Date: Fri, 25 Feb 2011 11:20:36 +0000
> From: pt11@PaulTaylor.EU
> To: categories@mta.ca
> Subject: categories: Subobject Classifier Algorithm
> 
> Ellis Cooper asked,
> 
>> What are the general rules for calculating the sub-object classifier
>> of a topos? Or, for what class of toposes is there an algorithm for
>> calculating the sub-object classifier of its members?
> 
> Thanks to Bill and Fred for describing the constructions.
> 
> I would suggest, however, that it is rather stretching the meaning
> of the word "algorithm" to describe them as such.   What kind of
> machine might be able to perform these operations?
> 
> A propos of this question, it is well known both to new students
> of category theory and to those who like to use the subject to
> discuss Life, The Universe And Everything, that:
> 
> (1)   a topos is a cartesian closed category with
> (2)   an internal Heyting algebra Omega,
> 

...

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

RE: Subobject Classifier Algorithm

[Paul Taylor]

I cannot work out whether the message that Bill Lawvere originally
sent in HTML was turned into plain text by him or by Bob Rosebrugh.

Either way, I take exception to having the quotation of my message
reduced in a way that suggests that I believe that the statements

>> (1)   a topos is a cartesian closed category with
>> (2)   an internal Heyting algebra Omega,

are sufficient to characterise a topos.

My objective was to move the discussion ON from quoting 1970s lemmas.

If someone has indeed programmed these lemmas in Maple then it would
be interesting to hear about that.  (Maybe David Rydeheard's work
on "electronic category theory" counts.)  Otherwise "lemma" remains
the appropriate word for them, not "algorithm".  By the way, I consider
it no disgrace to call something a lemma: see page 192 of my book.

The point of the characterisation that I gave for a topos is that
the difference between set theory (= a topos) on the one hand and
topology and computation on the other is that quantification over
arbitrary sets is allowed, but only over compact or overt spaces.

This restriction brings us a little closer to what most people
would call an algorithm.

Paul Taylor



[For admin and other information see: http://www.mta.ca/~cat-dist/ ]