Permissive-Nominal Logic (journal version)
Permissive-Nominal Logic (PNL) is an extension of first-order predicate logic in which term-formers can bind names in their arguments.
This allows for direct axiomatisations with binders, such as of the -binder of the lambda-calculus or the -binder of first-order logic. It also allows us to finitely axiomatise arithmetic, and similarly to axiomatise ‘nominal’ datatypes-with-binding.
Just like first- and higher-order logic, equality reasoning is not necessary to -rename.
This gives PNL much of the expressive power of higher-order logic, but models and derivations of PNL are first-order in character, and the logic seems to strike a good balance between expressivity and simplicity.
Categories and Subject Descriptors: F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic— Set theory; Lambda-calculus and related systems; I.2.3 [Artificial Intelligence]: Deduction and Theorem Proving— Metatheory
General Terms: Theory, Languages
Additional Key Words and Phrases: Permissive-nominal logic, nominal sets, names and binding, permutation
ACM Reference Format: Dowek, G., Gabbay, M. J., 2010. Permissive-nominal logic (journal version) ACM Trans. Comput. Logic V, N, Article A (January YYYY), 36 pages. DOI 10.1145/0000000.0000000 http://doi.acm.org/10.1145/0000000.0000000
Thanks to the anonymous referees. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.
1. INTRODUCTION
In the early 20th century, the expressivity of logics was considered in principle. For example, first-order predicate logics with or without term-formers are equally expressive, in principle.
In the early 21st century, more attention is paid to what we like to call ‘ergonomics’. First-order predicate logic with term-formers is more ergonomic than first-order predicate logic without term-formers; terms, propositions and proofs are shorter and more natural in the former than in the latter.
Another imperative is for a weak logic—the fewer ‘bells and whistles’ we have to worry about, the easier it will be to verify, implement, and prove its meta-theoretic properties. This can be in tension with being ergonomic, as the example of first-order predicate logic with or without term-formers illustrates.
Thus there enters a fruitful design tension: we aim for logics that are so ergonomic that they ‘just work’, yet so weak and well-behaved that we can still prove good properties for them.
Now we come to the issue of binding. Binding is ubiquitous in logical specifications in mathematics—binding features in function definitions via -abstraction, and binders are also used to define sets in comprehension, and to define finite and infinite sums, integrals, derivations, quantifiers, and so on. A logic for mathematics that provides support for this central and essential notion, is likely to be more ergonomic than a logic that does not.
First-order logic is weak, computationally tractable, and has good theoretical properties (unification of first-order terms is decidable; proof-search is simple and well-understood; models are simple). However, first-order logic is unergonomic in the sense that it does not admit term-formers that can bind. Thus it is hard to give direct, finite, first-order axiomatisations of set theory, arithmetic, higher-order logic, or the -calculus.
This is one reason that e.g. higher-order logic is often used as a specification language in theory (see [Farmer 2008] for an excellent exposition) and implementations (like Isabelle [Paulson 1990])—higher-order logic has a binder () built-in to terms, and so is more ergonomic.
However, higher-order logic is also stronger than first-order logic, less computationally tractable, and models tend to be more complex. The jump from first- to higher-order logic is quite large.
This motivates the study of direct extensions of first-order predicate logic with term-formers that can bind. The topic of this paper is the construction of one such extension, which we call permissive-nominal logic (PNL). PNL has a clear first-order flavour, and it admits term-formers that bind.
Technical summary and overview. The main technical contributions of this paper are: the definition of permissive-nominal logic, in particular how it handles freshness side-conditions and how this permits the addition of universal quantification to nominal terms; the Tarski-style models we then construct; and the finite yet fully first-order axiomatisations of substitution, first-order logic, and arithmetic which we then exhibit.
Soundness, completeness, and cut-elimination follow by fairly routine arguments, but we see this as a good sign: that the definition of permissive-nominal logic remains close to first-order logic, while allowing terms with binders.
An overview of this paper is as follows:
— We introduce the syntax and derivation rules of permissive-nominal logic (Section 2). The impatient reader can jump directly to Figure 1 on page 11 and see that these derivation rules are virtually indistinguishable from those of first-order logic; only an extra side-condition in (L) hints at any difference.1
— We prove soundness and completeness (Theorems 3.30 and 3.45) with respect to a suitable notion of permissive-nominal set (Definition 3.4).
— We axiomatise arithmetic in PNL and prove a correctness and conservative extension result Theorem 5.21. The axiomatisation of arithmetic is finite; the induction schema normally given in first-order logic arithmetic is represented by a single axiom with a universal quantification over a permissive-nominal terms unknown.
— We indicate how to axiomatise nominal inductive datatypes, the -quantifier, and semantic freshness (Section 6).
— We prove cut-elimination (Theorem 7.7). The proof is virtually identical to that of first-order logic.
Permissive-nominal logic, nominal logic, and nominal terms. Permissive-nominal logic follows the nominal logic of [Pitts 2003] in its name, which coined the term ‘nominal’, but nominal logic from [Pitts 2003] is a first-order theory of (set of axioms for) the equivariant Fraenkel-Mostowski sets and associated constructions used in [Gabbay and Pitts 2001]. The syntax, semantics, and derivability of PNL are new, as indeed is the application to arithmetic.
The term-language of PNL goes back to the nominal terms of [Urban et al. 2004]. It is permissive, which means that the freshness contexts from [Urban et al. 2004] become a kind of sorting constraint called permission sets. For more discussion see [Dowek et al. 2010] which introduced permissive-nominal terms, and amongst other things gave correspondences with nominal terms and also higher-order patterns.
In this paper we extend nominal syntax further by introducing shift-permutations (Definition 2.9). Also, unlike [Urban et al. 2004; Dowek et al. 2010] in PNL there is quantification over unknowns .
This journal paper follows a conference paper [Dowek and Gabbay 2010]. With respect to that paper, we have made the following changes:
— The treatment of -equivalence has been streamlined, leading to simplified proofs. Two structural rules and have been eliminated.
— The rule () from [Dowek and Gabbay 2010] is now part of the axiom rule, further simplifying the proof-theory.
— The notion of permutation includes shift-permutations; these permutations ‘shift all atoms up by one’. Some readers will see in this a de Bruijn-like ‘shift’ function [Abadi et al. 1991]. This gives desirable extra power to -quantification and, perhaps surprisingly, turns out to be compatible with nominal techniques’ characteristic small support property.
— We include proofs of completeness by a standard term-model construction, and a sketch proof of cut-elimination.
2. PERMISSIVE-NOMINAL LOGIC
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’.
A term-signature over a sort-signature () is a tuple ( ar) where:
— and are disjoint sets of term- and 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 ().
A signature is then a tuple ( ar).
We write f : () for ar(f) and similarly we write P : for ar(P.
The reader familiar with higher-order logic can read ar() as : and no harm will come of it. We do not do this because we are following a first-order logic notation—and because we want to avoid any possible confusion that () might be a sort. It is not.
A signature for the -calculus would have one name-sort , one base sort , and term-formers lam : ([]), app : (), and var : ().
A proposition-former for nominal freshness # would have arity (), though the arity ([]) would also be possible (this would handle more of the properties of names at the level of the logic). More on this in Subsection 6.3.
Plenty more examples of PNL theories will follow.
For each name sort fix a disjoint countably infinite set of atoms (level 1 names).
For each also fix a bijective function from to the integers 0 -1 1 -2 2 (that we can do this follows from our assumption that atoms are countable).
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 will range over permissions sets.
The use of and ensures that permission sets are infinite and also co-infinite (their complement with respect to is also infinite).
A permission set may be finitely represented
— either as the pair of finite sets () where and and ) ,
— or perhaps more elegantly as a single finite set such that where () () (exclusive or).
Permission sets are a sorting/typing annotation which will be associated to variables in Definition 2.11.
Given let a (level 1) swapping () be the bijection on atoms that maps to , to , and all other to themselves. Also define a bijection on atoms by:
Let the (level 1) permutations be the group of bijections on atoms generated by all swappings and . Call a permutation finite when it is generated just by swappings; thus, when nontriv(() is finite. Otherwise, call non-finite. will range over permutations. Write for the set of all permutations and write for the set of all finite permutations.
Swappings are used to manage -equivalence in nominal terms. This is standard and goes back (at least) to [Gabbay and Pitts 2001] and the second author’s thesis [Gabbay 2001].
The true importance of is that it bijects with for some —this cannot be achieved using a finite permutation. The relevance of this is that later when we build , this really will mean ‘for all ’ even though the permission set of makes it range over terms with free atoms in .
Permutations, like permission sets, easily admit finite representations. shift corresponds via the bijection with numbers to the operation ‘add 1’.
For each signature ar) and each sort over () and permission set fix a countably infinite set of unknowns (level 2 names) of that sort and permission set. will range over distinct unknowns. Write sort for the sort and pmss for the permission set of .
So an unknown has two type attributes: its sort , which intuitively describes what kind of data it denotes, and its permission set which describes the permitted free atoms of the terms, and also the nominal support of the denotations, with which it may be associated by a substitution or valuation—see the definitions of substitution and valuation in Definitions 2.32 and 3.19 respectively.
If has sort ‘integers’ and permission set , then intuitively represents ‘a term denoting an integer, with free atoms in ’.
Another name for permission set might be freshness set, since equally represents “terms with free atoms not in ”.2
For each signature , define raw terms and raw propositions over by:
As in Definition 2.1, we admit the possiblity of empty tuples so that () the empty tuple of terms is a term and has sort ().
We will quotient raw terms and propositions by -equivalence (to obtain terms and propositions ), later.
Consider lam([]app( var())) where pmss; this represents the -term schema () where fv
Recall that app and lam are term-formers of arities () and ([]). The sorts of and are (names) and (individuals) respectively.
Our version of PNL has connectives , , and . We could easily add other connectives like , , , , and . Instead we treat them as a definable extension using the standard ‘de Morgan’ encoding.
We may write id just as .
2.2. Permutation actions and free atoms/unknowns
Nominal techniques suggest handling -renaming using permutations. To a first approximation, if wherever the reader sees ‘permutation action’ they substitute ‘-renaming’, then they will not go too far wrong.
We use the following notation:
— Write for functional composition, so ()((())).
— Write id for the identity permutation, so id( always.
— Write for inverse, so id.
— Define by id and .
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.16.
Define a (level 2) permutation action by:
2.3. Free level 1 and level 2 variables
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(phi) by:
Define free unknowns fV and fV (phi) by:
fa(rfa and fa(phifa(phi).
Also, fV (ΠrfV and fV (ΠphifV (phi).
By routine inductions on r.
2.4. -equivalence
Call an equivalence relation on terms and on propositions a congruence when it is closed under the following rules:
We -convert and in P([]).
Let sort( sort and pmss( pmss(. Suppose and . Using () and () we deduce:
It is routine to convert this sketch into a full derivation-tree.
Furthermore, if we take syntax as above except that and , then we deduce P([]P([]).
Note that -equivalence is highly symmetric between levels 1 and 2, based on permutations instead of substitutions, and avoids equality reasoning in the logic.
In [Gabbay and Pitts 2001; Pitts 2003; Gabbay 2007a; Gabbay and Cheney 2004; Cheney 2005] it is not in general possible to ‘just -convert’ a level 1 abstraction. We must appeal instead to equality reasoning describing atoms-abstraction in nominal sets. But this is harder; derivable equality is more complex than syntactic equivalence.
For every , Π, r, s, phi, and psi, the following hold:
— r s if and only if r s and similarly phi psi if and only if phi psi.
— r s if and only if Πr Πs, and similarly phi psi if and only if Πphi Πpsi.
If r s then fa(r fa and fV (r fV
is an equivalence relation on terms and propositions.
By a standard argument as in [Fernández and Gabbay 2007], using Lemmas 2.21, 2.26, and 2.27.
If ( for every fa then r r.
For each signature , define terms and propositions over to be raw terms and propositions quotiented by -equivalence. and will range over terms. and will range over propositions.
Terms and propositions inherit the definitions and properties of raw terms and propositions. Thus for example we may write fa to mean ‘fa for some r ’ (Lemma 2.27 proves this is well-defined).
It is possible to construct terms and propositions directly using a variant of nominal syntax-with-binding from [Gabbay and Pitts 2001], tweaked to include permutation and abstraction by unknowns.
It is also possible to retain the definitions above—reasoning on -equivalence classes of terms—and to use theorems of abstractive functions developed in [Gabbay 2007b], which are an alternative ‘nominal’ way to guarantee well-definedness of functions defined on -equivalence classes.
We will not dwell on these issues in this paper because we are most interested in what PNL syntax can express rather than thinking about the syntax for its own sake. However, the mathematics to do this exists and is well-understood.
2.5. 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.
One kind of substitution will be particularly useful later:
By convention (Definition 2.11) and in Definition 2.34 range over distinct unknowns:
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 ”.
Only atoms in pmss may be captured in this way. Thus for instance, if pmss then ( is impossible because it would violate the condition fa(()) pmss in Definition 2.32.
The condition fa(()) pmss in Definition 2.32, and the condition fa
Consider a name sort and suppose : and : . Suppose pmss, so that by Definition 2.23 () id.3
Suppose we drop the conditions on free atoms of terms, so that we admit [] as a substitution. Then according to the definitions, (())[ whereas (id)[ .
In PNL, atoms are data; they are ‘bindable constant symbols’. Atoms are not variables; they do not come with a substitution as a primitive in PNL. (Unknowns are variables; they have a substitution action.)
The reader should not expect atoms to populate every sort, like variables do. Atoms populate their own special sorts, name-sorts, which are sorts for ‘bindable data’.
We can make atoms populate a base sort (e.g. variable symbols with sort ‘-terms’ or ‘functions’) with a term-former (Definition 2.3), e.g. var in Sections 4 and 6.
We can make atoms behave like variables using axioms, like those of SUB in Figure 4. In PNL, a substitution action for atoms is a matter of writing suitable axioms. Fortunately, nominal techniques make this fairly easy to do.
2.6. Sequents and derivability
Φ and Ψ will range over sets of propositions. We may write Φ and Φ as shorthand for Φ. We may write Φ Ψ as shorthand for Φ Ψ. Finally, define fV by
A sequent is a pair Φ Ψ.
The derivable sequents are defined in Figure 1.
As standard, the intuition of Φ Ψ being derivable is “the conjunction (logical and) of the propositions in Φ entails the disjunction (logical or) of the propositions in Ψ”. So for instance, intuitively the axiom rule (Ax) expresses that if and only if .
The in (Ax) is deliberate and represents equivariance (preservation of truth under permuting atoms) within permissive-nominal logic.4 Examples of how is used follow immediately in Subsection 2.7.
We may write Φ Ψ as shorthand for ‘Φ Ψ is a derivable sequent’.
We may write Φ Ψ as shorthand for ‘Φ Ψ is not a derivable sequent’.
Figure 1 includes rules for , , and . Following on from Remark 2.15, note that including rules for other connectives like , , , , and would be easy. Because the PNL in this paper is classical, we can treat derivation rules for them as a definable extension of what we already have.
We see no inherent difficulty with constructing an intuitionistic version of PNL.
2.7. Universal quantification, permission sorts, and shift-permutations
Recall the comment on ‘atoms as data’ in Remark 2.38. Because of permutations, in certain circumstances free atoms can still behave like variables ranging over distinct atoms (cf. the permutative convention of Definition 2.7). Atoms-substitution is not be primitive in PNL, but atoms-permutation is.
Thus in PNL we can express a theory of atoms-inequality in the following interesting way: Assume a name sort Atm and a proposition-former neq : (Atm Atm), along with a single proposition neq() for two distinct atoms in Atm—and, if we wish, a proposition neq() . The permutation in (Ax) ensures that and represent any two distinct atoms.
This goes further. The condition fa
— Suppose a name sort Atm and suppose : Atm and a proposition-former P of arity Atm. Suppose pmss. By considering the swapping () and (Ax), and (L),
In other words, we can derive from , even if is not permitted in . Thus, in the case of level 2 closed terms (without unknowns), these have finitely many atoms and we can use a finite permutation to place them in pmss
— This may not work for the more general case of a term with unknowns; for example there is no finite such that fa(()) pmss where pmss
So consider the general case of any sort and suppose : and pmss(. Suppose Q : . Consider any other : and pmss(. We will show that
Recall that shift permutation from Definition 2.9 and the definition of shift from Notation 2.16. Using shift permutations we can construct a permutation such that pmss5 We derive as follows:
— Nevertheless, does not mean “[] for every ”. This is because permutations are bijective. For example, suppose : Atm, pmss, and P : ([Atm]Atm). Then P([]) ([]) for all such that fa, and also P([]) ([]) for all and all such that fa. However,
The fact that pmss forbids capture by an instantiation, in a suitable sense.
3. SEMANTICS OF PERMISSIVE-NOMINAL LOGIC
Nominal sets were introduced in [Gabbay and Pitts 2001] (they were called ‘FM sets’). Technically, a nominal set is a set with a finitely-supported permutation action for atoms. Intuitively, a nominal set is a set with ‘free names’ in a manner which parallels how names feature in abstract syntax, but without necessarily being syntactic structures.
Names in nominal sets are modelled as atoms. They can be renamed by the permutation action; they can be bound by an atoms-abstraction construction; and they feature a finite support property which guarantees that we can always pick a fresh name.
The interested reader can consult a literature which includes [Gabbay and Pitts 2001] or [Gabbay 2011b] for detailed discussions of nominal sets and their applications.
We will interpret PNL using permissive-nominal sets. The permissive-nominal sets we use here generalise nominal sets in two ways:
— They allow infinite support, since permission sets from Definition 2.7 need not be finite.
— They allow (some) infinite permutations, since permutations from Definition 2.9 are generated as a group by swappings and by infinite shift permutations, thus giving -quantification extra power as discussed in Subsection 2.7.
The main results are soundness (Theorem 3.30) and completeness (Theorem 3.45). The main definitions are of permissive-nominal sets in Definition 3.4, and of the interpretations of terms and propositions in Definitions 3.20 and 3.25 respectively.
The permissive-nominal development here resembles that in [Gabbay and Pitts 2001]. Definition 3.4 is a little subtle because we ignore infinite permutations when we determine support, whereas equivariance from Definition 3.16 means commuting with all permutations.
3.1. Permissive-nominal sets
Recall the set of all permutations from Definition 2.9.
A set with a permutation action X is a pair (
— a carrier set and
— a group action on the carrier set (X) X, written infix as . So, id and () for every and and every X.
Say a set of atoms supports X when for all finite permutations , if ( for all then .
Thus, if a permission set supports and ( then .
contains infinite as well as finite permutations. In the next paragraph we construct an that is supported by (so that for all finite ) and yet () . This observation is the same as fuzzy support from [Gabbay 2007b].
Recall the order on from Definition 2.7 and consider
the set of finite permutations of written out in order, with the pointwise permutation action. Then for every finite permutation, but .
A permissive-nominal set is a set with a permutation action such that every element has a supporting permission set. X, Y will range over permissive-nominal sets.
Suppose X is a permissive-nominal set. Then every X has a unique least supporting set supp
As a corollary, if is finite and ( for all supp then .
Theorem 3.5 is familiar from [Gabbay and Pitts 2001], but we do have to be a little bit careful since we are not working with nominal sets. It all works out:
The corollary is immediate given the definition of support (Definition 3.2).
Define permission set, supports . Also, choose some permission set that supports .
Suppose is finite and ( for all . Write for the atoms in nontriv , in some order. Let be some choice of fresh atoms (so nontriv
Suppose X is a permissive-nominal set and X. Then supp(supp (Definition 2.19).
By a routine calculation using the group action.
Suppose X is a permissive-nominal set and X. Suppose supp. Then () implies supp
Suppose supp. We prove the contrapositive. Suppose supp. By Lemma 3.6 supp(())supp. By our suppositions, ()supp() supp. It follows that ().
3.2. Examples of permissive-nominal sets
3.2.1. Atoms
the set of atoms can be considered a permissive-nominal set with a natural permutation action
The set 0 1 can be considered a permissive-nominal set with the natural trivial permutation action for all and 0 1.
In the cases of and 0 1 only, we will be lax about the distinction between the set, and the permissive-nominal set with its natural permutation action.
3.2.2. Atoms-abstraction
In the definition of in Definition 3.9 recall that by our permutative convention . An equivalent and more compact way of writing this is () fix(supp) where fix((.
(1) X is a permissive-nominal set.
(2) ] if and only if , for and X.
(3) ] if and only if supp and (), for and X.
3.2.3. Product
If are permissive-nominal sets for 1 then define by:
— supp(
— supp([] supp
— supp((supp
Proofs are as in [Gabbay and Pitts 2001] or [Gabbay 2011b].
3.3. Interpretation and soundness
3.3.1. Interpretation of signatures
Suppose X and Y are sets with a permutation action. Call a function from to equivariant when
X((() (equivariance for functions)
If from to is equivariant then supp(()) supp for all X.
If fix(supp()) then ((), and if is finite then .
Suppose ar) is a signature (Definition 2.3).
A (PNL) interpretation for consists of the following data:
— An interpretation for the sort-signature () (Definition 3.14).
— For every f with ar(f) an equivariant function f from to (Definition 3.16).
— For every P with ar(P a finite equivariant function P from to 0 1 (Definition 3.8).
Suppose is an interpretation for . A valuation to is a map on unknowns such that for each unknown ,
—
— supp(()) pmss
will range over valuations.
3.3.2. Interpretation of terms
If : then
By a routine induction on .
.
supp() fa
3.3.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 .
always.
By induction on . We consider two cases:
— The case . Suppose . This means that for all
— The case . We have P(). As P is equivariant, we get P(). By Lemma 3.22 . Thus P(.
— [].
—
If ( for all fV then
By a routine induction on and .
3.3.4. Validity and soundness
Call the proposition valid in when for all .
Call the sequent valid in when () () is valid.
If Φ Ψ is derivable, then it is valid in all interpretations.
3.4. Completeness
In this subsection we prove Theorem 3.45: a converse to Theorem 3.30, that if is valid in all models, then it is derivable.
For this subsection fix the following data:
— A signature ar).
— A formula such that .
We will construct an interpretation and a valuation (Definition 3.14) such that . This suffices to prove the result.
3.4.1. Maximally consistent set of propositions
Choose a fixed but arbitrary enumeration of propositions , , , ...
Define . For each 1 we define as follows:
— If then write .
— If then write .
— If and then write .
There are now two cases:
— If has the form then we define [] where is some fixed but arbitrary choice of unknown that is not free in any proposition in and is such that pmss( pmss and sort( sort
— Otherwise, we define .
Finally, we define by .
For every , .
By induction on :
— By definition . As , we have
— Suppose . Either or []—we consider the first, simpler case; the second case is similar. Suppose . It follows that . So we are not in the third case of Definition 3.31 and we are either in the first or the second. So and thus ; a contradiction.
.
Assume . So there exists a finite subset Γ of such that Γ . As Γ is finite it is included in some , and , contradicting Proposition 3.32.
For every , at least one of and holds.
We check of Definition 3.31 that for every , either or . The result follows.
For every , if then there exists a such that [] .
There exists an such that . Since and , we have that , and so . Thus []. The result follows.
If then .
(1) () if and only if ( or ).
(2) if and only if (for every such that : sort and fa
(1) Suppose () and . Then and so by Lemma 3.36 . Suppose . By Lemma 3.34 . So and therefore . By Lemma 3.36 () . Suppose . Then and so . By Lemma 3.36 () .
(2) Suppose . By Lemma 3.36, if : sort and
3.4.2. The term model
Define by:
—
— f maps to
— P maps to 1 if P() and to 0 otherwise.
Define by
We endow with a permutation action given by the action on terms.
supp( fa
As a corollary, from Definition 3.38 is a permissive-nominal set.
We prove two subset inclusions:
— Proof that supp
— Proof that fa
The corollary is immediate, unpacking Definition 3.2.
(1) If ar(f) then f is well-defined, equivariant, and maps to .
(2) If ar(P then P is well-defined, equivariant, and maps to 0 1.
(1) The only (very) slightly non-trivial part is equivariance. We reason as follows:
(2) The case of P is similar.
is an interpretation of the signature ar) which we fixed at the beginning of this subsection. In addition, is a valuation to .
.
By a routine induction on the definition of in Definition 3.20. We consider just one case:
— The case of . We reason as follows:
if and only if .
If , then there exists a model and a valuation such that .
As and , we have . By Lemma 3.43, we get .
As a corollary we get Theorem 3.45:
4. SPECIFYING ARITHMETIC IN PERMISSIVE-NOMINAL LOGIC
We start by defining the sorts, term-formers, and proposition-formers of a signature which is suitable for finitely specifying arithmetic in PNL. We then specify its axioms and, in Subsection 4.2, we discuss them in detail.
4.1. The signature and the axioms
A signature suitable for writing out a PNL theory of first-order logic is given in Figure 2.
We introduce the following syntactic sugar:
— We may write ([]) as [].
— We may write ([]) as [].
— We may write both and just as .
Examples of this syntactic sugar in use, follow immediately below.
Equality. Axioms for equality : () and equality : () are given in Figure 3.
Substitution. Axioms for substitution and are given in Figure 4.
We arguably abuse notation in Figure 4 when we use variables of sort and as appropriate not necessarily giving them distinct names (e.g. in (sub) has sort , whereas in (sub) we use another variable also written with sort ).
First-order logic. Axioms reflecting first-order formulas (in a shallow sense) as terms in PNL (the , , and ) are given in Figure 5.
Arithmetic. Given EQU, SUB, and FOL, it is not hard to write axioms for arithmetic in PNL. This is in Figure 6. Later on in Theorem 5.21 we prove that this is an axiomatisation of arithmetic in PNL.
4.2. Comments on the axioms
In [Gabbay and Mathijssen 2008a] capture-avoiding substitution is equationally axiomatised using nominal algebra in the style of SUB. Soundness and completeness are proved, so providing some formal sense in which the axioms of SUB are ‘right’.
In [Gabbay and Mathijssen 2008b] first-order logic is equationally axiomatised using nominal algebra (so the axioms involve only equality). The axioms of FOL are not based on those of [Gabbay and Mathijssen 2008b]. In FOL, we take advantage of the stronger language provided by PNL; Because PNL is already a first-order logic, we can use , , and directly to capture the behaviour of , , and . In [Gabbay and Mathijssen 2008b] we had to work a little harder because the ambient logic, nominal algebra, was purely equational.
Instead of the axioms for equality EQU, we could directly extend PNL by adding derivation rules Figure 1 as follows:
Every unknown has a sort, and a permission set.
Different choices of permission set may yield logically equivalent results. For example, in (sublam) it is not vital that pmss is exactly (). The important point is that pmss
Similarly, in (subapp) it is not vital that pmss( pmss; when we use the axiom we can instantiate and to and such that fa() fa, and conversely if we take pmss() pmss then we can still instantiate and to and such that fa( fa
5. A THEORY OF ARITHMETIC IN FIRST-ORDER LOGIC
We now recall first-order logic and write Peano arithmetic in . Our two main theorems are:
— Theorem 5.6 which states that the PNL theory of first-order logic written in —in symbols this is EQU SUB FOL—soundly interprets first-order logic ; and
— Theorem 5.21 which states that the PNL theory of arithmetic in the PNL theory of first-order logic, soundly and completely interprets ordinary Peano arithmetic in written in .8
5.1. First-order logic
We will use the atoms from in Section 4 as variables of our first-order logic (this is not necessary, but it is convenient). So for this section, will range over distinct atoms in .
Write S for EQU SUB FOL.
S ([])
By routine inductions on and .
If Ξ is derivable in first-order logic then S (Ξ ) is derivable in PNL.
By a long but routine inspection we can check that EQU, SUB, and FOL allow us to model the behaviour of ‘real’ first-order logic. We use Lemma 5.5.
5.2. Interpretation of first-order logic
We recall the usual definition of interpretations in first-order logic:
It is convenient to fix some from here until Theorem 5.21.
Define by:
Call elements of
If write [] for the valuation mapping to and mapping to :
Give
will range over finitely-supported subsets of —so there exists some finite such that for all , if ( for all then .
would normally just be called ‘the set of valuations’. We are more specific since we separately also have valuations on unknowns (Definition 3.19).
PNL atoms are serving as variable symbols of . To conveniently apply nominal techniques, it is useful to restrict to valuations that are finite in the sense given in Definition 5.8. In any case, any term or formula will only contain finitely many atoms.
Call the formula valid in when for all .
Call valid in when () () is valid.
5.3. A theory of arithmetic in
Define a first-order theory of arithmetic by the axioms in Figure 7. An interpretation is a model of arithmetic when for each of (ps0), (pss), (p0), (psucc), (p0), (psucc), and every instance of (pind).
(pind) the induction axiom-scheme is of course of particular interest. We therefore unpack what its validity
means, in a little more detail. For every and :
— If [ , and
— if for every , implies that [succ()] ,
— then for every , .
In (pind) we take ‘every ’, and in (PInd) we do not. This is because in (PInd), is -convertible,
5.4. Building an interpretation for out of one for
Recall the PNL signature from Section 4. Suppose is a model of . We use it to build an interpretation of .
Extend to where we add all elements of as constants, and extend the interpretation to interpret these constants as themselves in . (So if then is a constant symbol in and .)
Define an -valuation
If is a term, we write for the function . If is a formula, we write for the function .
We now define an interpretation for . We give a denotation to the base sorts and of , as follows:
We give a denotation to the term-formers and proposition-formers of , as follows:
Here, and range over and and range over . We insert brackets where this might increase clarity.
For the reader’s convenience we indicate the types of some of the symbols above in an informal ‘crib sheet’:
This crib sheet is only indicative since, for instance, is not any function in (see Definition 5.8).
(1) []
(2) [] if only if .
The following equalities all hold:
(Definition 5.14) is a PNL interpretation.
We must check that:
— and are permissive-nominal sets. By routine calculations. (In fact, and are nominal sets; that is, their elements all have finite support.)
— The functions defined in Definition 5.14 map elements of , , , and correctly to the appropriate sets. By Lemma 5.17.
— is equivariant from to 0 1. By routine calculations using the fact that ().
If (Ξ ) is valid in , then Ξ is valid in .
We calculate that if (Ξ ) is valid in , then
But the proposition written out above is closed, so for all valuations , () ()
Recall from Notation 5.4 that we write S for EQUSUBFOL. Recall also from Definition 5.2 the mapping (-) from first-order logic to PNL terms.
is a model of S ARITH.
By a routine verification. We consider the axiom () from Figure 5. We unpack definitions and see that we must prove that for every in ,
— []
— []
This follows, because has a constant symbol for every . Validity of the other axioms is no harder.
We prove two implications. The top-to-bottom implication follows using Theorem 5.6.
For the bottom-to-top implication, we reason as follows: Suppose S ARITH (Ξ ) in PNL. Choose an arbitrary interpretation of first-order logic that is a model of arithmetic, with carrier set . By Soundness (Theorem 3.30) and Proposition 5.20, (Ξ ) is valid in . By Lemma 5.19 Ξ is valid in . was arbitrary, so by completeness of first-order logic [Shoenfield 1967, 4.2] it follows that Ξ is derivable.
6. MORE PNL THEORIES
So far we have built PNL and used it to finitely axiomatise arithmetic. In this section we briefly touch on how to express some known ‘nominal’ constructs within PNL.
6.1. Inductive types
Permissive-nominal logic can express the principles of nominal abstract syntax developed in [Gabbay and Pitts 2001].
Suppose a base sort , a name sort , and term-formers
Fix an unknown : and for brevity write [] as for every . Suppose an axiom-scheme, for every :
Here and have sort and we make a fixed but arbitrary choice of atom pmss
We can also express this finitely, if we axiomatise a sort for predicates (as we did for arithmetic). Here is the axiom-scheme above made finite by using the theories EQU, SUB, and FOL from Section 4:
6.2. The quantifier
Nominal sets support the -quantifier [Gabbay and Pitts 2001]. PNL also includes the -quantifier; the way in which it does this is quite interesting, as we shall see in a moment.
has some distinctive properties which are reflected in nominal logic (NL) and the logic of FM sets (FM):
Here and below we write a double horizontal line for ‘is provably equivalent to’. appears absent from Permissive-Nominal Logic (PNL). It is ‘hiding’ in the permission sets. Corresponding propositions are, where pmss:
We see from these examples that two things are happening: first, freshness conditions are hard-coded into the syntax by permission sets—and second, so is the -quantifier.
It is interesting to consider another example. In NL/FM:
Correspondingly in PNL we have:
It is easy to use the rule (Ax) from Figure 1 to construct a derivation proving that and
The in (Ax) expresses that truth is preserved by permutative renaming, or in symbols: always.
A permission set can be viewed in two ways: as giving permission to instantiate using free atoms in —but also as a form of for the atoms not in .
6.3. Freshness # and abstraction
PNL has a notion of syntactic freshness which we identify as a notion of ‘free atoms of’, and write fa and fa. Nominal sets also have a semantic notion of freshness # given by supp
As Lemma 3.23 demonstrates, intuitively if is not free in then is fresh for the denotation of . In symbols: fa
To capture in syntax the effect of a freshness predicate for a name sort on a sort , it suffices to assume EQU (or extend PNL with an equality primitive) and to assume a predicate # of arity () with an axiom
Here has sort and and have sort , and pmss and pmss. This is essentially equation 13 in [Gabbay and Pitts 2001], using permission sets to attain the effect of the -quantifier. See also [Gabbay and Mathijssen 2009, Subsection 5.2] and [Gabbay and Mathijssen 2007, Theorem 5.5] where similar observations were expressed for nominal algebra.
Similarly atoms-abstraction can be axiomatised not using atoms-abstraction as a term-former abs : () with axiom abs( ()) abs() where pmss (cf. [Gabbay and Mathijssen 2009, Subsection 5.1]).
However, it is worthwhile to provide atoms-abstraction as primitive in PNL because it gives us access to PNL -equivalence which is a structural part of the PNL derivation system: to rename in abs() into abs( ()) requires equality reasoning and axioms; to rename in requires nothing but an -conversion (in this paper, they are actually the same term).
7. CUT-ELIMINATION
Recall the (Cut) rule from Figure 1. In this section we prove that (Cut) is admissible in the presence of the other rules in Figure 1.
Suppose fa
Lemmas 7.2 and 7.3 are proved by routine arguments like those in [Dowek et al. 2010; Urban et al. 2004]:
()().
Suppose fV . Then
Suppose fa
(1) If there exists a derivation of Φ Ψ then there exists a derivation of Φ Ψ.
(2) If there exists a derivation of Φ Ψ then there exists a derivation of Φ Ψ.
By a simultaneous induction on . The case of (L) uses Lemma 7.2. (We need the simultaneous induction for (L) and (R), since parts of the proposition move between left and right.)
An instance of (Cut) rests on two sub-derivations. It is convenient to call them the left branch and right branch as illustrated:
If Φ Ψ is derivable with a derivation that uses (Cut), then it is derivable with a derivation that does not use (Cut).
The proof is as for first-order logic. The only differences are a in (Ax) and a side-condition fa
We commute instances of (Cut) upwards, as usual, following the method of [Dummett 1977, pages 139-145] or [Gabbay 2011a]. At each step, the following measure based on the depth of subderivations and the size of the cut formula, decreases:
— The size of the cut formula, and
— the longest path up the derivation the cut, that the formula persists,
lexicographically ordered.
— The commutation cases between rules for and are as standard for first-order logic.
— The essential case for is as standard.
— For the essential case for , suppose the subderivation has the following form:
By Lemma 7.4 there is a derivation ] of Φ [] Ψ. We eliminate the essential case as follows:
— Suppose the subderivation has the following form:
We use Lemma 7.5 to obtain a derivation of Φ Ψ (the transformations involved in the proof of Lemma 7.5 do not increase the inductive measure).
8. RELATED WORK
8.1. Other ‘nominal’ syntaxes and logics
Compared to other ‘nominal’ logics, PNL emphasises ergonomics. When we use PNL to axiomatize and build proofs in arithmetic or in set theory, we want our hypotheses to speak about natural numbers or sets, not to speak about atoms and freshness.
Thus, although notions of atom and freshness are important, they should be implicit; i.e. handled automatically by the logic. This is the purpose of permission sets, which allow us to handle freshness and -renaming separately from logical deduction and equality reasoning.
Axiomatisations. The two best-known ‘nominal’ logics are probably the nominal logic of [Pitts 2003] and FM set theory. Both of these are Hilbert-style theories—sets of axioms—in first-order logic. They are axiomatic theories of sets.
FM set theory contains axioms whose intended model is a sets cumulative hierarchy, whereas nominal logic contains axioms only for sets with a finitely-supported permutation action, with no assumption that they be composed of other sets. For the purposes of this paper, the difference is not important.
Qua logic, PNL is a logic whereas nominal logic and FM set theory are axiomatisations. In addition and closely related to this, we can ‘just -rename’ and ‘just choose a fresh atom’— as mentioned above we have -renaming and freshness without appealing to equality reasoning and axioms.
Proof-theories for the -quantifier. Natural deduction rules for are proposed e.g. in [Gabbay and Pitts 2001, Proposition 4.10], but these are not closed under substitution. The second author created a proof-theory for [Gabbay 2007a] with a good notion of proof-normalisation and a completeness proof, followed by an alternative treatment with Cheney [Gabbay and Cheney 2004].
These gave an operational behaviour as ‘pick a locally fresh name’; Cheney then developed another sequent system which gave an operational behaviour as ‘pick a globally fresh name’ [Cheney 2005].
The logic of [Cheney 2005] includes 12 infinite axiom-schemes (Figures 3 and 4 of [Cheney 2005]) describing the behaviour of atoms-abstraction from [Gabbay and Pitts 2001]. Thus, -equivalence (for atoms) is axiomatically handled and does not participate in the proof-theory.
PNL handles both -equivalence and the -quantifier very compactly, without recourse to axioms, and indeed requiring neither equality reasoning nor a -quantifier.
One-and-a-halfth order logic. This logic is designed to represent schematic first-order reasoning (first-order derivations in the presence of ‘unknown predicates’). It corresponds roughly to the axiomatisation of first-order logic in Section 4.
Semantic nominal terms. In [Gabbay and Mulligan 2009a] we show how to interpret level 2 variables (unknowns) as infinite lists of distinct level 1 variables (atoms). This allows us to build permissive-nominal term syntax as nominal abstract syntax-style inductive datatypes as proposed in [Gabbay and Pitts 2001]. The aim of this paper is to discuss the logic; not to analyse how its syntax could best be built.
8.2. From nominal terms-in-freshness-context to PNL terms-with-permission-sets
Nominal terms were introduced in [Urban et al. 2004] where a decidable and efficient unification algorithm was demonstrated (see [Calvès and Fernández 2008; Levy and Villaret 2010; Calvès 2010] for the state of the art). Nominal terms have been used in equational specification languages; in rewriting [Fernández and Gabbay 2007] and in universal algebra (the logic of equality) [Gabbay and Mathijssen 2009].
PNL differs from nominal terms in three ways:
— Nominal terms use a finite freshness context # whereas PNL uses permission sets, following [Dowek et al. 2009; Dowek et al. 2010] (a ‘permission set’ can equally well be considered as a freshness sets ).
— PNL predicates include universal quantification over unknowns .
— PNL term syntax includes shift-permutations (the implications of this are discussed in Subsection 2.7).
These features optimise PNL for being a first-order style logical foundation for mathematics with binding.
Another way to view this paper is as follows: PNL is the ‘obvious’ extension of nominal algebra [Gabbay and Mathijssen 2009] (an equational logic based on nominal terms), to a first-order logic.
But how then do we arrive at permissive nominal techniques, starting from nominal algebra? Suppose we have an equality axiom # f([]
(1) Assume first-order logic with a sort of atoms and some axioms (like nominal logic or FM set theory) and write
Here and are variables and freshness # can be expressed using the axioms of the logic. The problem with this is that we lose proof-theory; we are just working in a Hilbert-style axiom system.
(2) Imagine a first-order logic with nominal terms in which freshness conditions are attached to quantifiers, so that we can write
Here means ‘elements of for which is fresh’. The problem with this is that we have a poor theory of -equivalence; the freshness context for does not allow us to rename to [](), because there is no fresh for (more on this in Implementing PNL below).
Concerning the second option, we can add ‘freshening’ axioms or derivation rules to the effect that : be logically equivalent to :, and so on—this is in essence what the ‘freshening’ rule (fr) of nominal algebra (rule in Figure 2 of [Gabbay and Mathijssen 2009]) does. It should be possible to construct a version of PNL along these lines; the disadvantage would be that once is instantiated, we can no longer add further fresh atoms, unless we reintroduce (fr) into PNL, but even then we would not recover full permissive-nominal -equivalence.
In PNL we take the idea to the th degree; taking a limit of this ‘freshening’ operation to obtain infinitely many fresh atoms, we arrive at permission sets.
8.3. Non-nominal logics
First- and higher-order logic. As discussed in the Introduction, we see PNL as sitting somewhere in-between these two logics. It is more powerful—and we would claim more ergonomic—than first-order logic, because term-formers can bind. Its advantage over higher-order logic is the smaller and simpler models and generally more first-order character. Its term-syntax supports a decidable unification algorithm: both without shift [Dowek et al. 2010] and with [Gabbay 2012].
Logics based on the -quantifier. A family of logics exists based on higher-order patterns and the -quantifier [Miller and Tiu 2003; Tiu 2007; Gacek et al. 2008]. The intended meaning of e.g. is ‘’. Thus for instance the intended denotation of is , and this is false.
As this example suggests, logics based on use raising and patterns (in brief: higher-order variables applied to finite lists of distinct variables, as in ) to obtain the effect of capturing substitution and variable dependencies, whereas we use permission sets and a two-level term syntax. Our reading is that is a way of peeling a single -abstraction uniformly off all terms and pushing it ‘into the meta-level’. Or, to put it another way: generates a fresh -abstracted variable.
The main philosophical difference here is that is designed to assume -equivalence and treats variables as a ‘wire’ which must always be bound, either by in a term or possibly by a top-level ; in contrast nominal techniques treat names as global and permutable and break -equivalence down into names and permutation. In a separate journal paper submitted for publication, we relate these by translating permissive-nominal logic to higher-order logic in the style of e.g. a translation of permissive-nominal term unification to higher-order pattern unification [Dowek et al. 2010] or nominal algebra to algebra over higher-order terms [Gabbay and Mulligan 2009b].
However, note that raising can cause a linear expansion in the size of a term (because what is represented by in this paper would be represented by in a logic based on raising), and can also cause ‘silly’ -redexes (since the mechanism which encodes dependency is the same mechanism which encodes computation). This is one of the motivations for CMTT discussed below.
Contextual modal type theory (CMTT). CMTT [Nanevski et al. 2008] is a two-level system; typing contexts split into two halves; and Φ. The two levels are different from the two levels used in (permissive-)nominal terms. Variables : [Φ] range over representations of code; variables : Φ range over denotation.
This addresses a problem that is mostly orthogonal to what PNL tries to achieve. To the extent that this could be represented in PNL, it would be represented at the level of sorts—one sort for code, another for denotation (values).
Logics based on CMTT are consistent and have a well-studied proof-theory, so individual semantic models can be constructed using normal forms, but the question “what is the general class of structures which these syntactic models represent?”’ has no answer we know of. That is, no general sets-based class of models has has been given for CMTT. Developing such models—perhaps using techniques borrowed from nominal sets—would be interesting future work.
Further logics. Coming from other threads of research in computer science are logics designed to enrich first-order logic directly with binders without thinking specifically about inductive reasoning. We note in particular binding logic [Dowek et al. 2002] and -logic [Beeson 2004].
Binding logic enriched first-order terms with binders but forbade capture and turned out to be a little too weak.
-logic takes a direct approach of enriching first-order terms with -abstraction. The approach to binding taken by PNL is somewhat more general and is certainly different, in that it allows us to treat names as ‘bindable constants’. That is, we can compare names for inequality as names, while at the same time we can give them the behaviour of variables by axiomatising e.g. substitution for them, if we wish.
9. FURTHER REMARKS, FURTHER WORK
We have seen how permissive-nominal logic (PNL) extends first-order logic with term-formers that can bind. We have given PNL a nominal-sets based semantics and shown it sound and complete. We have considered a finite axiomatisation of arithmetic, based on a finite axiomatisation of first-order logic in PNL, and proven it correct. Finally, we have proved cut-elimination.
In most respects PNL behaves just like first-order logic. However, its ‘nominal’ constructs let it ergonomically perform many of the tasks that would require much more powerful constructs in e.g. higher-order logic.
We do not claim that PNL makes nominal terms like those used in [Urban et al. 2004; Fernández and Gabbay 2007] obsolete. The argument for permissive-nominal terms is that they are a more abstract and powerful mathematical model with which to do proofs; for we use them to ‘just quotient’ by -equivalence, and we use them to reconcile -equivalence of atoms with . But that story is entirely compatible with prevous work. For instance, though permission sets have the form () (Definition 2.7), in practice we only seem to specify restrictions like pmss and pmss—and these look like freshness environments. In the discussion of Subsection 2.7 we saw why: permission sets control capture, and we only care about controlling capture for the finitely many atoms mentioned explicitly in an axiom. Furthermore the use of shift-permutations (Definition 2.9) means that the exact choice of permission set ‘does not really matter’—more on this below. In a sense, freshness contexts live on in this paper and remain useful, as an emergent property of how we interact with a more abstract underlying mathematical model given by permissive-nominal terms.
We do not claim that PNL is the ultimate logic, whatever that means. However, we do see PNL as a significant step forward in the continuing search for logics suitable for axiomatising the systems with binding which are so common in computer science, as briefly discussed in Section 8. We hope that PNL will turn out to be a ‘sweet spot’ amongst such systems—fairly simple, yet usefully expressive and with good theoretic properties.
We will now briefly discuss some of the design decisions and design alternatives available to us in creating logics in the spirit of PNL.
Unknowns of name sort, and atoms. A swapping with unknowns, as in () where and have a name sort , is not primitive syntax in PNL. This is atoms as variables as in [Gabbay and Cheney 2004] and [Pitts 2003], as opposed to the atoms as constants approach of nominal terms [Urban et al. 2004] which is inherited by this paper.
The axioms of nominal logic [Pitts 2003, Section 5] can be copied over to endow term-formers abs and swap (see below) with the right properties; since the logic of [Pitts 2003] is already a set of axioms, there is no harm in doing this also in PNL. Alternatively, we can ‘promote’ behaviour from atoms to unknowns: Suppose a sort and a name sort Atm. Suppose sort( and pmss. Suppose a term-former abs : (Atm)[Atm]. The axiom ( abs()) ‘promotes’ atoms-abstraction, to an abstraction by unknowns of sort atom (over terms of sort ). Similarly for a term-former swap : (Atm Atm).
The question phrased in semantic terms is as follows:
— Should every inhabitant of the denotation of a name sort to be referenced in PNL syntax by an atom?
— Should every inhabitant of the semantics of name sorts, to be referenced by a closed term?
The answers to these questions matter, but not for this paper. It is not unusual (indeed, it is very common) for there to be more elements in a type than there are closed terms. Furthermore, we have proved completeness in Subsection 3.4, so any extra elements in name sorts cannot ‘make anything false’.
Yet it is reasonable to ask in future work whether we could exclude ‘non-standard atoms’ in the same way that for example we might try to exclude non-standard numbers from models of first-order theories of arithmetic. (Note that this is a general issue with a two-level syntax, and is not specific to PNL.)
We believe that this is possible. The idea is in the proof-theory for from ‘Fresh Logic’ [Gabbay 2007a]; see (Exhaust) in Figure 3, and Subsection 5.5.
Extending sorts. It would be a good idea to introduce sort-formers and polymorphism into the sorting system, so that e.g. we can conveniently axiomatise a substitution action on an infinite class of sorts. We see no difficulty in doing this—it is a definitional extension of what we already have.
Another interesting extension is to assume, for every sort , an associated name sort . This would allow us to talk about ‘the level 1 variables associated with ’ in the same way that we can already talk about ‘the level 2 variables of sort ’.
Design of permission sets. There is design freedom in the choice of permission sets. We briefly sketch some of the options.
We can have more permission sets. For instance, we can take uncountable and permission sets all countably infinite sets. We can also add finite permission sets, enabling us e.g. to reason about properties that only hold of (level 1) closed terms, or terms with a finitely bounded number of free atoms.
We can have fewer permission sets. For instance we could take permission sets to be , or for finite .
We can also have much fewer permission sets—one, to be precise. PNL would work just as well if we took as the single unique permission set. The effect of larger or smaller permission sets can then be obtained using permutations. For example if pmss( and pmss( pmss and sort( sort then the effect of can be obtained by the logically equivalent P(). Using further shift-permutations and conjugation by finite permutations, any of the permission sets of Definition 2.7 can be obtained.
Note that we never want to be a permission set. If we had that, then we would not be able to ‘choose a fresh atom’ and e.g. would be unable to -convert in if pmss(.
Taking a more abstract view, a natural generalisation of Definition 2.7 is an equivariant nominal join semi-lattice that does not contain . So specifically for sets of atoms, this means that if and are permission-sets then so are and , and is not a permission set. To illustrate how this works, note that if is a permission set and is finite then it easily follows using equivariance and sets unions that is a permission set. So to insist that is not a permission set, is really to insist that every permission set is coinfinite.
The design decision made in Definition 2.7 is simple, effective, and direct, and it allows us to express capture-avoidance conditions easily without complex ‘emulations’ involving shift.
PNL without shift. We can restrict PNL by dropping shift-permutations (but retaining permission sets as defined), yielding a logic that could be called PNL without shift. This is what was considered in the conference version of this paper [Dowek and Gabbay 2010].
This is less ergonomic, but in a certain sense it is just as powerful. It all depends on whether we want to be able to change our mind about a permission set in mid-derivation.
This is a similar issue as appears e.g. in the design of a sequent system, whether we allow weakening as an explicit sequent rule (so that we can weaken mid-derivation), or integrate weakening into the axiom rule (so we have to anticipate the other propositions needed in the sequent).
The isomorphism between pmss and pmss
Unification of permissive-nominal terms without shift was considered in [Dowek et al. 2010]. Subsequently to writing this paper, that theory was re-cast using shift [Gabbay 2012].
Note that nominal algebra satisfies an HSPA result whereas permissive-nominal algebra with shift satisfies an HSP result; details are elsewhere [Gabbay 2009; Gabbay 2012] but what is relevant to this discussion is that the extra expressivity which shift gives, can make a real, mathematically measurable, difference.
Implementing PNL. An implementation of PNL could follow the lines of a first-order theorem-prover, since the proof-rules in Figure 1 are so like those of first-order logic. The term-language would be richer and would include names and binding.
There would be many design choices, some of which we have touched on above: polymorphism in sorts; choice of permission sets (perhaps even adding variables to permission sets); whether or not to include shift; whether or not to exclude ‘non-standard’ atoms using an (Exhaust) rule like that in Figure 3 of [Gabbay 2007a]; and so on.
Another point is how much of the infinity of permission sets we should expose to the user. To discuss this further, we must draw together several strands that have run through this paper from the beginning.
At the start of this paper we introduced permission sets, which guarantee infinite supplies of fresh atoms for every unknown. This culminated in Definition 2.30 with the permissive-nominal ‘just quotient’ -equivalence, which is different from the notion of -equivalence used in nominal terms in e.g. [Urban et al. 2004; Fernández and Gabbay 2007; Gabbay and Mathijssen 2009]. In Subsection 8.2 we gave a sense in which PNL is obtained from nominal terms and nominal algebra by adding universal quantifiers while taking a limit of extending freshness contexts in the sense of nominal terms.
But then at the start of this section we noted that for any concrete derivation we only care about the finitely many atoms explicitly mentioned, thus for any concrete derivation we only care about finite freshness information after all.
So we have a choice, when implementing PNL, whether to present the user with and directly as we did in Definition 2.7, or to present a nominal terms syntax in which a (possibly but not necessarily finite) context of freshness assertions is carried and may be extended as needed (nominal algebra does this using a freshness rule (fr) [Gabbay and Mathijssen 2009]; an idea taken from [Gabbay 2007a]).
A specific disadvantage is that we would lose the permissive-nominal ‘just quotient syntax’ theory of -equivalence used in Definition 2.30.
At the moment it seems unclear how much this matters from the point of view of an implementation. After all, in an implementation we will have a specific goal with specific and (finitely many) atoms for which the user has chosen specific names. So will the user even appreciate explicit access to an infinite stock of fresh atoms? Or, will the user prefer a freshness context to be extended as needed? Note that the implementation might need fresh names when -renaming during resolution, so a resolution step might extend the freshness context with finitely but unboundedly many new names. An advantage of presenting explicitly is that these names are honestly presented to the user from the start.
As with any logic, there are many ways to present it. Yet, the underlying mathematics remains essentially the same.
Summary. PNL addresses problems of mathematical specification with names and binding. It provides a first-order logic environment which allows us to formally express the ‘informal meta-level’, complete with names and binding. As such, the most exciting potential application of PNL is as a logical foundation—as a meta-theory for mathematics—intermediate in power between first- and higher-order logic. We believe that, perhaps with some fairly modest extensions, it would make an expressive, ergonomic, and practical alternative meta-language for mechanised mathematics.
REFERENCES
Abadi, M., Cardelli, L., Curien, P.-L., and Lévy, J.-J. 1991. Explicit substitutions. Journal of Functional Programming 1, 4, 375–416.
Beeson, M. 2004. Lambda logic. In Second International Joint Conference on Automated Reasoning (IJCAR 2004). Lecture Notes in Computer Science Series, vol. 3097. Springer, 460–474.
Calvès, C. 2010. Complexity and implementation of nominal algorithms. Ph.D. thesis, King’s College London.
Calvès, C. and Fernández, M. 2008. A polynomial nominal unification algorithm. Theoretical Computer Science 403, 285–306.
Cheney, J. 2005. A simpler proof theory for nominal logic. In FoSSaCS. Lecture Notes in Computer Science Series, vol. 3441. Springer, 379–394.
Dowek, G. and Gabbay, M. J. 2010. Permissive Nominal Logic. In Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2010). ACM Press, 165–176.
Dowek, G., Gabbay, M. J., and Mulligan, D. P. 2009. Permissive Nominal Terms and their Unification. In Proceedings of the 24th Italian Conference on Computational Logic (CILC’09).
Dowek, G., Gabbay, M. J., and Mulligan, D. P. 2010. 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.
Dowek, G., Hardin, T., and Kirchner, C. 2002. Binding logic: Proofs and models. In Proceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2002). Springer, 130–144.
Dummett, M. 1977. Elements of intuitionism 1 Ed. Clarendon Press.
Farmer, W. M. 2008. The seven virtues of simple type theory. Journal of Applied Logic 3, 6, 267–286.
Fernández, M. and Gabbay, M. J. 2007. Nominal rewriting (journal version). Information and Computation 205, 6, 917–965.
Gabbay, M. 2011a. A proof-theoretic treatment of lambda-reduction with cut-elimination: lambda calculus as a logic programming language. Journal of Symbolic Logic 76, 2, 673–699.
Gabbay, M. J. 2001. A Theory of Inductive Definitions with alpha-Equivalence. Ph.D. thesis, University of Cambridge, UK.
Gabbay, M. J. 2005. A NEW calculus of contexts. In Proceedings of the 7th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming (PPDP 2005). ACM Press, 94–105.
Gabbay, M. J. 2007a. Fresh Logic. Journal of Applied Logic 5, 2, 356–387.
Gabbay, M. J. 2007b. A General Mathematics of Names. Information and Computation 205, 7, 982–1011.
Gabbay, M. J. 2009. Nominal Algebra and the HSP Theorem. Journal of Logic and Computation 19, 2, 341–367.
Gabbay, M. J. 2011b. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic 17, 2, 161–229.
Gabbay, M. J. 2011c. 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.
Gabbay, M. J. 2012. Nominal terms and nominal logics: from foundations to meta-mathematics. In Handbook of Philosophical Logic. Vol. 17. Kluwer.
Gabbay, M. J. and Cheney, J. 2004. A Sequent Calculus for Nominal Logic. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004). IEEE Computer Society, 139–148.
Gabbay, M. J. and Mathijssen, A. 2007. A Formal Calculus for Informal Equality with Binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation. Lecture Notes in Computer Science Series, vol. 4576. Springer, 162–176.
Gabbay, M. J. and Mathijssen, A. 2008a. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing 20, 4-5, 451–479.
Gabbay, M. J. and Mathijssen, A. 2008b. One-and-a-halfth-order Logic. Journal of Logic and Computation 18, 4, 521–562.
Gabbay, M. J. and Mathijssen, A. 2009. Nominal universal algebra: equational logic with names and binding. Journal of Logic and Computation 19, 6, 1455–1508.
Gabbay, M. J. and Mulligan, D. P. 2009a. Semantic nominal terms. In Proceedings of the 2nd International Workshop on the Theory and Applications of Abstraction, Substitution and Naming (TAASN 2009).
Gabbay, M. J. and Mulligan, D. P. 2009b. 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). ACM, 64–73.
Gabbay, M. J. and Pitts, A. M. 2001. A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing 13, 3–5, 341–363.
Gacek, A., Miller, D., and Nadathur, G. 2008. Combining generic judgments with recursive definitions. In Proceedings of the 23rd IEEE Symposium on Logic in Computer Science (LICS 2008). IEEE Computer Society Press, 33–44.
Levy, J. and Villaret, M. 2010. An efficient nominal unification algorithm. In Proceedings of the 21st International Conference on Rewriting Techniques and Applications (RTA 2010). Leibniz International Proceedings in Informatics (LIPIcs) Series, vol. 6. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 209–226.
Miller, D. and Tiu, A. 2003. A proof theory for generic judgments (extended abstract). In Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003). IEEE Computer Society Press, 118–127.
Nanevski, A., Pfenning, F., and Pientka, B. 2008. Contextual modal type theory. ACM Transactions on Computational Logic (TOCL) 9, 3, 1–49.
Paulson, L. C. 1990. Isabelle: the next 700 theorem provers. In Logic and Computer Science, P. Odifreddi, Ed. Academic Press, 361–386.
Pitts, A. M. 2003. Nominal logic, a first order theory of names and binding. Information and Computation 186, 2, 165–193.
Shoenfield, J. 1967. Mathematical Logic. Addison-Wesley.
Tiu, A. 2007. A logic for reasoning about generic judgments. Electronic Notes in Theoretical Computer Science 174, 5, 3–18.
Urban, C., Pitts, A. M., and Gabbay, M. J. 2004. Nominal Unification. Theoretical Computer Science 323, 1–3, 473–497.
Notes
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax 1 (212) 869-0481, or permissions@acm.org. c YYYY ACM 1529-3785/YYYY/01-ARTA $10.00 DOI 10.1145/0000000.0000000 http://doi.acm.org/10.1145/0000000.0000000
1The language of terms is significantly different, though; see Definition 2.13. ↩
2Via this intuition, permission sets correspond to the freshness constraints # of [Urban et al. 2004]. For the reader familiar with freshness constraints, another way to view permission sets is as fixing a single global freshness context with ‘enough’ freshnesses (the germ of this was already in [Gabbay 2005]) where ‘enough’ means that for any term, we can always pick an atom not free in that term. However the implications of doing this go beyond a syntactic tweak to nominal terms; permission sets are what make it possible for us to reconcile level 2 quantification with level 1 atoms-abstraction . ↩
3Remember that we quotient raw terms by -equivalence to obtain terms so this is now a real equality. ↩
4In this paper equivariance surfaces in a variety of technical features of PNL: the in (Ax); the way permutations distribute into terms in Definition 2.17; Definition 3.16 and how it is used in Definition 3.18; Lemma 3.22; and more. In fact, equivariance is broad and useful phenomenon. The interested reader is referred to [Gabbay and Pitts 2001, Lemma 4.7] and [Gabbay 2011b, Subsection 4.2], where it is treated in full generality. See also [Gabbay 2011c, Lemma 5.5], where the conditions on free atoms and support in Definitions 2.32 and 3.19 are also exhibited as forms of equivariance. ↩
5If permission sets were finite, or if all permutations were finite, then we could not do this in general. ↩
6supp need not necessarily be a permission set. For instance, supp(
7We favour the word ‘interpretation’ for assigning a denotational interpretation to a logic, and ‘model’ for checking whether the interpretation makes a theory (a set of axioms). These senses overlap, in that an interpretation is a model for the empty theory. In practice, we tend to use whichever word seems most appropriate in context. ↩
8Missing from this is a proof that EQU SUB FOL soundly and completely interprets first-order logic. We believe this to be true and the proof should be an elementary simplification of the more involved case for arithmetic—but it is not worth writing out here. Arithmetic is (in first-order logic) axiomatised using a schema. We use PNL to express them finitely; see e.g. the in (PInd) of Figure 6 which models the ‘every ’ in (pind) in Figure 7. Finite first-order logic theories (including the empty theory) are unproblematic. In these proofs, soundness and completeness are only a means to the end of demonstrating how we can axiomatise finitely in a nominal first-order logic PNL, structures that without names and binding would require infinite axiom schemes or higher orders. ↩