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

Permissive-Nominal Logic (journal version)

Gilles Dowek, INRIA, France. http://www-roc.inria.fr/who/Gilles.Dowek

Murdoch J. Gabbay, Heriot-Watt University, UK. http://www.gabbay.org.uk

Permissive-Nominal Logic (PNL) is an extension of first-order predicate logic in which term-formers can bind names in their arguments.

This allows for direct axiomatisations with binders, such as of the λ-binder of the lambda-calculus or the ∀-binder of first-order logic. It also allows us to finitely axiomatise arithmetic, and similarly to axiomatise ‘nominal’ datatypes-with-binding.

Just like first- and higher-order logic, equality reasoning is not necessary to α-rename.

This gives PNL much of the expressive power of higher-order logic, but models and derivations of PNL are first-order in character, and the logic seems to strike a good balance between expressivity and simplicity.

Categories and Subject Descriptors: F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic— Set theory; Lambda-calculus and related systems; I.2.3 [Artificial Intelligence]: Deduction and Theorem Proving— Metatheory

General Terms: Theory, Languages

Additional Key Words and Phrases: Permissive-nominal logic, nominal sets, names and binding, permutation

ACM Reference Format: Dowek, G., Gabbay, M. J., 2010. Permissive-nominal logic (journal version) ACM Trans. Comput. Logic V, N, Article A (January YYYY), 36 pages. DOI = 10.1145/0000000.0000000 http://doi.acm.org/10.1145/0000000.0000000

Thanks to the anonymous referees. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.

1. INTRODUCTION

In the early 20th century, the expressivity of logics was considered in principle. For example, first-order predicate logics with or without term-formers are equally expressive, in principle.

In the early 21st century, more attention is paid to what we like to call ‘ergonomics’. First-order predicate logic with term-formers is more ergonomic than first-order predicate logic without term-formers; terms, propositions and proofs are shorter and more natural in the former than in the latter.

Another imperative is for a weak logic—the fewer ‘bells and whistles’ we have to worry about, the easier it will be to verify, implement, and prove its meta-theoretic properties. This can be in tension with being ergonomic, as the example of first-order predicate logic with or without term-formers illustrates.

Thus there enters a fruitful design tension: we aim for logics that are so ergonomic that they ‘just work’, yet so weak and well-behaved that we can still prove good properties for them.

Now we come to the issue of binding. Binding is ubiquitous in logical specifications in mathematics—binding features in function definitions via λ-abstraction, and binders are also used to define sets in comprehension, and to define finite and infinite sums, integrals, derivations, quantifiers, and so on. A logic for mathematics that provides support for this central and essential notion, is likely to be more ergonomic than a logic that does not.

First-order logic is weak, computationally tractable, and has good theoretical properties (unification of first-order terms is decidable; proof-search is simple and well-understood; models are simple). However, first-order logic is unergonomic in the sense that it does not admit term-formers that can bind. Thus it is hard to give direct, finite, first-order axiomatisations of set theory, arithmetic, higher-order logic, or the λ-calculus.

This is one reason that e.g. higher-order logic is often used as a specification language in theory (see [Farmer 2008] for an excellent exposition) and implementations (like Isabelle [Paulson 1990])—higher-order logic has a binder (λ) built-in to terms, and so is more ergonomic.

However, higher-order logic is also stronger than first-order logic, less computationally tractable, and models tend to be more complex. The jump from first- to higher-order logic is quite large.

This motivates the study of direct extensions of first-order predicate logic with term-formers that can bind. The topic of this paper is the construction of one such extension, which we call permissive-nominal logic (PNL). PNL has a clear first-order flavour, and it admits term-formers that bind.

Technical summary and overview. The main technical contributions of this paper are: the definition of permissive-nominal logic, in particular how it handles freshness side-conditions and how this permits the addition of universal quantification to nominal terms; the Tarski-style models we then construct; and the finite yet fully first-order axiomatisations of substitution, first-order logic, and arithmetic which we then exhibit.

Soundness, completeness, and cut-elimination follow by fairly routine arguments, but we see this as a good sign: that the definition of permissive-nominal logic remains close to first-order logic, while allowing terms with binders.

An overview of this paper is as follows:

— We introduce the syntax and derivation rules of permissive-nominal logic (Section 2). The impatient reader can jump directly to Figure 1 on page 11 and see that these derivation rules are virtually indistinguishable from those of first-order logic; only an extra side-condition in (∀L) hints at any difference.1

— We prove soundness and completeness (Theorems 3.30 and 3.45) with respect to a suitable notion of permissive-nominal set (Definition 3.4).

— We axiomatise arithmetic in PNL and prove a correctness and conservative extension result Theorem 5.21. The axiomatisation of arithmetic is finite; the induction schema normally given in first-order logic arithmetic is represented by a single axiom with a universal quantification ∀X over a permissive-nominal terms unknown.

— We indicate how to axiomatise nominal inductive datatypes, the И-quantifier, and semantic freshness (Section 6).

— We prove cut-elimination (Theorem 7.7). The proof is virtually identical to that of first-order logic.

Permissive-nominal logic, nominal logic, and nominal terms. Permissive-nominal logic follows the nominal logic of [Pitts 2003] in its name, which coined the term ‘nominal’, but nominal logic from [Pitts 2003] is a first-order theory of (set of axioms for) the equivariant Fraenkel-Mostowski sets and associated constructions used in [Gabbay and Pitts 2001]. The syntax, semantics, and derivability of PNL are new, as indeed is the application to arithmetic.

The term-language of PNL goes back to the nominal terms of [Urban et al. 2004]. It is permissive, which means that the freshness contexts from [Urban et al. 2004] become a kind of sorting constraint called permission sets. For more discussion see [Dowek et al. 2010] which introduced permissive-nominal terms, and amongst other things gave correspondences with nominal terms and also higher-order patterns.

In this paper we extend nominal syntax further by introducing shift-permutations (Definition 2.9). Also, unlike [Urban et al. 2004; Dowek et al. 2010] in PNL there is quantification over unknowns ∀X.

This journal paper follows a conference paper [Dowek and Gabbay 2010]. With respect to that paper, we have made the following changes:

— The treatment of α-equivalence has been streamlined, leading to simplified proofs. Two structural rules (αL) and (αR) have been eliminated.

— The rule (И) from [Dowek and Gabbay 2010] is now part of the axiom rule, further simplifying the proof-theory.

— The notion of permutation includes shift-permutations; these permutations ‘shift all atoms up by one’. Some readers will see in this a de Bruijn-like ‘shift’ function [Abadi et al. 1991]. This gives desirable extra power to ∀-quantification and, perhaps surprisingly, turns out to be compatible with nominal techniques’ characteristic small support property.

— We include proofs of completeness by a standard term-model construction, and a sketch proof of cut-elimination.

2. PERMISSIVE-NOMINAL LOGIC

2.1. Syntax

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

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

We admit the possibility of empty tuples, so that () is a sort (the unit sort).

Example 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’.

Definition 2.3

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

— F and P are disjoint sets of term- and 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)τ.

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

Notation 2.4

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

Remark 2.5

The reader familiar with higher-order logic can read ar(f) = (α)τ as f : α →τ and no harm will come of it. We do not do this because we are following a first-order logic notation—and because we want to avoid any possible confusion that (α →α) →α might be a sort. It is not.

Example 2.6

A signature for the λ-calculus would have one name-sort ν, one base sort ι, and term-formers lam : ([ν]ι)ι, app : (ι, ι)ι, and var : (ν)ι.

A proposition-former for nominal freshness # would have arity (ν, ι), though the arity ([ν]ι) would also be possible (this would handle more of the properties of names at the level of the logic). More on this in Subsection 6.3.

Plenty more examples of PNL theories will follow.

Definition 2.7

For each name sort ν fix a disjoint countably infinite set of atoms Aν (level 1 names).

For each ν also fix a bijective function fν from Aν to the integers Z = {0, -1, 1, -2, 2, . . .} (that we can do this follows from our assumption that atoms are countable).

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. 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 with respect to A is also infinite).

Remark 2.8 (Representing permission sets).

A permission set S may be finitely represented

— either as the pair of finite sets (A, B) where A ⊆A< and B ⊆A> and S = (A< \ A) ∪B,

— or perhaps more elegantly as a single finite set C ⊆A such that S = A< ∆C where X ∆Y = {z | (z ∈X ∧z ∉Y) ∨ (z ∉X ∧z ∈Y) (exclusive or).

Permission sets are a sorting/typing annotation which will be associated to variables in Definition 2.11.

Definition 2.9

Given a, b ∈Aν let a (level 1) swapping (a b) be the bijection on atoms that maps a to b, b to a, and all other c to themselves. Also define a bijection shiftν on atoms by:

shiftν(a) = fν(f -1 ν (a) + 1) (a ∈Aν)shiftν(a) = a a ∈A \ Aν

Let the (level 1) permutations be the group of bijections on atoms generated by all swappings and shiftν. Call a permutation π finite when it is generated just by swappings; thus, when nontriv(π) = {a∈A | π(a)≠a} is finite. Otherwise, call π non-finite. π will range over permutations. Write P for the set of all permutations and write Pfin for the set of all finite permutations.

Remark 2.10

Swappings are used to manage α-equivalence in nominal terms. This is standard and goes back (at least) to [Gabbay and Pitts 2001] and the second author’s thesis [Gabbay 2001].

The true importance of shiftν is that it bijects A< with A< ∪{a} for some a ∉A<—this cannot be achieved using a finite permutation. The relevance of this is that later when we build ∀X.φ, this really will mean ‘for all X’ even though the permission set S of X makes it range over terms with free atoms in S.

Permutations, like permission sets, easily admit finite representations. shift corresponds via the bijection with numbers to the operation ‘add 1’.

Definition 2.11

For each signature S = (A, B, F, P, ar) and each sort α over (A, B) and permission set S fix a countably infinite set of unknowns (level 2 names) of that sort and permission set. X, Y, Z will range over distinct unknowns. Write sort(X) for the sort and pmss(X) for the permission set of X.

Remark 2.12

So an unknown X has two type attributes: its sort α, which intuitively describes what kind of data it denotes, and its permission set S which describes the permitted free atoms of the terms, and also the nominal support of the denotations, with which it may be associated by a substitution or valuation—see the definitions of substitution and valuation in Definitions 2.32 and 3.19 respectively.

If X has sort ‘integers’ and permission set A<, then intuitively X represents ‘a term denoting an integer, with free atoms in A<’.

Another name for permission set S might be freshness set, since equally X represents “terms with free atoms not in A \ S”.2

Definition 2.13

For each signature S, define raw terms and raw 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.phi prop. psi prop. phi ⇒psi prop.r : α (ar(P) = α) P(r) prop.phi prop. ∀X.phi prop.

As in Definition 2.1, we admit the possiblity of empty tuples so that () the empty tuple of terms is a term and has sort ().

We will quotient raw terms and propositions by α-equivalence (to obtain terms r and propositions φ), later.

Example 2.14

Consider lam([b]app(X, var(b))) where b ∉ pmss(X); this represents the λ-term schema λy.(ty) where y ∉ fv(t).

Recall that app and lam are term-formers of arities (ι, ι)ι and ([ν]ι)ι. The sorts of b and X are ν (names) and ι (individuals) respectively.

Remark 2.15

Our version of PNL has connectives ⊥, ⇒, and ∀. We could easily add other connectives like ⊤, ¬, ∧, ∨, and ∃. Instead we treat them as a definable extension using the standard ‘de Morgan’ encoding.

We may write id·X just as X.

2.2. Permutation actions and free atoms/unknowns

Nominal techniques suggest handling α-renaming using permutations. To a first approximation, if wherever the reader sees ‘permutation action’ they substitute ‘α-renaming’, then they will not go too far wrong.

Notation 2.16

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.

— Define πn by π0 = id and πn+1 = πn ◦π.

Definition 2.17

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) π·⊥= ⊥ π·(phi ⇒psi) = (π·phi) ⇒(π·psi)π·P(r) = P(π·r) π·(∀X.phi) = ∀X.π·phi
Definition 2.18

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

Define a (level 2) permutation action by:

Π·a = a Π·(r1, . . . , rn) = (Π·r1, . . . , Π·rn)Π·[a]r = [a]Π·r Π·(π·X) = π·(Π(X))Π·f(r) = f(Π·r) Π·⊥= ⊥ Π·(phi ⇒psi) = (Π·phi) ⇒(Π·psi)Π·P(r) = P(Π·r) Π·(∀X.phi) = ∀Π(X).Π·phi

2.3. Free level 1 and level 2 variables

Definition 2.19

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

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

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

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

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

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

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

Proof

By routine inductions on r.End of proof

2.4. α-equivalence

