Re: Equalisers and coequalisers in categories with a \dag-involution

Re: Equalisers and coequalisers in categories with a \dag-involution

[Peter Selinger]

Jamie Vicary wrote:
>
>     Of course, in the light of
>               http://www.arxiv.org/abs/math.CT/0604542   ,
> perhaps we only need require that our dagger-category has products and
> equalizers in order for it to have 'finite bilimits'! In remark 2.6 of
> [2] cited in your email below, you write that if a dagger-category has
> products then it must of course have coproducts, but it need not have
> biproducts. Presumably, math.CT/0604542 proves you wrong here?

You are referring to the paper "Finite Products are Biproducts in a
Compact Closed Category" by Robin Houston.

It does not prove me wrong. Robin's construction only applies to
compact closed categories. In general, a dagger category doesn't need
to be compact closed.

Actually, there is a counterexample to support my remark 2.6. It is
due to Robin Houston and myself (any typos or mistakes are mine).

(1) There exists a category C with finite products and coproducts,
    with a zero object, and such that for all A,B, A+B is isomorphic
    to AxB (not naturally), but for some A,B, the canonical map f:A+B
    -> AxB is not an isomorphism.

    Proof: Let C be the category of sets of cardinality 0 or aleph_0,
    with partial functions as the morphisms. Then the empty set is
    initial and terminal. We have AxB = A \union (A*B) \union B, where
    "x" denotes categorical product, and "*" denotes cartesian product
    of sets. Further A+B = A \union B. By inspecting cardinalities, we
    find that AxB and A+B have equal cardinality, for all A, B, and
    hence they are (not naturally) isomorphic. However, the canonical
    map f:A+B -> AxB satisfying p_i.f.q_j = \delta_{ij} maps
    everything to the first and third components of AxB = A \union
    (A*B) \union B, hence is not onto when A,B are non-empty.

(2) Corollary: C does not have biproducts.

(3) Corollary: There exists a category C with finite products and
    coproducts, and such that A+B = AxB for all A,B, but which does
    not have biproducts.

    Proof: choose a skeleton of the category in (1).

(4) There exists a dagger category with finite products, but which
    does not have biproducts.

    Proof: Take C as in (3), and consider D = C x C^op. Then D has
    products and coproducts as inherited componentwise from C and
    C^op. Also, it satisfies X+Y = XxY. Further, D has no biproducts,
    or else the forgetful functor to C would preserve them.

    Now consider D', the full subcategory of D consisting of objects
    of the form (A,A). This has products and coproducts, and they are
    not biproducts. Further, D' is a dagger category with (f,g)^{\dag}
    = (g,f).

Another related remark is that even *if* a dagger category has
biproducts, then they need not be dagger-biproducts. Here is a
counterexample. Consider the category of matrices with rational
entries. Objects are arities, and composition is standard matrix
multiplication, but define the following non-standard dagger: if A is
an mxn-matrix, then let A^\dag = A^{transpose} * 3^(n-m). This is
indeed an involutive, identity-on-objects functor.  As a category, it
is equivalent to finite-dimensional Q-vector spaces, so it has
biproducts, and it is also compact closed. However, there are no
isometries e : Q -> Q^2 (and hence, no dagger-biproducts). If such an
isometry existed, say with matrix (a, b)^{transpose}, then we would
have e^\dag.e = (a^2 + b^2)/3 = 1. However, the equation a^2 + b^2 = 3
has no solution in the rational numbers. (In Z/9Z, any sum of two
squares that is divisible by 3 is also divisible by 9; therefore the
same holds in the integers. The claim about the rational numbers
follows by taking a sufficiently large square common denominator).

I do not know whether Robin Houston's construction, when applied to a
dagger compact closed category, yields dagger-biproducts.  Note that
the previous counterexample is not dagger-compact closed (dagger does
not preserve tensor). It therefore doesn't answer this last question.

Best, -- Peter

Re: Equalisers and coequalisers in categories with a \dag-involution

[Jamie Vicary]

>     Could we make the following definition: a dagger-category has
> 'finite bilimits' if any finite diagram D in the category has an
> 'isometric cone', a cone for which all the associated morphisms to the
> objects of D are isometries, along with some sort of condition that
> the isometries are orthogonal in the correct way. It is interesting to
> consider this in the case of products and equalisers: for products
> AxB, so it seems, the isometries to A and B will generally be
> _projectors_, but for equalisers E-e->A=f,g=>B, the isometry e will
> generally be an _injector_! So we cannot ask for the cone morphisms to
> be isometric projectors, or isometric injectors. But perhaps this is
> OK, and we can just require them to be isometries. This definition of
> bilimit has the 'local flavour' of the definition of biproducts, but
> cooking up a generally-applicable orthogonality condition on the
> isometries seems tricky.

