Representation and duality of the untyped -calculus in nominal lattice and topological semantics, with a proof of topological completeness
We give a semantics for the -calculus based on a topological duality theorem in nominal sets. A novel interpretation of is given in terms of adjoints, and -terms are interpreted absolutely as sets (no valuation is necessary).
Additional Key Words and Phrases: Nominal algebras, fresh-finite limits, lambda-calculus, spectral spaces, lattices and order, variables, nominal techniques, mathematical foundations, Fraenkel-Mostowski set theory
1. INTRODUCTION
In this paper we build a topological duality result for the untyped -calculus in nominal sets and prove soundness, completeness, and topological completeness.
This means the following:
— We give a lattice-style axiomatisation of the untyped -calculus and prove it sound and complete.
— We define a notion of topological space whose compact open sets have notions of application and -abstraction.
— We prove that the categories of lattices-with- and topological-spaces-with- are dual.
— We give a complete topological semantics for the -calculus.
So this paper does what Stone duality does for Boolean algebras [Joh86], but for the -calculus.
1.1. A very brief summary of the contributions
We summarise some contributions of the paper; this list will be fleshed out in the rest of the Introduction:
(1) No previous duality result for -calculus theories exists. Duality results are interesting in themselves (see next subsection), and it is interesting to see how nominal techniques help to manage the technical demands of such a result.
(2) The topological representations obtained are concrete, being based on nominal sets.
(3) The representation of open terms does not use valuations; possibly open -terms are interpreted as open sets in a nominal topological space (this is sometimes called an absolute semantics). Function application and also -abstraction get interpreted as concrete sets operations on nominal-style atoms.
(4) This paper is a nontrivial application of nominal ideas, and the techniques on nominal sets which we use are original and have independent technical interest.1
(5) We make nominal-style atoms—urelemente in Fraenkel-Mostowski set theory—behave like variables of the -calculus. Urelemente in set theory come equipped with very few properties; indeed, by design urelemente have virtually no properties at all. It is remarkable that they can nevertheless acquire such rich structure.2
(6) -reduction and -expansion are exhibited as adjoint properties.
(7) The fine structure of the canonical models (those of the form ) is very rich, as we shall see. The use of canonical models in this paper probably does not exhaust their interest.
(8) We prove a topological completeness result—but this should be impossible: topological incompleteness results exist in the literature. This depends on the topology, so the fact that a notion of topology that ‘works’ for the -calculus exists, is surprising given the current state of the art. One would not expect this to work.
1.2. The point of duality results
What is the point of a duality result, and why bother doing it for the -calculus?
(1) Duality results are a strong form of completeness: for a given class of abstract models, every model has a concrete topological representation (i.e. in terms of sets with a few consistency conditions) and every map between models has a concrete representation as a continuous map (i.e. a map that has to respect those conditions).
Intuitively, Boolean algebras, Heyting algebras, and distributive lattices look like they all have to do with powersets (negation is some kind of sets complement, conjunction is sets intersection, disjunction is sets union, and so on). But is this true? Is it possible to construct some sufficiently bizzare model such that for instance conjunction must mean something other than sets intersection? The answer is no: duality theorems tell us that no matter how bizzare the model, it can be represented topologically. In topologies conjunction is sets intersection. The same analysis is applicable to our duality result for the -calculus.
(2) Of course, it is not obvious how conjunction enters into the untyped -calculus. Indeed, no duality result has been achieved for the -calculus before and it is not obvious even how to begin to go about this. One contribution of this paper is that we embed the -calculus in an impredicative logic which we characterise in two ways: in nominal algebra, and using a nominal generalisation of finite limits which we call fresh-finite limits (Definition 4.1.2).
An example observation that comes out of this is that we exhibit -reduction and -expansion as adjoint maps (counit and unit respectively; see Proposition 10.2.4).
Another example is that features in this paper as a derived object made out of the fresh-finite limit , and a right adjoint to application . See Notation 10.2.1 and the subsequent discussion. The quantifier is itself an interesting entity, a kind of arbitrary conjunction, which relies heavily on nominal techniques. More on this later. Thus, in the process of defining and proving our results—representation, duality, and completeness—we uncover a wealth of structure in the untyped -calculus (to add to the wealth of structure already known). The technical definitions and lemmas which our ‘main results’ depend on, are as interesting as the results themselves.
(3) Finally, we note that our topological semantics for the -calculus is complete (Theorem 11.9.5). This is remarkable because Salibra has shown that all known semantics for the -calculus based on partial orders, are incomplete [Sal03]. The fact that our semantics is topological (thus ordered) and complete, is unexpected.3 We discuss this apparent paradox in Subsection 12.1.5. In any case, new semantics for the untyped -calculus do not come along very often, and as mentioned above, no duality result for the -calculus has been proved before.
More interesting structure will be uncovered by this way of approaching the -calculus; the list above justifies why it is a priori interesting to try.
We would like to address one more obvious question: why is this paper so long?
Even granted that the results are interesting, reading them may require some stamina.4 Does it have to be this way? We think this is reasonable, because:
(1) This paper takes on two notoriously challenging types of proof: a duality result (for a complex logic) and a semantics for and completeness proof for the untyped -calculus. It is simply a fact that duality results are hard, completeness proofs are also hard, and semantics for the untyped -calculus are not trivial to construct.5
(2) This paper is based on nominal techniques. This is a relatively less developed and less familiar environment than the well-trodden Zermelo-Fraenkel/higher-order logic framework, so we have to build our tools as we go along. Even when material is taken from previous work, we cannot assume the reader is familiar with it. In short, there can be relatively less hand-waving. Where we can rely on the material being familiar, we will be more brief.
Given that we undertake two proofs which are known to be meaty, about a system whose semantics are challenging, and given that we build the tools for this from first principles, it may be more surprising that the paper is not longer.
So our starting point is urelemente (atoms) of Fraenkel-Mostowski set theory; our target is the untyped -calculus, and between them there is a lot of ground to cover. Everything in this paper is there because its has to be, it is worth the effort, and the material has natural momentum which propels us from the first definitions to the final results.
1.3. Background motivation, in a nutshell
Interpretations of () or () usually involve an explicit quantification over some domain. This is reflected in semantics, which involve a valuation assigning interpretations to variables.
Alternatively we can interpret variables as atoms in Fraenkel-Mostowksi sets. Originally this was applied to model inductive syntax [Gab01; GP01]. This paper is part of a research programme to apply the idea to models of logic and computation.
The key definitions go back to [GM06a; GM06b], where nominal algebraic notions of substitution and first-order logic were given. Variables receive a fixed interpretation in the model, as atoms. Instead of valuations is a nominal algebraic generalisation of substitution—this is the -action of this paper.
The payoff is interesting new classes of models. There is quite an extensive literature on this, discussed in the Conclusions. Most recently, in [Gab11b; Gab12] we consider nominal lattice and topological models of first-order logic—and in this paper we do something similar for the -calculus, though this is harder since the -calculus is more complex.
Universal quantification becomes a special kind of limit called a fresh-finite limit. On a -algebra this happens to coincide with an infinite conjunction of substitution instances, but that is a theorem, not a definition. splits into two halves, and essentially becomes a corollary of and application.
Using this we obtain axiomatic, lattice-theoretic, topological, and concrete models of the -calculus. We are used to seeing such things for the propositional case, for instance for Boolean algebras. It is more unusual to see this applied to languages with binders, but that is what nominal techniques help us to deal with. In doing this, we also give a complete topological semantics for the -calculus.
1.4. Map of the paper
Section 2 sets up some basic nominal theory. The reader might like to skim this at first, since the definitions might only make sense in terms of their application later on in the paper. Highlights are the notions of nominal set (Definition 2.1.5), finitely-supported and strictly-finitely supported powersets (Subsections 2.4.1 and 2.4.2), equivariance properties of atoms and the -quantifier (Theorem 2.3.1 and Definition 2.3.6), and the -quantifier for sets (Subsection 2.5).
Section 3 introduces - and -algebras. These are the basic building blocks from which our models will be constructed. The definitions are already non-trivial; highlights are the axioms of Figure 1 (which go back to [GM06a], where nominal algebra was introduced to axiomatise substitution) and [Gab11b] (which introduced -algebras), and the precise definition of the -action on nominal powersets in Definition 3.4.1, which uses the -quantifier.
Section 4 considers lattices over nominal sets. The technical highlight here is the characterisation of universal quantification in terms of fresh-finite limits (Definition 4.1.1 and subsequent results). Combined with impredicativity and the -action we arrive at Definitions 4.5.1 and 4.5.9, which are the lattice-theoretic structure within which we eventually build models of the -calculus which we write inDi (pronounced ‘India’).
Section 5 shows that (simplifying) every nominal powerset is a model of Definition 4.5.1. A technical highlight here is Proposition 5.2.8: a characterisation of universal quantification on nominal sets in terms of universal and new-quantification over all atoms. Definition 5.2.1 is also interesting just because it shows how the -action can be combined with other sets operations to do predicate logic.
Section 6 uses filters and prime filters to give a nominal sets representation of any inDi, and Section 7 extends this to a full duality.
This duality is for a propositional logic with quantifiers. To handle the -calculus we need more: this happens in Section 9. The most important points are probably the introduction of and its right adjoint in Definition 9.1.1, and the observation that their topological dual is a combination operator in Definition 9.2.1.
It now becomes fairly easy to show that every inDi is also a semantics for the untyped -calculus. This is Section 10, culminating in Definition 10.4.1 and Theorem 10.4.7; we include an interlude in Subsection 10.5 where we pause to take stock of what we have been doing so far.
Slightly harder is proving completeness, for which we must construct an object in inDiinSpect for any given -theory. This is Section 11: we have the tools (nominal and otherwise) required in principle to carry out the constructions (just build filters, etcetera)—but in practice the amount of detailed structure required to make this work is quite striking, involving amongst many other things the construction of and on points (Definition 11.3.1) and a left adjoint to the -algebra on filters (Definition 11.4.1). If two results should illustrate how tightly knit this part of the mathematics can be, then the technical results of Proposition 11.1.6 and Lemma 11.4.9 are good examples. The final Completeness result is Theorem 11.9.5.
We conclude in an Appendix with a nominal axiomatisation of , to go with the lattice-theoretic one of Definition 4.1.2, and some nice additional observations on the structure of points.
1.5. A list of interesting technical definitions
This list is not of the major results, nor is it an exhaustive list of technical definitions. But one technical definition or proof looks very much like another, so here are suggestions of which technical highlights might be worth looking at first:
— We characterise universal quantification in four different ways, all of which have their place in the paper: as a fresh-finite limit in Definition 4.1.2, using quanitification over all atoms in Proposition 5.2.8, slightly indirectly using the -quantifier in Definition 6.1.1, and finally using nominal algebra axioms in Appendix A.1.
— As mentioned above, -reduction and -expansion are derived from a counit and unit respectively in Proposition 10.2.4.
— We decompose of into and in Notation 10.2.1. We decompose further into atoms-quantification in Proposition 5.2.8.
— Proposition 5.2.8 and Lemma 11.5.2 are inherently surprising results.
— Three little proof gems are in Proposition 11.1.8, Lemma 11.2.4, and Lemma 11.5.1.
— We need two notions of filter: one is Definition 6.1.1 (the interesting new part is condition 4), the other is Definition 11.1.3 (we call it a point). Both notions use the -quantifier in interesting ways.
— The pointwise definition of substitution is in Definition 3.4.1; a different approach to substitution than the reader has likely seen, which makes use of the -quantifier and -algebra (Definition 3.2.1). The two concrete characterisations of it in Subsection 11.4.2 are also interesting.
— The reader will see much use made of the nominal -quantifier, meaning ‘for all but finitely many atoms’, and of nominal equivariance properties and notions of finite support and strict finite support. We mention two (connected) examples: the use of in defining the -action in Definition 3.4.1, and the treatments of the universal quantifier in Proposition 5.2.8 and in condition 4 of Definition 6.1.1. A search of the paper for uses of Corollary 2.1.10, Theorems 2.3.1 and 2.3.9, and Lemma 2.4.3 will find many more.
2. BACKGROUND ON NOMINAL TECHNIQUES
A nominal set is a ‘set with names’. The notion of a name being ‘in’ an element is given by support supp() (Definition 2.1.7). For more details of nominal sets, see [GP01; Gab11a].
Here we just give necessary background information. The reader not interested in nominal techniques per se might like to read this section only briefly in the first instance, and use it as a reference for the later sections, where the ideas get applied.
For the reader’s convenience we take a moment to note the overall message of this section:
— To the category-theorist we say that we work mostly in the category of nominal sets, or equivalently in the Schanuel topos (more on this in [MM92, Section III.9], [Joh03, A.21, page 79], or [Gab11a, Theorem 9.14]), and occasionally also in the category of sets with a permutation action.
— To the set-theorist we say that our constructions can be carried out in Fraenkel-Mostowski set theory (FM sets) and Zermelo-Fraenkel set theory with atoms (ZFA). A discussion of such sets foundations, tailored to nominal techniques, can be found in [Gab11a, Section 10]).
— To the reader not interested in foundations we say that the apparently inconsequential step of assuming names as primitive entities in Definition 2.1.1 gives us a remarkable clutch of definitions and results, notably Theorem 2.1.9 and Corollary 2.1.10, and Theorems 2.3.1 and 2.3.9. These properties are phrased abstractly but will quickly make themselves very useful in the body of this paper. See previous work for more background [GP01; Gab11a; Gab13].
2.1. Basic definitions
Fix a countably infinite set of atoms . We use a permutative convention that range over distinct atoms.
A (finite) permutation is a bijection on atoms such that nontriv( () is finite.
Write id for the identity permutation such that id( for all . Write for composition, so that ()((()). Write for inverse, so that . Write () for the swapping (terminology from [GP01]) mapping to , to , and all other to themselves, and take (.
If write
A set with a permutation action is a pair () of an underlying set and a permutation action written or just which is a group action on , so that id and () for all and permutations and . Say that supports when fix() . If a finite supporting exists, call finitely supported.
Call a set with a permutation action a nominal set when every has finite support. , , will range over nominal sets.
Call a function from to equivariant when ((() for all permutations and . In this case write : .
The category of nominal sets and equivariant functions between them is usually called the category of nominal sets.
Suppose is a nominal set and . Define the support of by
Write # as shorthand for supp() and read this as is fresh for .
Given atoms and elements write # as shorthand for supp(, or to put it more plainly: # for every and .
Suppose is a nominal set and . Then supp() is the unique least finite set of atoms that supports .
See part 1 of Theorem 2.21 of [Gab11a].
(1) If ( for all supp() then .
(2) If (() for every supp() then .
(3) # if and only if (# ()).
See part 2 of Theorem 2.21 of [Gab11a].
2.2. Examples
Suppose and are nominal sets, and suppose is a set with a permutation action. We consider some examples of sets with a permutation action and of nominal sets. These will be useful later on in the paper.
2.2.1. Atoms and booleans.
is a nominal set with the natural permutation action (). For the case of only we will be lax about the difference between (the set of atoms) and () (the nominal set of atoms with its natural permutation action). What that means in practice is that we will write and never write .6
The only equivariant function from to itself (Definition 2.1.6) is the identity map . There are more finitely supported maps from to itself; see the finitely supported function space below.
Write for the nominal set of Booleans, which has elements and the trivial permutation action that for all and .
2.2.2. Cartesian product.
is a nominal set with underlying set () and the pointwise action ().
An equivariant : () corresponds to a relation such that if and only if .
2.2.3. Tensor product.
is a nominal set with underlying set () supp()supp( and the pointwise action. For the pointwise action here to be well-defined depends on being a permutation and the fact (Proposition 2.3.3 below) that supp( supp().
2.2.4. Full function space.
Functions from to form a set with a permutation action with underlying set all functions from to , and the conjugation permutation action
2.2.5. Finitely supported function space.
is a nominal set with underlying set the functions from to with finite support under the conjugation action, and the conjugation permutation action.
A complete description of the finitely supported functions from to is as follows:
— The identity, mapping to itself.
— Any function such that there exists some and some finite such that if then ( (so is ‘eventually constant’).
2.2.6. Full powerset
Suppose is a set with a permutation action. Give subsets the pointwise permutation action
Then powerset() (the full powerset of ) is a set with a permutation action with
— underlying set (the set of all subsets of , and
— the pointwise action .
A particularly useful instance of the pointwise action is for sets of atoms. As discussed in Subsection 2.2.1 above, if then (). Thus if then
Even if is a nominal set, powerset() need not be a nominal set. That is, powerset() is not necessarily a nominal set.
Take to be equal to and consider the set
of ‘every other atom’. This does not have finite support, though permutations still act on it pointwise. For more discussion of this point, see [Gab11a, Remark 2.18].
We consider further examples in Subsection 2.4, including the finitely-supported and strictly finitely-supported powersets.
2.3. The principle of equivariance and the quantifier
We come to Theorem 2.3.1, a result which is central to the ‘look and feel’ of nominal techniques. It enables a particularly efficient management of renaming and -conversion in syntax and semantics and captures why it is so useful to use names in the foundations of our semantics and not some other infinite, set such as numbers.
Names are by definition symmetric (i.e. can be permuted). Taking names and permutations as primitive implies that permutations propagate to the things we build using them. This is the principle of equivariance (Theorem 2.3.1 below; see also [Gab11a, Subsection 4.2] and [GP01, Lemma 4.7]).
The principle of equivariance implies that, provided we permute names uniformly in all the parameters of our definitions and theorems, we then get another valid set of definitions and theorems. This is not true of e.g. numbers because our mathematical foundation equips numbers by construction with numerical properties such as less than or equal to , which can be defined from first principles with no parameters.
So if we use numbers for names then we do not care about because we just needed a countable set of elements, but we repeatedly have to prove that we did not use an asymmetric property like . In contrast, with nominal foundations and atoms, we do not have to explicitly prove symmetry because we can just look at our mathematical foundation and note that it is naturally symmetric under permuting names; we reserve numbers for naturally asymmetric activities, such as counting.
This style of name management is characteristic of nominal techniques. The reader can find it applied often, e.g. in Lemmas 3.2.5 and 3.4.8, Propositions 3.3.4 and 4.3.5, and Lemma 5.1.2.
If is a list , write for . Suppose () is a first-order logic predicate with free variables . Suppose () is a function specified using a first-order predicate with free variables . Then we have the following principles:
(1) Equivariance of predicates. () ().7
(2) Equivariance of functions. (() (cf. Definition 2.1.6).8
(3) Conservation of support. If denotes elements with finite support then supp(()) supp()supp(). If in addition is injective, then supp(( supp()supp().
See Theorem 4.4, Corollary 4.6, and Theorem 4.7 from [Gab11a].
supp(supp() (which means () supp()).
Lemma 2.3.4 goes back to [GM07, Lemma 5.2] and [GM09, Corollary 4.30]; see [Gab13, Lemma 7.6.2] for a recent presentation:
If is an equivariant function from to and #() then there exists some such that # and (().
Suppose : is an equivariant function and and . Suppose further that #. Then ( ())().
By equivariance ()((() ()). By Corollary 2.1.10 since # also ().
We can read as ‘for all but finitely many ’, ‘for fresh ’, or ‘for new ’. It captures a generative aspect of names, that for any we can find plenty of atoms such that supp(). was designed in [GP01] to model the quantifier being used when we informally write “rename in to be fresh”, or “emit a fresh channel name” or “generate a fresh memory cell”.
Specifically over nominal sets, however, displays special properties. In particular, it satisfies the some/any property that to prove a -quantified property we test it for one fresh atom; we may then use it for any fresh atom. This is Theorem 2.3.9:
Suppose () is a predicate with free variables .11 Suppose denotes elements with finite support. Then the following are equivalent:
2.4. Further examples
We now consider the finitely supported powerset and the strictly finitely supported powerset. These examples are more technically challenging and will be key to the later constructions.
2.4.1. Finitely supported powerset.
Suppose is a set with a permutation action (it does not have to be a nominal set).
Then pow(), the nominal powerset, is a nominal set, with
— underlying set those powerset() that are finitely supported, and
— with the pointwise action inherited from Definition 2.2.1.
Unpacking the definitions and using Corollary 2.1.10, is finitely supported when, equivalently:
— There exists some finite such that if fix() then .
— There exists some finite such that if fix() and then .
For instance:
— pow() is the set of finite and cofinite sets of atoms (a set of atoms is cofinite when its complement is finite).
— pow(powerset()) is a set of sets of atoms with finite support, though the elements need not have finite support. For instance, if we set comb from Lemma 2.2.2 then we can take all permutations . Here has finite (indeed, empty) support, even though none of its elements have finite support.
It is useful to formalise these observations as a lemma. A common source of confusion is to suppose that if supports pow() then must supports every . This is incorrect:
It is not true in general that if pow() and then supp() supp().
In other words, # and does not imply #.
It suffices to provide a counterexample. Take (the nominal set of atoms with the natural permutation action, from Subsection 2.2.1) and (the underlying set of the nominal set of all atoms, i.e. the set of all atoms!).
It is easy to check that supp( and and supp(.
2.4.2. Strictly finitely supported powerset.
Suppose is a nominal set.
Call strictly supported by when
If there exists some finite which strictly supports , then call strictly finitely supported.
Write strict() for the set of strictly finitely supported . That is:
strict( finite strictly supported by
If strict() then:
(1) supp() is finite.
(2) supp() supp().
(3) If is strictly finitely supported then it is finitely supported.
(4) implies supp() supp() (contrast this with Lemma 2.4.1).
(5) strict() with the pointwise permutation action is a nominal set.
The first part is immediate since by assumption there is some finite that bounds supp() for all . The second part follows by an easy calculation using part 3 of Corollary 2.1.10; full details are in [Gab11a, Theorem 2.29], of which Lemma 2.4.3 is a special case. The other parts follow by definitions from the first and second parts.
is finitely supported by but not strictly finitely supported. is finitely and strictly finitely supported by .
For the reader who does not like examples based on the empty set, another useful example is as follows: is finitely supported by but not strictly finitely supported. is finitely supported by and also strictly finitely supported by .
If is a nominal set and strict(strict()) then strict(). Or in words: “a strictly finitely supported set of strictly finitely supported sets, is strictly finitely supported”.
By routine calculations using part 4 of Lemma 2.4.3.
2.5. The -quantifier on nominal sets
Suppose is a set with a permutation action.
Given a finitely supported define the new-quantifier on (nominal) sets by
Suppose . Suppose is finitely supported. Then ().
was written n in [GLP11, Definition 5.2], and goes back to [Gab09b] where it was written . We will use in Lemma 11.4.8 to prove things about a -action.
supp() supp().
By a routine calculation using Corollary 2.1.10.
Recall from Subsection 2.4.1 the notion of nominal powerset pow().
If pow() then pow().
I. NOMINAL DISTRIBUTIVE LATTICES WITH QUANTIFICATION
3. NOMINAL ALGEBRAS OVER NOMINAL SETS
3.1. Definition of a sigma-algebra (-algebra)
3.1.1. A termlike -algebra.
Definitions 3.1.1, 3.1.4, and 3.2.1 assemble three key technical structures (see also Definitions 3.3.3 and 3.4.5).
A termlike -algebra is a tuple ) of:
— a nominal set () which we may write just as ; and
— an equivariant -action () , written [ or just []; and
— an equivariant injection written or just ,
such that the equalities (a), (id), (#), (), and () of Figure 1 hold, where , , and range over elements of .12
We may omit subscripts where is understood.
Definition 3.1.1 is abstract. It is an axiom system. We use nominal algebra, because the axioms require freshness side-conditions.
Examples of termlike -algebras include plenty of syntax: for instance the set of terms of first-order logic with substitution; or the syntax of the untyped -calculus quotiented by -equivalence with capture-avoiding substitution; or the syntax of propositional logic with quantifiers (syntax generated by , with capture-avoiding substitution [:]).
However, not all termlike -algebras are syntax. For a huge class of extremely non-syntactic termlike -algebras, consider models of FM sets [Gab09b].
3.1.2. A -algebra
A -algebra is a tuple sub) of:
— A nominal set () which we may write just as .
— A termlike -algebra .
— An equivariant -action () , written infix [ or [].
such that the equalities (id), (#), (), and () of Figure 1 hold,13 where ranges over elements of and and range over elements of .
As for termlike -algebras, we may omit the subscript . We may slightly informally say that has a -algebra structure over .
Every termlike -algebra is a -algebra over itself. The canonical ‘interesting’ example of a -algebra is the syntax of predicates of first-order logic, whose substitution action is not over predicates but over the termlike -algebra of terms.
Not all -algebras are syntactic. In this paper we will see many examples of non-syntactic -algebras, based on the -powersets of Definition 3.4.5.
3.2. Definition of an amgis-algebra (-algebra)
An -algebra (spoken: amgis-algebra) is a tuple ) of:
— A set with a permutation action () which we may write just as .
— A termlike -algebra .
— An equivariant amgis-action () , written infix [ or [].
such that the equality () of Figure 1 holds, where ranges over elements of and and range over elements of . We may omit the subscript .
[] looks like [] written backwards, and a casual glance at () suggests that it is just () written backwards. This is not quite true: we have [] on the right in () and not ‘[]’ (which would make no sense, since has no amgis-action).
Discussion of the origin of the axioms of -algebras is in Subsections 3.3 and 3.4; see also Proposition 3.3.4 and Subsection 3.4.3.
In this paper, the main classes of -algebras will be those based on the -powerset of Definition 3.3.3, those based on prime filters in Definition 6.2.2, and those based on in Proposition 6.2.3.
We conclude with three technical lemmas which will be useful later:
If is a -algebra and # then [).
By () [))[]. We use (id).
If # then #[].
If # then [][][).
In Subsection 3.3 we explore how to move from a -algebra to an -algebra using nominal powersets. In Subsection 3.4 we explore how to move from an -algebra to a -algebra, again using nominal powersets.
3.3. Duality I: to
Given a -algebra we generate an -algebra out of its subsets. This is Proposition 3.3.4.
Suppose is a -algebra and and . Then:
— if and only if .
— [] if and only if [] .
By easy calculations on the pointwise actions in Definition 3.3.1.
If is a -algebra then pow() from Definition 3.3.3 is an -algebra.
3.4. Duality II: to
3.4.1. The pointwise -action on subsets of an -algebra
Suppose is an -algebra and . Suppose and and #. Then:
(1) [] if and only if [] ().
(2) If furthermore has finite support15 and #, then we can simplify part 1 of this result to [] if and only if [] .
(3) if and only if .
Suppose is an -algebra and has finite support. If # then [))[].
Proposition 3.4.4 is useful, amongst other things, in Lemma 3.4.8. On syntax it is known as the substitution lemma, but here it is about an action on sets , and the proof is different:
Suppose is an -algebra and has finite support. Suppose . Then
We reason as follows, where we write ) ():
3.4.2. The -powerset pow().
Recall from Subsection 2.4.1 the finitely supported powerset pow() of a nominal set .
Lemma 3.4.6 rephrases conditions 1 and 2 of Definition 3.4.5, in a simpler language, albeit one which requires the -action on subsets of an -algebra from Definition 3.4.1:
Suppose (). Then [.
By construction [] , so we now check the properties listed in Definition 3.4.5.
By assumption in Definition 3.4.5, is finitely supported. Finite support of [] is from Theorem 2.3.1.
We check the conditions of Definition 3.4.5 for []:
(1) For fresh (so #), [][[]. We use Lemma 3.4.3 to assume without loss of generality that #. It suffices to reason as follows:
(2) For fresh (so #) [][)([]). It suffices to reason as follows:
If is an -algebra then () (Definition 3.4.5) is indeed a -algebra.
3.4.3. Some further remarks.
The definition of [] in Definition 3.4.1 is designed to make -equivalence (Lemma 3.4.3) hold—that is, () from Figure 1.
If is finitely supported so that every has finite support, then the definition can be simplified as described in part 2 of Proposition 3.4.2.
This simpler version of the definition appeared previously in [Gab11b; Gab12]. We arrived at Definition 3.4.1 as a modification and generalisation of the first definition to the case where we cannot assume that points have finite support (because of a later use of Zorn’s Lemma in Theorem 6.1.13).
Interestingly, only () comes directly from the structure of the underlying -algebra (from ()). Other axioms are forced—() from the definition (Lemma 3.4.3), and (#) and (id) from conditions 1 and 2 in Definition 3.4.5.
In fact, we could start from a structure satisfying just () to obtain an -algebra using the construction in Definition 3.3.1, then move to a -algebra using Definition 3.4.1.
In this paper, we never need to do this; we will always start from a full -algebra.
4. NOMINAL POSETS
4.1. Nominal posets and fresh-finite limits
A nominal poset is a tuple ) where () is a nominal set, and
— is an equivariant partial order.16
Say a nominal poset is finitely fresh-complete or has fresh-finite limits when:
— has a top element .
— has conjunctions (a greatest lower bound for and ).
— has -fresh limits , where is greatest amongst elements such that and supp() supp().
Say is finitely cocomplete17 or say it has finite colimits when:
— has a bottom element .
— has disjunctions (a least upper bound for and ).
Lemmas 4.1.3, 4.1.4, and 4.1.5 will be useful later:
If # then ().
, , , , and are unique if they exist.
Since for a partial order, and imply .
()().
Both the left-hand and right-hand sides specify a greatest element such that # and for 1.
.
Both the left-hand and right-hand sides specify a greatest element such that # and # and .
Suppose is a finitely fresh-complete nominal poset with a monotone -action. Then implies .
Suppose . By assumption and #. But then also and #, so .
We may write for .
4.2. More characterisations of fresh-finite limits
from Definition 4.1.2 is greatest in the set #. This is finitely supported but not strictly finitely supported. Definition 4.2.1 and Proposition 4.2.3 will characterise further as a limit of a strictly finitely-supported set.
This turns out to be important, and we use it in part 2 of Lemma 5.1.1, whose use in Lemma 5.2.3 is important for proving Proposition 5.2.6 (closure of under quantification).
Definition 4.2.5 and Proposition 4.2.7 then characterise in two ways: as a limit of a permutation orbit, and using the -quantifier. This ties to Proposition 5.2.8 and Remark 5.2.9 and to the opening discussion of Subsection 6.1. See also [Gab09b; GC11] and computational studies such as [BBKL12], with their emphasis on studying nominal sets in terms of their permutation orbits.
Suppose is a nominal poset and . Consider the set
Then write for the -greatest element of , if this exists. We call this the -strict limit of .
So:
— is the greatest beneath such that supp().
— is greatest beneath such that supp()supp().
It is not a priori evident that these two notions must coincide. However, they often do, as we will now show.
When they coincide, can be easier to work with than because it is the limit of a strictly finitely supported set, which have properties that finitely supported sets do not; see Lemma 2.4.3.
If exists then so does and they are equal.
Suppose exists. By construction supp()supp() and . Therefore (notation from Definition 4.2.1). Also by construction for every , since if supp() supp() then certainly #. It follows that is greatest in .
Recall from Notation 2.1.3 the definition of fix.
So we can rewrite this as follows:
— is the greatest beneath such that supp().
— Definition 4.2.5 specifies the greatest beneath and beneath () for every #.
Proposition 4.2.7 is needed for Proposition 5.2.8:
If is an element of a nominal poset and a greatest lower bound for exists in , then so does and they are equal, and vice versa.
As a corollary, if has fresh-finite limits then is greatest amongst such that ().
If exists then and #. It follows by equivariance and Corollary 2.1.10 that for every fix(supp().
Conversely suppose is greatest such that fix(supp()). Then is unique and by Theorem 2.3.1 supp() supp().
Now suppose has fresh-finite limits. Then and # so that by Corollary 2.1.10 ) (). Also, if () then is a lower bound for so that by the first part of this result, .
So we have seen three natural notions of ‘fresh-finite limit’ in nominal posets:
— Fresh-finite limits from Definition 4.1.2.
— Strict fresh-finite limits from Definition 4.2.1.
— Limits of permutation orbits.
By Proposition 4.2.7 the first and the third are identical, and by Proposition 4.2.3 the second one exists and is equal to the first (and the third) where the first exists. For a converse see Appendix A.2.
4.3. Compatible -structure
where and , where , , and exist.
Call the -action monotone when
Continuing Definition 4.3.1, if the -structure is compatible then it is monotone.
It is a fact that if and only if . The result follows.
Suppose is a nominal poset with a monotone -action, and suppose # for .
Then if then is a lower bound for [] , and as a particular corollary,
for every and .
By monotonicity [] [] for every . By (#) also []. The corollary follows just noting that by the definition of fresh-finite limit in Definition 4.1.2, and #.
#[]
We use part 3 of Corollary 2.1.10. Choose fresh (so #). Then we reason as follows:
Intuitively, universal quantification is an infinite intersection. Proposition 4.3.5 makes that formal for nominal posets:
Suppose is a nominal poset with a monotone -action (Definition 4.3.1), and suppose . Then:
(1) If exists then so does [] the limit for [] , and they are equal. In symbols:
(2) If [] exists then so does , and they are equal.
By Lemma 4.3.3 is a lower bound for [] .
Now suppose is any other lower bound, that is: [] for every . Note that we do not know a priori that #.
Choose fresh (so #) and take . Then [] (). Since # it follows that (). So [].
Now suppose that [] exists. By Lemma 4.3.4 and part 2 of Theorem 2.3.1 we have that # []. Also by assumption [] [] . Thus [] is an #lower bound for .
Now suppose and #; we need to show that []. This is direct from Lemma 4.3.3.
We also mention a characterisation of using a ‘smaller’ conjunction which does not depend on most of (see also Remark 5.2.9):
Suppose is a nominal poset with a monotone -action and . Then:
(1) If exists then so does [] where ranges over all atoms, and they are equal.
(2) If [] exists then so does , and they are equal.18
4.4. Definition of a nominal distributive lattice with
Suppose is a fresh-finitely complete and finitely cocomplete nominal poset. Call distributive when
Recall the notions of -algebra and termlike -algebra from Definitions 3.1.1 and 3.1.4:
Suppose and are -algebras. Call a pair of functions ) where and a (-algebra) morphism from to when:
(1) ( (so maps atoms to atoms).
(2) (() and (() (so is equivariant).
(3) ([()[()] and ([()[()] (so commutes with the -action).
If is termlike then we insist and we insist that .
We may omit the subscripts, writing for instance and , or even ), where the meaning is clear.
Suppose and are nominal distributive lattices with . Call a morphism ) : of underlying -algebras (Definition 4.4.4) a morphism of nominal distributive lattices with when commutes with fresh-finite limits and with finite colimits:
(1) (, and (()() and ((), and
(2) ( and (()().
Write nDi for the category of nominal distributive lattices with and morphisms between them.
4.5. Impredicative nominal distributive lattices
We are interested in modelling the -calculus, so we care about lattices where the substitution action is over itself. Therefore we introduce impredicative nominal distributive lattices with : this is Definition 4.5.1.
Recall the notion of termlike -algebra from Definition 3.1.1, and the notion of a nominal distributive lattice with from Definition 4.4.3.
So is impredicative when the things we substitute for—the in []— can be transferred over to the things we substitute in—the in [].
Given , we can obtain and so write (for instance) ()[]. This is not quite -calculus self-application, but we are moving in that direction.
It might help to break down the notation a little:
— injects into via an injection (this is the equivariant injection specified in Definition 3.1.1).
— maps to via .
— Thus we obtain —an atom-as-a-program—living in a sub--algebra of which is an image of , and which we call the programs of .
Lemma 4.5.5 is a routine sanity check that the definitions match up sensibly. It will be useful later:
Suppose is impredicative and . Then ()[.
Definition 4.5.1 can be looked at in some interesting ways:
— is impredicative when it has substitution [] over a substructure of itself.
— is impredicative when its quantifier quantifies over a sub--structure of . Thus, is the set of things we quantify over when we write , if is impredicative.
Note that the programs of need not be closed under the logical structure like , , and .
So for instance does not imply and it is not necessarily the case that , and so on. We do not forbid this either.
Suppose and are impredicative nominal distributive lattices with .
Call ) : a morphism in inDi when it is a morphism in nDi (Definition 4.4.5) and when in addition:
(3) . That is,
Definition 4.5.9 extends Definition 4.4.5:
Write inDi for the category of impredicative nominal distributive lattices with , and morphisms between them. As standard write inDi for “ is an impredicative nominal distributive lattice with ” and : inDi for “ inDi and is a morphism in inDi from to ”.
We continue the notation of Definition 4.5.9 and the discussion of Remark 4.5.4. Suppose : inDi is a morphism.
Note that ((). In informal words we can say that maps atoms-as-programs (Remark 4.5.4) in to themselves in . In symbols we can be even more brief:
We informally trace through how this happens. By condition 1 of Definition 4.4.4 maps an atom in to it incarnation in . By condition 3 of Definition 4.5.8 these are mapped to atoms-as-programs in and respectively.
5. THE -POWERSET AS A NOMINAL DISTRIBUTIVE LATTICE WITH
We saw in Proposition 3.4.9 how the nominal powerset of an -algebra generates a -algebra () (Definition 3.4.5). But powersets are also a lattice under subset inclusion, so perhaps () has more structure?
In fact, () is a nominal distributive lattice with (Definition 4.4.3). This is Theorem 5.2.10.
5.1. Basic sets operations
Suppose ) is an -algebra. Recall the definition of () from Definition 3.4.5.
Lemmas 5.1.1 and 5.1.2 are technical correctness properties of . The proofs are not entirely obvious, but they follow the same patterns of pointwise calculations on sets.
This subsection covers the simpler cases; in Subsection 5.2 we move on to quantification.
Suppose (). Then:
(1) If is strictly finitely supported (Definition 2.4.2) then
In words: commutes with strictly finitely supported sets intersections.
(2) If is strictly finitely supported then
In words: commutes with strictly finitely supported sets unions.
(3) For any ,
In words: intersections and unions are equivariant.
(4) If then [] []. In words: is monotone (Definition 4.3.1).
— and are in () and these are least and greatest elements in the subset inclusion ordering.
— If and are in () then so are and and these are greatest lower bounds and least upper bounds in the subset inclusion ordering.
We check the properties listed in Definition 3.4.5 for ; the case of is similar and the cases of and are even easier. We check that is a greatest lower bound for just as for ordinary sets. has finite support by Theorem 2.3.1.
(1) If is fresh (so #) then ()[ . By Lemmas 5.1.1 and 3.4.6 ( )[[]) ([ .
(2) If is fresh (so #) then ()[)(). We reason as follows:
5.2. Sets quantification
We now explore quantification. This is where we part company from Boolean algebras.
Suppose ) is an -algebra. Recall the definitions of pow() Subsection 2.4.1 and of () from Definition 3.4.5.
Definition 5.2.1 contains a wealth of structure. Clearly, this is our candidate for quantification over in (). But first, note that Definition 5.2.1 takes place in pow(), not (). This is the set of all finitely-supported subsets of , not the more restricted set of subsets forming a -algebra from Definition 3.4.5.
This is because it is easy to see that a set is in pow() (just from Theorem 2.3.1) and harder to prove that a set exists in (), because for a set to be in the latter it must satisfy two extra conditions (Definition 3.4.5) which are not trivial to prove.
So the proofs work by starting in pow(), then using Corollary 5.2.2 to present as a strictly finitely supported intersection, using that to prove Lemma 5.2.3,21 and then finally we promote the set from pow() to () in Proposition 5.2.6. The other main result of this subsection is Proposition 5.2.8, which gives useful alternative characterisations of Definition 5.2.1.
If pow() then
From Proposition 4.2.3.
Suppose pow() and and #. Then
Suppose (). Then
As a corollary, # and supp() supp().
If () then ().
Suppose (). Then is equal to in () considered as a nominal poset (Definition 4.1.1) under subset inclusion.
That is, is the largest element of ()#, and not just the largest element of pow()#.
By Proposition 5.2.6 is in (), which is a nominal poset. The result follows.
Because of Corollary 5.2.7, the set from Definition 5.2.1 can be characterised in several ways:
The following sets all exist and are equal to in ():
Above, ranges over all atoms, and may be equal to .
Proposition 5.2.8 converts a fresh-finite limit into a universal quantification ‘for all ’—and then into a universal quantification ‘for all atoms’ (line 2) and finally into a -quantifier ‘for all fresh atoms’ (line 4), both of which can be easier to handle than a universal quantification.
This is a theme of the nominal treatment of quantification; we saw it in Proposition 4.3.6, and we will see it again in Lemma 6.1.14.
This matters. Later on when we consider morphisms, we will need to know that a map in Proposition 8.2.2 commutes with . But can change the underlying termlike -algebra—that is, the domain of quantification can change. That would on the face of it interfere with the universal quantifier, because extra elements might appear that make a true universal quantification into a false one.
Proposition 5.2.8 says this cannot happen—or, to express the same mathematical fact in a different language, it makes formal that the notion of morphism used in Proposition 8.2.2 has to take any extra elements into account. In the language of [Sel02], Proposition 5.2.8 implies that our models are well-pointed.
A dedicated discussion of such issues in the context of nominal models of the -calculus is in [GM11, Subsection 3.4]. Also, compare this discussion with the definition of filter below in Definition 6.1.1.
Suppose is an -algebra. Then the -algebra () from Definition 3.4.5 naturally becomes a nominal distributive lattice with where , , , , and are interpreted as , set intersection , the empty set , set union , and .
This completes Part I. So far, we have defined nominal distributive lattices with and seen how to build them using nominal powersets. In Part II we show how to go from topologies (i.e. subsets of powersets subject to various sanity conditions, since powersets are usually very large) back to nominal distributive lattices with .
II. NOMINAL SPECTRAL SPACE REPRESENTATION
6. COMPLETENESS
The key definitions of this section are that of filter in Definition 6.1.1, and of an impredicative nominal distributive lattice with in Definition 4.5.1. The main result is a representation result, Theorem 6.4.4, which represents an impredicative nominal distributive lattice with as a set of sets of prime filters.
The key technical results are in the sequence Lemma 6.1.10, Proposition 6.1.12, and Theorem 6.1.13, which use Zorn’s lemma to exhibit every filter as a subset of some prime filter.
This story is familiar: it is standard to represent a lattice using sets of prime filters. However, making this work is not trivial. It is interesting to highlight three reasons for this:
(1) We must account for , of course. This is extra structure and our treatment uses properties of nominal sets and the -quantifier in subtle ways. See the discussion opening Subsection 6.1.
(2) Zorn’s Lemma is related to the Axiom of Choice, which can cause difficulties with nominal sets because it may lead to non-finite support (our definition of a nominal set from Definition 2.1.5 requires finite support).
We will find ourselves using elements which do have a permutation action—we are still within nominal techniques—but the elements do not necessarily have finite support. This is unusual. See Remark 6.1.3.
(3) Once these difficulties are navigated, we must still give points (prime filters) an -algebra structure. There is no reason to expect prime filters to behave well and support an -algebra structure. ‘By magic’, it just works: see Lemma 6.2.1.
A final technical hurdle is generated by our intended application of giving semantics to the untyped -calculus. In effect, this means that we want to consider lattices with a substitution action over themselves, in a suitable sense, whence the notion of impredicativity developed in Subsection 4.5. As usual for impredicative definitions, care is needed. Yet, once these definitions and results are in place, the main result Theorem 6.4.4 becomes quite natural.
6.1. Filters and prime filters
For this subsection, fix nDi a nominal distributive lattice with (Definition 4.4.3). Recall from Definition 4.4.3 that is a set with a finitely-supported permutation action, a -action (like a substitution action but abstractly specified as a nominal algebra), finite joins, fresh-finite meets, and satisfying a generalisation of the usual distributivity properties for lattices.
We start by defining our notion of (prime) filter, and proving that every filter is included in some prime filter.
The main definition is Definition 6.1.1 and the main result is Theorem 6.1.13. The main technical result is Lemma 6.1.10.
Condition 4 of Definition 6.1.1 is specific to the nominal filters. See also its verification in Lemma 6.1.10, in which is decomposed into and the permutation action —echoing Propositions 4.3.6 and 5.2.8. This decomposition of into and is important for two reasons:
— it converts an infinite conjunction over the entire domain into a -quantified assertion—the -quantifier has some excellent properties, such as commuting with conjunction and disjunction—and
— it does not depend on .
So condition 4 of Definition 6.1.1 means that to check the universal quantifier we do not need to know about all of the programs of . We just need to know about the atoms, and in particular, we just need to know about the fresh atoms.
This is familiar from proof-theory. To prove Γ we do not need to check [] for every term ; we just check [] for fresh .
A filter in is a nonempty subset (which need not have finite support) such that:
(1) (we say is consistent).
(2) If and then (we call up-closed).
(3) If and then .
(4) If () then .
The notion of prime filter is in Definition 6.1.11, and has no further surprises.
In fact, we shall see in Lemma 6.1.14 that condition 4 as written, implies both of these.
We do not assume that has finite support, so the bound by the -quantifier in condition 4 of Definition 6.1.1 need not necessarily be fresh for . So the reader familiar with nominal techniques should note that our use of is atypical. The ‘standard’ decomposition of into ‘+freshness’ and ‘+freshness’ familiar from e.g. Theorem 2.17 of [Gab11b], Theorem 6.5 of [Gab11a], or Theorem 9.4.6 of [Gab01] will not necessarily work here, at least not with respect to without finite support. Nevertheless, we have enough structure to obtain the results we need.
What is the case, is that is assumed to have finite support, and will be fresh for .
It will be important that we allow to have non-finite support; without this, we could not use Zorn’s lemma in Theorem 6.1.13.
A dual notion of Definition 6.1.1 will also be useful:
An ideal in is a subset (which need not have finite support) such that:
(1) .
(2) If and then (we call down-closed).
(3) If and then .
(1) If # and then .
(2) If # and () then .
(3) If # and (()) then .
— If then from Definition 6.1.6 is a filter.
— Conversely if then is an ideal.
Suppose . Then define:
So when for some .
The first two parts are clear. We now check that satisfies conditions 2 to 4 of Definition 6.1.1:
(2) If and then . By construction.
(3) If and then . Suppose and for . Then by condition 3 of Definition 6.1.1 , and it is a fact that ().
(4) If (()) then . Suppose for all but finitely many there exists an such that (). Then there certainly exists some such that # and (). We apply to both sides and use distributivity (Definition 4.4.1), and we conclude that
By Lemma 4.1.3 and condition 2 of Definition 6.1.1 we conclude that as required.
Recall from Definition 6.1.1 the notion of a filter:
— Call a filter prime when implies either or .
— Suppose is a filter and is an ideal, and suppose . Call maximal with respect to when for every filter with , if then .
— Call maximal when it is maximal with respect to the ideal .
Suppose is a filter and is an ideal, and suppose . If is a maximal filter with respect to then it is prime.
Suppose and . By Lemma 6.1.10 and maximality we have that () and () . It follows that there exist with . Since is an ideal,
Now we rearrange the left-hand-side to deduce that
We now note that (since , and indeed also ) and (since ) and (since ) and by assumption. But then , contradicting our assumption that .
Suppose is an ideal and is a filter and . Then there exists a prime filter with and .
As a corollary, if is a filter then there exists a prime filter containing .
The corollary follows taking to be , which we can easily verify is an ideal. We now consider the main result.
If is a chain in the set of filters ordered by subset inclusion, then is an upper bound for .23 By Zorn’s Lemma [End77, page 153] the set of filters such that and has a maximal element with respect to inclusion. By Proposition 6.1.12 is prime.
The following conditions are equivalent (below, ranges over all atoms, including ):
Suppose is a filter. Then:
(1) and .
(2) if and only if and .
(3) if and only if ().
(4) If is prime then if and only if or .24
6.2. The amgis-action on (prime) filters
For this subsection, fix nDi a nominal distributive lattice with (Definition 4.4.3).
Recall from Definition 3.3.1 the pointwise -action [[] where . In this subsection we check that this action preserves the property of being a (prime) filter (Definitions 6.1.1 and 6.1.11).
The work happens in the key technical result Lemma 6.2.1; Proposition 6.2.3 then puts the result in a some nice packaging.
If is a filter in then so is []. Furthermore, if is prime then so is [].
We check the conditions in Definition 6.1.1. We use Proposition 3.3.2 without comment:
— []. Since by (#) [.
— If [] and then []. From Lemma 4.3.2.
— If [] and [] then []. Since by assumption the -action is compatible, so ()[[]([]) (Definition 4.3.1).
— If (()[]) then []. Choose some fresh (so #). It is a fact that )(()) and by () also (). Thus, we may rename to assume without loss of generality that #.
Now suppose (())[] for all but finitely many ; so suppose #. By Corollary 2.1.10 (). Thus by Remark 3.1.2 and Corollary 2.1.10 we have that ()([]) for all but finitely many . Therefore ([]) and by compatibility (Definition 4.3.1) ()[] .
Now suppose is prime and suppose ()[] . Then by compatibility (Definition 4.3.1) []([]) . Therefore either [] or [] .
If nDi write points() for the -algebra determined by prime filters and the pointwise actions from Definition 3.3.1. That is:
points() is indeed an -algebra.
6.3. Injecting into the set of sets of prime filters
Recall from Definition 3.4.5 the notion of -powerset algebra , and from Definition 6.1.11 the notion of a prime filter.
In this subsection we consider how to embed a nominal distributive lattice with in the -powerset of its prime filters. The main definition is Definition 6.3.1. The main results are Lemma 6.4.2, Corollary 6.3.3, and Lemma 6.3.5.
It is standard to embed a lattice into sets of prime filters, and Definition 6.3.1 is has the form that one would expect. There is extra structure; for instance Lemma 6.4.1 and part 3 of Lemma 6.4.2. With the results we have proven so far, we can deal with this extra structure.
Suppose is a nominal distributive nominal lattice with . Define
a prime filter
if and only if .
The assignment is injective.
Direct from Lemma 6.3.2.
supp( supp().
Lemma 6.3.5 will be useful later but we prove it here because it has a family resemblance to Corollary 6.3.3 (see Remark 6.3.6). It expresses that “if all the ways of extending to a prime filter contain , then must already contain ”:
Suppose is a filter and , and suppose for every prime filter , if then . Then .
6.4. The map from , to prime filters containing , as a morphism
For this subsection, fix nDi a nominal distributive lattice with (Definition 4.4.3). Recall from Definition 6.3.1 that if then is the set of prime filters in that contain .
By Proposition 6.2.3 points() is an -algebra. So following Definition 3.4.1, sets of points points() inherit an action [[] . With this action we have the following:
Suppose and . Then:
(1)
(2)
The case of () is direct from Theorem 2.3.1 (a proof by concrete calculations similar to the case of [] is also possible). For the case of [], we reason as follows:
Parts 1, 2, and 4 just reformulate parts 1, 2, and 4 of Proposition 6.1.15.
For part 3, suppose (). By Definition 6.3.1 this is if and only if. By Lemma 6.1.14 this is if and only if [] for every . Using Definition 6.3.1 and Lemma 6.4.1 this is if and only if [] for every . We use line 2 of Proposition 5.2.8.
It is now easy to state and prove a nominal sets representation theorem, representing an abstract inDi concretely as the nominal sets-based structure :
If is in nDi then so is , and the pair of maps () is an isomorphism from to in nDi. If furthermore is in inDi (is impredicative) then so is and is an isomorphism from to .
Theorem 9.4.11 extends Theorem 6.4.4 with and .
7. NOMINAL -TOPOLOGICAL SPACES
7.1. The basic definition
A nominal -topological space is a tuple ( opens()) where
— () forms an -algebra (Definition 3.2.1) and
— opens()pow() (i.e. a set of finitely supported sets; see Subsection 2.4.1) is a set of open sets.
For clarity, we explicitly unpack what opens()pow() (Definition 3.4.5) means for opens():
(i) must have finite support.
(ii) # must imply that [.
(iii) # must imply that [).
Furthermore we impose the following conditions on opens():
(1) If opens() and () then opens() and [] opens() (where and [] are the pointwise actions from Definition 3.4.1).
(2) opens() and opens()
(3) If opens() and opens() then opens().
(4) If opens() is strictly finitely supported (Definition 2.4.2) then opens(); we call this a strictly finitely supported union of open sets.
As mentioned above, and [] mentioned in Definition 7.1.1 are the pointwise actions from Definition 3.4.1.
These are inherited from the permutation action and -action on the underlying points, using the fact that open sets are sets of points and points are delivered to us in Definition 7.1.1 as an -algebra. We spell this out for the reader’s convenience:
Topological spaces over Zermelo-Fraenkel (ZF) sets—that is, over ‘ordinary’ sets— are such that an arbitrary union of open sets is open.
Condition 4 of Definition 7.1.1 generalises that condition, because any ZF set is also naturally an FM set with the trivial permutation action, and with empty support; so arbitrary sets of ZF sets are already strictly finitely supported, by .
There are two natural generalisations of the topological condition to the nominal case: we could insist on finitely supported unions, or on strictly finitely supported unions. We used the first option in topological representations of first-order logic in [Gab12; Gab11b] and of the -quantifier in [GLP11].
In this paper, strict finite support seems to be required—we have not checked whether [Gab12; Gab11b; GLP11] would be re-done with this stricter condition. To see where it is used, the reader can search this paper for uses of Lemma 2.4.3, starting with the proof of Theorem 7.2.2.
The reader might be surprised that Definition 7.1.1 makes no mention of . Surely we should insist that if opens() then opens()?
We could do this and no harm would come of it. However, we can also leave to later, when we introduce coherence in Definition 7.4.1. We prefer this because it postpones complexity and increases the generality of the mathematics between now and then.
7.2. The map from distributive lattices to nominal -topological spaces
Suppose nDi is a nominal distributive lattice with .
References for technical definitions above: points() is from Definition 6.2.2, and the pointwise actions are from Definition 3.4.1. Strict finite support is from Definition 2.4.2 and is from Definition 6.3.1.
So opens(()) when where is a strictly finitely supported set of sets of points of the form .
If nDi is a nominal distributive lattice (Definition 4.5.1) then () is a -topological space.
We consider the properties in Definition 7.1.1 in turn:
(i) By assumption every has finite support, so by Corollary 6.3.4 and Lemma 2.4.3, so does every opens(()).
(ii) If # then [. Suppose #. By assumption for some strictly finitely supported union of . By Lemma 2.4.3 and Corollary 6.3.4 # for every so by (#) [. By Lemma 6.4.1 ([]) . We use part 4 of Lemma 6.4.2.
(iii) If # then [). Suppose #. By assumption for some strictly finitely supported union of . By Lemma 2.4.3 and Corollary 6.3.4 # for every so by Lemma 3.2.3 [). By Lemma 6.4.1 (()) ). We use part 4 of Lemma 6.4.2.
Furthermore:
(1) If opens(()) and () then opens(()) and [] opens(()). The case of is direct from Theorem 2.3.1. For the case of [] we note that by definition is equal to some strictly finitely-supported union . We then use Lemma 5.1.1 and part 3 of Definition 6.4.3.
(2) is open by construction and points().
(3) Suppose opens(()). So and for some strictly finitely supported sets . By Theorem 2.3.1 supp() supp() supp(). Thus using part 2 of Lemma 6.4.2 and some elementary sets calculations () and this is a strictly finitely supported union.
(4) If opens(()) is strictly finitely supported then opens(()). Using Corollary 2.4.5.
7.3. Compactness
7.3.1. The definition, and general properties.
Fix a nominal -topological space.
Suppose opens() and opens().
— Say covers when is strictly finitely supported and . Call a cover when it covers .
— Call compact when every cover of has a finite subcover. Write cpct() for the set of compact open sets of :
cpct( opens() is compact
Proposition 7.3.2 looks familiar enough, but we are in a nominal context so we have to check facts about support. It all works:
Suppose cpct(). Then:
(1) is compact.
(2) is compact.
(3) is compact.
(1) There are two covers of : the empty set of open sets and the set containing the empty set of points. Both are finite.
(2) Suppose and are compact and covers . Then covers . By Lemma 2.4.3 and Theorem 2.3.1 supp() supp()supp() for each . Thus
covers and is strictly supported, and we obtain a finite subcover of . Reasoning similarly for we obtain a finite subcover of . Putting these two finite subcovers together, we obtain one of .
In a sense, Definition 7.4.1 is a continuation of Proposition 7.3.2.
7.3.2. The specific case of ().
Fix some nDi.
Suppose is a strictly finitely supported set of open sets in (). Then
Suppose cpct(()) and . Then if covers then so does
From Lemma 7.3.3 covers .
If cpct(()) then define by
Continuing the notation of Definition 7.3.5, if and only if .
Given write for the least set such that:
— If then .
— If then .
— If and then .
Similarly write for the least set such that:
— If then .
— If then .
— If and then .
Intuitively, is trying to be the least ideal (Definition 6.1.4) containing ; it may fail to be an ideal if . Similarly, is moving in the direction of being a filter (Definition 6.1.1) containing ; it may fail to be a filter if either , or () and .
Suppose . Then is open and compact in ().
is open by construction in Definition 7.2.1.
Now consider a cover of . By Lemma 7.3.4 we may assume without loss of generality that every element of has the form for some . Write
Recall from Definitions 7.3.5 and 7.3.7 that ‘strips the - from the elements of ’ and - ‘tries to make a filter’ out of its argument.
We observe using Lemma 7.3.6 and some routine calculations that has a finite subcover if and only if .
We now observe that satisfies conditions 2, 3, and 4 of Definition 6.1.1:
(2) is up-closed. By the use of -.
(3) and imply . By the use of -.
(4) If (()) then . Choose fresh (so #), so there exist for 1 and such that for 1, and (). Now # and the cover is assumed to be strictly finitely supported, so by Lemma 2.4.3 and Corollary 6.3.4 also # for 1. By part 3 of Lemma 6.1.7 for 1. Also, using Lemma 4.1.5 (). It follows using Lemma 4.1.3 that .
It is now useful to consider two distinct possibilities: () or (). We treat each in turn:
— Suppose (). So take any (). Since (), there exist with . Since , there exist and such that for 1 and . We note that ()() and by some easy calculations that
Thus, using part 4 of Lemma 6.4.2 and Lemma 6.3.2 we have that () () covers .
— Now suppose (). In particular , so by the arguments above is a filter, and (), so () is an ideal. By Theorem 6.1.13 for some prime filter such that (). It is easy to check that , so by Definition 6.3.1 . Since covers , there must exist some with , that is, . But our assumption that () implies that , contradicting that and (by Lemma 7.3.6) .
There is something a little odd about the proof of Proposition 7.3.8.
Why did we define using - but introduce - only half-way through the proof? The key detail occurs when we verify that () implies (case 4 in the proof above). There, we use the fact that # implies # for every with . This only follows because (and therefore ) has strict finite support.
Now () does not have strict finite support in general, since does not imply supp() supp() in general. Thus we delay its introduction until the second half of the proof, after we have picked .
Remark 7.2.3 discusses why we introduced strict finite support in the first place. So here in the proof of Proposition 7.3.8, we just have to be a little cautious to only lose the strict finite support property of after we have constructed .
A converse to Proposition 7.3.8 also holds:
If is open and compact in () then for some unique .
7.4. Coherent spaces: closure under , and #
Coherence usually means that the compact open sets are closed under lattice operations and generate all open sets via sets unions. Our lattices have more structure (notably: a -action and ). Also, our notion of ‘generating’ open sets has some nominal aspects to it.
Definition 7.4.1 is how we extend the notion of coherence to account for this structure. Proposition 7.4.3 then checks that from Definition 7.2.1 does indeed generate coherent spaces.
Call a nominal -topological space coherent when:
(1) If is open and compact then so is [] for every .
(2) is (open and) compact.
(3) If and are open and compact then so is .
(4) If is open and compact then so is .
(5) Every open opens() is equal to for some strictly finitely supported cpct().
We rewrite Definition 7.4.1 in less precise, but more intuitive language:
(1) Compactness is closed under the -action.
(2) Compactness is closed under sets intersection.
(3) Compactness is closed under universal quantification.
(4) Compact open sets are a strictly finitely supported (Subsection 2.4.2) basis for all open sets.
Suppose nDi. Then () (Definition 7.2.1) is coherent.
By Propositions 7.3.8 and 7.3.10 we can identify the compact open sets of () with sets of the form for . We now reason as follows:
(1) By Lemma 6.4.1 [[]).
(2) By part 1 of Proposition 6.1.15 () (every point contains ).
(3) By part 2 of Lemma 6.4.2 ).
(4) By part 3 of Lemma 6.4.2 () .
(5) By construction in Definition 7.2.1 open sets are strictly finitely supported unions of the .
7.5. Impredicativity
We saw in Subsection 4.5 and Definition 4.5.1 a notion of impredicativity, based on the idea that the things we substitute for should map to the things we substitute in. In the context of a topological space, this means that should map to open sets. This is Definition 7.5.2, and Theorem 7.6.2 shows how () inherits any impredicative structure of .
We note an easy corollary of Definitions 7.1.1 and 7.4.1:
Suppose is a nominal -topological space. Then opens() inherits a -algebra structure over .
If is coherent, then also cpct() inherits a -algebra structure over .
We can think of Definition 7.5.2 as a dual to Definition 4.5.1, for the nominal -topological spaces from Definition 7.1.1:
The exposition in and following Notation 4.5.3 is also valid here, so we do not repeat it.
If inDi (so is impredicative) then () is also naturally impredicative.
We take () and ). (In fact, this is an injection by Theorem 6.4.4.)
7.6. The map from coherent spaces to distributive lattices
Suppose is a coherent (Definition 7.4.1) nominal -topological space.
Continuing Definition 7.6.1, if is coherent then () is a nominal distributive lattice with .
Furthermore, if is impredicative then so naturally is ().
If nDiinDi then () is equal to from Definition 6.4.3, and the map is an isomorphism in nDiinDi.
7.7. Sober spaces
Call a nominal -topological space sober when if opens() is completely prime then there exists a unique such that
Definition 7.7.2 is the standard notion of sobriety, and states intuitively that completely prime filters characterise the underlying points of the space. For the case of coherent spaces, a slightly more economical characterisation is possible and will be useful:
If is coherent then the completely prime filters of open sets are in a natural bijection with the filters of compact open sets, with the bijection given by:
— A completely prime filter opens() corresponds to cpct().
— A prime filter cpct() corresponds to opens() , the up-closure of in opens().
Suppose is a completely prime filter in opens(). By part 2 of Proposition 7.3.2 compactness is closed under finite unions and it follows that is a prime filter in cpct().
Conversely suppose cpct() is a prime filter. We will show that is completely prime. Suppose opens() is strictly finitely supported and suppose , so that for some . But this just states that covers , and by compactness has a finite subcover . It follows that . Since is prime it follows that for some , and therefore that .
It is routine to verify that since is coherent, the correspondences between and defined above are bijective.
Recall from Definition 7.2.1 that if inDi then () is the set of prime filters in .
If Top is coherent (Definition 7.4.1) then is a prime filter in (), and so it is an element of ().
Suppose Top is coherent and sober. Then is a prime filter in () if and only if for some , and that is unique.
As a corollary, the map is a bijection between and ().
If Top is coherent then is sober if and only if the map () (a point maps to the prime filter of compact open sets containing it) is a bijection.
Recall the definitions of , , and from Definitions 6.3.1, 7.7.4, and 7.3.5 respectively.
Suppose nDi. Then:
(1) If () then () .
(2) If () then ().
As a corollary, () is sober.
7.8. Nominal spectral spaces
If nDi then () (Definition 7.2.1) is spectral. If inDi then () is impredicative and spectral, that is, () is a nominal spectral space.
8. MORPHISMS OF NOMINAL SPECTRAL SPACES
8.1. The definition of inSpect, and viewed as a functor to it
We see from Definition 7.6.1 that we obtain a nominal distributive lattice with from an impredicative nominal spectral space by taking the lattice of compact open sets.
A spectral morphism usually taken to be a map of points whose inverse preserves the property of being compact. Our compact sets have permutation and -actions (and our points have permutation and -actions) so we need morphisms to interact appropriately with this extra structure. This is Definition 8.1.1.
Then, we extend from Definition 7.2.1 to act on morphisms, and check that this does indeed yield a functor. This is Definition 8.1.5 and Proposition 8.1.8. Theorem 8.1.9 packages this all up into a theorem.
Suppose and are nominal spectral spaces (Definition 7.8.1).
Suppose . Then:
— Call continuous when opens() implies () opens() (inverse image of an open is open).
— Call spectral when cpct() implies () cpct() (inverse image of a compact open is compact open).
Call ) a morphism from to , and (dropping subscripts) write ) : when:
(1) is equivariant, meaning that (().
(2) is continuous and spectral, and is a -algebra morphism (Definition 4.4.4) from to . So goes from to but goes from to .
(3) maps atoms-as-programs to themselves, meaning that ( for every atom .
(4) commutes with the -action, meaning that for and
(See Lemma 8.1.3 for another view of this condition.)
Write inSpect for the category of nominal spectral spaces, and morphisms between them.
Lemmas 8.1.2 and 8.1.3 are direct derivatives of condition 4 of Definition 8.1.1:
If : then for and , ()[([]).
Suppose . Then:
We take a moment to note an interaction of Lemma 8.1.3 with condition 3 of Definition 8.1.1:
maps programs to programs, meaning that ( for every .
Definition 8.1.5 extends Definition 7.2.1 from objects to morphisms:
We now work towards proving that () maps points to points in Proposition 8.1.8.
Suppose ) : is a morphism in inDi and suppose . Then ()-1(()).
We reason as follows, where points():
Suppose : is a morphism (Definition 4.5.8). Then if is a filter then so is ()( -1(), and if is prime then so is -1().
Suppose is a filter. We check the conditions of Definition 6.1.1 for -1(), freely using the fact that -1() if and only if () :
(1) -1(). By assumption in Definition 4.4.5 (, and by condition 1 of Definition 6.1.1 .
(2) -1() and implies -1(). Immediate.
(3) -1() and -1() implies -1(). Since (()().
(4) If (() -1()) then -1(). Suppose () -1(). It follows from Definition 4.4.5 that ()(), so by condition 3 of Definition 6.1.1 () . By Definition 4.4.5 again ((). The result follows.
Now suppose is prime and suppose -1(), so that () . From Definition 4.4.5 we have ()() . Since is prime, either () or () .
By Lemma 8.1.7 () maps prime filters of to prime filters of —that is, ( ()().
Now we show that () is a morphism. We verify the properties of Definition 8.1.1. By definition () which by construction is a -algebra morphism from to . Also:
(1) () is equivariant. We briefly sketch the reasoning; in step () we use condition 1 of Definition 8.1.1 for :
(2) ()-1 is continuous and spectral. We must prove two things:
— ()-1 maps open sets to open sets. By construction ()-1 preserves unions, and by construction every opens(()) is a strictly finitely supported union for . By Lemma 8.1.6 ()-1(() and by Corollary 6.3.4 and Theorem 2.3.1 supp(()) supp() for every . It follows that ()-1(() and this is a strictly finitely supported union and so is open in ().
— ()-1 maps compact sets to compact sets. By Lemma 8.1.6 ()-1((). We use Propositions 7.3.8 and 7.3.10.
(3) ()-1 maps atoms-as-programs to themselves. By Lemma 8.1.6 ()-1(()()) and by assumption in Definition 4.5.8 (.
(4) () commutes with the -action. Suppose () and () and . Following Theorem 7.5.4 () so . We reason as follows:
8.2. The action of on morphisms in inSpect
In Subsection 8.1 we went from inDi to inSpect. Now we go back.
So Definition 8.2.1 mapping inSpect to inDi is the dual to Definition 8.1.5 mapping inDi to inSpect:
By Theorem 7.6.2 maps objects of inSpect to objects of inDi.
Now consider a morphism : in the sense of Definition 8.1.1; the interesting part is to check that (—that is, —is a morphism in the sense of Definition 4.5.8.
We may drop subscripts henceforth. If cpct(), so is compact, and since is assumed spectral in Definition 8.1.1 we know () is also compact. It is routine to check that preserves the top and bottom elements ( and respectively) and interacts correctly with intersections and unions.
It remains to show that is equivariant, commutes with the -action, and commutes with . Equivariance, meaning that ((), is immediate by Theorem 2.3.1 (a proof by concrete calculations using Proposition 3.4.2 and condition 1 of Definition 8.1.1 is also possible). Commuting with the -action, meaning that ()[(([]), is Lemma 8.1.3.
Finally we check that commutes with :
Thus () is a morphism in inDi.
Notice of the last case above that we prove a property of an infinite intersection using its characterisation as a universal atoms-quantification; we can do this thanks to Proposition 5.2.8, and it makes the proof much easier.
8.3. The equivalence
In Subsections 8.1 and 8.2 we considered two functors : inDi inSpect and : inSpect inDi. They are dual; the key is to observe that () is isomorphic to . This is Lemma 8.3.1 and Proposition 8.3.2. Theorem 8.3.3 puts it all together.
We reason as follows:
Recall from Definitions 7.2.1 and 7.6.1 that () is a topological space whose points are prime filters of compact opens in .
If inSpect then mapping to () defines an isomorphism in inSpect between and ().
Injectivity and surjectivity are Corollary 7.7.6. Commutativity with the -action is Lemma 8.3.1, as can be checked by unravelling definitions.
We also need to show that is continuous. The reasoning is standard [BS81, Section 4] so we just sketch it. First, if () (so is a compact open set of ) consider the inverse image under - of .26
Thus, (.
Now by construction any open set in () is a union of , and it is a fact that the inverse image function preserves these unions. It follows that the inverse image of an open set is open.
: inSpect inDi defines an equivalence between inDi and inSpect.
We use [Mac71, Theorem 1, Chapter IV, Section 4].
— is essentially surjective on objects. This is Proposition 7.6.3.
— is faithful. Suppose inSpect and ; the interesting case here is then that there exists such that () (). ( and leave programs unchanged, so we can elide and .) By assumption is coherent and sober, so that by Lemma 7.7.7 () and ()—these are the sets of compact open sets in containing () and () respectively—are not equal. Thus there exists a compact open set opens() with () and () . Examining Definition 8.2.1 we see that ()() and ()(). Thus, () ().
— is full. Given in inSpect and : () () in inDi we construct a morphism : in inSpect such that (. By Proposition 8.3.2 : () mapping to is an isomorphism in inSpect. Set () . By routine calculations we can check that ()(() for every ().
III. ADDING APPLICATION AND ITS TOPOLOGICAL DUAL THE COMBINATION OPERATOR
So far we have seen inDi and inSpect, and Theorem 8.3.3 is a topological duality theorem relating them. This is in itself an interesting result: duality for an impredicative propositional logic (propositional logic with quantifiers over propositions; the reader might be familiar with this kind of logical system in the form of the type system of System F [GTL89]).
However, to model the -calculus we need more structure. This is developed in Section 9, and our results so far are extended accordingly—culminating in Subsection 9.6 with Theorem 9.6.6.
9. INDI AND INSPECT
9.1. Adding and to inDi to get inDi
We extend the notion of an impredicative nominal distributive lattice with from Definition 4.5.1 with two equivariant operators : () and : () , written infix as and . They must be adjoint as described in Figure 2, and they must be compatible as described in Figure 3 (the notation is from Notation 4.5.3).
() is an inequality, not an equality. This seems odd, given that () is an equality; is not intuitively an infinite conjunction or a fresh-finite limit? The reason is that this reflects the inequality in Lemma 9.1.9 below. To see how this works, we refer the interested reader to the case of () in Lemma 9.6.3.27
() might seem odd: why and not ? The precise technical reason is in Proposition 11.6.4; the form is what we prove of our canonical syntactic model .
We package our definitions up as a category:
We conclude with technical lemmas concerning the interaction of and with and the -action. For the rest of this subsection we fix inDi and and .
(1) If then .
(2) If then .
It is a fact that if and only if . We reason as follows:
(1)
if and only if .
The reasoning is standard:
— If then () L.
— If then ().
()[] [][].
We reason as follows:
9.2. The combination operator : a topological dual to and
In Subsection 9.1 we extended inDi with extra structure of and .
We can expect this to be reflected in the topologies by some kind of extension with a structure dual to and .28
What should dually correspond to and ? Remarkably, this requires only a little more structure on points: see the combination operator in Definition 9.2.1.
9.2.1. The basic definition.
Recall the finitely supported powerset pow(-) from Subsection 2.4.1.
We define an -algebra by extending the notion of -algebra from Definition 3.2.1 with an equivariant combination operator
written infix as .
An -algebra is just an -algebra with an equivariant combination function mapping pairs of points to sets of points. We now outline how the notion of spectral space is enriched by assuming (Definition 9.2.1) on its points.
We extend Definition 7.1.1:
9.2.2. and , and spectral spaces.
Extend Definition 3.4.1 as follows:
Continuing the notation of Definition 9.2.3, define by
can be conveniently rewritten using Definition 9.2.4 as
We can extend Proposition 3.4.2 to reflect the structure created by the combination action :
We extend Definition 7.4.1 to account for the extra structure:
Call a nominal -topological space with coherent when it is coherent in the sense of Definition 7.4.1 and in addition:
(5) If and are open and compact (so cpct()) then so are and .
(6) If cpct() then ()[[][] (so cpct() satisfies ()).
(7) If cpct() then ()[([]) (so cpct() satisfies ()).
Suppose is a nominal -topological space (Definition 9.2.2) and . Then:
— opens().
— If furthermore is coherent and cpct(), then cpct() .
Consider opens() and .
By Lemma 9.2.5 for any ( is from Definition 9.2.4). It follows from Definition 9.2.3 that . Conversely if then by Definition 9.2.3, for every , and thus by Lemma 9.2.5 also for every . So .
By the first part, opens() . If in addition is coherent then if cpct() then cpct() and so is one of the such that , so opens() .
Definition 9.2.9 extends Definition 7.8.1:
We extend the notion of morphism : of nominal spectral spaces from Definition 8.1.1 to insist that the inverse image should commute with and in the following sense:
— If cpct() then (()().
— If cpct() then (().
Write inSpect for the category of nominal spectral spaces with (Definition 9.2.9), and morphisms between them whose inverse image functions commute with and , as described above.
9.2.3. Useful technical lemmas.
We conclude with a pair of useful technical lemmas:
— ()(().
—
— If and then .
By elementary sets calculations on Definition 9.2.3.
The adjoint axioms () and () from Definition 9.1.1 are valid. That is, for :
9.3. Filters in the presence of and
The notions of filter and ideal from Definitions 6.1.1 and 6.1.4 do not change with the addition of and . This is very convenient, because it leaves unaffected the ‘logical’ structure studied previously to Section 9 and the theorems we proved so far, still hold.
However, the addition of and adds structure, which gives us useful new ways to build extra filters, which we explore in Lemmas 9.3.3 and 9.3.4 and in Proposition 9.3.7.
Fix some inDi (Definition 9.1.6).
If is a filter in then define by
is not necessarily a filter, but the notation will be useful nonetheless.
Lemmas 9.3.3 and 9.3.4 clearly belong to the same family as Proposition 6.1.12. We need them for the proof of Theorem 9.4.7, where at a certain point we have assumed (); we will use Lemmas 9.3.3 and 9.3.4 to generate prime filters and with and , and we use that to conclude that .
Suppose and are filters in and is an element in . Suppose is prime and suppose is a maximal filter such that .
Then is prime.
Suppose and .
By maximality () and (). It follows that there exist such that () and such that (). Since is prime, it follows that
Now we rearrange this to
Now by assumption (since , and indeed also ), and (since ) and (since ) and . Since we assumed that , it follows that , a contradiction.
Suppose , , and are filters in . Suppose is prime and suppose is maximal such that .
Then is prime.
Suppose and .
By maximality () and () . It follows that there exist and such that () , and and such that () .
Since is a filter, . For simplicity write . By part 1 of Lemma 9.1.7 and condition 2 of Definition 6.1.1 for it follows that
and since is prime we have
and so using () and writing the left-hand-side as we have
Now we rearrange this to
By assumption and by assumption . Furthermore by assumption . It follows that , a contradiction.
A justification for the notation is Lemma 9.3.6, which exhibits as a kind of dual to :
if and only if .
Routine from Definition 9.3.5.
We consider the conditions in Definition 6.1.1 for , freely using Lemma 9.3.6:
(2) If and then . If then . By part 2 of Lemma 9.1.7 and condition 2 of Definition 6.1.1 for we have , and so .
(3) If and then . Suppose , so that . Therefore ()() and by () () . Thus .
(4) If () then . We note that for fresh (so #)29 if # then by Corollary 2.1.10 ())(()) and by Lemma 4.1.3 (). So using Proposition 2.3.3 we may assume without loss of generality that #. Now suppose (). By Lemma 9.3.6 (()), and by Lemma 2.3.5 (for the equivariant function ) ()() . By condition 4 of Definition 6.1.1 ()
, thus by () and condition 2 of Definition 6.1.1 and so by Lemma 9.3.6 .
So might fail to be a filter if , but if then is indeed a filter.
9.4. The second representation theorem
We now show how to build -algebras with (recall from Subsection 9.2 that is the topological dual to application ).
For the rest of this subsection fix some inDi (Definition 9.1.6). Recall the definition of from Definition 6.3.1.
The first two clauses of Definition 9.4.1 echo Definition 3.3.1; the third gives prime filters a action in the sense of Definition 9.2.1:
Give prime filters and in actions as follows:
Prime filters of form an -algebra with in the sense of Definition 9.2.1.
We now work towards Proposition 9.4.6, which will be needed for Theorem 9.4.7. Definition 9.4.3 will be useful:
Suppose and are prime filters in and . Define by
is a useful technical notation for Proposition 9.4.4, which extends Proposition 3.3.2:
Suppose is a prime filter in . Then:
(1) if and only if .
(2) if and only if .
It will be convenient to package a few definitions and part of Proposition 9.4.4 into a technical corollary:
if and only if ().
Suppose is a prime filter in . Then if and only if .
We prove two implications.
The right-to-left implication. Suppose and suppose . We need to show that .
By Corollary 9.4.5 means that for some with it is the case that . So given some such , since we have that (). By () () and since is up-closed (condition 2 of Definition 6.1.1) we have , thus by Definition 6.3.1 as required.
The left-to-right implication. Suppose ; so if is a prime filter and , then . We need to show that .
Consider from Definition 9.3.5. If is not a filter then by Proposition 9.3.7 and so by Lemma 9.3.6 . Thus by Lemma 9.1.7 as required.
So now suppose is a filter. By Corollary 9.4.5 when for some with we have .
Take to be any prime filter containing ; at least one such exists, by Theorem 6.1.13. By Corollary 6.1.8 is a filter, and from Lemma 9.3.4 there exists a prime filter with and . Also . So we have some with and , so by assumption .
Now the reasoning of the previous paragraph holds for any prime containing . That is, for any prime with it is the case that .
It follows by Lemma 6.3.5 that , and so by Lemma 9.3.6 that as required.
Theorem 9.4.7 extends Lemma 6.4.2 for the additional structure of and :
Suppose inDi and . Then:
(1)
(2)
We consider each part in turn.
By Proposition 9.2.6 if and only if (), and by Proposition 9.4.4 this is if and only if () .
So suppose there exist prime filters and with and and . Then clearly . Conversely suppose for some prime filter . By Corollary 6.1.8 is a filter and it follows from Lemma 9.3.3 that there exists a prime filter with and . Also by Corollary 6.1.8 is a filter and from Lemma 9.3.4 there exists a prime filter with and .
For the second part we reason as follows, using Proposition 9.2.6 and Proposition 9.4.6:
We can now easily extend Definition 6.4.3 (the definition of ):
So Definitions 6.4.3 and 9.4.8 overload the notation for “the object in inDi composed of prime filters of inDi” and “the object of inDi composed of prime filters of inDi”. The meaning will always be clear.
Suppose and . Then () and () are valid in :
We reason as follows:
The adjoint and compatibility axioms from Definition 9.1.1 are valid in . That is:
Recall the definition of inDi from Definition 9.1.6.
If inDi then from Definition 9.4.8 is in inDi, and the assignment is an isomorphism in inDi between and .
9.5. Construction of the topological space (), with and
Recall the definitions of inDi and inSpect from Definitions 9.1.6 and 9.2.10. We extend Definition 7.2.1:
In Definition 9.5.1 we claim that () is a nominal spectral space with (Definition 9.2.9). This needs to be proved: Theorem 9.5.3 assembles the various verifications.
Recall from Definition 8.1.5 the map from : to () : () ().
Theorem 9.5.3 extends Theorem 8.1.9 from inDi and inSpect to inDi and inSpect:
is a functor from inDi to inSpect.
Part 1 of Proposition 9.5.2 is stated only for sets of the form and . In fact, we note that it can be extended to all opens(()):
()-1(()-1()()-1() for all opens(()) (and not only cpct(())).
Corollary 9.5.4 would not work for , because a result corresponding to Lemma 9.2.11 does not hold for it.
9.6. The duality, in the presence of and
It is routine to extend Definition 7.6.1—which sends a spectral space to the lattice of its compact open sets ()—and Definition 8.2.1—which sends a spectral map to its inverse image function (—to the case where we also assume and . We write it out, just to be clear:
Given : inSpect from Definition 9.2.10, define () : () () by ()( ().
Continuing the notation of Definition 9.6.1, suppose () and suppose (). Then
If inSpect then () validates the axioms from Definition 9.1.1.
We consider each axiom in turn. We take cpct() (open compacts in ):
— Axioms () and (). By assumption in Definition 9.2.7.
— The adjoint axioms () and (). Direct from Lemma 9.2.12.
— Axioms () and () ...are Lemma 9.2.11.
— Axioms (). If () then for some and . It follows that for and and for and , and therefore () (). The second () axiom follows similarly.
— Axiom (). Suppose # and (). It follows by Lemma 9.2.11 that [] for every . Now by part 1 of Lemma 3.4.6 and condition 6 of Definition 9.2.7, [])[]. So ()[] for every , and by line 2 of Proposition 5.2.8 also ().
— Axiom (). From Lemma 9.6.2.
— Axiom (). () () means or . In either case, and this means ().
— Axiom (). Suppose #. We reason as follows:
from Definition 9.6.1 is a functor from inSpect to inDi.
We checked in Proposition 9.5.2 that this is true for ()-1, so we can extend Proposition 7.6.3:
If inDi then () is equal to from Definition 9.4.8, and the map is an isomorphism in inDi.
It is routine to check that the and structure is orthogonal to the material of Subsections 8.2 and 8.3, and so we obtain Theorem 9.6.6:
: inSpect inDi defines an equivalence between inDi and inSpect .
Theorem 9.6.6 exhibits inDi and inSpect as dual to one another. This is a general result—the abstract nominal algebra structures in inDi correspond dually to concrete topological spaces in inSpect.
It remains to show how inDi and inSpect relate specifically to the untyped -calculus.
IV. APPLICATION TO THE -CALCULUS
10. THE -CALCULUS
In this section we sketch the untyped -calculus and show how it has been living inside inDi all along: this is in Notation 10.2.1. We make formal that Notation 10.2.1 is ‘a right thing to do’ with Proposition 10.2.4, Definition 10.4.1, and Theorem 10.4.7.
We also briefly unpack what is when is an open set in the topological representations in inSpect. This is Proposition 10.2.6.
Thus, we leverage our topological duality to give both abstract and concrete (i.e. nominal poset flavoured and nominal sets flavoured) semantics for the of the untyped -calculus.
10.1. Syntax of the -calculus
Consider -terms as a nominal set (Definition 2.1.5) by giving them the natural permutation action:
Write LmTm for the nominal set of -terms with this permutation action.
It is a fact that with the permutation action above, fa() the free atoms of and supp() the atoms in the support of , coincide.
Consider -terms as a termlike -algebra (Definition 3.1.1) by setting
so that [] acting on is ‘ with substituted for ’.
It is a fact that this does indeed determine a termlike -algebra. The nominal algebra axioms of Figure 1 reflect valid properties of capture-avoiding substitution on -terms.
10.2. , , and using adjoints
In objects of inDi, -abstraction arises naturally by combining the ‘logical’ structure and with the ‘combinational’ structure of and ; this is Notation 10.2.1. We shall see that -reduction and -expansion arise as natural corollaries of the adjoint properties of and ; this is Proposition 10.2.4.
Proposition 10.2.6 unpacks what this means in (), and Definition 10.4.1 and Theorem 10.4.7 show how we can interpert the full untyped -calculus.
10.2.1. using and .
If # then ()[([]).
We now derive -reduction and -expansion from the counit and unit axioms () and () respectively:
We consider each part in turn.
(1) Unfolding Notation 10.2.1 we have () (()). Renaming using Lemma 4.1.3 if necessary, assume # so that by Theorem 2.3.1 also #. By () (())(()). By Lemma 4.3.3 (()) (())[]. By Lemma 9.1.9 and () and (#), (())[] (([])). By () (([]))[].
(2) Suppose #. Unfolding Notation 10.2.1 ((()). By () (), so by Lemma 4.1.7 (()). Since #, is its own -fresh limit, that is, .
inDi gives a model of -reduction and -expansion. The reverse inclusions do not follow, but they are not forbidden:
— There exist models such that [] () (so that we do not have -equality) and # for some and yet () .
— There also exist models such that [) and for all , # implies (. To obtain one, choose any -equality theory Π (Definition 10.3.7; -equality would do here) and construct from Definition 11.1.3 and the subsequent constructions.
10.2.2. as a sets operation in ().
We take a moment to perform a sanity check by examining (Notation 10.2.1) for the specific case of the sets representation () (Definition 9.5.1) of inDi.
Suppose inDi, opens(()), and (), and let range over elements of (), which are prime filters in . Then for every ,
Recall the unpacking of from Remark 10.2.2. We reason as follows:
10.3. Idioms
It is convenient to generalise -syntax a little. Recall from Definition 3.1.1 that a termlike -algebra expresses in nominal algebra the property of ‘having a substitution action over itself’.
A (-)idiom is a termlike -algebra equipped with two further equivariant functions
such that for all and and :
(1) # (this justifies quantifier notation: abstracts the atoms argument ).
(2) If # then ()[:]([:]).
(3)
(4) If then , and .
Above, we use the fact that because is a termlike -algebra, it interprets atoms as atm() and as a -action [:].
The canonical example of a -idiom is LmTm; -terms up to -equivalence, with their natural substitution, application, and -actions.
In what follows, what the variables, substitution, application, and of an idiom have to be, will always be clear. For the rest of this section fix some -idiom .
We call elements of phrases. We let and range over phrases in , and also and range over phrases in .
Phrases of a -idiom ‘look like’ terms of -syntax up to -equivalence, inasmuch as they must support variables, substitution, a binary operator which we suggestively call application, and a variable-abstractor which we suggestively call . However, we do not insist that phrases be -terms; they need not even be syntax. They just have to support nominal algebraic models of variables, substitution, application and a -abstraction. Nothing about the constructions that follow immediately below depends on being syntactic.
Suppose is a -idiom. Call an equivariant preorder on phrases compatible when for all and :34
(1) If and then .
(2) If then .
(3) If then [:] [:].
(4) ()[:]. This is -reduction.
(5) If is not free in then (). This is -expansion.
A -reduction theory is a compatible preorder on an idiom , and a -equality theory is a compatible equivalence relation on .35 Π will range over -reduction theories.
If Π is a -reduction theory then we may write or Π or () Π for Π .
If Π is a -equality theory, so that Π is an equivalence relation, then we may write or Π or () Π for Π .
10.4. A sound denotation for the -calculus
Any inDi has the structure of , , and , so we can immediately interpret the -calculus in . Lo and behold, the interpretation is sound. This is Definition 10.4.1 and Theorem 10.4.7.
The denotation we obtain is absolute, meaning that a variable/atom is interpreted ‘as itself’—there is no valuation. Slightly more formally, a denotation is absolute when variable symbols in the syntax map to fixed entities in the denotation. In the case of this paper, (more strictly: ) is interpreted as (more strictly: , see Notation 4.5.3).
The role of a valuation is played by the -action. If we have some and want to ‘evaluate’ any in it to become , then we just apply []. This nominal approach to valuations using -algebras is more general than the usual Tarski denotation based on valuations; to see why, see the discussion in [Gab12, Remark 8.18].
Suppose inDi. Define a denotation of -terms by:36
— Write when .
— Write Π when for every () Π.
— Write Π when inDi Π .
Recall from Notation 4.5.3 that we write for the sets image of , i.e. , and recall that we call this image the programs of .
Call inDi replete if is closed under application and . That is:
— If then .
— If then .
Note that is a fact, where is shorthand for . If is replete then programs are closed under taking variables, application, or -abstraction, and intuitively this tells us the following:
If is replete then its programs include denotations for all -terms.
This intuition is exactly the notion of repleteness used in [GG10] (we called it faithful there, but that terminology clashes with faithfulness of functors in category theory). In this paper we are using nominal techniques, so we can give a name-based semantic treatment of , so that Definition 10.4.3 can be more abstract than it needed to be in [GG10], and it needs make no explicit mention of -term syntax.
So if is replete then Definition 10.4.1 generates programs, which can be substituted for in , and we can express Lemma 10.4.6:
Suppose inDi is replete. Then [[:].
( always exists, but repleteness ensures that so that the substitution [] also exists.)
Recall the notations and Π from Notation 10.3.8, applied here to the idiom LmTm (-terms). Recall the notation Π from Definition 10.4.1.
Suppose inDi is replete. Then if and Π then . In other words, Π implies Π . (The reverse implication also holds; see Theorem 11.9.5.)
We consider the rules defining a compatible relation on -terms (Definition 10.3.7):
(1) If and then . We use Lemma 9.1.7.
(2) If then . We use Lemmas 4.1.7 and 9.1.7.
(3) If then [:] [:]. We use Lemmas 10.4.6 and 4.3.2.
(4) ()[:]. We use Lemma 10.4.6 and part 1 of Proposition 10.2.4.
(5) If is not free in then (). If # then by Theorem 2.3.1 also #. We use part 2 of Proposition 10.2.4.
10.5. Interlude: axiomatising the -calculus in nominal algebra
Some words on where we are and where we are going.
Nominal algebra considers equality over nominal sets.37 It was introduced in two papers [GM06a; GM06b] where it was applied to axiomatise to substitution and first-order logic respectively.38 Both applications feature -equivalence and freshness side-conditions, which are of course just what nominal sets were developed to model, so this was very natural.
See [GP01] or see [Gab11a; Gab13] for surveys.
In [GM08b; GM10] nominal algebra was applied to the -calculus, extending an incomplete axiomatisation from [FG07]—Henkin style models of such axioms were considered in [GM11] and found to have some interesting properties. In particular the axiomatisation is sound and complete—so the axioms below really do axiomatise the -calculus; and this proof, in greatly strengthened form, has become the duality, soundness, and completeness results of the current paper.
So an axiomatisation of the -calculus is implicit in this paper. The reader could extract it by tracing through Notation 10.2.1 and the axioms of inDi. We do not have to write out this theory to prove soundness in this paper, because the notion of -calculus we use in this paper is the standard one based on -term syntax and reduction.
Yet the axiomatisation is there in the background, and for the reader’s convenience it might be illuminating to write it out.
Consider a nominal set .
We assume equivariant functions atm : and sub : and impose the axioms of a termlike -algebra from Figure 1:
Here we sugar atm() to just and sub() to just [].
Next we assume equivariant functions app : and lam : , and impose the axioms of - and -equality:
Here we sugar app() to and lam() to .
A few notes on this axiomatisation:
— The axiomatisation of [GM08b; GM10] identified substitution with a -reduct. The axiomatisation above distinguishes substitution and -reducts. This turns out to be important for making the results in this paper work; for more discussion see the Conclusions.
— The body of this paper is based on lattices, so we do not assume - or -equality; we only assume -reduction and -expansion. (The equalities might happen to be valid anyway, see for instance -equality theories in Definition 10.3.7.) This is also important for this paper.
In summary the axiomatisation above is a special case of a generalisation of [GM08b; GM10], which is itself a complete extension of a rewrite theory from [FG07; GM06a].
The axiomatisation above is also what we are aiming for, and models of -equality theories constructed in Section 11 are models of the axioms above, though the demands of our main results are such that we do not phrase matters in that specific form.
11. REPRESENTATION OF THE -CALCULUS IN INSPECT
In Section 10 we showed how any inDi / (dually) any inSpect, gives a sound abstract / (dually) concrete interpretation of the untyped -calculus.
The next step is to prove completeness. This is Theorem 11.9.5. The method is to construct a nominal spectral space out of a -reduction theory Π, in which only those subset inclusions are valid that are insisted on by Π.
is a rich structure. Notable technical definitions and results are Definition 11.1.1 and Proposition 11.1.6 ( and its equivalence with #), completeness under finitely-supported sets unions and intersections (Proposition 11.1.8), the -action on points (Definition 11.4.1) and its two characterisation in Subsection 11.4.2—one in terms of the now-ubiquitous .
For this section, fix the following data:
— Fix a -idiom (Definition 10.3.1).
— Fix a -reduction theory Π on (Definition 10.3.7).
, , , and will range over elements of , and and will range over elements of .
11.1. Π-points and -freshness
Given a subset , we can suggest two notions of ‘ is fresh for ’:
— One inherited from nominal techniques: (). We write this #.
— One inherited from our syntactic intuitions: if then [:] . We will make this formal in Definition 11.1.1 and write it .
A point is then defined to be a set of phrases for which these two notions of freshness coincide. This is Definition 11.1.3. The interesting part is condition 2, which is not obviously just “#”—for this, see the important and beautiful Proposition 11.1.6, which proves this from surprisingly little in the way of assumptions.
We conclude with Proposition 11.1.8, an important result asserting that is complete for finitely-supported diagrams (i.e. finitely-supported sets of points have an intersection that is also a point). This has some very useful consequences: for instance it makes possible the use of in Definitions 11.3.1, and 11.4.1, and also in Corollary 11.4.7.
If we say that is -fresh for .
Recall the notion of a -reduction theory from Definition 10.3.7.
Suppose Π is a -reduction theory. Call a subset a Π-point when:
(1) () . We call closed under Π.
(2) . We call finitely -supported.
Write for the set of Π-points.
Suppose . Then if then #.
Suppose . To show # it suffices by Corollary 2.1.10 to show that for fresh (so #) (). The permutation action is pointwise (Definition 2.2.1) so it suffices to show that for any , implies ().
By Lemma 3.2.6 ()[:][:][:] for fresh (so # and is distinct from and ). Now and # so [:] . Also # so [:][:] . Also # so [:][:][:] , and we are done.
We discussed at the introduction to this subsection why Proposition 11.1.6 is interesting:
Suppose . Then
# if and only if
We conclude the subsection with Proposition 11.1.8, a useful result with an attractive proof:
Suppose is finitely supported. Then
In words: finitely supported intersections and union of points, are points.
We check the conditions of Definition 11.1.3 for . Condition 1 is by a routine calculation.
For condition 2, suppose is fresh (so #). To prove we need to show that implies [:].
Consider and any , so that . Suppose #. We want to prove [:]. We cannot do this directly since we do not necessarily know that # (cf. Lemma 2.4.1).
So choose fresh (so #). Since also () (). So () and therefore (). By assumption # so by Proposition 11.1.6 so (())[:] . We -convert, and conclude that [:] as required.
The reasoning for is almost identical.
11.2. Constructing Π-points, and their -algebra structure
Recall the notion of idiom from Definition 10.3.1, the notion of -reduction theory Π from Definition 10.3.7, and the notion of point from Definition 11.1.3.
Suppose . Define by
If then is a point.
Our notation suggests that [] is an -action. This is true, but we must prove it: this is Lemma 11.2.4 and Corollary 11.2.5.
If and then [] is a Π-point.
We check the conditions of Definition 11.1.3, freely using Proposition 3.3.2:
(1) Suppose [:] and Π. By condition 3 of Definition 10.3.7 [:][:]. By assumption is closed under Π, and so [:] .
(2) Suppose is fresh (so #) and consider [:] . By assumption is finitely -supported and # so by Proposition 11.1.6 . Therefore
Now #, so by () for any we have [:][:[:][:[:]]. It follows (taking all of the form [:] above) that [:][:] , and so [:] [] as required.
is indeed an -algebra.
We conclude with a technical result which will be useful for Lemma 11.5.1:
If and # and then [].
11.3. Some further operations on points
11.3.1. The operations: , , , and on points.
Fix some -reduction theory Π.
Two things about Definition 11.3.1 might seem odd:
— is a sets union (not a sets intersection). This is a contravariance typical in duality results. See Proposition 11.7.11 for the treatment of , and see Lemma 11.7.6 for a clearer view of the contravariance in this case.
— There is no , even though in Proposition 11.1.8 we proved that a finite sets intersection of points is a point. This is because sets intersection of points does not interact correctly with the -action, see Remark 11.5.8. For that, we need to consider sets of points; see Corollary 11.7.9.
If and are Π-points then so are , , , and .
Suppose and suppose . Then:
(1) if and only if .
(2) If then () and () .
(3) If then .
Suppose . Then:
(1) .
(2) If # then .
(3) If then .
(4) If # then () if and only if .
The first three parts follow by construction in Definitionpt 3 11.3.1. For the final part, if then using part 1 of this result, and if then .
11.3.2. and make
().
As a corollary, if and only if .
For the reader’s convenience we apply Lemma 11.3.6 to some concrete cases. Suppose LmTm.
— Take . Then if and only if . We can calculate that and also .
— Assume some implementation of ordered pairs () and and for first and second projection, and take ) and . Then () if and only if (). We can calculate that and .
So we can think of as a kind of pattern-matching. We refine this to model in Proposition 11.3.9.
Recall from Definition 11.2.1, which is a point by Lemma 11.2.2.
).
Proposition 11.3.9 connects and on points, with on . It will also be useful later in Corollary 11.7.13. We suggested in Remark 11.3.7 that is a kind of pattern-matching; by that view, what we do now is pattern-matching on a universally quantified atom:
().
We prove two subset inclusions:
— Proof that () (). By condition 4 of Definition 10.3.7 (), so by Lemma 11.7.4 (()) (). It follows by Lemma 11.3.4 that (). By condition 1 of Definition 10.3.1 # so by Theorem 2.3.1 #(), and therefore by Lemma 11.3.5 () ().
— Proof that ()(). By condition 4 of Definition 10.3.7 (), so by Lemma 11.3.6 . By Lemma 11.3.5 (), and by condition 1 of Definition 11.1.3 ()().
11.4. The left adjoint [] to the -action []
By Proposition 11.1.8 a finitely-supported intersection of points is a point. This suggests that we could build a left adjoint to [] on points by taking a suitable intersection. We do this in Definition 11.4.1.
This left adjoint turns out to be very well-behaved. It has interesting characterisations (Subsection 11.4.2) which give us strong proof-methods for reasoning on it. Furthermore it is a -action; this is Proposition 11.5.6. So is both an -algebra and a -algebra.39
Even better, the -action commutes with - from Definition 11.7.1, which is key to how points are used to generate compact sets; this is part 1 of Theorem 11.7.8. Thus we can study the behaviour of substitution on open sets by understanding the behaviour of the left adjoint to the -algebra action of points.
In short, most of the rest of this section depends on Definition 11.4.1 and the results that follow it in this subsection.
11.4.1. Basic definition.
Recall from Definition 11.2.3 the -action on points []. We can build a left adjoint for it:
By Proposition 11.1.8, Definition 11.4.1 does indeed define a point.
Points here have finite support, so the proof of Proposition 11.4.3 is (almost) a replay of the proof of part 2 of Proposition 3.4.2 (only for subset inclusion instead of sets membership):
If # then [] if and only if [] .
Suppose is finitely supported and #. Then [))[].
As a corollary, if # then #[].
11.4.2. Two characterisations of []
By Proposition 11.1.8 and Lemma 11.2.2, [:] is a point. For the rest of this subsection, we assume .
If # then [] if and only if [:] .
As a corollary, if # then [:] [].
If # then
Recall from Definition 2.5.1 the notion of (the -quantifier, for sets).
If then also .
We verify the conditions of Definition 11.1.3:
(1) Suppose and . Then (). By equivariance of Π (Definition 10.3.7) ()() (for any ). It follows by condition 1 of Definition 11.1.3 that (), so that .
(2) Consider some fresh (so #) and consider and some fresh (so #), so that (). By condition 2 of Definition 11.1.3, , so that (())[:] . It follows that ()([:]) , and therefore [:] .
Lemma 11.4.9 gives a striking characterisation connecting the left adjoint to the -action, the pointwise substitution action, and the -quantifier for sets (Definitions 11.4.1, 11.4.5, and 2.5.1):
If # then [:] ([:]). As a corollary, if # then
11.4.3. Additional lemmas about the -action as an adjoint.
Lemmas 11.4.10 and 11.4.11 describe a unit and counit style interaction between [] and [] acting on points. We will not use these lemmas later—we will use the adjunction result they come from, Proposition 11.4.3, directly instead.
The lemmas are still worth looking at, because they are subject to freshness side-conditions and so are not quite exactly what one might assume.
If # then [][].
We cannot prove [][] from [] [] using Proposition 11.4.3, because we do not necessarily know #[]. Interestingly, a reverse inclusion does still hold:
If # then [][].
Suppose . Using Lemma 11.4.4 to rename if necessary, we may assume #. So [:, so that [] and so that [][:] L [][].
11.5. The left-adjoint [] as a -action on points
11.5.1. It is indeed a -action.
We prove Proposition 11.5.6, that [] is indeed a -action on points.
Suppose and #. Then [.
Using Lemma 11.4.4 and Corollary 2.1.10 assume without loss of generality that # as well as #.
By Lemma 11.2.6 [] so by Proposition 11.4.3 [] . Now suppose []. We will show that . Unpacking Definition 11.4.1, [] implies that there exists such that and for fresh (so #) ()[]. Now by (#) [:. Thus if then by Proposition 3.4.2 also []. Therefore (). By Corollary 2.1.10 since # and # also (), so as required.
If # then [).
By Lemma 11.4.9 [] if and only if ()[:], and by Definitions 11.2.1 and 11.4.5 this is if and only if [:]().
Now by assumption # so if supp() then by condition 2 of Definition 11.1.3 also [:] . So we may assume without loss of generality of the ‘’ above that the chosen satisfies #, so that [:).
Thus this is if and only if ()(). Rearranging the permutations, this is if and only if ()(()).
Again, since #, by Corollary 2.1.10 () so that if and only if (). Thus this is if and only if (), and by condition 1 of Definition 11.1.3 this is if and only if ().
Corollary 11.5.4 is a repeat of Corollary 3.4.7, but for points. We will use it in Proposition 11.5.6:
[.
If # then [][[][[]].
Proposition 11.5.6 does not hold in the general case of () from Definition 7.2.1, but it holds specifically for . The underlying reason this happens is Proposition 11.1.8, which allows us to build (finitely-supported) intersections of points and so construct [] in Definition 11.4.1:
with the action [] from Definition 11.4.1 is indeed a -algebra.
11.5.2. The -action distributes over union and subset
Suppose is strictly finitely supported (Subsection 2.4.2). Then
Lemma 11.5.7 does not give us distributivity of of substitution over sets intersection of points. This is why, as noted in Remark 11.3.2, we do not consider an operation ; it would not satisfy . To get this kind of property we need the topologies, developed below. See in particular Corollary 11.7.9.
If then [] [].
Using Lemma 11.5.7, since if and only if .
11.5.3. Relating and the -action [].
Recall that for we defined in Definition 11.3.1 and [] in Definition 11.4.1. (We proved that [] is a -action, as the notation suggests, in Proposition 11.5.6.)
Definition 11.3.1 defined #. There is nothing in this to a priori suggest that this should be a universal quantification. But it is: we prove it in Proposition 11.5.12.
#.
As a corollary, supp() supp().
and as a corollary, if then ([:] ).
We can now prove that is indeed a universal quantification over . If the reader is puzzled by the use of here—should it not be ?—remember that with points things are dual and so ‘upside-down’ (see Lemma 11.7.6 and part 2 of Proposition 11.7.11).
[].
— The left-to-right inclusion. By construction [] (we take and use Corollary 11.5.4). In addition, using Lemma 11.4.4 and Theorem 2.3.1 it can be proved that # []. We use part 4 of Lemma 11.3.5.
— The right-to-left inclusion. By construction in Definition 11.3.1 , so by Lemmas 11.5.9 and 11.5.1 [] for every .
11.6. How the -action on points commutes
The set of points has plenty of structure. It is a nominal set, it has an -action [] (Corollary 11.2.5), a -action [] (Proposition 11.5.6) and a subsidiary pointwise version [:] (Definition 11.4.5). It is a fresh semi-lattice (a top element, , and ; see Remark 11.1.4 and Definition 11.3.1) and has and (Definition 11.3.1) and even a sets version of the -quantifer (Lemma 11.4.8). There is also a map from to points given by maps to (Definition 11.2.1).
In this subsection we consider useful ways in which the -action commutes with some of this structure. These commutation results will later be useful in proving that sets of points have the structure of an impredicative lattice with and .
[[:].
Using () and Lemma 11.4.4 assume without loss of generality that #. We prove two subset inclusions.
— Proof that [] [:]. By Lemma 3.2.5 #[:] and by Theorem 2.3.1 also #[:]. Thus by Lemma 11.4.6 to it suffices to prove [:] [:]. Suppose . By condition 3 of Definition 10.3.7 [:][:]. The result follows.
— Proof that [:][]. By condition 1 of Definition 11.1.3 it suffices to note that [:] [].
From Definitions 11.3.1 and 11.4.5, we have that ()[:] when there exist and such that ()[:], and that [:][:] when there exist and such that [:] [:]. By () ()[:[:] [:].
For the second part, ()() when there exist and such that () and () and . It is a fact that the -quantifier distributes over conjunction [Gab11a, Theorem 6.6], so also ()() . The result follows.
Suppose . Then:
—
—
Proposition 11.6.4 is the key technical result to proving () valid in Corollary 11.8.18:
Suppose and #. Suppose . Then ()[ ([]).
For the right-to-left inclusion ([]) ()[] we reason as follows:
For the left-to-right inclusion ()[] ([]), using Lemma 11.4.4 to rename if necessary assume #. Using Theorem 2.3.1 also note that #([]). Thus by Lemma 11.4.6 and part 3 of Lemma 11.3.4 it suffices to prove that ()[:] ([:]).
Unpacking Definitions 11.3.1 (for ) 11.2.1 (for ) and 11.4.5 (for [:] on points), this simplifies to showing that for all ,
So suppose is such that and [:]. Take . So [:)[: as required.
11.7. Operations on sets of points
11.7.1. Basic definitions
and generate sets of points. We use these to build a topology and a nominal spectral space with over and so to prove Theorem 11.9.5 (completeness).
is a combination operator in the sense of Definition 9.2.1, so that we get operations and on sets of points from Definition 9.2.3.
Thus we have two operations named ; one on points from Definition 11.3.1 and one on sets of points from Definition 11.7.1. Similarly, we have two operations named . It will always be clear from context which is meant, and they are related by Proposition 11.7.11.
It might be worth mentioning that from Definition 11.7.1 is not a repeat of from Definition 6.3.1:
— In Definition 6.3.1 we assumed an underlying nominal distributive lattice with .
— Definition 11.7.1 is constructed using . Now we consider Definition 11.3.1 and see that if we ignore and then is almost a nominal distributive lattice with —but it lacks a disjunction. We could reasonably call it a semilattice with .
So is a specific structure with its own properties.
The proof of Lemma 11.7.4 is fairly simple, by unfolding definitions. However it is very important; for instance it is the final step in the proof of Completeness in Theorem 11.9.5.
The following conditions are equivalent:
if and only if .
From Lemma 11.7.4.
Lemma 11.7.6 is in the spirit of Lemma 6.3.2:
Suppose . Then the following conditions are equivalent:
Furthermore, if then .
The assignment is injective from to pow(). As a corollary, supp( supp().
11.7.2. Commutation properties.
Recall [] from Definition 11.4.1, [] from Definition 3.3.1, and (since by Corollary 11.2.5 is an -algebra) [] from Definition 3.4.1.
Theorem 11.7.8 is fairly easy to prove, but part 1 of it is key. It relates the natural -action [] to the -action on points [] from Proposition 11.5.6. Compare Theorem 11.7.8 with Lemma 6.4.1:
Suppose and .
(2)
Consider some ; we wish to show that [] ([]). By Lemmas 3.4.3 and 11.4.4 we may -rename in [] and [] to assume without loss of generality that #. We reason as follows; we use part 2 of Proposition 3.4.2 because by Corollary 11.1.7 and have finite support:
The corollary follows using Lemma 11.6.1.
The second part is proved by similar calculations, or directly from Theorem 2.3.1.
Corollary 11.7.9 describes how the -action interacts with sets union (see also Proposition 11.8.4):
Suppose is strictly finitely supported. Then
(1) # then ()[.
(2) If # then (())[[].
(1) ).
(3)
(4)
We consider each case in turn; with what we have proved so far, the calculations are routine. will range over elements of :
(1) We reason as follows:
(2) We reason as follows:
(3) We reason as follows:
(4) We reason as follows:
Corollary 11.7.12 resembles Lemma 9.4.9 and is proved similarly:
Suppose and . Then and validate axioms () and () from Figure 3:
We reason as follows:
If then ) and ().
We reason as follows:
11.8. A topology
11.8.1. Giving pointsΠ a topology
So opens() (meaning that is open) when there exists some strictly finitely supported (Definition 2.4.2) with .
We start with the conditions from Definition 7.1.1. By Corollary 11.2.5 () is an -algebra.
Consider opens(). As noted in Remark 11.8.2 and for some strictly finitely supported . We check the first three conditions spelled out in Definition 7.1.1:
(i) has finite support. From Theorem 2.3.1.
(ii) # implies [. Suppose #. By Lemma 2.4.3 and Theorem 2.3.1 # for every . By Corollary 11.7.10 [ for each . The result follows by Lemma 9.2.11.
(iii) # implies [))[]. Much as the previous case, using Corollary 11.7.10.
We now reason as follows:
(1) If is open then so are and []. Using Theorem 2.3.1 and Corollary 11.7.9 we have that:
and using Theorem 2.3.1 and [] are strictly finitely supported. The result follows.
(2) and are open. (the empty set of points) is open by construction of the topology, and is open—we noted in Remark 11.1.4 that the empty set of phrases is a point. Then is the set of all points and is strictly finitely supported (by the empty set of atoms).
(3) If and are open then so are and . It is a fact of sets that . We use part 1 of Proposition 11.7.11 and Theorem 2.3.1. For , it suffices to note that the union of two strictly finitely supported sets is strictly finitely supported.
(4) If is a strictly finitely supported set of open sets then is open. Using Corollary 2.4.5.
Finally, we consider Definition 9.2.2 and note that is a combination operator (that is equivariant follows immediately from Theorem 2.3.1).
In Proposition 11.8.3 we noted that () is an -algebra by Corollary 11.2.5. We can put together what we have so far and spell out what the corresponding -action does concretely to open sets:
Suppose opens(), so that by construction in Definition 11.8.1 for some strictly finitely supported set of points . Suppose . Then we can describe [] equivalently as follows:
11.8.2. The compact open sets of pointsΠ
If opens() then
If then is compact in with the topology from Definition 11.8.1. In symbols: cpct().
As a corollary, if then cpct().
If opens() is compact then for some finite .
Suppose is compact. By construction for some strictly finitely supported (but not necessarily finite) . By compactness this has a finite subcover . We take .
We have mentioned that the canonical model is not just a replay of () from the duality proof (Definition 7.2.1). So compare Proposition 7.3.10 (which identifies compacts in () with sets of points of the form ) with Lemma 11.8.7 (which identifies compacts in with finite unions of sets of the form ). If () and were the same, then we would expect Proposition 7.3.10 and Lemma 11.8.7 to also by the same. This is related to issues discussed in Remarks 11.3.2 and 11.5.8.
11.8.3. Interaction of and with and .
Lemmas 11.8.9 and 11.8.10 are useful for Corollary 11.8.11:
Suppose and . Then and .
If opens() and then the following conditions are equivalent:
If opens() and then () if and only if for 1.
() if and only if for some 1.
Suppose are finite. Then
11.8.4. Interaction of # with unions.
Remarkably, commutes with certain unions. This is Lemma 11.8.14. The property is not valid in general in inDi; indeed this is not generally true in logic: () is not normally logically equivalent to () (). But, it holds in the canonical model :
.
Suppose . Using Lemma 5.2.5 rename to assume without loss of generality that #.
Then by Definition 5.2.1 and Proposition 3.4.2 is if and only if [] for every . Choose fresh (so #). Then for some 1 we have that [] . Therefore () and so by Lemma 5.2.5 () .
Conversely, it is easy to prove that , either using Lemma 4.1.7 and Corollary 5.2.7 since —or by an easy direct calculation from Definition 5.2.1 and part 4 of Lemma 5.1.1.
11.8.5. Proof that pointsΠ is coherent and sober.
We saw in Proposition 11.8.3 that is a nominal -topological space in the sense of Definition 9.2.2. We now show that it is coherent (Definitions 7.4.1 and 9.2.7) and sober (Definition 7.7.2).
Suppose and are compact in and suppose . Then:
— is compact.
— is compact.
— [] is compact.
By Lemma 11.8.7 we may assume and for finite . We consider each part in turn:
— (which is a point, as noted in Remark 11.1.4). We use Lemma 11.8.6.
— Using part 1 of Proposition 11.7.11 (). By Lemma 11.8.6 each () is compact, and a finite union of compact sets is compact.
— By Lemma 5.1.1 and Theorem 11.7.8 [([]). By Lemma 11.8.6 each ([]) is compact, and a finite union of compact sets is compact.
Suppose is compact in . Then continuing Lemma 11.8.15:
— is compact.
By Lemma 11.8.7 we may assume and for finite . We consider each part in turn:
— By Lemma 9.2.11 and part 3 of Proposition 11.7.11 (). By Lemma 11.8.6 each () is compact, and a finite union of compact sets is compact.
— By Corollary 11.8.13 (). By Lemma 11.8.6 each () is compact; by Lemma 11.8.15 a finite intersection of compact sets is compact; and a finite unions of compact sets is compact.
is a coherent nominal -topological space.
is a nominal -topological space by Proposition 11.8.3. It remains to check the additional coherence conditions of Definitions 7.4.1 and 9.2.7.
We check the conditions of Definition 7.4.1. Suppose and are compact in . By Proposition 11.8.17 [], , and are compact. By Lemma 11.8.14 is compact.
By construction in Definition 11.8.1 every open set is a strictly finitely supported union of compact open sets (of the form for ).
We check the conditions of Definition 9.2.7. Suppose and are compact. By Proposition 11.8.17 and are compact. Conditions 6 and 7 of Definition 9.2.7 also hold (validity of () and ()):
is sober (Definition 7.7.2).
It suffices to observe that is uniquely identified by the set of open (indeed, compact) sets .
from Definition 11.8.1 is indeed a nominal spectral space with .
11.9. Logical properties of the topology, and completeness
Recall that at the start of this section we fixed an idiom (Definition 10.3.1) and a -reduction theory Π over (Definition 10.3.7).
We call () the canonical model.
We now set about proving Theorem 11.9.5, which uses () to prove completeness—the converse direction to soundness from Theorem 10.4.7.
Recall from Definition 10.4.1 the definition of and recall from Definition 10.1.2 that LmTm is the set of -terms. Suppose LmTm.
and as a corollary ().
By a routine induction on -terms:
—
—
—
The corollary follows from Lemma 11.8.6, since () is by definition the set of compact open sets of .
Recall from Notation 10.3.8 and Definition 10.4.1 the notations Π and () Π.
() Π.
11.10. Interlude: an interesting disconnect
The duality theorem from Theorem 9.6.6 is more general than the completeness theorem needs it to be. The completeness result of Theorem 11.9.5 is based on inSpect. Although is a spectral space (Theorem 11.8.20) it has more structure too: for instance it is replete (Definition 10.4.3) and has an existential quantifier, as we note later in Definition B.2.1.
Could we obtain a more specific duality result for structures that have more of the structure apparent in ?
We probably could. However, we do not do it in this paper. inDiinSpect have the minimal structure we need to interpret the -calculus and to carry out a filter-based duality proof. The less structure we impose, the more general our duality result,40 and we have more representations.
But in the completeness result we are happy if the canonical model has more structure, since it suggests more programming and reasoning constructs; an existential quantifier, for example, suggests that the ambient meta-logic implicit in permits unconstrained search. We do not care about any other structures because we have built one particular concrete structure and having built it, we want to obtain as many bells and whistles from it for free as possible.41
So on the one hand we have a world where less structure is good, because fewer assumptions means stronger theorems that are valid for a larger class of entities (provided we can still build the things we want to in those entities, i.e. interpret the -calculus, which we can), and on the other hand we have a world where more structure is good, because it gives us more tools to actually do things.
The apparent disconnect comes from a difference between two styles, each of which is optimised for its own purpose.
The general trend in this paper is a progression from the abstract and general, like inSpect, to the relatively more concrete and specific, like .
12. CONCLUSIONS
The semantics of this paper has the moderately unusual feature of being absolute, meaning that variables are interpreted directly in the denotation and there is no (Tarski-style) valuation.
The reader may find this takes some getting used to, but it is actually simple and natural.
What corresponds to valuations is the -action, which allows us to take some and ‘evaluate’ to in by forming []. This is an abstract nominal algebraic property of ; it is characterised by axioms and we do not necessarily have access to the internal structure of .
However, we can certainly build concrete -algebras if we want to: Two examples are -term syntax LmTm from Definition 10.1.1 and the canonical model from Subsection 11.9. Another example is how we move from -algebra structure to -algebra structure (and back) using nominal powersets (Definition 3.4.1). Nominal powersets have intersections, unions, and complements, and by combining all of these things we can interpret (Definition 5.2.1).
In fact, it turns out that with a little more effort and just a bit more structure we can interpret application and too. This brings us on to another unusual feature of our topological semantics: it is purely sets-based.
Algebraic (dually: topological) semantics for the -calculus exist, but our semantics is this in a different and stronger sense than usual, because everything is interpreted algebraically (dually: topologically), including variables, substitution, and -abstraction.
This paper gives a panoramic view of the interaction between nominal foundations and the -calculus. This gives us something that shorter papers might not do so well: a feel for the overall point of view, and how the parts of the puzzle fit together.
12.1. Related work
12.1.1. Algebraic semantics.
Algebraic semantics for logics or calculi with binding include polyadic algebras [Hal06, Part II], cylindric algebras [HMT85], and Lambda Abstraction Algebras [Sal00]. As far as we know, what is done in this paper has not been done in any of these (but see below).
We can suggest technical reasons for this. Consider for instance the treatment of substitution in this paper.
For us substitution exists independently from -reduction—this is the notion of -algebra from Subsection 3.1. This is important for our constructions to work. For instance, Subsections 3.3 and 3.4 do not assume and application, they only assume and . This is reflected in commutation results like Lemma 6.4.1 and Theorem 11.7.8.
The commutations for are later, and much harder: Lemmas 9.4.9 and 9.4.10 for inDi and Corollary 11.7.13 for .
It not obvious how substitution on its own could be axiomatised without permutations and freshness side-conditions, i.e. without nominal algebra. LAAs do not do this, neither do cylindric algebras. Polyadic algebras assume a monoid of substitutions. This is tantalisingly close to finite permutations, but without their invertibility.
By enriching the foundation with names and binding, nominal techniques allow us to express richer algebraic structures—for instance substitution, as was done in [GM06a; GM08a]. We exploited that fact in this paper to break constructions up into more manageable parts: we split into and (Notation 10.2.1), -reduction into , , and (Proposition 10.2.4), and then (substitution) itself into permutation and freshness (Definitions 3.1.4 or 3.4.1).
Representation theorems exist for cylindric algebras; for instance [Mon61] gives a representation theorem for cylindric algebras, and [PS95] gives one for LAAs. In both cases, an algebra is represented concretely as a set of valuations on the variables (on the indexes; the things that correspond to atoms in this paper).
This is typical. Representation theorems for cylindric-algebra-style systems do all seem to use something corresponding to a set of valuations. It works, but it is a soundness and completeness proof with respect to Tarski-style semantics. There is no duality result.
The only duality results we know of for logic were undertaken by Forssel [For07] and by the first author [Gab11b]. See [Gab11b] for a comparison of the two.
A Stone Representation has been given for Lambda Abstraction Algebras. This is a factorisation result in the style of the HSP theorem (also known as Birkhoff’s theorem): every LAA can be factored as a product of irreducible LAAs. The factorisations are identified by central elements of the algebra [MS10]. The LAA is never represented as anything resembling a Stone space, and there is no duality.
In passing, we note that the HSP part of the LAA result also follows in this paper (for inDi) off-the-shelf, by the nominal HSPA theorem [Gab09a; Gab13]. In other words, we get some of [MS10] for free, just by virtue of being nominal and using nominal algebra. The HSPA factorisation is slightly better than the HSP factorisation (because it has an A in it: for atoms-abstraction). Investigating any extra power this gives what that might mean for (nominal) LAAs, is an open problem.
We mention also [KP10]. This is an attempt to encode what makes nominal techniques work using many-sorted universal algebra. Equivariance, however, gets lost in the translation; a similar phenomenon was noted in [DG12] translating permissive-nominal logic (a first-order generalisation of nominal algebra) to higher-order logic.
12.1.2. Absolute semantics.
Absolute semantics have appeared before. Lambda-abstraction algebras (for the -calculus) and cylindric algebras and polyadic algebras (for first-order logic) are absolute. Selinger made a case for using absolute semantics for the -calculus in [Sel02] (see Subsection 2.2); a line of thought echoed by the first author with Mulligan in [GM11].
Yet absolute semantics have not caught on. We are inclined to believe that this is because the mathematical foundations to support it were not in place before, but they are now. Now that we have nominal techniques we can make a lot of things work that would not work before.
Without nominal techniques things we use repeatedly in the current paper, like finite support, freshness side-conditions, equivariance, the -quantifier, and even -equivalence, become challenging in various technical fiddly ways, and even the statements of some properties become practically impossible to even write out.
Concretely, let us imagine how we might set about rendering condition 4 of Definition 6.1.1, or Definition 11.4.1, or even the clause for in Definition 11.3.1, if we did not have finite support, freshness, and the -quantifier. We would probably have to invent them first.
We also mention Kit Fine’s arbitrary objects [Fin85] as an instance of a similar impulse towards absolute semantics, coming from philosophy. This comes from philosophy.
There is a precedent for this paper in the first author’s work; indeed this paper is based on them. The nominal semantics and duality results for first-order logic in [Gab11b] and [Gab12] are absolute, and are very much in the style and research programme of this paper.
Nominal algebra has helped us to reduce mathematical overhead and to simplify some technical manipulations that are otherwise all too easy to get bogged down in. This is just what any good mathematical toolbox or foundation should do.
12.1.3. -expansion.
In Proposition 10.2.4 we saw -reduction and -expansion appear spontaneously as corollaries of adjoint properties. So our notion of -reduction theory is more general than an extensional -equality theory because reductions can go one way and not the other, but it is also more specific than just any set of reductions because it must contain -expansion.
The reader used to seeing as a contraction rule in rewrite systems might be interested in a thread of publications by Barry Jay and Neil Ghani, which argues in favour of -expansion from the point of view of rewriting, for better confluence and other properties which they list. See [JG95] and [Gha97].
For us too, expansion rather than contraction seems to be the natural primitive.
On the basis of preliminary calculations in unpublished notes, we believe that we can remove -expansion at some cost in complexity in the models. We do this by considering two application operations and ; one intensional and one extensional. This is future work.
12.1.4. Previous treatment of -calculus by the authors.
In [GM06a; GM06b] the first author and Mathijssen developed nominal algebra and axiomatised substitution and first-order logic, with completeness proofs. Journal versions are [GM08a; GM08c].
An axiomatisation, again with completeness proofs, for the -calculus followed in [GM08b; GM10]. So the -axioms which appear in Figure 1 are taken from [GM06a], and the axioms for and are descended from [GM08b; GM10].
In [Gab11b] we applied duality theory to in nominal sets to the axiomatisation of [GM06b; GM08c]. The main conceptual challenge (aside from the inherent difficulty of duality proofs) was to invent -algebras.42 The -axioms of Figure 1 are from [Gab11b]. We have taken this further in [Gab12].
This paper carries out a similar project to [Gab11b], but for the -calculus. This has been a tougher target than first-order logic, which is unsurprising. The main conceptual difficulty of this paper over the previous work is the treatment of application and using adjoints and the logical quantifier. The ideas for this are from [GG10] (see Figure 2, where is written ). The similarity with [GG10] is somewhat hidden just because it was written in a ‘modal logic’ style. That style has been replaced in this paper by the nominal foundations.
In summary, and at least in principle, this paper just combines [GM06a], [GM08b], and [GG10] with [Gab11b]. (What could be simpler or more natural?)
12.1.5. No conflict with topological incompleteness results.
The best-known models of the untyped -calculus are Scott’s domain models and generalisations: graph semantics; filter semantics; stable semantics; strongly stable semantics; and so on. An excellent discussion with references—an annotated bibliography and survey, in fact—appears in [Sal01] between Theorems 4.5 and 4.6.
These are all ordered structures, and this is key, since the idea is to reduce the function space using continuity conditions.
These semantics are all incomplete. That is, domains-based denotational semantics proved the -calculus consistent, but results like [Sal03, Theorems 3.5 and 4.9] proved that this is not the whole story: see also [Sal01].43
The reader familiar with this literature and who has seen e.g. Theorem 3.5 of [Sal03] might be puzzled by Theorem 11.9.5: the former states that no semantics in terms of partially-ordered models with a bottom element can be complete, whereas the latter claims to prove completeness for a semantics based on inDi, and an object of inDi is a lattice and has a bottom element .
However, nothing insists that should be a program. That is, in the notation of Notation 4.5.3, it is perfectly possible that inDi and .
This illustrates that is a logical structure—its dual is topological—and just a subset is deemed to be ‘computational’. The models of the -calculus live in , and need not be closed under meets or joins.
The formal sense in which this is intended is just that programs are the things that can be substituted for by the -action; so intuitively atoms in inDi ‘range over’ programs. In the light of this reading of the definitions, Definition 10.4.3 calls replete when its programs are Turing complete.
It remains to discover whether there exists a -equality theory such that if inDi is a model of that theory then it can have no non-trivial order on its programs (so if then if then ).
12.1.6. Sheaves.
We impose a topology on a set to reduce the size of the function-space by restricting to continuous functions. Sheaves do much the same thing, but in more generality.
Nominal sets form a category which admits a sheaf presentation (a discussion specific to nominal techniques is in [Gab11a]). Simplifying a little, this amounts to observing that equivariance (commuting with the permutation action) can be represented as a generalised ‘continuity’ condition. There is no need to stop there. We could try to make ‘continuity’ represent, for instance, compatibility conditions such as () from Figure 3.
This is what is done by the Topological representation of the -calculus considered in [Awo00]. Examining equation (15) of the paper we see that, essentially, an open set is a set of substitution instances of evaluations from variables to terms. (The calculations are given only for the simply-typed -calculus.) Continuity ensures that function application commutes with substitution, i.e. ().
The closest thing to the construction of [Awo00] is the construction of in Definition 11.1.3. Both are representations of the (simply-typed) -calculus, and both are topological, but beyond that we see little resemblance between the two constructions. Our consistency conditions are axiomatic, and we use the topology to do logic and so to break -down into and . Substitution is managed by axioms.
12.1.7. In what universe does this paper take place?.
The points built in Theorem 6.1.13 do not have finite support, and in Definition 3.2.1 we assume a set with a permutation action but not necessarily a nominal set. Thus, this paper does not take place entirely in the topos of nominal sets; we do whatever is convenient to get the results we need and do not commit to any specific logic when we get them, even though our main results can be stated entirely in the nominal sets universe. In this we are being typical mathematicians, reasoning freely in English about informally but precisely specified mathematical objects.44
12.2. Future work
In Subsection 11.10 we noted that has plenty of structure. It remains to explore that structure: is a lattice and so contains a logic. We know this has interesting structure, investigated from Subsection 11.1. That does not exhaust the possibilities: Appendices B.2 and B.3 note that also supports an existential quantifier. What is the full logic of and how can it be used to investigate the -calculus?
Proposition 11.5.6 notes that also has a -action, which we characterise in different ways in Subsection 11.4.2; the characterisation in Lemma 11.4.9 seems particularly appealing. As we note in the body of the paper, there is probably a general theory here: a way of, given a -action on , building a -action on the nominal powerset of . Such a theory was already undertaken in [Gab09b], where constructions were applied to models of Fraenkel-Mostowski set theory; thus generating a huge class of huge -algebras, since there are many models of FM sets and many sets in each model. The construction in Proposition 11.5.6 suggests the possibility of a cleaner and/or alternative development of similar ideas.45
We have used nominal lattices to give semantics to the -calculus. Part of our axiomatisation is the compatibility conditions of Figure 3, which include the axiom () (substitution commutes with application). If we relax this axiom, we get a meta-programming environment (because it allows functions to ‘detect’ atoms in their arguments); conversely () says that functions cannot do this. Meta-programming is a large field which has proven resistant so far even to precise categorisation. Generalisations of inDi without () might be one place to start looking for mathematical semantics.
On a related note, in [GG10] we noted that has a dual construction, (), of pattern-matching (i.e. it applies to points in the ‘pattern’ and outputs the same points in the pattern ). We suspect this might be the semantic analogue of Jay’s pattern calculus [Jay04]. More generally, inDi and are not just for the -calculus; they are rich and interesting environments, combining computational and logical structures, and much more. We have used them as a bridge between lattice-theory and -calculus. We would go so far as to suggest that for some people this bridge might be just as interesting as the -calculus itself.
REFERENCES
Steve Awodey, Topological representation of the lambda-calculus, Mathematical Structures in Computer Science 10 (2000), no. 1, 81–96.
Mikolaj Bojanczyk, Laurent Braud, Bartek Klin, and Slawomir Lasota, Towards nominal computation, Proceedings of the 39th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2012), ACM Press, January 2012, pp. 401–412.
Stanley N. Burris and H. P. Sankappanavar, A course in universal algebra, Graduate texts in mathematics, Springer, 1981.
Gilles Dowek and Murdoch J. Gabbay, PNL to HOL: from the logic of nominal sets to the logic of higher-order functions, Theoretical Computer Science 451 (2012), 38–69.
B. A. Davey and Hilary A. Priestley, Introduction to lattices and order, 2 ed., Cambridge University Press, 2002.
Herbert B. Enderton, Elements of set theory, Academic Press, 1977.
Maribel Fernández and Murdoch J. Gabbay, Nominal rewriting (journal version), Information and Computation 205 (2007), no. 6, 917–965.
Maribel Fernández, Murdoch J. Gabbay, and Ian Mackie, Nominal Rewriting Systems, Proceedings of the 6th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming (PPDP 2004), ACM Press, August 2004, pp. 108–119.
Kit Fine, Reasoning with arbitrary objects, Blackwell, 1985.
Henrik Forssell, First-order logical duality, Ph.D. thesis, Carnegie Mellon University, December 2007.
Murdoch J. Gabbay, A Theory of Inductive Definitions with alpha-Equivalence, Ph.D. thesis, University of Cambridge, UK, March 2001.
, Nominal Algebra and the HSP Theorem, Journal of Logic and Computation 19 (2009), no. 2, 341–367.
, A study of substitution, using nominal techniques and Fraenkel-Mostowski sets, Theoretical Computer Science 410 (2009), no. 12-13, 1159–1189.
, Foundations of nominal techniques: logic and semantics of variables in abstract syntax, Bulletin of Symbolic Logic 17 (2011), no. 2, 161–229.
, Stone duality for First-Order Logic: a nominal approach, Howard Barringer Festschrift, December 2011.
, Semantics out of context: nominal absolute denotations for first-order logic and computation, Submitted.
, Nominal terms and nominal logics: from foundations to meta-mathematics, Handbook of Philosophical Logic, vol. 17, Kluwer, 2013.
Murdoch J. Gabbay and Vincenzo Ciancia, Freshness and name-restriction in sets of traces with names, Foundations of software science and computation structures, 14th International Conference (FOSSACS 2011), Lecture Notes in Computer Science, vol. 6604, Springer, 2011, pp. 365–380.
Michael J. Gabbay and Murdoch J. Gabbay, A simple class of Kripke-style models in which logic and computation have equal standing, International Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2010), 2010.
Neil Ghani, Eta-expansions in dependent type theory—the calculus of constructions, Typed Lambda Calculi and Applications (1997), 164–180.
Murdoch J. Gabbay, Tadeusz Litak, and Daniela Petrişan, Stone duality for nominal Boolean algebras with NEW, Proceedings of the 4th international conference on algebra and coalgebra in computer science (CALCO 2011), Lecture Notes in Computer Science, vol. 6859, Springer, 2011, pp. 192– 207.
Dov M. Gabbay and Larisa Maksimova, Interpolation and definability: Modal and intuitionistic logics, Oxford Logic Guides, Oxford Science Publications, 2005.
Murdoch J. Gabbay and Aad Mathijssen, Capture-avoiding Substitution as a Nominal Algebra, ICTAC 2006: Theoretical Aspects of Computing (Berlin), Lecture Notes in Computer Science, vol. 4281, Springer, November 2006, pp. 198–212.
, One-and-a-halfth-order logic, Proceedings of the 8th ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming (PPDP 2006), ACM, July 2006, pp. 189–200.
, A Formal Calculus for Informal Equality with Binding, WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, Lecture Notes in Computer Science, vol. 4576, Springer, July 2007, pp. 162–176.
, Capture-Avoiding Substitution as a Nominal Algebra, Formal Aspects of Computing 20 (2008), no. 4-5, 451–479.
, The lambda-calculus is nominal algebraic, Reasoning in simple type theory: Festschrift in Honour of Peter B. Andrews on his 70th Birthday (Christoph Benzmüller, Chad Brown, Jörg Siekmann, and Rick Statman, eds.), Studies in Logic and the Foundations of Mathematics, IFCoLog, December 2008.
, One-and-a-halfth-order Logic, Journal of Logic and Computation 18 (2008), no. 4, 521–562.
, Nominal universal algebra: equational logic with names and binding, Journal of Logic and Computation 19 (2009), no. 6, 1455–1508.
, A nominal axiomatisation of the lambda-calculus, Journal of Logic and Computation 20 (2010), no. 2, 501–531.
Murdoch J. Gabbay and Dominic P. Mulligan, Nominal Henkin Semantics: simply-typed lambda-calculus models in nominal sets, Proceedings of the 6th International Workshop on Logical Frameworks and Meta-Languages (LFMTP 2011), EPTCS, vol. 71, September 2011, pp. 58–75.
Murdoch J. Gabbay and Andrew M. Pitts, A New Approach to Abstract Syntax with Variable Binding, Formal Aspects of Computing 13 (2001), no. 3–5, 341–363.
Jean-Yves Girard, Paul Taylor, and Yves Lafont, Proofs and types, Cambridge University Press, 1989.
Paul R. Halmos, Algebraic logic, AMS Chelsea Publishing, 2006.
Furio Honsell and Simona Ronchi Della Rocca, An approximation theorem for topological lambda models and the topological incompleteness of lambda calculus, Journal of Computer and System Sciences 45 (1992), no. 1, 49–75.
Leon Henkin, J. Donald Monk, and Alfred Tarski, Cylindric algebras, North Holland, 1971 and 1985, Parts I and II.
C. Barry Jay, The pattern calculus, ACM Transactions in Programming Language Systems 26 (2004), no. 6, 911–937.
C. Barry Jay and Neil Ghani, The virtues of eta-expansion, Journal of Functional Programming 5 (1995), no. 2, 135–154.
Peter T. Johnstone, Stone spaces, vol. 3, Cambridge University Press, 1986.
, Sketches of an elephant: A topos theory compendium, Oxford Logic Guides, vol. 43 and 44, OUP, 2003.
Alexander Kurz and Daniela Petrişan, On universal algebra over nominal sets, Mathematical Structures in Computer Science 20 (2010), 285–318.
Edward Keenan and Dag Westerståhl, Generalized quantifiers in linguistics and logic, Handbook of Logic and Language (J. Van Benthem and A. Ter Meulen, eds.), Elsevier, 1996, pp. 837–894.
Saunders Mac Lane, Categories for the working mathematician, Graduate Texts in Mathematics, vol. 5, Springer, 1971.
Saunders Mac Lane and Ieke Moerdijk, Sheaves in geometry and logic: A first introduction to topos theory, Universitext, Springer, 1992.
Donald Monk, On the representation theory for cylindric algebras, Pacific Journal of Mathematics 11 (1961), no. 4, 1447–1457.
Giulio Manzonetto and Antonino Salibra, Applying universal algebra to lambda calculus, Journal of Logic and computation 20 (2010), no. 4, 877–915.
Don Pigozzi and Antonino Salibra, Lambda abstraction algebras: representation theorems, Theoretical Computer Science 140 (1995), no. 1, 5–52.
Antonino Salibra, On the algebraic models of lambda calculus, Theoretical Computer Science 249 (2000), no. 1, 197–240.
, A continuum of theories of lambda calculus without semantics, Proceedings of the 16th IEEE Symposium on Logic in Computer Science (LICS 2001), IEEE, 2001, pp. 334–343.
, Topological incompleteness and order incompleteness of the lambda calculus, ACM Transactions on Computational Logic 4 (2003), no. 3, 379–401.
Peter Selinger, The lambda calculus is algebraic, Journal of Functional Programming 12 (2002), no. 6, 549–566.
Dag Westerståhl, Quantifiers in formal and natural languages, Handbook of Philosophical Logic, Synthèse, vol. 4, Reidel, 1989, pp. 1–131.
A. MORE ON FRESH-FINITE LIMITS
A.1. Axiomatisation of fresh-finite limits
A key definition in this paper has been Definition 4.4.3; this is ‘poset-flavoured’, in the sense that and were characterised using fresh-finite limits (Definition 4.1.2).
It is interesting to ask whether fresh-finite limits can be rephrased in the syntax of nominal algebra, using equalities subject to freshness side-conditions.
This has implications, because if this can be done then inDi and inDi are algebraic varieties, and satisfy the nominal HSP theorems from [Gab09a; Gab13].46 This gives us off-the-shelf factorisation theorems similar to those considered in [MS10] (see especially Theorem 14), and in general, it is useful to know when a class of structures is an algebraic variety.
A bounded lattice in nominal sets is a tuple ) where:
— () is a nominal set which we may just write ,
— and are equivariant bottom and top elements,
— : () are equivariant functions, such that and form an idempotent monoid and and form an idempotent monoid,
— and and satisfy absorption
Here, range over elements of .
A bounded lattice is a poset by taking to mean or (the two conditions are provably equivalent). Definition A.1.1 is the usual definition of a bounded lattice, but over a nominal set; but we have not done anything with it yet.
Definition A.1.2 exploits the nominal set structure to algebraise the universal quantifier:
Suppose is a nominal poset.
A (nominal) universal quantifier on is an equivariant map : () satisfying the equalities () to () in Figure 4.
#.
Suppose is a bounded lattice with and . Then # implies
We reason as follows:
So . Furthermore by () , and we are done.
Suppose is a bounded lattice and suppose has a nominal universal quantifier . Then is the #limit for .
A.2. Support interpolation
We return to Proposition 4.2.3, which stated that in a nominal poset if exists then so does and they are equal (this mattered to us for proving Lemma 5.2.3 and so Proposition 5.2.6).
What can we say about the other way around? When does the existence of imply the existence of ?
We can note Proposition A.2.3 and Remark A.2.4.
supp() .
Say has support interpolation when if then there exists a such that
(Interpolation is used here by analogy with the concept in logic [GM05]; what we are interpolating is the set of names.)
Suppose has support interpolation and suppose exists for all and .
Then exists for all and and is equal to .
Suppose all strict fresh-finite limits exist. Consider some and .
— We show that if and # then . Suppose and #. By support interpolation there exists a with and supp() supp() supp(). By assumption and so
— We show that is least with this property. By Lemma A.2.1 supp() supp(). Thus in particular #. Also by construction . Thus for any other greatest element in #, .
Thus, exists and is equal to .
In the absence of support interpolation Proposition A.2.3 may fail. For instance, consider a nominal poset consisting of singleton atoms and unordered pairs of atoms and an element , such that:
— for all (distinct) and .
— for all .
We assume the natural pointwise permutation actions and , so that supp( and supp( and supp(.
Then but does not exist since .
B. ADDITIONAL PROPERTIES OF THE CANONICAL MODEL
We noted in Subsection 11.6 that has structure above and beyond being in inDi. We conclude with some further reflection on this.
These properties were not needed for our main results, but they seem striking enough to merit a note in an Appendix.
B.1. commutes with unions
We consider from Notation 10.2.1 in and prove Corollary B.1.3: commutes with sets union (cf. a similar property for proved in Lemma 11.8.14).
This property is not valid in general in inDi, because and do not commute with in general,47 but it does hold in the canonical model .
).
We reason as follows:
(().
We reason as follows:
.
B.2. An existential quantifier
from Definition 11.1.3 has a universal quantifier, defined in Definition 11.3.1. Proposition 11.1.8 hints that an existential quantifier might also exist.48 Indeed this is so, and it is not hard to construct:
Suppose and . Define by:
We shall see that is dual to Definition 11.3.1.
If then .
We verify the conditions of Definition 11.1.3:
(1) Proof that implies . Suppose , so that [:] for every . If then by condition 3 of Definition 10.3.7 also [:][:], and using condition 1 of Definition 11.1.3 also [:] . Thus as required.
(2) Proof that . Suppose is fresh (so #). Unpacking Definition 11.1.1, we need to show that ([:]). Suppose , so [:]. Since # by Proposition 11.1.6 also and [:][:]. It follows that [:][:] thus [:] , thus .
If then .
If then supp()supp().
If and and supp() supp() then .
In other words, is the greatest point contained in for which is fresh; compare and contrast this with the dual characterisation of in Definition 11.3.1.
Nominal spectral spaces do not have an existential quantifier in general. Given a nominal spectral space and an open set opens(), the obvious candidate for is [] . This is just the dual of Definition 5.2.1.
However, this is not necessarily an open set because [] is not necessarily strictly finitely supported. See condition 4 of Definition 7.1.1, and Remark 7.1.3.
B.3. Interaction of and with application and
The universal and existential quantifiers interact with similarly to how interacts with . We need Lemma B.3.1 as a simple technical lemma:
If then .
Routine from Definition 11.3.1.
If # then () ().
If # then ()().
Suppose #. Then ()[([]).
Notes
1It may be worth amplifying on this, just a little. We face design questions such as: Should the points be finitely-supported, assuming the open sets are? What is the proper notion of filter, in this context? Should covering sets be finitely supported? Should they be strictly finitely supported? In the presence of an -action, what is the correct notion of freshness for a set of points, anyway? And so on; dozens of such questions are addressed in the technical material to follow. Anybody doing topology and/or duality in nominal sets—we hope and expect that others will follow us here—will encounter similar questions, and so could benefit from an analysis of the answers we arrived at in this paper and in [Gab11b]. ↩
2We carry out a similar programme for variables of first-order logic in [Gab11b; Gab12]. ↩
3Our paper handles only the case where we have -expansion. We believe this could be generalised to the fully non-extensional case, at some cost in complexity. See Subsection 12.1.3. ↩
4Writing them certainly did. ↩
5There are actually two duality results: one for impredicative distributive lattices (corresponding to a propositional logic with , , and propositional quantification) from Part I, and the other when we add the combination structure in Part III. The second duality piggy-backs on the first, and is shorter. ↩
6Just sometimes, pedantry has its limit. ↩
7Here is understood to contain all the variables mentioned in the predicate. It is not the case that if and only if —but it is the case that if and only if . ↩
8Parts 1 and 2 of Theorem 2.3.1 are morally the same result: by considering to be a function from its arguments to the nominal set of Booleans from Subsection 2.2; and by treating a function as a functional relation, i.e. as a binary predicate. ↩
9The reasoning in this paper could in principle be fully formalised in a sets foundation with atoms, such as Zermelo-Fraenkel set theory with atoms ZFA. Nominal sets can be implemented in ZFA sets such that nominal sets map to equivariant elements (elements with empty support) and the permutation action maps to ‘real’ permutation of atoms in the model. See [Gab11a, Subsection 9.3] and [Gab11a, Section 4]. ↩
10There is also a nice proof of this fact by direct calculations; see [Gab11a, Theorem 2.19]. However, it just instantiates Theorem 2.3.1 to the particular specifying support. ↩
should not use the axiom of choice. Every used in this paper will satisfy this property. ↩
12Axiom (id) might be more pedantically written as [. ↩
13That is, the axioms except (a), since we do not assume a function . Axiom (id) can be more pedantically written as [. ↩
14...not just the finitely-supported ones; here might not have finite support and we build examples of this later in Theorem 6.1.13. ↩
15Our notion of -algebra permits the possibility of without finite support; see Definition 3.2.1. The -algebra underlying () in Definition 8.1.5 need not have finite support; the action happens in Theorem 6.1.13 where we use Zorn’s Lemma to make infinitely many choices. In contrast, the -algebra underlying in Definition 11.1.3 does have finite support. ↩
16So is transitive, reflexive, and antisymmetric, and if and only if . ↩
17There is also a notion of finitely fresh-cocomplete, but we will not need it. ↩
18Strictly speaking we should write [()]. See the notation in Definition 3.1.1. ↩
19A dual version of part 1 of Definition 4.4.1 is ()() and by a standard argument [DP02, Lemma 4.3] the two are equivalent. ↩
20Atoms get mapped into by , and gets mapped into by so atoms get mapped into . ↩
21We could take Definition 5.2.1 to be []—see line 2 of Proposition 5.2.8—but this has the disadvantage that it is not necessarily an intersection of a strictly finitely supported set. ↩
22We need and to build filters. Later on when we model the untyped -calculus in Subsection 10.2, we will need , , and . We will not need an existential . The existential may still exist; see Appendix B.2. ↩
23We do not insist on finite support here. ↩
24We assume that is finitely supported because in Definition 4.1.1 we assume () is a nominal set. We do not assume that a filter is finitely supported in Definition 6.1.1. This means that we may assume that is fresh for under the quantifier, but we do not know that is fresh for . This will not be a problem. ↩
25A prime filter satisfies this property—for finite . ↩
26Unpacking Definitions 6.3.1 and 7.6.1, is the set of prime filters of compact opens of of which is an element. ↩
27The even more interested reader is referred to Proposition 9.3.7, where () is just what we need for the final stages of the proof. ↩
28For instance, inDi has a -action, and this is reflected dually as an -action on prime filters. Similarly, has a permutation action; permutations are invertible, so the dual structure on prime filters is ...another permutation action. ↩
29We do not assume that has finite support so we do not know that #, but that will not be a problem. ↩
30Lemma 2.3.4 is applied here to the function . Equivariance is defined in Definition 2.1.6; Definition 9.4.8 states (amongst other things) that this function is equivariant. ↩
31It might be helpful to unwind the definitions for this final clause. This is not complicated—it just takes in a lot of definitions! is an element of the termlike -algebra over which () has an -action; is an element of the (impredicative) nominal distributive lattice with and ; () is the set of prime filters in points() that contain . By Proposition 7.3.8 this set of prime filters is compact, that is it is in cpct(), as required in Definition 7.5.2. ↩
32We could allow constants c too, if we wished. ↩
33...using nominal abstract syntax [Gab01; GP01] or by taking equivalence classes or by whatever other method the reader prefers. ↩
being a preorder means precisely that it is transitive and reflexive. (A partial order is an antisymmetric preorder.) Equivariance means that implies . See Definition 2.1.6 and the discussion in Subsection 2.2.2. Another description of this is that as an element of pow(LmTm LmTm) (Subsection 2.4.1), has supp(. ↩
35An equivalence relation is a symmetric preorder, so a -equality theory is, as one would expect, just a symmetric -reduction theory. ↩
36In the case for , is the copy of in the termlike -algebra (Definition 3.1.1) and is the function mapping to (see Definition 4.5.1 and Notation 4.5.3). We have written as just , but here we prefer the more careful notation. Of course, if we wanted to be really careful we would also mention that is itself shorthand for () from Definition 3.1.1. But the reader probably is not interested in that high level of pedantry, and may even be confused by it, so we will not labour the point further. ↩
37It is descended from nominal rewriting, which considers rewriting over nominal terms [FGM04; FG07]. ↩
38The papers wrote axioms and proved them sound and complete. So we really did check that the axioms do what one would expect them to do; no more and no less. ↩
39This fact is most likely a special case of a general result which deserves a paper written in its own right. For this paper, we are simply grateful for the fact and we press on to make good use of it. ↩
40Broadly speaking, within a given class of structures, the less structure we assume the more challenging the duality result is to prove. If duality theory were a competitive sport then it would be like golf: the lower your score the better your game. ↩
41So canonical models are like tennis: more points is better. ↩
42This took a couple of years: once the first author understood that for a duality result, a dual to was needed, the paper was easy to write. At least, for a certain highly technical value of ‘easy’. ↩
43Page 2 of [Sal03] includes a brief but comprehensive history of such results. The first incompleteness result was given in [HDR92] for the continuous semantics (Scott’s construction). This was followed by several generalisations. Salibra’s treatment has the benefit of covering a range of semantics in a uniform way. ↩
44Something similar happens in category theory when we talk about ‘the category of all sets’; what does that live in? This is usually left unspecified, which is usually fine. ↩
45...and this is exciting. Most of this paper works by building various -algebras over relatively simple nominal algebraic structures like sets of points. What more could be achieved if we gave ourselves an entire mathematical foundation structure to play with? ↩
46The nominal HSPA theorem states that every nominal algebra model is a subobject of a homomorphic image of a cartesian product of atoms-abstractions of free algebras (atoms-abstraction for nominal algebras is defined in [Gab09a], as is ‘free algebra’ and so on). In spirit, this is like the factorisation of natural numbers into primes or any other number of similar factorisation theorems. It is useful because it constrains the structure of models, and it is one of the applications of abstract algebraic techniques. The result proved in [Gab09a] considered an untyped syntax, but we expect it to generalise unproblematically to the typed case, if necessary. ↩
47The closest we get to this in the general case is () from Figure 3 and () from Figure 4 ↩
48Why? Because the proof of Proposition 11.1.8 would be simple and direct if we assume that is strictly finitely supported. The fact that it works for all finitely supported suggests there might be some way of removing atoms from the support of while also making smaller as a set. This is exactly what an existential quantifier on points would do (recall that everything is inverted/dual in ). ↩