An observation on support and freshness in nominal sets (Technical report)
There are two natural ways of excluding an atom a in nominal techniques: we can either consider the sets X such that a is fresh for X, or we can consider the sets X such that a is fresh for every x X.
The statements of ‘being fresh for all the elements of that set’ and ‘being fresh for a set’ are not the same: it is not the case that x Xa#x if and only if a#X.
Both notions encode natural notions of ‘fresh a’. In this paper, it is proved that these notions lead naturally to two categories that are isomorphic, so that in a suitable generalised sense they are the same.
The result is mathematically attractive and has an interesting reading: it is equivalent to add a fresh atom to the underlying universe, and to add a symbol to the meta-language referencing a fresh atom. Or to put it slightly differently: we prove the intuitively appealing but non-obvious fact that a fresh atom in the object-level is categorically isomorphic to a fresh atom in the meta-level.
May 18, 2010 c Gabbay
1 Introduction
1.1 A little background on nominal semantics
Nominal techniques were introduced in [14]. With Pitts, we considered the problem of giving semantics to inductive definitions with binding. We did this by considering inductively defined datatypes in Fraenkel-Mostowski set theory (FM sets).
FM sets was developed to prove the independence of the Axiom of Choice [2]. It is not obvious that a representation of binding is to be found in a set theory from the earlier half of the 20th century, but it is. This semantics is now used directly or through various logical and operational presentations such as nominal logic, FreshML, or the nominal datatypes package. See Mulligan’s online bibliography [21].
Nominal techniques give variable symbols a denotational reality as atoms, or urelemente. If the reader is familiar with nominal logic [23], FreshML [26], or the nominal datatypes package in Isabelle [28], they will recognise this idea in the datatype of atoms , used to represent variable symbols. Atoms are data.
The specific mathematical content here is in the fact that in FM sets and the systems which were then derived from it, this ‘datatype of atoms’ displays some striking behaviour which is a good semantic model of names and binding. This behaviour is distinctive and distinguishes nominal techniques from models of variable symbols based on functions [22], numbers [5], or links [1, Section 1].
Much of the content of FM sets is shared with work using presheaves [8]. The extra benefit of using FM sets is its sets-based presentation, which enjoys a unique notion of support.1
1.2 The support of a set X is not the support of its elements x X
In FM sets, every element has a notion of support, supp(x) (full definitions will follow). This generalises the syntactic notion of ‘free variable symbols of’. In the case that the set represents an abstract syntax tree, support and ‘free variable symbols of’ can be made to coincide in a natural way.
However, the support of X does not coincide with ‘atoms in the transitive closure of X’, nor with ‘union of the supports of all x X’.2
In my own experience, it is hard for people to see how a set that ‘contains a’ might not contain a in its support. There are strong intuitions that a X should imply a supp(X), and that a x for all x X should imply a supp(X).
This will be very familiar to some readers, and perhaps less so to others. Here are two illustrative examples:
supp( but the atoms in the transitive closure of is . Also supp(x) x .
a is ‘in’ the set of all atoms, but because so is every other atom, it is not in the support of the set of all atoms.
Also, supp(aa but the atoms in the transitive closure of a and supp(x) x a are both equal to a. a is ‘not in’ the set of all atoms minus a, but since it thus distinguishes itself by this absence, it is in the support of the set of all atoms minus a.
The behaviour illustrated above is important: the correctness of the self-duality of the -quantifier, of atoms-abstraction, and the nominal model of abstract-syntax-with-binding, intimately depend on this.
As standard, write a#x for a supp(x). The fact is that it is not the case that a#X if and only if x Xa#x. This is why we not only do not, but can not define supp by induction on sets (whereas ‘free variables of’ is and must be defined by induction). Thinking of X as a predicate and x X as a datum, and using a bit of nominal jargon, this is related to the fact that in nominal semantics equivariant functions and predicates can and do act on non-equivariant data.
1.3 The main results
In this paper, I will use a little bit of category theory and some elementary sets constructions to exhibit a sense in which natural generalisations of ‘support of X’ and ‘support of all x X’ — are equivalent.
For the reader already familiar with nominal techniques I will now briefly sketch the main definition and two results of this paper; full details will follow.
Write FMSet for the category with objects FM sets and arrows function(-sets) between them (see Definition 3.2 for the precise definition).
Our first main result is Theorem 3.3. This presents the strongest positive and direct connection I know of in general, between the support of X in FMSet and the support of x X.
To state the next result we need just a little notation.
Fix some atom a and define two new categories using FMSet:
Define a category FMSet#a by:
– Objects are elements X of FMSet such that xXa#x.
– Arrows are the full set of arrows f : X Y FMSet.
Define a category by:
– Objects are elements X of FMSet such that a#X.
– Arrows are arrows f : X Y FMSet such that a# f .
FMSet#a and both implement notions of ‘exclude a’:
In FMSet#a, a is excluded in the sense of ‘fresh for all the elements of’.
In , a is excluded in the sense of ‘fresh for’.
The second main result of this paper is Theorem 5.11. This states that FMSet#a and are isomorphic categories. In this sense, ‘fresh for’ and ‘fresh for all elements of’ are the same after all.
Another way of reading this is particularly interesting.
In FMSet#a a is fresh ‘at the object level’; the arrows represent functions that operate on elements without a in their support. Note that the functions themselves will have a in their support; think of the characteristic function of a.
In a is fresh ‘at the meta-level’; the arrows represent functions without a in their support. Note that the functions may operate on elements with a in their support; think of the characteristic function of .
(Just to locate all of this relative to the category of nominal sets NOM: the category NOM of equivariant FM sets and equivariant functions between them is a limit of the νa construction. It represents a totally equivariant meta-language, operating on data that need not be equivariant.)
The main result asserts an equivalence between freshness at the meta-level and freshness at the object-level in the sense above. Or, to put it slightly differently: we prove the intuitively appealing but non-obvious fact that a fresh atom in the object-level is categorically isomorphic to a fresh atom in the meta-level.
This paper presents part of the mathematics of a larger manuscript [11], in a more accessible form and with an exposition tailored to Theorems 3.3 and 5.11.
2 Basic nominal constructions
2.1 The cumulative hierarchy
Fix a countably infinite set of atoms. abc will range over distinct elements of . We call this the permutative convention.
We define a collection of elements U in the style of von Neumann [17] by ordinal induction as follows:
1.
2. If α β and U then U .
3. If U then U .
We let U be the collection of all x such that x for some α.
U is a standard cumulative hierarchy model of Zermelo-Fraenkel set theory with atoms (ZFA). Examples are illustrated in Figure 1. This construction has been used for example in [9, 14, 4].
U is the least pre-fixedpoint of the operator ‘take the powerset of’; powerset(U ) U .
Write x U for ‘x , for some ordinal α’, and read this as x is an element. x will range over elements of U .
Call a non-atomic element a set. That is, x is a set when x U and x .
If X is a set then X x x X. This is not the case of atoms. For example a x x a.
Let x and y be elements. Let X and Y be sets. Implement the ordered pair (xy) and product set X Y by
Functions are implemented as graphs f (x f (x) that are sets, as is standard. We let f , g range over elements that are function-sets.
Write X Y for the set of function-sets with domain X and range a subset of Y.
2.2 Permutations
A permutation π is a bijection on such that a π(a) a is finite (we say that π has finite support). πτ will range over permutations. We also use the following notation:
Write id for the identity permutation, so id(a a always.
Write for functional composition. So (π )(a π((a)).
Write π-1 for the inverse of π, so π π-1 id π- π.
Write for the set of all permutations.
We define a permutation action inductively by:
idx x and (πx π)x.
In words: permutation is a group action on U .
2.3 Support
Let A be a finite set of atoms.
Write fix(Aπ a Aπ(a a.
Say that A supports x when πx x for all π fix(A).
Say x has finite support when some finite A supporting x exists.
Define supp(x) the support of x by
if x has finite support, and supp(x) is undefined otherwise.
Write a#x when a supp(x) and call a fresh for x. Write a#xyz for ‘a#x and a#y and a#z’, and so on.
Not every element of U has finite support. Make a fixed but arbitrary choice of bijection of with the natural numbers 012345. Let comb be the element corresponding under this bijection with the even numbers 024.
comb contains ‘every other atom’ aceg. There is no finite A such that if π fix(A) then πcomb comb.
A supports x if and only if πA supports πx.
As an immediate corollary, πsupp(x supp(πx).
If π is a permutation and A is a set of atoms, write π for the partial function such that
Let x be any element. If A and B are finite and support x then so does A B. As a corollary:
1. If x has a finite supporting set then it has a least finite supporting set and this is equal to supp(x).
2. If π π then πx πx.
Suppose τ fixes A B pointwise. We must show τx x. Write
Choose an injection ι of B A into (A B K). Define a permutation π by π(a ι(a) if a B A, π(ι(a a if a B A, and π(b b if b B A and ι-1(b) B A. Note that π π id, so π π-1. π fixes A pointwise so πx x. Also π τ π fixes B pointwise so (π τ π)x x. We apply π to both sides, use Lemma 2.8, and simplify, and conclude that τx x as required.
The first corollary follows from the fact that a descending chain of finite sets ordered by strict subset inclusion, is finite. The second corollary follows directly from the definition of support in Definition 2.9.
2.4 Equivariance
The language of ZFA set theory is first-order logic with equality and a binary predicate called set inclusion. φ will range over predicates in this language.
Suppose φ(x) is a predicate mentioning only variables from the list x. Then
Atoms are atomic; if we build one model of ZFA sets then we can permute its atoms to obtain another model. The result follows by soundness and completeness of first-order logic [27].
The reader can find much more on permutations in [25]. Indeed, the use of permutations of variable symbols predates nominal techniques; see for example [19, Subsection 9.2].
As is standard, we can specify a map χ using a predicate φ(xz) such that
Suppose χ(x) is a function specified using a predicate mentioning only variables from the list xz. Then
Theorem 2.18 is useful and easy to prove:
Suppose χ(x) is a function on variables included in x, which is . Suppose x denotes elements with finite support. Then
As a corollary, if χ is injective then
The corollary follows by considering the result for χ and its inverse.
Suppose that π fix(supp() supp()). We reason as follows:
The result follows.
3 Relation between supp(X) and supp(x) for x X
Suppose that X is a set. If X has finite support and all x X have finite support then say that X has finite support to level 1.
X and Y will range over sets with finite support to level 1.
Consider the notions ‘fresh for’ versus ‘fresh for all elements of’. In symbols, consider the predicates
If X is finite then ‘fresh for’ and ‘fresh for all elements of’ coincide. This matches the naive expection discussed in the Introduction; this is exactly the behaviour displayed by (finite) name-carrying abstract syntax.
Also as discussed in the Introduction, a central feature of nominal techniques is that if X is infinite then the two notions part company, and no particular implication connects them in general. Recall Example 1.1.
So just because a#X does not mean that a is fresh for every element in X, and conversely, just because a#x for every x X does not mean that a is fresh for X overall.
Define the category FMSet by:
Objects are sets X in U with finite support to level 1.
Arrows f : X Y are the function-sets in X Y with finite support.
In [9, 14] we use the hereditarily finitely supported sets; in Definition 3.2 we use sets with finite support to level 1, which is not quite the same. The difference will not be important.
Theorem 3.3 is new to the best of my knowledge. It gives the strongest direct equality I know of between supp(X) and supp(x) for x X.
Suppose X has finite support to level 1. If supp(x) x X is finite then
Suppose that supp(x) x X is finite. We prove two set inclusions:
supp(X) supp(x) x X. If supp(x) x X is finite then the result follows by Theorem 2.13 and the fact that πX πx x X.
supp(x) x X supp(X). Suppose x X and a supp(x). Choose fresh b (so b#X and b# for every X). By Theorem 2.11 supp((b a)xb a)supp(x). Since X has no element y such that b supp(y), we know that (b a)x X and by Theorem 2.13 it must be that a supp(X).
The special case of Theorem 3.3 where X is a finite set is known. See for example [10, Lemma 2.22] or [16]. Note that Theorem 3.3 is more general, and holds for X infinite.
Thanks to anonymous referees of previous papers for suggesting the precise form of the result stated here, and for providing the reference to the Isabelle code.
4 The quantifier
Suppose φ(za) is a predicate on variables included in za — here z is shorthand for ‘any other variables mentioned in φ’, and we intend a to range over atoms.
The NEW quantifier aφ(za) is defined by
aφ(za) is true when a φ(za) is false is finite.
If z is a list of variables write
Theorem 4.3 expresses the characteristic some/any property of the -quantifier:
Suppose φ(za) is a predicate on variables included in za. Suppose z denotes a list of elements with finite support. Then the following are equivalent:
Freshness a#x (Definition 2.9) can be characterised directly using and equality (see [14, Equation 5] or [14, Equation 13]):
Let x be an element with finite support. Then
Suppose a#x. By Theorem 2.13 if (b a)x x then b supp(x). supp(x) is finite by assumption. The result follows.
Now suppose that b(b a)x x. Let B be a finite set such that for all b B, (b a)x x. Choose any pair of distinct atoms b and in B. Note that
Therefore (b )x x always.
fix(B a) is generated as a group by elements of the form ( b) and (b a) as considered above. It follows that if π fix(B a) then πx x. Therefore a supp(x).
5 Statement and proof of the isomorphism
Fix an atom a. Recall Definitions 3.1 and 1.2 for the definitions of FMSet, FMSet#a and .
5.1 a-fresh sets
If X FMSet write
Call this the a-fresh version of X.
If X FMSet and Y FMSet and f X Y, write
Definition 5.1 reprises a comment in [13, Section 7, page 9]. In [11] we use the construction to give some nice proofs of properties of atoms-abstraction. The same construction is used by Clouston in [4].
Lemma 5.2 underlines the distinctness of ‘fresh for’ and ‘fresh for all elements of’:
a#X does not necessarily imply that X# X.
Consider a#. Then a.
If f : X Y then f#a : X# Y# FMSet#a.
Suppose f : X Y . In particular, a# f . It follows using Theorem 2.18 that f#a : X# Y#a.
5.2 Atoms-restriction
A notion of atoms-restriction will be useful:
Suppose X is an object in FMSet. Define νaX by
We read νaX as restrict a in X.
νaX is a model of the name-restriction of [6] and [24]; it is closely related to the permutation orbits of [10].
Suppose X is an object in FMset.
1. supp(νaX) supp(X) a.
2. It is not true in general that supp(νaX supp(X) a.
3. a#X if and only if νaX X.
1. It is easy to check that if π fix(supp(X) a) then πνaX νaX. The result follows by Theorem 2.13.
2. It suffices to provide a counterexample. Choose any b and take X ) (ab) (Definition 2.5). It is easy to check that νaX .
3. Suppose a#X. Suppose fix(supp(X) a) and X. By Theorems 2.15 and 2.13, X. It follows easily that νaX X. Conversely, if νaX X then by part 1 of this result a#X.
1. Suppose X is an object in . Then νa(X# X.
2. Suppose X is an object in FMSet#a. Then (νaX)# X.
For the first part, we prove two set inclusions:
Proof that X νa(X#a). Suppose x X. Choose some fresh b (so b#xX). By Theorem 2.13 (b a)x X and furthermore by Theorem 2.11 (b a)x X#a. It follows from Definition 5.4 that x νa(X#a).
Proof that νa(X#a) X. Suppose x νa(X#a). So x for some fix(supp(X#a)a) and some X#a. By Theorem 2.18 supp(X#a) a supp(X). Therefore fix(supp(X)). Now X, so by Theorem 2.13 X.
For the second part, again we prove two set inclusions:
Proof that X (νaX)#a. Suppose x X (so a#x). Then x νaX and it is immediate that x (νaX)#a.
Proof that (νaX)# X. Suppose x (νaX)#a. So x for some fix(supp(X)a) and some X (so a#). Now choose some entirely fresh b (so b#Xxa) and write π b a) (b a). It is a fact that π fix(supp(X) a), so by Theorem 2.13 πX X. Since a#, it is also a fact that π . By Theorem 2.13 π. It follows that x X, and by Theorem 2.11 it also follows that a#x.
Suppose f X Y is a function-set. Then π f is a function-set in πX πY, and it represents the function
This is the conjugation action.
From equivariance (Theorem 2.15).
Suppose f : X Y FMSet#a. Define νa f as follows: if x νaX then we set
We read νa f as restrict a in f .
If f : X Y FMSet#a then:
νa f is well-defined (the choice of fresh b does not matter).
νa f : νaX νaY .
supp(νa f ) supp( f ) a.
First, we review what has to be proved.
Suppose x νaX. Choose some fresh b (so b# f ax).
By Theorem 4.3 ( form), to calculate νa f it suffices to calculate (b a) f ((b a)x). It is a fact that if b#(b a) f ((b a)x) then this result does not depend on the choice of fresh b.
We must also check that supp(νa f ) is finite, and a#νa f ; there is no need for a separate proof of this, since it is subsumed by a proof that supp(νa f ) supp( f ) a.
We sketch each part of the proof in turn:
(b a) f ((b a)x) well-defined. b#(b a) f ((b a)x) is immediate because we assumed that f FMSet#a. What is slightly non-trivial is to prove that if x νaX then (b a)x X. Since x νaX and X FMSet#a, there exists some fix(supp(X) a) and some X such that x and a#. We reason as follows:
It is a fact that ((b a) (b a)) fix(supp(X)) and it follows by Theorems 2.15 and 2.13 that (b a)x X.
b#(b a) f ((b a)x). Using Theorem 2.11.
b#(b a) f ((b a)x) νaY. It is a fact that f ((b a)x) Y. The result follows by the definition of νaY.
We now prove that supp(νa f ) supp( f ) a. By Theorem 2.18 supp(νa f ) supp( f ) a. By Theorems 4.4 and 4.3 ( form) it then suffices to check that ( a)(νa f νa f for some fresh (so # f a). Choose some x νaX and some fresh b. We reason as follows:
5.3 Statement and proof of the main result
The following data specifies a pair of functors between FMSet#a and :
-#a : FMSet#a maps X to X#a and f : X Y to f#a : X# Y#a.
-νa : FMSet# maps X to νaX and f : X Y to νa f : νaX νaY.
By routine calculations.
-#a and -νa define an isomorphism of categories between FMSet#a and .
That the functors are inverse on objects follows quickly from Lemma 5.6.
We check that these functors are inverse on arrows. Suppose f : X Y . So f X Y and a# f XY. We must check that νa( f# f . Take any x X and choose some entirely fresh b. We reason as follows:
Suppose f : X Y FMSet#a. So f X# Y#a. We must check that (νa f )# f . Take any x X#a and choose some entirely fresh b. We reason as follows:
6 Conclusions and related work
It is known that the category of nominal sets admits a representation as pullback-preserving presheafs, but abstract categorical presentations of the properties of this ‘nominal’ category that makes it ‘nominal’, have been lacking. There has been quite a lot of interest, especially recently, in more abstract accounts of what ‘nominal’ really is.
As far as I know Menni was the first to think about this, for the -quantifier [20]. Pitts and Clouston are developing a notion of ‘FM category’ [4]. Kurz and Petrisan are pursuing not dissimilar ideas, coming (speaking very roughly) from the point of view of many-sorted logic and cylindric algebra [18]. Fiore and Hur are developing their own categorical framework [7], of which aspects of nominal techniques are in a certain sense they make formal a special case. There are, of course, other models of of names at a very abstract semantic level; examples include [3] (not strictly speaking categorical) and [15].
Here, this paper could be timely and the observations in it could be of some use; to suggest categorical equivalences to look for in the authors’ respective environments, or indeed directly as a property of the category of FM sets FMSet.
Let me suggest an alternative reading of the results in this paper. FMSet#a and are both categories with ‘an atom missing’. In FMSet#a, the atom is missing because it is fresh for individual data. In , the atom is missing because it is fresh for the objects and arrows. Let us shift our point of view and consider a reading of FMSet as a version of FMSet#a and with an extra atom put in. In that sense, the two notions of freshness considered in this paper correspond to two notions of ‘add a fresh atom’: if we start from FMSet#a and add an atom to the underlying data, we get FMSet; and if we start from and give the language the power to resolve a, we also get FMSet. The main result of this paper is that these two starting-points are isomorphic.
The equivalence of FMSet#a and seems an elegant result. Up to a categorical isomorphism, there is only one way to add/subtract an atom.
References
[1] Nicolas Bourbaki, Théorie des ensembles, Hermann, Paris, 1970.
[2] Norbert Brunner, 75 years of independence proofs by Fraenkel-Mostowski permutation models, Mathematica Japonica 43 (1996), 177–199.
[3] Anna Bucalo, Furio Honsell, Marino Miculan, Ivan Scagnetto, and Martin Hofmann, Consistency of the theory of contexts, Journal of Functional Programming 16 (2006), no. 3, 327–395.
[4] Ranald Clouston, Equational logic for names and binding, Ph.D. thesis, University of Cambridge, UK, 2010, Pending graduation.
[5] Nicolaas G. de Bruijn, Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem, Indagationes Mathematicae 5 (1972), no. 34, 381–392.
[6] Maribel Fernández and Murdoch J. Gabbay, Nominal rewriting with name generation: abstraction vs. locality, Proceedings of the 7th ACM SIGPLAN International Symposium on Principles and Practice of Declarative Programming (PPDP 2005), ACM Press, 2005, pp. 47–58.
[7] Marcelo Fiore and Chung-Kil Hur, Term equational systems and logics, Electronic Notes in Theoretical Computer Science 218 (2008), 171–192.
[8] Marcelo P. Fiore, Gordon D. Plotkin, and Daniele Turi, Abstract syntax and variable binding, Proceedings of the 14th IEEE Symposium on Logic in Computer Science (LICS 1999), IEEE Computer Society Press, 1999, pp. 193–202.
[9] Murdoch J. Gabbay, A Theory of Inductive Definitions with alpha-Equivalence, Ph.D. thesis, University of Cambridge, UK, 2000.
[10], A study of substitution, using nominal techniques and Fraenkel-Mostowski sets, Theoretical Computer Science 410 (2009), no. 12-13, 1159–1189.
[11], The mathematical foundations of nominal techniques, (2010), Accepted subject to revision.
[12] Murdoch J. Gabbay and Martin Hofmann, Nominal renaming sets, Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2008), Springer, 2008, pp. 158–173.
[13] Murdoch J. Gabbay and Andrew M. Pitts, A New Approach to Abstract Syntax Involving Binders, 14th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, 1999, pp. 214– 224.
[14], A New Approach to Abstract Syntax with Variable Binding, Formal Aspects of Computing 13 (2001), no. 3–5, 341–363.
[15] Martin Hofmann, Semantical analysis of higher-order abstract syntax, Proceedings of the 14th Annual Symposium on Logic in Computer Science (LICS 1999), IEEE Computer Society Press, 1999, pp. 204–213.
[16] Isabelle/HOL/Nominal, Lemma supp of fin sets, 2009, http://isabelle.in.tum.de/repos/ isabelle/file/Isabelle2009-1/src/HOL/Nominal/Nominal.thy#l2331.
[17] Thomas Jech, Set theory, Springer, 2006, Third edition.
[18] Alexander Kurz and Daniela Petrisan, On universal algebra over nominal sets, Mathematical Structures in Computer Science 20 (2010), 285–318.
[19] James McKinna and Randy Pollack, Pure Type Systems formalized, Proceedings of the International Conference on Typed Lambda Calculi and Applications (TLCA 1993), LNCS, no. 664, Springer-Verlag, March 1993, pp. 289–305.
[20] Matias Menni, About -quantifiers, Applied Categorical Structures 11 (2003), no. 5, 421–445.
[21] Dominic P. Mulligan, Online nominal bibliography, www.citeulike.org/group/11951/, 2010.
[22] Frank Pfenning and Conal Elliott, Higher-order abstract syntax, PLDI (Programming Language Design and Implementation), ACM Press, 1988, pp. 199–208.
[23] Andrew M. Pitts, Nominal logic, a first order theory of names and binding, Information and Computation 186 (2003), no. 2, 165–193.
[24], Nominal system T, Proceedings of the 37th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2010), ACM Press, January 2010, pp. 159–170.
[25] Dugald Macpherson Richard Kaye (ed.), Automorphisms of first-order structures, Oxford University Press, 1994.
[26] Mark R. Shinwell, The fresh approach: Functional programming with names and binders, Ph.D. thesis, Computer Laboratory, University of Cambridge, December 2004.
[27] Joseph Shoenfield, Mathematical logic, Addison-Wesley, 1967.
[28] Christian Urban, Nominal reasoning techniques in Isabelle/HOL, Journal of Automatic Reasoning 40 (2008), no. 4, 327–356.
Notes
1Presheaves have a version of support, but in a sense that can be made entirely formal, it is possible for an element to have many distinct supports. See [12] for a more detailed discussion. ↩
2The transitive closure of X is the set containing the elements of X, the elements of the elements of X, and so on. It is the least fixedpoint of the mapping X X X. ↩