HTML reading edition · 43 source pages · Open the source PDF

From nominal sets binding to functions and λ-abstraction: connecting the logic of permutation models with the logic of functions

Gilles Dowek

www-roc.inria.fr/who/Gilles.Dowek

Murdoch J. Gabbay

gabbay.org.uk

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 ∀ : (ι→o)→o [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([a]r) to λa.r and app(r′, r) to r′r and var(a) to a. 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:

λx.(tx) = t if x is not free in t

Here is a PNL axiom for η-equivalence, written out formally:

∀Z.(λa.(Za) = Z) (a ∉pmss(Z))

(See [GM10] for a detailed study of this axiom in a nominal context.)

a is an atom and corresponds to the object-level variable x; a is not a PNL variable but it represents a variable of the object level system being axiomatised. Z is an unknown and correspond to the meta-level variable t; Z 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 t is typically taken to range over terms, Z 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 a ∉ pmss(Z) is a typing condition in PNL. The types, or permission sets as we call them, restrict the support of denotations associated to Z by a valuation. They correspond to freshness side-conditions in nominal terms from [UPG04] and to informal freshness conditions of the form ‘x not free in t’ 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 (λa.r)r′ to r[a↦→r′]. Then axioms for β-equivalence are:

∀Y. a[a↦→Y ] = Y∀Z, X. Z[a↦→X] = Z (a ∉pmss(Z))∀X′, X, Y. (X′X)[a↦→Y ] = (X′[a↦→Y ])(X[a↦→Y ]) ∀X, Z. (λa.X)[b↦→Z] = λa.(X[b↦→Z]) (a ∉pmss(Z))∀X. X[a↦→a] = X

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, a and b cannot be equal because they are distinct atoms, and atoms are data, not variables (a is a, and b is b, 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 ∀a.P(a) to ∀b.P(b) 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 D ⊢r : A 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

Definition 2.1

A sort-signature is a pair (A, B) of name and base sorts. ν will range over name sorts; τ will range over base sorts. A sort language is then defined by

α ::= ν | (α, . . . , α) | [ν]α | τ.
Remark 2.2

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.

Definition 2.3

A term-signature over a sort-signature (A, B) is a tuple (F, P, ar, X) where:

• F and P 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 ∈F a term-former arity (α)τ and to each P ∈P a proposition-former arity α, where α and τ are in the sort-language determined by (A, B). We will write ((α1, . . . , αn))τ just as (α1, . . . , αn)τ.

• X is a set of unknowns X, each of which has a sort sort(X) and a permission set pmss(X), such that for each sort α and permission set S the set {X ∈X | sort(X) = α, pmss(X) = S} is countably infinite. X, Y, Z will range over distinct unknowns.

A signature S is then a tuple (A, B, F, P, ar, X).

We write f : (α)τ for ar(f) = (α)τ and similarly we write P : α for ar(P) = α.

Example 2.4

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 ι.

Definition 2.5

For each ν fix a disjoint countably infinite set of atoms Aν, and an arbitrary bijection fν between Aν and the integers Z = {0, -1, 1, -2, 2, . . .}. Write

A< ν = {fν(i) | i < 0} A> ν = {fν(i) | i ≥0}.

Finally, write

A< =⋃A< νA> =⋃A> νA =⋃Aν

a, b, c, . . . will range over distinct atoms (we call this the permutative convention).

A permission set has the form (A< ∪A) \B where A ⊆A> and B ⊆A< are finite (and a permission set may be finitely represented by the pair (A, B)). S, T, and U will range over permissions sets.

The use of A< and A> ensures that permission sets are infinite and also co-infinite (their complement is also infinite).

Definition 2.6

A permutation is a bijection π on A such that a ∈Aν ⇔ π(a) ∈Aν and nontriv(π) = {a | π(a) ≠ a} is finite. Write P for the set of permutations. Given a, b ∈Aν let a swapping (a b) be the bijection on atoms that maps a to b, b to a, and all other c to themselves.

Notation 2.7

We use the following notation:

• Write π ◦π′ for functional composition, so (π ◦π′)(a) = π(π′(a))).

• Write id for the identity permutation, so id(a) = a always.

• Write π-1 for inverse, so π ◦π-1 = id.

Definition 2.8

For each signature S, define terms and propositions over S by:

(a ∈Aν) a : νr1 : α1 . . . rn : αn(r1, . . . , rn) : (α1, . . . , αn)r : α (ar(f) = (α)τ) f(r) : τr : α (a ∈Aν) [a]r : [ν]α(sort(X) = α) π·X : α⊥prop.φ prop. ψ prop. φ ⇒ψ prop.r : α (ar(P) = α) P(r) prop.φ prop. ∀X.φ prop.
Example 2.9

Continuing Example 2.4, we have the following terms and propositions:

• var(a) : ι where a ∈Aν.

• [a]X : [ν]ι where a ∈Aν and sort(X) = ι, and lam([a]X) : ι.

• ∀X.P(lam([a]X), X) 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.

Definition 2.10

Define a (level 1) permutation action on syntax by:

π·a = π(a) π·(r1, . . . , rn) = (π·r1, . . . , π·rn)π·[a]r = [π(a)]π·r π·(π′·X) = (π◦π′)·Xπ·f(r) = f(π·r) π·⊥= ⊥ π·(φ ⇒ψ) = (π·φ) ⇒(π·ψ)π·P(r) = P(π·r) π·(∀X.φ) = ∀X.π·φ
Definition 2.11

Let Π range over sort- and permission-set-preserving bijections on unknowns (so sort(Π(X))=sort(X) and pmss(Π(X))=pmss(X)) such that {X | Π(X) ≠ X} 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:

Π·a = a Π·(r1, . . . , rn) = (Π·r1, . . . , Π·rn)Π·[a]r = [a]Π·r Π·(π·X) = π·(Π(X))Π·f(r) = f(Π·r) Π·⊥= ⊥ Π·(φ ⇒ψ) = (Π·φ) ⇒(Π·ψ)Π·P(r) = P(Π·r) Π·(∀X.φ) = ∀Π(X).Π·φ
Definition 2.12

Suppose A is a set of atoms and π is a level 1 permutation. Suppose U is a set of unknowns and Π is a level 2 permutation. Define π·A and Π·U by

π·A = {π(a) | a ∈A} and Π·U = {Π(X) | X ∈U}.

This is the standard pointwise permutation action on sets.

Definition 2.13

Define free atoms fa(r) and fa(φ) by:

fa(π·X) = π·pmss(X) fa([a]r) = fa(r) \ {a} fa(a) = {a}fa(f(r)) = fa(r) fa((r1, . . . , rn)) = ⋃ fa(ri)fa(⊥) = ∅ fa(φ ⇒ψ) = fa(φ) ∪fa(ψ)fa(P(r)) = fa(r) fa(∀X.φ) = fa(φ)

Define free unknowns fV (r) and fV (φ) by:

fV (a) = ∅ fV (π·X) = {X} fV (f(r)) = fV (r)fV ([a]r) = fV (r) fV ((r1, . . . , rn)) = ⋃ fV (ri)fV (⊥) = ∅ fV (φ ⇒ψ) = fV (φ) ∪fV (ψ)fV (P(r)) = fV (r) fV (∀X.φ) = fV (φ) \ {X}
Lemma 2.14

fa(π·r) = π·fa(r) and fa(π·φ) = π·fa(φ).

Also, fV (Π·r) = Π·fV (r) and fV (Π·φ) = Π·fV (φ).

Proof

By routine inductions on r.End of proof

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).

Definition 2.15

Call a relation R on terms and on propositions a congruence when it is closed under the following rules:6

ri R si1 ≤i ≤n (r1, . . . , rn) R (s1, . . . , sn)r R s (f : (α)τ, r, s : α) f(r) R f(s)r R s [a]r R [a]sφ R φ′ψ R ψ′φ ⇒ψ R φ′ ⇒ψ′r R s (P : α, r, s : α) P(r) R P(s)φ R φ′∀X.φ R ∀X.φ′
Definition 2.16

Write (a b) for the (level 1) swapping permutation which maps a to b and b to a and all other c to themselves. Similarly, provided sort(X) = sort(Y) and pmss(X) = pmss(Y ), write (X Y) 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:

(a, b ∉fa(r)) (b a)·r =α r(X, Y ∉fV (φ)) (Y X)·φ =α φ
Example 2.17

We α-convert X and a in ∀X.P([a]X).

Let sort(Y ) = sort(X) and pmss(Y ) = pmss(X). Suppose b ∉ pmss(X). Using (a b) and (X Y) we deduce:

∀X.P([a]X)(a b)=α∀X.P([b](b a)·X)(X Y )=α∀Y.P([b](b a)·Y ).

It is routine to convert this sketch into a full derivation-tree.

Definition 2.18

For each signature S, we take terms and propositions quotiented by α-equivalence.

2.4. Substitution

Definition 2.19

A (level 2) substitution θ is a function from unknowns to terms such that:

• For all X, θ(X) : sort(X) and fa(θ(X)) ⊆ pmss(X).

• θ(X) = id·X for all but finitely many X.

θ will range over substitutions.

Definition 2.20

Define nontriv(θ) by:

nontriv(θ) = {X | θ(X)≠id·X or X∈fV (θ(Y)) for some Y }

nontriv(θ) is unknowns that can be produced or consumed by θ, other than in the trivial manner that θ(X) = id·X.

Definition 2.21

Define a substitution action by:

aθ = a (r1, . . . , rn)θ = (r1θ, . . . , rnθ)([a]r)θ = [a](rθ) (π·X)θ = π·θ(X)f(r)θ = f(rθ) ⊥θ = ⊥ (φ ⇒ψ)θ = (φθ) ⇒ψθ(P(r))θ = P(rθ) (∀X.φ)θ = ∀X.(φθ) (X ∉nontriv(θ))
Remark 2.22

