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

Finite and infinite support in nominal algebra and logic: nominal completeness theorems for free

Murdoch J. Gabbay

http://www.gabbay.org.uk

Abstract

By operations on models we show how to relate completeness with respect to permissive-nominal models to completeness with respect to nominal models with finite support. Models with finite support are a special case of permissive-nominal models, so the construction hinges on generating from an instance of the latter, some instance of the former in which sufficiently many inequalities are preserved between elements. We do this using an infinite generalisation of nominal atoms-abstraction.

The results are of interest in their own right, but also, we factor the mathematics so as to maximise the chances that it could be used off-the-shelf for other nominal reasoning systems too. Models with infinite support can be easier to work with, so it is useful to have a semi-automatic theorem to transfer results from classes of infinitely-supported nominal models to the more restricted class of models with finite support.

In conclusion, we consider different permissive-nominal syntaxes and nominal models and discuss how they relate to the results proved here.

Key words: Permissive-nominal techniques, infinite support, finite support, nominal algebra, permissive-nominal logic, completeness, infinite atoms-abstraction.

February 11, 2012

1. Introduction

Nominal techniques are an approach to variables in syntax and semantics which give variables denotational reality as names. The semantics underlying nominal techniques are nominal sets [GP01], which identify variable symbols with names or (for set theorists) urelemente. We may call names/urelemente atoms and we write the set of all atoms as A.

According to nominal techniques, syntax and semantics both ‘contain’ atoms, in a sense made formal by a notion of support (see Definition 2.7).

The original applications of nominal sets and nominal terms [GP01, UPG04] admitted only finite support (the interested reader can find more applications listed on [Mul10]).

Permissive-nominal terms and models generalise this by allowing infinite support (based on a set of finitely representable but still infinite supporting sets called permission sets). Precise definitions will come later. For the benefit of the reader already familiar with nominal techniques we give a simple schematic for how this fits together:

nominal sets ↔ nominal terms

⊆ ⊆

permissive-nominal sets ↔ permissive-nominal terms

Both models and syntax seem better-behaved in the permissive case: we avoid the conditional reasoning typical of more traditional finitely-supported nominal techniques.1 This makes it possible to unify the semantic and syntactic notions of α-equivalence and freshness, to ‘just quotient’ terms by α-equivalence, and to cleanly add universal quantification. Some complex mathematical proofs become dramatically simpler. Precise examples are cited in the Conclusions of this paper.

So permissive-nominal techniques are arguably nicer to work with, but ‘ordinary’ nominal techniques are arguably more elementary (no infinities to confuse the reader)— and they are sufficient for many applications.

We indicate subset inclusions in the schematic above because models with finite support are special cases of models with infinite support, and it has been shown by arguments on syntax how to map from ‘ordinary’ nominal syntax to permissive-nominal syntax [DGM10, Section 4].

But what about the other way around?

In this paper, we explore models with differently-sized sets of atoms, give constructions to move from ‘larger’ to ‘smaller’ support, and test when these size transformations can and cannot be internally detected by the logics concerned. The main two results are Theorems 6.8 and 7.15—these follow from two technical results, Theorem 5.2 and Lemma 5.4.

Because our arguments are based on models, it is fairly easy to apply them to different syntaxes. In this paper we use the two examples studied in previous work by the author and others: nominal algebra [GM09] (an equality reasoning system whose term language is nominal terms) and permissive-nominal logic (ditto, for first-order logic) [DG12]. See also a recent survey paper, which covers both of these in a uniform presentation [Gab12b].

Structure of the paper

• In Section 2 we briefly introduce permissive-nominal sets, with examples. These will be our semantic universe in this paper; nominal sets from [GP01] are a special case.

• In Section 3 we introduce permissive-nominal terms: signatures, terms, α-equivalence, and their interpretation in permissive-nominal sets. The critical definition is Definition 3.13, which maps from syntax to semantics.

• Section 4 shows how to reduce the size of the support of a interpretation with ‘large’ support, to obtain a interpretation with ‘smaller’ support. This requires some interesting technical constructions. Notably, we consider atoms-abstraction by a list of atoms [l]x (Definition 4.3), and a permutative notion of restricting a permutation π/S (Definition 4.11).

• In Section 5 are three technical commutation results: the common theme is that reducing the size of the support of a interpretation commutes with the structure of that interpretation.

• Section 6 proves our first main theorem, that permissive-nominal algebra is complete over finitely-supported interpretations (Theorem 6.8).

• Section 7 introduces a novel notion of ‘medium support’ (Definition 7.4) and proves our second main theorem, that permissive-nominal logic over interpretations with medium support has the same validity as over interpretations with finite support (Theorem 7.15). We discuss what this means in Subsection 7.4.

• Section 8 discusses how the precise design of permission sets and permutations affects the proofs of this paper. We find that the results are delicate: even quite small changes can break the proofs (Propositions 8.2 and 8.5).

• We conclude with a technical discussion of our results, related work, and future work.

2. Permissive-nominal sets

We start with the basic definitions of permission sets, permissive-nominal sets, and then we give some examples.

2.1. Atoms, permutations, permission sets

Definition 2.1

Write N = {0, 1, 2, 3, . . .} for the natural numbers. and Z = {0, -1, 1, -2, 2, . . .} for the integers.

Definition 2.2

For each i ∈N fix a pair of disjoint countably infinite sets of atoms A<i and A>i. Write

A< =⋃A<i, A> =⋃A>i, Ai = A<i ∪A>i, and A = A< ∪A>.

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

Definition 2.3

Given a, b ∈Ai for some i ∈N write (a b) for the swapping bijection on atoms mapping a to b, b to a, and any other c ∈A \ {a, b} to c.

If π is a bijection on atoms define nontriv(π) = {a | π(a) ≠ a}. Write Pfin for the group of bijections (finitely) generated by swappings, and call these bijections permutations.

Write π◦π′ for the composition of π and π′ (so (π◦π′)(a) = π(π′(a))). Write id for the identity permutation (so id(a) = a always).

Lemma 2.4

A bijection π on atoms is a permutation if and only if

• a ∈Ai if and only if π(a) ∈Ai.

• nontriv(π) = {a | π(a) ≠ a} is finite.

Definition 2.5

If A ⊆A define the pointwise action by π·A = {π(a) | a ∈A}.

A permission set S is a set of the form π·A<. S, T will range over permission sets. The choices made in Definitions 2.3 and 2.5 make Theorems 6.8 and 7.15 work. These choices are possible within the framework of [Gab12b].

2.2. Permissive-nominal sets

Definition 2.6

A set with a permutation action X is a pair (|X|, ·) of a carrier set |X| and a group action on the carrier set (Pfin × |X|) →|X|, written infix as π·x.2

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

Definition 2.7

A permissive-nominal set is a set with a permutation action such that every element has a unique least supporting set supp(x) such that supp(x) ⊆S for some permission set S. We call this the support of x. X, Y will range over permissive-nominal sets.

In fact, if x ∈|X| has some supporting set A ⊆S, then it has a least one; see e.g. [DG10, Theorem 4.3].

Definition 2.8

If π is a permutation and A ⊆A write π|A for the restriction of π to A. This is the partial function such that π|A(a) = π(a) when a ∈A, and is undefined otherwise.

Lemma 2.9

Suppose X is a nominal set. Suppose x ∈|X| and A ⊆A supports x.

Then π|A = π′|A implies π·x = π′·x.

Proof

From the definition of support, considering π-1◦π′.End of proof

Lemma 2.10

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

Proof

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

We conclude with a useful condition for checking whether a ∈ supp(x):

Corollary 2.11

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

Proof

Suppose b ∉ supp(x). The right-to-left implication is by the definition of support. For the left-to-right implication, we prove the contrapositive. Suppose a ∈ supp(x). By Lemma 2.10 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

2.3. Examples

We briefly consider examples of permissive-nominal sets, which will be useful shortly.

Definition 2.12

A the set of atoms can be considered a permissive-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, and the permissive-nominal set with its natural permutation action.

Definition 2.13

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

(Compare Definition 2.13 with Definition 4.3.)

Remark 2.14

In the definition of [a]x in Definition 2.13 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} [Gab11a, Definition 3.8].

Lemma 2.15

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

Definition 2.16

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

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

• supp(a) = {a}.

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

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

