Subject: categories: Re: quantum quandaries - a category-theoretic perspective

From: Vaughan Pratt <[email-masked]>
Date: Thu, 8 Apr 2004 17:08:14 -0700

Good morning -- very, what with not just one but two very interesting
papers, from Tom Leinster and John Baez.

The following from John's abstract got my immediate attention:

>We argue that these features only seem puzzling when we try to treat Hilb
>as analogous to Set rather than nCob, so that quantum theory will make more
>sense when regarded as part of a theory of spacetime.

This calls for an immediate response.  I've argued elsewhere (perhaps not
sufficiently forcefully?) that Set is _very_ analogous to Hilb, _as part
of a *-category_.

The easily made mistake with Set is to view it as an autonomous category
in its own right (ok, so that's not a mistake in many contexts, but it is
when proposing to incorporate Set into a Theory of Everything).

A much better view is Girard's (which he applies to logic, but logic is, or
should be, a reflection of reality).  Girard starts out with a *-autonomous
universe (of propositions if doing logic, of objects if doing mathematics).
He obtains comonoids (intuitionistic logic if doing logic, sets or related
objects forming a CCC if doing mathematics) by finding them in a smaller
cartesian closed retract of the big universe, via bang, of-course.  (One can
in fact have a hierarchy of bangs, with the bigger bangs delivering dyadic,
..., n-adic comonoids and the smaller ones delivering posets, sets, finite
sets, finite sets of even cardinality, etc.)

This view of intuitionistic logic as a fragment of the bigger linear logic,
and of comonoid objects such as sets as a fragment of a bigger mathematical
universe, has the following benefits.

1.  It locates signature in the object.

Traditionally signature is determined by context.  Typical contexts are a
theory such as the theories of groups, vector spaces, Boolean algebras, etc.,
or a category such as the categories of any of these.  The signature thus
resides not in the objects but in the theories or categories of those objects.

Instead I propose to view all structure of an object, including its
signature, as an intrinsic property of that object independently of what
signature and structure other objects in the same universe might have.
This then permits dispensing with either theories or categories, at least
in their role as specifiers of either signature or structure.

To this end, organize each object A as a set of subjects, a set of predicates,
and an inference rule for taking A out of the loop in order to get straight
to the truth about the structure of A.  The only context needed is a tensor
unit I and its dual \Omega.

  Subjects: the arrows I->A
  Predicates: the arrows A->\Omega
  Rule: The compositions I->\Omega that bypass A, taking it out of the loop

This is a way of looking at Chu(Set,\Omega).  A Chu space (A,r,X) is a set
A of subjects, a set X of predicates, and a rule r:AxX -> \Omega giving the
value r(a,x) of predicate x at subject a directly.  A Chu space has no
other signature or structure.

The Chu construction embeds any autonomous category V with pullbacks
autonomously into the *-autonomous category Chu(V,k), via an arbitrary
selection of object k of V.  Chu(Set,\Omega) embeds Set autonomously---no
need to abandon the autonomous structure on Set, and it is located in the
broader context of a universe whose properties can be considered "puzzling
features" in John's sense.

While this simple representation might not seem capable of accommodating
much structure, an impressively wide variety of structures for objects
are achievable with it.  For example, the structure of a Hilbert space,
as Lafont and Streicher point out, is representable as a Chu space simpy by
taking \Omega to be the set of complex numbers, without committing \Omega
to any particular properties of or operations on the complex numbers,
simply taking it to be a pure set.  (Actually L&S only embed Vct, but
Hilb is easily embedded as well simply by disallowing a few predicates in
their Vct embedding; also they don't actually say "Chu" and "*-autonomous,"
but they could have.)

Chu(Set,\Omega) embeds Set autonomously into the same *-autonomous universe
that also embeds Hilb.  Any difference between sets and Hilbert spaces is
internal to those objects, as opposed to being determined by context as
done traditionally.

2.  It furnishes a strikingly simple explanation for the "puzzling features"
John alludes to.

Once the place of Set in the grander scheme of things is seen, these "puzzling
features" that are traditionally accounted for in terms of Hilbert spaces
can really be seen as having a more fundamental origin: structure.

(As a slight digression on whether it is fair to characterize sets as
really being devoid of structure, certainly their *elements* are discretely
organized, but their *predicates* are highly organized.  The discreteness is
really a result of emphasizing the elements over the predicates; the same
object viewed from the dual perspective interchanging these is heavily
structured!)

Granted Hilbert spaces give rise to puzzling features, but complete
semilattices give rise to essentially the same puzzling features.  It is
not Hilbert spaces or complete semilattices that are doing this, it is the
much broader notion that *structure* is doing this.  Hilbert spaces are
just structured objects; so are complete semilattices; so are sets.

My views on the role of structure in creating the strangeness of quantum
mechanics appeared in an early form in 1992 in "Linear Logic for Generalized
Quantum Mechanics," without Chu spaces however, available as

  http://boole.stanford.edu/pub/ql.pdf