Level 2 substitution rθ is capturing for level 1 abstraction [a]-. For example if θ(X) = a then ([a]X)θ = [a]a. This is the behaviour displayed by the informal meta-level when we write “take t to be x in λx.t”.

2.5. Sequents and derivability

Definition 2.23

Φ 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 (φ) | φ ∈ Φ} ∪⋃{fV (ψ) | ψ ∈ Ψ}.

(Ax)Φ, φ ⊢π·φ, Ψ(⊥L)Φ, ⊥⊢ΨΦ ⊢φ, Ψ Φ, ψ ⊢Ψ(⇒L)Φ, φ ⇒ψ ⊢ΨΦ, φ ⊢ψ, Ψ(⇒R)Φ ⊢φ ⇒ψ, ΨΦ, φ[X::=r] ⊢Ψ (fa(r)⊆pmss(X), r:sort(X)) (∀L) Φ, ∀X.φ ⊢ΨΦ ⊢φ, Ψ (X ∉fV (Φ, Ψ))(∀R)Φ ⊢∀X.φ, Ψ
Figure 1: Sequent derivation rules of full Permissive-Nominal Logic
(Axπ)Φ, φ ⊢π φ, Ψ(⊥L)Φ, ⊥⊢π ΨΦ ⊢π φ, Ψ Φ, ψ ⊢π Ψ(⇒L)Φ, φ ⇒ψ ⊢π ΨΦ, φ ⊢π ψ, Ψ(⇒R)Φ ⊢π φ ⇒ψ, ΨΦ, φ[X::=r] ⊢π Ψ (fa(r)⊆pmss(X), r:sort(X)) (∀L) Φ, ∀X.φ ⊢π ΨΦ ⊢π φ, Ψ (X ∉fV (Φ, Ψ))(∀R)Φ ⊢π ∀X.φ, Ψ
Figure 2: Sequent derivation rules of restricted Permissive-Nominal Logic
Definition 2.24 (Derivable sequents).

Define the derivable sequents of full PNL and restricted PNL by the rules in Figures 1 and 2 respectively.

The sole difference between Figures 1 and 2 is in the axiom rule, and is highlighted with a light blue rectangle.

Notation 2.25

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 n! permutation instances of each r or φ, where n is some notion of the number of atoms in r 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 n! 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 a, b : ν. Then the difference in the entailment relations of PNL and restricted PNL can be summed up as follows:

• P(a) ⊢ P(a) and P(a) ⊢π P(a).

• P(a) ⊢ P(b) but [crossed out (restricted PNL): P(a) ⊢π P(b)].

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 n! 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.

Definition 3.1

A HOL signature is a set D of base types, which includes a distinguished base type of truth-values o ∈D. µ will range over base types. A type-language is defined by

β ::= µ | (β, . . . , β) | β →β.

It is not necessary to include products (β1, . . . , βn), but for the purposes of translating PNL into HOL doing this is convenient.

Definition 3.2

A term-signature over a HOL signature D is a tuple (G, type) where:

• G is a set of constants, which must contain elements ⊥, ⇒, and ∀β for every type β.

• type assigns to each g ∈G a type β in the type-language determined by D, such that type(⊥) = o, type(⇒) = o →o →o, and type(∀β) = (β →o) →o.7

A signature T is then a tuple (D, G, type).

We write g : β for type(g) = β.

Definition 3.3

For each signature T = (D, G, type) and each type β over D fix a countably infinite set of variables of that type.

X, Y, Z will range over distinct HOL variables.8 Write type(X) for the type of X.

Definition 3.4

For each signature T define HOL terms over T by

t ::= X | λX.t | tt | (t, . . . , t) | g

and a typing relation by:

t : β (type(X)=β′) λX.t : β′→βt′ : β′t : β′→β t′t : βt1 : β1 . . . tn : βn(t1, . . . , tn) : (β1, . . . , βn)(type(g)=µ) g : µ

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:

Definition 3.5

A permutation of HOL variables is a bijection ϖ such that nontriv(ϖ) = {X | ϖ(X) ≠ X} is finite. Give HOL terms a permutation action ϖ·t defined by:

ϖ·X =ϖ(X) ϖ·λX.t=λϖ(X).ϖ·t ϖ·(t′t)=(ϖ·t′)(ϖ·t)ϖ·(t1, . . . , tn)=(ϖ·t1, . . . , ϖ·tn) ϖ·g=g

Free variables are defined by:

fv(X)={X} fv(λX.t)=fv(t) \ {X} fv(t′t)=fv(t′) ∪fv(t)fv((t1, . . . , tn))=⋃i fv(ti) fv(g)=∅

Call a relation R on HOL terms a congruence when it is closed under the following rules:

t R u λX.t R λX.ut′ R u′t R u t′t R u′uti R ui(1 ≤i ≤n) (t1, . . . , tn) R (u1, . . . , un)

Define α-equivalence to be the least congruence that is an equivalence relation and is such that:

(X, Y ∉fv(t)) (Y X)·t =α t

We quotient terms by α-equivalence and define capture-avoiding substitution t[X::=u] as usual.

(hAx)Ξ, ξ ⊢λ ξ, χ(h⊥L)Ξ, ⊥⊢λ χΞ ⊢λ ξ, χΞ, χ ⊢λ χ(h⇒L)Ξ, ξ ⇒χ ⊢λ χΞ, ξ ⊢λ χ, χ(h⇒R)Ξ ⊢λ ξ ⇒χ, χΞ, ξ[X::=t] ⊢λ χ(t:type(X))(h∀L)Ξ, ∀X.ξ ⊢λ χΞ ⊢λ ξ, χ(X ∉fV (Ξ,χ))(h∀R)Ξ ⊢λ ∀X.ξ, χ
Figure 3: Sequent derivation rules of Higher-Order Logic
Definition 3.6

We write t : β for t is a term and has type β. We call t typable when t : β for some type β.

We call a term a HOL proposition when it has type o. ξ and χ will range over HOL propositions.

Definition 3.7

Ξ and χ will range over sets of HOL propositions. We may write ξ, Ξ and Ξ, ξ as shorthand for {ξ} ∪ Ξ.

Write fV (Ξ,χ) = ⋃{fV (ξ) | ξ ∈ Ξ} ∪⋃{fV (χ) | χ ∈χ}. A sequent is a pair Ξ ⊢λ χ.

Definition 3.8 (Derivable sequents).

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 S 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 S to a HOL signature TS. First, we set up some notation:

Notation 4.1

Let D range over finite lists of distinct atoms.

• Write a ∈D when a occurs in D.

• Write D′ ⊆D when every element in D′ occurs in D (disregarding order). Similarly if S is a set of atoms write D ⊆S when every element in D occurs in S.

• If S is a set of atoms write D ∩S for the list obtained by removing from D just those atoms not in S. Also write DX as shorthand for D ∩ pmss(X).

• Write π·D for the list obtained by applying π pointwise to the elements of D in order.

• Write D, a for the list obtained by appending a; when we write this we include an assumption that a ∉D.

• Write λD.t for λd1. . . . λdn.t where D = [d1, . . . , dn].

⌊a⌋D = a ⌊(r1, . . . , rn)⌋D = (⌊r1⌋D, . . . , ⌊rn⌋D) ⌊f(r)⌋D = gf ⌊r⌋D⌊[a]r⌋D = λa.⌊r⌋D⌊π·X⌋D = XDπ·DX⌊⊥⌋D = ⊥ ⌊φ ⇒ψ⌋D = ⇒⌊φ⌋D⌊ψ⌋D⌊P(r)⌋D = gP ⌊r⌋D⌊∀X.φ⌋D = ∀λX.⌊φ⌋D
Figure 4: Translation from PNL to HOL
Definition 4.2

From a PNL signature S determine a HOL signature TS by the following specification:

• For every atoms-sort ν in S assume a HOL base type µν.

• For every base sort τ assume a HOL type µτ.

Translate sorts in S to types in TS as follows:

⌊ν⌋= µν⌊τ⌋= µτ⌊(α1, . . . , αn)⌋= (⌊α1⌋, · · · , ⌊αn⌋)⌊[ν]α⌋= ν →⌊α⌋

• For every term-former f : (α)τ assume a HOL constant gf : ⌊α⌋→τ.

• For every proposition-former P : α assume a HOL constant gP: ⌊α⌋→o.

• For every atom a : ν assume a HOL variable a : ν.
It is convenient to assume this correspondence is a literal identity; i.e. that Aν 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 X : α and list D assume a distinct HOL variable XD that is not an atom9 of type νDX →⌊α⌋ where νDX is the sorts of the atoms in DX, in order.

Definition 4.3

Given a list D translate PNL terms and propositions in S to HOL terms and propositions in TS (Definition 4.2) by the rules in Figure 4. (The notation π·DX is defined in Notation 4.1.)

Example 4.4

Suppose DX (Notation 4.1) is the list [a] and write X for XD. Assume a proposition-former equal of appropriate arity. Then:

⌊id·X⌋D = Xa ⌊(b a)·X⌋D = Xb ⌊[a]id·X⌋D = λa.(Xa) ⌊[b](b a)·X⌋D = λb.(Xb)⌊∀X.equal([a]X, [b](b a)·X)⌋D = ∀λX.(equal(λa.(Xa))(λb.(Xb)))

Assuming appropriate axioms for equal, we would expect this to be true. Now assume DY is the list [a, b] and write Y for YDY . Then:

⌊id·Y ⌋D = Y ab ⌊(b a)·Y ⌋D = Y ba ⌊[a]id·Y ⌋D = λa.(Y ab) ⌊[b](b a)·Y ⌋D = λb.(Y ba)⌊∀Y.equal([a]Y, [b](b a)·Y )⌋D = ∀λY.(equal(λa.(Y ab))(λb.(Y ba)))

We would expect this to be false. What has changed with respect to the previous case, is that b is fresh for X but not for Y .

Lemma 4.5

• Suppose a is an atom. Then if a ∈ fv(⌊r⌋D) then a ∈ fa(r).

• ⌊π·r⌋D = π·⌊r⌋D (for π on the right-hand side considered as a permutation of HOL variables).

As a corollary, the translation ⌊r⌋D is well-defined. That is, if r and s are α-equivalent then ⌊r⌋D = ⌊s⌋D.

Proof

By routine inductions on r. The proof that fa(π·X) ⊆ fv(⌊π·X⌋D) uses the assumption that DX ⊆ pmss(X). The corollary follows; for more details see [DGM10, Section 8].End of proof

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].

Definition 4.6

Define capture typings D ⊢r : A and D ⊢φ : A inductively by the rules in Figure 5. Here D ranges over finite lists of distinct atoms as described in Notation 4.1, and A ranges over finite sets of atoms.

If A = ∅ then we may omit the ‘:A’ and write just D ⊢r and D ⊢φ. Write D ⊢ Ψ when D ⊢ψ for every ψ ∈ Ψ.

Remark 4.7

The interesting case in Figure 5 is the rule for π·X. This ensures that D is large enough to record all the important atoms in π or abstracted further up in the term—that is, those permitted in X—so that we do not lose information when we form ⌊π·X⌋D = Xπ·DX. This is made formal in Proposition 4.8, which is Theorems 8.12 and 8.14 of [DGM10]:

Proposition 4.8

• If D ⊢r and D ⊢s then ⌊r⌋D = ⌊s⌋D implies r = s (note that = denotes

α-equality, because we quotiented terms by this relation), and similarly for φ and ψ.

• If D ⊬r then there exists s such that ⌊r⌋D = ⌊s⌋D yet r ≠ s, and similarly for φ.

Definition 4.3 maps PNL terms and predicates to typable HOL terms:

Proposition 4.9

If r : α then for any D, ⌊r⌋D : ⌊α⌋, and ⌊φ⌋D : o.

Proof

By inductions on r and φ.

• The case a ∈Aν. a : ν by definition.

• The case [a]r where a ∈Aν. By inductive hypothesis ⌊r⌋D : β for some type β. It follows that ⌊[a]r⌋D = λa.⌊r⌋D : ν →β.

• The case π·X. Suppose D ⊢π·X. It is routine to check that XΓπ·DX : ⌊sort(X)⌋.End of proof

D ⊢a : AD ⊢r : A D ⊢f(r) : AD ⊢r : A, a D ⊢[a]r : AD ⊢ri : A (1≤i≤n) D ⊢(r1, . . . , rn) : A((nontriv(π) ∪A) ∩pmss(X) ⊆D) D ⊢π·X : AD ⊢r : A D ⊢P(r) : AD ⊢φ : A D ⊢ψ : A D ⊢φ ⇒ψ : AD ⊢⊥: AD ⊢φ : A D ⊢∀X.φ : A
Figure 5: Capture typing

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 Γ:

Definition 4.10

Define a substitution ⟦Γ′↦→Γ⟧ by:

⟦Γ′↦→Γ⟧(XΓ′) = λD′ X.(XΓDX)⟦Γ′↦→Γ⟧(Y ) = Y all other Y
Theorem 4.11

If D′ ⊢r : A then ⌊r⌋D =αβ ⌊r⌋D′⟦D′↦→D⟧.

Similarly, if D′ ⊢φ : A then ⌊φ⌋D =αβ ⌊φ⌋D′⟦D′↦→D⟧.

Proof

By inductions on r and φ. We consider a selection of cases:

• The case π·X. We reason as follows:

⌊π·X⌋D′⟦D′↦→D⟧ = (XD′π·D′ X)⟦D′↦→D⟧ Definition 4.3= (λD′ X.(XDDX))π·D′ XDefinition 4.10= XDπ·DXnontriv(π) ∩pmss(X) ⊆D′ X

• The case [a]r. We reason as follows:

⌊[a]r⌋D′⟦D′↦→D⟧ = (λa.⌊r⌋D′)⟦D′↦→D⟧ Definition 4.3= λa.(⌊r⌋D′⟦D′↦→D⟧) taking a ∉D, D′= λa.(⌊r⌋D) ind. hyp.= ⌊λa.r⌋DDefinition 4.3

• The case ∀X.φ. We reason as follows:

⌊∀X.φ⌋D′⟦D′↦→D⟧ = (∀λX.⌊φ⌋D′)⟦D′↦→D⟧ Definition 4.3= ∀λX.(⌊φ⌋D′⟦D′↦→D⟧) fact= ∀λX.⌊φ⌋Dind. hyp.= ⌊∀X.φ⌋DDefinition 4.3End of proof

4.4. Soundness of the translation

Recall that HOL terms have a permutation action π·t given by considering π as a permutation on HOL variables and using Definition 3.5. Then:

Lemma 4.12

If nontriv(π) ∩ fv(t) ⊆D then (λD.t)π·D =αβ π·t (see Notation 4.1).

Proof

A fact of αβ-conversion [DGM10, Lemma 9.2].End of proof

Definition 4.13

Write r′: X when r′: sort(X) and fa(r′) ⊆ pmss(X).

Lemma 4.14

Suppose D ⊢r and D ⊢φ. Suppose r′: X. Then:

• ⌊r[X::=r′]⌋D =αβ ⌊r⌋D[X::=λDX.⌊r′⌋D].
• ⌊φ[X::=r′]⌋D =αβ ⌊φ⌋D[X::=λDX.⌊r′⌋D].
Proof

By routine inductions on r and φ. We sketch two cases:

• The case (π·X)[X::=r′]. We must prove that

⌊π·r′⌋D =αβ(λDX.⌊r′⌋D)π·DX.

This follows by Lemmas 4.5 and 4.12.

• The case P(r)[X::=r′]. We must prove that

⌊P(r[X::=r′])⌋D =αβ gP(⌊r⌋D)[X::=λDX.⌊r′⌋D].

This follows directly from the first part.End of proof

Proposition 4.15

Suppose D ⊢φ and D ⊢r′: X. Then ⌊∀X.φ⌋D ⊢λ ⌊φ[X::=r′]⌋D.

Proof

Using Lemma 4.14 and (h∀L) from Figure 3.End of proof

Theorem 4.16

The interpretation is sound: if Φ ⊢π Ψ and D ⊢ Φ and D ⊢ Ψ then ⌊Φ⌋D ⊢λ ⌊Ψ⌋D.

Proof

Choose D′ such that D′ ⊢ Ψ′ and D′ ⊢ Φ′ for every sequent Ψ′ ⊢ Φ′ appearing in Π—it is not hard to verify that some such D′ must exist.

It is routine to verify by induction on Π that ⌊Φ′⌋D′ ⊢λ ⌊Ψ′⌋D′ is derivable; the case of (∀R) uses Proposition 4.15. So in particular ⌊Φ⌋D′ ⊢λ ⌊Ψ′⌋D.

It follows, applying the substitution ⟦D′↦→D⟧ to both sides and using Theorem 4.11, that ⌊Φ⌋D ⊢λ ⌊Ψ⌋D.End of proof

Lemma 4.17

The interpretation for full PNL (Figure 1, with the stronger axiom rule) would not be sound. That is, there exist Φ and Ψ and D such that D ⊢ Φ, D ⊢ Ψ, and Φ ⊢ Ψ, but ⌊Φ⌋D ⊬λ ⌊Ψ⌋D.

Proof

Consider a name sort ν and a unary predicate P : ν. Then P(a) ⊢ P(b) in full PNL, but it is not the case that gPa ⊢ gPb in HOL.End of proof

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 [a::=b] (instead of a typical permutation (a b)). 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 ⌊[a]r⌋D = λa.⌊r⌋D in Definition 4.3.

In PNL models, an abstraction [a]r is modelled as Gabbay-Pitts atoms-abstraction [a]x, a sets-based construction from [GP01] (Definition 5.26, in this paper). This is constructed like a pair, from a and x, but destructed like a partial function the graph of which is evident in Definition 5.26. It is defined for fresh b but not for b ∈ supp(x) \ {a}.

When we translate [a]r to HOL we interpret [a]r as a function using λ-abstraction. This suggests of our models that we translate a partial function [a]x to a total function. But then we have to give meaning to [a]x applied to b where b 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

Definition 5.1

Suppose ρ is a map from A to A. Define dom(ρ) and img(ρ) by

dom(ρ) = {a | ρ(a) ≠ a} and img(ρ) = {ρ(a) | a ∈dom(ρ)}.

Echoing Definition 2.6, a renaming is a map ρ from A to A such that a ∈Aν ⇔ ρ(a) ∈Aν and nontriv(ρ) = dom(ρ) ∪ img(ρ) is finite. Write R for the set of renamings.

For a, b ∈Aν let an atomic renaming [a::=b] map a to b, b to b, and other c to themselves.

ρ will range over renamings.

Definition 5.2

• A permutation set is a pair X⟳= (|X⟳|, ·) of an underlying set |X⟳| and a permutation action (P × |X⟳|) →|X⟳| which is a group action; write it infix.

(So id·x = x and π·(π′·x) = (π ◦π′)·x.)

