Subobject Classifier Algorithm

["Ellis D. Cooper" <xtalv1@netropolis.net>]

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