Definition 2.22

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

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
phi R phi′psi R psi′phi ⇒psi R phi′ ⇒psi′
r R s (P : α, r, s : α) P(r) R P(s)
phi R phi′∀X.phi R ∀X.phi′
Definition 2.23

Write (a b) for the (level 1) swapping permutation which maps a to b, b to a, and all other c to themselves. Similarly write (X Y) for the (level 2) swapping.

Define α-equivalence on terms and propositions to be the least congruence =α such that:

(b a)·r =α s (b ∉fa(r)) [a]r =α [b]s(π(a) = π′(a) for all a∈pmss(X)) π·X =α π′·X(Y X)·phi =α psi (Y ∉fV (phi)) ∀X.phi =α ∀Y.psi
Example 2.24

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

Let sort(Y ) = sort(X) and pmss(Y ) = pmss(X) = A<. Suppose a ∈A< and b ∉A<. 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.

Furthermore, if we take syntax as above except that a ∉A< and b ∉A<, then we deduce ∀X.P([a]X) =α ∀Y.P([b]Y).

Remark 2.25

Note that α-equivalence is highly symmetric between levels 1 and 2, based on permutations instead of substitutions, and avoids equality reasoning in the logic.

In [Gabbay and Pitts 2001; Pitts 2003; Gabbay 2007a; Gabbay and Cheney 2004; Cheney 2005] it is not in general possible to ‘just α-convert’ a level 1 abstraction. We must appeal instead to equality reasoning describing atoms-abstraction in nominal sets. But this is harder; derivable equality is more complex than syntactic equivalence.

Lemma 2.26

For every π, Π, r, s, phi, and psi, the following hold:

— r =α s if and only if π·r =α π·s and similarly phi =α psi if and only if π·phi =α π·psi.

— r =α s if and only if Π·r =α Π·s, and similarly phi =α psi if and only if Π·phi =α Π·psi.

Lemma 2.27

If r =α s then fa(r) = fa(s) and fV (r) = fV (s).

Proposition 2.28

=α is an equivalence relation on terms and propositions.

Proof

By a standard argument as in [Fernández and Gabbay 2007], using Lemmas 2.21, 2.26, and 2.27.End of proof

Lemma 2.29

If π(a) = a for every a ∈ fa(r) then π·r =α r.

Definition 2.30

For each signature S, define terms and propositions over S to be raw terms and propositions quotiented by α-equivalence. r and s will range over terms. φ and ψ will range over propositions.

Remark 2.31

Terms and propositions inherit the definitions and properties of raw terms and propositions. Thus for example we may write fa(r) to mean ‘fa(r) for some r ∈r’ (Lemma 2.27 proves this is well-defined).

It is possible to construct terms and propositions directly using a variant of nominal syntax-with-binding from [Gabbay and Pitts 2001], tweaked to include permutation and abstraction by unknowns.

It is also possible to retain the definitions above—reasoning on α-equivalence classes of terms—and to use theorems of abstractive functions developed in [Gabbay 2007b], which are an alternative ‘nominal’ way to guarantee well-definedness of functions defined on α-equivalence classes.

We will not dwell on these issues in this paper because we are most interested in what PNL syntax can express rather than thinking about the syntax for its own sake. However, the mathematics to do this exists and is well-understood.

2.5. Substitution

Definition 2.32

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.

One kind of substitution will be particularly useful later:

Definition 2.33

Suppose X is an unknown and suppose t : sort(X) and fa(t) ⊆ pmss(X). Define [X::=t] by:

[X::=t](X) = t [X::=t](Y ) = id·Y all other Y

By convention (Definition 2.11) X and Y in Definition 2.34 range over distinct unknowns:

Definition 2.34

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

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

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

Only atoms in pmss(X) may be captured in this way. Thus for instance, if a ∉ pmss(X) then θ(X) = a is impossible because it would violate the condition fa(θ(X)) ⊆ pmss(X) in Definition 2.32.

Remark 2.37

The condition fa(θ(X)) ⊆ pmss(X) in Definition 2.32, and the condition fa(t) ⊆ pmss(X) in Definition 2.33, are necessary for the substitution action in Definition 2.35 to be well-defined.

Consider a name sort ν and suppose X : ν and a, b : ν. Suppose a, b ∉ pmss(X), so that by Definition 2.23 (a b)·X = id·X.3

Suppose we drop the conditions on free atoms of terms, so that we admit [X::=a] as a substitution. Then according to the definitions, ((a b)·X)[X::=a] = b whereas (id·X)[X::=a] = a.

Remark 2.38

In PNL, atoms are data; they are ‘bindable constant symbols’. Atoms are not variables; they do not come with a substitution as a primitive in PNL. (Unknowns are variables; they have a substitution action.)

The reader should not expect atoms to populate every sort, like variables do. Atoms populate their own special sorts, name-sorts, which are sorts for ‘bindable data’.

We can make atoms populate a base sort (e.g. variable symbols with sort ‘λ-terms’ or ‘functions’) with a term-former (Definition 2.3), e.g. var in Sections 4 and 6.

We can make atoms behave like variables using axioms, like those of SUB in Figure 4. In PNL, a substitution action for atoms is a matter of writing suitable axioms. Fortunately, nominal techniques make this fairly easy to do.

2.6. Sequents and derivability

Definition 2.39

Φ and Ψ will range over sets of propositions. We may write φ, Φ and Φ, φ as shorthand for {φ} ∪ Φ. We may write Φ, Ψ as shorthand for Φ ∪ Ψ. Finally, define fV (φ) by

fV (Φ) =⋃{fV (φ) | φ ∈Φ}.

A sequent is a pair Φ ⊢ Ψ.

Definition 2.40 (Derivable sequents).

The derivable sequents are defined in Figure 1.

Remark 2.41

As standard, the intuition of Φ ⊢ Ψ being derivable is “the conjunction (logical and) of the propositions in Φ entails the disjunction (logical or) of the propositions in Ψ”. So for instance, intuitively the axiom rule (Ax) expresses that φ if and only if π·φ.

The π in (Ax) is deliberate and represents equivariance (preservation of truth under permuting atoms) within permissive-nominal logic.4 Examples of how π is used follow immediately in Subsection 2.7.

Notation 2.42

We may write Φ ⊢ Ψ as shorthand for ‘Φ ⊢ Ψ is a derivable sequent’.

We may write Φ ⊬ Ψ as shorthand for ‘Φ ⊢ Ψ is not a derivable sequent’.

Remark 2.43

Figure 1 includes rules for ⊥, ⇒, and ∀. Following on from Remark 2.15, note that including rules for other connectives like ⊤, ¬, ∧, ∨, and ∃ would be easy. Because the PNL in this paper is classical, we can treat derivation rules for them as a definable extension of what we already have.

We see no inherent difficulty with constructing an intuitionistic version of PNL.

(Ax)Φ, φ ⊢π·φ, Ψ(⊥L)Φ, ⊥⊢ΨΦ ⊢φ, Ψ Φ, ψ ⊢Ψ(⇒L)Φ, φ ⇒ψ ⊢ΨΦ, φ ⊢ψ, Ψ(⇒R)Φ ⊢φ ⇒ψ, ΨΦ, φ[X::=r] ⊢Ψ (fa(r)⊆pmss(X), r:sort(X)) (∀L) Φ, ∀X.φ ⊢ΨΦ ⊢φ, Ψ (X ∉fV (Φ, Ψ))(∀R)Φ ⊢∀X.φ, ΨΦ ⊢φ, Ψ Φ, φ ⊢Ψ(Cut)Φ ⊢Ψ
Fig. 1: Sequent derivation rules of Permissive-Nominal Logic

2.7. Universal quantification, permission sorts, and shift-permutations

Recall the comment on ‘atoms as data’ in Remark 2.38. Because of permutations, in certain circumstances free atoms can still behave like variables ranging over distinct atoms (cf. the permutative convention of Definition 2.7). Atoms-substitution is not be primitive in PNL, but atoms-permutation is.

Thus in PNL we can express a theory of atoms-inequality in the following interesting way: Assume a name sort Atm and a proposition-former neq : (Atm, Atm), along with a single proposition neq(a, b) for two distinct atoms in Atm—and, if we wish, a proposition neq(a, a) ⇒⊥. The permutation π in (Ax) ensures that a and b represent any two distinct atoms.

This goes further. The condition fa(r) ⊆ pmss(X) in (∀L) might suggest that ∀X.φ means “φ[X::=r] for every r such that fa(r) ⊆ pmss(X)”. Indeed this is so, but what pmss(X) in ∀X.φ really restricts is capture, as we now discuss.

— Suppose a name sort Atm and suppose X : Atm and a proposition-former P of arity Atm. Suppose b ∈ pmss(X). By considering the swapping (b a) and (Ax), and (∀L), ∀X.P(X) ⊢ P(a) for all a, even if a ∉ pmss(X), as follows:

(Ax) π = (b a)P(b) ⊢P(a)(∀L) [X::=b]∀X.P(X) ⊢P(a)

In other words, we can derive P(a) from ∀X.P(X), even if a is not permitted in X. Thus, in the case of level 2 closed terms (without unknowns), these have finitely many atoms and we can use a finite permutation to place them in pmss(X).

— This may not work for the more general case of a term with unknowns; for example there is no finite π such that fa(π·(X, a)) ⊆ pmss(X) where a ∉ pmss(X).
So consider the general case of any sort α and suppose X : α and pmss(X) = S. Suppose Q : α. Consider any other Y : α and pmss(Y ) = T. We will show that ∀X.Q(X) ⊢ Q(Y ) is derivable.

Recall that shift permutation shiftν from Definition 2.9 and the definition of shiftn ν from Notation 2.16. Using shift permutations we can construct a permutation π such that S ∪T ⊆π·pmss(X).5 We derive as follows:

(Ax)Q(π-1·Y ) ⊢Q(Y )(∀L) [X::=π-1·Y ]∀X.Q(X) ⊢Q(Y )

— Nevertheless, ∀X.φ does not mean “φ[X::=r] for every r”. This is because permutations are bijective. For example, suppose X : Atm, a ∉ pmss(X), and P : ([Atm]Atm). Then ∀X.P([a]X) ⊢P([a]r) for all r such that a ∉ fa(r), and also ∀X.P([b]X) ⊢P([b]r) for all r and all b such that b ∉ fa(r). However,

∀X.P([a]X) ⊬P([a]a), and for all b, ∀X.P([a]X) ⊬P([b]b).

The fact that a ∉ pmss(X) forbids capture by an instantiation, in a suitable sense.

3. SEMANTICS OF PERMISSIVE-NOMINAL LOGIC

Nominal sets were introduced in [Gabbay and Pitts 2001] (they were called ‘FM sets’). Technically, a nominal set is a set with a finitely-supported permutation action for atoms. Intuitively, a nominal set is a set with ‘free names’ in a manner which parallels how names feature in abstract syntax, but without necessarily being syntactic structures.

Names in nominal sets are modelled as atoms. They can be renamed by the permutation action; they can be bound by an atoms-abstraction construction; and they feature a finite support property which guarantees that we can always pick a fresh name.

The interested reader can consult a literature which includes [Gabbay and Pitts 2001] or [Gabbay 2011b] for detailed discussions of nominal sets and their applications.

We will interpret PNL using permissive-nominal sets. The permissive-nominal sets we use here generalise nominal sets in two ways:

— They allow infinite support, since permission sets from Definition 2.7 need not be finite.

— They allow (some) infinite permutations, since permutations from Definition 2.9 are generated as a group by swappings and by infinite shift permutations, thus giving ∀-quantification extra power as discussed in Subsection 2.7.

The main results are soundness (Theorem 3.30) and completeness (Theorem 3.45). The main definitions are of permissive-nominal sets in Definition 3.4, and of the interpretations of terms and propositions in Definitions 3.20 and 3.25 respectively.

The permissive-nominal development here resembles that in [Gabbay and Pitts 2001]. Definition 3.4 is a little subtle because we ignore infinite permutations when we determine support, whereas equivariance from Definition 3.16 means commuting with all permutations.

3.1. Permissive-nominal sets

Recall P the set of all permutations from Definition 2.9.

Definition 3.1

A set with a permutation action X is a pair (|X|, ·) of

— a carrier set |X| and

— a group action on the carrier set (P × |X|) →|X|, written infix as π·x. So, id·x = x and π·(π′·x) = (π ◦π′)·x for every π and π′ and every x ∈|X|.

Definition 3.2

Say a set of atoms A ⊆A supports x ∈|X| when for all finite permutations π, if π(a) = a for all a ∈A then π·x = x.

Thus, if a permission set S supports x and ∀a∈S.π(a) = π′(a) then π·x = π′·x.

Remark 3.3