Proof

Proofs are as in [GP01] or [Gab11a].End of proof

3. Permissive-nominal terms syntax and its interpretation

3.1. Signatures

Definition 3.1

A sort-signature is a tuple (A, B) of name and base sorts A ⊆N and B.

ν will range over name sorts; τ will range over base sorts. A sort language is defined by

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

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

• C is a set of constants.

• X is a set of unknowns.

• F is a set of term-formers.

• ar assigns

– to each constant C ∈C a base sort τ which we may write sort(C),

– to each unknown X ∈X a sort α which we write may sort(X), and

– to each f ∈F a term-former arity (α)τ, where α and τ are in the sort-language determined by (A, B).

• pmss assigns to each constant a set pmss(C) ⊆A<.

A (nominal terms) signature Σ is then a tuple (A, B, C, X, F, ar, pmss).

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

3.2. Terms

Definition 3.3

For each signature Σ = (A, B, C, X, F, ar, pmss), define terms over Σ by:

(a ∈Aν, ν ∈A) a : ν(sort(C) = τ) π·C : τ(sort(X) = α) π·X : αr : α (ar(f) = (α)τ) f(r) : τr1 : α1 . . . rn : αn(r1, . . . , rn) : (α1, . . . , αn)r : α (a ∈Aν, ν ∈A) [a]r : [ν]α

We may write f((r1, . . . , rn)) as f(r1, . . . , rn).

Definition 3.4

Define free atoms and the permutation action, and free variables on terms r as follows:

fa(a) = {a} fa(f(r)) = fa(r)fa(π·C) = π·pmss(C) fa((r1, . . . , rn)) = ⋃1≤i≤n fa(ri)fa(π·X) = π·A<fa([a]r) = fa(r)\{a}π·a = π(a) π·f(r) = f(π·r)π·(π′·C) = (π◦π′)·C π·(r1, . . . , rn) = (π·r1, . . . , π·rn)π·(π′·X) = (π◦π′)·X π·[a]r = [π(a)]π·rfv(a) = ∅ fv(f(r)) = fv(r)fv(π·C) = ∅ fv((r1, . . . , rn)) = ⋃1≤i≤n fv(ri)fv(π·X) = {X} fv([a]r) = fv(r)
Remark 3.5

In Definition 3.4 we in effect give every unknown permission set A< (so that fa(π·X) = π·A<). We obtain the effect of an unknown with permission set π·A< just by writing π·X. This simplified design makes Proposition 5.6 easier to express. It corresponds roughly to [Gab12b, Example 3.1.7(2)].

Lemma 3.6

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

Lemma 3.7

If π(a) = π′(a) for all a ∈ fa(r) then π·r = π′·r.

3.3. α-equivalence

Definition 3.8

A congruence is an equivalence relation R such that if r R s then f(r) R f(s) and (t1, . . . , r, . . . , tn) R (t1, . . . , s, . . . , tn) and [a]r R [a]s.

α-equivalence is then the least congruence such that if a, b ∉ fa(r) then (b a)·r =α r.3 We do not quotient terms by α-equivalence. The syntax [a]r is a formal pair of a and r. So for example, [a]X and [b](b a)·X for b ∉A< are different concrete terms.

In fact, we never use α-equivalence =α directly in this paper (it would be needed if we proved soundness and completeness, but these proofs are in other papers and are not included here). However =α lurks in the background, hard-wired into the denotation: it can be proved that if r =α s then r and s will always denote the same element in Definition 3.13.

3.4. Interpretation of signatures and terms

Definition 3.9

Suppose X and Y are permissive-nominal sets and F ∈|X| →|Y| is a function. Call F equivariant when F(π·x) = π·F(x) for all permutations π ∈Pfin and x ∈|X|.

Definition 3.10

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

A interpretation I for (A, B) consists of an assignment of a permissive-nominal set ⟦α⟧I to each sort α in (A, B), along with equivariant maps

• for each ν ∈A an equivariant and injective map Aν → ⟦ν⟧I which we write aI,

• for each ν ∈A and α an equivariant and injective map [Aν]⟦α⟧I →⟦[ν]α⟧I which we write [a]I x, and

• for each αi for 1 ≤i ≤n an equivariant and injective map Πi⟦αi⟧I→ ⟦(α1, . . . , αn)⟧I which we write (x1, . . . , xn)I .

Definition 3.11

Suppose Σ = (A, B, C, F, ar, pmss) is a signature (Definition 3.2).

A (Σ-)interpretation I for Σ, or Σ-algebra, consists of the following data:

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

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

• An assignment of a CI ∈⟦sort(C)⟧I to C ∈C, such that supp(CI) ⊆ pmss(C).

Definition 3.12

Suppose I is a Σ-algebra. A valuation ς to I is an equivariant function on unknowns X such that for each unknown X, ς(X) ∈⟦sort(X)⟧I.

ς will range over valuations.

Definition 3.13

Suppose I is a Σ-algebra. Suppose ς is a valuation to I .

Extend I to an interpretation on terms ⟦r⟧I ς (where of course r is a term in the signature Σ) by:

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

Lemmas 3.14 to 3.17 are proved by routine inductions:

Lemma 3.14

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

Lemma 3.15

If ς(X) = ς′(X) for every X ∈ fv(r) then ⟦r⟧I ς = ⟦r⟧I ς′ .

Lemma 3.16

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

Lemma 3.17

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

Looking ahead, later on in Section 6, we use interpretations to define a notion of validity with respect to a model or a collection of models, written H ⊨r = s and T ⊨r = s.

4. Reducing support of an interpretation

In this section we show how, given an interpretation H , to build an interpretation [m]H with ‘smaller’ support.

[m]H will have ‘almost the same structure’ as H . If two terms have a distinct denotation in H then their interpretation in [m]H is also distinct (Proposition 6.3, which is essentially Theorem 5.2 combined with Lemma 4.5).

As we shall see in Section 6, this result can be leveraged to proofs of completeness with respect to interpretations with finite support, assuming completeness with respect to all interpretations.

The idea of the construction is simple: in Definition 4.3 we take H and abstract all but finitely many atoms in its elements—in Definition 4.15 we show how to combine this with the interpretation of the term-formers of H .

One way to think of this, is that we replace atoms by numerical indexes (where a is identified with its position in the infinite list of abstractions which we impose). We can think of [m]H as a version of H with abstract de Bruijn indexes, where we recall that de Bruijn indexes are a method of representing object-level variables as numerical indexes [dB72] typically applied concretely to formal syntax rather than to models. More on this in the Conclusions.

4.1. Abstraction by atoms and by infinite lists of distinct atoms: [a]x and [l]x

Definition 4.1

Choose a fixed but arbitrary enumeration a-1, a-2, a-3, . . . of some subset of A<—since atoms are countable, this can be done. Write this enumeration as a list, l∗= [a-1, a-2, a-3, . . .].4

Define a permissive-nominal set L (parameterised by l∗) by:

π·l∗= [π(a-1), π(a-2), π(a-3), . . .] |L| = {π·l∗| all π}

l will range over elements of |L|.

It is very easy to check that L is indeed a permissive-nominal set, and that supp(l) is equal to the atoms in l.

We will be most interested in the cases of Definition 4.1 when l∗ enumerates all of A< (Section 6) and when l∗ enumerates ‘half’ of A< (Section 7). However, nothing in the mathematics below will depend on this.

Definition 4.2

If A ⊆A define fix(A) by:

fix(A) = {π | ∀a∈A.π(a) = a}
Definition 4.3

Suppose X is a permissive-nominal set and x ∈|X|. Suppose l ∈|L|. Define [l]x and [L]X as follows:

[l]x = {(π·l, π·x) | π ∈fix(supp(x)\supp(l))} |[L]X| = {[l]x | x ∈|X|, l ∈|L|} π·[l]x = [π·l]π·x
Remark 4.4

[l]x and [L]X mirror [a]x and [A]X from Definition 2.13, and have broadly similar properties. The idea of abstracting over infinitely many atoms was investigated in [Gab07] (see equation (2) in Subsection 2.1).

Lemma 4.5

Suppose X is a permissive-nominal set and x, y ∈|X|. Suppose l ∈|L|.

Then [l]x = [l]y if and only if x = y.

Proof