• A renaming set is a pair X⇒= (|X⇒|, ·) of an underlying set |X⇒| and a renaming action (R × |X⇒|) →|X⇒| which is a monoid action; write it infix.

(So id·x = x and ρ•(ρ′ •x) = (ρ ◦ρ′)•x.)
Definition 5.3

• Suppose X⟳ is a permutation set. Say that A ⊆A supports x ∈|X⟳|

when for all π, π′ ∈P, if ∀a ∈A.π(a) = π′(a) then π·x = π′·x.

• Suppose X⇒ is a renaming set. Say that A ⊆A supports x ∈|X⇒| when for all ρ, ρ′ ∈P, if ∀a ∈A.ρ(a) = ρ′(a) then ρ•x = ρ′ •x.

Lemma 5.4

If x ∈|X⟳|/|X⇒| 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 x. We call this the support of x when it exists, and write it supp(x).

Definition 5.5

• Call x ∈|X⟳|/|X⇒| supported when supp(x) exists.

• Call X⟳/X⇒ supported when every element x ∈|X⟳|/|X⇒| is supported.

Lemma 5.6

• If x ∈|X⟳| then supp(π·x) = π·supp(x).

• If x ∈|X⇒| then supp(ρ•x) ⊆ρ•supp(x). As a corollary, if ρ is injective on supp(x) then supp(ρ•x) = ρ•supp(x).

Proof

By routine calculations using the group/monoid action.End of proof

Example 5.7

The reverse subset inclusion in Lemma 5.6 would not work. For instance, consider A × A ∪{∗} with the ‘exploding’ renaming action such that:

• ρ(∗) = ∗.

• ρ•(a, a) = (ρ(a), ρ(a)).

• ρ•(a, b) = (ρ(a), ρ(b)) if ρ(a) ≠ ρ(b).10

• ρ•(a, b) = ∗ if ρ(a) = ρ(b).

Then supp([a::=b]•(a, b)) = ∅⊊ {a} = [a::=b]•supp((a, b)).

5.1.2. Equivariant elements and maps

Definition 5.8

Call an element x in |X⟳|/|X⇒| equivariant when supp(x) = ∅.

x is equivariant when π·x = x for all π, or ρ•x = x for all ρ, respectively.

Definition 5.9

• Call a function F ∈|X⟳| →|Y⟳| equivariant when

∀π∈P.∀x∈|X⟳|.F(π·x) = π·F(x).

• Call a function G ∈|X⇒| →|Y⇒| equivariant when

∀ρ∈R.∀x∈|X⇒|.G(ρ•x) = ρ•G(x).

F and G will range over equivariant functions between pairs of permutation and renaming sets respectively.

Lemma 5.10

1. Suppose F ∈|X⟳| →|Y⟳| is equivariant. Then supp(F(x)) ⊆ supp(x) for every x ∈|X⟳|.

2. Suppose G ∈|X⇒| →|Y⇒| is equivariant. Then supp(G(x)) ⊆ supp(x) for every x ∈ |X⇒|.

Proof

We consider only the second part. Suppose S supports x so that for all ρ and ρ′, if ∀a ∈S.ρ(a) = ρ′(a) then ρ•x = ρ′ •x. The result follows if we note that ρ•G(x) = G(ρ•x) and ρ′ •G(x) = G(ρ′ •x).End of proof

Definition 5.11

• 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.

Definition 5.12

• Suppose X⟳, Y⟳∈ PmsPrm. Suppose f ∈|X⟳| →|Y⟳| (f is not necessarily equivariant). Call f supported when there exists a permission set Sf ⊆A such that for every x ∈|X⟳| and permutation π ∈P, if nontriv(π) ∩Sf = ∅ then

π •(f(x)) = f(π •x).

• Suppose X⇒, Y⇒∈ PmsRen. Suppose f ∈|X⇒| →|Y⇒| (f is not necessarily equivariant). Call f supported when there exists a permission set Sf ⊆A such that for every x ∈|X⇒| and renaming ρ ∈R, if dom(ρ) ∩Sf = ∅ then

ρ•(f(x)) = f(ρ•x).
Remark 5.13

Definition 5.12 uses a word ‘supported’ for f, suggestive of Definition 5.3, even though f has no permutation/renaming action. It will have a permutation/renaming action (Remark 5.14 and Definition 5.17), and then the terminologies will coincide (see Lemma 5.21).

Remark 5.14

It is a fact that PmsPrm is cartesian closed and functions have the conjugation action

(π·f)(x) = π·(f(π-1·x)).

and f is supported in the sense of Definition 5.12 if and only if it is supported as an element of |X⟳| →|Y⟳| 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 π·f(x) = (π·f)(π·x).

Lemma 5.15

If f is supported then supp(f(x)) ⊆Sf ∪ supp(x) for every x ∈|X⇒|.

Proof

By contradiction. Suppose there exists a ∈ supp(f(x)) \ (Sf ∪ supp(x)). Choose b fresh (so b ∉ supp(f(x))∪Sf ∪supp(x)). Then (b a)•(f(x)) = f((b a)•x) since a, b ∉Sf and f((b a)•x) = f(x) since b, a ∉ supp(x). It follows by Lemma 5.6 that (b a)•supp(f(x)) = supp(f(x)), which is impossible.End of proof

Definition 5.16

Suppose S ⊆A is a permission set and A ⊆A is finite. Call ρ1 and ρ2 a freshening pair of renamings for A with respect to S when:

• dom(ρ1) = A and dom(ρ2) = img(ρ1).

• (ρ2 ◦ρ1)(a) = a for all a ∈A.

• dom(ρ2) ∩ (S ∪A) = ∅.

In words, ρ1 maps the atoms in A to be outside S (and A), and ρ2 is an ‘inverse’ to ρ1 that puts them back.

5.2.2. Renaming action

Definition 5.17

(We continue the notation of Definition 5.12.) If f is supported then define ρ•f by

(ρ•f)(x) = (ρ2 ◦ρ)•f(ρ1 •x)

for some/any freshening pair of renamings ρ1 and ρ2 for nontriv(ρ) (which is finite), with respect to supp(x) ∪Sf.

Lemma 5.18

Definition 5.17 is well-defined. That is, it does not matter which freshening pair of renamings we choose.

Proof

Consider two freshening pairs of renamings ρ1, ρ2 and ρ′ 1, ρ′ 2.

Let ρ′′ 1 map img(ρ1) to img(ρ′ 1) and ρ′′ 2 map dom(ρ′ 2) = img(ρ′ 1) to dom(ρ2) = img(ρ1) in such a way that

• ρ′ 1(a) = (ρ′′ 1 ◦ρ1)(a) for all a ∈ dom(ρ′ 1),

• ρ′ 2(a) = (ρ2 ◦ρ′′ 2)(a) for all a ∈ dom(ρ′ 2), and

• nontriv(ρ′′ 1) = img(ρ1) ∪ img(ρ′ 1) and nontriv(ρ′′ 2) = dom(ρ′ 2) ∪ dom(ρ2).

We reason as follows:

(ρ′ 2 ◦ρ)•f((ρ′ 1 ◦ρ)•x) = (ρ2 ◦ρ′′ 2 ◦ρ)•f((ρ′′ 1 ◦ρ1 ◦ρ)•x) Lems. 5.15 & 5.6, Def. 5.3= (ρ2 ◦ρ′′ 2 ◦ρ◦ρ′′ 1)•f((ρ1 ◦ρ)•x) dom(ρ′′ 1) ∩Sf = ∅= (ρ2 ◦ρ′′ 2 ◦ρ′′ 1 ◦ρ)•f((ρ1 ◦ρ)•x) nontriv(ρ′′ 1) ∩nontriv(ρ) = ∅= (ρ2 ◦ρ)•f((ρ1 ◦ρ)•x) Lems. 5.15 & 5.6, Def. 5.3End of proof
Lemma 5.19

Suppose x ∈|X⇒| and ρ is a renaming. Suppose f ∈|X⇒| →|Y⇒| is supported.

Then ρ•(f(x)) = (ρ•f)(ρ•x).

Proof

Let ρ1 and ρ2 be a freshening pair of renamings of nontriv(ρ) with respect to Sf ∪ supp(x).

Let ρ′ be a renaming with nontriv(ρ′) = img(ρ1) such that ρ1 ◦ρ = ρ′ ◦ρ1; this exists since ρ1 is injective on nontriv(ρ) and ‘freshens’ this set to some fresh set of atoms.

We reason as follows:

(ρ•f)(ρ•x) = (ρ2 ◦ρ)•f((ρ1 ◦ρ)•x) Definition 5.17= (ρ2 ◦ρ)•f((ρ′ ◦ρ1)•x) Definition 5.3= (ρ2 ◦ρ ◦ρ′)•f(ρ1 •x) nontriv(ρ′) ∩Sf = ∅= (ρ ◦ρ2)•f(ρ1 •x) Lem. 5.15, Def. 5.3= ρ•f((ρ2 ◦ρ1)•x) dom(ρ2) ∩Sf = ∅= ρ•f(x) Definition 5.3End of proof

5.2.3. Definition of the exponential

Definition 5.20

Write X⇒⇒ Y⇒ for the renaming set with underlying set those f ∈ |X⇒| →|Y⇒| that are supported in the sense of Definition 5.12, and renaming action as defined in Definition 5.17.

Lemma 5.21

If f is supported in the sense of Definition 5.12 then it is supported by Sf in the sense of Definition 5.3. Thus, X⇒⇒ Y⇒ is indeed a permissive-nominal renaming set.

Proof

It suffices to show that if a ∉Sf then ([a::=b]•f)(x) = f(x). This follows by routine calculations.End of proof

Lemma 5.22

PmsRen (Definition 5.11) is cartesian closed:

• The exponential is X⇒⇒ Y⇒ from Definition 5.20.

• Products are given pointwise as in Definition 5.31.

• The terminal object 1⇒ is the singleton set {0} with the trivial action ρ•0 = 0.

Proof

The bijection between (X⇒×Y⇒) → Z⇒ and X⇒→ (X⇒⇒ Y⇒) is given by currying and uncurrying as usual. Thus G : (X⇒× Y⇒) → Z⇒ maps to x↦ →λy.G(x, y). It is not hard to verify that if dom(ρ) ∩ supp(x) = ∅ then

(ρ•λy.F(x, y))(y) = ρ•F(x, y) = F(x, ρ•y) = (λy.F(x, y))(ρ•y).

Thus λy.G(x, y) is supported by supp(x) and is in Y⇒⇒ Z⇒.End of proof

We take a moment to build a particular exponential which will be useful later.

Definition 5.23

Suppose x ∈|X⇒| and a ∈Aν. Write λa.x ∈|Aν| →|X⇒| for the function mapping a to x and b to [a::=b]•x.

Lemma 5.24

λa.x ∈|Aν ⇒ X⇒|.

Proof

It suffices to show that λa.x is supported by supp(x) (in fact, it is also supported by supp(x)\{a}). Suppose dom(ρ)∩supp(x) = ∅ and z ∈Aν (z is not necessarily distinct from a). Write ρ-a for the renaming such that (ρ-a)(b) = ρ(b) and (ρ-a)(a) = a. We sketch the relevant reasoning:

ρ•((λa.x)z) = (ρ ◦[a::=z])•x = ([a::=ρ(z)] ◦(ρ-a))•x = [a::=ρ(z)]•x = (λa.x)(ρ•z)End of proof

5.3. Atoms, products, atoms-abstraction, and functions out of atoms

5.3.1. Atoms

Definition 5.25

Write B for the nominal set and the permutation/renaming set with underlying set {0, 1} and the trivial permutation/renaming action such that π·x = x/ρ•x = x always.

We will be lax and write x ∈B for x ∈|B|.

Write Aν for the permutation set and the renaming set with underlying set Aν and the natural permutation/renaming action such that π·x = π(x)/ρ•x = ρ(x) always.

We will be lax and write x ∈Aν for x ∈|Aν|.

5.3.2. Atoms-abstraction in permutation and renaming sets

Definition 5.26

Suppose X⟳ is a supported permutation set. Suppose x ∈|X⟳| and a ∈Aν. Define atoms-abstraction [a]x and [Aν]X⟳ by:

[a]x = {(a, x)} ∪{(b, (b a)·x) | b ∈Aν\supp(x)} |[Aν]X⟳| = {[a]x | a ∈Aν, x ∈|X⟳|} π·[a]x = [π(a)]π·x
Lemma 5.27

Suppose X⟳ is a supported permutation set.

1. [Aν]X⟳ is a supported permutation set.

2. [a]x=[a]x′ if and only if x=x′, for a∈Aν and x∈|X⟳|.

3. [a]x=[a′]x′ if and only if a′∉supp(x) and (a′ a)·x=x′, for a, a′∈Aν and x, x′∈|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.

Definition 5.28

Suppose X⇒ is a supported renaming set. Suppose x ∈|X⇒| and a ∈Aν. Define atoms-abstraction [a]x and [Aν]X⇒ by:

[a]x = {(a, x)} ∪{(b, [a::=b]•x) | b ∈Aν\supp(x)} |[Aν]X⇒| = {[a]x | a ∈Aν, x ∈|X⇒|} ρ•[a]x = [a]ρ•x (a ∉nontriv(ρ))
Remark 5.29

Definitions 5.26 and 5.28 look similar; both define graphs of partial functions defined on supp(x) \ {a}. However, the critical difference is that in renaming sets, this partial function can be extended to a total function in Aν → X⇒.

That is, [a]x ∈ [Aν]X⇒ determines a total function which we could write λa.x, mapping a to x and any other b to [a::=b]•x. We return to this in Lemma 7.3 where we show that the natural map from [Aν]X⇒ to Aν ⇒ X⇒ is not surjective; so Definition 5.28 identifies a ‘small’ and ‘well-behaved’ subset of the function space.

A cognate of Lemma 5.27 also holds for [Aν]X⇒:

Lemma 5.30

Suppose X⇒ is a finitely-supported permutation set.

1. [Aν]X⇒ is a permissive-nominal set.

2. [a]x=[a]x′ if and only if x=x′, for a∈Aν and x∈|X⇒|.

3. [a]x=[a′]x′ if and only if a′∉supp(x) and (a′ a)•x=x′ (or equivalently [a::=a′]•x=x′), for a, a′∈Aν and x, x′∈|X⟳|.

5.3.3. Product

Definition 5.31

If X⟳i and X⇒i are supported permutation sets for 1 ≤i ≤n then define X⟳1 × . . . × X⟳n and X⇒1 × . . . × X⇒n by:

|X⟳1 × . . . × X⟳n| = |X⟳1| × . . . × |X⟳n| π·(x1, . . . , xn) = (π·x1, . . . , π·xn)|X⇒1 × . . . × X⇒n| = |X⇒1 | × . . . × |X⇒n| ρ•(x1, . . . , xn) = (ρ•x1, . . . , ρ•xn)
Lemma 5.32

• supp(a) = {a}.

• supp([a]x) = supp(x) \ {a}.

• supp((x1, . . . , xn)) = ⋃{supp(xi) | 1 ≤i ≤n}.

Proof

By routine arguments like those in [GP01] or [Gab11a, Corollary 2.30 & Theorem 3.11].End of proof

5.4. The free extension of a permutation set to a renaming set

Notation 5.33

If ∼ is an equivalence relation, [-]∼ will denote the equivalence class of -in ∼.

Definition 5.34

We define a functor ren(-) from PmsPrm to PmsRen as follows:

• Action of ren(-) on objects. X⟳ maps to ren(X⟳) = ((Rfin × |X⟳|)/∼, •) where ρ•[(ρ′, x)]∼= [(ρ ◦ρ′, x)]∼ and ∼ is the least equivalence relation such that:

1. If ρ(a) = ρ′(a) for every a ∈supp(x) then (ρ, x) ∼(ρ′, x). 2. (ρ ◦π, x) ∼(ρ, π·x).

For convenience we will write [(ρ, x)]∼ as ρ•x.

• Action of ren(-) on arrows. An arrow F : X⟳−→ Y⟳ maps to ren(F) : ren(X⟳) −→ ren(Y⟳) given by:

ren(F)(ρ•x) = ρ•F(x)
Lemma 5.35

ren(F) is well-defined; that is, that if (ρ, x) ∼ (ρ′, x′) then ren(F)((ρ, x)) ∼ ren(F)((ρ′, x′)).

Proof

Induction on the derivation that (ρ, x)∼(ρ′, x′). We consider the two base cases:

• The case ρ(a) = ρ′(a) for every a ∈ supp(x). By part 2 of Lemma 5.10 also ρ(a) = ρ′(a) for every a ∈ supp(F(x)).

• The case (ρ ◦π, x) ∼ (ρ, π·x). Then also (ρ ◦π, F(x)) ∼ (ρ, π·F(x)) and by equivariance π·F(x) = F(π·x).End of proof

Remark 5.36

Rules 2 and 1 of Definition 5.34 can be viewed as α-conversion and garbage-collection respectively. Thus in ρ•x ∈ ren(X⟳) we may without loss of generality (using rule 2) assume that dom(ρ) ∩S = ∅ for any permission set S, and we may also assume (using rule 1) that dom(ρ) ⊆ supp(x).

Lemma 5.37

1. ren(B) (for B considered a set with the trivial permutation action) is isomorphic to B (for B considered a set with a trivial renaming action).

2. ren(Aν) (for Aν with its natural permutation action) is isomorphic to Aν (for Aν with its natural renaming action).

Proof

We consider only the second part. This follows if we note that according to the rules for ∼ in Definition 5.34,

(ρ, a) rule 1∼ ((ρ(a) a), a) rule 2∼ (id, ρ(a)).End of proof

Where we are dealing with more than zero or one atoms at a time, isomorphisms like those in Lemma 5.37 may fail:

Lemma 5.38

ren(Aν×Aν) is not isomorphic to ren(Aν)×ren(Aν) (which is isomorphic to Aν×Aν).

Proof

Consider the element [a::=b]•(a, b).End of proof

6. Interpretation of permissive-nominal logic

6.1. Interpretation of signatures

Definition 6.1

Suppose (A, B) is a sort-signature (Definition 2.1).

A PNL interpretation I for (A, B) consists of an assignment of a nonempty supported permutation set τI to each τ ∈B.

We extend an interpretation I to sorts by:

⟦τ⟧I = τI⟦(α1, . . . , αn)⟧I = ⟦α1⟧I × . . . × ⟦αn⟧I⟦ν⟧I = Aν⟦[ν]α⟧I = [Aν]⟦α⟧I
Definition 6.2

Suppose S = (A, B, F, P, ar, X) is a signature (Definition 2.3).

A (non-equivariant) PNL interpretation I for S consists of the following data:

• An interpretation for the sort-signature (A, B) (Definition 6.1).

• For every f ∈F with ar(f) = (α′)α an equivariant function fI from ⟦α′⟧I to ⟦α⟧I (Definition 5.9).

• For every P ∈P with ar(P) = α a supported function PI from ⟦α⟧I to {0, 1}.

If every PI is equivariant, then call I a fully equivariant interpretation.11

6.2. Interpretation of terms

Definition 6.3

Suppose I is an interpretation for S. A valuation ς to I is a map on unknowns such that for each unknown X,