P contains infinite as well as finite permutations. In the next paragraph we construct an x that is supported by ∅ (so that π·x = x for all finite π ∈P) and yet shiftν(x) ≠ x. This observation is the same as fuzzy support from [Gabbay 2007b].

Recall the order fν on Aν from Definition 2.7 and consider

x = {π·(fν(0), fν(-1), fν(1), fν(-2), . . .) | π ∈Pfin}

the set of finite permutations of Aν written out in order, with the pointwise permutation action. Then π·x = x for every finite permutation, but shiftν·x ≠ x.

Definition 3.4

A permissive-nominal set is a set with a permutation action such that every element has a supporting permission set. X, Y will range over permissive-nominal sets.

Theorem 3.5

Suppose X is a permissive-nominal set. Then every x ∈|X| has a unique least supporting set supp(x) ⊆A.6

As a corollary, if π is finite and π(a) = a for all a ∈ supp(x) then π·x = x.

Theorem 3.5 is familiar from [Gabbay and Pitts 2001], but we do have to be a little bit careful since we are not working with nominal sets. It all works out:

Proof

The corollary is immediate given the definition of support (Definition 3.2).

Define A = ⋂{S | S permission set, supports x}. Also, choose some permission set S that supports x.

Suppose π is finite and π(a) = a for all a ∈A. Write a1, . . . , an for the atoms in nontriv(π)∩ S, in some order. Let b1, . . . , bn be some choice of fresh atoms (so bi ∉S ∪ nontriv(π) ∪A for 1 ≤i ≤n). Write τ = (b1 a1) ◦. . . ◦ (bn an). It is routine to check that (τ ◦π ◦τ)(a) = a for every a ∈S. Thus τ·(π·(τ·x)) = x. Now τ·x = x, and it follows by a routine manipulation that π·x = x as required.End of proof

Lemma 3.6

Suppose X is a permissive-nominal set and x ∈|X|. Then supp(π·x) = π·supp(x) (Definition 2.19).

Proof

By a routine calculation using the group action.End of proof

Corollary 3.7

Suppose X is a permissive-nominal set and x ∈|X|. Suppose b ∉ supp(x). Then (b a)·x = x implies a ∉ supp(x).

Proof

Suppose b ∉ supp(x). We prove the contrapositive. Suppose a ∈ supp(x). By Lemma 3.6 supp((b a)·x) = (b a)·supp(x). By our suppositions, (b a)·supp(x) ≠ supp(x). It follows that (b a)·x ≠ x.End of proof

3.2. Examples of permissive-nominal sets

3.2.1. Atoms

Definition 3.8

A the set of atoms can be considered a permissive-nominal set with a natural permutation action π·a = π(a).

The set {0, 1} can be considered a permissive-nominal set with the natural trivial permutation action π·x = x for all π ∈P and x ∈{0, 1}.

In the cases of A and {0, 1} only, we will be lax about the distinction between the set, and the permissive-nominal set with its natural permutation action.

3.2.2. Atoms-abstraction

Definition 3.9

Suppose X is a permissive-nominal set and Aν is a set of atoms. 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
Remark 3.10

In the definition of [a]x in Definition 3.9 recall that by our permutative convention b ≠ a. An equivalent and more compact way of writing this is [a]x = {(π(a), π·x) | π ∈ fix(supp(x)\{a})} where fix(A) = {π | ∀a∈A.π(a) = a}.

Lemma 3.11

(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′, for a, a′∈Aν and x, x′∈|X|.

3.2.3. Product

Definition 3.12

If Xi are permissive-nominal sets for 1 ≤i ≤n then define X1 × . . . × Xn by:

|X1 × . . . × Xn| = |X1| × . . . × |Xn| π·(x1, . . . , xn) = (π·x1, . . . , π·xn)
Lemma 3.13

— supp(a) = {a}.

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

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

Proof

Proofs are as in [Gabbay and Pitts 2001] or [Gabbay 2011b].End of proof

3.3. Interpretation and soundness

3.3.1. Interpretation of signatures

Definition 3.14

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

A (PNL) interpretation or model I for (A, B) consists of an assignment of a nonempty permissive-nominal set τI to each τ ∈B.7

We extend an interpretation I to sorts by:

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

Note in Definition 3.14 that a base sort τ is interpreted by a permissive-nominal set τI given in the interpretation, whereas a name sort ν must be interpreted by its corresponding set of atoms Aν as fixed in Definition 2.7. This is part of a nominal ‘slogan’ that atoms are interpreted by themselves.

Definition 3.16

Suppose X and Y are sets with a permutation action. Call a function f from |X| to |Y| equivariant when

∀π ∈P.∀x ∈|X|.π·(f(x)) = f(π·x). (equivariance for functions)

Lemma 3.17

If f from |X| to |Y| is equivariant then supp(f(x)) ⊆ supp(x) for all x ∈|X|.

Proof

If π ∈ fix(supp(x)) then π·f(x) = f(π·x), and if π is finite then π·x = x.End of proof

Definition 3.18

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

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

— An interpretation for the sort-signature (A, B) (Definition 3.14).

— For every f ∈F with ar(f) = (α)τ an equivariant function fI from ⟦α⟧I to ⟦τ⟧I (Definition 3.16).

— For every P ∈P with ar(P) = α a finite equivariant function PI from ⟦α⟧I to {0, 1} (Definition 3.8).

Definition 3.19

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.

3.3.2. Interpretation of terms

Definition 3.20

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 3.21

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

Proof

By a routine induction on r.End of proof

Lemma 3.22

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

Proof

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

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

Lemma 3.23

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.20. By assumption in Definition 3.19 supp(ς(X)) ⊆ pmss(X).

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

3.3.3. Interpretation of propositions

Definition 3.24

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 a function ς[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 3.25

Suppose that 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)}
Lemma 3.26

⟦φ⟧Iς = ⟦π·φ⟧Iς always.

Proof

By induction on φ. We consider two cases:

— The case ∀X.φ. Suppose ⟦∀X.φ⟧Iς = 1. This means that ⟦φ⟧Iς[X::=x] = 1 for all x ∈ ⟦α⟧I such that supp(x) ⊆ pmss(X). By inductive hypothesis ⟦π·φ⟧Iς[X::=x] = 1 for all x ∈ ⟦α⟧I such that supp(x) ⊆ pmss(X). Therefore ⟦∀X.π·φ⟧Iς = 1. The result follows, since π·(∀X.φ) = ∀X.π·φ.

— The case P(r). We have ⟦P(r)⟧Iς = PI(⟦r⟧Iς). As PI is equivariant, we get ⟦P(r)⟧Iς = PI(π·⟦r⟧Iς). By Lemma 3.22 π·⟦r⟧Iς = ⟦π·r⟧Iς. Thus ⟦P(r)⟧Iς = PI(⟦π·r⟧Iς) = ⟦π·P(r)⟧Iς.End of proof

Lemma 3.27

— ⟦r⟧Iς[X::=⟦t⟧Iς] = ⟦r[X::=t]⟧Iς.

— ⟦φ⟧Iς[X::=⟦t⟧Iς] = ⟦φ[X::=t]⟧Iς.

Proof

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

— The case of ⟦π·X⟧Iς[X::=t]. We reason as follows:

⟦π·X⟧Iς[X::=⟦t⟧Iς] = π·⟦t⟧IςDefinition 3.20= ⟦π·t⟧IςLemma 3.22= ⟦(π·X)[X::=t]⟧IςDefinition 2.35.

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

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

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

3.3.4. Validity and soundness

Definition 3.29 (Validity).

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.

Theorem 3.30 (Soundness).

If Φ ⊢ Ψ is derivable, then it is valid in all interpretations.

Proof

By induction on derivations (Figure 1). The case of (Ax) uses Lemma 3.26. The case of (∀L) uses Lemma 3.27. The case of (∀R) uses Lemma 3.28. Other rules are routine by unpacking definitions.End of proof

3.4. Completeness

In this subsection we prove Theorem 3.45: a converse to Theorem 3.30, that if φ is valid in all models, then φ it is derivable.

For this subsection fix the following data:

— A signature S = (A, B, F, P, ar).

— A formula φ such that ⊬φ.

We will construct an interpretation I and a valuation ς (Definition 3.14) such that ⟦φ⟧Iς = 0. This suffices to prove the result.

3.4.1. Maximally consistent set of propositions

Definition 3.31

Choose a fixed but arbitrary enumeration of propositions ξ1, ξ2, ξ3, ...

Define Φ1 = {¬φ}. For each i ≥ 1 we define Φi+1 as follows:

— If Φi ⊢ξi then write ξ = ξi.

— If Φi ⊢¬ξi then write ξ = ¬ξi.

— If Φi ⊬ξi and Φi ⊬¬ξi then write ξ = ξi.

There are now two cases:

— If ξ has the form ¬∀X.ξ′ then we define Φi+1 = Φi ∪{ξ, ¬ξ′[X::=Z]} where Z is some fixed but arbitrary choice of unknown that is not free in any proposition in Φi and is such that pmss(Z) = pmss(X) and sort(Z) = sort(X).

— Otherwise, we define Φi+1 = Φi ∪{ξ}.

Finally, we define Φω by Φω = ⋃i Φi.

Lemma 3.32

For every i, Φi ⊬⊥.

Proof

By induction on i:

— By definition Φ1 = {¬φ}. As ⊬φ, we have ¬φ ⊬⊥

— Suppose Φi ⊬⊥. Either Φi+1 = Φi ∪{¬ξ} or Φi+1 = Φi ∪{¬ξ, ¬ξ′[X::=Z]}—we consider the first, simpler case; the second case is similar. Suppose Φi, ξ ⊢⊥. It follows that Φi ⊢¬ξ. So we are not in the third case of Definition 3.31 and we are either in the first or the second. So Φi ⊢ξ and thus Φi ⊢⊥; a contradiction.End of proof

Lemma 3.33

Φω ⊬⊥.

Proof

Assume Φω ⊢⊥. So there exists a finite subset Γ of Φω such that Γ ⊢⊥. As Γ is finite it is included in some Φi, and Φi ⊢⊥, contradicting Proposition 3.32.End of proof

Lemma 3.34

For every ξ, at least one of ξ ∈ Φω and ¬ξ ∈ Φω holds.

Proof

We check of Definition 3.31 that for every i, either ξi ∈ Φi+1 or ¬ξi ∈ Φi+1. The result follows.End of proof

Lemma 3.35

For every ξ, if ¬∀X.ξ ∈ Φω then there exists a Z such that ¬ξ[X::=Z] ∈ Φω.

Proof

There exists an i such that ξi = ¬∀X.ξ. Since Φω ⊢ξi and Φω ⊬⊥, we have that Φω ⊬¬ξi, and so Φi ⊬¬ξi. Thus Φi+1 = Φi ∪{¬∀X.ξ, ¬ξ[X::=Z]}. The result follows.End of proof

Lemma 3.36

If Φω ⊢φ then φ ∈ Φω.

Proof

As, by Lemma 3.33, Φω ⊬⊥, if Φω ⊢φ then ¬φ ∉ Φω. Thus by Lemma 3.34, φ ∈ Φω.End of proof

Corollary 3.37

(1) (φ ⇒ψ) ∈ Φω if and only if (φ ∉ Φω or ψ ∈ Φω).

(2) ∀X.φ ∈ Φω if and only if (for every r such that r : sort(X) and fa(r) ⊆ pmss(X), φ[X::=r] ∈ Φω).

Proof

(1) Suppose (φ ⇒ψ) ∈ Φω and φ ∈ Φω. Then Φω ⊢ψ and so by Lemma 3.36 ψ ∈ Φω. Suppose φ ∉ Φω. By Lemma 3.34 ¬φ ∈ Φω. So Φω ⊢¬φ and therefore Φω ⊢φ ⇒ψ. By Lemma 3.36 (φ ⇒ψ) ∈ Φω. Suppose ψ ∈ Φω. Then Φω ⊢ψ and so Φω ⊢φ ⇒ψ. By Lemma 3.36 (φ ⇒ψ) ∈ Φω.

(2) Suppose ∀X.φ ∈ Φω. By Lemma 3.36, if r : sort(X) and ∀(r) ⊆ pmss(X) then φ[X::=r] ∈ Φω. Conversely, suppose φ[X::=r] ∈ Φω for every r such that r : sort(X) and ∀(r) ⊆ pmss(X). We proceed by contradiction: suppose ∀X.φ ∉ Φω. By Lemma 3.34 ¬∀X.φ ∈ Φω and by Lemma 3.35, there exists a Z such that ¬φ[X::=Z] ∈ Φω. So Φω ⊢¬φ[X::=Z], and so Φω ⊢φ[X::=Z], and so Φω ⊢⊥, contradicting Lemma 3.33.End of proof

3.4.2. The term model

Definition 3.38

Define I by:

— ⟦α⟧I = {r | r : α}.

— fI maps r to f(r).

— PI maps r1, . . . , rn to 1 if P(r1, . . . , rn) ∈ Φω and to 0 otherwise.

Define ς by

ς(X) = X.

We endow ⟦α⟧I with a permutation action given by the action on terms.

Lemma 3.39

supp(r) = fa(r).

As a corollary, ⟦α⟧I from Definition 3.38 is a permissive-nominal set.

Proof

We prove two subset inclusions:

— Proof that supp(r) ⊆ fa(r). By Lemma 2.29, if π(a) = a for all a ∈ fa(r) then r = π·r. It follows by the definition of support (Theorem 3.5) that supp(r) ⊆ fa(r).

— Proof that fa(r) ⊆ supp(r). Suppose a ∈ fa(r). Choose some fresh b (so b ∉ fa(r) ∪ supp(r)). By Lemma 2.21 fa((b a)·r) = (b a)·fa(r). Since (b a)·fa(r) ≠ fa(r) it follows using Lemma 2.27 that r ≠ (b a)·r. The result follows by the first part of this result and by Corollary 3.7.

The corollary is immediate, unpacking Definition 3.2.End of proof

Lemma 3.40

(1) If ar(f) = (α)τ then fI is well-defined, equivariant, and maps ⟦α⟧I to ⟦τ⟧I.

(2) If ar(P) = α then PI is well-defined, equivariant, and maps ⟦α⟧I to {0, 1}.

Proof

(1) The only (very) slightly non-trivial part is equivariance. We reason as follows:

π·fI(r) = π·f(r) Definition 3.20= f(π·r) Definition 2.17= fI(π·r) Definition 3.20

(2) The case of P is similar.End of proof

Proposition 3.41

I is an interpretation of the signature S = (A, B, F, P, ar) which we fixed at the beginning of this subsection. In addition, ς is a valuation to I.

Proof

By Lemma 3.39 each ⟦α⟧I is a permissive-nominal set. By Lemma 3.40 for each f : (α)τ ∈F, fI is an equivariant map from ⟦α⟧I to ⟦τ⟧I and for each P : α ∈P, PI is a finite equivariant function from ⟦α⟧I to {0, 1}.

By construction ς(X) ∈⟦sort(X)⟧I always. By Lemma 3.39 supp(ς(X)) = supp(X) ⊆ pmss(X) always.

The result follows.End of proof

Lemma 3.42

⟦r⟧Iς = r.

Proof

By a routine induction on the definition of ⟦r⟧Iς in Definition 3.20. We consider just one case:

— The case of ⟦π·X⟧Iς. We reason as follows:

⟦π·X⟧Iς = π·ς(X) Definition 3.20= π·X Definition 3.38.End of proof
Lemma 3.43

⟦ξ⟧Iς = 1 if and only if ξ ∈ Φω.

Proof

By induction on the definition of ⟦ξ⟧Iς (Definition 3.25):

— The case of ⟦P(r)⟧Iς. We reason as follows:

⟦P(r)⟧Iς = 1 ⇔PI(⟦r⟧Iς) = 1 Definition 3.25⇔PI(r) = 1 Lemma 3.42⇔P(r) ∈ΦωDefinition 3.38

— The case of ⟦⊥⟧Iς. By definition ⟦⊥⟧Iς = 0. By part 1 of Corollary 3.37, ⊥∉ Φω.

— The case of ⟦φ ⇒ψ⟧Iς. We reason as follows: ⟦φ ⇒ψ⟧Iς = 1 ⇔ ⟦φ⟧Iς = 0 or ⟦ψ⟧Iς = 1 Definition 3.25

⇔φ ∉Φω or ψ ∈Φωind. hyp.⇔φ ⇒ψ ∈ΦωCorollary 3.37, part 2

— The case of ⟦∀X.φ⟧Iς, where α = sort(X) and S = pmss(X).

⟦∀X.φ⟧Iς = 1 ⇔∀t ∈⟦α⟧I.supp(t) ⊆S ⇒⟦φ⟧Iς[X::=t] = 1 Definition 3.25⇔∀t ∈⟦α⟧I.supp(t) ⊆S ⇒⟦φ[X::=t]⟧Iς = 1 Lems. 3.28, 3.42⇔⟦φ[X::=t]⟧Iς = 1 every t : α s.t. fa(t) ⊆S Lem. 3.39⇔φ[X::=t] ∈Φω every t : α s.t. fa(t) ⊆S ind. hyp.⇔∀X.φ ∈ΦωCor. 3.37, part 4End of proof
Lemma 3.44

If ⊬φ, then there exists a model I and a valuation ς such that ⟦φ⟧Iς = 0.

Proof

As ¬φ∈Φ0⊆Φω and Φω⊬⊥, we have φ∉Φω. By Lemma 3.43, we get ⟦φ⟧Iς = 0.End of proof

As a corollary we get Theorem 3.45:

Theorem 3.45 (Completeness).

If φ is valid in all models, then φ is derivable.

4. SPECIFYING ARITHMETIC IN PERMISSIVE-NOMINAL LOGIC

We start by defining the sorts, term-formers, and proposition-formers of a signature ˙L which is suitable for finitely specifying arithmetic in PNL. We then specify its axioms and, in Subsection 4.2, we discuss them in detail.

4.1. The signature ˙L and the axioms

Definition 4.1

A signature ˙L suitable for writing out a PNL theory of first-order logic is given in Figure 2.

We introduce the following syntactic sugar:

— We may write subo([a]r, t) as r[a↦→t].

— We may write subι([a]r, t) as r[a↦→t].

— We may write both ≈ι and ≈o just as ≈.

Examples of this syntactic sugar in use, follow immediately below.