Fred Linton has pointed out to me that my terminology here is not
standard. By "isometric injector", I mean a morphism which is unitary
on its range, i.e., one-to-one and norm-preserving in the case of
Hilbert spaces; I believe this is usually simply referred to as an
isometry. By "isometric projector", I mean a morphism which is unitary
on the complement of its kernel; some people prefer to call this a
"partial isometry". I was then using the terms "isometric" and
"isometry" to mean "isometric projector or isometric injector".

    Anyway, the simple prescription I give for a bilimit cannot work,
as it is easy to find diagrams in the category of finite-dimensional
Hilbert spaces, our canonical example of a strongly compact-closed
category with biproducts, for which the colimit and limit are not
isomorphic. A diagram f:A-->B for non-iso A and B is the simplest
example. However, if we restrict to diagrams F:D-->FdHilb such that D
admits a dagger-operation compatible with the dagger on FdHilb, then I
believe the conjecture becomes plausible.

            Regards,
                 Jamie Vicary.

Re: Equalisers and coequalisers in categories with a \dag-involution

[Jamie Vicary]

Peter,

    Thank you for that detailed response! So it seems that if these
dagger-subobjects do exist, then then will have good properties. But
existence is tricky; in particular, there does not seem to be an
elegant property (analagous to having finite limits and colimits) that
will guarantee that all of this works.

    Could we make the following definition: a dagger-category has
'finite bilimits' if any finite diagram D in the category has an
'isometric cone', a cone for which all the associated morphisms to the
objects of D are isometries, along with some sort of condition that
the isometries are orthogonal in the correct way. It is interesting to
consider this in the case of products and equalisers: for products
AxB, so it seems, the isometries to A and B will generally be
_projectors_, but for equalisers E-e->A=f,g=>B, the isometry e will
generally be an _injector_! So we cannot ask for the cone morphisms to
be isometric projectors, or isometric injectors. But perhaps this is
OK, and we can just require them to be isometries. This definition of
bilimit has the 'local flavour' of the definition of biproducts, but
cooking up a generally-applicable orthogonality condition on the
isometries seems tricky.

    Of course, in the light of
              http://www.arxiv.org/abs/math.CT/0604542   ,
perhaps we only need require that our dagger-category has products and
equalizers in order for it to have 'finite bilimits'! In remark 2.6 of
[2] cited in your email below, you write that if a dagger-category has
products then it must of course have coproducts, but it need not have
biproducts. Presumably, math.CT/0604542 proves you wrong here?

                     Jamie.

Re: Equalisers and coequalisers in categories with a \dag-involution

[Peter Selinger]

Jamie Vicary wrote:
>
> Dear all,
>
>     Consider the following straightforward coequaliser (e,E) formed by
> f,g:A-->B and e:B-->E, with e.f=e.g. I am working in a category with
> biproducts, and with a contravariant involutive endofunctor (--)^\dag
> on the category which is compatible with the biproducts; i.e.
>                 (projection)^\dag = injection
> for all projections and injections making up a part of a biproduct. In
> such a category, it is natural to consider the coequaliser object E to
> be the subspace of B on which the morphisms f and g agree. It is
> therefore natural to require e.(e^\dag) = id_E; this sort of condition
> is similar to the sorts of conditions that form part of the definition
> of the biproduct.
>
>     I'm asking whether there exists a natural framework generalising
> the theory of biproducts, which is analagous to the way that
> (co)limits generalise (co)products, within which I can safely assume
> that e.(e^\dag) = id_E. Biproducts seem quite different from products
> and coproducts, though, so I don't know how it would work.
>
>                Jamie Vicary.

Dear Jamie,

your equation e.(e^\dag) = id_E only makes sense if your functor
(--)^\dag is the identity on objects. In this case, you are dealing
with a dagger category in the sense of [1]. Dagger categories are
important in quantum physics; an important example is the category
Hilb of Hilbert spaces and linear operators, with dagger being the
adjoint of an operator.

I will dualize your question to make it a question about equalizers,
or more generally, monomorphisms. Monomorphisms with the property
(e^\dag).e = id_E are investigated in [2], where they are called
dagger-subobjects. (Both papers also deal with biproducts of the kind
you asked about).

Your question raises a basic problem, which is that it is not
well-defined. Specifically, while equalizers are only defined "up to
isomorphism", the property

 (e^\dag).e = id_E   (*)

is not invariant under isomorphisms of E. As a simple example, the two
morphisms f,g: C -> C^2 in Hilb, defined by f(x) = (x,0) and g(x) =
(2x,0), define isomorphic subobjects, yet f satisfies (*), whereas g
does not. Therefore one cannot ask whether "the" equalizer of two maps
satisfies (*).