• ς(X) ∈⟦sort(X)⟧I, and

• supp(ς(X)) ⊆ pmss(X).

ς will range over valuations.

Definition 6.4

Suppose I is an interpretation of a signature S. Suppose ς is a valuation to I.

Define an interpretation ⟦r⟧Iς in S by:

⟦a⟧Iς = a ⟦[a]r⟧Iς = [a]⟦r⟧Iς⟦f(r)⟧Iς = fI(⟦r⟧Iς) ⟦π·X⟧Iς = π·ς(X)⟦(r1, . . . , rn)⟧Iς = (⟦r1⟧Iς, . . . , ⟦rn⟧Iς)
Lemma 6.5

If r : α then ⟦r⟧Iς ∈ ⟦α⟧I.

Proof

By a routine induction on r.End of proof

Lemma 6.6

π·⟦r⟧Iς = ⟦π·r⟧Iς.

Proof

By a routine induction on r. We consider one case:

• The case π′·X. By Definition 6.4 ⟦π′·X⟧Iς = π′·ς(X). Therefore π·⟦π′·X⟧Iς = π·(π′·ς(X)). It is a fact of the group action (Definition 5.2) that π·(π′·ς(X)) = (π ◦π′)·ς(X), and of the permutation action (Definition 2.10) that π·(π′·X) = (π ◦π′)·X. The result follows.End of proof

Lemma 6.7

supp(⟦r⟧Iς) ⊆ fa(r).

Proof

By a routine induction on r. We consider one case in detail:

• The case π·X. fa(π·X) = π·pmss(X) by Definition 2.13. By assumption in Definition 6.3 supp(ς(X)) ⊆ pmss(X).

The cases of a, [a]r, and [a]r use parts 1, 2, and 3 of Lemma 5.32. The case of f uses part 1 of Lemma 5.10.End of proof

6.3. Interpretation of propositions

Definition 6.8

Suppose ς is a valuation to an interpretation I. Suppose X is an unknown and x ∈⟦sort(X)⟧I is such that supp(x) ⊆ pmss(X). Define ς[X::=x] by

(ς[X::=x])(Y ) = ς(Y ) and (ς[X::=x])(X) = x.

It is easy to verify that ς[X::=x] is also a valuation to I.

Definition 6.9

Suppose I is an interpretation. Define an interpretation of propositions by:

⟦P(r)⟧Iς = PI(⟦r⟧Iς)⟦⊥⟧Iς = 0 ⟦φ ⇒ψ⟧Iς = max{1−⟦φ⟧Iς, ⟦ψ⟧Iς}⟦∀X.φ⟧Iς = min{⟦φ⟧Iς[X::=x] | x∈⟦sort(X)⟧I, supp(x)⊆pmss(X)}

We may identify ⟦φ⟧I with a set of valuations {ς | ⟦φ⟧Iς = 1}. We discuss soundness and completeness in Appendix A.

Lemma 6.10

• ⟦r⟧Iς[X::=⟦r′⟧Iς] = ⟦r[X::=r′]⟧Iς.

• ⟦φ⟧Iς[X::=⟦r′⟧Iς] = ⟦φ[X::=r′]⟧Iς.

Proof

By routine inductions on the definitions of ⟦r⟧Iς and ⟦φ⟧Iς in Definitions 6.4 and 6.9. We consider two cases:

• The case of ⟦π·X⟧Iς[X::=r′]. We reason as follows:

⟦π·X⟧Iς[X::=⟦r′⟧Iς] = π·⟦r′⟧IςDefinition 6.4= ⟦π·r′⟧IςLemma 6.6= ⟦(π·X)[X::=r′]⟧IςDefinition 2.21.

• The case of ⟦P(r)⟧Iς[X::=r′]. We reason as follows:

⟦P(r)⟧Iς[X::=⟦r′⟧Iς] = PI(⟦r⟧Iς[X::=⟦r′⟧Iς]) Definition 6.9= PI(⟦r[X::=r′]⟧Iς) Part 1 of this result= ⟦P(r)[X::=r′]⟧IςDefinition 6.9.End of proof
Lemma 6.11

If ς(X) = ς′(X) for all X ∈ fV (r) then ⟦r⟧Iς = ⟦r⟧Iς′, and similarly for φ.

Proof

By a routine induction on r and φ.End of proof

7. Interpretation of HOL

For this section fix some PNL interpretation I of a PNL signature S. Recall from Definition 4.2 the definition of the corresponding HOL signature TS.

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 ⌊-⌋D 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 I for the PNL signature S. Recall the definition of ς[X::=x] (Definition 6.8), and the interpretations of terms ⟦r⟧Iς (Definition 6.4) and propositions ⟦φ⟧Iς (Definition 6.9).

We give similar definitions for HOL and renaming sets, culminating with Theorem 7.15 (soundness).

Definition 7.1

We provide an interpretation H of TS by:

⟦⌊α⌋⟧H = ren(⟦α⟧I)⟦o⟧H = B ⟦(β1, . . . , βn)⟧H = ⟦β1⟧H × . . . × ⟦βn⟧H(βi not of the form ⌊α⌋for at least one i)⟦β′ →β⟧H = ⟦β′⟧H ⇒⟦β⟧H(β′ or β not of the form ⌊α⌋)

Recall X⇒⇒ Y⇒ from Definition 5.20 and X⇒× Y⇒ from Definition 5.31.

Remark 7.2

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, Aν ⇒ - contains ‘exotic elements’ making it bigger than [Aν]-, 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. Aν × Aν in PmsRen has an ‘exotic element’.

Lemma 7.3

1. The natural map from ren(Aν) to Aν mapping ρ•a to ρ(a), is a bijection (cf. Lemma 5.37).

2. The natural map from ren(X⟳× Y⟳) to ren(X⟳) × ren(Y⟳) mapping ρ•(x, y) to (ρ•x, ρ•y) is neither surjective nor injective.

3. The natural map from ren([Aν]X⟳) to [Aν]ren(X⟳) mapping ρ•[a]x where a ∉ nontriv(ρ) to [a]ρ•x, is not surjective.

4. The natural map from [Aν]Y⇒ to Aν ⇒ Y⇒ mapping [a]x to λa.x (Definition 5.23), is not surjective.

Proof

1. By rule 2 of Definition 5.34.

2. Take X⟳= Y⟳= Aν. The natural map from ren(X⟳× Y⟳) to ren(X⟳) × ren(Y⟳) takes id •(a, b) to (id •a, id •b). By equivariance it must map [a::=b]•(a, b) to (id •b, id •b). But then it is not injective, since [a::=b]•(a, b) ≠ id •(b, b) in ren(X⟳× Y⟳). Now take X⟳= Y⟳= Aν × Aν. It is not hard to see that ([a::=b]•(a, b), id •(b, b)) is not in the image of the natural map, so the map is also not surjective.

3. Take X⟳= Aν × Aν and consider [a][a::=b]•(a, b) ∈ [Aν]ren(X⟳).

4. Take X⇒= Y⇒= Aν for Aν considered a renaming set as in Definition 5.25. Consider the function [a::=b] ∈Aν ⇒Aν, mapping a to b, b to b, and all other c to c.End of proof

7.2. Interpretation of terms

Definition 7.4

A (HOL) valuation ϱ to H is a map on variables X : β such that ϱ(X) ∈ ⟦β⟧H. ϱ will range over valuations.

Definition 7.5

Suppose ϱ is a valuation. Suppose X is a variable and x ∈⟦type(X)⟧H. Define a function ϱ[X::=x] by:

(ϱ[X::=x])(b) = ϱ(b) (ϱ[X::=x])(Y ) = ϱ(Y ) and (ϱ[X::=x])(X) = x

It is easy to verify that ϱ[X::=x] is also a valuation to H.

Definition 7.6

Extend H to terms as follows:

• ⟦a⟧H(ϱ) = ϱ(a).

• ⟦X⟧H(ϱ) = ϱ(X).

• ⟦gf⟧H = ren(fI) and ⟦gP⟧H = ren(PI) (Definition 5.34).

• ⟦⊥⟧H(ϱ) = 0.

• ⟦⇒⟧H(ϱ) = λx ∈B, y ∈B.max{1−x, y}.

• ⟦∀β)⟧H(ϱ) = λx ∈⟦β ⇒B⟧H.min{xy | y ∈ ⟦β⟧H}.

• ⟦λa.t⟧H(ϱ) = ρ•[a]x where ⟦t⟧H(ϱ[a::=a]) = ρ•x provided that t : ⌊α⌋ for some PNL sort α and a ∈Aν for some name sort ν and (α-converting if necessary) a ∉⋃X∈fv(t)\{a} supp(ϱ(X)).

• ⟦λX.t⟧H(ϱ) = λx.⟦t⟧H(ϱ[X::=x]) provided that λX.t : β′ →β where β′ →β is not equal to ⌊[Aν]α⌋ for any ν or α.

• ⟦tu⟧H(ϱ) = ([a::=b]◦ρ)•x provided that t : ⌊α⌋ for some PNL sort α, where ⟦u⟧H(ϱ) = id •b (by construction some such b always exists) and ⟦t⟧H(ϱ) = ρ•[a]x, and (renaming if necessary) a ∉ nontriv(ρ) ∪{b}.

• ⟦tu⟧H(ϱ) = ⟦t⟧H(ϱ)⟦u⟧H(ϱ) provided that t : β for β not equal to ⌊α⌋ for any PNL sort α.

• ⟦(t1, . . . , tn)⟧H(ϱ) = (⋃ ρi)•(x1, . . . , xn) provided that ti: ⌊αi⌋ for 1 ≤i ≤n, where ⟦ti⟧H = ρi •xi, and we choose represenatives such that dom(ρi) ∩ dom(ρj) = ∅ for all 1 ≤i ≠ j ≤n.

