Poset-valued sets or how to build models for linear logics.
We describe a method for constructing models of linear logic based on the category of sets and relations. The resulting categories are non-degenerate in general; in particular they are not compact closed nor do they have biproducts. The construction is simple, lifting the structure of a poset to the new category. The underlying poset thus controls the structure of this category, and different posets give rise to differently-flavoured models. As a result, this technique allows the construction of models for both, intuitionistic or classical linear logic as desired. A number of well-known models, for example coherence spaces and hypercoherences, are instances of this method.
Introduction
Models for (fragments of) Linear Logic can hardly be called scarce|we know
the categorical properties required, and a number of examples can be found
in the literature. So, why introduce more? In fact, we have been asked in
jest whether we would not consider naming this paper Yet another model for
Linear Logic.
The answer is twofold. For one we provide a tool for constructing models for
(fragments of) Linear Logic which gives precise control over such properties
as
classical versus intuitionistic, that is we can choose to have a negation satisfying
the usual equations, or not;
Preprint submitted to Elsevier Preprint 26 July 2000
products (&) and coproducts () coincide on objects, or not, and similarly
for their units;
tensor
. ) coincide on objects, or not, and similarly for their
units.
This is achieved by making specic choices for the two parameters in our
construction. It is very easy to do this to match a specied design.
From a category-theoretic point of view our construction starts with the compact
closed category of sets and relations and adds enough structure to ensure
that the resulting category (in general) is not compact closed, nor does it
have biproducts. Whether it is symmetric monoidal closed, -autonomous,
has products and coproducts depends on the second ingredient, a poset, and
its structure as a category.
Finally, a number of existing models for linear logic, such as Girard's coherence
spaces and phase spaces as well as Ehrhard's hypercoherences, are instances
of our construction. Thus we obtain new insight into how those models work,
and oer an explanation for the 'collapse' that occurs in those, for example.
Looking at models for (classical) linear logic one nds that many of them split
the world into a co-variant and a contra-variant part so that negation can be
obtained by exchanging the two. Examples for this are Player versus Opponent
in games 3 , the pair of sets for Chu spaces or dialectica, and morphisms
I - A versus those A - ? in the double glueing construction (see [8,7])
employed by Tan [11]. Structurally somewhat simpler models, on the other
hand, such as coherence spaces or hypercoherences, can do without this kind
of built-in duality|the negation of any object can be dened just via the
structure it carries 4 . Our models denitely belong to this second category. At
rst sight the construction may look similar to (a weak form of) glueing, but
the categorical structure arises dierently.
The paper is split into the following sections: First of all, we motivate our
construction by extracting it from some of the intended examples. We then
explore how the categorical structure arises discussing how to obtain models
for Linear Logic. We compile a list of examples for our construction which
arise in the literature and discuss an example which is genuinely new as a
model. Finally we consider remaining questions and future work.
3 Note that to obtain a model for classical linear logic here one has to move away
from the naive interpretations, see Abramsky and Jaghadeesan's work [1]
Coherence spaces at least can also be seen as an example of the 'two-worlds'
paradigm, see [7]
Why poset-valued sets?
Consider one of the best-known models for Linear Logic, namely coherence
spaces [4,6].
Recall that a coherence space X is given by a set jXj (its 'web'), and a re
exive
binary relation _ ^ on jXj. We use _ to denote the relation resulting from
removing the diagonal from _ ^ . Viewing this model from a dierent angle,
we encode this structure via a function  from jXj  jXj to the three element
ordered set 3 := f^< i <_g.
_
Fig. 1. The poset 3
We map hx; x 0 i in jXj  jXj to i and to _ i x _x 0 , giving
Further recall that a morphism of coherence spaces is given by a relation
satisfying the following condition: Suppose that x R y, x 0 R
In the above representation
of coherence spaces as maps from jXj jXj to 3, this is equivalent
to the condition:
The ordered set 3 can easily be seen to carry a -autonomous structure, which
in our chosen representation can be used to explain that same structure on the
category of coherence spaces: (We use  for the multiplication (or tensor) and
. for the linear function space in the posets to avoid overloading the notation
too much since this might lead to confusion later. The unit for  is i.)
.
Our new way of representing coherence spaces would, of course, not be of much
interest unless said representation also were to capture (at least some of) the
structure which makes this a model for Linear Logic. The main idea of this
paper is that said structure can be explained in terms of the corresponding
structure on the underlying poset 3, as well as that of the underlying category
of sets and relations Rel.
To start with, and as a motivation, we will take a look at negation. Clearly,
X ? is given by
3:
Now for the symmetric monoidal closed structure on the category of coherence
spaces. The tensor product of two coherence spaces X and Y ,
Y , has the
underlying set jXjjY j and its tensor product structure is dened by hx;
Given functions
and encoding the structure on X and Y we can express
this as a function
(jXj  jXj)  (jY j  jY
via hhx; yi; hx
Similarly the linear function space of X and Y , X -Y , has jXj  jY j as its
underlying set. In this case hx; yi _
Again this can easily be expressed as a function
(jXj  jXj)  (jY j  jY
via hhx; yi; hx
Thus the tensor of coherence spaces is obtained using the tensor product of
3 and the linear function space of coherence spaces is similarly obtained from
the linear function space in 3.
Consider a second example for a model of Linear Logic, namely that of hyper-
coherences [3]. Recall that a hypercoherence X is given by a set jXj (also called
the 'web'), and a subset (X) of the set of nite non empty subsets of jXj containing
all singletons. This can be encoded as a function
where P fne
denotes the (nite, non-empty) powerset functor: X maps a -
nite subset a of jXj to i i a is a singleton, and to _ i it is an element
of (X). Again this representation does capture the -autonomous structure
of the category of hypercoherences in terms of the corresponding operations
on 3:
negation is given in terms of negation on 3. The tensor product of
two hypercoherences has jXj jY j as its underlying web. The tensor structure
is given by
Y ), which is the set of all non-empty nite subsets E of
jY j such that  1 (E) is in (X) and  2 (E) is in (Y ). In our chosen
representation, we encode this structure by the function P fne
(jXj  jY
that maps a set c to X using the tensor product  of 3. The
linear function space of hypercoherences can be represented exactly the same
way, with the linear implication operator, ., replacing , the tensor product
on 3.
Morphisms of hypercoherences also t well into this representation. Recall
that a morphism of hypercoherences is a relation R
for every nite subset E of R, the following conditions are satised:
(ii) If  2 (E) is a singleton then  1 (E) is a singleton.
We take the nite powerset functor on the category of sets and relations Rel
to be dened on morphisms by a (P fne
i there is a (nite) subset E of R with  1 b. Then R
being a morphism of hypercoherences is equivalent to the condition a (P fne
implying X (a)   Y (b).
These observations suggest a pattern. As objects, we will consider functions
is a functor on the category of sets and relations, Rel,
A is a set and P is a poset which, as a category, is symmetric monoidal closed.
As morphisms we consider relations such that for a in FA, b in
FB, a implies (a)  (b).
To obtain a tensor-product on this category, we need a natural transformation
with components  A;B : F satisfying suitable properties
to make (AB;   ()   A;B ) the tensor of (A; ) and (B; ). Similarly,
we obtain a linear function space, and we will proceed to demonstrate that
the other connectives of Linear Logic can also be handled in this setting.
This construction turns out to be
exible enough to handle both Classical
and Intuitionistic Linear Logic. It also provides very good control over the
collapse of various connectives and their units. It suggests that the reason
that multiplicative constants coincide in the cases of coherence spaces and
hypercoherences, is the fact that they do so in the underlying poset 3. The
additive constants work slightly dierently.
3 Poset-valued sets
As suggested in the previous section, we want to build categories over Rel by
considering as objects sets which take values in a poset|in both the examples
in the previous section, that was 3.
All symbols referring to categorical constructs such as ,
and .
. are
meant to be interpreted in terms of the underlying category Rel (rather than
Set). Recall that products and co-products in Rel have the disjoint union
as underlying set, whereas tensor and par both are obtained via the cartesian
product, which also serves as the set underlying the linear function space (Rel
being compact closed, and every object being its own dual). To remind us of
the compact closure, we will use ( )  to denote the duality.
The traditional use of these symbols regarding our chosen motivating exam-
ples, coherence spaces and hypercoherences, is dierent|it appeals to the
category of sets and function. However, since the underlying category is really
Rel, it seems less confusing all in all to adopt a dierent meaning for the
various symbols. This has the advantage that the tensor in Rel will give rise
to the tensor in our category, et cetera.
There are two more ingredients from which we will build our category: Firstly,
we need an endofunctor on Rel to play the r^ole the diagonal for tensor and
the nite powerset functor played for the two motivating examples. Secondly,
we will need a poset P to take over the r^ole of 3. Any properties we demand
for P will be driven by the kind of structure we desire the resulting category
to have.
This approach has an odd tension between functions and relations. Since we
work in the category of sets and relations one might expect to deal with
relations exclusively. However, it turns out that our construction does not work
for relations in general. Also, when we view P as a category then we expect
its structure (multiplication and linear function space, inma (products) and
suprema (coproducts)) to be given by functions, too.
Since we are free to think of functions in the category of sets and relations we
can certainly use Rel as the underlying universe. It also is not unusual in category
theory to restrict some considerations to sub-collections of morphisms.
We will refer to relations which we know to be functions as 'functional', and
we will use the usual style arrow - to denote them, whereas maps that
may be relations will be denoted by
3.1
Having dealt with the preliminaries, we are now ready to formally introduce
the category we are interested in|the main idea was described in Section 2.
Denition 1 Let F be an endofunctor on Rel and let P be a poset. The
category of P F -sets, P F Set is dened as follows:
An object is a map FA ! P , a P F -set.
A morphism given by a relation
in P F Set are identity relations, and composition is also taken from
Rel. It is not di-cult to check that this denes a category. There is an obvious
forgetful functor to the category of sets and relations. To map Rel to
F Set, on the other hand, one has to map an object A to a constant function
Such a functor will not preserve the categorical structure unless P
is a singleton.
This is the reason for restricting ourselves to functions FA For the identity
relation on A to give a morphism
it has to be the case that if a  p and a  p 0 then p  p 0 since a id A a  p 0 ,
and thus by symmetry It would be possibly to allow partial functions
(rather than proper relations) here, but that does seem to lead to rather
unfamiliar categories overall.
An equivalent denition for the morphisms is given by the demand that such
a morphism R satisfy     FR were  is a pre-order dened on hom-sets
with co-domain P as follows:
For say that R  S i for all x 2 A and all
Hence in a situation where we have    FR,
that is a morphism R of P F -sets, we will use 'weakly commuting' diagrams
drawn as follows:
FA
This shows how to generalize this construction to categories C other than Rel:
What is needed here is an object P in C such that all hom-sets with co-domain
are order-enriched. However, for P F Set to have good categorical structure
it turns out that we use so much of the structure of Rel (the fact that it
is compact closed as well as the fact that A negated is naturally isomorphic
to that it does not seem worthwhile to give the most general version here.
We shall need a number of useful properties for this pre-order which are given
in the following lemma.
S  R  S 0  R.
only if  is less than or equal to
in the pointwise order for functions.
Having given the basic denition, we can now concentrate on the question of
when P F Set has good categorical structure.
3.2 Tensor products and symmetric monoidal closure
Let F be an endofunctor on Rel. Since Rel is compact closed, a natural
transformation F (
making F monoidal yields a natural
transformation going in the opposite direction. We say that a natural
transformation is functional if all its components are functions.
Proposition 3 Let monoidal and let F be a monoidal
functor with functional natural transformation  : F
Then P F Set is a symmetric monoidal category. The tensor of
F
The unit for tensor is given by ( i
is the composition of
the (only) function F I ! I and the function that picks the identity
for  in P . The forgetful functor P F Set ! Rel preserves the tensor strictly.
PROOF. The proof is simple; all the structure is inherited from Rel and P
via the following. Let R; R . If R  R 0 and
R
If one then goes on to ask for closure, one really starts making use of the fact
that Rel has rather special structure. In some ways we are spoiled for choice
here as for how to express it, since isomorphisms abound.
Here is the basic idea. Assume that the poset P is symmetric monoidal closed
as a category. This gives us a tensor product  on P as before as well as its
adjoint, say . Then we can use its structure to make P F Set a symmetric
monoidal category. There is a question of how to view P 's structure as it
embeds into Rel. If we view . as a relation
dene the
linear function space of
F
This looks nice and tidy, but in order to argue that this makes P F Set symmetric
monoidal closed we have to use the fact that Rel is compact closed
and that every object is isomorphic to its dual.
On the other hand, we can try to dene the same linear function space as
F
using the same properties. Finally, one might be tempted to instead view .
as a relation P
but that then requires us to view  as going from
to P  , ultimately making the same assumptions.
Proposition 4 If P is symmetric monoidal closed and F satises the conditions
from Proposition 3 then the category P F Set is symmetric monoidal
closed. The forgetful functor P F Set ! Rel preserves the structure strictly.
PROOF. No matter which formulation one ultimately chooses, this is a
simple consequence of Rel being compact closed and P being symmetric
monoidal closed. Again we have a useful fact making the connections for
us. Let R; R
.
R
S  .  RS 0 . 2
Note that although the base category Rel is compact closed, P F Set will not
be degenerate (in general): all that is required is that P not be compact closed
(as a category).
Remark 5 Attempts to generalize this to non-compact categories fail for the
following reason: The obvious underlying objects for tensor and linear functions
space are
A
B and A -B, respectively. This requires the existence of
natural transformations
F
In the general case, the existence of the one does not imply that of the other|
but the latter implies the existence of a natural transformation
Adding a couple of innocent conditions linking these transformations with the
symmetric monoidal closed structure on the underlying category to make the
proposed adjunction work result in the demand that F
B) be isomorphic
to F
F (B) which seems to be too restrictive to be useful.
3.3 Negation and -autonomous structure
Assume P has a negation, that is an order-reversing function (
This allows us to dene a duality on P F Set as
Note that this removes the collapse that occurs in Rel|there an object
and its dual are isomorphic, whereas here this only occurs if P is a singleton.
For morphisms, we make use of the duality on Rel|the involution on P
ensures that the dual of a morphism of P F -sets is another such.
Such a negation is not of much interest in isolation, and the desired connection
is created by the following proposition.
Proposition 6 If P is -autonomous and F satises the conditions from
Proposition 3 then the category P F Set is -autonomous. The forgetful functor
Rel preserves the structure strictly.
PROOF. Again this is a simple consequence of the structure on Rel together
with the fact that P is -autonomous. 2
3.4 Products and co-products
The next question we wish to answer is that of what it takes for P F Set to have
at least some limits and co-limits. Let us have a look at co-products rst. We
have a candidate for the underlying set of
namely A + B, and candidates for the embeddings, namely inl and inr from
Rel. It remains to determine the structure, that is a function F
that will give us the desired universal property.
For that, we will make use of the fact that there are many 'weakly universal'
objects in P F Set in the following sense:
Lemma 7 'Fill-in property': Let P be a complete lattice, let R
-set. Then there is a P F -set  based on
B such that
(i) The relation R is a morphism
sets, that is the following diagram commutes weakly:
FA
(ii) such that S  R is a morphism from
is a morphisms from
that is the weak commutativity of
FA
implies that of
(iii) The function  is uniquely dened by (i) and (ii).
PROOF. Let (b) := W
a(FR)b (a). Obviously, this makes R
morphism of P F -sets To see that those
two conditions determine  uniquely, use (ii) applied to the identity, which
proves that any two functions satisfying (i) and (ii) have to be equal. 2
We will apply this to get the universal property wanted for co-products. Consider
the following diagrams:
FA
F
F
The desired co-product is then given by (' l _
structure is the pointwise join of those two functions. Obviously, products can
be obtained via the dual of this process. Also, note that we don't make use of
the fact that this is a nite co-limit at all.
Proposition 8 If P is a complete lattice then any category of P F -sets has all
products and co-products.
PROOF. We will just prove that (' l _
above has the necessary universal property for co-products|it is obvious how
to extend this to innite co-products. The proof for products works dually.
What we really need to show is that if R and S are morphisms of P F -sets, then
the same is true for [R; S] which we know exists in Rel (and thus satises the
desired equations and uniqueness condition).
Suppose that we have morphisms R
By the denition of ' l , this implies ' l
F [R; S], and analogously we can
prove that ' r
Hence we obtain ' l _ ' r
The empty co-product is the empty set, the structure is the function mapping
every element of F; to the least element of P . If F; is empty then the structure
map is the empty function. 2
Note that even if we are only asking for nite products and co-products, P will
have to be complete, unless we restrict ourselves to a constructive universe of
sorts:
If we only allow nitary relations as morphisms, that is ones R
such that for all a 2 A, the set of all b 2 B that are R-related to a is nite,
and such that for all b 2 B, the number of elements of A which are R-related
to b is nite as well. If F restricts and co-restricts to the resulting category,
then we can use that subcategory of Rel, and under those circumstances,
the existence of nite joins and nite meets in P is su-cient to obtain nite
products and co-products in P F Set, respectively. Or, alternatively, if F is such
that for each c in some F (A+B), the number of elements related to c by F inl
or F inr is nite, then nite suprema are su-cient to guarantee the existence
of nite coproducts, and the dual statement is true for products.
Products and coproducts will in general not coincide unless P is a singleton.
An obvious exception to this is choosing F to be the identity functor on Rel,
in which case binary products coincide with binary coproducts. (However,
terminal and nal object will be dierent.)
Comonads, comonoids, and linear exponentials
Since ultimately we want to demonstrate how we can combine all the structures
we talked about so far to obtain a model for Linear Logic, we will also
have to concern ourselves with comonads and comonoids which are used to
model linear exponentials.
We wish to use the notion given in some detail in [2]; see it for a comparison
with other denitions. If a symmetric monoidal category has a monoidal
comonad satisfying the conditions given in [2] then we say that it has a linear
exponential comonad. Assume we have a monoidal monad on Rel whose
carry a commutative monoid structure. This
could be, for example, the free commutative monoid, or the nite powerset
monad. If we turn around the direction of all the morphisms which form such
a structure, we obtain a monoidal comonad (!;
m) where all free algebras
are commutative comonoids via natural transformations with components
!A and e A : !A ! I. We will abuse notation and refer to the
desired monoidal comonad on P F Set again as (!; ; -; m I
m).
Since talking about comonoids in this setting only makes sense if P F Set has a
tensor product, we will assume for the remainder of this section that P is, in
fact, a monoid, and that F satises the conditions which ensure that P F Set
is a symmetric monoidal category as per Proposition 3.
The underlying set of !( is to be !A, but it will be a bit more
troublesome to obtain a suitable structure on that set. The idea, however,
is simple: Since morphisms of P F -sets are given by relations, we can re-use
the comonad on Rel, including the comonoidal structure on the algebras, as
long as we can ensure that they satisfy the condition for such morphisms.
Therefore, the problem can be reduced to dening a suitable structure on
This gives us seven 'universal' inequalities we want to hold, one each for ,
, m, d, e, and morphisms of the type !R. Given the generality of this
approach (after all, F is just an arbitrary endofunctor on Rel), we cannot
expect a constructive denition of the desired structure F !A ! P . It is rather
surprising that we can get away without putting any restrictions on so general
a situation.
The main idea for tackling this problem is to view !A as a comonoid cogenerated
by A in some sense. This suggests that three of the seven inequalities
mentioned above are more central than the remaining one.
Denition 9 A !-candidate for
that satises the following inequalities:
F !A
F I
FA
F !A
F
(!A
F !A
In other words, a !-candidate t for
comonoid 'co-generated' by Among all the !-candidates there
is a canonical one that will yield the desired object, namely the (pointwise)
join of all !-candidates|if it exists. To ensure that, we assume from now on
that P has all joins, that is is a complete lattice.
It should be noted that for certain F and !, this condition can be relaxed
to just demanding the existence of nite joins and nite meets in P as long
as everything takes place in a 'nitary' category as described in the section
about products and co-products. In that case, which is more in the constructive
spirit, it is possible to give a constructive denition for the largest !-candidate
(that is without quantifying over all !-candidates).
Let us begin the proof that P F Set has the desired comonad by noting that
this will indeed give us another !-candidate, namely the largest one:
Proposition 10 The pointwise join of all !-candidates for a P F -set is another
such.
There is one Lemma we have to present before we can tackle the Theorem we
are looking for; it explains how to obtain !-candidates for the tensor-product
of two P F -sets.
Lemma 11 If t and u are !-candidates for the P F -sets
respectively, then the function obtained via the ll-in property
(Lemma 7) from the following diagram is a !-candidate for
A
F
(!A
F !B
F
PROOF. We have to prove that the arrow obtained from the ll-in property,
behaves well with respect to e, , and d. To do that, we will make extensive
use of property (ii) from Lemma 7. Basically, what we will do is prove the
commutativity of the 'outer' diagram from which the desired inequality will
follow as the lower sub-diagram.
The weak commutativity of the following diagrams is fairly straight-forward,
although the last one uses some coherence properties (the morphism indicated
by
A
A
A
F
(!A
F !B
F
F
A
I;I
I
F I
A
F I
F I
F
(!A
F !B
F
F
A
F
A
FA
A
F
(!A
F
F !B
F
F (d
A
F (mA;B
FdA
F
(!A
F
FdA
(!A
F
!B;!B
-Proposition 12 If P is symmetric monoidal and a complete lattice then any
linear exponential comonad on Rel gives a linear exponential comonad on
PROOF. All that remains to be shown is that the join of all !-candidates for
any P F -set the seven desired inequalities. The ones
for e,  and d are dealt with in Proposition 10, which leaves us with four
inequalities to take care of.
Let us start with m I
. To prove that this relation is a morphism of P F -sets
we have to prove that  i
is less than or equal to Fm I
followed by the largest
!-candidate for ( i
be the function dened via the ll-in
property (Lemma 7) in the following diagram:
F I
F !I
I
We can prove that  0 is a !-candidate and therefore we obtain  i
and by inserting the largest !-candidate for ( i
get the desired
inequality.
To do so, we keep making use of the part (ii) of Lemma 7|in fact, we'll
only state the commutativity of the 'outer' diagram since the conclusion is
obvious from there|the same method was employed in the proof of Lemma 11.
To show that  0 is indeed a !-candidate, the commutativity of the following
diagrams is thus su-cient:
F I
F !I
Fm I
F I
id F I
Fe I
F I
F !I
Fm I
F I
id F I
F !I
F
I
F I
F
(!I
I
I
!I;!I
Fd I
F
!I
F !I
I
Fm I
All sub-diagrams above commute (weakly) for fairly obvious reasons.
The natural transformation m is being taken care of in a Lemma 11, so we
can move on to -. Again, we will make use of Lemma 7. Let
be a !-candidate for be the ll-in from
the following diagram:
F !A
F !!A
We prove (with similar techniques as employed above) that u is a !-candidate
Applied to denotes the largest
!-candidate for then results in a !-candidate u for the P F -
set which implies the desired inequality
which has the largest !-candidate for in the place of u.
To see why two of the following diagrams commute weakly, note that - A is a
morphism of free !-co-algebras (in Rel) (!A; - (!!A; - !A ) and therefore a
morphism of comonoids.
F !A
F !!A
F I
F !!A
F !A
id A
F !A
F !!A
F
(!A
F !A
F
(!!A
A
!!A;!!A
Fd !A -
F
F !!A
A
This leaves us with one last thing to show, namely that !R is a morphism if
we impose the structure on that we propose. For that, it is
su-cient to prove that if t is a !-candidate for then the map
obtained from the following diagram via the ll-in property is a !-candidate
F !A
F !B
Again, that leave us with three diagrams to prove weakly commutative. We
will use the fact that, as a morphism of free co-algebras, !R is a morphism of
comonoids.
F !A
F !B
F I
F !A
F !B
FA
F !A
F !B
F
(!A
F !A
F
(!R
!B;!B
F
F !B
F !R
-3.6 Putting it all together|models for Linear Logic
We use here the following terminology.
Denition 13 A categorical model of Intuitionistic Linear Logic consists of
a category which
is symmetric monoidal closed;
has nite products;
is equipped with a linear exponential comonad.
To model the classical calculus we additionally require a strong duality. So a
model for Classical Linear Logic consists of a category which
is -autonomous;
has nite products and (so) nite coproducts;
is equipped with a linear exponential comonad and (so) a linear exponential
monad.
Summarizing all the results we have the following.
Theorem 14 If P is -autonomous as well as a complete lattice then P F Set
is a model for Classical Linear Logic. In addition, it has arbitrary products
and coproducts.
If P is symmetric monoidal closed as well as a complete lattice then P F Set is
a model for Intuitionistic Linear Logic. In addition, it has arbitrary products
and coproducts.
Unlike Rel, our category P F Set will in general not suer collapse and thus
result in a degenerate model. P F Set will be compact closed only if P is. The
units for tensor and par will be dierent as long as they are in P . It will not
have biproducts unless P is a singleton, or F trivial. The initial and terminal
objects coincide if P is a singleton or if F maps the empty set to itself.
Note that if the general aim is to model larger fragments of Intuitionistic
Linear Logic, the construction presented here is capable of coping with that
as well.
4 Examples for poset-valued sets
4.1 Phase spaces and completeness
Let us consider what categories we obtain if we take away some of the degrees
of freedom we have with P F -sets. First of all, there is the possibility of F being
a constant functor, mapping everything to a one element set. In that case, the
structure map  picks out an element of P , and the operations are as dened
on P|apart from !, obviously, which is a derived operation, and in that case
Proposition 12 tells us how to dene a modality for P .
One particular example of this would be that of phase spaces: Recall that a
phase space M consists of a commutative monoid and a subset ? of M . For
subsets X of M , negation is dened via
In that case, let P := fX  M j
'facts'. They form a complete lattice with respect to  since facts are closed
under arbitrary intersection. The tensor is given via
We will not repeat here how the other connectives are dened.
It seems, however, interesting to point out how the exponentials Girard gives
compare to the ones obtained from our technique. There are, in fact, more
than just one interpretation for ! to be found in the literature, but we are
interested in the one described in [4], where
is the unit
for
, where 1 is the unit of the monoid M .
Our denition, on the other hand, makes ! the largest function
satisfying t(X)  I, t(X)  X and t(X)
t(X). (Note that due to
the nature of F , it does not matter with which denition of ! on Rel we start.)
Obviously, Girard's denition satises the rst two of those inequalities, but
not the third. However, if a formula  is provable in Linear Logic, then 1 is an
element of its interpretation (no matter which phase space we are looking at),
and for facts X containing 1, the desired inequality is true. Hence, whereas
we make sure that !X
!X is true for all elements of P , Girard restricts
himself to those elements which can possibly be interpretations of formulae.
Thus he obtains a nice explicit denition for ! which, however, has a bit of an
ad hoc nature. We obtain the somewhat less appealing formula
The above discussion also answers the question whether our semantics is com-
plete, since phase spaces are known to be.
Another model of a similar nature which we can view as a category of P F -sets
are Mitchell's IE-quantales [10]|they also t the case where F is a constant
functor of the kind described above.
The other possibility for obtaining a degenerate model is to have P be a
singleton. In the case where F is the identity, this will give us the category of
sets and relations with the usual connectives (and collapses, of course), and
with whatever denition of ! we start.
4.2 Coherence spaces and hypercoherences revisited
As we have seen in Section 2, coherence spaces can be encoded as P F -sets, by
choosing P to be 3, and F to be the diagonal functor  for the tensor product
on Rel. If we denote with G the functor we obtain from mapping a coherent
space to the corresponding 3 -set, we get the following result:
Proposition 15 The functor G is full and faithful and preserves the monoidal
closed structure on the category of coherence spaces as well as products and
co-products.
The image of the embedding G consists of all 3 -sets whose structure map
takes the value 1 exactly on the diagonal.
As some minor calculations show, the modalities we obtain for 3 -sets if we
take ! to be the nite powerset functor on Rel correspond to the ones described
in [4]. To obtain the ones from [5] we have to adjust our denition of !, for
the construction we introduced in the last section has one major fault: The
underlying set for !(A; ) is always !A, ie  cannot be used to determine a
subset of !A to use instead, the way it is done in the usual version of the
modalities for coherence spaces. However, we can provide for that to some
degree:
Under the assumptions of Theorem 14, let there be a subset !  A of !A for
every Further assume that the restrictions and co-restrictions of the
linear structure on rels to these subsets, and the equations between those are
still valid. If F preserves inclusion of relations, then this results in another
linear category. We will not go into the details of the proof here|basically,
it consists on showing that the notion of !-candidate can be adapted to those
circumstances.
The other example we looked at in Section 2 was that of hypercoherences. To
encode those, we chose
, the nite powerset functor on
Rel.
By dening the resulting functor on morphisms the same way we dened
above, we again obtain a full and faithful embedding that preserves the
monoidal closed structure. Its image in the category of 3 P fne
-sets is given by
those (X; X ) which take the value 1 if and only if the argument is a singleton.
However, the image of that embedding is not closed under products and co-products
(the property of the structure taking the value 1 exactly on singletons
is not preserved under these constructions). The modalities, however, can be
expressed in the category of 3 P fne
-sets as described for coherence spaces.
4.3 Lamarche's Q n
A -coherences
Lamarche's attempt to nd a generalization of models for Linear Logic such
as hypercoherences and coherence spaces led him to the introduction of what
he calls Q n
A -coherences [9], where Q is a -autonomous poset. These can be
viewed as Q P n
-sets, where P n is a powerset functor which only considers sets
up to cardinality n. (The additional parameter A species a subset of Q which
is used to 'mark' the singleton sets.) Any category of Q n
A -coherences can be
embedded into the category of Q -sets, and this embedding preserves all
multiplicative and additive connectives as well as being full and faithful.
4.4 New models
Let us assume that we want to build a model for (Classical) Linear Logic such
that the units for tensor and par do not coincide. Other than that we would
like to keep it simple, say in the spirit of coherence spaces. The framework
developed in this paper tells us that this can be achieved as long as (unlike
in the three-element poset 3) the two constants i (the unit for multiplication)
? have dierent interpretations in the underlying poset model. This
suggests using a binary relation with values in 4 given below:
_
Fig. 2. The poset 4
Objects in our category will be functions
A
4, where A is an object
in Rel. Morphisms are relations R such that a R b and a 0 R b 0
implies that 'b and b 0 are at least as related as a and a 0 , in other words,
The poset 4 is equipped with the obvious negation given in the table below,
so the negation of  :
A
assigns the 'opposite' value to a pair ha; a 0 i.
Similar to our treatment of coherence spaces, we use the following abbreviations

a
a a 0 i ha; a
a # a
a _ a
The relation on the tensor of two objects is given by 5
none of the above:
This is justied by the -autonomous structure on 4 given by:
Note that it does not make sense to read ha; a which is what
happens for coherence spaces, since the rules for tensor do not t with that
interpretation. The unit for tensor is the singleton set whose one element is
-related with itself, whereas the unit for par is the singleton set whose one
element is #-related with itself.
Product and co-product are formed in a way similar to coherence spaces: The
underlying set of the product of  B, the
5 At rst sight the denition of tensor looks rather odd. Here is an example where
one would expect this kind of behaviour: Assume that the elements of A are products
of intervals in some R N . We might then be interested in whether two such intervals
have empty intersection (are ^-related), are equal (are -related), have a union
which is a product of intervals, but are not equal (are #-related), or for which none
of these hold (are _-related). Then there is an obvious way to dene the tensor of
two such objects: To nd how ha; bi is related with ha study the products a  b
and a 0  b 0 . This evaluates to the tensor given above.
disjoint union of A and B. Then
_ otherwise
Co-products work similarly, only in the last case, the value of
Note that the unit for product coincides with that for co-product since the
underlying set is empty and the tensor product of the empty set with itself is
again the empty set, allowing only one choice for a function to 4. If we wanted
to separate those we would have to use another functor (rather
than
who maps the empty set to a non-empty set. The nite powerset functor is an
option here, giving a model similar to hypercoherences. We will not spell out
a description of the exponentials for these specic models here.
5 Conclusions and Future Work
The way of constructing models of Linear Logic as described above seems suitable
for interested parties to 'create their own', using the building blocks of
their choice and then following the given instructions. Such models do not have
to be much more complicated than hypercoherences or coherence spaces. Section
4.4 gives an example for how one might employ the techniques described
here to obtained a model with specied properties.
There is the question whether other models which are mainly 'one-sided' (in
that the dual is given internally rather than by a priori making every object a
pair, so that the dual can be taken by switching components) can be considered
within this framework, like event structures, join-complete semilattices,
and other domain theoretic models. One possible obstacle is that in the domain
theoretic case, morphisms will in general not be relations of some kind,
but there is plenty of work in that eld suggesting that they can be understood
as such as long as the domains considered satisfy some 'niteness' or
'approximability' condition. Similar considerations apply to event structures.
Our techniques are not designed to cope with what we call 'two-sided' models
such as games, Chu-spaces, dialectica and others.
Another thrust for future work would be to nd a categorical setting in which
this kind of construction could live rather than restrict everything to the
category of sets and relations. Our proof does make use of the fact that the
base category is compact closed, and we cannot see a way of generalizing this
method to, say, -autonomous or symmetric monoidal closed categories.
We would like to thank Martin Hyland for numerous discussions on the subject
of this paper. The referees made useful suggestions regarding additions to the
original draft. Thanks also to Paul Taylor for the use of his diagrams package.
This work was supported by an EU HCM individual fellowship and EPSRC
grant GR/L27848.



--R

Games and full completeness for multiplicative linear logic.
What is a categorical model of intuitionistic linear logic?
Hypercoherences: a strongly stable model of linear logic.
Linear logic: its syntax and semantics.
Linear logic.
Proofs and Types
Glueing and orthogonality for models of linear logic.
Abstract games for linear logic.

The carcinogenic example.
Full completeness for models of linear logic.
--TR
Linear logic
Proofs and types
Games and full completeness for multiplicative linear logic
Linear logic
What is a Categorical Model of Intuitionistic Linear Logic?
Glueing and orthogonality for models of linear logic
categorical models;linear logic