Clearly if x = y then [l]x = [l]y. Suppose [l]x = [l]y. By construction (l, x) ∈ [l]x, so also (l, x) ∈ [l]y. It follows that there exists π such that π·l = l and π·y = x, and π ∈ fix(supp(y) \ supp(l)). From π·l = l follows that π ∈ fix(supp(l)). It follows that π ∈ fix(supp(y)) and so by Lemma 2.9 that π·y = y.End of proof

Lemma 4.6

Suppose X is a permissive-nominal set and x ∈|X|. Suppose l ∈|L|.

Then supp([l]x) = supp(x)\supp(l).

Proof

By properties of the group action if π ∈ fix(supp(x)\supp(l)) then π·[l]x = [π·l]π·x.

Now suppose a ∈ supp(x)\supp(l) and choose any b fresh (so b ∉ supp(x) ∪ supp(l)). It is easy to use Lemma 2.10 to verify that every (l′, x′) ∈ [l]x satisfies a ∈ supp(x′) whereas every (l′, x′) ∈ (b a)·[l]x satisfies a ∉ supp(x′). It follows that (b a)·[l]x ≠ [l]x and so by Corollary 2.11 a ∈ supp([l]x).End of proof

Corollary 4.7

[L]X from Definition 4.3 is a permissive-nominal set.

Proof

That it is a set with a permutation action is clear. That every element has a supporting permission set follows from Lemma 4.6.End of proof

Lemma 4.8

Suppose X is a permissive-nominal set. Suppose ˆx ∈|[L]X| and l ∈|L| is such that supp(ˆx) ∩ supp(l) = ∅. Then there exists a unique element, write it ˆx@l ∈|X|, such that ˆx = [l](ˆx@l).

Proof

By Lemma 4.5 ˆx@l is unique if it exists.

Suppose supp(l) ∩ supp(ˆx) = ∅. By construction (Definition 4.3) ˆx = [l′]x′ for some l′ ∈L and x′ ∈|X|. By construction (Definition 4.1) l′ = π·l for some π.5 It is also a fact that since supp(l) ∩ supp(ˆx) = ∅ and (by Lemma 4.6) supp(l′) ∩ supp(ˆx) = ∅, we can suppose without loss of generality that nontriv(π) ∩ supp(ˆx) = ∅. It follows that ˆx = [l]π-1·x′ and so ˆx@l exists and is equal to π-1·x′.End of proof

Lemma 4.9

Suppose y1, . . . , yn ∈|[L]X|. Then for any l such that supp(l) ∩⋃ supp(yi) = ∅, there exist x1, . . . , xn ∈|X| such that yi = [l]xi for 1 ≤i ≤n.

Proof

We use Lemma 4.8 and take xi = yi@l.End of proof

4.2. Restricting permutations π/S

Intuitively, π/S (Definition 4.11) is the ‘smallest’ permutation to agree with π on S. π/S is ‘trying’ to be π|S (Definition 2.8) but π/S is a total function and furthermore is a permutation. The main result is Theorem 4.14, and we use π/S in Theorem 5.2.

As nominal techniques demonstrate, permutations are an attractive way to handle name-binding. Think of π/S as a version of π|S that we can use if we want to stay in the world of permutations.

Example 4.10

Suppose π = (a b c d e)(f g) (so π maps a to b to c to d to e to a, and f to g to f). Then:

π/{a} = (a b e) π/{a, b} = (a b c e)π/{a, c} = (a b c d e) π/{a, f} = (a b e)(f g)

Suppose π = (a b c d e f). Then

π/{b, e} = (a b c)(d e f) π/{b} = (a b c)π/{b, e, d} = (a b c d e f) π/{a, d} = (a b f)(c d e)

Recall the definitions of nontriv(π) and π from Definition 2.3.

Definition 4.11

Represent permutations π as cycles; so we write π as a finite set of finite cycles indexed by i ∈I where cycle number i has length αi > 1:

π = Πi∈I(ai1 ai2 . . . aiαi)

Define π/S as that permutation obtained as follows:

• Delete from the cycle representation of π above any atom a such that {a, π(a), π-1(a)} ∩S = ∅. That is, if there is any part of a cycle of the form ‘a1 a2 a3’ where a1 ∉S, a2 ∉S, and a3 ∉S, then we replace it with ‘a1 a3’. Repeat, until we cannot proceed.

• If there is any part of a cycle of the form ‘a1 a2 a3 a4’ where a1 ∈S and a4 ∈S but a2 ∉S and a3 ∉S, break the cycle into two subcycles as follows:

‘a1 a2)(a3 a4’.

In words:

π/S is obtained from π by eliding sequences of three or more consecutive atoms not in S, and then by splitting cycles at any two consecutive atoms not in S.

Lemma 4.12

π/S is well-defined.

Proof

At each step the size of nontriv reduces, so the rewrite system is terminating. It is not hard to check that rewrites are locally confluent. The result follows by Newman’s Lemma [New42].End of proof

Definition 4.13

Define π′ ≤S π when:

• π′|S = π|S

• (π′)-1|S = π-1|S

• For every cycle with atoms C′ in π′, there is a cycle with atoms C in π such that C′ ⊆C.

It is easy to verify that ≤S is a transitive reflexive relation. ≤S is not antisymmetric: if π = (a b c) and π′ = (a c b) and S = ∅ then π ≤S π′ and π′ ≤S π yet π ≠ π′.

Theorem 4.14

1. π/S is the unique ≤S-least permutation beneath π.

2. As a corollary, (π/S)|S = π|S and if π|S = π′|S and π-1|S = (π′)-1|S then π/S = π′/S.

Proof

By construction π/S contains only those atoms, in the smallest possible cycles, necessary to agree with π and π-1 on S.End of proof

4.3. Making support smaller

Given an interpretation H and a list of atoms m, we are interested in ‘subtracting’ m from the support of H , in some sense. The main definition is Definition 4.15, which builds an interpretation with smaller support out of an interpretation. For the cases we care about, ‘smaller support’ will mean finite support; this will come later in Lemmas 6.4 and 7.10, which are then used in Theorems 6.8 and Theorem 7.15 respectively. Here, we give the relevant construction.

Definition 4.15

Given a signature Σ, a Σ-interpretation H , and a list m ∈|L| construct a Σ-interpretation [m]H as follows:

⟦α⟧[m]H = {[l]x | l ∈|L|, x ∈⟦α⟧H } a[m]H = [l](aH ) (supp(l) ∌a) f[m]H ([l]x) = [l]fH (x)([l]x1, . . . , [l]xn)[m]H = [l](x1, . . . , xn)H[a][m]H ([l]x) = [l]([a]H x)C[m]H = [m]CH
Remark 4.16

A couple of comments on Definition 4.15:

The index m of [m]H is only used to interpret constants C. We have to choose some list of atoms to abstract—if our language did not admit non-equivariant constants, as was the case for the original Urban-Pitts-Gabbay syntax from [UPG04] or its permissive variant from e.g. [DGM10], then we could just write [L]H .

In the case of tuples, we know we can write every element in the form [l]xi for 1 ≤i ≤n for some xi, by Lemma 4.9.

Proposition 4.17

[m]H from Definition 4.15 is an interpretation.

Proof

It is routine to check that every condition in Definitions 3.10 and 3.11 is satisfied.End of proof

The next step is to build valuations to [m]H . This is Definition 4.18 and Proposition 4.19.

Definition 4.18

Suppose ς is a valuation to H and l ∈|L|. Define [l]ς by:

([l]ς)(X) = [l](ς(X))
Proposition 4.19

If ς is a valuation to H then [l]ς is a valuation to [m]H .

Proof

Consider an unknown X. By assumption ς(X) ∈⟦sort(X)⟧H and supp(ς(X)) ⊆ A<. By construction in Definitions 2.5 and 4.3, A< \ supp(l) is finite so by Lemma 4.6, supp([l]ς(X)) is finite. The result follows.End of proof

5. Three commutation results

Theorem 5.2, Lemma 5.4, and Proposition 5.6 are three commutation results. In Sections 6 and 7 we will use these as the technical ‘engine’ behind main theorems such as Theorems 6.8 and 7.15.

5.1. Atoms of a term

First, we need a technical tool atoms(r). We need this to express the side-condition atoms(r)∩supp(l) = ∅ in Theorem 5.2, and the side-condition atoms(r)∩nontriv(π) = ∅ in Proposition 5.6. Without these side-condition, the results would not hold.

Definition 5.1

Define atoms(r) inductively by:

atoms(a) = {a} atoms(f(r)) = atoms(r)atoms(π·C) = nontriv(π/pmss(C)) atoms((r1, . . . , rn)) = ⋃ atoms(ri)atoms(π·X) = nontriv(π/A<) atoms([a]r) = atoms(r) ∪{a}

atoms(r) collects the atoms ‘explicit’ in r. Contrast this with ‘free atoms of’ fa(r) from Definition 3.4 which collects the atoms ‘potentially’ in r. For instance, fa(X) = A< and is infinite, but atoms(X) = ∅. This is because X mentions no atoms explicitly, but intuitively it could be instantiated for any term with atoms in A<.

5.2. First commutation result

Recall from Definition 4.1 the construction of L, parameterised over some l∗.

Theorem 5.2

Suppose l ∈|L| and atoms(r) ∩ supp(l) = ∅. Then ⟦r⟧[l]H [l]ς = [l]⟦r⟧H ς .

Proof

By induction on r:

• The case a. We reason as follows:

⟦a⟧[l]H [l]ς = [l]aHDefs 3.13, 4.15, a ∉supp(l)= [l]⟦a⟧H ςDefinition 3.13

We know a ∉ supp(l) because we assumed atoms(r)∩supp(l) = ∅, and atoms(a) = {a}.

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

⟦π·X⟧[l]H [l]ς = π·[l]ς(X) Definition 3.13= (π/A<)·[l]ς(X) Lems 2.9 & 4.6, Thm 4.14= [l](π/A<)·ς(X) Fact= [l]π·ς(X) Lems 2.9 & 4.6, Thm 4.14= [l]⟦π·X⟧H ςDefinition 3.13

The fact above follows since we assumed atoms(π·X) ∩ supp(l) = ∅.

• The case [a]r, where a ∉ supp(l). We reason as follows:

⟦[a]r⟧[l]H [l]ς = [a][l]H ⟦r⟧[l]H [l]ςDefinition 3.13= [a][l]H [l]⟦r⟧H ςind. hyp.= [l]([a]H ⟦r⟧H ς ) Definition 4.15= [l]⟦[a]r⟧H ςDefinition 3.13

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

⟦π·C⟧[l]H [l]ς = π·[l]CHDefs 3.13 & 4.15= (π/pmss(C))·[l]CHLems 2.9 & 4.6, Thm 4.14= [l](π/pmss(C))·CHFact= [l]π·CHLems 2.9 & 4.6, Thm 4.14= [l]⟦π·C⟧H ςDefinition 3.13

The fact above follows since we assumed atoms(π·C) ∩ supp(l) = ∅.

• The case (r1, . . . , rn). We reason as follows:

⟦(r1, . . . , rn)⟧[l]H [l]ς = (⟦r1⟧[l]H [l]ς , . . . , ⟦rn⟧[l]H [l]ς )[l]HDefinition 3.13= ([l]⟦r1⟧H ς , . . . , [l]⟦rn⟧H ς )[l]H ind. hyp.= [l](⟦r1⟧H ς , . . . , ⟦rn⟧H ς )HDefinition 4.15= [l]⟦(r1, . . . , rn)⟧H ςDefinition 3.13

• The case f(r) ... is routine.End of proof

5.3. Second commutation result

Definition 5.3

Given an interpretation H , a valuation ς to H , and some X and x ∈ ⟦sort(X)⟧H with supp(x) ⊆A<, define ς[X := x] by:

ς[X := x](X) = x ς[X := x](Y ) = ς(Y )
Lemma 5.4

Suppose ς, X, and x are as in Definition 5.3. Suppose l ∈|L|. Then

([l]ς)[X:=[l]x]) = [l](ς[X:=x]).
Proof

By routine calculations.End of proof

5.4. Third commutation result

Definition 5.5

Suppose ς is a valuation. Suppose π is a permutation such that nontriv(π) ⊆ A<.

Define π◦ς by

(π◦ς)(X) = π·ς(X).
Proposition 5.6

Suppose nontriv(π) ⊆A< and atoms(r) ∩ nontriv(π) = ∅. Then ⟦r⟧H π◦ς = π·⟦r⟧H ς .

Proof

By a routine induction on r similar to that in Theorem 5.2:

• The case a. By assumption a ∉ nontriv(π).

• The case π′·X. By assumption nontriv(π)∩nontriv(π′/A<) = ∅. Since nontriv(π) ⊆ A< it is a fact that nontriv(π) ∩ nontriv(π′) = ∅. The result follows.

• The case [a]r, where a ∉ supp(l). By assumption a ∉ nontriv(π).

• The case π′·C. As for π′·X.

• The cases (r1, . . . , rn) and f(r) ... are routine.End of proof

6. Nominal algebra completeness relative to interpretations with finite support

We now have everything we need to set up two notions of validity ⊨ and ⊨fin (Definition 6.7) and prove our main result, that they are equal (Theorem 6.8).

Definition 6.1

Suppose r and s are terms in Σ, which is the signature of an interpretation H .

• Write H , ς ⊨r = s when ⟦r⟧H ς = ⟦s⟧H ς . • Write H ⊨r = s when H , ς ⊨r = s for every valuation ς to H .
Notation 6.2

For the rest of this section, we will take l∗ from Definition 4.1 to enumerate all of A<. We write the L so generated by Definition 4.1 as L<.

Recall the construction of [m]H from Definition 4.15.

Proposition 6.3

Suppose r and s are terms in Σ, which is the signature of an interpretation H . Suppose m ∈|L< |. Then:

1. If H ⊭r = s then [m]H ⊭r = s.

2. If H ⊨r = s then [m]H ⊨r = s.

Proof

For the first part, suppose H ⊭r = s. So there exists a valuation ς to H such that ⟦r⟧H ς ≠ ⟦s⟧H ς . Choose some l such that supp(l) ∩ (atoms(r) ∪ atoms(s)) = ∅. We can do this, because atoms(r) and atoms(s) are finite. By Theorem 5.2 ⟦r⟧[m]H [l]ς= [l]⟦r⟧H ς and ⟦s⟧[m]H [l]ς= [l]⟦s⟧H ς . By Lemma 4.5 [l]⟦r⟧H ς ≠ [l]⟦s⟧H ς . It follows that ⟦r⟧[m]H [l]ς≠ ⟦s⟧[m]H [l]ς .

For the second part, suppose that H ⊨r = s and suppose ς′ is a valuation to [m]H . Choose some l ∈|L< | such that

supp(l) ∩(atoms(r) ∪atoms(s) ∪⋃{supp(ς′(X)) | X ∈fv(r) ∪fv(s)})= ∅.

We can do this since all the sets on the right-hand side of ∩ are finite.

Using Lemmas 4.9 and 3.15 there exists a valuation ς to H such that ⟦r⟧[m]H ς′= ⟦r⟧[m]H [l]ς and ⟦s⟧[m]H ς′= ⟦s⟧[m]H [l]ς . We now reason using Theorem 5.2 and Lemma 4.5, as in the first part.End of proof

The model [m]H is composed of ordinary—i.e. finitely-supported—nominal sets, in the sense of [GP01]:

Lemma 6.4

Every [l]x ∈ ⟦α⟧[m]H has finite support.

Proof

It suffices to observe Lemma 4.6 and note that by assumption supp(x) is contained in a permission set, and by assumption in Notation 6.2 supp(l) is a permission set, and by construction permission sets differ finitely from one another.End of proof

Definition 6.5 is standard, e.g. from [GM09] (nominal) or [Gab12b] (permissive-nominal):

Definition 6.5

A (permissive-)nominal algebra theory T = (Σ, Ax) is a pair of a signature Σ and a set of equality axioms Ax. (So elements of Ax are pairs r = s.)

Suppose H is a Σ-interpretation (Definition 3.11). Write H ⊨ T to mean that for every valuation ς to H and every (r = s) ∈ Ax, ⟦r⟧H ς = ⟦s⟧H ς .

Definition 6.6

Suppose Σ is a signature and F is a Σ-interpretation. Say that F has finite support when for every sort α in Σ and every x ∈|⟦α⟧F|, it is the case that supp(x) is finite.

