Date: Tue, 23 May 1995 00:47:14 -0300 (ADT)
Subject: question about bounded toposes
---------- Forwarded message ----------
Date: Mon, 22 May 95 19:09:45 +0300
Subject: question about bounded toposes
Topos theoretic concepts are implicitly in the focus of semantic modeling --
an active subarea of the DataBase research. The corresponding theory
developed in the DB community is a diverse collection of awkward
pseudo-formal constructs, semi-formal correct specifications (whose precise
counterparts are however known in Category Theory long ago), and also deep
insights elaboration of which seems can contribute to CT itself.
In particular, the following categorial construct which I'd call a
{\em bounded power-object}
is extremely useful in DB theory and my question is whether it was
explored by anybody before.
DEFINITION 1. A category ${\cal C}$ is said to have {\em bounded power-objects}
if any jointly monic pair (relation), f:R-->a, g:R-->B, can be extended to the
following commutative diagram (PDiag):
B===B where the square (r,s,n,f) is pull-back
^ ^ and (s,e) is jointly monic.
e| |
s | |
P<---E |g
^ ^ |
r| |n |
| | |
A<---R===R
f
In addition, this augmentation enjoys the following universal property:
for any other similar augmentation of (f,g): (PDiag') with P',E',r' etc
instead of P,E,r etc. there are uniquely determined arrows u1:P-->P' and
u2:E-->E' commuting the entire diagram (PDiag)+(PDiag').
It is easy to prove that bounded power-objects are unique up to isomorphism.
So, given an object B, there is no the universal power-object of the object
B, ${\bf P}B $, but for any relation R=(f,g) with B a domain there is the
R-specific power-object ${\bf P}_{R}B $. Thus, B has many power-objects
indexed by relations to B.
Of course, if ${\cal C}$ is cocomplete they can be joined into the
universal power-object of B but unbounded cocompleteness is just the property
we wish to avoid.
DEFINITION 2. {\em A bounded topos} is a category with finite limits and
finite colimits which has bounded power-objects for all jointly monic pairs
of arrows.
REMARK 1. I do not familiar with Mikkelsen's proof that finite limits and
power-objects imply finite colimits so I do not know to what extent the
finite colimits condition can be relaxed.
REMARK 2. The concept of bounded topos constitutes a natural universe for
computationally feasible set theory. Indeed, bounded power-sets are tractable
(ie, within the polynomial time computability) in contrast to intractability
of finitary yet unbounded powersets.
QUESTION: What is known about bounded toposes? What is known about
complexity evaluations of topos-theoretic operations?
CONCLUDING REMARK. The interplay between computational and descriptional
complexities is one of the most nice and exciting hot topics of the modern
model theory. It seems that exploring the interplay between two hierarchies
when the descriptional one is specified in the language of graph-based
topos-theoretic operations will be of equal beaty but simultaneously of a much
more immediate practical impact.
Grateful for any comments and remarks,
Zinovy Diskin
Date: Tue, 23 May 1995 09:41:59 -0300 (ADT)
Subject: Diskin's question
Date: Tue, 23 May 95 10:01 BST
From: Dr. P.T. Johnstone
I don't have a direct answer to Diskin's question, but here are a few
immediate comments about it.
1. I'm not happy with the terms `bounded power-objects' and `bounded
topos', because `bounded' has another meaning in topos theory (bounded
geometric morphisms) and I sense that this could lead to confusion. It
seems to me that something like `local power-objects' would be a better
name for the concept Diskin describes ... but of course `local' is also
a word which is already heavily used by topos-theorists.
2. I presume that the universal property of the bounded/local
power-object, as described by Diskin, is the wrong way round: that is,
one wants (P,E) to be terminal rather than initial in the category of
diagrams of the form (PDiag). (If you ask for an initial object, then
the problem always has a trivial solution: take P = A and E = R.)
3. Assuming I'm right about (2), then the condition that an object B
has bounded power-objects is equivalent to saying that the functor
Rel(-,B) is multi-representable in the sense of Diers (rather than
representable, as it would be in a topos). There is a considerable
literature (much of it written by Diers, but some by other people
including myself) about multi-representability, multi-limits and the
like; but I don't think any of it addresses the multi-representability
of this particular functor.
4. I'd find it a lot easier to think about the problem if I had a
simple example of a category (other than a topos) with this property,
on which to test my ideas. Does Diskin (or anyone else) have such an
example?
Peter Johnstone
Date: Wed, 24 May 1995 17:52:49 -0300 (ADT)
Subject: Re: question about bounded toposes
Date: Wed, 24 May 95 18:41:47 +0300
From: Zinovy Diskin
Dear All,
I must apologize: the universal property of (PDiag) described
in my previous definition of bounded power-object is evidently
not suitable (thanks to Peter Johnstone) and terminality of
(P,E) is also not suitable: take for P' a superobject of A and
for E' a relation from A' to B which is a "conservative"
expansion of R -- then there are no canonical arrows from P' to
P (and from P to P' too).
So, actually the question is open which universal property of
(PDiag) provides intended semantics of the construction.
Zinovy Diskin
Date: Sun, 11 Jun 1995 11:24:32 -0300 (ADT)
Subject: Re: Diskin's question (fwd)
Date: Fri, 09 Jun 95
From: Mamuka Jibladze
Despite some confusion around the question of Diskin I think there is an
exemplary situation where one may test ideas; hence a partial answer to
> 4. I'd find it a lot easier to think about the problem if I had a
> simple example of a category (other than a topos) with this property,
> on which to test my ideas. Does Diskin (or anyone else) have such an
> example?
>
> Peter Johnstone
>
. Choose some notion of `small' good enough, in particular inherited by
quotients (plus further strong requirements; e.g. I believe `K-finite'
satisfies them all). Take a topos where the subobject classifier is not small.
Consider the subcategory of small objects. Then the IMAGES of classifying maps
of relations may serve for the purpose Diskin is talking about.
One simple example: the category of finite-sets-with-an-endomap.
Mamuka Jibladze
Date: Thu, 29 Jun 1995 16:21:08 -0300 (ADT)
Subject: answer to Diskin's question
Date: Thu, 29 Jun 1995 19:05:29 MESZ
From: Thomas Streicher
I think I have an answer now to Z. Diskin's question on what he called
originally bounded toposes.
His setting is a category C with pullbacks and binary products.
Assume that there is given a family of B-indexed subobjects of A represented bya mono R >-> BxA. How can formulate by a universal property the collection of
all subobjects of A showing up in the enumeration
" { {a:A|R(b,a)} | b:B} "
Consider the presheaf H_R : C^op -> Set defined as
H_R(I) = { (fxA)*R | f : I -> B }
H_R(f)(S) = (fxA)*S
We say that that the "power object of A bounded by R" exists if the presheaf
H_R is representable, i.e. there exists an object P_R(A) together with a
subobject E(A,R) >-> P_R(A)xA such that for any f : I -> B the subobject
(fxA)*R can be obtained as (chi x A)*E(A,R) for a unique chi : I -> P_R(A).
If "bounded" is understood in the liberalized sense that one means by P_R(A)
the collection of subsets of A contained in a {a:A|R(b,a)} for some b : B then
one simply has to redefine the presheaf H_R as follows
H_R(I) = { S >-> IxA | S contained in (fxA)*R for some f : I -> B} .
Under this interpretation of "bounded" a category C with finite limits is a
topos iff for any A the bounded Power Object P_R exists for the relation
: A -> 1xA.
Thomas Streicher