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

Permissive-Nominal Logic

Gilles Dowek www.lix.polytechnique.fr/˜dowek

Murdoch J. Gabbay www.gabbay.org.uk

Abstract

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

This allows for direct axiomatisations with binders, such as the ∀-quantifier of first-order logic itself and the λ-binder of the lambda-calculus. This also allows us to finitely axiomatise arithmetic.

Like first- and higher-order logic and unlike other nominal logics, equality reasoning is not necessary to α-rename.

All this gives PNL much of the expressive power of higher-order logic, but terms, derivations and models 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]: Proof theory—Nominal techniques

General Terms Theory

Keywords First-order logic, permissive-nominal terms, mechanized mathematics.

1. Introduction

Binding is ubiquitous in logical specifications in mathematics — it features in function definitions as λ-abstraction, and binders are also used to define sets in comprehension, and to define finite and infinite sums, integrals, derivations, and so on.

This suggests we consider logics that support term-formers that can bind variables, to conveniently specify systems with binding. This turns out to be not so easy.

First-order logic is computationally tractable (unification of first-order terms is decidable, and proof-search is simple and well-understood) and expressive (it can be used for example to specify groups, rings, and combinators).

However, first-order logic does not admit term-formers that can bind. Thus it is difficult in first-order logic to give direct, finite, 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 [9] for an excellent exposition) and implementations (like Isabelle [27]). Higher-order logic has a convenient and powerful binder (λ) built in to terms. However, it is also stronger than first-order logic, less computationally tractable, and models tend to be more complex. The jump from first- to higher-order is quite large.

This motivates the study of direct extensions of first-order 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.

An overview of the content of this paper is as follows:

• We introduce the syntax and derivations of permissive-nominal logic (Section 2).

• We axiomatise equality, substitution, first-order logic, ‘nominal’ inductive datatypes, the N-quantifier, semantic freshness — and arithmetic (Sections 3 and 7).

• We prove soundness (Theorems 5.15) for a suitable semantics of permissive-nominal sets (Section 4).

• We prove the axiomatisation of arithmetic correct (Theorem 6.20).

It is a fact that Cut can be eliminated and PNL is complete for the semantics in this paper. Proofs will be in a longer paper.

Unification of permissive-nominal terms is decidable [7], and models of PNL are like those of first-order logic. Complexities common in higher-order syntax and semantics do not arise.

The axiomatisation of arithmetic is finite; the induction schema is represented by a single axiom with a universal quantification over a nominal unknown. This axiomatisation goes strictly further than previous axiomatisations in nominal algebra, making specific use of the first-order structure of PNL. It is also very close to the informal specification often given for first-order arithmetic.

To use a phrase that has become something of a slogan in nominal techniques, our axiomatisation of arithmetic, and we would argue more generally the natural use of PNL, is indeed ‘ϵ away’ from informal practice.

For the reader’s convenience we now cut a tranche through existing nominal work, briefly sketching how the nominal ideas in this paper relate to what has come before. An extended discussion of related work is in the Conclusions.

Nominal techniques were introduced in [22], where the properties of Fraenkel-Mostowski set theory (FM) were studied.

Nominal logic (NL) [28] was another set of axioms in first-order logic; to use a bit of nominal jargon, it restricted to equivariant FM sets and removed the cumulative hierarchy. Both FM and NL were and remain important but note that the language used in both is just first-order terms and propositions.

A multi-level language (with atoms a and unknowns X) was introduced as nominal terms in [31]. The problem we see with this is that nominal terms have freshness contexts and cannot be conveniently quotiented by α-equivalence. We find this inconvenient for several reasons, one of which is difficulty introducing binders like ∀X and λX.

a ∈Aνa : νr1 : α1 . . . rn : αn(r1, . . . , rn) : (α1, . . . , αn)r : α (ar(f) = (α)τ) f(r) : τr : α (a ∈Aν) [a]r : [ν]α(s(X) = α) π·X : α⊥prop.φ prop. ψ prop. φ ⇒ψ prop.r : α (ar(P) = α) P(r) prop.φ prop. ∀X.φ prop.
Figure 1: Terms and propositions

We introduced permissive-nominal terms in [7]; these can be quotiented by α-equivalence and can be extended with binders for X. To a first approximation, this paper studies syntax, semantics, derivability, and expressivity of ∀X in a permissive-nominal terms context. In another paper we make a similar study of λX.

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 inductively defined by

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

Examples of base sorts are: ‘λ-terms’, ‘formulae’, ‘π-calculus processes’, and ‘program environments’, ‘functions’, ‘truth-values’, ‘behaviours’, and ‘valuations’.

Examples of name sorts are ‘variable symbols’, ‘channel names’, or ‘memory locations’.

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 (α)τ 1 and to each P ∈P a proposition-former arity α, where α and τ are in the sort-language determined by (A, B).

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

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

Definition 2.4

For each τ fix two disjoint countably infinite set of atoms A< τ and A> τ. Write Aτ = A< τ ⊎A> τ (⊎ denotes disjoint set union), and 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 is also infinite).

Definition 2.5

A (level 1) permutation is a bijection π on atoms such that a ∈Aτ implies π(a) ∈Aτ always, and

nontriv(π) = {a∈A | π(a)≠a}

is finite. π will range over permutations.