Definition 6.7

Suppose T = (Σ, Ax) is a theory. Then:

• Define T ⊨fin r = s to mean that F ⊨ T implies F ⊨r = s, for every Σ-interpretation F with finite support.

• Define T ⊨r = s to mean that H ⊨ T implies H ⊨r = s, for every Σ-interpretation H .

Theorem 6.8

Suppose that T is a Σ-theory.

Then T ⊨fin r = s if and only if T ⊨r = s.

Proof

The right-to-left implication is immediate since an interpretation with finite support is an interpretation.

For the left-to-right implication we prove the contrapositive. Suppose T ⊭r = s. So there is an interpretation H such that H ⊨ T and a valuation ς to H such that ⟦r⟧H ς ≠ ⟦s⟧H ς .

Choose any m ∈|L< |. By part 2 of Proposition 6.3 [m]H ⊨ T. By part 1 of Proposition 6.3 [m]H ⊭r = s, and by Lemma 6.4 we are done.End of proof

Permissive-nominal algebra is sound and complete with respect to permissive-nominal models (the proof is by a Herbrand construction; see [Gab12b, Subsection 7.5]). So the relevance of Theorem 6.8 is to give completeness also with respect to interpretations with finite support.

7. Permissive-nominal logic

Permissive-nominal logic (PNL) extends signatures with proposition-formers P with arity α. It is ‘first-order logic over (permissive-)nominal terms’.

Full details can be found in [DG10, DG12] or [Gab12b, Section 9]. Here, we only give the necessary outline.

7.1. Sketch of permissive-nominal logic

Definition 7.1

PNL propositions are defined by

φ, ψ ::= ⊥| φ⇒φ | ∀X.φ | P(r)

where we insist that r : α (where α is the arity of P).

Definition 7.2

if X is a nominal set and U ⊆|X| call U equivariant when x ∈U ⇔π·x ∈ U for all x ∈|X| and all permutations π.6

Definition 7.3 corresponds to e.g. [DG10, Definition 5.11].

Definition 7.3

An interpretation H maps a term to an element of a permissive-nominal set as in Definition 3.13, and maps each P to an equivariant subset PH ⊆ ⟦α⟧H .

This extends to propositions φ just as in first-order logic where ⟦φ⟧H ς is a truth-value ⊤ or ⊥, as follows:

• ⟦⊥⟧H ς (the syntax) is equal to ⊥ (the truth-value).

• The PNL of [DG10, DG12, Gab12b] is classical, so ⟦φ⇒ψ⟧H ς is interpreted as ‘not ⟦φ⟧H ς or ⟦ψ⟧H ς ’.

• ⟦P(r)⟧H ς is equal to ‘⟦r⟧H ς is an element of PH ’.

• The only non-obvious case is the universal quantifier, which gets a denotation as follows:

⟦∀X.φ⟧H ς =⋀{⟦φ⟧H ς[X := x] | x ∈⟦sort(X)⟧H , supp(x) ⊆A<}

This is non-obvious because the ∀X in ∀X.φ quantifies only over x with support in A<. More discussion on this in the Conclusions.

7.2. Three notions of validity in denotations

Three distinct notions of validity will interest us. They are parameterised by ‘how many atoms’ they allow in support. This is Definition 7.6; to express it, we need Definition 7.4.

Definition 7.4

For each i ∈N fix some set A<<i ⊆A<i such that A<<i and A<i \ A<<i are both infinite. Write A<< = ⋃i A<<i and:

• Say that x ∈ ⟦α⟧H has medium support when supp(x) ⊆π·A<< for some π.

• Say that H has medium support when for every sort α and every x ∈ ⟦α⟧H , x has medium support.

Remark 7.5

The point of Definition 7.4 is that x with medium support may have infinite support, but this support cannot exhaust the atoms in A<. But did we not see this already in Definition 2.2 when we split A into A< and A>? Yes, but PNL has a ∀X, so that now (and unlike was the case in permissive-nominal algebra) we have to worry about exhausting all the atoms in A< within nested quantifiers. To see this idea made concrete, consider the proof of Proposition 7.7.

Definition 7.6

• Write ⊨φ to mean that H , ς ⊨φ for every interpretation H and valuation ς to H .

• Write ⊨<< φ to mean that H , ς ⊨<< φ for every interpretation H with medium support and valuation ς to H .

• Write ⊨fin φ to mean that F , ς ⊨φ for every interpretation F with finite support and valuation ς to F .

Proposition 7.7

⊨φ implies ⊨<< φ. The reverse implication does not necessarily hold.

Proof

The first part is immediate since an interpretation with medium support is also an interpretation.

For the second part it suffices to provide a counterexample. Suppose a base sort τ and name sort ν and variables X : τ and Y : ν. Suppose a predicate # : (ν, τ) with intended meaning ‘is fresh for’/‘is not in the support of’. Consider the formula φ = ∀X.∃Y.Y #X. Then ⊨fin φ and ⊨<< φ, but not ⊨φ; it might be that ς(X) = l where l lists all atoms in A<, so there exists no atom in A< (by Definition 7.3, Y ranges over atoms in A<) that is not in supp(l).End of proof

The rest of this section is devoted to proving that ⊨<< φ if and only if ⊨fin φ (Theorem 7.15). We discuss the relevance of these results in Subsection 7.4.

7.3. Finite support denotations from medium support denotations

Notation 7.8

For the rest of this section, we will take l∗ from Definition 4.1 to enumerate A<<. We write the L generated by Definition 4.1 as L<<.

Definition 7.9

Given a PNL interpretation H with medium support and a list m ∈|L<<|, generate a PNL interpretation [m]H by extending Definition 4.15 such that

P[m]H = {[l]x | x ∈PH , l ∈|L<<|}.

Where does the m in [m]H appear on the right-hand side here? It does not: m is only used to reduce the support of the interpretations of constant symbols; see Definition 4.15. PNL only allows equivariant (Definition 7.2) interpretation of proposition-formers. If we considered a flavour of PNL in which proposition-formers could receive non-equivariant interpretation (so that in the syntax we would allow terms of the form (π·P)(r)), then Definition 7.9 would mention m on the right. This makes no difference to expressivity since we can emulate the effect of a non-equivariant proposition-former using P(C, r). Our design follows the path of the simplest definitions and proofs.

Lemma 7.10

Every [l]x ∈ ⟦α⟧[m]H has finite support.

Proof

As for Lemma 6.4, but now using Notation 7.8 and our assumption that x ∈ ⟦α⟧H has medium support.End of proof

Definition 7.11

Extend atoms(r) (Definition 5.1) to propositions atoms(φ) inductively by:

atoms(⊥) = ∅ atoms(φ⇒ψ) = atoms(φ)∪atoms(ψ)atoms(P(r)) = atoms(r) atoms(∀X.φ) = atoms(φ)

Lemma 7.12 extends Proposition 5.6 to predicates, and is needed for Proposition 7.14. Recall from Definition 5.5 the definition of π◦ς:

Lemma 7.12

Suppose ς is a valuation to an interpretation H . Suppose φ is a predicate and π a permutation such that nontriv(π) ⊆A< and nontriv(π) ∩ atoms(φ) = ∅.

Then ⟦φ⟧H π◦ς = ⟦φ⟧H ς .

Proof

By a routine induction on φ. We consider two cases:

• The case of P(r). By definition ⟦P(r)⟧H π◦ς = ⊤ if and only if ⟦r⟧H π◦ς ∈ PH . By Proposition 5.6 ⟦r⟧H π◦ς = π·⟦r⟧H ς . By assumption PH is equivariant (Definition 7.2).

• The case of ∀X.φ.

⟦∀X.φ⟧H π◦ς = ⋀{⟦φ⟧H (π◦ς)[X:=x] | x ∈⟦sort(X)⟧H , supp(x) ⊆A<} = ⋀{⟦φ⟧H (π◦ς)[X:=π·x] | x ∈⟦sort(X)⟧H , supp(x) ⊆A<} = ⋀{⟦φ⟧H π◦(ς[X:=x]) | x ∈⟦sort(X)⟧H , supp(x) ⊆A<} = ⋀{⟦φ⟧H ς[X:=x] | x ∈⟦sort(X)⟧H , supp(x) ⊆A<} = ⟦∀X.φ⟧H ςEnd of proof
Lemma 7.13

