From nominal sets binding to functions and -abstraction: connecting the logic of permutation models with the logic of functions
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
We acknowledge the support of DIGITEO, Paris and grant RYC-2006-002131, Polytechnic University of Madrid. November 20, 2011
1. Introduction
Permissive-Nominal Logic (PNL) extends first-order predicate logic with term-formers that can bind names in their arguments. For instance, arithmetic, set theory, and functions axiomatise naturally in PNL; their binders are modelled as ordinary PNL term-formers and their axioms look very much like the axioms normally written in informal practice. PNL is sound and complete for a first-order style semantics in (permissive-nominal) sets [DG11, Gab11b]. This captures the essence of nominal techniques, whose initial motivation has been to handle names and binding in a first-order framework.
Higher-order logic (HOL) also has binding [Mil92, 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].
This paper is not about how PNL and HOL can be used as meta-mathematical reasoning frameworks, or about what models look like expressed as nominal sets or as functions. The deeper point is that we have before us two foundations for mathematics. The question we address is then as follows: There is a ‘nominal’ model of names and binding which can be applied in various ways, and also a functional model which can also be applied in various ways. These are captured by two logics—PNL and HOL—and by their nominal and functional denotations respectively. We observe that these are clearly different, yet their applications just as clearly overlap. So, what positive and mathematically precise statements we now make about their relationship?
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.2
This raises the question of how PNL translates to HOL, and how PNL models translate to functional models.
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 seems to be inherent and reflects natural differences in structure between nominal and ‘ordinary’ sets. 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. Thus, the nominal and functional models of names and binding are distinct, but they 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. PNL is designed as a first-order logic for denotations with binding. The reader can find sound and complete nominal algebra theories for substitution, -equivalence, and first-order logic [GM06a, GM10, GM06c] (nominal algebra can be viewed as the equality fragment of PNL). Not all PNL theories are expressed in the equality fragment. For instance, in the paper which introduced PNL [DG10] we included theories of first-order logic and arithmetic which put universal quantification to the left of an implication. This cannot be done in nominal algebra because it is a purely equational logic.
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 pmss 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 automatically by the PNL system.
Sugar () to []. Then axioms for -equivalence are:
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.
Note that in the axioms above, and cannot be equal because they are distinct atoms, and atoms are data, not variables ( is , and is , and they are distinct). More on this and on the use of permutations in the body of the paper.3
Equality reasoning is not necessary to -rename atoms in PNL; we can quotient by -equivalence so that we can rename to without proving a logical equivalence. This is unlike other ‘nominal’ reasoning systems, such as Fraenkel-Mostowski set theory as used by the author with Pitts to introduce nominal techniques in [GP01], nominal rewriting by Fernández and the second author [FG07], nominal algebra by the second author with Mathijssen [GM06b, GM07, GM09a], Prolog by Cheney and Urban [CU08], and other systems in the same spirit.
1.2. 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, DG11].4 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.
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 [Gab11b]). 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.5 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 [DG11] 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, DG11, Gab11b].
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 locations’.
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.
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 pmss, such that for each sort and permission set the set sort( pmss( 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 .
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).
A permutation is a bijection on such that
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.4, we have the following terms and propositions:
var() : where .
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 pmss(Π(pmss) such that Π() is finite.
Write Π for functional composition, Id for the identity permutation, and Π-1 for inverse, much as in Notation 2.7.
Define a (level 2) permutation action by:
Suppose is a set of atoms and is a level 1 permutation. Suppose is a set of unknowns and Π is a level 2 permutation. Define and Π by
This is the standard pointwise permutation action on sets.
Define free atoms fa and fa by:
Define free unknowns fV and fV by:
fa(fa and fa(fa
Also, fV (ΠfV and fV (ΠfV
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:6
Write () for the (level 1) swapping permutation which maps to and to and all other to themselves. Similarly, provided sort( sort() and pmss( pmss, 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:
We -convert and in P([]).
Let sort( sort and pmss( pmss. Suppose pmss. Using () and () we deduce:
It is routine to convert this sketch into a full derivation-tree.
2.4. Substitution
A (level 2) substitution is a function from unknowns to terms such that:
For all , () : sort and fa(()) pmss
( id for all but finitely many .
will range over substitutions.
Define nontriv by:
nontriv(()id or fV (()) for some
nontriv is unknowns that can be produced or consumed by , other than in the trivial manner that ( id.
Level 2 substitution is capturing for level 1 abstraction -. For example if ( then ([])]. This is the behaviour displayed by the informal meta-level when we write “take to be in ”.
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 fV (ΦfV
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 Φ Ψ.
Figure 1 is the logic of [DG11, Gab11b]. 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.6); 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:
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 [Mil92, 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.
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() .7
A signature is then a tuple ( type).
We write g : for type(g.
For each signature type) and each type over fix a countably infinite set of variables of that type.
will range over distinct HOL variables.8 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.
Ξ and will range over sets of HOL propositions. We may write Ξ and Ξ as shorthand for Ξ.
Write fV (ΞfV
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 . Also write as shorthand for pmss
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:
For every atoms-sort in assume a HOL base type .
For every base sort assume a HOL type .
Translate sorts in to types in as follows:
For every term-former f : () assume a HOL constant : .
For every proposition-former P : assume a HOL constant .
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.6 is also a permutation in the sense of Definition 3.5.
For every unknown : and list assume a distinct HOL variable that is not an atom9 of type where is the sorts of the atoms in , in order.
Suppose (Notation 4.1) is the list and write for . Assume a proposition-former equal of appropriate arity. Then:
Assuming appropriate axioms for equal, we would expect this to be true. Now assume is the list [] and write for . Then:
We would expect this to be false. What has changed with respect to the previous case, is that is fresh for but not for .
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 fa() fv() uses the assumption that pmss. The corollary follows; for more details see [DGM10, Section 8].
4.2. Capture typing
In order to translate to HOL, some atoms are ‘important’ and others are not. This is expressed by a capture typing, an idea going back to [DGM09, DGM10].
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 . This is made formal in Proposition 4.8, which is Theorems 8.12 and 8.14 of [DGM10]:
If and then
-equality, because we quotiented terms by this relation), and similarly for and .
If then there exists such that
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.
The case where . By inductive hypothesis : for some type . It follows that : .
The case . Suppose . It is routine to check that : sort.
4.3. Re-indexing capture contexts
When we prove soundness of the translation (Theorem 4.16) there will be a problem, because we are interested in proving soundness of translating a sequent Φ Ψ but because we work by induction on derivations Π we may have to translate all sequents in Π, some of which might have ‘extra’ capturable atoms.
We need to translate using a large and then re-index to Γ:
Define a substitution Γ by:
If : then
Similarly, if : then
By inductions on and . We consider a selection of cases:
The case . We reason as follows:
The case . We reason as follows:
The case . We reason as follows:
4.4. 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.5. Then:
If nontriv
A fact of -conversion [DGM10, Lemma 9.2].
Write when sort and fa
Suppose and . Suppose . Then:
Suppose and . Then [].
Choose such that and for every sequent appearing in Π—it is not hard to verify that some such must exist.
It is routine to verify by induction on Π that is derivable; the case of (R) uses Proposition 4.15. So in particular .
It follows, applying the substitution to both sides and using Theorem 4.11, that
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
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.6 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.26, in this paper). This is constructed like a pair, from and , but destructed like a partial function the graph of which is evident in Definition 5.26. It is defined 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.10). Completeness quickly follows.
5.1. Categories of finitely-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.6, a renaming is a map from to such that
For let an atomic renaming [] map to , to , and other to themselves.
will range over renamings.
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.5) 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.
If X then supp(supp
If X then supp() supp As a corollary, if is injective on supp then supp(supp
By routine calculations using the group/monoid action.
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.
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.
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
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
It is a fact that PmsPrm is cartesian closed and functions have the conjugation action
and is supported in the sense of Definition 5.12 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.17. However, the end result is similar to the conjugation action, in a sense made formal in Lemma 5.19 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 (()
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.12.) 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.17 is well-defined. That is, it does not matter which freshening pair of renamings we choose.
Consider two freshening pairs of renamings and .
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
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 ([])(
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
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 domsupp( and ( is not necessarily distinct from ). Write - for the renaming such that (-)(
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
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.28 for the completeness proof but we include it for the interested reader to compare and constrast with Definition 5.26.
Definitions 5.26 and 5.28 look similar; both define graphs of partial functions defined on supp
That is,
A cognate of Lemma 5.27 also holds for X:
Suppose X is a finitely-supported permutation set.
1. X is a permissive-nominal set.
2. ] if and only if , for and X.
3. ] if and only if supp and () (or equivalently []), for and X.
5.3.3. Product
If X and X are supported permutation sets for 1 then define X X and X X by:
supp(
supp([] supp
supp((supp
5.4. The free extension of a permutation set to a renaming set
If is an equivalence relation, [-] will denote the equivalence class of -in .
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.10 also ( for every supp(()).
The case () (). Then also (()) (()) and by equivariance (().
Rules 2 and 1 of Definition 5.34 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
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.34,
() ((
Where we are dealing with more than zero or one atoms at a time, isomorphisms like those in Lemma 5.37 may fail:
ren() is not isomorphic to renren (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.3).
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.9).
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.11
6.2. Interpretation of terms
Suppose is an interpretation for . A valuation to is a map on unknowns such that for each unknown ,
supp(()) pmss
will range over valuations.
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
It is easy to verify that [] is also a valuation to .
Suppose is an interpretation. Define an interpretation of propositions by:
We may identify with a set of valuations
If ( for all fV then
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.34). 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.10. Completeness follows quickly as a corollary (Theorem 8.12).
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 intepretation 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).
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 wrapping 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.10 work, which is central to Corollary 8.11 and to Completeness (Theorem 8.12).
Why Lemma 8.10 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.10 is that ren(-) does not commute with atoms-abstraction or even with cartesian product. That is, even e.g. in PmsRen has an ‘exotic element’.
1. The natural map from ren to mapping to , is a bijection (cf. Lemma 5.37).
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 (Definition 5.23), is not surjective.
1. By rule 2 of Definition 5.34.
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 ([]() id ()) is not in the image of the natural map, so the map is also not surjective.
3. Take X and consider [][]()
4. Take X Y for considered a renaming set as in Definition 5.25. Consider the function [] , mapping to , to , and all other to .
7.2. Interpretation of terms
A (HOL) valuation to is a map on variables : such that
Extend to terms as follows:
ren(f) and ren(P) (Definition 5.34).
(max1.
)(min
( where ([ provided that : for some PNL sort and for some name sort and (-converting if necessary) supp(()).
(([]) provided that : where is not equal to for any or .
(]) provided that : for some PNL sort , where ( id (by construction some such always exists) and (, and (renaming if necessary) nontriv
(
()()() provided that
()(
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 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.26) is the graph of a partial function, whereas ‘wants’ to take denotation as a total function. So we use a commuting square as illustrated, and in PmsRen atoms-abstraction can be viewed as a total function, as noted in Remark 5.29. Definition 7.6 uses this, and fills in the right-hand arrow.
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.34.
Lemma 8.9 proves commutativity of the square.
Suppose and . Suppose supp(()) for every fv
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
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 ):
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
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.12) of the translation from Definition 4.3. The proof is subtle; notably Lemma 8.4 and the case of in Lemma 8.10 are non-trivial. Some mathematical action also takes place in Lemma 8.9 and the case of in Lemma 8.10.
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
as a corollary, if : and
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.10 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 [] [].
Suppose . Then (( id for some sort.12
Compare Lemma 8.9 with Lemma 4.12:
If nontriv
Lemma 8.10 proves that the schematic diagram of Remark 7.7 does indeed commute:
Suppose : and : . Then:
If then (( id
If then ((
By inductions on and .
The case . We reason as follows, where sort and pmss:
Note of the penultimate step that by assumption , so by Definition 4.6 nontriv
The case . We reason as follows:
The case We reason as follows:
The case . Write sort and pmss. From Definition 7.6
By construction in Definition 7.1 every [] has the form for . By Lemma 8.4 we have
Using Lemma 8.4 again we assume without loss of generality that supp([]) pmss
Now we unfold definitions and use the inductive hypothesis that ()[id ([]), 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 modality [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. 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, DG11].
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.11 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.10. We describe and exploit that overlap, in this paper.
PmsRen from Definition 5.11 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, Gab07].
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.34 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 apparent 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.13
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, refinement, 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 [DG11] 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
Neither equivariance nor shift are translated to HOL in this paper; more on this in the next subsection.
9.2. 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 [DG11, Gab11b]. 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 [GM08, DG11].
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 extensionality. Journal of Symbolic Logic, 69:1027–1088, 2004.
[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.
[CU08] James Cheney and Christian Urban. Nominal logic programming. ACM Transactions on Programming Languages and Systems (TOPLAS), 30(5):1–47, 2008.
[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, 2010.
[DG11] Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic (journal version). Transactions on Computational Logic, 2011. In press.
[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.
[FG07] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting (journal version). Information and Computation, 205(6):917–965, June 2007.
[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, 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.
[Gab07] 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. Nominal terms and nominal logics: from foundations to meta-mathematics. In Handbook of Philosophical Logic, volume 17. Kluwer, 2012.
[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.
[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. Nominal Algebra. In 18th Nordic Workshop on Programming Theory, October 2006.
[GM06c] 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.
[GM08] Murdoch J. Gabbay and Aad Mathijssen. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing, 20(4-5):451–479, June 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.
[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. Cambridge 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.
[Mil92] Dale Miller. Logic, higher order. In Stuart Shapiro, editor, Encyclopedia of artificial intelligence (second edition). Wiley, 1992. Available online from the author’s webpage.
[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.
[UPG04] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, September 2004.
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 [DG11, Section 7] or [Gab11b, 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 [DG11, Gab11b] 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 (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
Define a translation - from PNL propositions in the signature to PNL propositions in the signature by mapping 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.13 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.14
If Φ Ψ in PNL and fa(Φ) fa(Ψ) pmss() 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 instantiate .
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 pmss(). By assumption fa(Φ) fa(Ψ) fa
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(Ψ) pmss(). Thus by Proposition A.8 Φ Ψ.
By completeness of full PNL with respect to equivariant models ([DG11, Theorem 3.45], [Gab11b, 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). ↩
2In other words, we want a shallow embedding of PNL into HOL. A deep embedding e.g. of HOL in PNL is an answer to a different question; for more on this direction, see [GM09b]. ↩
3The axioms above also have typing constraints, because unknowns are typed with their permission set. These typing constraints turn out not to be so restrictive, for quite subtle reasons. The interested reader can find a discussion in [DG11, Subsection 2.7]. For the purposes of the discussion here, it is not important. ↩
4Note 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. ↩
5There has been more than enough of that already, and anyway, because truth is free, proving theorems is never a zero sum game. ↩
6We do not assume a congruence is an equivalence relation. This is because in a more general context we are interested in rewriting relations, which satisfy the rules below but are not equivalence relations. ↩
7The authors deprecate calling this ‘higher-order abstract syntax’ (HOAS), as sometimes happens. We should reserve that term for inductive types with binding constructed using constants of higher type like (Λ Λ) Λ (strong HOAS) or ( Λ) Λ (weak HOAS) [DH94, PE88]. 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]. ↩
8This means that if the reader sees ‘’ this could refer either to a HOL variable or—recalling Definition 2.3—to a PNL unknown. We will make sure that it is always clear from context which is meant. ↩
9So is one of the countably infinitely many HOL variables that are not atoms. ↩
10Recall from Definition 2.5 that by convention and are distinct. ↩
11A 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(). ↩
12The point here is that (()) is not equal to for any that is non-injective on supp ↩
13Conversely, 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 converging 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]. ↩
14(R) and (L) can increase the free unknowns—but not the free atoms. ↩