Definition 2.6

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 of that sort and permission set. X, Y, Z will range over distinct unknowns. Write s(X) for the sort and p(X) for the permission set of X.

Permission sets correspond to the freshness contexts of [31]. Unlike freshness contexts they are fixed, and being co-infinite they guarantee infinitely many ‘fresh names’. This gives a ‘permissive’ treatment of α-equivalence, as will become clear.

Definition 2.7

For each signature S, define terms and propositions (over S) inductively by the rules in Figure 1.

Remark 2.8

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.

Example 2.9

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

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

2.2 Permissive-nominal logic syntax is finitary

Terms and propositions are finite trees. Permission sets differ finitely from A< and so trivially admit a finite represenation.

In fact, permissive-nominal term α-equality can be decided in linear time. A permissive-nominal unification algorithm [7] has been implemented [25].

α-equivalence is defined in this paper in Definition 2.16.

2.3 Permutation actions

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.

Definition 2.10

Write π ◦π′ for functional composition (so (π ◦π′)(a) = π(π′(a))), id for the identity permutation (so id(a) = a always) and π-1 for inverse (so π ◦π-1 = id).

Define a (level 1) permutation action by:

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

Let Π range over sort- and permission-set-preserving bijections on unknowns (so s(Π(X))=s(X) and p(Π(X))=p(X)) such that {X | Π(X) ≠ X} is finite.

Write Π◦Π′ for functional composition, Id for the identity permutation, and Π-1 for inverse, much as in Definition 2.10.

Define a (level 2) permutation action by:

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

2.4 Free level 1 and level 2 variables

Definition 2.12

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

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

This is the standard pointwise permutation action on sets.

Definition 2.13

Define free atoms fa(r) by:

fa(π·X) = π·p(X) fa([a]r) = fa(r) \ {a}fa(f(r)) = fa(r) fa((r1, . . . , rn)) = ⋃ fa(ri)fa(a) = {a}

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

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

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

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

Proof

By routine inductions on r.End of proof

2.5 α-equivalence

Definition 2.15

Call a 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φ R φ′ψ R ψ′φ ⇒ψ R φ′ ⇒ψ′r R s (P : α, r, s : α) P(r) R P(s)φ R φ′∀X.φ R ∀X.φ′
Definition 2.16

Write (a b) for the (level 1) swapping permutation which maps a to b, 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) all a ∈p(X)) π·X =α π′·X(Y X)·φ =α ψ (Y ∉fV (φ)) ∀X.φ =α ∀Y.ψ
Example 2.17

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

Let s(Y ) = s(X) and p(Y ) = p(X) = A<. Suppose 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.

Remark 2.18

Note that α-equivalence is:

• Highly symmetric between levels 1 and 2.

• Based on permutations instead of substitutions (in keeping with the ‘nominal’ ideas in [22]).

• Does not require equality reasoning in the logic.

We emphasise this last point. We say that in PNL we can ‘just α-convert’. We take this for granted in first- and higher-order logic. In this respect, PNL is close to informal practice.

In [4, 12, 14, 22, 28] it is not in general possible to ‘just α-convert’ a level 1 abstraction. We 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.19

For every π, Π, r, s, φ, and ψ, the following hold: r =α s if and only if π·r =α π·s and similarly φ =α ψ if and only if π·φ =α π·ψ. Also, r =α s if and only if Π·r =α Π·s, and similarly for φ =α ψ.

Lemma 2.20

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

Proposition 2.21

=α is an equivalence relation on terms and propositions.

Proof

By a standard argument as in [10], using Lemmas 2.14, 2.20, and 2.19.End of proof

Lemma 2.22

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

PNL retains the ‘nominal’ power to reason on names and binding in nominal abstract syntax. See the example theories of freshness and inductive datatypes in Section 7.

2.6 Substitution

Definition 2.23

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

• θ(X) : s(X) always,

• fa(θ(X)) ⊆ p(X) always,

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

θ will range over substitutions. 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.24

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.φ)θ ≡∀Y.(((Y X)·φ)θ)

In the clause for ∀X we rename X to be fresh for nontriv(θ), if necessary, using a fixed but arbitrary choice of fresh Y for each X, φ, θ.

Remark 2.25

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

Remark 2.26

Unknowns are variables; they have a substitution action. Atoms are not variables. Atoms are data; they are ‘bindable constant symbols’.

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 function-symbol (Definition 2.3), e.g. var in Sections 3 and 7.

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.

(Ax)Φ, φ ⊢φ, Ψ(⊥L)Φ, ⊥⊢ΨΦ ⊢φ, Ψ Φ, ψ ⊢Ψ(⇒L)Φ, φ ⇒ψ ⊢ΨΦ, φ ⊢ψ, Ψ(⇒R)Φ ⊢φ ⇒ψ, ΨΦ, φ ⊢Ψ(N)Φ, π·φ ⊢ΨΦ, φ[X::=r] ⊢Ψ (fa(r)⊆p(X), r:s(X))(∀L)Φ, ∀X.φ ⊢ΨΦ ⊢φ, Ψ (X ∉fV (Φ, Ψ))(∀R)Φ ⊢∀X.φ, ΨΦ, φ ⊢Ψ (φ =α ψ)(αL)Φ, ψ ⊢ΨΦ ⊢φ, Ψ (φ =α ψ)(αR)Φ ⊢ψ, Ψ
Figure 2: Sequent derivation rules of Permissive-nominal Logic