fa(φ) ⊆A< ∪ atoms(φ) and fa(r) ⊆A< ∪ atoms(r).

Proof

By a routine induction on Definitions 5.1 and 7.11 and by a routine calculation using part 2 of Theorem 4.14 for the base case of π·X.End of proof

Proposition 7.14

Suppose φ is a proposition, H is a PNL interpretation with medium support (Definition 7.4), and ς is a valuation to H . Suppose A ⊆A is a finite set of atoms such that atoms(φ) ⊆A, and suppose l ∈|L<<| and supp(l) ∩A = ∅.

Then H , ς ⊨φ if and only if [l]H , [l]ς ⊨φ.

Proof

By induction on φ. We consider a selection of cases:

• The case of P(r). We consider the two implications separately. (⇐) Suppose [l]H , [l]ς ⊨ P(r). This means that ⟦r⟧[l]H [l]ς∈ P[l]H . By Theorem 5.2 ⟦r⟧[l]H [l]ς= [l]⟦r⟧H ς (note that atoms(P(r)) = atoms(r)), and so by Definitions 7.9 and 4.3 π′·⟦r⟧H ς∈ PH for some π′ ∈ fix(supp(⟦r⟧H ς ) \ supp(l)). By equivariance of PH it immediately follows that ⟦r⟧H ς ∈ PH and so that H , ς ⊨ P(r). (⇒) Now suppose H , ς ⊨ P(r), so that by definition ⟦r⟧H ς∈ ⟦P⟧H . As in the previous paragraph by Theorem 5.2 [l]⟦r⟧H ς = ⟦r⟧[l]H [l]ς . It follows by Definition 7.11 that ⟦r⟧[l]H [l]ς ∈ P[l]H .

• The case of ∀X.φ. Again we consider the two implications separately: (⇐) Suppose H , ς ⊭∀X.φ. Unpacking definitions, this means there is some x ∈|⟦sort(X)⟧H | with supp(x) ⊆A< and H , ς[X:=x] ⊭φ. By inductive hypothesis [l]H , [l](ς[X:=x]) ⊭φ. We can use Lemma 5.4 to write [l](ς[X:=x]) as ([l]ς)[X:=[l]x]. Furthermore, by assumption supp(x) ⊆A< so by Lemma 4.6 supp([l]x) ⊆A< \ supp(l) ⊆A<. It follows by Definition 7.3 that [l]H , [l]ς ⊭∀X.φ. (⇒) Suppose [l]H , [l]ς ⊭∀X.φ. Unpacking Definition 7.3 this means there are x′ ∈|⟦sort(X)⟧H | and l′ ∈|L<<| such that

supp([l′]x′) ⊆A<and [l]H , ([l]ς)[X:=[l′]x′] ⊭φ.

If supp([l′]x′) ∩ supp(l) = ∅ then we may use Lemma 4.8 and write [l′]x′ as [l](([l′]x′)@l) and deduce by inductive hypothesis that H , ς ⊭φ. Otherwise, we choose some π′ that maps supp([l′]x′)∩supp(l) ≠ ∅ to a set of atoms in A< that is disjoint from supp(l) ∪ atoms(φ), and π′ fixes all other atoms. This is possible because by construction supp([l′]x′) is finite and A< \ (supp(l)∪atoms(φ)) is infinite (recall that A< \ A<< is assumed infinite). Using Lemma 7.12

[l]H , ([l]ς)[X:=π′·([l′]x′)] ⊭φ.

We now proceed as in the case where supp([l′]x′) ∩ supp(l) = ∅.

• The case of φ⇒ψ. Suppose H , ς ⊨φ⇒ψ. This means that H , ς ⊭φ or H , ς ⊨ψ. By inductive hypothesis this is if and only if [l]H , [l]ς ⊭φ or [l]H , [l]ς ⊨ψ. In either case [l]H , [l]ς ⊨φ⇒ψ, and we are done.End of proof

Theorem 7.15

⊨fin φ if and only if ⊨<< φ.

Proof

The right-to-left implication is immediate, just as in Theorem 6.8. The left-to-right implication follows using Proposition 7.14 and Lemma 7.10.End of proof

7.4. Relevance of the theorem

It will help to establish some new terminology:

Notation 7.16

Suppose X is a set with a permutation action and x ∈|X|.

• Say the element x ∈|X| is finite-namespace when supp(x) is finite. Similarly say X is finite-namespace when every x ∈|X| has finite support. This is synonymous with X being a nominal set in the sense of [GP01]; cf. also Definition 6.6.

• Say x is A<<-namespace when supp(x) ⊆π·A<< for some π. Similarly say that X is A<<-namespace when every x ∈|X| is A<<-namespace. This is synonymous with medium support from Definition 7.4.

• Say x is A<-namespace when supp(x) ⊆π·A< for some π. Similarly say that X is A<-namespace when every x ∈|X| is A<<-namespace. This is synonymous with X being a permissive-nominal set in the sense of Definition 2.7 or [Gab12b].

Similarly we will call interpretations finite-namespace, A<<-namespace, and A<-namespace in accordance with the support of their underlying sets.

The relevance of Theorem 7.15 is that a PNL predicate is valid over A<<-namespace interpretations if and only if it is valid over finite-namespace interpretations.7

The PNL of [DG10, DG12, Gab12b] has a sequent system giving a notion of logical entailment which is proved sound and complete for ⊨, that is, for the collection of A<-namespace interpretations. This differs from the validity ⊨<<, which is validity over A<<-namespace interpretations (those with medium support). This is a more restricted class of models.

Medium support is a new idea to the theory of PNL. When models are restricted, more statements become valid (usually). In this case we get a family of theorems, which is exemplified by Proposition 7.7. It remains to devise a complete proof system for PNL over medium support.

We would not speculate on whether large or medium support is ‘better’; we suspect that the situation is similar to the intuitionistic/classical question of whether to allow double negation elimination: sometimes we may want it and sometimes we may not.

The value of Theorem 7.15 is that it tells us that A<< is as small as we need go in exploring validity: restricting models of PNL further to smaller namespaces, and in particular to finite support, will not give us any extra valid propositions. As we shall argue in the Conclusions, working with sets with infinite support can be easier than working with sets with finite support, so this matters.

And note the obvious: once we carried out our constructions and applied them to permissive-nominal algebra, we could re-use them for permissive-nominal logic with a relatively slight effort of two pages of mathematics in Subsection 7.3.

8. More permission sets, more permutations

In Definition 2.5 we followed [Gab12b] and took permission sets to be sets of the form π·A<. This captures a simple assertion language about the atoms permitted in unknowns. The results in this paper are sensitive to the expressivity of this language: if we make it slightly more powerful then the results in this paper fail.

8.1. More permission sets

If we follow e.g. [DGM10] and take permission sets to be sets of the form (A< \A)∪B where A ⊆A< and B ⊆A> are finite, then the results in this paper fail.

This genuinely enlarges the set of permission sets (and so makes the assertion language which they represent, more expressive). For instance, if b ∈A> then there is no finite permutation π such that π·A< = A< ∪{b}.

Notation 8.1

Write P for the set of all sets of atoms differing finitely from A< as just described.

Proposition 8.2

There exists a theory T in permissive-nominal algebra with permission sets from P, and an assertion r′ = s′ in that theory, such that T ⊨fin r′ = s′ and T ⊭r′ = s′ (where models are permissive-nominal sets with permission sets in P).

Proof

Assume one base type τ and one term former 0 : τ with pmss(0) = ∅. Assume an axiom X = 0 where fa(X) = A<. Assume an unknown Z with sort(Z) = τ and fa(Z) = A< ∪{b} where b ∈A>. Then:

• T ⊨fin Z = 0.

For suppose F is an interpretation of T with finite support: then for any x ∈ ⟦τ⟧F, there is some finite π with supp(π·x) ⊆A<, hence by our single axiom π·x = 0 and by equivariance x = π-1·0 = 0, since 0 has empty support.

• However, T ⊭Z = 0. To see this, interpret τ to be the set {π·(A< ∪{b}) | π finite} ∪{∅}, interpret 0 by ∅, and take ς(Z) = A< ∪{b}.End of proof