• ⟦(t1, . . . , tn)⟧H(ϱ) = (⟦t1⟧H(ϱ), . . . , ⟦tn⟧H(ϱ)) provided that there exists some i and β such that ti: β and β is not equal to ⌊α⌋ for any PNL sort α.

Remark 7.7

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:

PNL syntax⌊-⌋D⟦-⟧IςHOL syntax⟦-⟧H(D(ς))not possiblePmsPrmren(-)PmsRen

We translated PNL to HOL using ⌊-⌋D 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 [a]r translates to λa.⌊r⌋D and has nominal denotation as an atoms-abstraction [a]⟦r⟧Iς; atoms-abstraction (Definition 5.26) is the graph of a partial function, whereas λa.⌊r⌋D ‘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.

Lemma 7.8

Suppose a ∈Aν and b ∈Aν. Suppose a ∉ supp(ϱ(X)) for every X ∈ fv(r) \ {a} (including b). Then ⟦t⟧H(ϱ[a::=id •b]) = [a::=b]•(⟦t⟧H(ϱ)).

Proof

By a routine induction on t. We mention two cases:

• The case t is a. Using the fact that id •b = [a::=b]•a in Aν with the action described in Definition 5.25.

• The case t is X for some HOL variable that is not an atom. By assumption a ∉ supp(ϱ(X)) and so by Definition 5.3, ϱ(X) = [a::=b]•ϱ(X). The result follows.End of proof

Remark 7.9

Lemma 7.8 may fail if a ∈ supp(ϱ(X)). For instance, if ϱ(X) = a where a ∈Aν and type(X) = µν and X is not itself an atom, then ⟦X⟧H(ϱ[a::=id •b]) = id •a yet [a::=b]•(⟦X⟧H(ϱ)) = [a::=b]•(id •a) = id •b.

We need to check that the denotation of terms populates the denotation of their types, and that β-equivalent terms receive equal denotations.

Lemma 7.10

If t : β then ⟦t⟧H(ϱ) ∈ ⟦β⟧H.

Theorem 7.11

⟦(λX.t)u⟧H(ϱ) = ⟦t⟧H(ϱ[X::=⟦u⟧H(ϱ)]).

Proof

There are two cases, depending on whether λX.t : ⌊[Aν]α⌋ for some PNL sort, or not.

• The case t : ⌊α⌋. By Definition 7.6 ⟦u⟧H(ϱ) = id •b and ⟦λX.t⟧H(ϱ) = ρ•[a]x, for some b, a, and x. α-converting if necessary assume X is equal to a which we choose

fresh (so a ∉ nontriv(ρ) ∪{b} and a ∉ supp(ϱ(Y)) for every Y ∈ fv(t) \ {a}). Then also by definition ⟦(λa.t)u⟧H(ϱ) = ([a::=b] ◦ρ)•x. Thus it suffices to check that ([a::=b] ◦ρ)•x = ⟦t⟧H(ϱ[a::=b]). This follows using Lemma 7.8.

• The case t : β where β is not equal to ⌊α⌋ for any PNL sort α. This is as standard.End of proof

7.3. Soundness

Lemma 7.12

If ϱ(X) = ϱ′(X) for all X ∈ fV (t) then ⟦t⟧H(ϱ) = ⟦t⟧H(ϱ′).

Proof

By a routine induction on terms.End of proof

Lemma 7.13

⟦t⟧H(ϱ[X::=⟦u⟧H(ϱ)]) = ⟦t[X::=u]⟧H(ϱ).

Proof

By a routine induction on t. We mention two cases (bearing in mind that in HOL, a variable X : ν may be an atom in Aν):

• The case t equals X equals a ∈Aν for some atom a. By Definition 7.6, ⟦a⟧H(ϱ[a::=⟦u⟧H(ϱ)]) = ⟦u⟧H(ϱ).

• The case t equals λY.t′. We assume Y ∉ fv(u), so (λY.t′)[X::=u] = λY.(t′[X::=u]), and use the inductive hypothesis.End of proof

Definition 7.14 (Validity).

Call the proposition ξ valid in H when ⟦ξ⟧H(ϱ) = 1 for all ϱ.

Call the sequent ξ1, ..., ξn ⊢λ χ1, ..., χp valid in H when (ξ1 ∧... ∧ξn) ⇒ (χ1 ∨... ∨χp) is valid.

If this is true for all H then write ξ1, . . . , ξn ⊨λ χ1, . . . , χp.

Theorem 7.15 (Soundness).

If Ξ ⊢λ χ is derivable then Ξ ⊨λ χ.

Proof

Fix some interpretation H. We work by induction on derivations (Figure 2). We sketch the two non-trivial cases:

• The case of (h∀L). We check that u : type(X) implies ⟦∀X.ξ⟧H(ϱ) ≤⟦ξ[X::=u]⟧H(ϱ). We reason as follows:

⟦∀X.ξ⟧H(ϱ) = min{⟦λX.ξ⟧H(ϱ)y | y ∈⟦type(X)⟧H} Definition 7.6= min{⟦ξ⟧H(ϱ[X::=y]) | y ∈⟦type(X)⟧H} Definition 7.6≤⟦ξ⟧H(ϱ[X::=⟦u⟧H(ϱ)]) Fact= ⟦ξ[X::=u]⟧H(ϱ) Lemma 7.13

In the second use of Definition 7.6 above, note that [Aν]o is never of the form ⌊[Aν]α⌋ for any α.

• The case of (h∀R). We use Lemma 7.12 and routine calculations on truth-values.End of proof

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 ∀X.φ in Lemma 8.10 are non-trivial. Some mathematical action also takes place in Lemma 8.9 and the case of π·X 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:

Lemma 8.1

Suppose G : X⇒−→B. Then for every ρ, G(x) = 1 implies G(ρ•x) = 1.

Proof

From equivariance and the fact that ρ•1 = 1 in B.End of proof

Corollary 8.2

Suppose F : X⟳−→B. Then ren(F)(ρ•x) = F(x).

Notation 8.3

Write ρ•ϱ for the valuation mapping X to ρ•ϱ(X).

Lemma 8.4

Suppose ξ is a HOL proposition. Then

• ⟦ξ⟧H(ρ•ϱ) = ⟦ξ⟧H(ϱ) for every ρ and ϱ, and

• as a corollary, if X : β and x ∈ ⟦β⟧H then ⟦ξ⟧H(ϱ[X::=x]) = ⟦ξ⟧H(ϱ[X::=ρ•x]).

Proof

We work by induction on ξ. For each ξ the corollary follows from the first part using a freshening pair of renamings (see Definition 5.16). For the first part, the case of gP is by Corollary 8.2. The case of ∀ follows using the second part and some routine calculations. The cases of ⊥ and ⇒ are immediate.End of proof

Remark 8.5

Lemma 8.4 expresses that ⟦ξ⟧H 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 ∀X.φ in Lemma 8.10 to ‘jettison’ unwanted ρ in the denotation of the quantified variable.

8.2. The completeness proof

Notation 8.6

Suppose D = [d1, . . . , dn] is a finite list of distinct atoms in Aν1, ..., Aνn respectively. Suppose r : α is a PNL term. Then:

• Write [D]r for the PNL term [d1] . . . [dn]r.

• Write [AD]α for the PNL sort [Aν1] . . . [Aνn]α.

Definition 8.7

Given a finite list of distinct atoms D, map a PNL valuation ς to a HOL valuation D(ς) defined by

D(ς) maps X : α to id •[DX]ς(X) ∈⟦⌊[ADX]α⌋⟧Handa : ν to a ∈Aν
Lemma 8.8

Suppose D ⊢r. Then ⟦⌊r⌋D⟧H(D(ς)) = id •x for some x ∈⟦⌊sort(r)⌋⟧H.12

Proof

By a routine induction on Definition 7.6 using Definition 8.7 for the case that r is a variable X.End of proof

Compare Lemma 8.9 with Lemma 4.12:

Lemma 8.9

If nontriv(π) ∩ supp(x) ⊆D′ then (id •[D′]x)π·D′ = id •π·x.

Proof

From Definition 7.6 and rule 2 of Definition 5.34.End of proof

Lemma 8.10 proves that the schematic diagram of Remark 7.7 does indeed commute:

Lemma 8.10

Suppose r : α and φ : α. Then:

• If D ⊢r then ⟦⌊r⌋D⟧H(D(ς)) = id •⟦r⟧I(ς).

• If D ⊢φ then ⟦⌊φ⌋D⟧H(D(ς)) = ⟦φ⟧I(ς).

Proof

By inductions on r and φ.

• The case π·X. We reason as follows, where α = sort(X) and S = pmss(X):

⟦⌊π·X⌋D⟧H(D(ς)) = ⟦Xπ·DX⟧H(D(ς)) Definition 4.3= D(ς)(X)π·DXDefinition 7.6= (id •[DX]ς(X))π·DXDefinition 8.7= id •π·ς(X) Lemma 8.9, supp(ς(X))⊆S= id •⟦π·X⟧I(ς) Definition 6.4

Note of the penultimate step that by assumption D ⊢r, so by Definition 4.6 nontriv(π) ∩S ⊆DX = D ∩S.

• The case [a]r. We reason as follows:

⟦⌊[a]r⌋D⟧H(D(ς)) = ⟦λa.⌊r⌋D⟧H(D(ς)) Definition 4.3= ρ•[a]x Definition 7.6, a fresh, ρ•x = ⟦⌊r⌋D⟧H(D(ς)[a::=a])= id •[a]x Wlog ρ = id by Lemma 8.8= id •[a]⟦r⟧I(ς) ind. hyp.= id •⟦[a]r⟧I(ς) Definition 6.4