2.7 Sequents and derivability

Definition 2.27

Φ and Ψ will range over sets of propositions. We may write φ, Φ and Φ, φ as shorthand for {φ} ∪ Φ.

A sequent is a pair Φ ⊢ Ψ. Write

fV (Φ, Ψ) =⋃ {fV (φ) | φ ∈Φ} ∪⋃ {fV (ψ) | ψ ∈Ψ}.

The derivable sequents are inductively defined in Figure 2.

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

Remark 2.28

Figure 2 includes rules for ⊥, ⇒, and ∀. We could add rules for other connectives like ⊤, ∧, ∨, and ∃. 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.

Example 2.29

The condition fa(r) ⊆ p(X) in (∀L) might suggest that ∀X.φ means “φ[X::=r] for every r such that fa(r) ⊆ p(X)”. Indeed this is so, but this restriction is not quite what it seems.

Suppose a name sort Atm and suppose X : Atm and P : Atm. By (∀L), ∀X.P(X) ⊢ P(b) for some b ∈ p(X). But then by considering the swapping (a b) and (N), ∀X.P(X) ⊢ P(a) for all a, even if a ∉ p(X).

In spite of this ∀X.φ does not mean “φ[X::=r] for every r”. This is because permutations are bijective. For example, suppose X : Atm, a ∉ p(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(a, X) ⊢P(b, r) for all r and all b such that b ∉ fa(r).

In spite of this, ∀X.P(a, X) ⊬P(a, a).

3. Arithmetic as a PNL theory

Definition 3.1

We start by defining the sorts, term-formers, and proposition-symbols of a signature ˙L which is suitable for finitely specifying arithmetic in PNL.

We assume one atomic sort ν and two base sorts ι and o. We assume term-formers

0 : ι succ : (ι)ι + : (ι, ι)ι ∗: (ι, ι)ι˙⊥: o ˙⇒: (o, o)o˙∀: ([ν]o)o ˙≈: (ι, ι)ovar : (ν)ι subι : ([ν]ι, ι)ι subo : ([ν]o, ι)o

and proposition-formers

≈ι: (ι, ι) ≈o: (o, o) ϵ : (o).

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]; and we may write both ≈ι and ≈o just as ≈.

Example 3.2

Here are some example terms:

• ˙∀[a]X. This represents the first-order logic schema ∀x.φ. If a ∈ p(X) then this corresponds to x ∈ fv(φ) being permitted; otherwise it is not. ˙∀ is a function-symbol, of arity ([ι]o)o, and the sorts of a and X are ν (names) and o (truth-values) respectively.

• ˙∀[b](b a)·X where b ∉ p(X). This also represents the first-order logic schema ∀x.φ, but we have α-converted a to some fresh b. We might write this ‘∀y.φ[y/x] where y is fresh’.

We now build up theories in PNL, bit by bit. Higher-order logic (e.g. in Isabelle/Pure) can be used in much the same way [26], but starting from a higher-order logical foundation. In a PNL implementation we would probably need just a few bells and whistles, e.g. polymorphism in the sorts.

Remark 3.3

Informally, we might call ˙≈ ‘object-level’ equality, and ≈ ‘meta-level’ equality. Similarly ˙⊥ is ‘object-level’ and ⊥ is ‘meta-level’. ϵ converts ‘object-level’ truth to ‘meta-level’ truth. This is the same distinction as between = and ==, between ∀ and ⋀, and the same as the function from o to Prop, in Isabelle/FOL.

Perhaps level 1 and level 2 are a better terminology than ‘object-level’ and ‘meta-level’, since the above is all object-level in the sense that it is written formally in PNL and not informally in English.

Formally, ˙∀[a] ˙⊥ is a term of type o, and ∀X.⊥ is a proposition. ϵ mediates between terms of type o and propositions.

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

. . . substitution Axioms SUB for subι and subo are 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.

Remark 3.4