Initially we used P; notably in [DG10, DGM10, DG12]. However, in later papers such as [Gab12b] we preferred the design of Definition 2.5 because it seemed to make some proofs easier to express. In the light of the results of this paper we can now better understand the significance of our design choices: Proposition 8.2 suggests that our design in Definition 2.5 is mathematically more elementary and somewhat closer to the design ‘nominal terms + finitely-supported nominal sets’ from the previous literature. That is, the design of Definition 2.5 and [Gab12b] is the closest ‘permissive’ version of traditional nominal techniques, and the design of [DG10, DGM10, DG12] is slightly but measurably more expressive.

8.2. shift-permutations

In the presence of infinite permutations, the results in this paper fail. We sketch the mathematics involved, starting with a justification of why infinite permutations are an interesting case to consider.

For simplicity assume a single sort of atom.

Definition 8.3

Suppose a ∈A< = {a, a-1, a-2, a-3, . . . } and A> = {a1, a2, a3, . . . }.

Assume a bijection δ on atoms mapping A< to A< \ {a} and such that A \ nontriv(π) is infinite (we can do this because we assumed that A is countable).

We illustrate an example:

Illustration of δ: a-6a-5a-4a-3a-2a-1a a1a2a3a4a5a6

Call δ a shift-permutation.

δ has a measurable and favourable effect on the mathematics and algorithmics of nominal syntax. For instance:

• δ nontrivially increases the deductive power of ∀X in PNL [DG12, Subsection 2.7]. If fa(X) = A< where a ∈A< then ∀X.R(X, X) does not entail R((X, a), (X, a)) without δ, but it does entail R((X, a), (X, a)) with δ (for R having an appropriate arity). This extra power is irrelevant if we only care about finitely-supported models, which is why the issue has not arisen in previous work.

• shift-permutations can be used to obtain a particularly concise unification algorithm [Gab12b, Section 4].

For more discussion see [Gab12b, Subsection 3.6].

This extra power is not particularly expensive: we can do what we are used to in nominal techniques, in the presence of δ. Indeed, the results of [Gab12b] are parameterised over a permutation group general enough to admit δ because this was easier than excluding it. In particular the specific design of the nominal unification algorithm and HSP result there, are shorter and simpler because of their use of δ.

However, in the presence of δ the results of this paper fail. Proposition 8.5 gives an example of a signature for which permissive-nominal algebra ⊨ (all permissive-nominal models) is complete, but ⊨fin (models with finite support) are not. In order to state this result we must ‘upgrade’ the material in this paper with δ.

Definition 8.4

To augment Sections 2 and 3 with a shift permutation δ, we proceed as follows:

1. In Definition 2.3 permutations are finitely generated by swappings and δ (they remain finitely representable, but nontriv(π) is now not always finite). Write Pδ for the group of bijections generated by swappings and δ.

2. In Definition 2.6 assume the permutation action has type (Pδ × |X|) →|X|. So permissive-nominal sets have an action by swappings and δ.

3. In Definition 2.6 we say that A ⊆A supports x ∈|X| when for every permutation π ∈Pδ, if π(a) = a for all a ∈A then π·x = x.8

4. In the examples of Subsection 2.3 extend for the extra permutations in the natural way. So π·a = π(a) for π ∈Pδ and π·[a]x = [π(a)]π·x for π ∈Pδ.

5. In Definition 3.3 extend terms also with the extra permutations. So π·X is a term for π ∈Pδ. The permutation action Definition 3.4 extends in the natural way.

6. We extend the notion of equivariance (Definition 3.9) with the extra permutations. So F is equivariant when F(π·x) = π·F(x) for all permutations π ∈Pδ and x ∈|X|.9

Proposition 8.5

There exists a theory T in permissive-nominal algebra with δ, and an assertion r′ = s′ in that theory, such that T ⊨fin r′ = s′ and T ⊭r′ = s′ (where models are permissive-nominal sets with δ).

Proof

Assume no term-formers and one base type τ. Assume a ∈A< and a shift permutation δ bijecting A< with A< \ {a}, as illustrated just after Definition 8.3.

Assume an axiom (b a)·X = X where b ∉A<. Then:

• If F is a model of T with finite support then supp(x) = ∅ for every x ∈ ⟦τ⟧F. For suppose there exists x with supp(x) ≠ ∅. By equivariance we may (apply a permutation to x to) assume without loss of generality that a, b ∉ supp(x).

Now choose some a′ ∈ supp(x) and choose some π mapping supp(x) to a subset of A< and such that specifically π(a′) = a. By our axiom, (b a)·(π·x) = π·x. It follows by calculations on permutations that (b a′)·x = x and so by Corollary 2.11 that a′ ∉ supp(x), a contradiction.

Thus, T ⊨fin δ·Y = Y .

• T ⊭δ·Y = Y . To see this consider the elements xi = {(π◦δi)·A< | π finite} with the pointwise action, for every i ∈Z (where Z is the integers; see Definition 2.1). It is a fact that (b a)·xi = xi, but it is also a fact that δ·xi = xi+1 ≠ xi. We interpret τ to be the set {xi | i ∈Z} and see that (b a)·xi = xi for every i so the axiom (b a)·X = X is valid, but δ·x0 ≠ x0 so T ⊭δ·X = X. This observation is exactly the fuzzy support noted in [Gab07], see also Remark 3.3 from [DG12].End of proof

Remark 8.6

Where do the proofs fail? Failure occurs in the interaction of atoms(r) (Definition 5.1) with Theorem 5.2.

The reasonable definition for atoms(δ·X) is nontriv(δ)/A<, which is infinite. This gives us infinitely many atoms to avoid in order to guarantee atoms(r) ∩ supp(l) = ∅ in Theorem 5.2. Thus, supp([l]⟦r⟧H ς ) need not be finite.

As a corollary we can clarify something that is evident but only semi-formal in previous work: permissive-nominal terms with δ are strictly more expressive than permissive-nominal terms without δ, and also strictly more expressive than ‘ordinary’ nominal terms.

9. Conclusions

We have seen permissive-nominal sets and how, given a permissive-nominal set X, we can build a corresponding nominal set [L]X from X by applying to each x ∈|X| an infinite simultaneous atoms-abstraction abstracting all but finitely many of the atoms in supp(x). We have used this to translate between interpretations with differently sized sets of support, and we have used this translation to translate between different notions of validity for permissive-nominal syntaxes.

It can be easier to work with permissive-nominal models—even dramatically easier. To see an example, compare the direct completeness proof for nominal algebra with respect to finitely-supported models in [GM09] (subsections 4.3 and 4.4; over five pages including a ‘trick’) with the completeness proof for the permissive-nominal algebra used in this paper with respect to permissive-nominal models in [Gab12b] (subsection 7.5; under two pages, and the maths is straightforward). Even more extreme, compare the proof of the Nominal HSPA theorem from [Gab09] (twenty-eight pages) with the permissive-nominal HSP theorem from [Gab12b] (five pages).10

What this means is that—based on this author’s experience—even if the reader is interested specifically in finitely-supported models, it might be shorter and cleaner to prove completeness with respect to some flavour of infinitely-supported permissive-nominal models first, and then to use this paper off-the-shelf.

de Bruijn indexes. The technical construction at the heart of this paper, [L]X from Definition 4.3, is arguably reminiscent of de Bruijn indexes [dB72]. Given an x ∈|X| with infinite support, we form [l]x where supp(x) \ supp(l) is finite. In doing this, we in effect convert all but finitely many of the atoms in supp(x) into numerical indexes, where a is identified by the position in l at which it occurs (if any).

Of course this is not a literal replacement in x, since we assume no internal structure. But it is an abstract de Bruijn indexing in the sense that binding names in order corresponds to turning them into numerical indexes. An explicit connection is made in [Gab07, Section 4] as mentioned below.

Infinite sets of atoms in the literature. The notions of infinite support, infinite lists of atoms, and infinite simultaneous atoms-abstraction were considered by the author in [Gab02, Gab07].

Translations between nominal abstract syntax, name-carrying syntax, and de Bruijn syntax were given in [Gab07, Section 4]. The precise definition used in this paper is different and tailored to our intended application (e.g. we restrict to abstractions such that supp([l]x) is finite), and of course, we concentrate on things other than abstract syntax.