We assume one atomic sort ν and two base sorts ι and o. We assume term-formers and proposition-formers as follows: ˙0 : ι ˙succ : (ι)ι ∔: (ι, ι)ι ˙∗: (ι, ι)ι˙⊥: o ˙⇒: (o, o)o˙∀: ([ν]o)o ˙≈: (ι, ι)ovar : (ν)ι subι : ([ν]ι, ι)ι subo : ([ν]o, ι)o≈ι: (ι, ι) ≈o: (o, o) ϵ : (o)
Fig. 2: Signature suitable for a PNL specification of arithmetic
(≈2) ∀X′, X, Y ′, Y.(X′≈X∧Y ′≈Y ) ⇒X′ op Y ′ ≈X op Y op∈{∔, ˙∗, ˙⇒, ˙≈}(≈1) ∀X′, X. X′≈X ⇒op(X′) ≈op(X) op∈{ ˙succ}(≈0) ∀X. X ≈X(≈˙∀) ∀Z′, Z. Z′≈Z ⇒˙∀([a]Z′) ≈˙∀([a]Z)(≈sub) ∀X′, X, Y ′, Y.(X′≈X∧Y ′≈Y ) ⇒op([a]X′, Y ′) ≈op([a]X, Y ) op∈{subι, subo}(≈o) ∀Z′, Z. Z′≈Z ⇒(ϵ(Z′) ⇔ϵ(Z))(≈ι) ∀X′, X. X′≈X ⇒ϵ(X′ ˙≈X) We fill in sorts as appropriate. Thus, ˙⊥≈o ˙⊥whereas 0 ≈ι 0, and so on. The permission sets of all variables are equal to A<, and a ∈A<.
Fig. 3: EQU: axioms for equality as a PNL theory
(subvar) ∀X. var(a)[a↦→X] ≈X(sub#) ∀X, Z. Z[a↦→X] ≈Z (pmss(Z) = (b a)·A<)(sub ˙succ) ∀X′, X. ˙succ(X′)[a↦→X] ≈ ˙succ(X′[a↦→X])(sub∔) ∀X′′, X′, X. (X′′ ∔X′)[a↦→X] ≈(X′′[a↦→X] ∔X′[a↦→X])(sub˙∗) ∀X′′, X′, X. (X′′ ˙∗X′)[a↦→X] ≈(X′′[a↦→X] ˙∗X′[a↦→X])(sub ˙⇒) ∀X′′, X′, X. (X′′ ˙⇒X′)[a↦→X] ≈(X′′[a↦→X] ˙⇒X′[a↦→X])(sub ˙≈) ∀X′′, X′, X. (X′′ ˙≈X′)[a↦→X] ≈(X′′[a↦→X] ˙≈X′[a↦→X])(sub˙∀) ∀X, Z. (˙∀([b]Z))[a↦→X] ≈˙∀([b](Z[a↦→X])) (pmss(Z) = (b a)·A<)(subid) ∀X. X[a↦→var(a)] ≈X a ∈A< and b ∉A<. The permission set of X′′, X′, and X is equal to A<. The permission set of Z is equal to (b a)·A< (Definition 2.19).
Fig. 4: SUB: axioms for substitution as a PNL theory

Equality. Axioms for equality ≈: (ι, ι) and equality ≈: (o, o) are given in Figure 3.

Substitution. Axioms for substitution subι and subo are given in Figure 4.

We arguably abuse notation in Figure 4 when we use variables of sort ι and o as appropriate not necessarily giving them distinct names (e.g. in (sub∗) X has sort ι, whereas in (sub˙⇒) we use another variable also written X with sort o).

First-order logic. Axioms reflecting first-order formulas (in a shallow sense) as terms in PNL (the ˙⊥, ˙⇒, and ˙∀) are given in Figure 5.

Arithmetic. Given EQU, SUB, and FOL, it is not hard to write axioms for arithmetic in PNL. This is in Figure 6. Later on in Theorem 5.21 we prove that this is an axiomatisation of arithmetic in PNL.

( ˙⇒) ∀Z′, Z. ϵ(Z′ ˙⇒Z) ⇔(ϵ(Z′) ⇒ϵ(Z))(˙∀) ∀Z.(ϵ(˙∀([a]Z)) ⇔∀X.ϵ(Z[a↦→X]))( ˙⊥) ϵ( ˙⊥) ⇒⊥ Here Z′ and Z have sort o, permission set A<, and a ∈A<.
Fig. 5: FOL: axioms for first-order formulas as a PNL theory
(PS0) ∀X. ˙succ(X) ≈˙0 ⇒⊥(PSS) ∀X′, X. ˙succ(X′) ≈ ˙succ(X) ⇒X′ ≈X(P+0) ∀X. X ∔˙0 ≈X(P+succ) ∀X′, X. X′ ∔ ˙succ(X) ≈ ˙succ(X′) ∔X(P∗0) ∀X. X ˙∗˙0 ≈˙0(P∗succ) ∀X′, X. X′ ˙∗ ˙succ(X) ≈(X′ ˙∗X) ∔X(PInd) ∀Z. (ϵ(Z[a↦→˙0]) ⇒(∀X.(ϵ(Z[a↦→X]) ⇒ϵ(Z[a↦→˙succ(X)])))⇒∀X.ϵ(Z[a↦→X])) All variables have permission set A<, and a ∈A<.
Fig. 6: ARITH: axioms for arithmetic as a PNL theory

4.2. Comments on the axioms

Remark 4.2

In [Gabbay and Mathijssen 2008a] capture-avoiding substitution is equationally axiomatised using nominal algebra in the style of SUB. Soundness and completeness are proved, so providing some formal sense in which the axioms of SUB are ‘right’.

In [Gabbay and Mathijssen 2008b] first-order logic is equationally axiomatised using nominal algebra (so the axioms involve only equality). The axioms of FOL are not based on those of [Gabbay and Mathijssen 2008b]. In FOL, we take advantage of the stronger language provided by PNL; Because PNL is already a first-order logic, we can use ⊥, ⇒, and ∀ directly to capture the behaviour of ˙⊥, ˙⇒, and ˙∀. In [Gabbay and Mathijssen 2008b] we had to work a little harder because the ambient logic, nominal algebra, was purely equational.

Remark 4.3

Instead of the axioms for equality EQU, we could directly extend PNL by adding derivation rules Figure 1 as follows:

Φ, r ≈s, φ[X::=r], φ[X::=s] ⊢Ψ (fa(r) ∪fa(s) ⊆pmss(X)) (≈S) Φ, r ≈s, φ[X::=r] ⊢ΨΦ, r ≈r ⊢Ψ(≈R)Φ ⊢Ψ
Remark 4.4

Every unknown has a sort, and a permission set.

Different choices of permission set may yield logically equivalent results. For example, in (sublam) it is not vital that pmss(Z) is exactly (b a)·A<. The important point is that a ∉ pmss(Z).

Similarly, in (subapp) it is not vital that pmss(X′′) = pmss(X′); when we use the axiom we can instantiate X′′ and X′ to r′′ and r′ such that fa(r′′) ≠ fa(r′), and conversely if we take pmss(X′′) ≠ pmss(X′) then we can still instantiate X′′ and X′ to r′′ and r′ such that fa(r′′) = fa(r′) ⊆ pmss(X′′) ∩ pmss(X′). More on this in Section 9.

5. A THEORY OF ARITHMETIC IN FIRST-ORDER LOGIC

We now recall first-order logic L and write Peano arithmetic in L. Our two main theorems are:

— Theorem 5.6 which states that the PNL theory of first-order logic written in ˙L—in symbols this is EQU ∪ SUB ∪ FOL—soundly interprets first-order logic L; and

— Theorem 5.21 which states that the PNL theory of arithmetic in the PNL theory of first-order logic, soundly and completely interprets ordinary Peano arithmetic in written in L.8

5.1. First-order logic L

We will use the atoms Aν from ˙L in Section 4 as variables of our first-order logic (this is not necessary, but it is convenient). So for this section, a, b, c, . . . will range over distinct atoms in Aν.

Definition 5.1

Define terms and formulas of L by:

t ::= a | 0 | succ(t) | t + t | t ∗t ξ ::= t ≈t | ⊥| ξ ⇒ξ | ∀a.ξ

Substitution t′[a::=t] and ξ[a::=t] is as usual for first-order logic. We write sequents Ξ ⊢χ where Ξ and χ are sets of formulas. Derivability is as usual for first-order logic.

Definition 5.2

Define a mapping (-). from terms and formulas of L to terms of ˙L by:

(a). = a (0). = ˙0(succ(t)). = ˙succ((t).) (t′ + t). = (t′). ∔(t).(t′ ∗t). = (t′). ˙∗(t).(t′ ≈t). = (t′). ˙≈(t).(⊥). = ˙⊥(ξ′ ⇒ξ). = (ξ′). ˙⇒(ξ).(∀a.ξ). = ˙∀[a](ξ).
Definition 5.3

Extend (-). to first-order logic sequents Ξ ⊢χ as follows:

(Ξ ⊢χ). = ϵ(˙∀[a1] . . . ˙∀[an]((ξ1 ∧. . . ∧ξk) ⇒(χ1 ∨. . . ∨χl)).)

Here, Ξ = {ξ1, . . . , ξk}, χ = {χ1, . . . , χl}, and the free variables of Ξ and χ are {a1, . . . , an} (in some order).

Notation 5.4

Write S for EQU ∪ SUB ∪ FOL.

Lemma 5.5

S ⊢ (t′[a::=t]). ≈ (t′).[a↦→(t).] and

S ⊢(ξ[a::=t]). ≈(ξ).[a↦→(t).].
Proof

By routine inductions on t and ξ.End of proof

Theorem 5.6 (Correctness).

If Ξ ⊢χ is derivable in first-order logic then S ⊢ (Ξ ⊢χ). is derivable in PNL.

Proof

By a long but routine inspection we can check that EQU, SUB, and FOL allow us to model the behaviour of ‘real’ first-order logic. We use Lemma 5.5.End of proof

5.2. Interpretation of first-order logic

We recall the usual definition of interpretations in first-order logic:

Definition 5.7

A (first-order logic) interpretation M is a carrier set M, and elements

0M ∈M, succM ∈M →M, +M ∈(M × M) →M, and ∗M ∈(M × M) →M.

It is convenient to fix some M from here until Theorem 5.21.

Definition 5.8

Define Valu𝔸ν (M) by:

Valu𝔸ν(M) = {ε ∈Aν →M | ∃A ⊆Aν.A finite ∧∀a, b ∉A.ε(a) = ε(b)}

Call elements of Valu𝔸ν (M) Aν-valuations (to M). ε will range over Aν-valuations.

If x ∈M write ε[a::=x] for the valuation mapping b to ε(b) and mapping a to x:

ε[a::=x](a) = x ε[a::=x](b) = ε(b)

Give ε ∈ Valu𝔸ν (M) and X ⊆ Valu𝔸ν (M) a pointwise permutation action:

(π·ε)(a) = ε(π-1(a)). π·X = {π·ε | ε ∈X}.

U, V will range over finitely-supported subsets of Valu𝔸ν (M)—so there exists some finite A ⊆Aν such that for all π, if π(a) = a for all a ∈A then π·U = U.

Remark 5.9

Valu𝔸ν (M) would normally just be called ‘the set of valuations’. We are more specific since we separately also have valuations on unknowns X (Definition 3.19).

PNL atoms are serving as variable symbols of L. To conveniently apply nominal techniques, it is useful to restrict to valuations that are finite in the sense given in Definition 5.8. In any case, any term or formula will only contain finitely many atoms.

Definition 5.10

We extend the interpretation to first-order logic syntax as follows:

⟦a⟧Mε = ε(a) ⟦0⟧Mε = 0M⟦succ(t)⟧Mε = succM(⟦t⟧Mε )⟦t′ + t⟧Mε = +M(⟦t′⟧Mε , ⟦t⟧Mε )⟦t′ ∗t⟧Mε = ∗M(⟦t′⟧Mε , ⟦t⟧Mε )⟦⊥⟧Mε = 0 ⟦ξ′ ⇒ξ⟧Mε = max{1−⟦ξ′⟧Mε , ⟦ξ⟧Mε }⟦∀a.ξ⟧Mε = min{⟦ξ⟧Mε[a::=x] | x ∈M}⟦t′ ≈t⟧Mε = 1 if ⟦t′⟧Mε = ⟦t⟧Mε and 0 otherwise
Definition 5.11

Call the formula ξ valid in M when ⟦ξ⟧Mε = 1 for all ε.

Call ξ1, . . . , ξk ⊢χ1, . . . , χl valid in M when (ξ1 ∧. . . ∧ξk) ⇒ (χ1 ∨. . . ∨χl) is valid.

(ps0) ∀a. succ(a) ≈0 ⇒⊥(pss) ∀a′, a. succ(a) ≈succ(a′) ⇒a ≈a′(p+0) ∀a. a + 0 ≈a (p+succ) ∀a′, a. a′ + succ(a) ≈succ(a′) + a (p∗0) ∀a. a ∗0 ≈0 (p∗succ) ∀a′, a. a′ ∗succ(a) ≈(a′ ∗a) + a (pind) ξ[a::=0] ⇒ ∀a.(ξ ⇒ξ[a::=succ(a)]) ⇒ ∀a.ξ (every ξ, every a)
Fig. 7: arithmetic: axioms for arithmetic in first-order logic

5.3. A theory of arithmetic in L

Definition 5.12

Define a first-order theory of arithmetic by the axioms in Figure 7. An interpretation is a model of arithmetic when ⟦ξ⟧M = 1 for ξ each of (ps0), (pss), (p+0), (p+succ), (p∗0), (p∗succ), and every instance of (pind).

Remark 5.13

(pind) the induction axiom-scheme is of course of particular interest. We therefore unpack what its validity

⟦ξ[a::=0] ⇒∀a.(ξ ⇒ξ[a::=succ(a)]) ⇒∀a.ξ⟧M = 1 (every ξ, every a)

means, in a little more detail. For every a and ξ:

— If ⟦ξ[a::=0]⟧Mε = 1, and

— if for every x ∈M, ⟦ξ⟧Mε[a::=x] = 1 implies that ⟦ξ[a::=succ(a)]⟧Mε[a::=x] = 1,

— then for every x ∈M, ⟦ξ⟧Mε[a::=x] = 1.

In (pind) we take ‘every a’, and in (PInd) we do not. This is because in (PInd), a is α-convertible,

5.4. Building an interpretation for ˙L out of one for L

Recall the PNL signature ˙L from Section 4. Suppose M is a model of L. We use it to build an interpretation N of ˙L.

Definition 5.14

Extend L to L+M where we add all elements of M as constants, and extend the interpretation to interpret these constants as themselves in M. (So if x ∈M then x is a constant symbol in L+M and ⟦x⟧Mε = x.)

Define an Aν-valuation ε0 ∈ Valu𝔸ν (M) by

ε0(a) = 0Malways.

If t is a term, we write ⟦t⟧M for the function λε.⟦t⟧Mε . If ξ is a formula, we write ⟦ξ⟧M for the function λε.⟦ξ⟧Mε .

We now define an interpretation N for ˙L. We give a denotation to the base sorts ι and o of ˙L, as follows:

ιN = {⟦t⟧M | t a term of L+M} π·⟦t⟧M = ⟦π·t⟧MoN = {⟦ξ⟧M | ξ a formula of L+M} π·⟦ξ⟧M = ⟦π·ξ⟧M

We give a denotation to the term-formers and proposition-formers of ˙L, as follows:

varN a ε = ε(a) ˙0N ε = 0M( ˙succN u) ε = succM(uε)∔N (u, v) ε = +M(uε, vε)˙∗N (u, v) ε = ∗M(uε, vε)subNι ([a]u, v) ε = u(ε[a::=vε]) ˙⊥N ε = 0subNo ([a]u, v) ε = u(ε[a::=vε]) ˙⇒N (U, V ) ε = max{1−Uε, V ε} ˙∀N ([a]U) ε = min{U(ε[a::=x]) | x ∈M} ˙≈N (u, v) ε = ≈M(uε, vε)≈Nι (u, v) = 1 if u=v and 0 otherwise≈No (U, V ) = 1 if U=V and 0 otherwise ϵN U = U(ε0)

Here, u and v range over ιN and U and V range over oN. We insert brackets where this might increase clarity.

Remark 5.15

For the reader’s convenience we indicate the types of some of the symbols above in an informal ‘crib sheet’:

ε : Aν→M varN : Aν→(Aν→M)→Mu : (Aν→M)→M U : (Aν→M)→{0, 1}0M : M˙0N : (Aν→M)→M≈M : M 2→{0, 1} ˙≈N : ((Aν→M)→M)2→(Aν→M)→{0, 1} ˙∀N : [Aν]((Aν→M)→{0, 1}) →(Aν→M)→{0, 1}

This crib sheet is only indicative since, for instance, ε is not any function in Aν→M (see Definition 5.8).

Lemma 5.16

(1) ⟦t′[a::=t]⟧Mε = ⟦t′⟧Mε[a::=⟦t⟧Mε ].

(2) ⟦ξ[a::=t]⟧Mε = 1 if only if ⟦ξ⟧Mε[a::=⟦t⟧Mε ] = 1.

Lemma 5.17

The following equalities all hold:

varN(a) = ⟦a⟧M˙0N = ⟦0⟧M˙succN(⟦t⟧M) = ⟦succ(t)⟧M∔N(⟦t′⟧M, ⟦t⟧M) = ⟦t′ + t⟧M˙∗N (⟦t′⟧M, ⟦t⟧M) = ⟦t′ ∗t⟧MsubNι([a]⟦t′⟧M, ⟦t⟧M) = ⟦t′[a::=t]⟧MsubNo([a]⟦ξ⟧M, ⟦s⟧M) = ⟦ξ[a::=s]⟧M˙⊥N = ⟦⊥⟧M˙⇒N(⟦ξ′⟧M, ⟦ξ⟧M) = ⟦ξ′ ⇒ξ⟧M˙∀N([a]⟦ξ⟧M) = ⟦∀a.ξ⟧M˙≈N(⟦r⟧M, ⟦s⟧M) = ⟦r ≈s⟧M
Proof

We compare Definitions 5.14 and 5.10. Most cases are immediate; we consider only the slightly less trivial ones:

varN(a) = (λa.λε.ε(a))a Definition 5.14= (λa.⟦a⟧M)a Definition 5.10= ⟦a⟧MfactsubNι([a]⟦t′⟧M, ⟦t⟧M) = λε.⟦t′⟧M(ε[a::=⟦t⟧Mε]) Definition 5.14= λε.⟦t′[a::=t]⟧MLemma 5.16

Other cases are no harder.End of proof

Lemma 5.18

N (Definition 5.14) is a PNL interpretation.

Proof

We must check that:

— ιN and oN are permissive-nominal sets. By routine calculations. (In fact, ιN and oN are nominal sets; that is, their elements all have finite support.)

— The functions defined in Definition 5.14 map elements of ιN, oN, [A]ιN, and [A]oN correctly to the appropriate sets. By Lemma 5.17.

— ϵN is equivariant from oN to {0, 1}. By routine calculations using the fact that (a b)·ε0 = ε0.End of proof

Lemma 5.19

If (Ξ ⊢χ). is valid in N, then Ξ ⊢χ is valid in M.

Proof

We calculate that if (Ξ ⊢χ). is valid in N, then

⟦(ξ1 ∧. . . ∧ξk) ⇒(χ1 ∨. . . ∨χl)⟧Mε0 = 1

But the proposition written out above is closed, so for all valuations ε, ⟦(ξ1 ∧. . . ∧ξk) ⇒ (χ1 ∨. . . ∨χl)⟧Mε = 1.End of proof

Recall from Notation 5.4 that we write S for EQU∪SUB∪FOL. Recall also from Definition 5.2 the mapping (-). from first-order logic L to PNL terms.

Proposition 5.20

N is a model of S ∪ ARITH.

Proof

By a routine verification. We consider the axiom (˙∀) from Figure 5. We unpack definitions and see that we must prove that for every ξ in L+M,

— ∀x ∈M.ε0[a::=x] ∈ ⟦ξ⟧N if and only if

— ε0[a::=⟦t⟧Nε0] ∈ ⟦ξ⟧N for every t a term of L+M.

This follows, because L+M has a constant symbol for every x ∈M. Validity of the other axioms is no harder.End of proof

Theorem 5.21

arithmetic, Ξ ⊢χ in first-order logic if and only if

S ∪ ARITH ⊢ (Ξ ⊢χ). in PNL.

Proof

We prove two implications. The top-to-bottom implication follows using Theorem 5.6.

For the bottom-to-top implication, we reason as follows: Suppose S ∪ ARITH ⊢ (Ξ ⊢χ). in PNL. Choose an arbitrary interpretation M of first-order logic that is a model of arithmetic, with carrier set M. By Soundness (Theorem 3.30) and Proposition 5.20, (Ξ ⊢χ). is valid in N. By Lemma 5.19 Ξ ⊢χ is valid in M. M was arbitrary, so by completeness of first-order logic [Shoenfield 1967, §4.2] it follows that Ξ ⊢χ is derivable.End of proof

6. MORE PNL THEORIES

So far we have built PNL and used it to finitely axiomatise arithmetic. In this section we briefly touch on how to express some known ‘nominal’ constructs within PNL.

6.1. Inductive types

Permissive-nominal logic can express the principles of nominal abstract syntax developed in [Gabbay and Pitts 2001].

Suppose a base sort ι, a name sort ν, and term-formers

var : ν →ι, app : (ι, ι) →ι, and lam : [ν]ι →ι.

Fix an unknown U : ι and for brevity write φ[U::=r] as φ(r) for every φ. Suppose an axiom-scheme, for every φ:

φ(var(a)) ⇒ ∀X.(φ(X) ⇒φ(lam([a]X))) ⇒ ∀X, Y.(φ(X) ⇒φ(Y ) ⇒app(X, Y )) ⇒ ∀X.(φ(X))

Here X and Y have sort ι and we make a fixed but arbitrary choice of atom a ∈ pmss(X).

We can also express this finitely, if we axiomatise a sort for predicates (as we did for arithmetic). Here is the axiom-scheme above made finite by using the theories EQU, SUB, and FOL from Section 4:

∀Z.ϵ(Z[a↦→var(a)]) ⇒ ∀X.(ϵ(Z[a↦→X]) ⇒ϵ(Z[a↦→lam([a]X))) ⇒ ∀X, Y.(ϵ(Z[a↦→X]) ⇒ϵ(Z[a↦→Y ]) ⇒ϵ(Z[a↦→app(X, Y )])) ⇒ ∀X.ϵ(Z[a↦→X])

6.2. The И quantifier

Nominal sets support the И-quantifier [Gabbay and Pitts 2001]. PNL also includes the И-quantifier; the way in which it does this is quite interesting, as we shall see in a moment.

И has some distinctive properties which are reflected in nominal logic (NL) and the logic of FM sets (FM):

∀x.(P(x) ⇒Иa.Q(a, x)) ================== ∀x.Иa.(P(x) ⇒Q(a, x))∀x.Иa.Иb.(b a)·x≈x =============================Иa.Иb.∀x.(a#x ⇒b#x ⇒(b a)·x≈x)

Here and below we write a double horizontal line for ‘is provably equivalent to’. И appears absent from Permissive-Nominal Logic (PNL). It is ‘hiding’ in the permission sets. Corresponding propositions are, where a, b ∉ pmss(X):

∀X.(P(X) ⇒Q(a, X)) ================= ∀X.(P(X) ⇒Q(a, X))∀X.(b a)·X ≈X ============= ∀X.(b a)·X ≈X

We see from these examples that two things are happening: first, freshness conditions are hard-coded into the syntax by permission sets—and second, so is the И-quantifier.

It is interesting to consider another example. In NL/FM:

Иa.P(a) ∧Иa.Q(b) ================Иa.Иb.(P(a) ∧Q(b))Иa.P(a) ∧Иa.Q(b) ==============Иa.(P(a) ∧Q(a))

Correspondingly in PNL we have:

P(a) ∧Q(b) ========= P(a) ∧Q(b)P(a) ∧Q(b) ========= P(a) ∧Q(a)

It is easy to use the rule (Ax) from Figure 1 to construct a derivation proving that P(a)∧Q(b) and P(a) ∧ Q(a) are indeed logically equivalent in Permissive-Nominal Logic.

The π in (Ax) expresses that truth is preserved by permutative renaming, or in symbols: ⊢φ ⇔π·φ always.

A permission set S can be viewed in two ways: as giving permission to instantiate using free atoms in S—but also as a form of И for the atoms not in S.

6.3. Freshness a#x and abstraction

PNL has a notion of syntactic freshness which we identify as a notion of ‘free atoms of’, and write fa(t) and fa(φ). Nominal sets also have a semantic notion of freshness a#x given by a ∉ supp(x).

As Lemma 3.23 demonstrates, intuitively if a is not free in t then a is fresh for the denotation of t. In symbols: a ∉ fa(t) ⇒a#⟦t⟧ (see [Gabbay 2012, Subsection 7.6] for a kind of converse).

To capture in syntax the effect of a freshness predicate for a name sort ν on a sort α, it suffices to assume EQU (or extend PNL with an equality primitive) and to assume a predicate # of arity (ν, α) with an axiom

∀X.(a#X ⇔(b a)·X ≈X).

Here X has sort α and a and b have sort ν, and a ∈ pmss(X) and b ∉ pmss(X). This is essentially equation 13 in [Gabbay and Pitts 2001], using permission sets to attain the effect of the И-quantifier. See also [Gabbay and Mathijssen 2009, Subsection 5.2] and [Gabbay and Mathijssen 2007, Theorem 5.5] where similar observations were expressed for nominal algebra.

Similarly atoms-abstraction [a]r can be axiomatised not using atoms-abstraction as a term-former abs : (ν, τ) with axiom ∀X.abs(b, (b a)·X) ≈ abs(a, X) where b ∉ pmss(X) (cf. [Gabbay and Mathijssen 2009, Subsection 5.1]).

However, it is worthwhile to provide atoms-abstraction as primitive in PNL because it gives us access to PNL α-equivalence which is a structural part of the PNL derivation system: to rename a in abs(a, X) into abs(b, (b a)·X) requires equality reasoning and axioms; to rename a in [a]X requires nothing but an α-conversion (in this paper, they are actually the same term).

7. CUT-ELIMINATION

Recall the (Cut) rule from Figure 1. In this section we prove that (Cut) is admissible in the presence of the other rules in Figure 1.

Definition 7.1

Suppose fa(r) ⊆ pmss(X) and r : sort(X). Define Φ[X::=r] by

Φ[X::=r] = {φ[X::=r] | φ ∈Φ}.

Lemmas 7.2 and 7.3 are proved by routine arguments like those in [Dowek et al. 2010; Urban et al. 2004]:

Lemma 7.2

(π·r)θ = π·(rθ).

Lemma 7.3

Suppose Y ∉ fV (t). Then

r[Y ::=u][X::=t] = r[X::=t][Y ::=u[X::=t]].
Lemma 7.4

Suppose fa(r) ⊆ pmss(X) and r : sort(X). Then

Φ ⊢Ψ implies Φ[X::=r] ⊢Ψ[X::=r].
Proof

By a routine induction on derivations. The case of (Ax) uses Lemmas 7.2 and 7.3. The case of (∀L) uses Lemma 7.3.End of proof

Lemma 7.5

(1) If there exists a derivation ∆ of Φ ⊢ψ, Ψ then there exists a derivation of Φ ⊢ π·ψ, Ψ.

(2) If there exists a derivation ∆ of Φ, φ ⊢ Ψ then there exists a derivation of Φ, π·φ ⊢ Ψ.

Proof

By a simultaneous induction on ∆. The case of (∀L) uses Lemma 7.2. (We need the simultaneous induction for (⇒L) and (⇒R), since parts of the proposition move between left and right.)End of proof

Notation 7.6

An instance of (Cut) rests on two sub-derivations. It is convenient to call them the left branch and right branch as illustrated:

··· Left branch Φ, φ ⊢Ψ··· Right branch Φ ⊢φ, Ψ(Cut)Φ ⊢Ψ
Theorem 7.7 (Cut-elimination).

If Φ ⊢ Ψ is derivable with a derivation that uses (Cut), then it is derivable with a derivation that does not use (Cut).

Proof

The proof is as for first-order logic. The only differences are a π in (Ax) and a side-condition fa(r) ⊆ pmss(X) in (∀L). These affect terms and have no effect on the structure of derivations; for the purposes of this proof they are irrelevant.

We commute instances of (Cut) upwards, as usual, following the method of [Dummett 1977, pages 139-145] or [Gabbay 2011a]. At each step, the following measure based on the depth of subderivations and the size of the cut formula, decreases:

— The size of the cut formula, and

— the longest path up the derivation the cut, that the formula persists,

lexicographically ordered.

— The commutation cases between rules for ⇒ and ∀ are as standard for first-order logic.

— The essential case for ⇒ is as standard.

— For the essential case for ∀, suppose the subderivation has the following form:

Φ, φ[X::=r] ⊢Ψ(∀L)Φ, ∀X.φ ⊢Ψ··· ∆ Φ ⊢φ, Ψ(∀R)Φ ⊢∀X.φ, Ψ(Cut)Φ ⊢Ψ

By Lemma 7.4 there is a derivation ∆[X::=r] of Φ ⊢φ[X::=r], Ψ. We eliminate the essential case as follows:

Φ, φ[X::=r] ⊢Ψ··· ∆[X::=r] Φ ⊢φ[X::=r], Ψ(Cut)Φ ⊢Ψ

— Suppose the subderivation has the following form:

(Ax)Φ, φ ⊢π·φ, Ψ··· ∆ Φ, π·φ ⊢Ψ(Cut)Φ, φ ⊢Ψ

We use Lemma 7.5 to obtain a derivation ∆′ of Φ, φ ⊢ Ψ (the transformations involved in the proof of Lemma 7.5 do not increase the inductive measure).End of proof

8. RELATED WORK

8.1. Other ‘nominal’ syntaxes and logics

Compared to other ‘nominal’ logics, PNL emphasises ergonomics. When we use PNL to axiomatize and build proofs in arithmetic or in set theory, we want our hypotheses to speak about natural numbers or sets, not to speak about atoms and freshness.

Thus, although notions of atom and freshness are important, they should be implicit; i.e. handled automatically by the logic. This is the purpose of permission sets, which allow us to handle freshness and α-renaming separately from logical deduction and equality reasoning.

Axiomatisations. The two best-known ‘nominal’ logics are probably the nominal logic of [Pitts 2003] and FM set theory. Both of these are Hilbert-style theories—sets of axioms—in first-order logic. They are axiomatic theories of sets.

FM set theory contains axioms whose intended model is a sets cumulative hierarchy, whereas nominal logic contains axioms only for sets with a finitely-supported permutation action, with no assumption that they be composed of other sets. For the purposes of this paper, the difference is not important.

Qua logic, PNL is a logic whereas nominal logic and FM set theory are axiomatisations. In addition and closely related to this, we can ‘just α-rename’ and ‘just choose a fresh atom’— as mentioned above we have α-renaming and freshness without appealing to equality reasoning and axioms.

Proof-theories for the И-quantifier. Natural deduction rules for И are proposed e.g. in [Gabbay and Pitts 2001, Proposition 4.10], but these are not closed under substitution. The second author created a proof-theory for И [Gabbay 2007a] with a good notion of proof-normalisation and a completeness proof, followed by an alternative treatment with Cheney [Gabbay and Cheney 2004].

These gave И an operational behaviour as ‘pick a locally fresh name’; Cheney then developed another sequent system which gave И an operational behaviour as ‘pick a globally fresh name’ [Cheney 2005].

The logic of [Cheney 2005] includes 12 infinite axiom-schemes (Figures 3 and 4 of [Cheney 2005]) describing the behaviour of atoms-abstraction from [Gabbay and Pitts 2001]. Thus, α-equivalence (for atoms) is axiomatically handled and does not participate in the proof-theory.

PNL handles both α-equivalence and the И-quantifier very compactly, without recourse to axioms, and indeed requiring neither equality reasoning nor a И-quantifier.

One-and-a-halfth order logic. This logic is designed to represent schematic first-order reasoning (first-order derivations in the presence of ‘unknown predicates’). It corresponds roughly to the axiomatisation of first-order logic in Section 4.

Semantic nominal terms. In [Gabbay and Mulligan 2009a] we show how to interpret level 2 variables (unknowns) as infinite lists of distinct level 1 variables (atoms). This allows us to build permissive-nominal term syntax as nominal abstract syntax-style inductive datatypes as proposed in [Gabbay and Pitts 2001]. The aim of this paper is to discuss the logic; not to analyse how its syntax could best be built.

8.2. From nominal terms-in-freshness-context to PNL terms-with-permission-sets

Nominal terms were introduced in [Urban et al. 2004] where a decidable and efficient unification algorithm was demonstrated (see [Calvès and Fernández 2008; Levy and Villaret 2010; Calvès 2010] for the state of the art). Nominal terms have been used in equational specification languages; in rewriting [Fernández and Gabbay 2007] and in universal algebra (the logic of equality) [Gabbay and Mathijssen 2009].

PNL differs from nominal terms in three ways:

— Nominal terms use a finite freshness context a#X whereas PNL uses permission sets, following [Dowek et al. 2009; Dowek et al. 2010] (a ‘permission set’ S can equally well be considered as a freshness sets A \ S).

— PNL predicates include universal quantification over unknowns ∀X.

— PNL term syntax includes shift-permutations (the implications of this are discussed in Subsection 2.7).

These features optimise PNL for being a first-order style logical foundation for mathematics with binding.

Another way to view this paper is as follows: PNL is the ‘obvious’ extension of nominal algebra [Gabbay and Mathijssen 2009] (an equational logic based on nominal terms), to a first-order logic.

But how then do we arrive at permissive nominal techniques, starting from nominal algebra? Suppose we have an equality axiom a#X ⊢ f([a]X) = g(X). We want to write a corresponding first-order axiom. There are two obvious routes to follow:

(1) Assume first-order logic with a sort of atoms ν and some axioms (like nominal logic or FM set theory) and write

∀z, x.z#x ⇒f([z]x) = g(x).

Here z and x are variables and freshness # can be expressed using the axioms of the logic. The problem with this is that we lose proof-theory; we are just working in a Hilbert-style axiom system.

(2) Imagine a first-order logic with nominal terms in which freshness conditions are attached to quantifiers, so that we can write

∀X:ν#a.f([a]X) = g(X).

Here ν#a means ‘elements of ν for which a is fresh’. The problem with this is that we have a poor theory of α-equivalence; the freshness context for X does not allow us to rename [a]X to [b](b a)·X, because there is no b fresh for a (more on this in Implementing PNL below).

Concerning the second option, we can add ‘freshening’ axioms or derivation rules to the effect that ∀X : ν#a.φ be logically equivalent to ∀X:ν#a,b.φ, and so on—this is in essence what the ‘freshening’ rule (fr) of nominal algebra (rule in Figure 2 of [Gabbay and Mathijssen 2009]) does. It should be possible to construct a version of PNL along these lines; the disadvantage would be that once X is instantiated, we can no longer add further fresh atoms, unless we reintroduce (fr) into PNL, but even then we would not recover full permissive-nominal α-equivalence.

In PNL we take the idea to the ωth degree; taking a limit of this ‘freshening’ operation to obtain infinitely many fresh atoms, we arrive at permission sets.

8.3. Non-nominal logics

First- and higher-order logic. As discussed in the Introduction, we see PNL as sitting somewhere in-between these two logics. It is more powerful—and we would claim more ergonomic—than first-order logic, because term-formers can bind. Its advantage over higher-order logic is the smaller and simpler models and generally more first-order character. Its term-syntax supports a decidable unification algorithm: both without shift [Dowek et al. 2010] and with [Gabbay 2012].

Logics based on the ∇-quantifier. A family of logics exists based on higher-order patterns and the ∇-quantifier [Miller and Tiu 2003; Tiu 2007; Gacek et al. 2008]. The intended meaning of e.g. ∇x.r=s is ‘λx.r=λx.s’. Thus for instance the intended denotation of ∇x.∇y.x=y is λx.λy.x=λx.λy.y, and this is false.

As this example suggests, logics based on ∇ use raising and patterns (in brief: higher-order variables applied to finite lists of distinct variables, as in xx1. . . xn) to obtain the effect of capturing substitution and variable dependencies, whereas we use permission sets and a two-level term syntax. Our reading is that ∇ is a way of peeling a single λ-abstraction uniformly off all terms and pushing it ‘into the meta-level’. Or, to put it another way: ∇ generates a fresh λ-abstracted variable.

The main philosophical difference here is that ∇ is designed to assume α-equivalence and treats variables as a ‘wire’ which must always be bound, either by λ in a term or possibly by a top-level ∇; in contrast nominal techniques treat names as global and permutable and break α-equivalence down into names and permutation. In a separate journal paper submitted for publication, we relate these by translating permissive-nominal logic to higher-order logic in the style of e.g. a translation of permissive-nominal term unification to higher-order pattern unification [Dowek et al. 2010] or nominal algebra to algebra over higher-order terms [Gabbay and Mulligan 2009b].

However, note that raising can cause a linear expansion in the size of a term (because what is represented by X in this paper would be represented by xx1. . . xn in a logic based on raising), and can also cause ‘silly’ β-redexes (since the mechanism which encodes dependency is the same mechanism which encodes computation). This is one of the motivations for CMTT discussed below.

Contextual modal type theory (CMTT). CMTT [Nanevski et al. 2008] is a two-level system; typing contexts split into two halves; ∆ and Φ. The two levels are different from the two levels used in (permissive-)nominal terms. Variables u : A[Φ] ∈∆ range over representations of code; variables x : A ∈ Φ range over denotation.

This addresses a problem that is mostly orthogonal to what PNL tries to achieve. To the extent that this could be represented in PNL, it would be represented at the level of sorts—one sort for code, another for denotation (values).

Logics based on CMTT are consistent and have a well-studied proof-theory, so individual semantic models can be constructed using normal forms, but the question “what is the general class of structures which these syntactic models represent?”’ has no answer we know of. That is, no general sets-based class of models has has been given for CMTT. Developing such models—perhaps using techniques borrowed from nominal sets—would be interesting future work.

Further logics. Coming from other threads of research in computer science are logics designed to enrich first-order logic directly with binders without thinking specifically about inductive reasoning. We note in particular binding logic [Dowek et al. 2002] and λ-logic [Beeson 2004].

Binding logic enriched first-order terms with binders but forbade capture and turned out to be a little too weak.

λ-logic takes a direct approach of enriching first-order terms with λ-abstraction. The approach to binding taken by PNL is somewhat more general and is certainly different, in that it allows us to treat names as ‘bindable constants’. That is, we can compare names for inequality as names, while at the same time we can give them the behaviour of variables by axiomatising e.g. substitution for them, if we wish.

9. FURTHER REMARKS, FURTHER WORK

We have seen how permissive-nominal logic (PNL) extends first-order logic with term-formers that can bind. We have given PNL a nominal-sets based semantics and shown it sound and complete. We have considered a finite axiomatisation of arithmetic, based on a finite axiomatisation of first-order logic in PNL, and proven it correct. Finally, we have proved cut-elimination.

In most respects PNL behaves just like first-order logic. However, its ‘nominal’ constructs let it ergonomically perform many of the tasks that would require much more powerful constructs in e.g. higher-order logic.

We do not claim that PNL makes nominal terms like those used in [Urban et al. 2004; Fernández and Gabbay 2007] obsolete. The argument for permissive-nominal terms is that they are a more abstract and powerful mathematical model with which to do proofs; for we use them to ‘just quotient’ by α-equivalence, and we use them to reconcile α-equivalence of atoms with ∀X. But that story is entirely compatible with prevous work. For instance, though permission sets have the form (A<∪A)\B (Definition 2.7), in practice we only seem to specify restrictions like a ∈ pmss(X) and b ∉ pmss(X)—and these look like freshness environments. In the discussion of Subsection 2.7 we saw why: permission sets control capture, and we only care about controlling capture for the finitely many atoms mentioned explicitly in an axiom. Furthermore the use of shift-permutations (Definition 2.9) means that the exact choice of permission set ‘does not really matter’—more on this below. In a sense, freshness contexts live on in this paper and remain useful, as an emergent property of how we interact with a more abstract underlying mathematical model given by permissive-nominal terms.

We do not claim that PNL is the ultimate logic, whatever that means. However, we do see PNL as a significant step forward in the continuing search for logics suitable for axiomatising the systems with binding which are so common in computer science, as briefly discussed in Section 8. We hope that PNL will turn out to be a ‘sweet spot’ amongst such systems—fairly simple, yet usefully expressive and with good theoretic properties.

We will now briefly discuss some of the design decisions and design alternatives available to us in creating logics in the spirit of PNL.

Unknowns of name sort, and atoms. A swapping with unknowns, as in (X Y)·r where X and Y have a name sort ν, is not primitive syntax in PNL. This is atoms as variables as in [Gabbay and Cheney 2004] and [Pitts 2003], as opposed to the atoms as constants approach of nominal terms [Urban et al. 2004] which is inherited by this paper.

The axioms of nominal logic [Pitts 2003, Section 5] can be copied over to endow term-formers abs and swap (see below) with the right properties; since the logic of [Pitts 2003] is already a set of axioms, there is no harm in doing this also in PNL. Alternatively, we can ‘promote’ behaviour from atoms to unknowns: Suppose a sort α and a name sort Atm. Suppose sort(X) = α and a ∈ pmss(X). Suppose a term-former abs : (Atm, α)[Atm]α. The axiom ∀X, Y.(X≈a ⇒ abs(X, Y)≈[a]Y) ‘promotes’ atoms-abstraction, to an abstraction by unknowns of sort atom (over terms of sort α). Similarly for a term-former swap : (Atm, Atm, α)α.

The question phrased in semantic terms is as follows:

— Should every inhabitant of the denotation of a name sort ν to be referenced in PNL syntax by an atom?

— Should every inhabitant of the semantics of name sorts, to be referenced by a closed term?

The answers to these questions matter, but not for this paper. It is not unusual (indeed, it is very common) for there to be more elements in a type than there are closed terms. Furthermore, we have proved completeness in Subsection 3.4, so any extra elements in name sorts cannot ‘make anything false’.

Yet it is reasonable to ask in future work whether we could exclude ‘non-standard atoms’ in the same way that for example we might try to exclude non-standard numbers from models of first-order theories of arithmetic. (Note that this is a general issue with a two-level syntax, and is not specific to PNL.)

We believe that this is possible. The idea is in the proof-theory for И from ‘Fresh Logic’ [Gabbay 2007a]; see (ExhaustA) in Figure 3, and Subsection 5.5.

Extending sorts. It would be a good idea to introduce sort-formers and polymorphism into the sorting system, so that e.g. we can conveniently axiomatise a substitution action on an infinite class of sorts. We see no difficulty in doing this—it is a definitional extension of what we already have.

Another interesting extension is to assume, for every sort α, an associated name sort να. This would allow us to talk about ‘the level 1 variables associated with α’ in the same way that we can already talk about ‘the level 2 variables of sort α’.

Design of permission sets. There is design freedom in the choice of permission sets. We briefly sketch some of the options.

We can have more permission sets. For instance, we can take A uncountable and permission sets all countably infinite sets. We can also add finite permission sets, enabling us e.g. to reason about properties that only hold of (level 1) closed terms, or terms with a finitely bounded number of free atoms.

We can have fewer permission sets. For instance we could take permission sets to be A< \A, or π·A< for finite π.

We can also have much fewer permission sets—one, to be precise. PNL would work just as well if we took A< as the single unique permission set. The effect of larger or smaller permission sets can then be obtained using permutations. For example if pmss(X) = A< and pmss(Y ) = shiftτ·pmss(X) and sort(X) = τ = sort(Y ) then the effect of ∀Y.P(Y ) can be obtained by the logically equivalent ∀X.P(shiftτ·X). Using further shift-permutations and conjugation by finite permutations, any of the permission sets of Definition 2.7 can be obtained.

Note that we never want A to be a permission set. If we had that, then we would not be able to ‘choose a fresh atom’ and e.g. would be unable to α-convert a in [a]X if pmss(X) = A.

Taking a more abstract view, a natural generalisation of Definition 2.7 is an equivariant nominal join semi-lattice that does not contain ⊤. So specifically for sets of atoms, this means that if S and T are permission-sets then so are π·S and S ∪T, and A is not a permission set. To illustrate how this works, note that if S is a permission set and A \ S is finite then it easily follows using equivariance and sets unions that A is a permission set. So to insist that A is not a permission set, is really to insist that every permission set is coinfinite.

The design decision made in Definition 2.7 is simple, effective, and direct, and it allows us to express capture-avoidance conditions easily without complex ‘emulations’ involving shift.

PNL without shift. We can restrict PNL by dropping shift-permutations (but retaining permission sets as defined), yielding a logic that could be called PNL without shift. This is what was considered in the conference version of this paper [Dowek and Gabbay 2010].

This is less ergonomic, but in a certain sense it is just as powerful. It all depends on whether we want to be able to change our mind about a permission set in mid-derivation.

This is a similar issue as appears e.g. in the design of a sequent system, whether we allow weakening as an explicit sequent rule (so that we can weaken mid-derivation), or integrate weakening into the axiom rule (so we have to anticipate the other propositions needed in the sequent).

The isomorphism between pmss(X) and pmss(X) ∪{a} for a ∉ pmss(X) is explicit in full PNL and an implicit fact in PNL without shift.

Unification of permissive-nominal terms without shift was considered in [Dowek et al. 2010]. Subsequently to writing this paper, that theory was re-cast using shift [Gabbay 2012].

Note that nominal algebra satisfies an HSPA result whereas permissive-nominal algebra with shift satisfies an HSP result; details are elsewhere [Gabbay 2009; Gabbay 2012] but what is relevant to this discussion is that the extra expressivity which shift gives, can make a real, mathematically measurable, difference.

Implementing PNL. An implementation of PNL could follow the lines of a first-order theorem-prover, since the proof-rules in Figure 1 are so like those of first-order logic. The term-language would be richer and would include names and binding.

There would be many design choices, some of which we have touched on above: polymorphism in sorts; choice of permission sets (perhaps even adding variables to permission sets); whether or not to include shift; whether or not to exclude ‘non-standard’ atoms using an (ExhaustA) rule like that in Figure 3 of [Gabbay 2007a]; and so on.

Another point is how much of the infinity of permission sets we should expose to the user. To discuss this further, we must draw together several strands that have run through this paper from the beginning.

At the start of this paper we introduced permission sets, which guarantee infinite supplies of fresh atoms for every unknown. This culminated in Definition 2.30 with the permissive-nominal ‘just quotient’ α-equivalence, which is different from the notion of α-equivalence used in nominal terms in e.g. [Urban et al. 2004; Fernández and Gabbay 2007; Gabbay and Mathijssen 2009]. In Subsection 8.2 we gave a sense in which PNL is obtained from nominal terms and nominal algebra by adding universal quantifiers while taking a limit of extending freshness contexts in the sense of nominal terms.

But then at the start of this section we noted that for any concrete derivation we only care about the finitely many atoms explicitly mentioned, thus for any concrete derivation we only care about finite freshness information after all.

So we have a choice, when implementing PNL, whether to present the user with A< and A> directly as we did in Definition 2.7, or to present a nominal terms syntax in which a (possibly but not necessarily finite) context of freshness assertions ∆ is carried and may be extended as needed (nominal algebra does this using a freshness rule (fr) [Gabbay and Mathijssen 2009]; an idea taken from [Gabbay 2007a]).

A specific disadvantage is that we would lose the permissive-nominal ‘just quotient syntax’ theory of α-equivalence used in Definition 2.30.

At the moment it seems unclear how much this matters from the point of view of an implementation. After all, in an implementation we will have a specific goal with specific and (finitely many) atoms for which the user has chosen specific names. So will the user even appreciate explicit access to an infinite stock of fresh atoms? Or, will the user prefer a freshness context to be extended as needed? Note that the implementation might need fresh names when α-renaming during resolution, so a resolution step might extend the freshness context with finitely but unboundedly many new names. An advantage of presenting A> explicitly is that these names are honestly presented to the user from the start.

As with any logic, there are many ways to present it. Yet, the underlying mathematics remains essentially the same.

Summary. PNL addresses problems of mathematical specification with names and binding. It provides a first-order logic environment which allows us to formally express the ‘informal meta-level’, complete with names and binding. As such, the most exciting potential application of PNL is as a logical foundation—as a meta-theory for mathematics—intermediate in power between first- and higher-order logic. We believe that, perhaps with some fairly modest extensions, it would make an expressive, ergonomic, and practical alternative meta-language for mechanised mathematics.

REFERENCES

Abadi, M., Cardelli, L., Curien, P.-L., and Lévy, J.-J. 1991. Explicit substitutions. Journal of Functional Programming 1, 4, 375–416.

Beeson, M. 2004. Lambda logic. In Second International Joint Conference on Automated Reasoning (IJCAR 2004). Lecture Notes in Computer Science Series, vol. 3097. Springer, 460–474.

Calvès, C. 2010. Complexity and implementation of nominal algorithms. Ph.D. thesis, King’s College London.

Calvès, C. and Fernández, M. 2008. A polynomial nominal unification algorithm. Theoretical Computer Science 403, 285–306.

Cheney, J. 2005. A simpler proof theory for nominal logic. In FoSSaCS. Lecture Notes in Computer Science Series, vol. 3441. Springer, 379–394.

Dowek, G. and Gabbay, M. J. 2010. Permissive Nominal Logic. In Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2010). ACM Press, 165–176.

Dowek, G., Gabbay, M. J., and Mulligan, D. P. 2009. Permissive Nominal Terms and their Unification. In Proceedings of the 24th Italian Conference on Computational Logic (CILC’09).

Dowek, G., Gabbay, M. J., and Mulligan, D. P. 2010. Permissive Nominal Terms and their Unification: an infinite, co-infinite approach to nominal techniques (journal version). Logic Journal of the IGPL 18, 6, 769–822.

Dowek, G., Hardin, T., and Kirchner, C. 2002. Binding logic: Proofs and models. In Proceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2002). Springer, 130–144.

Dummett, M. 1977. Elements of intuitionism 1 Ed. Clarendon Press.

Farmer, W. M. 2008. The seven virtues of simple type theory. Journal of Applied Logic 3, 6, 267–286.

Fernández, M. and Gabbay, M. J. 2007. Nominal rewriting (journal version). Information and Computation 205, 6, 917–965.

Gabbay, M. 2011a. A proof-theoretic treatment of lambda-reduction with cut-elimination: lambda calculus as a logic programming language. Journal of Symbolic Logic 76, 2, 673–699.

Gabbay, M. J. 2001. A Theory of Inductive Definitions with alpha-Equivalence. Ph.D. thesis, University of Cambridge, UK.

Gabbay, M. J. 2005. A NEW calculus of contexts. In Proceedings of the 7th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming (PPDP 2005). ACM Press, 94–105.

Gabbay, M. J. 2007a. Fresh Logic. Journal of Applied Logic 5, 2, 356–387.

Gabbay, M. J. 2007b. A General Mathematics of Names. Information and Computation 205, 7, 982–1011.

Gabbay, M. J. 2009. Nominal Algebra and the HSP Theorem. Journal of Logic and Computation 19, 2, 341–367.

Gabbay, M. J. 2011b. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic 17, 2, 161–229.

Gabbay, M. J. 2011c. Two-level nominal sets and semantic nominal terms: an extension of nominal set theory for handling meta-variables. Mathematical Structures in Computer Science 21, 997–1033.

Gabbay, M. J. 2012. Nominal terms and nominal logics: from foundations to meta-mathematics. In Handbook of Philosophical Logic. Vol. 17. Kluwer.

Gabbay, M. J. and Cheney, J. 2004. A Sequent Calculus for Nominal Logic. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004). IEEE Computer Society, 139–148.

Gabbay, M. J. and Mathijssen, A. 2007. A Formal Calculus for Informal Equality with Binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation. Lecture Notes in Computer Science Series, vol. 4576. Springer, 162–176.

Gabbay, M. J. and Mathijssen, A. 2008a. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing 20, 4-5, 451–479.

Gabbay, M. J. and Mathijssen, A. 2008b. One-and-a-halfth-order Logic. Journal of Logic and Computation 18, 4, 521–562.

Gabbay, M. J. and Mathijssen, A. 2009. Nominal universal algebra: equational logic with names and binding. Journal of Logic and Computation 19, 6, 1455–1508.

Gabbay, M. J. and Mulligan, D. P. 2009a. Semantic nominal terms. In Proceedings of the 2nd International Workshop on the Theory and Applications of Abstraction, Substitution and Naming (TAASN 2009).

Gabbay, M. J. and Mulligan, D. P. 2009b. Universal algebra over lambda-terms and nominal terms: the connection in logic between nominal techniques and higher-order variables. In Proceedings of the 4th International Workshop on Logical Frameworks and Meta-Languages (LFMTP 2009). ACM, 64–73.

Gabbay, M. J. and Pitts, A. M. 2001. A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing 13, 3–5, 341–363.

Gacek, A., Miller, D., and Nadathur, G. 2008. Combining generic judgments with recursive definitions. In Proceedings of the 23rd IEEE Symposium on Logic in Computer Science (LICS 2008). IEEE Computer Society Press, 33–44.

Levy, J. and Villaret, M. 2010. An efficient nominal unification algorithm. In Proceedings of the 21st International Conference on Rewriting Techniques and Applications (RTA 2010). Leibniz International Proceedings in Informatics (LIPIcs) Series, vol. 6. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 209–226.

Miller, D. and Tiu, A. 2003. A proof theory for generic judgments (extended abstract). In Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003). IEEE Computer Society Press, 118–127.