>From the abstract: "In this extension [of quantum reasoning] the uncertainty
tradeoff [of complementary or dual quantities] emerges via the structure
veil."  The paper argues that the basis for Heisenberg uncertainty is the
structure veil as an unavoidable phenomenon on one side of the duality or
the other attributable to Stone duality, not just qualitatively but even
quantitatively to some extent.

Shortly thereafter I realized that Chu spaces was the perfect framework for
these ideas, and described the idea at the 1992 Cosener's House (Abingdon)
meeting on domain theory and games, where I characterized Chu(Set,K) as
"A Theory of Everything dual to a Model of Everything."  Subsequent papers
further developed the theme, e.g. "Rational Mechanics and Natural Mathematics"
(TEMPUS'94 notes), "Chu Spaces: Automata with Quantum Aspects" (PhysComp'94),
and "The Stone Gamut" (LICS'95).  In these more recent papers I tightened
up the quantitative aspect of structural uncertainty result by furnishing
every Chu space with its own "Planck's constant" defined as the reciprocal
of the area of the Chu space, which works beautifully!

I've largely neglected this QM relationship lately, partly due to competing
interests, but also from a sense that, for whatever reason, the idea
simply was not taking hold.  Something was wrong: the idea, the audience,
the timing, the exposition, ...  I knew neither what to fix nor how fix it.
If I ever find out I'll certainly be more than happy to write further on the
notion of quantum mechanics as the reflection in nature of pure structure,
as opposed to the conventional wisdom that ties it to specific structures
such as Hilbert space.

If anyone would like to argue against this, i.e. that pure structure is *not*
a good basis for quantum mechanics, the title "A Critique of Pure Structure"
has been taken only in the context of "The Limits of Rationality and Culture
in the Transition from Feudalism to Capitalism."

Anyway, on to point 3:

3.  It saves mathematics from Cantor's paradise.

In the *-autonomous view of Set as part of something bigger, a set A has
not just elements but also predicates.  Whereas the elements are structured
discretely, the predicates are structured logically, e.g. as a Boolean
algebra.  Forming the power set of A as \Omega^A or A-o\Omega means not
the production of an exponentially larger set, but instead the swapping
of the elements and predicates of A.  It is natural to want to repeat this
as \Omega^\Omega^A or (A-o\Omega)-o\Omega, but (as I mentioned in a post a
couple of weeks ago), as long as one remembers that power sets are heavily
structured then one simply recovers the original set A after the second swap.
"Doubly exponential" then has its involutory connotation as in logic rather
than its hugeness connotation as in set theory or combinatorics.

We all want to go to paradise eventually, some just sooner than others.
Combinatorialists and others sometimes want these huge numbers now.  This is
accomplished with bang.  Replacing the Boolean algebra B having 2^n elements
and n predicates (aka ultrafilters) with !B leaves the elements unchanged
while greatly increasing the number of predicates from n to 2^2^n, a double
whammy right there with one bang!  (This assumes \Omega=2 and Set bang;
other choices of \Omega and bang will give different cardinalities but the
general idea remains the same.)

One should measure combinatorial growth neither by the number of iterations
of exponentiation (which is an involution), nor by the number of bangs (which
is idempotent at least for little chu), but by the number of *alternations*
of exponentiation and bang.

Apropos of the "hierarchy of bangs" mentioned above, I'll be talking next
month in X'ian about using comonoids to generalize CPOs so that they work
more like logic.  CPOs are designed for the passage from A to A-and-B,
whereas logic caters not only for that passage but also the other direction,
from A to A-or-B.  The CCC of comonoids addresses both directions, and
moreover symmetrically.

I would *love* to know whether all T1 comonoids are discrete.  This question
applied to the special case of DCPOs is positively answered as an obvious
consequence of how one topologizes DCPOs, and the same holds for Lamarche's
larger CCC of "casuistries."  Neither of these enjoys the above-mentioned
up-down symmetry of logic however.  For the yet larger CCC of comonoids,
where this symmetry kicks in, the question seems to be dauntingly difficult,
and I've been posing it to people for eight years.  A year ago I decided
it was high time to offer some sort of bounty on the problem, currently at
$2,000, see http://thue.stanford.edu/puzzle.html for more details.

Vaughan Pratt

---

From: Paul B Levy <[email-masked]>
Date: Fri, 9 Apr 2004 11:56:18 +0100 (BST)

Hi Vaughan,

> This view of intuitionistic logic as a fragment of the bigger linear logic,

is widely held but I don't agree with it.

A model of (propositional) intuitionistic logic is a bicartesian closed
category.  (I'm assuming we want to model proofs, not just provability.)

But a model of linear logic doesn't, as far as I'm aware, give rise to a
bicartesian closed category.

So there's no translation (at the level of proofs, rather than
provability) from intuitionistic logic to linear logic.

Paul