categories - Category Theory list
 help / color / mirror / Atom feed
* Subobject Classifier Algorithm
@ 2011-02-23 15:16 Ellis D. Cooper
  2011-02-24 17:11 ` F. William Lawvere
  2011-02-25 11:20 ` Paul Taylor
  0 siblings, 2 replies; 10+ messages in thread
From: Ellis D. Cooper @ 2011-02-23 15:16 UTC (permalink / raw)
  To: categories

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


^ permalink raw reply	[flat|nested] 10+ messages in thread
* Re: Subobject Classifier Algorithm
@ 2011-02-24 22:14 Fred E.J. Linton
  0 siblings, 0 replies; 10+ messages in thread
From: Fred E.J. Linton @ 2011-02-24 22:14 UTC (permalink / raw)
  To: Ellis D. Cooper, categories

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


^ permalink raw reply	[flat|nested] 10+ messages in thread
* Subobject Classifier Algorithm
@ 2011-03-03 15:17 Ellis D. Cooper
  2011-03-04 13:44 ` Eduardo J. Dubuc
  0 siblings, 1 reply; 10+ messages in thread
From: Ellis D. Cooper @ 2011-03-03 15:17 UTC (permalink / raw)
  To: categories

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


^ permalink raw reply	[flat|nested] 10+ messages in thread
* Subobject classifier algorithm
@ 2013-10-20  8:25 Venkata Rayudu Posina
  2013-10-23  9:52 ` Prof. Peter Johnstone
  0 siblings, 1 reply; 10+ messages in thread
From: Venkata Rayudu Posina @ 2013-10-20  8:25 UTC (permalink / raw)
  To: categories

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


^ permalink raw reply	[flat|nested] 10+ messages in thread

end of thread, other threads:[~2013-10-23  9:52 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-02-23 15:16 Subobject Classifier Algorithm Ellis D. Cooper
2011-02-24 17:11 ` F. William Lawvere
2011-02-25 11:20 ` Paul Taylor
2011-03-01 16:52   ` F. William Lawvere
2011-03-02 10:35     ` Paul Taylor
2011-02-24 22:14 Fred E.J. Linton
2011-03-03 15:17 Ellis D. Cooper
2011-03-04 13:44 ` Eduardo J. Dubuc
2013-10-20  8:25 Subobject classifier algorithm Venkata Rayudu Posina
2013-10-23  9:52 ` Prof. Peter Johnstone

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).