• The case P(r). We reason as follows:

⟦⌊P(r)⌋D⟧H(D(ς)) = ⟦gP(⌊r⌋D)⟧H(D(ς)) Definition 4.3= gH P(⟦⌊r⌋D⟧H(D(ς))) Definition 6.9= gH P(id •⟦r⟧I(ς)) part 1= ren(PI)(id •⟦r⟧I(ς)) Definition 7.6= PI(⟦r⟧I(ς)) Corollary 8.2= ⟦P(r)⟧I(ς) Definition 6.9

• The case ∀X.φ. Write α = sort(X) and S = pmss(X). From Definition 7.6

⟦⌊∀X.φ⌋D⟧H(D(ς)) = min{⟦⌊φ⌋D⟧H(D(ς)[X::=x]) | x ∈⟦⌊[ADX]α⌋⟧H}

By construction in Definition 7.1 every x ∈⟦⌊[ADX]α⌋⟧H has the form ρ•x′ for x′ ∈ [DX]⟦α⟧I. By Lemma 8.4 we have

min{⟦⌊φ⌋D⟧H(D(ς)[X::=x]) | x ∈⟦⌊[ADX]α⌋⟧H}= min{⟦⌊φ⌋D⟧H(D(ς)[X::=id •x′]) | x′ ∈⟦[ADX]α⟧I}

Using Lemma 8.4 again we assume without loss of generality that supp([DX]x′) ⊆ pmss(X) \ DX, and so:

min{⟦⌊φ⌋D⟧H(D(ς)[X::=id •[DX]x′]) | x′ ∈⟦[ADX]α⟧I}= min{⟦⌊φ⌋D⟧H(D(ς)[X::=id •x′′]) | x′′ ∈⟦α⟧I, supp(x′′)⊆pmss(X)}

Now we unfold definitions and use the inductive hypothesis that D(ς)[X::=id •[DX]x′′] = D(ς[X::=x′′]), and we obtain:

min{⟦⌊φ⌋D⟧H(D(ς)[X::=id •[DX]x′′]) | x′′ ∈⟦α⟧I, supp(x′′)⊆pmss(X)}= min{⟦⌊φ⌋D⟧H(D(ς[X::=x′′])) | x′′ ∈⟦α⟧I, supp(x′′)⊆pmss(X)}= min{⟦φ⟧I(ς[X::=x′′]) | x′′ ∈⟦α⟧I, supp(x′′)⊆pmss(X)}= ⟦∀X.φ⟧I(ς)
End of proof
Corollary 8.11

Suppose Φ = {φ1, . . . , φn} and Ψ = {ψ1, . . . , ψp} and D ⊢ Φ, and D ⊢ Ψ (Definition 4.6). Suppose I is a PNL interpretation and suppose φ1, . . . , φn ⊢π ψ1, . . . , ψp is not valid in I.

Then H from Definition 7.1 is a HOL interpretation and ⌊φ1⌋D, . . . , ⌊φn⌋D ⊢λ ⌊ψ1⌋D, . . . , ⌊ψp⌋D is not valid in H.

Proof

Suppose ς is such that ⟦φ1 ∧· · · ∧φn⟧I(ς) = 1 and ⟦ψ1 ∨· · · ∨ψp⟧I(ς) = 0. We use Lemma 8.10 for D(ς) (Definition 8.7).End of proof

Theorem 8.12 (Completeness).

Suppose D ⊢ Φ and D ⊢ Ψ. If Φ ⊬π Ψ then ⌊Φ⌋D ⊬λ ⌊Ψ⌋D.

Proof

We use the contrapositive of completeness of restricted PNL (Theorem A.9), then Corollary 8.11, then the contrapositive of HOL soundness (Theorem 7.15).End of proof

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 [a]t is interpreted as a function, like λa.t 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 [A]α 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 SetsF (presheaves over the category of finite sets and functions between them). PmsRen corresponds to presheaves (not quite over F, 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 SetsI.)

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 SetsF. This semantics is functional in that atoms-abstractions in SetsF 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 SetsF, 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 ∈|X⇒| need not have finite support is significant because it is impossible with a finite renaming to rename supp(x) to be entirely disjoint for some other permission set S. 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 [a::=b]•(a, b) and id •(b, b) are distinct elements in ren(Aν× Aν) in PmsRen; this happens because the free construction ‘suspends the non-injectivity’ of [a::=b] on (a, b). 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 [a::=b]·x really does identify a with b in x 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.

P(a) ⊢P(b).

In the journal version [DG11] of [DG10] we strengthen PNL further by allowing a shift-permutation. This is a non-finitely-supported bijection on A 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. A< ∪{a} = π·A< for some π, where a ∉A<) 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 ∀X.P(X) ⊢ P(Z) where pmss(X) = A< and pmss(Z) = A< ∪{a} where a ∉A<, which was not possible in the PNL from [DG10].

Neither equivariance nor shift are translated to HOL in this paper; more on this in the next subsection.

9.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

Definition A.1 (Validity).

Suppose I is a non-equivariant interpretation of a signature S (Definition 6.2). Call the proposition φ valid in I when ⟦φ⟧Iς = 1 for all ς.

Call the sequent φ1, ..., φn ⊢ψ1, ..., ψp valid in I when (φ1 ∧... ∧φn) ⇒ (ψ1 ∨... ∨ψp) is valid.

If this is true for all non-equivariant I then write φ1, . . . , φn ⊨π ψ1, . . . , ψp. If this is true for all equivariant I then write φ1, . . . , φn ⊨ψ1, . . . , ψp.

Theorem A.2 (Soundness).

1. If Φ ⊢π Ψ is derivable then Φ ⊨π Ψ.

2. If Φ ⊢ Ψ is derivable then Φ ⊨ Ψ.

Proof

Fix some interpretation I. 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 I is fully equivariant then it can further be proved that ⟦φ⟧Iς = ⟦π·φ⟧Iς always, so that (Ax) is valid. If I is not fully equivariant, then just (Axπ) is valid.End of proof

Theorem A.3

(Cut) is admissible in both full and restricted PNL.

Proof

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.End of proof

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 S = (A, B, F, P, ar, X).

• A formula φ such that ⊬π φ.

Definition A.4

Define a new signature Sπ as follows:

• Aπ = A and Bπ = B ∪{τ π} (so we have the same atom sorts and the same base sorts, plus one extra base sort τ π).

• Fπ = F and Pπ = P (so we have the same term- and proposition-formers).

• If f ∈F then ar π(f) = ar(f) (the term-formers are identical).

• If P ∈P and ar(P) = α then ar π(P) = (τ π, α) (so proposition-formers take one extra argument of sort τ π).

• X π = X ∪{Zπ i,S | i ∈N, S a permission set} where sort(Zπ i,S) = τ π (so we add unknowns of sort τ π).

Now fix some particular unknown Zπ with sort(Zπ) = τ π and such that fa(φ) ⊆ pmss(Zπ).

Definition A.5

Define a translation -π from PNL propositions in the signature S to PNL propositions in the signature Sπ by mapping P(r) to P(Zπ, r) and extending this in the natural way to all predicates.

Our proof depends on the following technical lemma about restricted PNL:

Lemma A.6

If Φ ⊢ Ψ is derivable in full PNL then there exists a derivation Π such that every sequent Φ′ ⊢ Ψ′ in Π satisfies fa(Φ′) ∪ fa(Ψ′) ⊆ fa(Φ) ∪ fa(Ψ).

Proof

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.14End of proof

Lemma A.7

π·r = π′·r if and only if π(a) = π′(a) for every a ∈ fa(r), and similarly for φ.

See [Gab11b, Lemma 3.2.9] or [DGM10, Lemma 4.15].

Proposition A.8

If Φπ ⊢ Ψπ in PNL and fa(Φ) ∪ fa(Ψ) ⊆ pmss(Zπ) then Φ ⊢π Ψ.

Proof

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 Zπ.

So we can go through the entire syntax of Π and delete Zπ 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 π′·Zπ = id·Zπ (recall from Subsection 2.3 that we quotient by α-equivalence) and so by Lemma A.7 that π′(a) = a for all a ∈ pmss(Zπ). By assumption fa(Φ) ∪ fa(Ψ) ∪ fa(ψ) ∪ fa(ψ′) ⊆ pmss(Zπ) and so by Lemma A.7 ψ = ψ′, and we are done.End of proof

Theorem A.9

If Φ ⊨π Ψ then Φ ⊢π Ψ.

Proof

We prove the contrapositive, that if Φ ⊬π Ψ then Φ ⊭π Ψ. Suppose Φ ⊬π Ψ. Using the constructions above we augment to a signature Sπ (Definition A.4) with some Zπ with fa(Φ) ∪ fa(Ψ) ⊆ pmss(Zπ). 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 I and valuation ς to I such that ⟦Φ⟧Iς = 1 and ⟦Ψ⟧Iς = 0. It is now routine to convert I into a non-equivariant model of the original signature S by taking PH(x) = PI(ς(Zπ), x).End of proof

Notes

1A word of clarification here: we take o 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 o, namely ∀ : (ι→o)→o. ∀-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 ∀β : (β →o) →o (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 ‘X’ 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 X is one of the countably infinitely many HOL variables that are not atoms. ↩

10Recall from Definition 2.5 that by convention a and b 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(r) ⇎ P(π·r); 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(r) = f(π·r). ↩

12The point here is that ⟦⌊r⌋D⟧H(D(ς)) is not equal to ρ•x for any ρ that is non-injective on supp(x). ↩

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. ↩