Note there are no axioms (sub0) and (sub ˙⊥). These are subsumed by (sub#). Note also that (sub#) really is necessary, for completeness; there might be models not all of whose elements are referenced by closed terms.

... first-order logic Axioms FOL for ˙⊥, ˙⇒, and ˙∀ are in Figure 5.

... and arithmetic Given EQU, SUB, and FOL, it is not hard to write axioms for arithmetic in PNL. This is in Figure 6.

Remark 3.5

SUB is from [16], which includes a formal proof of soundness and completeness. In [17] 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 [17]. PNL has ⊥, ⇒, and ∀, whereas nominal algebra does not; we use this extra structure to capture the behaviour of ˙⊥, ˙⇒, and ˙∀.

Remark 3.6

Instead of EQU we could extend Figure 2 with derivation rules as follows:

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

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 p(Z) is exactly (b a)·A<. The important point is that a ∉ p(Z). Similarly, in (subapp) it is not vital that p(X′′) = p(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 p(X′′) ≠ p(X′) then we can still instantiate X′′ and X′ to r′′ and r′ such that fa(r′′) = fa(r′) ⊆ p(X′′)∩p(X′). More on this in Section 9.

As discussed in Example 2.29, these axioms apply to all instantiating terms.

Remark 3.8

These axioms conservatively extend the usual first-order logic axiomatisation of arithmetic in a sense we make formal and prove in Section 6. First, we must introduce a suitable notion of model.

4. Permissive-nominal sets

Nominal sets were introduced in [22]. (They were called ‘equivariant FM sets’, and given their modern name later in [28].) Nominal sets have a finite support property, that every element has a supporting finite set. Permissive-nominal sets have a similar property that every element has a supporting permission set (Definition 4.2). This need not be finite but most of the good properties of nominal sets are preserved.

Definition 4.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 (Permutations × |X|) → |X|, written infix as π·x. (Here, we write Permutations for the set of all finite permutations defined in Definition 2.5.) So, id·x = x and π·(π′·x) = (π ◦π′)·x for every π and π′ and every x ∈|X|.

Definition 4.2

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

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

Theorem 4.3

Every x ∈|X| has a unique least supporting set supp(x) ⊆A.

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

Proof

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

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

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

Lemma 4.4

If x ∈|X| then supp(π·x) = π·supp(x) (Def. 2.12).

Proof

By routine calculations using the group action.End of proof

Corollary 4.5

Suppose x ∈|X| and 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 4.4 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

4.1 Examples of permissive-nominal sets: atoms; atoms-abstraction; cartesian product

Definition 4.6

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

In the case of A only, we will be lax about the distinction between the set of atoms, and the permissive-nominal set of atoms with its natural permutation action.

Definition 4.7

Suppose x ∈|X| and a ∈Aτ. Define:

[a]x = {(a, x)} ∪{(b, (b a)·x | b ∈Aτ\supp(x)} |[Aτ]X| = [Aτ]X = {[a]x | a ∈Aτ, x ∈|X|}

Give [Aτ]X the permutation action π·[a]x = [π(a)]π·x.

Lemma 4.8

• [Aτ]X is a permissive-nominal set.

• [a]x=[a]x′ if and only if x=x′, for a∈Aτ and x∈|X|.

• [a]x=[a′]x′ if and only if a′∉supp(x) and (a′ a)·x=x′, for a, a′∈Aτ and x, x′∈|X|.

Definition 4.9

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

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

• supp(a) = {a}.

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

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

Proof

Proofs are as in [22].End of proof

Definition 4.11

Suppose X and Y are sets with a permutation action. Call a function f from |X| to |Y| finite equivariant when π·(f(x)) = f(π·x) for all x ∈|X|.

Call a subset U ⊆|X| finite equivariant when x ∈U if and only if π·x ∈U for all x ∈|X| and all π (so π·U = U always, extending the permutation action pointwise to sets).

Remark 4.12

We write ‘finite’ equivariant, because it is possible to be equivariant up to finite permutations but not up to infinite permutations. The distinction was first observed as ‘fuzzy support’ in [13]. More on this in a later paper.

∀X′, X, Y ′, Y.(X′ ≈X ∧Y ′ ≈Y ) ⇒X′ op Y ′ ≈X op Y op ∈{+, ∗, ˙⇒, ˙≈}∀X′, X. X′ ≈X ⇒succ(X′) ≈succ(X) op ≈op op ∈{0, ˙⊥}∀Z′, Z. Z′ ≈Z ⇒˙∀([a]Z′) ≈˙∀([a]Z) ∀X′, X, Y ′, Y.(X′ ≈X ∧Y ′ ≈Y ) ⇒op([a]X′, Y ′) ≈op([a]X, Y ) op ∈{subι, subo}∀Z′, Z. Z′ ≈Z ⇒(ϵ(Z′) ⇔ϵ(Z)) We fill in sorts as appropriate. Thus, ˙⊥≈o ˙⊥whereas 0 ≈ι 0, and so on.
Figure 3: EQU: axioms for equality as a PNL theory
(subvar) ∀X. var(a)[a↦→X] ≈X(sub#) ∀X, Z. Z[a↦→X] ≈Z (p(Z) = (b a)·A<)(subsucc) ∀X′, X. succ(X′)[a↦→X] ≈succ(X′[a↦→X])(subop) ∀X′′, X′, X. (X′′ op X′)[a↦→X] ≈(X′′[a↦→X] op X′[a↦→X]) (op ∈{+, ∗, ˙⇒, ˙≈})(sub˙∀) ∀X, Z. (˙∀([b]Z))[a↦→X] ≈˙∀([b](Z[a↦→X])) (p(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<.
Figure 4: SUB: axioms for substitution as a PNL theory
( ˙⇒) ∀Z′, Z. ϵ(Z′ ˙⇒Z) ⇔(ϵ(Z′) ⇒ϵ(Z))(˙∀) ∀Z.(ϵ(˙∀([a]Z)) ⇔∀X.ϵ(Z[a↦→X]))( ˙⊥) ϵ( ˙⊥) ⇒⊥( ˙≈) ∀X′, X. X′ ≈X ⇒ϵ(X′ ˙≈X) Here Z′ and Z have sort o and permission set A<; X′ and X have sort ι and permission set A<; and a ∈A<.
Figure 5: FOL: axioms for first-order logic 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<.
Figure 6: ARITH: axioms for arithmetic as a PNL theory

5. Semantics

We now interpret PNL in a notion of permissive-nominal set. We sketch a proof of soundness (Theorem 5.15). PNL is also complete for the same semantics; more on that in a journal version of this paper.

Definition 5.1

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

An interpretation I for (A, B) consists of an assignment of a permissive-nominal set τI to each τ ∈B.

We extend I to sorts by:

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

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

An interpretation I for S consists of the following data:

• An interpretation for the sort-signature (A, B) (Def. 5.1).

• For every f ∈F with ar(f) = (α)τ a finite equivariant function fI from (α)I to (τ)I (Definition 4.11).

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

Definition 5.3

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

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

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

ς will range over valuations.

Definition 5.4

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

Define an interpretation ⟦r⟧I ς in S inductively 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 5.5

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

Lemma 5.6

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

Proof

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

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

Lemma 5.7

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

Proof

Routine induction using Lemmas 4.4 and 4.10.End of proof

Lemma 5.8

If r =α s then for all ς, ⟦r⟧I ς = ⟦s⟧I ς.

Proof

The non-trivial part is to check that if a ∉ fa(r) and b ∉ fa(r) then ⟦(a b)·r⟧I ς = ⟦r⟧I ς. Suppose a ∉ fa(r) and b ∉ fa(r). By Lemma 5.7 a ∉ supp(⟦r⟧I ς) and b ∉ supp(⟦r⟧I ς). By the definition of support in Definition 4.2, (a b)·⟦r⟧I ς = ⟦r⟧I ς. We use Lemma 5.6.End of proof

Definition 5.9

Suppose ς is a valuation to an interpretation I. Suppose X is an unknown and x ∈ (s(X))I is such that supp(x) ⊆ p(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 5.10

If Q is a set of numbers write min Q for the least and max Q for the greatest elements in Q, as is standard.

Definition 5.11

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

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

⟦φ⟧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) ⊆ p(X). By inductive hypothesis ⟦π·φ⟧I ς[X::=x] = 1 for all x ∈⟦α⟧I such that supp(x) ⊆ p(X). Therefore ⟦∀X.π·φ⟧I ς = 1. The result follows, since π·(∀X.φ) ≡∀X.π·φ.

• The case P(r). Suppose ⟦P(r)⟧I ς = 1, so PI(⟦r⟧I ς) = 1.

By assumption PI is an equivariant function, and it follows that PI(π·⟦r⟧I ς) = 1. By Lemma 5.6 π·⟦r⟧I ς = ⟦π·r⟧I ς. Thus PI(⟦π·r⟧I ς) = 1, and so ⟦π·P(r)⟧I ς = 1.End of proof

Lemma 5.13

If φ =α ψ then ⟦φ⟧I ς = ⟦ψ⟧I ς.

Proof

By routine calculations using Lemma 5.8 for α-equality of terms in propositions.End of proof

Definition 5.14 (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 5.15 (Soundness).

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

Proof

By induction on the derivation of Φ ⊢ Ψ (Figure 2). The case of (N) uses Lemma 5.12. The cases of (αL) and (αR) use Lemma 5.13. Other rules are routine by unpacking definitions.End of proof

6. Arithmetic

6.1 A language L for first-order logic

For this section, a, b, c, . . . range over distinct atoms in Aν, where Aν is the set of atoms used in ˙L in Section 3 (this is not necessary, but it is convenient).

Definition 6.1

Define terms and sentences 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 sentences. Derivability is as usual for first-order logic.

Definition 6.2

Define a mapping (-). from terms and sentences of L to terms of ˙L inductively as follows:

(a). = a (0). = 0(succ(t)). = succ((t).) (t′ + t). = (t′). + (t).(t′ ∗t). = (t′). ∗(t). (t′ ≈t). = (t′). ˙≈(t).(⊥). = ˙⊥(ξ′ ⇒ξ). = (ξ′). ˙⇒(ξ).(∀a.ξ). = ˙∀[a](ξ).
Definition 6.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 6.4

Write S for EQU ∪ SUB ∪ FOL.

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

6.2 Interpretation of first-order logic

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

Definition 6.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 6.20.

Definition 6.8

Define Valu𝔸ν (M) by:

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

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.

Give ε a permutation action defined by (π·ε)(a) = ε(π-1(a)). Give subsets X of Valu𝔸ν (M) the pointwise permutation action defined by π·X = {π·ε | ε ∈X}.

(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)
Figure 7: arithmetic: axioms for arithmetic in first-order logic

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 6.9

Valu𝔸ν (M) would normally just be called ‘the set of valuations’. We are more specific because we already have a notion of valuation on unknowns X (Definition 5.3).

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 (1). In any case, any term or sentence will only contain finitely many atoms.

Definition 6.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 6.11

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

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

6.3 Axioms and models

Definition 6.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 6.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,

6.4 Building an interpretation for ˙L out of one for L

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

Definition 6.14

Extend L to L+M where we add 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) = 0M always.

If t is a term, we write ⟦t⟧M for the function λε.⟦t⟧M ε . If ξ is a sentence, 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} oN = {⟦ξ⟧M | ξ a sentence of L+M}

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

varN a ε = ε(a) 0N ε = 0MsuccN 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.

Lemma 6.15

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

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

Lemma 6.16

The following equalities all hold:

varN(a) = ⟦a⟧M0N = ⟦0⟧MsuccN(⟦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 6.14 and 6.10. Most cases are immediate; we consider only the slightly less trivial ones:

varN(a) = (λa.λε.ε(a))a Definition 6.14= (λa.⟦a⟧M)a Definition 6.10= ⟦a⟧Mfact

subNι([a]⟦t′⟧M, ⟦t⟧M) = λε.⟦t′⟧M(ε[a::=⟦t⟧Mε]) Definition 6.14

= λε.⟦t′[a::=t]⟧MLemma 6.15

Other cases are no harder.End of proof

Lemma 6.17

N (Definition 6.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 6.14 map elements of ιN, oN, [A]ιN, and [A]oN correctly to the appropriate sets.

By Lemma 6.16.

ϵN is equivariant from oN to {0, 1}.

By routine calculations using the fact that (a b)·ε0 = ε0.End of proof

Lemma 6.18

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

Proposition 6.19

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] ∈(ξ). if and only if ε0[a::=(t).] ∈(ξ). 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 6.20

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 6.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 5.15) and Proposition 6.19, ⊨N (Ξ⊢χ).. By Lemma 6.18 Ξ ⊢χ is valid in M. M was arbitrary, so by completeness of first-order logic [29, §4.2] it follows that Ξ ⊢χ is derivable.End of proof

7. Other theories in PNL

We briefly sketch three other smaller, but relevant and interesting, PNL theories.

7.1 Inductive types

Permissive-nominal logic can express the principles of nominal abstract syntax developed in [22].

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 ∈ p(X).

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

∀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])

7.2 Freshness: from a ∉ fa(r) to a ∉ supp(x)

PNL has a notion of ‘free atoms of’ a ∈ fa(φ). Nominal sets have rather similar-looking notion of support a ∈ supp(x).

Support, or rather its negation freshness, is definable using equality, intuitively as

“a is fresh for x when (b a)·x = x for some/any fresh b.”

See e.g. equation 13 in [22].

To capture a freshness predicate for a name sort ν on a sort α in PNL, we assume EQU (or extend PNL with an equality primitive) and 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 ∈ p(X) and b ∉ p(X).

A detailed discussion of support as a definitional extension of equational reasoning is in Sections 5.2 and 6.1.1 of [18].

The reader should distinguish the notion ‘free atoms’ from the nominal sets notion ‘support’. These are two distinct concepts and they are not the same.

7.3 The rule (N), and the N quantifier

Nominal sets support the N-quantifier [22]. PNL does too, but in an unexpected and perhaps rather elegant manner.

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

∀x.(P(x)⇒Na.Q(a,x))∀x.Na.Nb.(ba)·x≈x==================∀x.Na.(P(x)⇒Q(a,x))=============================Na.Nb.∀x.(a#x⇒b#x⇒(ba)·x≈x)

Here and below we write a double horizontal line for ‘is provably equivalent to’. In PNL N is ‘hiding’ in the permission sets. Corresponding propositions are, where a, b ∉ p(X):

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

Two things are happening: freshness conditions are hard-coded into the syntax by permission sets — and so is N.

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

Na.P(a) ∧Na.Q(b) ================Na.Nb.(P(a) ∧Q(b))Na.P(a) ∧Na.Q(b) ==============Na.(P(a) ∧Q(a))

Correspondingly in PNL:

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

It is easy to use the rule (N) from Figure 2 to construct a derivation proving that P(a) ∧ Q(b) and P(a) ∧ Q(a) are indeed logically equivalent in PNL.

(N) expresses that truth is preserved by permutative renaming, or in symbols: ⊢φ ⇔π·φ always. We call this rule (N) because of another way of looking at matters: every atom in φ is abstracted by a generalised N-abstraction. Permission sets, or perhaps rather their complements, are a freshness quantifier.

8. Related work

Nominal terms Nominal terms were introduced in [31] where a decidable and efficient unification algorithm was demonstrated (see [3] for the state of the art). Nominal terms were then used in specification languages; in rewriting [10], and in universal algebra (the logic of equality) [18].

Nominal terms require a finite freshness context a#X. These are explicit assertions corresponding to a ∉ p(X).

Contrast a prototype of permissive-nominal term unification [25] with the Haskell Nominal Toolkit (HNT) [2]. Core functions in the PNL implementation (e.g. unification and alpha-equivalence checks) are pure. The types of their HNT counterparts are monadic because of explicit freshness contexts. The freshness context becomes a notion of state, which must be passed around in a monad.

Compare the types (1) of the alpha-equivalence check function from the HNT and (2) of the implementation of permissive-nominal terms:2

(1)alpha′check::(Showt,Eqt,Orda,Ordv)⇒FrsCtxtva→Termatv→Termatv→CSr(ExtBle(ErrorT[Char]))m()

(2) aeq :: (Eq a, Permissive b) ⇒ Term a b → Term a b → Bool

The type associated with the ‘permissive’ version is shorter. To be fair, HNT does a lot more and this is also responsible for some complexity. Nevertheless, we have seen a similar phenomenon, which has been truly inconvenient, in our own work [10, 11, 15, 17, 20].

Relative to nominal terms, PNL does without freshness contexts and adds quantification over unknowns.

Permissive-nominal terms Permissive-nominal terms were developed to address the concerns above [6, 7]. They simplify α-equality and freshness and separate them from equational reasoning. There is no ‘freshness monad’.

Permissive-nominal terms correspond to the term-language of PNL. Their unification algorithm, which is decidable and closer to the first-order case than that of nominal terms, extends easily to the syntax of PNL.

Relative to [7], we add first-order logic and in particular universal quantification ∀X over unknowns.

Nominal logic The two best-known ‘nominal’ logics are probably the nominal logic of [28] and FM set theory. Both are Hilbert-style theories — sets of axioms — in first-order logic.

FM set theory contains axioms whose intended model is the cumulative hierarchy of hereditarily finitely supported sets. Nominal logic contains axioms whose intended model is sets with a finitely-supported permutation action.

Natural deduction rules for N were proposed e.g. in [22, Proposition 4.10], but these are not closed under substitution. The second author created a proof-theory for N [12] with a good notion of proof-normalisation and a completeness proof, followed by an alternative treatment with Cheney [14]. These did not give N a direct operational behaviour as ‘pick a globally fresh name’; this was captured by Cheney in a later paper [4].

Cheney’s logic involves 12 infinite axiom-schemes (see Figures 3 and 4 of [4]). These describe atoms-abstraction as an equality theory.

PNL handles α-equivalence, and the N-quantifier, without recourse to axioms, and indeed, without requiring an equality or a N-quantifier. We can ‘just α-rename’; freshness and renaming are separated from equality reasoning in the logic.

Nominal logic from [28] is not complete for its semantics in nominal sets, for reasons discussed and addressed by Cheney in [5]. In fact, PNL is complete for the semantics in this paper; permissive-nominal sets with their infinite support are clearly related to Cheney’s support ideals.

The PNL proof system is ‘ϵ away’ from that of first-order logic. Arguably, it is more immediate to first-order logic than any other previous reasoning system based on nominal sets.

One-and-a-halfth order logic from [17] 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 3.

Semantic nominal terms In [19] 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 [22]. The aim of this paper is to discuss the logic; not to analyse how its syntax could best be built.

[19] does a few other things, and one of them is relevant to the logic of PNL: it defines a capturing and capture-avoiding substitution, which we plan to import into PNL in a later journal version of this work.

First- and higher-order logic As discussed in the Introduction, we see PNL as sitting between these two logics. It is better than first-order logic, in that term-formers can bind. It is better than higher-order logic in that its models are smaller and simpler, and its syntax supports a decidable unification algorithm.

PNL syntax and derivations can be translated to higher-order logic as nominal algebra can [21], though syntax may undergo a quadratic increase in size in the translation. We map to a pattern fragment of full higher-order syntax.

The issue is how naturally the structure of our intended axioms fits the structure of the logic — and also how naturally the semantics reflects any intuitions we have about those axioms. We feel that PNL does a very nice job of being first order and making binding convenient to work with in syntax and semantics.

Logics based on the ∇-quantifier A family of logics based on the ∇-quantifier [23, 24, 30] has been developed specifically for reasoning on inductive datatypes with binding. Permissive-nominal logic can do this too, and because of its ‘nominal’ ancestry it does so in the style of nominal techniques.

Logics based on ∇ use raising to obtain the effect of capturing substitution and variable dependencies, whereas we use a two-level term syntax.

∇ commutes with ∀-quantification and the N-quantifier does not; PNL does away with the N-quantifier altogether.

An interesting similarity is that some recent work in this field has also moved to using a syntax with name-constants and equivariance, reminiscent of the atoms and rule (N) [30]. We would like to give these logics models in nominal sets, which would give us a better view of where they stand in relation to our own work.

Contextual modal type theory (CMTT) Logics based on CMTT are consistent and have a well-studied proof-theory, so models can be constructed using normal forms. We do not know of what general class of possibly non-syntactic structures these syntactic models are instances. Developing such models would be interesting future work.

CMTT is a two-level system (contexts split into two halves; ∆ and Φ) but the two levels do a different job from the two levels used in (permissive-)nominal terms. Variables u : A[Φ] ∈∆ range over representations of code; x : A ∈ Φ range over denotation.

To the extent that this could be represented in PNL at all, it would be represented in the sorts — one sort for code, another for denotation (values).

Further logics Coming from other threads of research in computer science, there have been logics designed to enrich first-order logic directly with binders. We note binding logic [8] and λ-logic [1].

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

Unknowns of name sort, and atoms Should every inhabitant of the semantics of a name sort ν be referenced by an atom? Should every inhabitant of the semantics of name sorts be referenced by a closed term? In PNL as it stands, neither is necessarily the case.

This is only as much of an issue as we choose to make of it. It is not unusual for there to be more elements in a type than there are closed terms. It is a fact that PNL is complete for the semantics of this paper, so extra elements in name sorts cannot ‘make anything false’.

We can view ‘non-standard atoms’ like as like ‘non-standard numbers’ in first-order arithmetic; a price we pay for the first-order aspect of the language.

It is still reasonable to ask whether we can exclude these ‘non-standard atoms’. In fact, we believe that this is possible. The idea is in the proof-theory for N from ‘Fresh Logic’ [12]; see (ExhaustA) in Figure 3, and Subsection 5.5. This is a topic for future research.

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.

We might also assume, for every sort α, an associated name sort να. In particular, this would allow us to conveniently talk about ‘atoms (level 1 variables) associated with α’ in the same way that we can talk about ‘level 2 variables of sort α’.

Size of permission sets There is design freedom in the choice of permission sets. For example, we can take A uncountable and permission sets all countably infinite sets, or we can take permission sets {π(a) | a ∈A<\A, A⊆A finite, all π}. We do not currently see a ‘right’ choice. The choice in Definition 2.4 is simple.

Note the following: Suppose a base sort τ, a name sort ν and a : ν, a proposition-former P : τ, and a function-symbol f : (τ, ν)τ. In spite of this, ∀X.P(X) ⊬ P(f(X, a)) where a ∉ p(X), since no finite permutation maps p(X) to fa(f(X, a)) = p(X) ∪{a}.

On closed terms (with no unknowns), this is a non-issue because the syntax is finite and mentions finitely many atoms. Closed terms will be sufficient for many purposes; for example closed terms contains the image of the translation of first-order arithmetic in this paper; any sensible choices of permission set will thus allow us to write axioms as we have done in this paper.

In [19] we generalise the substitution action [X::=r] to the case that fa(r) ⊆ p(X) is not necessarily true. Developing this is future work.

Summary Permissive-nominal logic comes out of research into inductive definitions with names and binding in mechanised mathematics. It can also be applied to these problems.

But PNL provides a logical environment which, we feel, does a very good job of modelling the ‘informal meta-level’, complete with names, binding, and first-order reasoning.

Arguably its most exciting potential application is as a logical foundation — as a meta-theory for mathematics — intermediate in power between first- and higher-order logic. The case studies in this paper suggest that this could be feasible. We believe that, perhaps with some fairly modest extensions, it would make an expressive, ergonomic, and practical alternative meta-language for mechanised mathematics.

References

[1] Michael Beeson. Lambda logic. In Second International Joint Conference on Automated Reasoning (IJCAR 2004), volume 3097 of Lecture Notes in Computer Science, pages 460–474. Springer, 2004.

[2] Christophe Calvès. A Haskell nominal toolkit. In Proceedings of the 2nd International Workshop on Theory and Applications of Abstraction, Substitution and Naming (TAASN 2009), 2009.

[3] Christophe Calvès and Maribel Fernández. A polynomial nominal unification algorithm. Theoretical Computer Science, 403:285– 306, August 2008.

[4] James Cheney. A simpler proof theory for nominal logic. In FoSSaCS, volume 3441 of Lecture Notes in Computer Science, pages 379–394. Springer, 2005.

[5] James Cheney. Completeness and Herbrand theorems for nominal logic. Journal of Symbolic Logic, 71:299–320, 2006.

[6] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification. In Proceedings of the 24th Italian Conference on Computational Logic (CILC’09), 2009.

[7] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification (journal version). Logic Journal of the IGPL, 2010. In press.

[8] Gilles Dowek, Thérèse Hardin, and Claude Kirchner. Binding logic: Proofs and models. In Proceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2002), pages 130–144. Springer, 2002.

[9] William M. Farmer. The seven virtues of simple type theory. Journal of Applied Logic, 3(6):267–286, 2008.

[10] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting (journal version). Information and Computation, 205(6):917–965, 2007.

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

[12] Murdoch J. Gabbay. Fresh Logic. Journal of Applied Logic, 5(2):356–387, June 2007.

[13] Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205(7):982–1011, July 2007.

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

[15] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus (extended version). Information and computation, 207:1369–1400, 2009.

[16] Murdoch J. Gabbay and Aad Mathijssen. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing, 20(4-5):451–479, June 2008.

[17] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order Logic. Journal of Logic and Computation, 18(4):521–562, August 2008.

[18] Murdoch J. Gabbay and Aad Mathijssen. Nominal universal algebra: equational logic with names and binding. Journal of Logic and Computation, 19(6):1455–1508, December 2009.

[19] Murdoch J. Gabbay and Dominic P. Mulligan. Semantic nominal terms. In TAASN, 2009.

[20] Murdoch J. Gabbay and Dominic P. Mulligan. Two-level lambda-calculus. In Proceedings of the 17th International Workshop on Functional and (Constraint) Logic Programming (WFLP 2008), volume 246, pages 107–129, August 2009.

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

[22] Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing, 13(3–5):341–363, 2001.

[23] Andrew Gacek, Dale Miller, and Gopalan Nadathur. Combining generic judgments with recursive definitions. In Proceedings of the 23rd IEEE Symposium on Logic in Computer Science (LICS 2008), pages 33–44. IEEE Computer Society Press, 2008.

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

[25] Dominic P. Mulligan. Implementation of permissive nominal terms. Available at http://www2.macs.hw.ac.uk/˜dpm8/ permissive/perm.htm, 2009.

[26] Lawrence C. Paulson. The foundation of a generic theorem prover. Journal of Automated Reasoning, 5(3):363–397, 1989.

[27] Lawrence C. Paulson. Isabelle: the next 700 theorem provers. In P. Odifreddi, editor, Logic and Computer Science, pages 361–386. Academic Press, 1990.

[28] Andrew M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 186(2):165–193, 2003.

[29] Joseph Shoenfield. Mathematical Logic. Addison-Wesley, 1967.

[30] Alwen Tiu. A logic for reasoning about generic judgments. Electronic Notes in Theoretical Computer Science, 174(5):3–18, 2007.

[31] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473– 497, 2004.

Notes

1 We will write ((α1, . . . , αn))τ just as (α1, . . . , αn)τ. ↩

2 See the documentation for module Nominal.Matching at http://www.dcs.kcl.ac.uk/pg/calves/hnt/doc/Nominal-Matching.html and module Terms.Terms in the permissive-nominal terms implementation source code, available at http://www.macs.hw.ac.uk/˜dpm8/permissive/ ↩