Finite and infinite support in nominal algebra and logic: nominal completeness theorems for free
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 .
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 (Definition 4.3), and a permutative notion of restricting a permutation (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
Write 0 1 2 3 for the natural numbers. and 0 -1 1 -2 2 for the integers.
For each fix a pair of disjoint countably infinite sets of atoms and . Write
will range over distinct atoms: we call this the permutative convention.
Given for some write () for the swapping bijection on atoms mapping to , to , and any other to .
If is a bijection on atoms define nontriv(() . Write for the group of bijections (finitely) generated by swappings, and call these bijections permutations.
Write for the composition of and (so ()((())). Write for the identity permutation (so ( always).
A bijection on atoms is a permutation if and only if
if and only if
nontriv(() is finite.
2.2. Permissive-nominal sets
A set with a permutation action X is a pair (
Say supports X when for every (finite) permutation , if ( for all then .
A permissive-nominal set is a set with a permutation action such that every element has a unique least supporting set supp such that supp
In fact, if X has some supporting set , then it has a least one; see e.g. [DG10, Theorem 4.3].
If is a permutation and write for the restriction of to . This is the partial function such that (
Suppose X is a nominal set. Suppose X and supports .
Then implies .
From the definition of support, considering .
Suppose X is a permissive-nominal set and X. Then supp(supp
By a routine calculation using the group action.
We conclude with a useful condition for checking whether supp:
Suppose X is a permissive-nominal set and X. Suppose supp Then () if and only if supp
Suppose supp. The right-to-left implication is by the definition of support. For the left-to-right implication, we prove the contrapositive. Suppose supp. By Lemma 2.10 supp(())supp. By our suppositions, ()supp() supp It follows that ().
2.3. Examples
We briefly consider examples of permissive-nominal sets, which will be useful shortly.
the set of atoms can be considered a permissive-nominal set with a natural permutation action
In the case of only, we will be lax about the distinction between the set, and the permissive-nominal set with its natural permutation action.
(Compare Definition 2.13 with Definition 4.3.)
1. X is a permissive-nominal set.
2. ] if and only if , for and X.
3. ] if and only if supp and (), for and X.
If are permissive-nominal sets for 1 then define by:
supp(
supp([] supp
supp((supp
3. Permissive-nominal terms syntax and its interpretation
3.1. Signatures
A term-signature over a sort-signature () is a tuple ( ar pmss) where:
is a set of constants.
is a set of unknowns.
is a set of term-formers.
ar assigns
– to each constant a base sort which we may write sort
– to each unknown a sort which we write may sort, and
– to each f a term-former arity , where and are in the sort-language determined by ().
pmss assigns to each constant a set pmss
A (nominal terms) signature Σ is then a tuple ( ar pmss).
We may write (()) just as ().
3.2. Terms
We may write f(()) as f().
Define free atoms and the permutation action, and free variables on terms as follows:
fa(fa
If ( for all fa then .
3.3. -equivalence
A congruence is an equivalence relation such that if then
-equivalence is then the least congruence such that if fa then ().3 We do not quotient terms by -equivalence. The syntax is a formal pair of and . So for example, and []() for 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 then and will always denote the same element in Definition 3.13.
3.4. Interpretation of signatures and terms
Suppose X and Y are permissive-nominal sets and XY is a function. Call equivariant when ( for all permutations and X.
Suppose () is a sort-signature (Definition 3.1).
A interpretation I for () consists of an assignment of a permissive-nominal set I to each sort in (), along with equivariant maps
for each an equivariant and injective map
for each and an equivariant and injective map which we write , and
for each for 1 an equivariant and injective map () which we write ()I .
Suppose I is a Σ-algebra. A valuation to I is an equivariant function on unknowns such that for each unknown ,
will range over valuations.
Lemmas 3.14 to 3.17 are proved by routine inductions:
If : then
If ( for every fv then
.
supp( ) fa
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 and T .
4. Reducing support of an interpretation
In this section we show how, given an interpretation H , to build an interpretation H with ‘smaller’ support.
H will have ‘almost the same structure’ as H . If two terms have a distinct denotation in H then their interpretation in 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 is identified with its position in the infinite list of abstractions which we impose). We can think of 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: [] and []
Choose a fixed but arbitrary enumeration of some subset of —since atoms are countable, this can be done. Write this enumeration as a list, ].4
Define a permissive-nominal set (parameterised by ) by:
will range over elements of
It is very easy to check that is indeed a permissive-nominal set, and that supp is equal to the atoms in .
We will be most interested in the cases of Definition 4.1 when enumerates all of (Section 6) and when enumerates ‘half’ of (Section 7). However, nothing in the mathematics below will depend on this.
If define fix by:
[] and X mirror and 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).
Suppose X is a permissive-nominal set and X. Suppose .
Then ] if and only if .
Clearly if then ]. Suppose ]. By construction ()
Suppose X is a permissive-nominal set and X. Suppose .
Then supp([] suppsupp
[]X from Definition 4.3 is a permissive-nominal set.
That it is a set with a permutation action is clear. That every element has a supporting permission set follows from Lemma 4.6.
Suppose X is a permissive-nominal set. Suppose []X and is such that supp) supp(. Then there exists a unique element, write it @X, such that @).
By Lemma 4.5 @ is unique if it exists.
Suppose supp() supp. By construction (Definition 4.3) ] for some and X. By construction (Definition 4.1) for some .5 It is also a fact that since supp
Suppose X. Then for any such that supp
We use Lemma 4.8 and take @.
4.2. Restricting permutations
Intuitively, (Definition 4.11) is the ‘smallest’ permutation to agree with on . is ‘trying’ to be (Definition 2.8) but is a total function and furthermore is a permutation. The main result is Theorem 4.14, and we use in Theorem 5.2.
As nominal techniques demonstrate, permutations are an attractive way to handle name-binding. Think of as a version of that we can use if we want to stay in the world of permutations.
Suppose )() (so maps to to to to to , and to to ). Then:
Suppose ). Then
Recall the definitions of nontriv and from Definition 2.3.
Represent permutations as cycles; so we write as a finite set of finite cycles indexed by where cycle number has length 1:
Define as that permutation obtained as follows:
Delete from the cycle representation of above any atom such that . That is, if there is any part of a cycle of the form ‘’ where , , and , then we replace it with ‘’. Repeat, until we cannot proceed.
If there is any part of a cycle of the form ‘’ where and but and , break the cycle into two subcycles as follows:
In words:
is obtained from by eliding sequences of three or more consecutive atoms not in , and then by splitting cycles at any two consecutive atoms not in .
is well-defined.
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].
Define when:
For every cycle with atoms in , there is a cycle with atoms in such that .
It is easy to verify that is a transitive reflexive relation. is not antisymmetric: if ) and ) and then and yet .
1. is the unique -least permutation beneath .
2. As a corollary, () and if and )- then .
By construction contains only those atoms, in the smallest possible cycles, necessary to agree with and on .
4.3. Making support smaller
Given an interpretation H and a list of atoms , we are interested in ‘subtracting’ 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.
A couple of comments on Definition 4.15:
The index of H is only used to interpret constants . 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 H .
In the case of tuples, we know we can write every element in the form for 1 for some , by Lemma 4.9.
[]H from Definition 4.15 is an interpretation.
The next step is to build valuations to H . This is Definition 4.18 and Proposition 4.19.
If is a valuation to H then is a valuation to H .
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. We need this to express the side-condition atomssupp( in Theorem 5.2, and the side-condition atomsnontriv( in Proposition 5.6. Without these side-condition, the results would not hold.
Define atoms inductively by:
atoms collects the atoms ‘explicit’ in . Contrast this with ‘free atoms of’ fa from Definition 3.4 which collects the atoms ‘potentially’ in . For instance, fa( and is infinite, but atoms(. This is because mentions no atoms explicitly, but intuitively it could be instantiated for any term with atoms in .
5.2. First commutation result
Recall from Definition 4.1 the construction of , parameterised over some .
Suppose and atoms
By induction on :
The case . We reason as follows:
We know supp because we assumed atomssupp(, and atoms(
The case . We reason as follows:
The fact above follows since we assumed atoms() supp(.
The case , where supp We reason as follows:
The case . We reason as follows:
The fact above follows since we assumed atoms() supp(.
The case (). We reason as follows:
The case ... is routine.
5.3. Second commutation result
Given an interpretation H , a valuation to H , and some and sort with supp
Suppose , , and are as in Definition 5.3. Suppose . Then
By routine calculations.
5.4. Third commutation result
Suppose nontriv
By a routine induction on similar to that in Theorem 5.2:
The case . By assumption nontriv
The case . By assumption nontrivnontriv(. Since nontriv
The case , where supp By assumption nontriv
The case . As for .
The cases () and ... are routine.
6. Nominal algebra completeness relative to interpretations with finite support
We now have everything we need to set up two notions of validity and (Definition 6.7) and prove our main result, that they are equal (Theorem 6.8).
Recall the construction of H from Definition 4.15.
Suppose and are terms in Σ, which is the signature of an interpretation H . Suppose . Then:
1. If H then H .
2. If H then H .
For the first part, suppose H . So there exists a valuation to H such that
For the second part, suppose that H and suppose is a valuation to H . Choose some such that
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
The model H is composed of ordinary—i.e. finitely-supported—nominal sets, in the sense of [GP01]:
Every
Definition 6.5 is standard, e.g. from [GM09] (nominal) or [Gab12b] (permissive-nominal):
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 .)
Suppose H is a Σ-interpretation (Definition 3.11). Write H T to mean that for every valuation to H and every () Ax,
Suppose Σ is a signature and F is a Σ-interpretation. Say that F has finite support when for every sort in Σ and every , it is the case that supp is finite.
Suppose T Ax) is a theory. Then:
Define T to mean that F T implies F , for every Σ-interpretation F with finite support.
Define T to mean that H T implies H , for every Σ-interpretation H .
Suppose that T is a Σ-theory.
Then T if and only if T .
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 . So there is an interpretation H such that H T and a valuation to H such that
Choose any . By part 2 of Proposition 6.3 H T. By part 1 of Proposition 6.3 H , and by Lemma 6.4 we are done.
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
if X is a nominal set and X call equivariant when for all X and all permutations .6
Definition 7.3 corresponds to e.g. [DG10, Definition 5.11].
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 P
This extends to propositions just as in first-order logic where is a truth-value or , as follows:
(the syntax) is equal to (the truth-value).
The PNL of [DG10, DG12, Gab12b] is classical, so is interpreted as ‘not or ’.
The only non-obvious case is the universal quantifier, which gets a denotation as follows:
This is non-obvious because the in quantifies only over with support in . 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.
For each fix some set such that and are both infinite. Write and:
Say that
Say that H has medium support when for every sort and every
The point of Definition 7.4 is that with medium support may have infinite support, but this support cannot exhaust the atoms in . But did we not see this already in Definition 2.2 when we split into and ? Yes, but PNL has a , so that now (and unlike was the case in permissive-nominal algebra) we have to worry about exhausting all the atoms in within nested quantifiers. To see this idea made concrete, consider the proof of Proposition 7.7.
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 to mean that F for every interpretation F with finite support and valuation to F .
implies . The reverse implication does not necessarily hold.
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 : and : . Suppose a predicate # : () with intended meaning ‘is fresh for’/‘is not in the support of’. Consider the formula #. Then and , but not ; it might be that ( where lists all atoms in , so there exists no atom in (by Definition 7.3, ranges over atoms in ) that is not in supp
The rest of this section is devoted to proving that if and only if (Theorem 7.15). We discuss the relevance of these results in Subsection 7.4.
7.3. Finite support denotations from medium support denotations
Given a PNL interpretation H with medium support and a list , generate a PNL interpretation H by extending Definition 4.15 such that
Where does the in H appear on the right-hand side here? It does not: 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)()), then Definition 7.9 would mention on the right. This makes no difference to expressivity since we can emulate the effect of a non-equivariant proposition-former using P(). Our design follows the path of the simplest definitions and proofs.
Every
Extend atoms (Definition 5.1) to propositions atoms inductively by:
Lemma 7.12 extends Proposition 5.6 to predicates, and is needed for Proposition 7.14. Recall from Definition 5.5 the definition of :
Suppose is a valuation to an interpretation H . Suppose is a predicate and a permutation such that nontriv
Then
fa
Suppose is a proposition, H is a PNL interpretation with medium support (Definition 7.4), and is a valuation to H . Suppose is a finite set of atoms such that atoms
Then H if and only if H
By induction on . We consider a selection of cases:
The case of We consider the two implications separately. () Suppose H
The case of . Again we consider the two implications separately: () Suppose H . Unpacking definitions, this means there is some sort with supp
If supp([]) supp( then we may use Lemma 4.8 and write as [](([])@) and deduce by inductive hypothesis that H . Otherwise, we choose some that maps supp([])supp() to a set of atoms in that is disjoint from supp
We now proceed as in the case where supp([]) supp(.
The case of . Suppose H . This means that H or H . By inductive hypothesis this is if and only if H
if and only if .
7.4. Relevance of the theorem
It will help to establish some new terminology:
Suppose X is a set with a permutation action and X.
Say the element X is finite-namespace when supp is finite. Similarly say X is finite-namespace when every X has finite support. This is synonymous with X being a nominal set in the sense of [GP01]; cf. also Definition 6.6.
Say is -namespace when supp
Say is -namespace when supp
Similarly we will call interpretations finite-namespace, -namespace, and -namespace in accordance with the support of their underlying sets.
The relevance of Theorem 7.15 is that a PNL predicate is valid over -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 -namespace interpretations. This differs from the validity , which is validity over -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 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 . 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 () where and 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 then there is no finite permutation such that .
Write for the set of all sets of atoms differing finitely from as just described.
There exists a theory T in permissive-nominal algebra with permission sets from , and an assertion in that theory, such that T and T (where models are permissive-nominal sets with permission sets in ).
Assume one base type and one term former 0 : with pmss. Assume an axiom where fa(. Assume an unknown with sort( and fa( where . Then:
For suppose F is an interpretation of T with finite support: then for any
However, T . To see this, interpret to be the set () finite, interpret 0 by , and take (.
Initially we used ; 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.
Suppose and .
Assume a bijection on atoms mapping to and such that nontriv is infinite (we can do this because we assumed that is countable).
We illustrate an example:
Illustration of :
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 in PNL [DG12, Subsection 2.7]. If fa( where then R() does not entail R(() ()) without , but it does entail R(() ()) 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 (models with finite support) are not. In order to state this result we must ‘upgrade’ the material in this paper with .
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 for the group of bijections generated by swappings and .
2. In Definition 2.6 assume the permutation action has type (X) X. So permissive-nominal sets have an action by swappings and .
3. In Definition 2.6 we say that supports X when for every permutation , if ( for all then .8
4. In the examples of Subsection 2.3 extend for the extra permutations in the natural way. So
5. In Definition 3.3 extend terms also with the extra permutations. So is a term for . 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 is equivariant when ( for all permutations and X.9
There exists a theory T in permissive-nominal algebra with , and an assertion in that theory, such that T and T (where models are permissive-nominal sets with ).
Assume no term-formers and one base type . Assume and a shift permutation bijecting with , as illustrated just after Definition 8.3.
Assume an axiom () where . Then:
If F is a model of T with finite support then supp( for every
Now choose some supp and choose some mapping supp to a subset of and such that specifically (. By our axiom, ()(. It follows by calculations on permutations that () and so by Corollary 2.11 that supp, a contradiction.
T . To see this consider the elements () finite with the pointwise action, for every (where is the integers; see Definition 2.1). It is a fact that (), but it is also a fact that . We interpret to be the set and see that () for every so the axiom () is valid, but so T . This observation is exactly the fuzzy support noted in [Gab07], see also Remark 3.3 from [DG12].
Where do the proofs fail? Failure occurs in the interaction of atoms (Definition 5.1) with Theorem 5.2.
The reasonable definition for atoms() is nontriv, which is infinite. This gives us infinitely many atoms to avoid in order to guarantee atoms
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 X from X by applying to each X an infinite simultaneous atoms-abstraction abstracting all but finitely many of the atoms in supp. 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, X from Definition 4.3, is arguably reminiscent of de Bruijn indexes [dB72]. Given an X with infinite support, we form where supp
Of course this is not a literal replacement in , 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([]) 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 and unknowns, which this paper has not explored. Elsewhere we explore how a model of unknowns is given by infinite well-orderings of permission sets [Gab11b, Gab12a].
One way to view is as ‘ abstracted by an unknown ’.
Now from Definition 4.1 is a single permutation orbit under finite permutations of some list of atoms. This author calls this a namespace— 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 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([]
It is shown in [Gab11b] and [Gab12b] that valuations (Definition 3.12) can be thought of as (finite-)equivariant maps out of moderated unknowns 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 as a representative of the permutation equivalence class a permutation. Permissive-nominal syntax is already non-equivariant, because for each unknown-up-to-permutations we have chosen a canonical representative .
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 ‘ is fresh for ’ [GM09], whereas ‘permissive-nominal algebra’ uses just equations [Gab12b]. ↩
2So, and () for every and and every 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: fa then []()
4We use negative indexes because we wrote 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: is composed of a single orbit under the permutation action. ↩
6This notion of equivariance coincides with that of Definition 3.9, if we consider 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 -namespace interpretations (and thus also not valid of all -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 supports X when for every finite permutation (so no ), if ( for all then . 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. ↩