NOMINAL ALGEBRA AND THE HSP THEOREM (TECHNICAL REPORT)
Abstract. Nominal algebra is a logic of equality developed to reason algebraically in the presence of binding. In previous work the authors have shown how nominal algebra can be used to specify and reason algebraically about systems with binding, such as first-order logic, the -calculus, or process calculi. Nominal algebra has a semantics in nominal sets (sets with a finitely-supported permutation action) and in previous work the authors proved soundness and completeness.
The HSP theorem characterises the class of models of an algebraic theory as a class closed under homomorphic images, subalgebras, and products, and is a fundamental result of universal algebra.
It is not obvious that nominal algebra should satisfy the HSP theorem: nominal algebra axioms are subject to so-called freshness conditions which give them some flavour of implication; nominal sets have significantly richer structure than the sets semantics traditionally used in universal algebra. The usual method of proof for the HSP theorem does not obviously transfer to the nominal algebra setting.
In this paper we give the constructions which show that, after all, a ‘nominal’ version of the HSP theorem holds for nominal algebra.
1. Introduction
Algebra is the logic of equality. It has the virtue of simplicity; axioms assert equalities between terms, validity of equality is interpreted by identity in models, and two equal terms can be replaced in any context since they must denote the same element in all models. This simplicity also has benefits in the theory of models: every model of an algebraic theory can be exhibited as a homomorphic image of a subalgebra of a product of free algebras (for definitions see elsewhere [1] or Subsection 8). This result is called Birkhoff’s theorem [1, Theorem 11.12] and also the HSP theorem (Homomorphism, Subalgebra, Product); in this paper we call the result HSP since Birkhoff’s name is attached to several other results. The HSP theorem allows us to factor out complexity in models of algebraic theories in much the same way that the fundamental theorem of arithmetic allows us to factor large numbers into products of primes.
It would be useful if algebraic models of logic and computation were susceptible to this kind of treatment. However reasoning about systems with binding is somewhat resistent to algebraic treatments. Consider for example the following ‘equalities’ which arise naturally in informal practice:
Here fv() denotes the free variables of . It is easy to extend this list with more examples. Difficulties arise treating these ‘equalities’ algebraically. Firstly, there are two levels of variable:
and are variables of the system being axiomatised, we call these object-level variables.
, , , , , and range over terms of that system’s syntax, we call them meta-level variables.
Equalities are subject to freshness side-conditions fv(). The two levels of variable, and the freshness conditions, make it impossible to translate informal ‘equalities’ like those above directly into universal algebra. Formalisation of such systems in the traditional algebraic framework can require a fair amount of emulation.
We recall De Bruijn’s words [4]:
“I think that in formalizing mathematics, and in particular in preparing mathematics for justification, it is usually elegant as well as efficient to do everything in the natural way.”
Nominal Algebra [10, 16] is a logic of equality which represents the two-level variable structure and freshness conditions noted above directly in its syntax. It uses a semantics in nominal sets [12]. Informal equalities can often be represented almost symbol-for-symbol. For example the equalities above are represented by the following axioms in nominal algebra:
Here and are distinct atoms representing object-level variables; and are distinct unknowns representing meta-level variables; [] is an abstraction of an atom in a term . Each equality is equipped with a freshness condition of the form # that guarantees that can only be instantiated to a term for which is fresh.
Nominal algebra has been used to axiomatise substitution [9] and first-order logic [11]. Also in other work [20, 5, 2], nominal techniques have proved their ability to be ‘ away from informal practice’, following de Bruijn’s philosophy while remaining mathematically completely rigorous.
In this paper we fill an important gap in the foundational theory of nominal algebra; nominal algebra does indeed satisfy a version of the HSP theorem (Theorem 9.3). The HSP result is extended in an interesting way to include nominal abstractions; we give full details in the rest of the paper.
HSP for nominal algebra is not evident: freshness side-conditions give nominal algebra axioms a flavour of implication (which undermines closure under homomorphic images), and nominal sets have structure which ‘normal sets’ do not. If we try to directly transfer proofs of the HSP theorem to the nominal setting [1], the proofs fail. For these reasons, doubt over the validity of the HSP theorem has persisted since it was first introduced [10].
The constructions to prove the nominal HSP theorem are subtle and interesting.
The fact that this holds gives a precise mathematical sense in which nominal algebra can be viewed as a continuation of the long mathematical tradition of universal algebra. We hope that HSP will be as useful to the algebraic study of logic and computation using nominal techniques, as HSP has been in universal algebra.
2. Nominal Algebra Syntax
Fix a countably infinite collection of atoms . We shall use a permutative convention that range permutatively over atoms, so that for example and are always distinct. Fix a countably infinite collection of unknowns . Fix term-formers f to each of which is associated some unique arity which is a nonnegative number. Assume these collections are disjoint. A signature Σ is some set of term-formers.
Let range over (finitely supported) permutations. So bijects atoms with themselves and there is a finite set of atoms such that ( for all atoms not in . Write id for the identity permutation such that id( always. Write for functional composition and write for inverse. This makes permutations into a group — write for the set of all permutations.
Let nominal terms in some signature Σ be:
where f : ranges over the elements of Σ.
We write id just as , for brevity.
Write for syntactic identity of terms. Let be inductively defined by:
If then we say that occurs in (the syntax of) ’. Let be inductively defined by:
If then we say that ‘ occurs in (the syntax of) ’. Similarly write and for ‘does not occur in the syntax of ’.
A freshness (assertion) is a pair # of an atom and a term . An equality (assertion) is a pair where and are terms. Call a freshness of the form # (so ) primitive. Write ∆for a finite set of primitive freshnesses and call it a freshness context. We drop set brackets in freshness contexts, e.g. writing ## for ##.
Nominal algebra has two judgement forms, a pair ∆ # of a freshness context and a freshness assertion, and a pair ∆ of a freshness context and an equality assertion. We may write # as # and as .
A theory T Ax) is a pair of a signature Σ and a possibly infinite set of equality judgement forms Ax in that signature; we call them the axioms.
A motivation of these definitions, with example theories, is elsewhere [10].
3. A Derivation System
Now we need a notion of derivation which represents freshness assumptions on meta-variables, and permits axioms involving abstraction and conditioned on freshness assumptions, just like we do in informal reasoning.
We define a permutation action by:
() () and id .
By an easy induction on the structure of .
A substitution is a finitely supported function from unknowns to terms. Here, finite support means: for some finite set of unknowns () , and for all other unknowns
We define a substitution action on terms by:
Write for ()# (()) #.
Define a notion of derivability on freshnesses by the rules in Fig. 1. Here in accordance with our permutative convention and range over distinct atoms. Write ∆ # when # may be derived from ∆.
Suppose that T Ax). Define a notion of derivability on equalities between terms in Σ by the rules in Fig. 2. Here (fr) is subject to a condition that and the square brackets denote discharge of assumptions in natural deduction style [13].
Write ∆ when a derivation of from ∆exists, using only terms in Σ and axioms in Ax. We call such a derivation a ‘derivation of ∆ ’.
(ax) allows us to permutatively rename atoms and to instantiate unknowns. This gives the effect that atoms in axioms can be understood to range over any (distinct) atoms, and unknowns can be understood to range over any terms.
A basic result is the following:
If and is such that # for every #, then .
Fix a signature Σ. Call a term ground (in Σ) when it does not mention unknowns (and mentions only term-formers in Σ). We let variables named and range over ground terms; these are inductively characterised by
Here f ranges over elements of Σ.
Call a derivation ground (in Σ) when
It does not mention any unknowns (so all terms in it are ground terms).
It uses no instance of (#X ).
It uses no instance of (fr).
It mentions only term-formers in Σ.
If is derivable and and are ground terms in Σ then a ground derivation exists for in Σ.
Let Π be a derivation of . Take to be an atom that does not occur anywhere in Π. Let be Π in which:
each unknown is mapped to ;
each instance of (#X ) is replaced by (#ab); that is, each instance of (#X ) is of the form
where square brackets denote discharge of the freshness assumption. This is replaced by
Note that we write instead of () since (. Using Lemma 3.7 it is not hard to see that is a valid derivation of that does not mention unknowns. Therefore it contains no instance of (#X ).
Instances of (fr) discharge no assumptions, because these assumptions would mention unknowns and there are none, so these instances be simply be removed. The result follows.
Write ds() for the set () , the difference set of and . We write ∆ ds()# for a set of proof-obligations ∆ #, one for each ds().
If ds()# then .
By induction on the number of elements in ds().
4. Nominal Sets
A model of a nominal algebra theory T is a nominal set which interprets the term-formers so as to make the axioms valid. We use nominal sets [12] because they permit a direct semantic interpretation of freshness judgements # and permutations , an interpretation which is not conveniently definable on ‘ordinary’ sets.
A nominal set is a pair (
a -group action is a function such that id and () ;
finite support means there is some finite set of atoms such that if and ( for every , then .
We write as shorthand for and call an element of .
In [12, Proposition 3.4] it is shown that if an element has finite support, then there is a unique least finite set of atoms that supports .
When has a finite supporting set, call the least set of atoms supporting the support of , and write it as supp
We write # (read ‘ fresh for ’) when supp
The set of all atoms with action () is a nominal set; the support of is . Note that for , # when .
Basic results of nominal sets are:
(1) supp( () is not finite.
(2) If # for every ds() then .
(3) If # then ()#.
Elsewhere [12, Proposition 3.4] and by easy calculations.
Let be a countably infinite indexing set and () an -indexed collection of nominal sets. Write for the nominal set with underlying set those -tuples () such that there exists some finite set of atoms such that supp
We give this the component-wise permutation action, so
We write for where for 1 .
#() if and only if # for every .
Call a function equivariant when (() for all .
If and are nominal sets and is equivariant, then supp(()) supp
As a corollary, # implies #
By Definition 4.7 ((), so if then (
The corollary follows by the definition of support.
Subsets of (the underlying set of) a nominal set will be important later when we build free algebras.
inherits a pointwise permutation action
We will always use the pointwise action on .
# does not imply that # for every . For example and it is a fact that # — but and not #. Furthermore does not imply that is finitely supported. For example if we order as then it is a fact that is not finitely supported. However, the finitely-supported subsets of form a nominal set — they have a permutation action, and by construction they are finitely supported.
Suppose is a nominal set and is finitely-supported. Suppose that ##. There exists some such that ##.
Choose any . Let be fresh (so # and # for 1 ). By part 2 of Lemma 4.4 () () . Write ) () . By Definition 4.9 and we conclude # for 1 by part 3 of Lemma 4.4 and the assumption #.
Further discussion of nominal sets is elsewhere [12].
5. Semantics
We use nominal sets to give a semantics to nominal algebra signatures and theories:
A Σ-algebra consists of the following data:
An underlying nominal set
An equivariant map - to interpret atoms; we write .
An equivariant map such that #() always, to interpret abstraction.
An equivariant map for each term-former f : Σ to interpret term-formers.
We tend to write and for Σ-algebras.
Consider a Σ-algebra . A valuation in maps unknowns to elements
Interpretations are equivariant:
Suppose that is a Σ-algebra and is a valuation to . Then [[ ]] ]] for any .
By induction on the structure of , using Lemma 4.8 for the cases of , [] and f().
Suppose that is a Σ-algebra. Define a notion of validity by:
Suppose that T Ax). A model of T is a Σ-algebra such that [[ ∆ ]] for every axiom ∆ in Ax and every valuation .
The nominal sets semantics for nominal algebra is sound ([10, 16]):
That is T Ax) is a theory, is a Σ-algebra which is a model of T, and is a valuation to . Then:
If # is derivable then #]] is valid.
If is derivable then ]] is valid.
We work by induction on derivations (Figures 1 and 2):
(#ab). We must show #. By Lemma 4.8 this follows from #, which is a standard property of freshness (see Example 4.3).
(#X ). By the inductive hypothesis we know ()#(). By part 3 of Lemma 4.4 we conclude #
(#[]a). #abs( [[ ]] ) holds by assumption.
(#[]b). By Lemmas 4.8 and 4.6 and the fact that #, #[[ ]] implies #abs( [[ ]] ).
(#f). If #[[ , . . . , #[[ then by Lemma 4.8 #([[ [[ ) and we conclude #([[ [[ ) using Lemma 4.6.
(refl), (symm), (tran), (cong[]), (congf). By properties of equality.
(perm). By part 2 of Lemma 4.4, #[[ ]] and #[[ ]] imply () [[ ]] ]] . We conclude [[ () ]] ]] by Lemma 5.3.
(ax). Suppose [[ ]] for any . Then ()#
holds. ∆ is an axiom of T so [[ ]] ]] holds, and by Lemma 5.3 we obtain [[ ]] ]] . Now by a straightforward induction on syntax we can verify that [[ ]] ]] and [[ ]] ]] , and we conclude [[ ]] ]] .
The case of (fr). Suppose that [[ ∆]] is valid and # is derivable, with a derivation Π.
If #() then [[ # is valid and by hypothesis [[ ]] is valid and we are done.
Suppose supp(()). Choose some such that #() and also #() for every # ∆. Write ∆ for ∆with every # ∆replaced by # . Then ∆ is derivable; we obtain the derivation by replacing every in Π by , to obtain a derivation . Now [[ # is valid and is no longer than Π. Therefore [[ ]] is valid as required.
The nominal sets semantics for nominal algebra is complete:
Fix a theory T Ax) and an equality-in-context where and are nominal terms in the signature Σ.
Suppose that for all models of T and all valuations to , if is valid then [[ ]] ]]. Then is derivable.
6. Free algebras
The usual technique to obtain models for a theory is to add constant symbols to the language and to quotient the set of terms by provable equality — the extra constant symbols ensures there are ‘enough elements’ in the model. In nominal algebra constants have empty support; if d has arity 0 then #d is derivable for any . Adding extra constant symbols only ensures a supply of elements with empty support. Following [6], we add extra term-formers (which may have arity greater than 0).
6.1. Ground terms.
Fix a signature Σ and a (possibly infinite) set of term-formers disjoint from Σ (the ‘extra’ term-formers mentioned above).
Let ground terms (Σ) be inductively generated by
Here f : ranges over elements of Σ, and d : ranges over elements of . Give this a permutation action as in Definition 3.1; in full:
If (Σ) then supp(. As a corollary, if and only if #.
(Σ) with its permutation action, as defined in Definition 6.1, is a nominal set.
Elements of (Σ) are labelled trees. Structurally, [] is a tree with a root note labelled ‘[]’ and two daughters, one is , the other is ; the ability of abstraction to actually abstract comes later when we take equivalence classes in (T). supp( follows by an easy induction on the tree structure of using Lemma 4.6. It follows that (Σ) is a nominal set.
We need a technical lemma:
If (Σ) then implies #.
By an easy induction on syntax using the rules in Figure 1.
Call a derivation Π an (T)-derivation when:
Π does not use (congd) for any d . We discuss this condition in Remark 6.6 below.
Π only mentions term-formers in Σ .
That is, we should only mention terms in the signature we are working in.
Π does not use (fr). This can be ‘guaranteed’ in the sense given by Corollary 3.9.
Π does not mention unknowns and in particular does not mention (#X ). This can be also ‘guaranteed’ in the sense given by Corollary 3.9.
Write Π(T) for the set of (T)-derivations.
If (Σ) write [ for the set of (Σ) such that some Π Π(T) exists of . Write (T) for the nominal set such that
We exclude (congd) to avoid the following pathological situation: if we allow (congd) and T contains the axiom then the reader can easily verify that supp[d()]. This is unwanted behaviour: the intended rôle of d() is to be an ‘unknown element with support ’ in a model we are building, and this should hold independently of the axioms in T.
This is also why our syntax of ground terms does not allow terms of the form d() for general . Note that in related work [8, 9] we do allow such terms; we use them to build a model with a substitution action.
Suppose that (T). Then:
id .
is supported by # for any .
As a corollary (T) defined in Definition 6.5 above is a nominal set, and furthermore if # then #[.
Suppose that (T). By construction for some (Σ). id
Write #. This is finite by Lemma 6.3. It suffices to show that supports [. Let be a permutation such that ( for all . We must show
The corollary follows from Definition 4.2.
The following technical lemma will be useful later:
Suppose that (T). Then ## if and only if there exists some such that ## are all derivable.
For the left-right implication we use Lemma 4.10 to pick some such that ##. By Lemma 6.2 this is equivalent to ##. We conclude ## by 6.3.
The right-to-left implication is by Lemma 6.7.
The following example shows why Lemma 6.8 is non-trivial:
Consider a theory ATOM with one axiom . [ and therefore #[. Also and # are derivable. For further discussion see elsewhere [16, 3.4.3].
Suppose T Ax) and suppose is a set of term-formers disjoint from Σ. The free algebra of T over , we overload notation from Definition 6.5 and write it (T), is the Σ-algebra with:
Underlying nominal set (T) as defined in Definition 6.5.
Interpretation of atoms .
Interpretation of abstraction (] for some .
(f()]T for some , for each term-former f : in Σ.
We overload (T) to stand both for the Σ-algebra and its underlying nominal set.
(T) is a Σ-algebra.
The underlying set (T) is a nominal set by Lemma 6.7. For the interpretation functions we must show that they are well-defined — that is, we mus show that for [-]- and the choices of and do not matter — and equivariant. This is easy using the definitions of [-]T and the permutation action.
The only slightly non-trivial part is to show that #() holds, that is, that #[[]. Choose fresh (so and #[[]). Since #[[], also #() [[] by part 3 of Lemma 4.4. By definition of the permutation action also #[[]() . Since #[]() and #[]() by Lemma 6.3 and the derivation rules of Figure 1, we know []() ] by (perm). Then [[]() ] and we obtain #[[] as required.
Suppose Σ is a signature and is a set of fresh term-formers (so ). Suppose that is a term in Σ . Suppose that
By an easy induction on the structure of :
The case . Note that from the definitions and [[ ]] . It follows that []] .
The case of .
The case []. We use the inductive hypothesis:
The cases of f() for f Σ and d() are similar, but simpler.
(T) is a model of T.
Suppose ∆ is an axiom of T. Suppose that is a valuation to (T) and suppose that #() for every # We must show that [[ ]] ]] .
Let be the set of all unknowns mentioned in ∆, , or . By Lemma 6.8, for every there is an element () such that # for every # Let be the substitution such that
7. The inverse mapping
Fix a signature Σ and a finite set of fresh term-formers (so Σ ).
For each finite make a fixed but arbitrary choice of the following data:
For each some choice of unknown ; our choice is injective in the sense that implies for 1 . Write . We call the ‘unknown corresponding to ’.
A choice of a set of atoms with the same cardinality as , but disjoint from it (so ).
For each with 1 let
– be some choice of distinct elements of in some arbitrary order, and
– be some choice of distinct elements of in some arbitrary order, where is the arity of . We call , and the ‘choices of atoms in order corresponding to ’.
Suppose that . Write (Σ) for the set of (Σ) such that .
If (Σ) then let (Σ)-1() be the tuple (∆ ) where:
(Note that #d() if and only if .)
( id for all .
is defined inductively by:
We call this construction the inverse mapping.
The following technical lemma will be useful later:
()-.
We unpack definitions and observe that () ()() ( id.
We may use Lemma 7.4 without comment:
Suppose that (Σ). Suppose that
then , , , and .
The construction of ∆and ∆ does not depend on and . Similarly for and , and , and and .
Suppose that (Σ) and (Σ)-1 Then .
We work by induction on . All cases are routine, we consider only the case () for where is the arity of . Then
and
Suppose that (Σ). Suppose that
Then implies .
By Lemma 7.5 and ∆ . The result follows using (tran).
Suppose that d() (Σ) and suppose . Then #d()-1 if and only if .
Recall our choices of and from and respectively. By construction d() for some , were
By the syntax-directed structure of the rules in Figure 1# if and only ()#. The result follows by the construction of ∆.
Suppose that ( for all . Suppose that (Σ) and suppose that (Σ)-1(). Then:
#()-1 if and only if # ().
()-1 providing that ( for all .
We work by induction on . The only non-trivial case is when d() where is the arity of d. It suffices to show that # if and only if ∆ # where is our choice of unknown in to correspond to d and
and
This follows by easy calculations using the construction of ∆and the assumption that ( for 1 .
We work by induction on . The only non-trivial case is again when d() where is the arity of d. It suffices to show that for , , and as in the first part of this result. By Lemma 3.11 it suffices to show ∆ ds()#. This follows by easy calculations as in the first part.
If Π is a nominal algebra derivation, write Π when occurs in the syntax of Π (that is, when there exists some term in the syntax of Π such that ). Theorem 7.9 is an important technical result (compare with Lemma 6.18 from [9] and Lemma 3.4.23 from [16]):
Suppose that (Σ). Suppose that
Then:
If # then #.
If a derivation Π Π(T) exists of and Π then
We inductively transform Π into a derivation of ∆ .
The cases of (#ab), (#[]a), (#[]b), (cong[]), (refl), (symm) and (tran) are easy.
The case (#f). There are two possibilities:
– Suppose #f() for f Σ. By assumption # for 1 # by inductive hypothesis. By construction f() f( ) and the result follows.
– Suppose #() for and the arity of . By assumption # for 1 . It follows that . The result follows by Lemma 7.7.
(congf). There are two cases:
– The case of f Σ easily follows using the inductive hypothesis.
– The case of d is impossible, since we assumed that Π does not mention (congd).
(perm). By inductive hypothesis ∆ # and ∆ #. Then ∆ () by (perm). By Lemma 7.8 (() )-1 ) . The result follows.
(ax). Then and for some permutation and substitution .
We must show ∆ ()-1 )-1 and by inductive hypothesis we may assume ∆ ()-1.
By Lemma 7.8 it suffices to show
given
Define by:
Then (), () and (∆), so it suffices to show
By (ax) this follows from ∆ .
8. Homomorphisms, Subalgebras and Product Algebras
We now establish some basic definitions required for stating the nominal HSP theorem.
8.1. Algebra homomorphisms.
For Σ-algebras and , a Σ-algebra homomorphism from to is an equivariant function : such that:
for every atom.
( ().
( () for every f in Σ.
Suppose and are Σ-algebras. Call a homomorphic image of when there is a Σ-algebra homomorphism from to such that is a surjection onto
The following technical lemma establishes a ‘capture-avoidance’ property needed for Corollary 8.4.
Suppose that and are Σ-algebras and suppose that is equivariant. Then if and # then there exists such that # and .
Informally, is a representative of () which ‘avoids name-clash’ with supp().
Suppose Σ is a signature and suppose that and are Σ-algebras. Suppose is a Σ-algebra homomorphism from to .
Suppose that is a valuation to and is a valuation to . Finally suppose that (((()) for all unknowns .
By an easy induction on .
Suppose Σ is a signature and T ) is a theory. Suppose that and are Σ-algebras and suppose is a homomorphic image of .
Then if is a model of T, then so is .
Write for the Σ-algebra homomorphism from to . Recall that by assumption is surjective.
Choose any (∆ ) and a valuation to . It suffices to show that ]] is valid.
Suppose [[ ∆]] is valid; unpacking definitions this means that #() for every #
For each unknown let (
By construction [[ ∆]] is valid, and so by assumption [[ ]]]]. We apply to both sides of the equality and use Lemma 8.3 to conclude that [[ ]] ]] as required.
8.2. Subalgebras.
For Σ-algebras and , call a subalgebra of when the following conditions are satisfied:
.
for all atoms .
( () for all atoms and .
For every term-former f in signature Σ, if f has arity and then ( ().
In other words, is closed under the interpretation of the term-formers which it inherits from .
For Σ-algebras , and a theory T Ax), if is a model of T and is a subalgebra of then is a model of T.
Suppose (∆ ) Ax and suppose is a valuation to such that #() for every # Since is also a valuation to , it follows that [[ ]] ]] . Therefore satisfies all the axioms of T.
8.3. Products.
Let be a (possibly countably infinite) indexing set and () be an -indexed collection of Σ-algebras. The product algebra is the Σ-algebra with:
Underlying nominal set as defined in Definition 4.5, considering each as a nominal set.
Recall that this has the component-wise permutation action; ().
(
For each term-former f of arity the component-wise interpretation function
It is easy to check that is a Σ-algebra:
For any -indexed collection of Σ-algebras , if is a model of T Ax) for every then so is .
Suppose that is a valuation to . Suppose that (∆ ) Ax and suppose that #() for every # ∆. We must show that [[ ]] ]] .
For each we obtain a valuation to projecting to the th component of By Lemma 4.6 we know that # for every # It follows that the th projection of [[ ]] is equal to the th projection of [[ ]] , and thus that [[ ]] ]] .
8.4. Atoms-abstraction.
Suppose is a nominal set and suppose and .
Define atoms-abstraction by
Write [] for the nominal set such that:
(Note that by our permutative convention ranges over atoms not equal to .) It is not hard to prove that [] is a nominal set. This definition is known [12] and has been extensively used and studied. We mention those of its properties that we need, with references to proofs.
If
By [12, Proposition 5.5].
If ] then .
By [12, Proposition 5.5].
supp([] supp
By [12, Proposition 5.2].
If # and # then ].
By definition ()
Suppose that is a Σ-algebra. Define [] by:
] (for any ).
[] is a Σ-algebra.
There are two things to check:
is well-defined. Suppose . By Lemma 4.8 # and #. By Lemma 8.13 []].
f is equivariant. This follows easily from the definitions:
If is a Σ-algebra and is a valuation to , then write [] for the valuation to such that maps to []
Suppose that is a Σ-algebra and is a valuation to . Then if then
By induction on :
The case . [[ ]][ ]]([[ ]]).
The case . Here there is nothing to prove, since we assumed that .
The case f().
Suppose that and . Then [[ ]] ]] if and only if [[ ]][ ]][.
Suppose and .
If [[ ]] ]] then [][[ ]] ][[ ]] and the result follows by Lemma 8.17.
Conversely suppose [[ ]][ ]][. By Lemma 8.17 [][[ ]] ][[ ]]. The result follows by Lemma 8.11.
9. Varieties and Equational Classes of Algebras
A (nominal algebra) variety for a signature Σ is a collection of Σ-algebras closed under
homomorphic images (Subsection 8.1),
subalgebras (Subsection 8.2),
countable products (Subsection 8.3),1 and
atoms-abstraction (Subsection 8.4).
That is:
If and is a homomorphic image of , then .
If and is a subalgebra of then .
If is any countable indexing set and for all then .
If then [].
The notion of nominal algebra variety is standard [1] — except that we insist on closure under atoms-abstraction. Atoms-abstraction leaves ‘ordinary sets’ unaffected and in that sense Definition 9.1 specialises to the usual notion of variety.
Call a collection of Σ-algebras (nominal algebra) equational when there is some theory T Ax) in nominal algebra such that is the collection of all models of T.
From now on unless stated otherwise ‘variety’ means ‘nominal algebra variety’ and ‘equational’ means ‘nominal algebra equational’.
Our main result is a version of the HSP theorem [1] for nominal algebra:
A collection of Σ-algebras is equational if and only if it is a variety.
The proof is the rest of this section.
9.1. Surjections out of free algebras.
Fix a signature Σ and a collection of Σ-algebras . In practice we care about the case that is a variety, but nothing in this subsection depends on that.
Suppose is a model of theory T Ax). Suppose is a set of fresh constructors (so ). Then the following data determines a Σ-algebra homomorphism from (T) to : for each -ary term-former d
a choice of atoms and
a choice of element d() such that
This is an initiality property [15] adapted to our particular situation of nominal sets.
We define a function, by abuse of notation write it , from (Σ) to by:
().
Suppose we could prove that if [ then . Then we can view as a function from (T) to
Also:
It is easy to prove by induction on that (), and it follows that
( abs( abs(T).
It follows that viewed as a function from (T) to is also a Σ-algebra homomorphism and we are done.
It remains to prove that [ implies . Suppose Π Π(T) (Definition 6.4) is a derivation of . Let Π and let be the term-formers mentioned in Π. Let
Let ((()). By an easy inductive argument we deduce that and . By Theorem 7.9 is derivable. The result follows by Soundness (Theorem 5.6).
We need some notation for the proof of Theorem 9.8:
Suppose that T Ax). Suppose that Σ-algebras and for are models of T. Suppose is a family of homomorphisms. Then write for the natural map from to , mapping to (.
It is easy to verify that above is a homomorphism.
If then there exists some (sufficiently large) set of fresh constructors such that there exists a Σ-algebra homomorphism from (T) to , such that is a surjection on underlying sets.
That is: every element of is a homomorphic image of some sufficiently large free algebra.
Write car() for the cardinality of . Suppose that is a set of fresh constructors with at least car() constructors of every arity 0, and with no constructors of arity 0. We shall exhibit a suitable from (T) to .
For each permutation equivalence class choose a representative . For each ,
order supp() as , pick a unique -ary term-former d (which has not been assigned to any other ), and
assign d(.
For each remaining unassigned d() assign d(.2 By Lemma 9.4 this assignment extends to a homomorphism from (T) to .
It remains to show that this is a surjection, but this is easy: Consider any . By construction there exists some representative such that . So write . By construction d() for some d() and so d().
9.2. Injections out of free algebras.
Fix a signature Σ and a set of Σ-algebras . As in Subsection 9.1 we care most about the case that is a variety, but nothing in this subsection depends on assuming that.
Let T Ax) where Ax is the collection of judgements valid in all for all valuations. Call T the theory generated by .
That is, (∆ ) Ax when for every and every valuation to , it is the case that if #() for every # ∆then [[ ]] ]].
Suppose that is a collection of Σ-algebras. Let T be the theory generated by . Suppose is any set of fresh constructors (so ).
Then there exists some indexing set and algebras for such that there exists a Σ-algebra homomorphism from (T) to such that is an injection on underlying sets.
Let be the set of pairs () of ground terms in the signature Σ such that [.
Choose some ) .
Let . Let be the set of term-formers in occurring in and . Recalling Lemma 7.4, suppose that
We assumed that so by Corollary 7.6 . By Completeness (Theorem 5.7) there exists some model and valuation such that [[ ∆]] is valid and [[ ]]]] . Let
in some order. Write for [] and write for []
is closed under atoms-abstraction so . By Corollary 8.18
We construct a partial assignment by
for each d , where is the unknown corresponding to d, and is the choice of atoms in order corresponding to d, in the sense given in Definition 7.1.
We want to use Lemma 9.4 to obtain a homomorphism from (T) to but in order to do so we must verify that supp() .
Suppose that . By the rules in Figure 1 #d(). By Theorem 7.9 #d()-1. By assumption [[ ∆]] so by Soundness (Theorem 5.6) #[[ d()-1 ]]. Using Lemma 7.3 we deduce that #. It follows that supp() as required.
Note that by construction ([) ([).
It follows by the choice of that from (T) to is injective as a map on underlying sets.
The reader might ask why we bother with [] when we can build this as the subalgebra of in the image of — write it just abs. The answer is that we cannot: abs is not necessarily injective in the sense given by Lemma 8.11. Without this property Corollary 8.18 is not possible and the proof of Theorem 9.8 fails. In a sorted version of nominal algebra with abstraction sorts [7] we can insist that abs coincide with ‘real’ nominal sets abstraction — but in fact, this just pushes technicalities elsewhere; into the notions of algebra, subalgebra, product, and homomorphic image, and ultimately into the fact that to map out of an abstraction sort a term-former, write it abs, is required. This is an abs by another name.
Suppose that is a variety and suppose T is the theory generated by . Then (T) for every set of fresh term-formers D.
By Theorem 9.8 there is some indexing set , set of Σ-algebras for , and Σ-algebra homomorphism from (T) to that is an injection on underlying sets. is closed under products so . The image of (T) is a subalgebra of , and (T) is a homomorphic image (by inverting ) of that subalgebra. is closed under subalgebras and homomorphic images, and the result follows.
9.3. Proof of the nominal HSP theorem.
of Theorem 9.3. Suppose that is equational. By Lemma 8.8 is closed under products. By Corollary 8.4 is closed under homomorphic images. By Lemma 8.6 is closed under subalgebras. Therefore is a variety.
Conversely, suppose is a variety. Let T be the theory on Σ generated by as described in Definition 9.7. Let be any model of T. By Theorem 9.6 there exists some such that is a homomorphic image of (T). By Corollary 9.10 (T) . Since is closed under homomorphisms, as required. Therefore is equational.
10. Conclusions
The form and intended use of nominal algebra fits squarely into the mathematical tradition of using the logic of equalities for specification and reasoning; nominal algebra is a flavour of universal algebra [1].
As discussed in the Introduction, universal algebra enjoys the HSP theorem [1, Theorem 11.12]. The technical contribution of this paper is to establish that nominal algebra satisfies a similar property. We must assume closure not only under homomorphisms, subalgebras, and product algebras (the ‘H’, ‘S’, and ‘P’ in ‘HSP’ respectively), but also under atoms-abstraction algebras whose (rather elegant) construction is introduced in this paper in Subsection 8.4. At first we imagined that atoms-abstraction might be built out of homomorphisms, subalgebras, and product algebras. However the obvious constructions seemed to fail and it remains an open problem whether closure under abstractions does or does not follow from the other closure properties considered in this paper.
The term-language of nominal algebra is nominal terms [20]. Nominal terms extend first-order terms (the language of universal algebra) with object-level variables (atoms), and with constructs to support binding (nominal abstraction), -equivalence (permutations), and capture-avoidance (freshness conditions). Nominal algebra was developed with Mathijssen [10, 16]. A sound and complete semantics in nominal sets [12] has been explored (for full details see [16, Section 3]).
The technical constructions used in this paper are similar to those used in the proofs of completeness for nominal algebra [16, Subsection 3.4] but they are not a special case of them. Informally speaking, in the completeness proof we start with open terms and create ground terms (the from [16, Subsection 3.4]); in this paper we start from ground terms and create open terms, a typical example is in the last paragraph of Lemma 9.4. Therefore, a different set of technical lemmas is required and they seem to ‘point in the other direction’ from the lemmas required to prove completeness. It would be interesting to place the two sets of proofs in a single development and draw out their common core. This is future work.
Another ‘nominal’ logic is nominal logic [18]. This does not directly use nominal terms and nominal algebra is not the equality fragment of nominal logic; the two logics have different treatments of freshness [16, Subsection 3.4.3] — nominal equational logic by Pitts and Clouston [3] is closer to being the equality fragment of nominal logic. To our knowledge an HSP result has not (yet) been obtained for nominal equational logic.
Sun has developed ‘binding algebras’ [19]. Like nominal algebra, binding algebras are an algebraic framework enriched with constructs to support binding. Binding algebras are based on a functional semantics (that is, binding is modelled by a form of functional abstraction in syntax, and by restricted function-spaces in the semantics). Nominal techniques are not functional; binding is modelled by the Gabbay-Pitts model of abstraction in nominal sets [12]. Functional and nominal approaches seem to tend to achieve the same things in different ways; consider for example nominal rewriting [5] and combinatory reduction systems [14] or higher-order rewrite systems [17]. Therefore it is not a surprise to find a ‘functional’ algebraic framework for binding in the literature. The precise connection with nominal algebra is not well-understood. Concerning an HSP result for binding algebras, this is noted as an open problem [19, Discussion 9.1] and to our knowledge it has not yet been solved.
References
[1] S. Burris and H. Sankappanavar. A Course in Universal Algebra. Springer, 1981.
[2] J. Cheney and C. Urban. System description: Alpha-Prolog, a fresh approach to logic programming modulo alpha-equivalence. In Proc. 17th Int. Workshop on Unification, UNIF’03, pages 15–19. Universidad Politecnica de Valencia, 2003.
[3] Ranald A. Clouston and Andrew M. Pitts. Nominal equational logic. ENTCS, 172:223–257, 2007.
[4] N.G. de Bruijn. Checking mathematics with computer assistance. Notices of the American Mathematical Society (AMS), 38(1):8–15, 1991.
[5] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting. Information and Computation, 205:917–965, 2007.
[6] Murdoch J. Gabbay. Fresh logic. Journal of Logic and Computation, 2006. In press.
[7] Murdoch J. Gabbay and Aad Mathijssen. A formal calculus for informal equality with binding. to be submitted to Information and Computation.
[8] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding substitution as a nominal algebra. In Theoretical Aspects of Computing: ICTAC 2006, volume 4281 of LNCS, pages 198–212. Springer, 2006.
[9] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding substitution as a nominal algebra. Formal Aspects of Computing, 2007. To appear.
[10] 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 LNCS, pages 162–176. Springer, 2007.
[11] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order logic. Journal of Logic and Computation, 2007. To appear.
[12] 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, 2002.
[13] Wilfrid Hodges. Elementary predicate logic. In D.M. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 1–131. Kluwer Academic, 2001.
[14] Jan Willem Klop, Vincent van Oostrom, and Femke van Raamsdonk. Combinatory reduction systems, introduction and survey. Theoretical Computer Science, 121:279–308, 1993.
[15] S. Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer, 1971.
[16] Aad Mathijssen. Logical Calculi for Reasoning with Binding. PhD thesis, Technische Universiteit Eindhoven, 2007.
[17] Richard Mayr and Tobias Nipkow. Higher-order rewrite systems and their confluence. Theoretical Computer Science, 192:3–29, 1998.
[18] Andrew M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 186(2):165–193, 2003.
[19] Yong Sun. An algebraic generalization of Frege structures - binding algebras. Theoretical Computer Science, 211:189–232, 1999.
[20] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal unification. Theoretical Computer Science, 323(1–3):473–497, 2004.
Notes
1It is not hard to generalise to closure under uncountable or larger products. ↩
2This is why we insist that the fresh constructors d have arity at least 1, and so are applied to at least one atom; this makes it easy to pick a default value to which to map them in . ↩