Nanevski, A., Pfenning, F., and Pientka, B. 2008. Contextual modal type theory. ACM Transactions on Computational Logic (TOCL) 9, 3, 1–49.

Paulson, L. C. 1990. Isabelle: the next 700 theorem provers. In Logic and Computer Science, P. Odifreddi, Ed. Academic Press, 361–386.

Pitts, A. M. 2003. Nominal logic, a first order theory of names and binding. Information and Computation 186, 2, 165–193.

Shoenfield, J. 1967. Mathematical Logic. Addison-Wesley.

Tiu, A. 2007. A logic for reasoning about generic judgments. Electronic Notes in Theoretical Computer Science 174, 5, 3–18.

Urban, C., Pitts, A. M., and Gabbay, M. J. 2004. Nominal Unification. Theoretical Computer Science 323, 1–3, 473–497.

Notes

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or permissions@acm.org. ⃝c YYYY ACM 1529-3785/YYYY/01-ARTA $10.00 DOI 10.1145/0000000.0000000 http://doi.acm.org/10.1145/0000000.0000000

1The language of terms is significantly different, though; see Definition 2.13. ↩

2Via this intuition, permission sets correspond to the freshness constraints a#X of [Urban et al. 2004]. For the reader familiar with freshness constraints, another way to view permission sets is as fixing a single global freshness context with ‘enough’ freshnesses (the germ of this was already in [Gabbay 2005]) where ‘enough’ means that for any term, we can always pick an atom not free in that term. However the implications of doing this go beyond a syntactic tweak to nominal terms; permission sets are what make it possible for us to reconcile level 2 quantification ∀X with level 1 atoms-abstraction [a]r. ↩