The fundamental issue is that in a dagger-category, there is a
distinguished subclass of isomorphisms: the unitary ones. An
isomorphism f: E -> E' is called unitary if f^\dag = f^{-1}. And
although the property (*) is not invariant under arbitrary
isomorphisms, it is invariant under unitary isomorphisms.

To many category theorists, it may seem strange that some important
categorical property is not invariant under isomorphism. But actually,
this is quite natural. With every notion of structure comes a notion
of structure-preserving isomorphism, and one expects properties
related to the structure to be preserved only by the
structure-preserving isomorphisms, not by arbitrary isomorphisms.
Dagger is such a structure, whose structure-preserving morphisms are
exactly the unitary ones.

Now to get back to your question: Consider equalizers (or more
generally, subobjects) in a dagger category. Of the many maps e: E ->
A representing a given subobject (or equalizing a given pair of
arrows), some may not be unitarily isomorphic to some others, so they
fall into equivalence classes modulo unitary isomophism. One may ask
whether any of these equivalence classes is distinguished, i.e.,
whether one of them deserves to be called "the" equalizer or "the"
subobject, and would be unique up to unitary isomorphism. It turns out
that, provided it exists at all, there is indeed a distinguished
choice of such a subobject, and it is the one satisfying (*). So we
can call a monomorphism satisfying (*) a "dagger-subobject", and an
equalizer satisfying (*) a "dagger-equalizer", and so forth. (In the
literature, particularly on Hilbert spaces, a morphism satisfying (*)
is also called an "isometry").

Fortunately, if any representative of a subobject satisfies (*), then
that representative is unique up to unitary isomorphism. So it really
makes sense to speak of "the" dagger-subobject etc.

While uniqueness is easy, existence is a tricky matter. There
certainly are examples of subobjects that are not isomorphic to any
dagger-subobject. One such example is in the category of integer
matrices (objects are arities, composition is matrix multiplication,
and dagger is transpose). The morphism (2) (as a 1x1-matrix) is monic,
but not isomorphic (as a subobject) to any isometries. However, it is
also not an equalizer. To get an example with equalizers, consider the
two morphisms f = (1,0) and g = (0,1) (as 1x2-matrices). Their
equalizer is the 2x1-matrix e = (1,1)^\dag. However, this is not
isomorphic to any isometry, and hence not to any dagger-equalizer.  So
in general, dagger-equalizers don't exist even if equalizers do.  (For
this example, it is important that the scalars are integers. If real
numbers were allowed, then e/sqrt{2} would be the dagger-equalizer.)

On the other hand, it is proved in [2] (Proposition 5.6) that under
some relatively mild condition, every subobject is isomorphic to a
dagger-subobject.

I hope this answers part of your question!

Let me close with some speculation: if e : E -> A is a monomorphism
such that (e^\dag).e is invertible, then it is probably relatively
easy to add a representative e' : E' -> A freely, and fully
faithfully, to the category such that e,e' are isomorphic (as
subobjects) and e' satisfies (*). [Clearly if (e^\dag).e is not
invertible, then this is never possible]. On the other hand, it is not
clear whether (e^\dag).e is invertible in general, or whether at least
this is the case when e is an equalizer.

-- Peter

[1] P. Selinger. Dagger compact closed categories and completely
positive maps. To appear in Proceedings of the 3rd International
Workshop on Quantum Programming Languages, Chicago, June 30 - July 1,
2005. ENTCS, 23 pages.
http://www.mathstat.dal.ca/~selinger/papers.html#dagger

[2] P. Selinger. Idempotents in dagger categories. To appear in
Proceedings of the 4th International Workshop on Quantum Programming
Languages, Oxford, July 17-19, 2006. ENTCS, 15 pages.
http://www.mathstat.dal.ca/~selinger/papers.html#idem

Equalisers and coequalisers in categories with a \dag-involution

[Jamie Vicary]

Dear all,

    Consider the following straightforward coequaliser (e,E) formed by
f,g:A-->B and e:B-->E, with e.f=e.g. I am working in a category with
biproducts, and with a contravariant involutive endofunctor (--)^\dag
on the category which is compatible with the biproducts; i.e.
                (projection)^\dag = injection
for all projections and injections making up a part of a biproduct. In
such a category, it is natural to consider the coequaliser object E to
be the subspace of B on which the morphisms f and g agree. It is
therefore natural to require e.(e^\dag) = id_E; this sort of condition
is similar to the sorts of conditions that form part of the definition
of the biproduct.

    I'm asking whether there exists a natural framework generalising
the theory of biproducts, which is analagous to the way that
(co)limits generalise (co)products, within which I can safely assume
that e.(e^\dag) = id_E. Biproducts seem quite different from products
and coproducts, though, so I don't know how it would work.

               Jamie Vicary.