PNL to HOL: from the logic of nominal sets to the logic of higher-order functions
Murdoch J. Gabbay
Abstract
Permissive-Nominal Logic (PNL) extends first-order predicate logic with term-formers that can bind names in their arguments. It takes a semantics in (permissive-)nominal sets. In PNL, the -quantifier or -binder are just term-formers satisfying axioms, and their denotation is functions on nominal atoms-abstraction.
Then we have higher-order logic (HOL) and its models in ordinary (i.e. Zermelo-Fraenkel) sets; the denotation of or is functions on full or partial function spaces.
This raises the following question: how are these two models of binding connected? What translation is possible between PNL and HOL, and between nominal sets and functions?
We exhibit a translation of PNL into HOL, and from models of PNL to certain models of HOL. It is natural, but also partial: we translate a restricted subsystem of full PNL to HOL. The extra part which does not translate is the symmetry properties of nominal sets with respect to permutations. To use a little nominal jargon: we can translate names and binding, but not their nominal equivariance properties. This seems reasonable since HOL—and ordinary sets—are not equivariant.
Thus viewed through this translation, PNL and HOL and their models do different things, but they enjoy non-trivial and rich subsystems which are isomorphic.
Key words: Permissive-nominal logic, higher-order logic, nominal sets, nominal renaming sets, mathematical foundations of programming. MSC-class: 03B70 (primary), 68Q55 (secondary) ACM-class: F.3.0; F.3.2
June 7, 2012
1. Introduction
Permissive-Nominal Logic (PNL) extends first-order predicate logic with name-binding term-formers. For instance first-order logic, set theory, and the untyped -calculus axiomatise in PNL; their binders , comprehension, and are just modelled as binding PNL term-formers. The canonical semantics of PNL is in nominal sets, and it is first-order.
Higher-order logic (HOL) also has binding [Mil92a, Far08]. This has been used to encode other binders, e.g. the Church encoding of quantifiers as constants of higher type such as : () [And86, Chu40]; higher-order abstract syntax (HOAS) encoding term-formers of an encoded syntax with binders as constants of higher type such as : () or : () (strong vs. weak HOAS)1 [DH94, PE88]; and higher-order rewrite systems [MN98].
Since PNL is first-order and has a sound and complete semantics (so expressivity and models are fairly ‘small’), whereas HOL is higher-order (so expressivity and models are fairly ‘large’), the natural direction for a translation is from nominal sets and PNL, to functions and HOL (a shallow embedding of PNL into HOL).2
In this paper we translate a subsystem of PNL into HOL and prove it sound and complete using arguments on nominal sets and and nominal renaming sets models [GH08]. The proof of completeness involves giving a functional semantics to nominal terms, and a nominal semantics to -terms in the spirit of Henkin models [And86, BBK04]. This involves a construction on nominal sets models corresponding to a free extension to nominal renaming sets, as previously considered by the second author with Hofmann [GH08].
The partiality of the translation of PNL seems to be inherent and reflects natural dif-ferences in structure between nominal and ‘ordinary’ sets; nominal sets are subject to the action of a symmetry group of atoms-permutations, which cannot be naturally represented in HOL or its ‘ordinary’ sets semantics. That is, it is not the case that nominal techniques are ‘just’ a concise presentation of HOL with a weakened -equivalence (e.g. higher-order patterns [Mil91]). There is that, but there is also more. The nominal and functional models of binding are distinct, but they do have non-trivial and rich subsystems which are isomorphic in a sense made precise in this paper.
1.1. Some background on PNL
We study PNL for its own sake in this paper, but the interested reader can find example nominal theories in the literature: for substitution, -equivalence, and first-order logic [GM06a, GM08a, GM10, GM06b, GM08b].
These axiomatisations are in nominal algebra (which can be viewed as the equality fragment of PNL) and are accompanied by proofs of correctness in the respective papers.
Not all PNL theories are expressed in the equality fragment. For instance, in the papers which introduced PNL [DG10, DG12] we included theories of first-order logic and arithmetic which put universal quantification to the left of an implication.
To give some idea of what this family of logics looks like in practice, assume a name-sort and a base sort and term-formers lam : ([]), app : (), and var : (). (Full definitions are in the body of the paper.) We sugar lam([]) to and app() to and var() to . Atoms in PNL are a form of data and populate their own sort ; so var serves to map them into the sort , where they represent object-level variables.
Here is -equivalence, written out as it would be informally:
( if is not free in
Here is a PNL axiom for -equivalence, written out formally:
(See [GM10] for a detailed study of this axiom in a nominal context.)
is an atom and corresponds to the object-level variable ; is not a PNL variable but it represents a variable of the object level system being axiomatised. is an unknown and correspond to the meta-level variable ; is a variable in PNL and may be instantiated.
The reader can see how similar the two axioms look. Their status is different in the following sense: whereas is typically taken to range over terms, ranges over elements of nominal sets (via a valuation; see Definition 6.3). This is possible because nominal sets have a notion of supporting set of atoms which mirrors the free variables of a term.
The condition pms() is a typing condition in PNL. The types, or permission sets as we call them, restrict the support of denotations associated to by a valuation. They correspond to freshness side-conditions in nominal terms from [UPG04] and to informal freshness conditions of the form ‘ not free in ’ in informal practice. To see this intuition made formal see a translation from nominal terms to permissive-nominal terms in [DGM10].
There is no requirement to axiomatise -equivalence because this is done automati-cally by the PNL system.
For instance, axioms for -equivalence [GM10] are:
See [GM10] for a proof that these axioms really do axiomatise the -calculus.3
It is important to appreciate that most models of the axioms above are abstract and algebraic, not concrete and syntactic. So for instance the final axiom is not admissible because the objects ranges over do not necessarily have inductive structure and we cannot necessarily push the -redex in to the atoms.
In particular, this is not a paper about representing syntax-with-binding, unlike the first applications of nominal techniques to syntax-with-binding [GP01]. True, we wrote above that atoms represent object-level variables. But indeed, they represent variables, not variable symbols. Nominal sets admit open elements and we can write axioms about names and binding in PNL, so that the full behaviour of variables is in PNL susceptible to algebraic axiomatisation. For instance the equality axioms above give atoms the behaviour of -convertibile -calculus variables; see [GM10] for a proof. Most models of the theory above are not built out of syntax.
Several nominal algebraic theories have been developed, with proofs of correctness: see [GM08a] (substitution), [GM10] (-calculus) or [DG10, DG12] (first-order logic and arithmetic). For examples of natural non-syntactic models of nominal-style theories see [DG12, Subsection 5.2] and [Gab11b].
Thus, the design philosophy of PNL is that axioms should look like what we would write informally anyway, where variables map to atoms, meta-variables to unknowns, binding to atoms-abstraction, and capture-avoidance conditions to choice of permission sets. In particular, open terms and predicates map to elements and subsets of nominal sets with non-empty support.
1.2. On symmetry
The thing that goes missing in the translation from PNL to HOL is name-symmetry. Nominal sets are sets with an action of permutations of atoms; that is, nominal sets are sets with a symmetry action.
It turns out that this symmetry is key. For instance, we can define define atoms-abstraction as a symmetric equivalence class (Definition 5.29, in this paper). This class is ‘first-order’ in flavour and does not involve the construction of a full function-space.
In PNL syntax permutative symmetry is reflected in the use of atoms and atoms-abstraction and by the permutations in terms (the interested reader could look at the ‘symmetry-based’ definition of -equivalence in Definition 2.18).
In PNL derivation this is reflected in the axiom rule (rule (Ax) of Figure 1 in this paper). This rule gives that for all PNL predicates; so PNL predicates are fully symmetric up to permuting atoms. This is impossible to model in HOL because functional abstraction is asymmetric: obviously, is not equal to .
Truth in restricted PNL (Figure 2) is also asymmetric; restricted PNL is therefore a weaker system. It still has nominal semantics, but its predicates are not symmetric. This is the logic that we translate to HOL.
The symmetry of full PNL might seem counterintuitive—especially if the reader is used to modelling names as functional arguments (or indeed as numbers). We do not expect () to be symmetric with (), or (for numbers) to be symmetric with .
Consider the predicate in PNL (assume an equality, for the sake of argument). This is false because is a distinct atom from . If the reader is used to thinking of variables as things that ‘vary’ then might be either false or true depending the values associated to and . Not so in PNL: at the level of PNL syntax atoms are not variables; and are distinct; and their distinctness is symmetric up to permuting atoms so that , , and are also false. If the reader is used to thinking of variables as numbers then there might exist some predicate that puts them in order. Not so in PNL: such a predicate is forbidden.4 The unknowns and in PNL do vary, and they are variables. More on this in Remark 2.22 and Subsection 2.6.
1.3. Map of the paper
This paper has a lot of technical ground to cover. This is unavoidable, because we need to deal with two logics (restricted PNL and HOL) and two semantics (nominal sets, and the hand-crafted Henkin models in nominal renaming sets used in the completeness proof), as well as two translations (from logic to logic, and from models to models).
For the reader’s convenience, we provide an overview of the main technical points with brief justifications for their design:
Section 2 introduces permissive-nominal logic. This comes from previous work into ‘nominal’ axiomatisations of systems with binding [DG10, DG12].5 In fact, we need to introduce two logics: full PNL and also a restricted version which has a weaker non-equivariant axiom rule. We write the entailment relations and respectively. It is the restricted version that we will eventually translate to HOL.
Section 3 introduces higher-order logic as a theory over the syntax of the simply-typed -calculus. We write the entailment relation .
Section 4 defines the translation from restricted PNL to HOL, and proves it sound using arguments on syntax. In order to do the translation, we need to introduce a capture typing : which is a measure of how many functional abstractions are required to translate a given nominal term without losing information; that is, of the functional complexity of a nominal term.
Our goal is then to prove completeness of the translation. We do this by transforming models of PNL into models of HOL. So Section 5 introduces two categories: PmsPrm of permissive-nominal sets and PmsRen of permissive-nominal renaming sets. We also give a free construction, transforming a permissive-nominal set into a permissive-nominal renaming set.
In Section 6 we interpret full and restricted PNL in PmsPrm. In Section 7 we interpret HOL in PmsRen.
Finally, in Section 8 we use the free construction of Section 5 to map a model of PNL in PmsPrm to a model in PmsRen, and because the free construction does not ‘make anything equal’ this is sufficient to prove completeness.
As one further mathematical note, the results in the literature concern full PNL and not restricted PNL. So in Appendix A we sketch proofs of soundness, cut-elimination, and completeness of restricted PNL with respect to non-equivariant models in PmsPrm. These are modest, if not entirely direct, modifications of the existing definitions and proofs for full PNL and equivariant models in PmsPrm.
Quite a number of new ideas are required to make this all work. The highlights are: permissive-nominal renaming sets and their application to give non-standard ‘nominal’ Henkin models for higher-order logic; restricted PNL and its semantics; the free construction; and the technical arguments as discussed in Section 8.
1.4. Review of motivation
Given that the proofs and constructions in this paper are non-trivial and involve an effort to extend existing machinery, we should pause to ask again why doing this is justified, even necessary.
Nominal techniques were designed originally to reason on syntax-with-binding (see the original journal paper [GP01] or a recent survey paper [Gab11a]). But since then this remit has expanded to reasoning about denotations with binding more generally (an overview of which is in [Gab12b]). In doing this, we have created a whole new syntax and semantics for meta-mathematics.
We will not argue for or against either the nominal foundation or the higher-order foundation for mathematics.6 Our question is: given that these two foundations exist, how do they relate?
In fact, questions have been asked about how nominal names and binding are related to functions, ever since nominal techniques were conceived in the second author’s thesis. Since then, the development of PNL [DG12] and nominal renaming sets [GH08] has given us two powerful new tools with which to address these questions: a proof-theory for a logic in which nominal reasoning so far can be formalised, and a visibly nominal semantics which is not based on permutations but on possibly non-bijective renamings on atoms, so that atoms-abstraction can be considered as a function in that semantics.
In this paper, we leverage this to give a precise, concrete, and mathematically detailed account of how these two worlds really stand in relation to one another—and how they differ. In conclusion we speculate that there is some potential (not explored in this paper) that our translations might be used to piggyback nominal techniques on the substantial implementational efforts that have gone into developing HOL over the past seventy years.
2. Permissive-Nominal Logic
Permissive-nominal logic is a first-order logic for nominal terms quotiented by -equivalence. Doing this is not entirely trivial; the interested reader can find more on this elsewhere [UPG04, DG10, DG12, Gab12b].
2.1. Syntax
Examples of base sorts are: ‘-terms’, ‘formulae’, ‘-calculus processes’, and ‘program environments’, ‘functions’, ‘truth-values’, ‘behaviours’, and ‘valuations’.
Examples of name sorts are ‘variable symbols’, ‘channel names’, or ‘memory loca-tions’.
[] is an abstraction sort. This does a similar job to function-types in higher-order logic but note that must always be a name-sort. The behaviour of a term of sort [] corresponds to ‘bind a name of sort in a term of sort ’. Such a term does not denote a function, though later on in our completeness proof we will deliberately undermine that intuition to obtain our completeness result.
For each fix a disjoint countably infinite set of atoms , and an arbitrary bijection between and the integers 0 -1 1 -2 2. Write
Finally, write
will range over distinct atoms (we call this the permutative convention).
A permission set has the form () where and are finite (and a permission set may be finitely represented by the pair ()). , , and will range over permissions sets.
The use of and ensures that permission sets are infinite and also co-infinite (their complement is also infinite).
Permission sets are simple, but surprisingly subtle.
and are reminiscent of some treatments of syntax where a formal distinction is made between ‘names that exist to be bound’ and ‘names that exist to be free’. See for instance the freie and gebundene Gegenstansvariable of Gentzen [Gen35, Section 1], and the individual variables and parameters of Prawitz [Pra65, Section 1], or Smullyan [Smu68, Chapter IV, Section 1].
However, for any given atom there is no fixed sense in which it is either capturable or not capturable. Each permission set defines a world of capturable/non-capturable atoms. Furthermore, even once a permission set is fixed, we shall see that permutations can shift an atom from one to the other. See Example 2.20 and Remark 2.28 for examples of permission sets in action, controlling -equivalence and substitution respectively.
We make and both infinite so that we have inexhaustible supplies of both kinds of atom.7 Further technical discussion of the advantages of permissive-nominal techniques is in [DGM10].
A term-signature over a sort-signature () is a tuple ( ar) where:
and are disjoint sets of term- and proposition-formers. f will range over term-formers. P will range over proposition-formers.
ar assigns to each f a term-former arity () and to each P a proposition-former arity , where and are in the sort-language determined by (). We will write (()) just as ().
is a set of unknowns , each of which has a sort sort() and a permission set pms(), such that for each sort and permission set the set sort( pms( is countably infinite. will range over distinct unknowns.
A signature is then a tuple ( ar).
We write f : () for ar(f) and similarly we write P : for ar(P.
The signature for the -calculus from the Introduction has a name-sort for -calculus object-level variables , a base sort for -terms, and appropriate term-formers:
var : () to form -calculus variables in out of names in ,
app : () for application, and
lam : ([]) taking an abstraction in [] and forming from it a -abstraction term in .
A permutation is a bijection on such that () and nontriv(() is finite. Write for the set of permutations. Given let a swapping () be the bijection on atoms that maps to , to , and all other to themselves.
We use the following notation:
Write for functional composition, so ()((())).
Write id for the identity permutation, so id( always.
Write for inverse, so id.
Continuing Example 2.6, we have the following terms and propositions:
var() : where .
[] : [] where and sort(.
lam([]) : since [] : [] and lam : ([]).
P(lam([])) is a proposition if P is a proposition-former and P : ().
2.2. Permutation, substitution, and so on
These definitions are all needed for the rest of the paper, starting with -equivalence in Subsection 2.3. We need them at both levels; both for atoms and for unknowns.
Define a (level 1) permutation action on syntax by:
Let Π range over sort- and permission-set-preserving bijections on unknowns (so sort(Π(sort() and pms(Π(pms()) such that Π() is finite.
Write Π for functional composition, Id for the identity permutation, and Π-1 for inverse, much as in Notation 2.8.
Define a (level 2) permutation action by:
A curious asymmetry between Definitions 2.11 and 2.12 is that ( but Π(Π()Π. Note that not applied to the binding occurrence of , but Π is.
In fact, we could take (. We would have to complicate Definition 2.9 by introducing as well-formed syntax, but we could do this. However, it turns out that this would make no difference. It turns out that and are logically equivalent.
To gain a quick intuitive understanding of why this is so, bear in mind that the substitution ‘ maps to ’ maps to (this is made formal later, in Definition 2.26) and in fact ‘ maps to ’ would map to (the interested reader can find a wider discussion of this in and around [Gab12b, Remark 3.4.7]).
So, rather curiously, means the same thing and would receive the same denotation, regardless of : this would be the denotation of the PNL proposition . We can therefore simplify our syntax and take (.
Something similar happens in the much more abstract semantic context of two-level nominal sets; see [Gab11c, Lemma 2.25]. Further comments on asymmetries between atoms and unknowns in PNL will follow in Remark 2.22.
Suppose is a function on a set and . Define by
This is the standard pointwise action of a function on a set. We use this for acting on sets of atoms, Π acting on sets of unknowns, and (from Definition 5.1 onwards) acting on sets of atoms.
Define free atoms fa() and fa() by:
Define free unknowns fU () and fU () by:
fa(fa() and fa(fa().
Also, fU (ΠfU () and fU (ΠfU ().
By routine inductions on .
2.3. -equivalence
The use of permissive-nominal terms allows us to ‘just quotient’ syntax by -equivalence. We can do this for both level 1 variable symbols (atoms) and level 2 variable symbols (unknowns).
Call a relation on terms and on propositions a congruence when it is closed under the following rules:8
Write () for the (level 1) swapping permutation which maps to and to and all other to themselves. Similarly, provided sort( sort() and pms( pms(), write () for the (level 2) swapping.
Define -equivalence on terms and propositions to be the least equivalence relation that is a congruence and is such that:
Definition 2.18 is inductive, but the reader familiar with nominal terms from e.g. [UPG04, DGM10, DG12] might be familiar with a more syntax-directed inductive characterisation whose characteristic rules for atoms would look like this in our current notation:
The form of Definition 2.18 is more compact and more abstract. It was introduced in [GM06a, GM07] (in particular see [GM07, Lemma 3.2] and the discussion surrounding it); a detailed proof of an equivalence of the two presentations is in [GM08a, Theorem 2.31]
We illustrate Definition 2.18. Suppose : and : for some name sort and base sort . Also suppose pms() and suppose pms().
1. We -convert and in [][].
First we note that fa([]) so by symmetry [] ()[]], and by congruence [][] [][]. Next we note that fa([][]) so by symmetry [][] ()[][]][]. We use transitivity.
2. We -convert [][] to [][]. We reason as follows: [][] [][] [][].
3. We -convert (()()) to . First we note that fa(())pms(), so (() ()))(() () . Then we note that fa() so () . We use transitivity.
4. We -convert and in P([]). Using () and () we deduce:
It is routine to convert this sketch into a full derivation-tree.
5. In [GM06a, GM06b] an axiom of substitution/-equivalence was stated which, translated to a permissive-nominal syntax, is expressed thus:
Since fa([]) we have [] [](). Writing for an unknown with pms()pms() we can therefore rephrase this axiom as follows:
This is the form that the same axiom took in [GM10]; that paper used the slightly less flexible nominal terms framework, so the equivalence noted above had to be the subject of a proof [GM10, Lemma 2.16].
It is not hard to prove by inductive arguments that the definition of -equivalence here gives the same result as that found for instance in [DG12, Subsection 2.4] or [DG10, Definition 2.16].9
Atoms and unknowns both have permutation actions and both participate in -conversion and both ‘look like’ variable symbols. Indeed, in the translation to HOL of Subsection 4.1 atoms and unknowns both are translated to variables. However, in PNL syntax atoms and unknowns are very distinct:
Atoms populate only their own special name-sorts . Unknowns populate any sort.
Unknowns depend on atoms in the sense that pms() is a set of atoms. Atoms do not depend on anything.
Atoms and unknowns both get permuted in syntax but only unknowns also have a substitution action (defined next in Subsection 2.4). Conversely, only atoms-permutation is explicit in the syntax, as (there is no Π in any , only an action of Π on ).
If is proposition then is a proposition, but is never well-formed syntax.
Later on when we build the denotation in Subsection 6.2, atoms are interpreted as themselves (so ) whereas unknowns are interpreted via a valuation, in typical Tarski style (so ()).
Why this asymmetry?
PNL is a first-order logic. Therefore it has a syntactic class of variables which we call unknowns , with an unknowns-substitution action [] (Definition 2.27), a universal quantifier , -conversion, and a denotation using valuations for unknowns () (Definition 6.4).
PNL treats atoms (names) as a special kind of symmetric data (i.e. data with a group action). It has sorts for atoms which are populated by atoms-as-terms, a nominal-terms style explicit permutation to permute atoms in terms, atoms-abstraction [] to bind atoms in terms, and a nominal sets style semantics for atoms as themselves; so that and [] ] (Definition 6.4).
PNL is expressive enough to axiomatise a substitution action for atoms, and even a universal quantifier for atoms. Thus we can make atoms behave like first-order logic variables, if we want to do this. For more on these and other nominal theories see [GM08a] or Figures 4 and 5 of [DG10, DG12].
The asymmetry noted above reflects the standard design of first-order logic: unknowns ‘live in’ in the sense that they are used to make universal assertions , and atoms ‘live in’ in the sense that they interact with the term- and sort-system and we can form [] and f().
What can be a little confusing is that can mimic variables, and indeed, we can and do use PNL to axiomatise logic. In short: PNL is a first-order logic for axiomatising logics.
We can still ask to what extent it might be possible to go beyond PNL and to ‘fold’ unknowns back down into the syntax, possibly recursively, to obtain some language and/or semantics in which atoms and unknowns are just two aspects of a single well-founded structure.
In fact this idea predates PNL: the Lambda Context Calculus (LamCC) [GL08, GL09] features just such an infinite hierarchy, but it has no semantic theory, no primitive notion of proposition, and has a weak notion of -equivalence.10 Concurrently with PNL, in two recent papers [Gab11c, Gab12a] the first author has investigated these questions from a semantic perspective. In [Gab11c] we develop an abstract notion of two-level nominal set that can directly interpret unknowns and atoms just as the nominal sets of this paper directly interpret atoms . In [Gab12a] we develop a concrete model of unknowns as infinite lists of distinct atoms. It would be future work to integrate these semantics into a new logic.11 A PNL-like logic with more than two levels of variable and a perfect symmetry across levels, is certainly imaginable.
2.4. Substitution
A (level 2) substitution is a function from unknowns to terms such that:
For all , () : sort() and fa(()) pms().
( id for all but finitely many .
will range over substitutions.
Define nontriv() by:
nontriv(()id or fU (()) for some
nontriv() is unknowns that can be produced or consumed by , other than in the trivial manner that ( id.
One kind of substitution will be particularly useful, starting with (L) in Figure 1:
Suppose : and : and fa() pms(). Define [] by:
[]( []( all other
It is easy to verify that [] is indeed a substitution.
Famously, nominal terms substitution is capturing [UPG04, Definition 2.13]. We spell out how this works in our permissive-nominal context: Suppose pms() and pms() (where we assume appropriate sorts). Then:
([])[]. The in the substitution [] has been captured by the [].
It is impossible to even ask what ([])[] is equal to because [] is not a substitution, since pms(). So pms() cannot be captured by a substitution [], because that substitution does not exist.
Also, []()]. By construction,
So the choice of representative of [] does not matter for capture to occur.
In [Gab12a] we propose a view of as a well-ordering on its permission set; that is, we identify literally with an infinite list of atoms. Viewed from this perspective, the nominal substitution action is not capturing at all: it is simply a compact way to present an ‘infinite raising’ or ‘infinite Skolemisation’ (cf. Remark 4.5), or a de Bruijn index [dB72]. This idea underlies also the translation to HOL which we construct later in Definition 4.3.
2.5. Sequents and derivability
Φ and Ψ will range over sets of propositions. We may write Φ and Φ as shorthand for Φ (where we do not insist that Φ, that is, the union need not be disjoint).
A sequent of restricted PNL is a pair Φ Ψ.
A sequent of full PNL is a pair Φ Ψ.
Write fU (ΦfU () ΦfU () Ψ.
The sole difference between Figures 1 and 2 is in the axiom rule, and is highlighted with a light blue rectangle.
We may write Φ Ψ as shorthand for ‘Φ Ψ is a derivable sequent’. We may write Φ Ψ as shorthand for ‘Φ Ψ is not a derivable sequent’.
Similarly for Φ Ψ and Φ Ψ.
2.6. Discussion of the PNL axiom rule
Figure 1 is the logic of [DG12, Gab12b]. Figure 2 is the logic we translate to HOL in this paper. The only difference is the ‘’ in the axiom rule: full PNL has it (see (Ax)), and restricted PNL does not (see (Ax)). Restricted PNL is a subset of full PNL, in the sense that (obviously) Φ Ψ implies Φ Ψ (this suggests that the models of restricted
PNL should be a superset of those of full PNL, which will indeed turn out to be the case; see Appendix A).
Why the difference? Because the translation to HOL identifies atoms with functional arguments. Atoms are symmetric up to permutation in full PNL; this is built into (Ax) in Figure 1. Functional arguments are typically not symmetric.
We might try to translate full PNL to HOL by translating ! permutation instances of each or , where is some notion of the number of atoms in or (cf. capture typings in Definition 4.7); but that would be ‘cheating’ in the sense that most of the syntax would then be generated by a meta-level ‘macro’ which does ! amount of work. The issue here is not whether PNL can be encoded in HOL; the issue is whether it can be cleanly translated into HOL. These are related but distinct questions.
To quickly see the difference in derivational power between full and restricted PNL, assume a name sort , a proposition-former P : , and two atoms : . Then the difference in the entailment relations of PNL and restricted PNL can be summed up as follows:
P() P() and
P() P() but
Note that not even full PNL can derive that () entails (); we can permute, but we have to permute in the entire proposition. So for instance if we axiomatise the syntax and derivability of first-order logic in PNL then we would have a predicate entails and we might prove entails(P() P()). By equivariance of full PNL we could also derive entails(() P()).12 However, we still cannot derive entails(P() P()), and if we could then that would be wrong.
In Appendix A we see that this difference corresponds in models to proposition-formers being interpreted by equivariant functions (for full PNL) or not necessarily equivariant functions (for restricted PNL).
It has to be this way: Definition 4.3 translates PNL terms and predicates to HOL terms and predicates. In Lemma 4.17 we illustrate why only restricted PNL can be translated to HOL by our translation: the derivability of full PNL is too strong for HOL derivability and the translation would not be sound.
Note that this does not prove that other translations to HOL do not exist, but (as the discussion of ! above suggests) we speculate that they would be significantly less natural.
3. HOL syntax and derivability
Higher-order logic (HOL) syntax and derivability should be familiar [Mil92a, Far08, And86, Chu40]. We give the basics.
3.1. Syntax
We present HOL as a derivation system over simply-typed -terms with constants and types for logical reasoning (like a type of truth-values and constant symbols like and ). This is all standard.
It is not necessary to include products (), but for the purposes of translating PNL into HOL doing this is convenient.
A term-signature over a HOL signature is a tuple ( type) where:
is a set of constants, which must contain elements , , and for every type .
type assigns to each g a type in the type-language determined by , such that type(, type(, and type() .
A signature is then a tuple ( type).
We write g : for type(g.
We strongly deprecate referring to the constant : () as ‘higher-order abstract syntax’ (HOAS), as sometimes happens. That term should refer to inductive types with binding constructed using constants of higher type like (Λ Λ) Λ (strong HOAS) or ( Λ) Λ (weak HOAS) [DH94, PE88] (the study of inductive syntax with binding is not the topic of this paper).
A term : () (plus axioms) expresses the meaning of [Chu40, Section 2] and would still have meaning if our syntax was, e.g. combinators. In contrast, the syntax of combinators could be represented without any need for higher-order syntax, since it does not have binders [HS08, Section 2].
For each signature type) and each type over fix a countably infinite set of variables of that type.
will range over distinct HOL variables.13 Write type() for the type of .
We now define -equivalence. We would not normally be so detailed about this, but when we map PNL terms and propositions to HOL later, it will be useful to have been precise here:
A permutation of HOL variables is a bijection such that nontriv( () is finite. Give HOL terms a permutation action defined by:
Free variables are defined by:
Call a relation on HOL terms a congruence when it is closed under the following rules:
Define -equivalence to be the least congruence that is an equivalence relation and is such that:
We quotient terms by -equivalence and define capture-avoiding substitution [] as usual.
We write : for is a term and has type . We call typable when : for some type .
We call a term a HOL proposition when it has type . and will range over HOL propositions. We may write as .
Ξ and will range over sets of HOL propositions. We may write Ξ and Ξ as shorthand for Ξ.
A sequent is a pair Ξ .
The derivable sequents are defined in Figure 3.
4. The translation from nominal to functional syntax, and its soundness
4.1. Translation from PNL to higher-order logic
In this subsection we show how to translate a PNL signature and propositions and terms in that signature, to a higher-order logic (HOL) signature and propositions and terms in that signature. We start by translating a PNL signature to a HOL signature . First, we set up some notation:
Let range over finite lists of distinct atoms.
Write when occurs in .
Write when every element in occurs in (disregarding order). Similarly if is a set of atoms write when every element in occurs in .
If is a set of atoms write for the list obtained by removing from just those atoms not in .
Write for the list obtained by applying pointwise to the elements of in order.
Write for the list obtained by appending ; when we write this we include an assumption that .
Write for where ].
From a PNL signature determine a HOL signature by the following specification:
1. For every atoms-sort in assume a HOL base type .
2. For every base sort assume a HOL type .
Translate sorts in to types in as follows:
3. For every term-former f : () assume a HOL constant : .
4. For every proposition-former P : assume a HOL constant .
5. For every atom : assume a HOL variable : .
It is convenient to assume this correspondence is a literal identity; i.e. that is actually a subset of the set of HOL variables of type , and that there are countably infinitely many HOL variables of type that are not atoms.
In particular, this means that every permutation in the sense of Definition 2.7 is also a permutation in the sense of Definition 3.7.
6. For every unknown : and list assume a distinct HOL variable that is not an atom14 of type where is the sort of the th atom in pms() (by convention and as standard, if pms() is empty we take this to be ).
Suppose pms() (Notation 4.1) is the list []. Assume a proposition-former equal of appropriate arity. Then:
Assuming appropriate axioms for equal, we would expect this to be true. Now assume pms() is the list []. Then:
id()[]id() []()()
We would expect this to be false. What has changed with respect to the previous case, is that is fresh for but not for .
The translation of to ( pms()) can be seen as a Skolemisation or raising, where is a finite collection of atoms/variables that are considered ‘relevant’.
See for instance Subsections 4.2 and 4.3 of Chapter 1 of [DGHP99] or Definition 53 of Chapter 3 of [DGHP99], where Skolemisation is discussed in the context of tableau methods. There, just as here, there is a notion of the ‘relevant’ variables. See also Section 5 of [Mil92b], where raising is discussed in the context of unification in the presence of mixed quantifiers.
In fact, Definition 4.3 is a modified version of [DGM10, Definition 8.3] which translated between nominal unification and unification over a generalisation of the same notion of pattern used by Miller in [Mil91, Mil92b]. See also [GM09b], where similar ideas are applied to algebraic reasoning. The idea of these ‘nominal’ translations is that translates to a variable of higher order. In Proposition 4.10 we state a formal sense in which, provided contains all ‘relevant’ atoms, this translation loses no information (the result itself is from [DGM10]). What does ‘relevant’ mean? We examine Figure 5 and see that it means intuitively ‘is permuted by some acting on pms()’. In Subsection 4.3 we apply this to PNL.
Suppose is an atom. Then if fv() then fa().
(for on the right-hand side considered as a permutation of HOL variables).
As a corollary, the translation is well-defined. That is, if and are -equivalent then .
By routine inductions on . The proof that fv() fa() uses the fact that pms() pms(). The corollary follows; for more details see [DGM10, Section 8].
4.2. Capture typing
We mentioned in Remark 4.5 that the translation of Definition 4.3 requires us to declare a finite list of ‘relevant’ atoms. How large must be in order to capture all the important information in some or ? This is calculated by a capture typing, an idea going back to [DGM09, DGM10].
We are only interested in the case , but we need to consider nonempty just as part of the inductive definition. Intuitively, : can be read as ‘ is relevant to in the context of abstractions over the atoms in ’.
As we mentioned in Remark 4.5, the intuitive reading of is ‘the atoms in get permuted in some occurring in ’.
Thus, the interesting case in Figure 5 is the rule for . This ensures that is large enough to record all the important atoms in or abstracted further up in the term—that is, those permitted in —so that we do not lose information when we form ( pms()). This is made formal in Proposition 4.10, which is Theorems 8.12 and 8.14 of [DGM10]:
If and then implies (note that
denotes -equality, because we quotiented terms by this relation), and similarly for and .
If then there exists such that yet , and similarly for .
Definition 4.3 maps PNL terms and predicates to typable HOL terms:
If : then for any , : , and : .
By inductions on and .
The case . By Definition 4.2 : .
The case [] where . By inductive hypothesis : for some type . It follows that [] : .
The case . Suppose . It is routine to check that ( pms()) :
4.3. Soundness of the translation
Recall that HOL terms have a permutation action given by considering as a permutation on HOL variables and using Definition 3.7. Then:
If nontriv() fv() then () (see Notation 4.1).
A fact of -conversion [DGM10, Lemma 9.2].
Suppose and . Suppose sort() and fa() pms(). Then:
[][( pms())].
[][( pms())].
Suppose and and sort() and fa() pms().
For any finite set of predicates there exists some such that for every .
We calculate nontriv() for every occurring in every , in some order, and take this to be . It is not hard to verify that this sufficies.
The interpretation is sound: if Φ Ψ with a derivation and and for every sequent appearing in , then ΦΨ (by Lemma 4.15, some such always exists).
By induction on the derivation of Φ Ψ. It is routine to verify by induction on that is derivable for each appearing in ; the case of (R) uses Proposition 4.14. So in particular ΦΨ.
The interpretation for full PNL (Figure 1, with the stronger axiom rule) would not be sound. That is, there exist Φ and Ψ and such that Φ, Ψ, and Φ Ψ, but ΦΨ.
Consider a name sort and a unary predicate P : . Then P() P() in full PNL, but it is not the case that in HOL.
5. Semantics
For the reader’s convenience we will clarify one aspect of the coming notation now: if the reader sees X this is a set with a permutation action; if the reader sees X this is a set with a renaming action. There is no particular connection between X and X.
A typical renaming is [] (instead of a typical permutation ()). Formal definitions are in Definition 2.7 and 5.1.
The reader may not be surprised by the use of sets with a permutation action— nominal techniques are based on these [GP01]. But why the renaming action? We need renamings to make a function out of an atoms-abstraction, mirroring the clause [] in Definition 4.3.
In PNL models, an abstraction [] is modelled as Gabbay-Pitts atoms-abstraction [], a sets-based construction from [GP01] (Definition 5.29, in this paper). This is constructed like a pair, forming [] from and , but destructed like a partial function the graph of which is evident in Definition 5.29. It is defined on [] for fresh but not for supp() .
When we translate [] to HOL we interpret [] as a function using -abstraction. This suggests of our models that we translate a partial function [] to a total function. But then we have to give meaning to [] applied to where is not fresh. This is where renaming sets are used.
We can then conclude by noting that every model of PNL can be transformed into a model of HOL, and in a compositional manner (Lemma 8.9). Completeness quickly follows.
5.1. Categories of supported permutation and renaming sets
5.1.1. Permutation and renaming sets
Suppose is a map from to . Define dom() and img() by
Echoing Definition 2.7, a renaming is a map from to such that () and nontriv( dom() img() is finite. Write for the set of renamings.
For let an atomic renaming [] map to , to , and other to themselves.
will range over renamings.
We use the following notation (analogously to Notation 2.8):
Write for functional composition, so ()((())).
Write id for the identity renaming, so id( always.
Unlike in Notation 2.8, we have no notation for inverse, because for renamings inverses need not exist.
A permutation set is a pair XX) of an underlying set X and a permutation action (X) X which is a group action; write it infix.
A renaming set is a pair XX) of an underlying set X and a renaming action (X) X which is a monoid action; write it infix.
Suppose X is a permutation set. Say that supports X
Suppose X is a renaming set. Say that supports X when for all , if (() then .
If XX has a supporting permission set (Definition 2.3) then it has a unique least supporting set which is equal to the intersection of all permission sets supporting . We call this the support of when it exists, and write it supp().
Call XX supported when supp() exists.
Call X/X supported when every element XX is supported.
Recall from Definition 2.14 the pointwise actions of and on sets of atoms.
1. If X then supp(supp().
2. If X then supp() supp(). As a corollary, if is injective on supp() then supp(supp().
By routine calculations using the group/monoid action.
The reverse subset inclusion in part 2 of Lemma 5.7 is not true in general:
There exists a renaming set X, an element X, and a renaming such that supp() supp().
Consider () with the non-standard ‘exploding’ renaming action such that:
(Recall from Definition 2.3 that by our permutative convention, and are distinct.) Then supp([](]supp(()).
5.1.2. Equivariant elements and maps
Call an element in XX equivariant when supp(.
is equivariant when for all , or for all , respectively.
Call a function XY equivariant when
Call a function XY equivariant when
and will range over equivariant functions between pairs of permutation and renaming sets respectively.
Equivariance is a characteristic feature of nominal techniques. Equivariance means in words ‘symmetric under permuting atoms’; in this paper we are also interested in ‘symmetric under renaming atoms’. Whichever meaning is appropriate, equivariance is a symmetry property.
For an element X or X equivariance means that has empty support (in fact, supp() is a measure of asymmetry in ). For a function XY equivariance means that commutes with . For a function XY equivariance means that commutes with .
Equivariance and support are abstract mathematical concepts, but they were originally derived from the study of syntax in [GP01]. For syntax, equivariance corresponds to ‘closed’; in usual informal usage the syntax is closed and is symmetric under changing to .15 The reader might therefore find it useful to read ‘equivariant’ as ‘closed’.
However, this is just an analogy and it can be quite treacherous. For instance, is closed as a term but it is not permutatively symmetric with . (If we build our syntax using nominal abstract syntax then [][] is equal to [][], but the reason for this is that [] is equal, via symmetry up to permutation, with [].)
So, while an analogy of ‘equivariance’ with ‘closure’ is historically reasonable and may be helpful, bear in mind that what it really means is ‘symmetric’.
1. Suppose XY is equivariant. Then supp(()) supp() for every X.
2. Suppose XY is equivariant. Then supp(()) supp() for every X.
We consider only the second part. Suppose supports so that for all and , if (() then . The result follows if we note that (() and (().
Write PmsPrm for the category with objects supported permutation sets and arrows equivariant functions between them. Henceforth, X and Y will range over objects in PmsPrm.
Write PmsRen for the category with objects supported renaming sets and arrows equivariant functions between them. Henceforth, X and Y will range over objects in PmsPrm.
Both PmsPrm and PmsRen are categories of sets with a monoid action (in the case of PmsPrm that monoid happens to be a group).
PmsPrm can be thought of as the category of pullback-preserving presheaves on the category of permission sets and finite injections between them (so an object is a permission set, and an arrow from to is a permutation such that ). PmsRen can be thought of as the category of those presheaves on the category of permission sets and finite renamings between them (so an object is a permission set, and an arrow from to is a renaming such that ) that preserve pullbacks of monos.
For details on this see [GH08], and for a more wide-ranging survey of the applications of sets with an action and presheaves see [GMM06]. See also the discussion of presheaves in Subsection 9.2.
5.2. The exponential in PmsRen
PmsPrm and PmsRen are both cartesian closed, but we only discuss exponentials for PmsRen in this paper. The reader can find the constructions for PmsPrm e.g. in [Gab11a, Section 9].
PmsPrm is used to give denotation to PNL only, while PrmRen is used to give a denotation to PNL and also to HOL. For this reason, the exponentials of PmsRen are of specific and immediate importance to us, but not those of PmsPrm.
5.2.1. Functions
Recall the definitions of dom and img from Definition 5.1.
Suppose X Y PmsPrm. Suppose XY ( is not necessarily equivariant). Call supported when there exists a permission set such that for every X and permutation , if nontriv() then
Suppose X Y PmsRen. Suppose XY ( is not necessarily equivariant). Call supported when there exists a permission set such that for every X and renaming , if dom() then
It is a fact that PmsPrm is cartesian closed and functions have the conjugation action
and is supported in the sense of Definition 5.15 if and only if it is supported as an element of XY with the conjungation action. For more on this see [Gab11a, GP01].
Renamings are not invertible, so we must work a little harder to define a renaming action. This is Definition 5.20. However, the end result is similar to the conjugation action, in a sense made formal in Lemma 5.22 which is similar to an immediate corollary of the conjugation action that (()().
If is supported then supp(()) supp() for every X.
By contradiction. Suppose there exists supp(()) ( supp()). Choose fresh (so supp(())supp()). Then ()(((()) since and (()() since supp(). It follows by Lemma 5.7 that ()supp(( supp(()), which is impossible.
Suppose is a permission set and is finite. Call and a freshening pair of renamings for with respect to when:
dom( and dom( img().
()( for all .
dom() (.
In words, maps the atoms in to be outside (and ), and is an ‘inverse’ to that puts them back.
5.2.2. Renaming action
(We continue the notation of Definition 5.15.) If is supported then define by
for some/any freshening pair of renamings and for nontriv() (which is finite), with respect to supp() .
Definition 5.20 is well-defined. That is, it does not matter which freshening pair of renamings we choose.
Consider two freshening pairs of renamings and . These exist because nontriv() is finite and (supp() ) is infinite.
Let map img() to img() and map dom( img() to dom( img() in such a way that
()() for all dom(),
()() for all dom(), and
nontriv( img() img() and nontriv( dom() dom().
We reason as follows:
Suppose X and is a renaming. Suppose XY is supported.
Then (()().
Let and be a freshening pair of renamings of nontriv() with respect to supp().
Let be a renaming with nontriv( img() such that ; this exists since is injective on nontriv() and ‘freshens’ this set to some fresh set of atoms.
We reason as follows:
5.2.3. Definition of the exponential
It suffices to show that if then ([])((). This follows by routine calculations.
The bijection between (XY) Z and X (X Y) is given by currying and uncurrying as usual. Thus : (X Y) Z maps to (). It is not hard to verify that if dom() supp( then
Thus () is supported by supp() and is in Y Z.
We take a moment to build a particular exponential which will be useful later.
Suppose X and . Write X for the function mapping to and to [].
X.
It suffices to show that is supported by supp() (in fact, it is also supported by supp()). Suppose dom()supp( and ( is not necessarily distinct from ). Write - for the renaming such that (-)(() and (-)(. We sketch the relevant reasoning:
5.3. Atoms, products, atoms-abstraction, and functions out of atoms
5.3.1. Atoms
Write for the nominal set and the permutation/renaming set with underlying set 0 1 and the trivial permutation/renaming action such that / always.
We will be lax and write for .
Write for the permutation set and the renaming set with underlying set and the natural permutation/renaming action such that ()/() always.
We will be lax and write for .
5.3.2. Atoms-abstraction in permutation and renaming sets
Suppose X is a supported permutation set.
1. []X is a supported permutation set.
2. []] if and only if , for and X.
3. []] if and only if supp() and (), for and X.
We do not need Definition 5.31 for the completeness proof but we include it for the interested reader to compare and constrast with Definition 5.29.
Definitions 5.29 and 5.31 look similar; both define graphs of partial functions defined on supp() . However, the critical difference is that in renaming sets, this partial function can be extended to a total function in X.
That is, [] []X determines the total function from Definition 5.26, mapping to and any other to []. We return to this in Lemma 7.3 where we show that the natural map from []X to X which we construct in a moment in Definition 5.34, is not surjective. So Definition 5.31 identifies a ‘small’ and ‘well-behaved’ subset of the function space.
A cognate of Lemma 5.30 also holds for []X:
Suppose X is a supported renaming set.
1. []X is a supported renaming set.
2. []] if and only if , for and X.
3. []] if and only if supp() and () (or equivalently []), for and X.
It may be useful to organise Definitions 5.26 and 5.31 and Lemma 5.33 into two functors and a natural transformation:
Write []- for the functor taking X to []X and taking : X Y to [] : XY which maps [] to []().
Write - for the functor taking X to X and taking : X Y to : XY which maps to (()).
Finally, write AbsFun for the natural transformation from []- to - such that AbsFun(X) : []XX maps [] to (Definition 5.26).
The functors []- and - and the natural transformation AbsFun are indeed well-defined.
By routine calculations using the fact that : X Y is equivariant (Definition 5.10). We consider two of the relevant calculations:
If : X Y then [] is well-defined. Suppose []][]X. By Lemma 5.33 supp() and (). By equivariance (())(). By part 2 of Lemma 5.12 supp(()). By Lemma 5.33 [](]().
AbsFun is a natural transformation. We need that (((()). Unpacking Definition 5.26 ()] (here is not necessarily distinct from ). By equivariance of , (()[](). This is exactly equal to () as required.
In part 4 of Lemma 7.3 we prove that AbsFun does not have an inverse. This merely points out the obvious: there are more functions from to X than can be represented in the form [].
5.3.3. Product
If X and X are supported permutation and renaming sets respectively for 1 then define X X and X X by:
supp(.
supp([] supp() .
supp((supp() 1 .
5.4. The free extension of a permutation set to a renaming set
We now show how to construct a renaming set ren(X) out of a nominal set. At the start of Section 5 we noted that an atoms-abstraction [][]X can be viewed as a partial function and that in renaming sets atoms-abstraction also exists but can be completed to a total function (Remark 5.32). We can view our free construction as a canonical way to move from a world in which atoms-abstraction is partial, to a world in which it is total.
If is an equivalence relation, [-] will denote the equivalence class of -in .
We define a functor ren(-) from PmsPrm to PmsRen as follows:
Action of ren(-) on objects. X maps to ren(XX)) where [()])] and is the least equivalence relation such that:
For convenience we will write as shorthand for [()].16
Action of ren(-) on arrows. An arrow : X Y maps to ren() : ren(X) ren(Y) given by:
ren() is well-defined; that is, that if () () then ren()(()) ren()(()).
Induction on the derivation that ()(). We consider the two base cases:
The case (() for every supp(). By part 2 of Lemma 5.12 also ( () for every supp(()).
The case () (). Then also (()) (()) and by equivariance (().
Rules 2 and 1 of Definition 5.39 can be viewed as -conversion and garbage-collection respectively. Thus in ren(X) we may without loss of generality (using rule 2) assume that dom() for any permission set , and we may also assume (using rule 1) that dom() supp().
1. ren() (for considered a set with the trivial permutation action) is isomorphic to (for considered a set with a trivial renaming action).
2. ren() (for with its natural permutation action) is isomorphic to (for with its natural renaming action).
We consider only the second part. This follows if we note that according to the rules for in Definition 5.39,
() ((() )) (id())
Where we are dealing with more than zero or one atoms at a time, isomorphisms like those in Lemma 5.42 may fail:
ren() is not isomorphic to ren()ren() (which is isomorphic to ).
Consider the element []().
6. Interpretation of permissive-nominal logic
6.1. Interpretation of signatures
Suppose () is a sort-signature (Definition 2.1).
A PNL interpretation for () consists of an assignment of a nonempty supported permutation set to each .
We extend an interpretation to sorts by:
Suppose ar) is a signature (Definition 2.5).
A (non-equivariant) PNL interpretation for consists of the following data:
An interpretation for the sort-signature () (Definition 6.1).
For every f with ar(f) an equivariant function f from to (Definition 5.10).
For every P with ar(P a supported function P from to 0 1.
If every P is equivariant, then call a fully equivariant interpretation.17
6.2. Interpretation of terms
Suppose is an interpretation for . A valuation to is a map on unknowns such that for each unknown ,
() sort(), and
supp(()) pms().
will range over valuations.
Having interpreted sorts in Definition 6.1 as permissive-nominal sets , we now interpret nominal terms : as elements of those sets :
If : then .
By a routine induction on .
.
supp() fa().
6.3. Interpretation of propositions
Suppose is a valuation to an interpretation . Suppose is an unknown and sort() is such that supp() pms(). Define [] by
It is easy to verify that [] is also a valuation to .
We may identify with a set of valuations . We discuss soundness and completeness in Appendix A.
[].
If (() for all fU () then , and similarly for .
By a routine induction on and .
7. Interpretation of HOL
For this section fix some PNL interpretation of a PNL signature . Recall from Definition 4.2 the definition of the corresponding HOL signature .
We have our interpretation of PNL and we have from Definition 4.3 a translation of PNL syntax to HOL syntax. We also have a functor from nominal sets to renaming sets (Definition 5.39). It remains to interpret HOL in renaming sets consistent with these interpretations and translations. This is Definitions 7.1 and 7.6, and the key technical result Lemma 8.9. Completeness follows quickly as a corollary (Theorem 8.11).
Note that in the interpretation (Definition 7.1) the type is not necessarily interpreted as the set of all functions; it may be interpreted as a small subset of this function space. This is an old idea: since Henkin, models of HOL have been constructed to cut down on the full function-space (e.g. to create a complete semantics [And86, Section 55]; see also [BBK04] for a survey of non-standard semantics for HOL).
What we need to prove completeness of the syntactic translation - is the existence of some interpretation of HOL with certain properties. This should not be mistaken as a commitment of nominal techniques to using this model of HOL always (unless we want to).
7.1. Interpretation of types
Recall the definition of a valuation (Definition 6.3) to an interpretation for the PNL signature . Recall the definition of [] (Definition 6.8), and the interpretations of terms (Definition 6.4) and propositions (Definition 6.9).
We give similar definitions for HOL and renaming sets, culminating with Theorem 7.15 (soundness).
We provide an interpretation of by:
Recall X Y from Definition 5.23 and X Y from Definition 5.36.
Not all function types are interpreted equally by Definition 7.1.
If a type is the image of a PNL sort then we handle it using the first clause by wrap-ping it up in ren(-). Otherwise the interpretation is as standard: pairs to product; function types to the (supported) function set. This case-split makes Lemma 8.9 work, which is central to Corollary 8.10 and to Completeness (Theorem 8.11).
Why Lemma 8.9 could not work if we did not do this, is indicated in Lemma 7.3. Briefly, - contains ‘exotic elements’ making it bigger than []-, which readers familiar with higher-order abstract syntax would expect [DH94, exotic terms].
Perhaps less familiar from Lemma 8.9 is that the free construction ren(-) does not commute with atoms-abstraction or even with cartesian product (which tells us that the associated functor does not have a left adjoint). So even e.g. in PmsRen has an ‘exotic element’.
The natural maps below in Lemma 7.3 are functors (some are defined in Definition 5.34). Technically, Lemma 7.3 implies that various natural transformations between these functors do not have inverses. More loosely, this is a way of putting some formal measure to the intuition that the translation from (restricted) PNL to HOL cannot be surjective:
1. The natural map from ren() to mapping to (), is a bijection (cf. Lemma 5.42).
2. The natural map from ren(X Y) to ren(X) ren(Y) mapping () to () is neither surjective nor injective.
3. The natural map from ren([]X) to []ren(X) mapping [] where nontriv() to [], is not surjective.
4. The natural map from []Y to Y mapping [] to (see Definitions 5.26 and 5.34), is not surjective.
1. By rule 2 of Definition 5.39.
2. Take X Y. The natural map from ren(X Y) to ren(X) ren(Y) takes id () to (id id ). By equivariance it must map []() to (id id ). But then it is not injective, since []() id () in ren(X Y). Now take X Y. It is not hard to see that ([]() []()) is not in the image of the natural map, so the map is also not surjective.
3. Take X and consider [][]() []ren(X).
4. Take Y for considered a renaming set as in Definition 5.28. Consider () , mapping to , to , and all other to .
7.2. Interpretation of terms
A (HOL) valuation to is a map on variables : such that
() for every variable .
() id is finite.18
will range over valuations.
It is easy to verify that [] is also a valuation to .
Extend to terms as follows:
ren(f) and ren(P) (Definition 5.39).
(max1.
)(min.
([] where ( provided that : for some PNL sort and for some name sort and (-converting if necessary) supp(()) and ( id .
(([]) provided that : where is not equal to [] for any or .
(] ) provided that : [] for some PNL name sort and sort , where ( id (by construction some such always exists) and ([], and (renaming if necessary) nontriv() .
(()() provided that : for not equal to for any PNL sort (it is a fact that this case and the previous case exhaust all the possibilities for ).
()()() provided that : for 1 , where , and we choose represenatives such that dom() dom( for all 1 .
()(()()) provided that there exists some and such that and is not equal to for any PNL sort .
Definition 7.6 propagates to terms the case-split noted in Remark 7.2. We treat terms differently depending on whether they populate the translation of a PNL sort, or not. We must do this because of how we interpreted types in Definition 7.1.
Just to locate where we are, here is an schematic of the overall structure of the proof of completeness:
We translated PNL to HOL using - in Definition 4.3. Ideally, to prove completeness we would now give HOL a denotation directly in PmsRen.
Unfortunately this is not possible (the dashed arrow) because [] translates to and has nominal denotation as an atoms-abstraction []. Atoms-abstraction (Definition 5.29) is the graph of a partial function, whereas ‘wants’ to take denotation as a total function.
So instead we use a commuting square as illustrated; in PmsRen atoms-abstraction can be viewed as a total function, as noted in Remark 5.32. Definition 7.6 uses this, and fills in the right-hand arrow. We also need to convert the PNL valuation to a HOL valuation (); this comes later in Definition 8.7.
Note that by forming this diagram we give a new semantics to PNL in PmsRen, and thus in particular give a semantics to nominal atoms-abstraction in which it becomes interpreted as a total function.
The top arrow is Definition 4.3; the left-hand arrow is Definition 6.4; and the bottom arrow is Definition 5.39. Lemma 8.8 proves commutativity of the square.
Suppose and . Suppose supp(()) for every fv() (including ). Suppose ( id .
Then ([id ](()).
Lemma 7.8 may fail if supp(()). For instance, if ( where and type( and is not itself an atom, then ([id id yet []((](id id .
We need to check that the denotation of terms populates the denotation of their types, and that -equivalent terms receive equal denotations.
If : then () .
()(([()]).
There are two cases, depending on whether : [] for some PNL sort, or not.
The case : . By Definition 7.6 ( id and ([], for some , , and . -converting if necessary assume is equal to which we choose fresh (so nontriv() and supp(()) for every fv() and ( id ). Then also by definition ()(] ). Thus it suffices to check that ([] )([]). This follows using Lemma 7.8.
The case : where is not equal to for any PNL sort . This is as standard.
7.3. Soundness
If (() for all fv() then (().
By a routine induction on terms.
([([]().
By a routine induction on . We mention two cases (bearing in mind that in HOL, a variable : may be an atom in if ):
The case equals equals for some atom . By Definition 7.6, ([(().
The case equals . We assume fv(), so ()[([]), and use the inductive hypothesis.
Call the proposition valid in when ( for all .
Call the sequent valid in when () () is valid.
If this is true for all then write .
If Ξ is derivable then Ξ .
Fix some interpretation . We work by induction on derivations (Figure 2). We sketch the two non-trivial cases:
The case of (hL). We check that : type() implies () [](). We reason as follows:
In the second use of Definition 7.6 above, note that [] is never of the form [] for any .
The case of (hR). We use Lemma 7.12 and routine calculations on truth-values.
8. Completeness of the translation of PNL to HOL
We are now ready to prove completeness (Theorem 8.11) of the translation from Definition 4.3. The proof is subtle; notably Lemma 8.4 and the case of in Lemma 8.9 are non-trivial. Some mathematical action also takes place in Lemma 8.8 and the case of in Lemma 8.9.
8.1. Renamings and HOL propositions
We need a few technical observations about how renamings interact with the denotations of HOL propositions:
Suppose : X. Then for every , ( implies (.
From equivariance and the fact that in .
Suppose : X. Then ren()(().
Write for the valuation mapping to ().
Suppose is a HOL proposition. Then
(() for every and , and
as a corollary, if : and then ([([]).
Lemma 8.4 expresses that does not examine atoms for inequality across its arguments (if it did then Lemma 8.4 could not hold, because can identify atoms— make them become equal—in the denotations of variables in ). The corollary is even more powerful: we can even apply renamings to the denotations of individual free variables, and still not affect validity.
We use this in the case of in Lemma 8.9 to ‘jettison’ unwanted in the denotation of the quantified variable.
8.2. The completeness proof
Suppose ] is a finite list of distinct atoms in , ..., respectively. Suppose : is a PNL term. Then:
Write [] for the PNL term [] [].
Write [] for the PNL sort [] [].
Compare Lemma 8.8 with Lemma 4.12:
Suppose and nontriv() supp() . Then
Lemma 8.9 proves that the schematic diagram of Remark 7.7 does indeed commute:
Suppose : and is a proposition. Then:
If then (( id ().
If then ((().
By inductions on and .
The case . We reason as follows:
Note of the penultimate step that by assumption , so by Definition 4.7
The case []. By Definition 4.3
By inductive hypothesis (( id () and so by Definition 7.6 (eliding routine freshness reasoning for )
Finally by Definition 6.4
and by transitivity of equality we are done.
The case P(). We reason as follows:
The case . Write sort(). From Definition 7.6
By construction in Definition 7.1 every [] has the form for [ pms()]. By Lemma 8.4 we have
Using Lemma 8.4 again we assume without loss of generality that supp([ pms()]) pms() pms(), and so:
Now we unfold definitions and use the inductive hypothesis which tells us that ()[id [ pms()]([]), and we obtain:
Suppose Φ and Ψ. If Φ Ψ then ΦΨ.
9. Conclusions
We have translated a logic with its own proof-theory, syntax, and sound and complete semantics. Any formal theory specified in the PNL fragment of this paper can be systematically, soundly, and completely translated to HOL.
For the reader interested in nominal techniques, the main contribution of this paper is that in proving completeness of the translation, we have given another semantics of permissive nominal logic, besides the ‘obvious’ one in nominal sets. In this new semantics, a term of the form [] is interpreted as a function, like would be in higher-order logic. This shows at the semantic level an implicit similarity between PNL and HOL (we discuss presheaves in the next Subsection).
For the reader interested in higher-order logic, this paper is of interest because its image is readily identified with the higher-order patterns developed by Miller [Mil91] (so that, intuitively, restricted PNL could be thought of as a compact first-order logic and nominal semantics for higher-order patterns).
In this semantics the sort [] is not interpreted as the set of all functions from atoms to the interpretation of , but as a small subset of this function space. This is an old idea: since Henkin, models of HOL have been constructed to cut down on the full function-space (e.g. to create a complete semantics [And86, Section 55]). Moreover in weak HOAS to avoid so-called exotic terms, function existence axioms must be weakened in HOL: for instance, the description axiom that entails the existence of a function for all functional relations has to be dropped (an alternative is to introduce an explicit modal-ity [DPS01]). We now have a new view of these ‘smaller’ function-spaces as being the image of nominal atoms-abstractions via the semantic operations considered in this paper.
9.1. The big picture
It is quite interesting to understand this paper via a contrast between what nominal foundations and ‘ordinary’ foundations provide.
The denotation of an open term in PNL is an open element of a nominal set (i.e. an element with atoms in its support): so for instance an atom maps just to itself in the denotation, rather than being assigned some other element by a valuation. PNL has binding term-formers because its open denotation in nominal sets provides constructions like atoms, permutations, and atoms-abstraction (Definition 5.29); see Section 6.
In contrast, in HOL there is no concept of open element—there are open terms, but their denotation is closed by a valuation. If we want the effect of a free variable then we Skolemise/raise. Indeed, any mathematics using technology based on the HOL/ZF (Zermelo-Fraenkel sets) foundations of mathematics must handle names either as something like functional arguments or something like numbers; simply because numbers and functions are what HOL/ZF foundations provide.
The translation from PNL to HOL in Section 4 works by raising.19 However, we can only raise variables, in order. So the translation has to be on a per-derivation basis, including the (finitely many) atoms of interest in that (finite) derivation. Furthermore, we lose the equivariance (name symmetry) of full PNL. So we can only naturally translate individual derivations in restricted PNL.
This matters because in losing symmetry we lose what makes nominal techniques so distinctive. So although we show how to translate a complete ‘nominal’ proof to a complete ‘HOL’ proof, we also see how how the way in which nominal and HOL proofs are manipulated and combined, are different.
The translation is not entirely trivial to define and prove sound, but the technically hardest part in this paper is clearly the proof of its completeness. For this we build a hybrid denotation for HOL in nominal renaming sets which is sound but in which certain function spaces are restricted to be ‘not too large’. That motivates the bulk of the technical mathematics of this paper.
9.2. Permissive nominal logic in perspective
Permissive-nominal logic is the endpoint—so far—of an evolution as follows:
Fraenkel-Mostowski set theory and a first-order axiomatisation by Pitts introduced and described the underlying nominal sets models in first-order logic [GP01, Pit03].
Nominal terms introduced a dedicated syntax with two-levels of variable and freshness side-conditions [UPG04].
Nominal algebra and Prolog inserted nominal terms syntax into formal reasoning systems [GM09a, CU04].
Permissive-nominal terms introduced permission sets [DGM10].
PNL introduced a proof-theory and universal quantifier for nominal terms unknowns [DG10, DG12].
Meanwhile in the semantics
Nominal renaming sets extended nominal sets from a permutation action to a renaming action [GH08].
A permissive version of nominal algebra (an equality fragment of PNL) was given semantics in PmsPrm and theories were translated from HOL [GM09b], but this was done purely syntactically without using nominal renaming sets and without considering universal quantification.
The categories PmsPrm and PmsRen from Definition 5.13 are identical to the categories of nominal sets and nominal renaming sets from [GP01] and [GH08], except that here we insist on supporting permission sets instead of supporting finite sets.
The reader familiar with presheaf techniques will see in PmsRen the category Sets (presheaves over the category of finite sets and functions between them). PmsRen corresponds to presheaves (not quite over , as discussed in the previous paragraph) that preserve pullbacks of pairs of monos [GH08] and because of this it admits an arguably preferable sets-based presentation. (In the same sense, PmsPrm corresponds to Sets.)
If for the sake of argument we set aside the issues of finiteness and preserving pullbacks of monos, then this paper can be summed up as follows: PNL, and thus nominal terms, can be given a semantics in something that looks like Sets. This semantics is functional in that atoms-abstractions in Sets can be naturally identified with total functions, though not all of them, which is good. HOL can also be given a semantics in something that looks like Sets, and in such a way that it overlaps with the semantics of PNL, as described in Definition 7.6 and 8.9. We describe and exploit that overlap, in this paper.
PmsRen from Definition 5.13 is related to the category of (finitely-supported) nominal renaming sets from [GH08]. Here, the difference that X need not have finite support is significant because it is impossible with a finite renaming to rename supp() to be entirely disjoint for some other permission set . The definitions and proofs in Subsection 5.2 are delicately revised with respect to those in [GH08, Section 3]. Thus this paper contributes to the use of non-finitely-supported objects in nominal techniques, building on [GH08] and also on Cheney’s and the second author’s considerations of infinitely supported permutation sets [Che06, Gab07b].
A similar construction as in Subsection 5.4 has been considered, also in the context of names, though tersely, in Fiore and Turi’s paper on the semantics of name and value passing [FT01]. The reader can compare for example the final two paragraphs of Subsection 1.3 in [FT01] with Definition 5.39 from Subsection 5.4. Fiore and Turi want substitutions to model bisimulation in the presence of name-generation and message-passing; we want renamings to model function application on names. The underlying technical demands overlap and are similar.
Fiore and Turi’s framework includes the possibility of arbitrary substitutions for atoms (not just what we call renamings: substitution of atoms for atoms). This was ap-parent in [FT01] and is developed greatly in subsequent work by Fiore and Hur [FH10]. We hypothesise that from the point of view of PNL, their logic and semantics correspond to PNL enriched with substitution actions like those in [DG10, GM06a], but this remains to be checked.20
Levy and Villaret translated nominal unification problems to higher-order unification problems [LV08]. A similar but more detailed analysis, translating solutions and introducing the same notion of capturable atoms as used in the capture typings in this paper, appears in the paper which introduced permissive nominal terms [DGM10]. See also a journal version of Levy and Villaret’s paper [LV11], which expanded on their previous work by eliminating freshness contexts (in a similar spirit to PNL, we feel, though the details are different). This paper can be viewed as a very considerable extension, re-finement, and generalisation of these works: this paper is their grandchild, so to speak, via two other papers [DG10, GM09b].
The extension of nominal sets to nominal renaming sets is free. This is touched on in Lemma 7.3 when we note that []() and id () are distinct elements in ren( ) in PmsRen; this happens because the free construction ‘suspends the non-injectivity’ of [] on (). This is as things should be, in order to obtain completeness. The second author has considered a more radical non-free construction [Gab09], which has the effect of extending atoms-abstraction to a total function and in which [] really does identify with in in a suitable sense.
As we have emphasised, we translate a fragment of PNL to HOL. In [DG10] we considered full PNL with equivariance, which corresponds to strengthening the axiom rule (Ax) in Figure 2 from to as illustrated in Figure 1. This internalises the equivariance assumed in Definition 6.2 and allows us to derive e.g.
In the journal version [DG12] of [DG10] we strengthen PNL further by allowing a shift-permutation. This is a non-finitely-supported bijection on similar to a de Bruijn shift function [ACCL91, Subsection 2.2]. Its effect in this paper is to make all permission sets isomorphic up to bijection (e.g. for some , where ) and this deals with a subtle restriction in the power of universal quantification discussed for instance in [DG10, Example 2.29]. Briefly, shift lets us derive P() P() where pms( and pms( where , which was not possible in the PNL from [DG10].
Neither equivariance nor shift are translated to HOL in this paper; more on this in the next subsection.
9.3. Future work
We have translated Permissive-Nominal Logic to Higher-Order Logic. The translation is not surjective: all variables are at most second-order; all constants are at most third-order; higher types are not used; and in fact all terms in the image of the translation are -patterns [Mil91]. In addition, the translation is not total: we have dropped equivariance.
This is with good reason. We have not been able to simulate equivariance in HOL— not without ‘cheating’ by simply adding it (and causing a blowup in the size of propositions). We have not proved this impossible, but we hypothesise that it cannot be done. We further hypothesise (based on preliminary calculations not included in this paper) that HOL augmented with the -quantifier from [MT03] would allow us to express equivariance.
It is not currently clear how to extend HOL with a shift-like permutation as discussed in [DG12, Gab12b]. This seems reasonable since shift would correspond to an infinite renaming.
Some natural theories in PNL might correspond to other fragments of HOL. Notably, it is not known what relation exists between HOL and PNL with the theory of atoms-substitution from [GM08a, DG12].
References
[ACCL91] Martín Abadi, Luca Cardelli, Pierre-Louis Curien, and Jean-Jacques Lévy. Explicit substitutions. Journal of Functional Programming, 1(4):375–416, 1991.
[And86] Peter B. Andrews. An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof. Academic Press, 1986.
[BBK04] Christoph Benzmüller, Chad E. Brown, and Michael Kohlhase. Higher-order semantics and ex-tensionality. Journal of Symbolic Logic, 69:1027–1088, 2004.
[BBKL12] Mikolaj Bojanczyk, Laurent Braud, Bartek Klin, and Slawomir Lasota. Towards nominal computation. In Proceedings of the 39th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2012), pages 401–412. ACM Press, January 2012.
[Che06] James Cheney. Completeness and Herbrand theorems for nominal logic. Journal of Symbolic Logic, 71:299–320, 2006.
[Chu40] Alonzo Church. A formulation of the simple theory of types. Journal of Symbolic Logic, pages 56–68, 1940.
[CU04] James Cheney and Christian Urban. Alpha-prolog: A logic programming language with names, binding and alpha-equivalence. In Bart Demoen and Vladimir Lifschitz, editors, Proceedings of the 20th International Conference on Logic Programming (ICLP 2004), number 3132 in Lecture Notes in Computer Science, pages 269–283. Springer, 2004.
[dB72] Nicolaas G. de Bruijn. Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indagationes Mathematicae, 5(34):381–392, 1972.
[DG10] Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic. In Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2010), pages 165–176. ACM Press, 2010.
[DG12] Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic (journal version). Transactions on Computational Logic, 2012. In press.
[DGHP99] Marcello D’Agostino, Dov M. Gabbay, Reiner Hähnle, and Joachim Posegga, editors. Handbook of Tableau Methods. Kluwer, 1999.
[DGM09] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification. In Proceedings of the 24th Italian Conference on Computational Logic (CILC’09), 2009.
[DGM10] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification: an infinite, co-infinite approach to nominal techniques (journal version). Logic Journal of the IGPL, 18(6):769–822, 2010.
[DH94] Joëlle Despeyroux and André Hirschowitz. Higher-order abstract syntax with induction in COQ. In LPAR’94, volume 822 of Lecture Notes in Computer Science, pages 159–173. Springer, 1994.
[DHK98] Gilles Dowek, Thérèse Hardin, and Claude Kirchner. Theorem proving modulo. Rapport de Recherche 3400, Institut National de Recherche en Informatique et en Automatique, April 1998.
[DPS01] Joëlle Despeyroux, Frank Pfenning, and Carsten Schürmann. Primitive recursion for higher-order abstract syntax. Theoretical Computer Science, 266(1-2):1–57, September 2001.
[Far08] William M. Farmer. The seven virtues of simple type theory. Journal of Applied Logic, 3(6):267–286, 2008.
[FH10] Marcelo Fiore and Chung-Kil Hur. Second-order equational logic. In Proceedings of the 19th EACSL Annual Conference on Computer Science Logic (CSL 2010), Lecture Notes in Computer Science. Springer, 2010.
[FT01] Marcelo Fiore and Daniele Turi. Semantics of name and value passing. In Proceedings of the 16th IEEE Symposium on Logic in Computer Science (LICS 2001), pages 93–104. IEEE Computer Society Press, 2001.
[Gab07a] Murdoch J. Gabbay. Fresh Logic. Journal of Applied Logic, 5(2):356–387, June 2007.
[Gab07b] Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205(7):982– 1011, July 2007.
[Gab09] Murdoch J. Gabbay. A study of substitution, using nominal techniques and Fraenkel-Mostowski sets. Theoretical Computer Science, 410(12-13):1159–1189, March 2009.
[Gab11a] Murdoch J. Gabbay. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic, 17(2):161–229, 2011.
[Gab11b] Murdoch J. Gabbay. Stone duality for First-Order Logic: a nominal approach. In Howard Barringer Festschrift. December 2011.
[Gab11c] Murdoch J. Gabbay. Two-level nominal sets and semantic nominal terms: an extension of nominal
set theory for handling meta-variables. Mathematical Structures in Computer Science, 21:997–1033, 2011.
[Gab12a] Murdoch J. Gabbay. Meta-variables as infinite lists in nominal terms unification and rewriting. Logic Journal of the IGPL, 2012.
[Gab12b] Murdoch J. Gabbay. Nominal terms and nominal logics: from foundations to meta-mathematics. In Handbook of Philosophical Logic, volume 17. Kluwer, 2012.
[Gen35] Gerhard Gentzen. Untersuchungen über das logische Schließen [Investigations into logical deduction]. Mathematische Zeitschrift 39, pages 176–210,405–431, 1935. Translated in [Sza69], pages 68–131.
[GH08] Murdoch J. Gabbay and Martin Hofmann. Nominal renaming sets. In Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2008), pages 158–173. Springer, November 2008.
[GL08] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus. Electronic Notes in Theoretical Computer Science, 196:19–35, January 2008.
[GL09] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus (extended version). Information and computation, 207:1369–1400, December 2009.
[GM06a] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding Substitution as a Nominal Algebra. In ICTAC 2006: Theoretical Aspects of Computing, volume 4281 of Lecture Notes in Computer Science, pages 198–212, November 2006.
[GM06b] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order logic. In Proceedings of the 8th ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming (PPDP 2006), pages 189–200. ACM, July 2006.
[GM07] Murdoch J. Gabbay and Aad Mathijssen. A Formal Calculus for Informal Equality with Binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of Lecture Notes in Computer Science, pages 162–176. Springer, July 2007.
[GM08a] Murdoch J. Gabbay and Aad Mathijssen. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing, 20(4-5):451–479, June 2008.
[GM08b] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order Logic. Journal of Logic and Computation, 18(4):521–562, August 2008.
[GM09a] Murdoch J. Gabbay and Aad Mathijssen. Nominal universal algebra: equational logic with names and binding. Journal of Logic and Computation, 19(6):1455–1508, December 2009.
[GM09b] Murdoch J. Gabbay and Dominic P. Mulligan. Universal algebra over lambda-terms and nominal terms: the connection in logic between nominal techniques and higher-order variables. In Proceedings of the 4th International Workshop on Logical Frameworks and Meta-Languages (LFMTP 2009), pages 64–73. ACM, August 2009.
[GM10] Murdoch J. Gabbay and Aad Mathijssen. A nominal axiomatisation of the lambda-calculus. Journal of Logic and Computation, 20(2):501–531, April 2010.
[GMM06] Fabio Gadducci, Marino Miculan, and Ugo Montanari. About permutation algebras, (pre)sheaves and named sets. Higher Order Symbolic Computation, 19(2-3):283–304, September 2006.
[GP01] Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing, 13(3–5):341–363, July 2001.
[HS08] J. Roger Hindley and Jonathan P. Seldin. Lambda-Calculus and Combinators, An Introduction. Cam-bridge University Press, 2nd edition, 2008.
[LV08] Jordi Levy and Mateu Villaret. Nominal unification from a higher-order perspective. In Rewriting Techniques and Applications, Proceedings of RTA 2008, volume 5117 of Lecture Notes in Computer Science. Springer, 2008.
[LV11] Jordi Levy and Mateu Villaret. Nominal unification from a higher-order perspective. Transactions on Computational logic (TOCL), 13, 2011.
[Mil91] Dale Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Journal of Logic and Computation, 1(4):497 – 536, 1991.
[Mil92a] Dale Miller. Logic, higher order. In Stuart Shapiro, editor, Encyclopedia of artificial intelligence (second edition). Wiley, 1992. Available online from the author’s webpage.
[Mil92b] Dale Miller. Unification under a mixed prefix. Journal of Symbolic Computation, 14(4):321–358, 1992.
[MN98] Richard Mayr and Tobias Nipkow. Higher-order rewrite systems and their confluence. Theoretical Computer Science, 192:3–29, 1998.
[MT03] Dale Miller and Alwen Tiu. A proof theory for generic judgments (extended abstract). In Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), pages 118–127. IEEE Computer Society Press, 2003.
[PE88] Frank Pfenning and Conal Elliott. Higher-order abstract syntax. In PLDI (Programming Language
Design and Implementation), pages 199–208. ACM Press, 1988.
[Pit03] Andrew M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 186(2):165–193, 2003.
[Pra65] Dag Prawitz. Natural deduction: a prooof-theoretical study. Almquist and Wiksell, 1965. Reprinted by Dover, 2006.
[Smu68] Raymond Smullyan. First-order logic. Springer, 1968. Reprinted by Dover, 1995.
[Sza69] M. E. Szabo, editor. Collected Papers of Gerhard Gentzen. North Holland, 1969.
[UPG04] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, September 2004.
Acknowledgements: Thanks to the careful attention of two anonymous referees. We acknowl-edge the support of DIGITEO in Paris, of grant RYC-2006-002131 at the Polytechnic University of Madrid, and of the Leverhulme Trust in the UK.
A. Soundness and completeness of restricted PNL with respect to non-equivariant
models
A.1. Validity and soundness
Suppose is a non-equivariant interpretation of a signature (Definition 6.2). Call the proposition valid in when for all .
Call the sequent valid in when () () is valid.
If this is true for all non-equivariant then write . If this is true for all equivariant then write .
1. If Φ Ψ is derivable then Φ Ψ.
2. If Φ Ψ is derivable then Φ Ψ.
Fix some interpretation . We work by induction on derivations. The case of (L) uses Lemma 6.10. The case of (R) uses Lemma 6.11. Other rules are routine by unpacking definitions.
If the interpretation is fully equivariant then it can further be proved that always, so that (Ax) is valid. If is not fully equivariant, then just (Ax) is valid.
(Cut) is admissible in both full and restricted PNL.
The proof for full PNL is in [DG12, Section 7] or [Gab12b, Subsection 11.2]; the derivation rules are almost exactly those of first-order logic, and so is the proof of cut-elimination. The argument for restricted PNL is identical; we note that none of the cut-eliminating transformations add to axiom rules unless they are already there, so the same reductions on derivations work also for the restricted system.
A.2. Completeness
In [DG12, Gab12b] we prove completeness of full PNL with respect to equivariant models, by means of a Herbrand construction (a model built out of syntax). We can leverage this result to concisely prove completeness of restricted PNL with respect to non-equivariant models, without having to repeat the model constructions.
For this subsection, fix the following data:
A signature ar).
A formula such that .
Define a new signature as follows:
and (so we have the same atom sorts and the same base sorts, plus one extra base sort ).
and (so we have the same term- and proposition-formers).
If f then ar (f ar(f) (the term-formers are identical).
If P and ar(P then ar (P) (so proposition-formers take one extra argument of sort ).
a permission set where sort( (so we add unknowns of sort ).
Now fix some particular unknown with sort( and such that fa() pms().
Define a translation - from PNL propositions in the signature to PNL propositions in the signature by mapping P() to P() and extending this in the natural way to all predicates.
Our proof depends on the following technical lemma about restricted PNL:
If Φ Ψ is derivable in full PNL then there exists a derivation such that every sequent in satisfies fa() fa() fa(Φ) fa(Ψ).
By cut-elimination of restricted PNL (Theorem A.3) if a derivation of Φ Ψ exists then a cut-free derivation exists. We now examine the derivation rules in Figure 2 and the definition of free atoms in Definition 2.15 and note that the rules (L), (R), (L), and (R) do not increase the free atoms moving from below the line to above the line.21
if and only if (() for every fa(), and similarly for .
See [Gab12b, Lemma 3.2.9] or [DGM10, Lemma 4.15].
If Φ Ψ in PNL and fa(Φ) fa(Ψ) pms() then Φ Ψ.
Using cut-elimination of full PNL (Theorem A.3) assume a cut-free PNL derivation of Φ Ψ. Because of Lemma A.6, the condition on free atoms holds of every sequent in . Because of the form of the derivation rules in Figure 1, cannot instanti-ate .
So we can go through the entire syntax of and delete to obtain a structure that is a candidate for being a derivation in restricted PNL of Φ Ψ.
The only non-trivial thing to check is that valid instances of (Ax) are transformed to valid instances of (Ax). Suppose we deduce Φ Ψ using (Ax). By assumption for some . It follows that id (recall from Subsection 2.3 that we quotient by -equivalence) and so by Lemma A.7 that ( for all pms(). By assumption fa(Φ) fa(Ψ) fa() fa() pms() and so by Lemma A.7 , and we are done.
If Φ Ψ then Φ Ψ.
We prove the contrapositive, that if Φ Ψ then Φ Ψ. Suppose Φ Ψ. Using the constructions above we augment to a signature (Definition A.4) with some with fa(Φ) fa(Ψ) pms(). Thus by Proposition A.8 Φ Ψ.
By completeness of full PNL with respect to equivariant models ([DG12, Theorem 3.45], [Gab12b, Theorem 9.4.15]) we have that Φ Ψ. So there exists an equivariant model and valuation to such that Φ and Ψ . It is now routine to convert into a non-equivariant model of the original signature by taking P( P(()).
Notes
1A word of clarification here: we take to be a type of truth-values, to be a type of terms, and to be a type of predicates. -the-quantifier generates truth-values, whence the type headed by , namely : (). -the-syntax-building-constant in HOAS generats terms, whence the types headed by , namely : () or : (). Do not confuse a HOL constant for a HOAS-style binder (a way to give meaning to building syntax with binding) with a HOL constant for the corresponding quantifier (a way to give meaning to what that that syntax is intended to denote; namely, actual quantification). ↩
2A deep embedding e.g. of HOL in PNL is an answer to a different question; for more on this direction, see [GM09b]. ↩
3These axioms first appeared in [GM06a, GM06b] where a slightly different version of the final axiom was used. They are equivalent; see part 5 of Example 2.20 in this paper. ↩
4This is because we used all finite permutations of atoms as our symmetry group. Generalisations of this as suggested e.g. in [BBKL12, Subsection 3.1] are possible. See also Remark 2.1.8 of [Gab12b]. ↩
5Note that PNL is not only about nominal abstract syntax as considered in e.g. [GP01, Gab11a]. Nominal abstract syntax is a denotation for syntax with binding. PNL and its models are a (more general) syntax and semantics for denotations with binding in general, which are not all necessarily datatypes of abstract syntax. ↩
6There has been more than enough of that already, and anyway, because truth is free, proving theorems is never a zero sum game. ↩
7For comparison, nominal terms have only a finite supply of fresh atoms. The effect of this is that the nominal terms of [UPG04] cannot be quotiented by -equivalence as primitive, and the freshness context may need to be extended dynamically with fresh names. This introduces an ‘impure’ flavour of state and sequentiality into the theory of nominal terms which is absent from the permissive-nominal version. In short, making permission sets infinite and coinfinite makes the whole theory noticably more ‘pure’. ↩
8We do not assume a congruence is an equivalence relation. We prefer to keep the notion of ‘being pre-served by all term-formers’ orthogonal to the notion of ‘being transitive, reflexive, and symmetric’. For instance, we want a rewrite relation to have the first property but not the second. In [DHK98] the second author considers combining sequents with rewriting. This is deduction modulo; a nominal version of deduction modulo is future work and is one of the background motivations for the creation of PNL. ↩
9In fact, this was the characterisation used to design the ‘exotic’ multi-level -equivalences of permissive-nominal logic or two-level nominal sets [Gab11c]. ↩
10In the LamCC, atoms are level 1 variables, unknowns are level 2 variables and behave much like ‘holes’ in a program context, and there are level 3 variables, and so on. Many interesting program constructs can be expressed in this language. ↩
11The second author is most interested in PNL as a first-order basic for specifying logic and computation in theorem-proving and also in undergraduate teaching. Fancier logics and semantics than PNL can certainly be imagined, and perhaps created, but this does not undermine the interest of a ‘simple’ logic, like PNL. ↩
12This has actually been used in real proofs; starting with [Gab07a] we used what amounts to (Ax) to rename variable symbols in inductive proofs. See [Gab11a, Subsection 4.2] for this equivariance principle discussed as a practical tool to obtain one-line proofs at the rigorous but informal meta-level of papers. ↩
13This means that if the reader sees ‘’ this could refer either to a HOL variable or—recalling Definition 2.5—to a PNL unknown. We will make sure that it is always clear from context which is meant. ↩
14So is one of the countably infinitely many HOL variables that are not atoms. ↩
15For the rest of this remark is a term-former. So refers to the term, not the function. ↩
is not ‘ acting on ’ and cannot be, since X only has a permutation action. However this notation gives us cleaner-looking maths and the nice equality (id (in long form: [(id)] [()]). The notation follows the nominal terms tradition of writing both for ‘ acting on the moderated unknown id’, and for ‘the moderated unknown ’ [UPG04]. ↩
17A non-equivariant PNL interpretation still interprets term-formers equivariantly. Only the predicates might not be equivariant. We do this in order to completely model (Ax) from Figure 2, so that P() P(); see Theorem A.9. Of course it is possible to imagine a notion of non-equivariant interpretation where term-formers are interpreted as non-equivariant functions. This would correspond to something else: namely, to losing the property that f( f(). ↩
18In other words, restricted to those HOL variables in that are PNL atoms (condition 5 of Definition 4.2) is a renaming (Definition 5.1). ↩
19If we translated PNL to first-order logic then we would probably map atoms to numbers instead. This is future work. ↩
20Conversely, Fiore and Hur would view PNL as a restriction of their logic without substitution. The two points of view are consistent with each other, of course, and it is interesting that different authors are converg-ing on similar systems. It might be worth mentioning that deduction modulo by the first author with Hardin and Kirchner was designed to mediate between these kinds of design decisions while retaining proof-theory [DHK98]. ↩
21(R) and (L) can increase the free unknowns—but not the free atoms. ↩