3Remember that we quotient raw terms by α-equivalence to obtain terms so this is now a real equality. ↩

4In this paper equivariance surfaces in a variety of technical features of PNL: the π in (Ax); the way permutations distribute into terms in Definition 2.17; Definition 3.16 and how it is used in Definition 3.18; Lemma 3.22; and more. In fact, equivariance is broad and useful phenomenon. The interested reader is referred to [Gabbay and Pitts 2001, Lemma 4.7] and [Gabbay 2011b, Subsection 4.2], where it is treated in full generality. See also [Gabbay 2011c, Lemma 5.5], where the conditions on free atoms and support in Definitions 2.32 and 3.19 are also exhibited as forms of equivariance. ↩

5If permission sets were finite, or if all permutations were finite, then we could not do this in general. ↩

6supp(x) need not necessarily be a permission set. For instance, supp(a) = {a}. ↩

7We favour the word ‘interpretation’ for assigning a denotational interpretation to a logic, and ‘model’ for checking whether the interpretation makes a theory (a set of axioms). These senses overlap, in that an interpretation is a model for the empty theory. In practice, we tend to use whichever word seems most appropriate in context. ↩

8Missing from this is a proof that EQU ∪ SUB ∪ FOL soundly and completely interprets first-order logic. We believe this to be true and the proof should be an elementary simplification of the more involved case for arithmetic—but it is not worth writing out here. Arithmetic is (in first-order logic) axiomatised using a schema. We use PNL ∀X to express them finitely; see e.g. the ∀X in (PInd) of Figure 6 which models the ‘every ξ’ in (pind) in Figure 7. Finite first-order logic theories (including the empty theory) are unproblematic. In these proofs, soundness and completeness are only a means to the end of demonstrating how we can axiomatise finitely in a nominal first-order logic PNL, structures that without names and binding would require infinite axiom schemes or higher orders. ↩