The notion of not-necessarily-finite support was also raised in [Pit03], and Cheney took up the suggestion in [Che06]. The support ideals considered there are not quite the same as the permission sets considered here (for instance, permission sets in this paper are never finite, and the emphasis on well-orderings is absent in Cheney’s work), but the spirit of the maths is similar.

Implicit connection with unknowns. A non-evident connection exists between [l]x and unknowns, which this paper has not explored. Elsewhere we explore how a model of unknowns X is given by infinite well-orderings of permission sets [Gab11b, Gab12a].

One way to view [l]x is as ‘x abstracted by an unknown X’.

Now L from Definition 4.1 is a single permutation orbit under finite permutations of some list l∗ of atoms. This author calls this a namespace—L is a namespace, that is, a set of sets of atoms (in order) obtained by permuting finitely many of them at a time. We go from X to [L]X essentially by abstracting a namespace, and because an unknown identifies a namespace, this can be read as a (level 1) abstraction of (the atoms in) a level 2 variable.

This paper does not make anything of these connections, but they exist in the background. At some point, we hope to produce a broader account which will bring the threads in the various papers together and makes clearer the overall picture. For now, the results in this paper have independent interest as discussed above.

shift-permutations. We concluded the technical part of this paper in Section 8 by discussing shift-permutations. These infinite permutations are useful and mathematically well-behaved, but they mark a point at which permissive-nominal techniques go strictly beyond the expressivity of nominal techniques, and this is made formal: we saw in Section 8 how the results of Section 6 depend on permutations π being finite and when we include infinite permutations in syntax, the results begin to fail. This is reasonable and as it should be.

So a lesson we can draw from this paper and from the translation in [DGM10, Section 4] is this: permissive-nominal terms with finite permutations are essentially the same thing as (but somewhat better-behaved than) ‘ordinary’ nominal terms; permissive-nominal terms with possibly infinite permutations are different, and they are strictly more expressive.

Non-equivariance of atoms. One curious aspect of our proofs is that the function atoms from Definition 5.1, which plays a role in Section 5, is not invariant under α-equivalence. For instance, atoms([a]X) = {a} and atoms([b](b a)·X) = {b, a} (where a ∈A< and b ∈A>).

It is shown in [Gab11b] and [Gab12b] that valuations ς (Definition 3.12) can be thought of as (finite-)equivariant maps out of moderated unknowns π·X considered as a permissive-nominal set.

The non-equivariance of atoms is an artefact of the fact that the syntax of this paper amounts to choosing id·X as a representative of the permutation equivalence class {π·X | π a permutation}. Permissive-nominal syntax is already non-equivariant, because for each unknown-up-to-permutations we have chosen a canonical representative X.

None of this matters for the proofs here, because we only care about avoiding capture with finitely many atoms.

Final words on set theory. The results of this paper are reminiscent of the upwards and downwards Löwenheim-Skolem theorems, which express that a first-order theory cannot ‘count’ the cardinality of its infinite models [Hod93]. The construction of this paper can be read as saying that first-order permissive-nominal syntax with finite permutations cannot ‘count’ the cardinality of its supporting sets.

We believe it would be fairly easy to strengthen and generalise this result to the following: first-order nominal syntax cannot ‘count’ the cardinality of the set of atoms or its supporting sets, so long as these are no smaller than the permutations in that syntax. Making this formal would require us to be just a little systematic but it should not be too hard using a free construction—and the syntax should be a natural generalisation sufficient to subsume permissive-nominal algebra and permissive-nominal logic.

More generally, we can also ask how the group of permutations can be independently enlarged or restricted in syntax and in the denotation. For instance, in this paper we have considered syntax and semantics using the same group of permutations. But the semantics could allow more permutations than the syntax, e.g. we could allow shift in the denotation (this is useful to ‘make support smaller’ in some element), but not in the syntax (so that we might avoid the issues discussed in Subsection 8.2 and specifically in Remark 8.6). In short, we see this paper as the first of a family of similar results which may become useful if and when further variations on logics based on nominal terms, and their models, are developed. We leave these thoughts to future work.

Acknowledgements.

Many thanks to an anonymous referee, without whose careful attention this paper would not have reached its current form. We acknowledge the support of the Leverhulme Trust and of grant RYC-2006-002131 at the Polytechnic University of Madrid.

References

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

[dB72] Nicolaas G. de Bruijn. Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indagationes Mathematicae, 5(34):381–392, 1972.

[DG10] Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic. In Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2010), pages 165–176, 2010.

[DG12] Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic (journal version). Transactions on Computational Logic, 2012. In press.

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

[Gab02] Murdoch J. Gabbay. FM-HOL, a higher-order theory of names. In F. Kamareddine, editor, 35 Years of Automath, April 2002.

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

[Gab09] Murdoch J. Gabbay. Nominal Algebra and the HSP Theorem. Journal of Logic and Computation, 19(2):341–367, April 2009.

[Gab11a] Murdoch J. Gabbay. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic, 17(2):161–229, 2011.

[Gab11b] Murdoch J. Gabbay. 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, 2011.

[Gab12a] Murdoch J. Gabbay. Meta-variables as infinite lists in nominal terms unification and rewriting. Logic Journal of the IGPL, 2012. In press.

[Gab12b] Murdoch J. Gabbay. Nominal terms and nominal logics: from foundations to meta-mathematics. In Handbook of Philosophical Logic, volume 17. Kluwer, 2012.

[GM07] Murdoch J. Gabbay and Aad Mathijssen. A Formal Calculus for Informal Equality with Binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of Lecture Notes in Computer Science, pages 162–176. Springer, July 2007.

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

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

[Hod93] Wilfrid Hodges. Model theory. Cambridge University Press, 1993.

[Mul10] Dominic P. Mulligan. Online nominal bibliography. www.citeulike.org/group/11951/, 2010.

[New42] M.H.A. Newman. On theories with a combinatorial definition of equivalence. Annals of Mathematics, 43(2):223–243, 1942.

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

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

Notes

1For instance, ‘nominal algebra’ uses equations conditional on freshness constraints saying that ‘a is fresh for X’ [GM09], whereas ‘permissive-nominal algebra’ uses just equations [Gab12b]. ↩

2So, id·x = x and π·(π′·x) = (π◦π′)·x for every π and π′ and every x ∈|X|. ↩

3This characterisation, which follows [GM07] (see Lemma 3.2 and the discussion preceding it in [GM07]) captures in slightly abstract form three more syntax-directed rules: b ∉ fa(r) then [b](b a)·r =α [a]r, and if π|A< = π′|A< then π·X =α π′·X, and if π|pmss(C) = π′|pmss(C) then π·C =α π′·C. ↩

4We use negative indexes because we wrote A< with a <. Of course this does not matter, but it does allow the diagram in Section 8 to make geometric sense. ↩

5This is the crux of the proof: L is composed of a single orbit under the permutation action. ↩

6This notion of equivariance coincides with that of Definition 3.9, if we consider U as a function to truth-values {⊤, ⊥}, such that π·⊤= ⊤ and π·⊥= ⊥ for all π. ↩

7For comparison, nominal logic does not have this property [Pit03]: there are nominal logic predicates that are valid of all finite-namespace interpretations but not of all A<<-namespace interpretations (and thus also not valid of all A<-namespace interpretations). Nominal logic, of course, is a first-order theory; an axiomatisation in first-order logic similar to the axiomatisation of Fraenkel-Mostowski sets from which it is descended. What makes the languages of this paper different is that they are purpose-built using the dedicated new syntax of (permissive-)nominal terms. ↩

8This is a little stronger than we need. We could also retain the condition that π be finite in the definition of supporting set, so we say that A ⊆A supports x ∈|X| when for every finite permutation π ∈Pfin (so no δ), if π(a) = a for all a ∈A then π·x = x. We only ever α-convert by finitely many atoms in this paper, so the proofs remain unchanged. What does happen is that we admit models with elements which are fixed by finite permutations, but perhaps not by δ. For more on this design see [DG12], in particular Remark 3.3. ↩

9We then call the notion of equivariance from Definition 3.9 finite equivariance. It is possible to be equivariant for finite permutations but not for δ. The proof of Proposition 8.5 will depend on this. ↩

10This is unfair. For instance, the five pages do not include setting up the syntax. Still, looking at the maths, a leap in difference in complexity is clear. ↩