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

NOMINAL ALGEBRA AND THE HSP THEOREM (TECHNICAL REPORT)

MURDOCH J. GABBAY AND AAD MATHIJSSEN

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:

λ-calculus: λx.(tx) = t if x ∉fv(t)First-order logic: ∀x.(φ ⇒ψ) = φ ⇒∀x.ψ if x ∉fv(φ)π-calculus: νx.(P | Q) = P | νx.Q if x ∉fv(P)

Here fv(t) denotes the free variables of t. It is easy to extend this list with more examples. Difficulties arise treating these ‘equalities’ algebraically. Firstly, there are two levels of variable:

• x and y are variables of the system being axiomatised, we call these object-level variables.

• t, u, φ, ψ, P, and Q range over terms of that system’s syntax, we call them meta-level variables.

Equalities are subject to freshness side-conditions x ∉ fv(t). 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:

λ-calculus: a#X ⊢ λ[a](Xa) = XFirst-order logic: a#X ⊢∀[a](X ⇒Y ) = X ⇒∀[a]Yπ-calculus: a#X ⊢ ν[a](X | Y ) = X | ν[a]Y

Here a and b are distinct atoms representing object-level variables; X and Y are distinct unknowns representing meta-level variables; [a]t is an abstraction of an atom a in a term t. Each equality is equipped with a freshness condition of the form a#X that guarantees that X can only be instantiated to a term for which a 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

Definition 2.1

Fix a countably infinite collection of atoms a, b, c, . . .. We shall use a permutative convention that a, b, c, . . . range permutatively over atoms, so that for example a and b are always distinct. Fix a countably infinite collection of unknowns X, Y, Z, . . .. Fix term-formers f to each of which is associated some unique arity n which is a nonnegative number. Assume these collections are disjoint. A signature Σ is some set of term-formers.

Definition 2.2

Let π range over (finitely supported) permutations. So π bijects atoms with themselves and there is a finite set of atoms S such that π(a) = a for all atoms not in S. Write id for the identity permutation such that id(a) = a always. Write π ◦π′ for functional composition and write π-1 for inverse. This makes permutations into a group — write P for the set of all permutations.

Definition 2.3

Let nominal terms t, u, v in some signature Σ be:

t ::= a | [a]t | π · X | f(t1, . . . , tn),

where f : n ranges over the elements of Σ.

We write id · X just as X, for brevity.

Definition 2.4

Write t ≡u for syntactic identity of terms. Let a ∈t be inductively defined by:

a ∈aπ(a) ≠ a a ∈π · Xa ∈ti(1 ≤i ≤n) a ∈f(t1, . . . , tn)a ∈t a ∈[b]ta ∈[a]t

If a ∈t then we say that a occurs in (the syntax of) t’. Let X ∈t be inductively defined by:

X ∈π · XX ∈ti(1 ≤i ≤n) X ∈f(t1, . . . , tn)X ∈t X ∈[a]t

If X ∈t then we say that ‘X occurs in (the syntax of) t’. Similarly write a ∉t and X ∉t for ‘does not occur in the syntax of t’.

Definition 2.5

A freshness (assertion) is a pair a#t of an atom a and a term t. An equality (assertion) is a pair t = u where t and u are terms. Call a freshness of the form a#X (so t ≡X) 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 a#X, b#Y for {a#X, b#Y }.

Definition 2.6

Nominal algebra has two judgement forms, a pair ∆ ⊢a#t of a freshness context and a freshness assertion, and a pair ∆ ⊢t = u of a freshness context and an equality assertion. We may write ∅⊢a#t as ⊢a#t and ∅⊢t = u as ⊢t = u.

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.

Definition 3.1

We define a permutation action π · t by:

π · a ≡π(a) π · (π′·X) ≡(π ◦π′) · X π · [a]t ≡[π(a)]π · t π · f(t1, . . . , tn) ≡f(π · t1, . . . , π · tn)
Lemma 3.2

π · (π′ · t) ≡ (π ◦π′) · t and id · t ≡t.

Proof

By an easy induction on the structure of t. □

(#ab)a#bπ-1(a)#X(#X )a#π · Xa#t1 · · · a#tn (#f) a#f(t1, . . . , tn)(#[]a)a#[a]ta#t(#[]b)a#[b]t
Figure 1. Derivation rules for freshness
(refl)t = tt = u(symm)u = tt = u u = v(tran)t = vπ · ∆σ(ax∆⊢t=u)π · tσ = π · uσt = u(cong[])[a]t = [a]ut = u(congf)f(. . . , t, . . .) = f(. . . , u, . . .)[a#X] ∆··· t = u(fr) (a ∉t, u)t = ua#t b#t(perm)(a b) · t = t
Figure 2. Derivation rules for equality
Definition 3.3

A substitution σ is a finitely supported function from unknowns to terms. Here, finite support means: for some finite set of unknowns σ(X) ≢X, and for all other unknowns σ(X) ≡X. Write [t1/X1, . . . , tn/Xn] for the substitution σ such that σ(Xi) ≡ti and σ(Y ) ≡Y , for all Y ≢Xi and all 1 ≤i ≤n.

Definition 3.4

We define a substitution action tσ on terms by:

aσ ≡a (π · X)σ ≡π · σ(X) ([a]t)σ ≡[a]tσ f(t1, . . . , tn)σ ≡f(t1σ, . . . , tnσ)

Write π · ∆σ for {π(a)#π · (σ(X)) | a#X ∈∆}.

Definition 3.5

Define a notion of derivability on freshnesses by the rules in Fig. 1. Here in accordance with our permutative convention a and b range over distinct atoms. Write ∆ ⊢a#t when a#t may be derived from ∆.

Definition 3.6

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 a ∉t, u and the square brackets denote discharge of assumptions in natural deduction style [13].

Write ∆ ⊢T t = u when a derivation of t = u from ∆exists, using only terms in Σ and axioms in Ax. We call such a derivation a ‘derivation of ∆ ⊢T t = u’.

(ax∆⊢t=u) 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:

Lemma 3.7

If ∆⊢T t = u and ∆′ is such that ∆′ ⊢a#σ(X) for every a#X ∈∆, then ∆′ ⊢T tσ = uσ.

Proof

By a routine induction on the length of derivations. For details see elsewhere [10, 20]. □

Definition 3.8

Fix a signature Σ. Call a term ground (in Σ) when it does not mention unknowns (and mentions only term-formers in Σ). We let variables named g and h range over ground terms; these are inductively characterised by

g, h, g′, h′ ::= a | [a]g | f(g, . . . , g)

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

Corollary 3.9

If ⊢T g = h is derivable and g and h are ground terms in Σ then a ground derivation exists for ⊢T g = h in Σ.

Proof

Let Π be a derivation of ⊢T g = h. Take c to be an atom that does not occur anywhere in Π. Let Π′ be Π in which:

• each unknown X is mapped to c;

• each instance of (#X ) is replaced by (#ab); that is, each instance of (#X ) is of the form

[π-1(a)#X](#X ),a#π · X

where square brackets denote discharge of the freshness assumption. This is replaced by

(#ab).a#c

Note that we write c instead of π(c) since π(c) = c. Using Lemma 3.7 it is not hard to see that Π′ is a valid derivation of g = h 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. □

Definition 3.10

Write ds(π, π′) for the set {a | π(a) ≠ π′(a)}, the difference set of π and π′. We write ∆ ⊢ ds(π, π′)#t for a set of proof-obligations ∆ ⊢a#t, one for each a ∈ ds(π, π′).

Lemma 3.11

If ∆⊢ ds(π, π′)#t then ∆⊢T π · t = π′ · t.

Proof

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 a#x and permutations π · x, an interpretation which is not conveniently definable on ‘ordinary’ sets.

Definition 4.1

A nominal set X is a pair (|X|, ·) of a(n ordinary) set |X| with a P-group action such that each x ∈X has finite support, where:

• a P-group action · is a function P × |X| →|X| such that id · x = x and π · (π′ · x) = (π ◦π′) · x;

• finite support means there is some finite set of atoms A such that if π ∈P and π(a) = a for every a ∈A, then π · x = x.

We write x ∈X as shorthand for x ∈|X| and call x an element of X.

In [12, Proposition 3.4] it is shown that if an element x ∈X has finite support, then there is a unique least finite set of atoms that supports x.

Definition 4.2

When x ∈X has a finite supporting set, call the least set of atoms supporting x the support of x, and write it as supp(x).

We write a#x (read ‘a fresh for x’) when a ∉ supp(x).

Example 4.3

The set A of all atoms with action π · a = π(a) is a nominal set; the support of a ∈A is {a}. Note that for x, y ∈A, x#y when x ≠ y.

Lemma 4.4

Basic results of nominal sets are:

(1) supp(x) = {a ∈A | {b ∈A | (a b) · x ≠ x} is not finite}.

(2) If a#x for every a ∈ ds(π, π′) then π · x = π′ · x.

(3) If a#x then π(a)#π · x.

Proof

Elsewhere [12, Proposition 3.4] and by easy calculations. □

Definition 4.5

Let I be a countably infinite indexing set and (Xi)i∈I an I-indexed collection of nominal sets. Write Πi∈IXi for the nominal set with underlying set those I-tuples (xi)i∈I ∈ Πi∈I|Xi| such that there exists some finite set of atoms A such that supp(xi) ⊆A for all i ∈I.

We give this the component-wise permutation action, so π · (xi)i∈I = (π · xi)i∈I; it is not hard to prove that all (xi)i∈I ∈ Πi∈IXi have finite support.

We write Xn for Πi∈{1,...,n}Xi where Xi = X for 1 ≤i ≤n.

Lemma 4.6

a#(xi)i∈I if and only if a#xi for every i ∈I.

Proof

By an easy calculation using part 1 of Lemma 4.4 (see [12]). □

Definition 4.7

Call a function f ∈|X| →|Y| equivariant when π · f(x) = f(π · x) for all x ∈|X|.

Lemma 4.8

If X and Y are nominal sets and f ∈|X| →|Y| is equivariant, then supp(f(x)) ⊆ supp(x).

As a corollary, a#x implies a#f(x).

Proof

By Definition 4.7 π · f(x) = f(π · x), so if π · x = x then π · f(x) = f(x).

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.

Definition 4.9

X ⊆|X| inherits a pointwise permutation action

π · X = {π · x | x ∈X}.

We will always use the pointwise action on X ⊆|X|.

a#X does not imply that a#x for every x ∈X. For example A ⊆A and it is a fact that a#A — but a ∈A and not a#a. Furthermore X ⊆|X| does not imply that X is finitely supported. For example if we order A as {a1, a2, a3, . . .} then it is a fact that {a1, a3, a5, . . .} is not finitely supported. However, the finitely-supported subsets of |X| form a nominal set — they have a permutation action, and by construction they are finitely supported.

Lemma 4.10

Suppose X is a nominal set and X ⊆|X| is finitely-supported. Suppose that a1#X, . . . , an#X. There exists some x ∈X such that a1#x, . . . , an#x.

Proof

Choose any x ∈X. Let b1, . . . , bn be fresh (so bi#X and bi#x for 1 ≤i ≤n). By part 2 of Lemma 4.4 (b1 a1) · · · (bn an) · X = X. Write y = (b1 a1) · · · (bn an) · x. By Definition 4.9 y ∈X and we conclude ai#y for 1 ≤i ≤n by part 3 of Lemma 4.4 and the assumption bi#x. □

Further discussion of nominal sets is elsewhere [12].

5. Semantics

We use nominal sets to give a semantics to nominal algebra signatures and theories:

Definition 5.1

A Σ-algebra X consists of the following data:

• An underlying nominal set X = (|X|, ·).

• An equivariant map -X ∈A →|X| to interpret atoms; we write aX ∈X.

• An equivariant map absX ∈A × X →X such that a#absX(a, x) always, to interpret abstraction.

• An equivariant map fX ∈|Xn| →|X| for each term-former f : n ∈ Σ to interpret term-formers.

We tend to write X and Y for Σ-algebras.

Definition 5.2

Consider a Σ-algebra X. A valuation ς in X maps unknowns X to elements ς(X) ∈|X|. Suppose that t is a term in Σ. The interpretation [[ t ]]Xς, or just [[ t]] ς if X is understood, is defined inductively by:

[[ a ]] ς = aX[[ π · X ]] ς = π · ς(X) [[ [a]t ]] ς = abs X(a, [[ t ]] ς) [[ f(t1, . . . , tn) ]] ς = fX([[ t1 ]] ς, . . . , [[ tn ]] ς)

Interpretations are equivariant:

Lemma 5.3

Suppose that X is a Σ-algebra and ς is a valuation to |X|. Then π · [[ t]] ς = [[ π · t]] ς for any π.

Proof

By induction on the structure of t, using Lemma 4.8 for the cases of a, [a]t and f(t1, . . . , tn). □

Definition 5.4

Suppose that X is a Σ-algebra. Define a notion of validity by:

[[ ∆]] ς (is valid) when a#ς(X) for each a#X ∈∆
[[ ∆⊢a#t ]] ς when [[ ∆]] ς implies a#[[ t ]] ς[[ ∆⊢t = u ]] ς when [[ ∆]] ς implies [[ t ]] ς = [[ u ]] ς
Definition 5.5

Suppose that T = (Σ, Ax). A model of T is a Σ-algebra X such that [[ ∆ ⊢t = u]] ς for every axiom ∆ ⊢t = u in Ax and every valuation ς.

The nominal sets semantics for nominal algebra is sound ([10, 16]):

Theorem 5.6 (Soundness).

That is T = (Σ, Ax) is a theory, X is a Σ-algebra which is a model of T, and ς is a valuation to |X|. Then:

• If ∆⊢a#t is derivable then [[ ∆⊢a#t]] ς is valid.

• If ∆⊢T t = u is derivable then [[ ∆⊢t = u]] ς is valid.

Proof

We work by induction on derivations (Figures 1 and 2):

• (#ab). We must show a#bX. By Lemma 4.8 this follows from a#b, which is a standard property of freshness (see Example 4.3).

• (#X ). By the inductive hypothesis we know π-1(a)#ς(X). By part 3 of Lemma 4.4 we conclude a#π · ς(X).

• (#[]a). a#abs(a, [[ t]] ς) holds by assumption.

• (#[]b). By Lemmas 4.8 and 4.6 and the fact that a#b, a#[[ t]] ς implies a#abs(b, [[ t]] ς).

• (#f). If a#[[ t1]] ς, . . . , a#[[ tn]] ς then by Lemma 4.8 a#([[ t1]] ς, . . . , [[ tn]] ς) and we conclude a#fX([[ t1]] ς, . . . , [[ tn]] ς) using Lemma 4.6.

• (refl), (symm), (tran), (cong[]), (congf). By properties of equality.

• (perm). By part 2 of Lemma 4.4, a#[[ t]] ς and b#[[ t]] ς imply (a b) · [[ t]] ς = [[ t]] ς. We conclude [[ (a b) · t]] ς = [[ t]] ς by Lemma 5.3.

• (ax∆′⊢t=u). Suppose [[ π · ∆′σ]] ς for any ς. Then π(a)#π · σ(X)ς holds for all a#X ∈∆′. By part 3 of Lemma 4.4 also a#σ(X)ς for all a#X ∈∆′.

Define ς′ by ς′(X) = σ(X)ς for all X. Then a#ς′(X) for all a#X ∈∆′,

so [[ ∆′]] ς′ holds. ∆′ ⊢t = u is an axiom of T so [[ t]] ς′ = [[ u]] ς′ holds, and by Lemma 5.3 we obtain [[ π · t]] ς′ = [[ π · u]] ς′. Now by a straightforward induction on syntax we can verify that [[ π · t]] ς′ = [[ π · tσ]] ς and [[ π · u]] ς′ = [[ π · uσ]] ς, and we conclude [[ π · tσ]] ς = [[ π · uσ]] ς.

• The case of (fr). Suppose that [[ ∆]] ς is valid and a#X, ∆⊢T t = u is derivable, with a derivation Π.

If a#ς(X) then [[ a#X, ∆]] ς is valid and by hypothesis [[ t = u]] ς is valid and we are done.

Suppose a ∈ supp(ς(X)). Choose some a′ such that a′#ς(X) and also a′#ς(Y) for every a#Y ∈ ∆. Write ∆′ for ∆with every a#Y ∈ ∆replaced by a′#Y . Then ∆′ ⊢t = u is derivable; we obtain the derivation by replacing every a in Π by a′, to obtain a derivation Π′. Now [[ a′#X, ∆]] ς is valid and Π′ is no longer than Π. Therefore [[ t = u]] ς is valid as required.

□

The nominal sets semantics for nominal algebra is complete:

Theorem 5.7

Fix a theory T = (Σ, Ax) and an equality-in-context ∆⊢t = u where t and u are nominal terms in the signature Σ.

Suppose that for all models V of T and all valuations ς to |V|, if [[ ∆]] ς is valid then [[ t ]]Vς = [[ u]]Vς. Then ∆⊢T t = u is derivable.

Proof

See [10] or (for full details) see [16]. □

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 ⊢a#d is derivable for any a. 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 D a (possibly infinite) set of term-formers disjoint from Σ (the ‘extra’ term-formers mentioned above).

Definition 6.1

Let ground terms F(Σ, D) be inductively generated by

g ::= a | [a]g | f(g1, . . . , gn) | d(a1, . . . , am).

Here f : n ranges over elements of Σ, and d : m ranges over elements of D. Give this a permutation action π · g as in Definition 3.1; in full:

π · a ≡(a) π · f(g1, . . . , gn) ≡f(π · g1, . . . , π · gn)π · [a]g ≡[π(a)]π · g π · d(a1, . . . , an) ≡d(π(a1), . . . , π(am)).
Lemma 6.2

If g ∈F(Σ, D) then supp(g) = {a ∈A | a ∈g}. As a corollary, a ∉g if and only if a#g.

F(Σ, D) with its permutation action, as defined in Definition 6.1, is a nominal set.

Proof

Elements of F(Σ, D) are labelled trees. Structurally, [a]g′ is a tree with a root note labelled ‘[]’ and two daughters, one is a, the other is g′; the ability of abstraction to actually abstract comes later when we take equivalence classes in F(T, D). supp(g) = {a ∈A | a ∉g} follows by an easy induction on the tree structure of g using Lemma 4.6. It follows that F(Σ, D) is a nominal set. □

We need a technical lemma:

Lemma 6.3

If g ∈F(Σ, D) then a ∉g implies ⊢a#g.

Proof

By an easy induction on syntax using the rules in Figure 1. □

Definition 6.4

Call a derivation Π an F(T, D)-derivation when:

• Π does not use (congd) for any d ∈D. We discuss this condition in Remark 6.6 below.

• Π only mentions term-formers in Σ ∪D.

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, D) for the set of F(T, D)-derivations.

Definition 6.5

If g ∈F(Σ, D) write [g]T for the set of g′ ∈F(Σ, D) such that some Π ∈ Π(T, D) exists of ⊢T g = g′. Write F(T, D) for the nominal set such that

• |F(T, D)| = {[g]T | g ∈F(Σ, D)}.

• π · [g]T = [π · g]T.

Remark 6.6

We exclude (congd) to avoid the following pathological situation: if we allow (congd) and T contains the axiom ⊢a = b then the reader can easily verify that supp[d(a1, . . . , an)]T = ∅. This is unwanted behaviour: the intended rôle of d(a1, . . . , an) is to be an ‘unknown element with support {a1, . . . , an}’ 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(g1, . . . , gn) for general g1, . . . , gn. Note that in related work [8, 9] we do allow such terms; we use them to build a model with a substitution action.

Lemma 6.7

Suppose that x ∈F(T, D). Then:

• id · x = x.

• π′ · (π · x) = (π′ ◦π) · x.

• x is supported by {a ∈A | ⊬a#g} for any g ∈x.

As a corollary F(T, D) defined in Definition 6.5 above is a nominal set, and furthermore if ⊢a#g then a#[g]T.

Proof

Suppose that x ∈F(T, D). By construction x = [g]T for some g ∈F(Σ, D). id · [g]T = [g]T and π′ · (π · [g]T) = (π′ ◦π) · [g]T follow by Lemma 3.2.

Write A = {a | ⊬a#g}. This is finite by Lemma 6.3. It suffices to show that A supports [g]T. Let π be a permutation such that π(a) = a for all a ∈A. We must show π · [g]T = [g]T. By definition it suffices to show [π · g]T = [g]T, that is, ⊢T π · g = g. By Lemma 3.11 this follows from ⊢ ds(π, id)#g. But this follows since ds(π, id) and A are disjoint.

The corollary follows from Definition 4.2. □

The following technical lemma will be useful later:

Lemma 6.8

Suppose that x ∈F(T, D). Then a1#x, . . . , an#x if and only if there exists some g ∈x such that ⊢a1#g, . . . , ⊢an#g are all derivable.

Proof

For the left-right implication we use Lemma 4.10 to pick some g ∈x such that a1#g, . . . , an#g. By Lemma 6.2 this is equivalent to a1#g, . . . , an#g. We conclude ⊢a1#g, . . . , ⊢an#g by 6.3.

The right-to-left implication is by Lemma 6.7. □

The following example shows why Lemma 6.8 is non-trivial:

Example 6.9

Consider a theory ATOM with one axiom ⊢a = b. [a]T = A and therefore a#[a]T. Also ⊢ATOM a = b and ⊢a#b are derivable. For further discussion see elsewhere [16, 3.4.3].

Definition 6.10

Suppose T = (Σ, Ax) and suppose D is a set of term-formers disjoint from Σ. The free algebra of T over D, we overload notation from Definition 6.5 and write it F(T, D), is the Σ-algebra with:

• Underlying nominal set F(T, D) as defined in Definition 6.5.

• Interpretation of atoms aF(T, D) = [a]T.

• Interpretation of abstraction absF(T, D)(a, x) = [[a]g]T for some g ∈x.

• fF(T, D)(x1, . . . , xn) = [f(g1, . . . , gn)]T for some g1 ∈x1, . . . , gn ∈xn, for each term-former f : n in Σ.

We overload F(T, D) to stand both for the Σ-algebra and its underlying nominal set.

Lemma 6.11

F(T, D) is a Σ-algebra.

Proof

The underlying set F(T, D) 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 fF(T, D) the choices of g ∈x and g1 ∈x1, . . . , gn ∈xn 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 a#absF(T, D)(a, x) holds, that is, that a#[[a]g]T. Choose b fresh (so b ∉g and b#[[a]g]T). Since b#[[a]g]T, also a#(b a) · [[a]g]T by part 3 of Lemma 4.4. By definition of the permutation action also a#[[b](b a) · g]T. Since ⊢a#[b](b a) · g and ⊢b#[b](b a) · g by Lemma 6.3 and the derivation rules of Figure 1, we know ⊢T [b](b a) · g = [a]g by (perm). Then [[b](b a) · g]T = [[a]g]T and we obtain a#[[a]g]T as required. □

Lemma 6.12

Suppose Σ is a signature and D is a set of fresh term-formers (so D ∩Σ = ∅). Suppose that t is a term in Σ ∪D. Suppose that σ(X) ∈F(Σ, D) for every X ∈t. Suppose that ς is a valuation to |F(T, D)| such that σ(X) ∈ ς(X) for every X ∈t.

Then [tσ]T = [[ t ]] ς.
Proof

By an easy induction on the structure of t:

• The case a. Note that from the definitions aσ ≡a and [[ a]] ς = [a]T. It follows that [aσ]T = [[ aσ]] ς.

• The case of π · X.

[(π · X)σ]T = π · [σ(X)]T = π · ς(X) = [[ π · X ]] ς.

• The case [a]t. We use the inductive hypothesis:

[([a]t)σ]T = [[a](tσ)]T = abs F(T, D)(a, [tσ]T) = abs F(T, D)(a, [[ t ]] ς) = [[ [a](tσ) ]] ς) = [[ ([a]t)σ ]] ς.

• The cases of f(t1, . . . , tn) for f ∈ Σ and d(a1, . . . , an) are similar, but simpler.

□

Theorem 6.13

F(T, D) is a model of T.

Proof

Suppose ∆ ⊢t = u is an axiom of T. Suppose that ς is a valuation to |F(T, D)| and suppose that a#ς(X) for every a#X ∈∆. We must show that [[ t]] ς = [[ u]] ς.

Let X be the set of all unknowns mentioned in ∆, t, or u. By Lemma 6.8, for every X ∈X there is an element gX ∈ς(X) such that ⊢a#gX for every a#X ∈∆. Let σ be the substitution such that σ(X) ≡gX when X ∈X and σ(X) ≡X when X ∉X. Then ⊢∆σ, and we obtain ⊢T tσ = uσ by (ax). This derivation is clearly in Π(T, D) (Definition 6.4) so [tσ]T = [uσ]T. Therefore [tσ]T = [[ t]] ς and [uσ]T = [[ u]] ς by Lemma 6.12 and the result follows. □

7. The inverse mapping

Fix a signature Σ and a finite set of fresh term-formers D = {d1, . . . , dn} (so Σ ∩D = ∅).

Definition 7.1

For each finite A ⊆A make a fixed but arbitrary choice of the following data:

• For each i some choice of unknown Xi; our choice is injective in the sense that Xi = Xj implies i = j for 1 ≤i, j ≤n. Write X = {X1, . . . , Xn}. We call Xi the ‘unknown corresponding to di’.

• A choice B of a set of atoms with the same cardinality as A, but disjoint from it (so B ∩A = ∅).

• For each i with 1 ≤i ≤n let

– ai1, . . . , aim be some choice of m distinct elements of A in some arbitrary order, and

– bi1, . . . , bim be some choice of m distinct elements of B in some arbitrary order, where m is the arity of di. We call ai1, . . . , aim, and bi1, . . . , bim the ‘choices of atoms in order corresponding to di’.

Definition 7.2

Suppose that A ⊆A. Write F(Σ, D, A) for the set of g ∈F(Σ, D) such that {a | a ∈g} ⊆A.

If g ∈F(Σ, D, A) then let F(Σ, D, A)-1(g) be the tuple (∆ ⊢g-1, σ, B, X) where:

• ∆={b#X | X ∈X, b ∈B} ∪ {a#Xi | a ∈A, Xi ∈X, ⊢a#d(ai1, . . . , aim)}.

(Note that a#d(ai1, . . . , aim) if and only if a ∉{ai1, . . . , aim}.)

• σ(Xi) = di(ai1, . . . , aim).

• σ(Y ) = id · Y for all Y ∉X.

• g-1 is defined inductively by:

a-1 ≡a ([a]g)-1 ≡[a]g-1f(g1, . . . , gn)-1 ≡f(g-1 1 , . . . , g-1 n )d(a′ 1, . . . , a′ n)-1 ≡(a′ 1 b1) · · · (a′ n bn)(b1 a1) · · · (bn an) · X

We call this construction the inverse mapping.

The following technical lemma will be useful later:

Lemma 7.3

di(ai1, . . . , ain)-1 ≡Xi.

Proof

We unpack definitions and observe that (a1 b1) · · · (an bn)(b1 a1) · · · (bn an) = id. □

We may use Lemma 7.4 without comment:

Lemma 7.4

Suppose that g, h ∈F(Σ, D, A). Suppose that

(∆⊢t, σ, B, X) = F(Σ, D, A)-1(g) and (∆′ ⊢u, σ′, B′, X ′) = F(Σ, D, A)-1(h).

then ∆= ∆′, σ = σ′, B′ = B, and X ′ = X.

Proof

The construction of ∆and ∆′ does not depend on g and h. Similarly for σ and σ′, B′ and B, and X ′ and X. □

Lemma 7.5

Suppose that g ∈F(Σ, D, A) and (∆⊢g-1, σ, B, X) = F(Σ, D, A)-1(g). Then ⊢CORE g-1σ = g.

Proof

We work by induction on g. All cases are routine, we consider only the case g ≡ di(a′ 1, . . . , a′ n) for di ∈D where n is the arity of di. Then

g-1 ≡(a′ 1 bi1) · · · (a′ n bin)(bi1 ai1) · · · (bin ain) · Xi

and σ(Xi) ≡ di(ai1, . . . , ain). The result follows by an easy calculation using the definition of the permutation action. □

Corollary 7.6

Suppose that g, h ∈F(Σ, D, A). Suppose that

F(Σ, D, A)-1(g) = (∆⊢g-1, σ, B, X) and F(Σ, D, A)-1(h) = (∆⊢h-1, σ, B, X).

Then ∆⊢T g-1 = h-1 implies ⊢T g = h.

Proof

By Lemma 7.5 ∆⊢g-1σ = g and ∆ ⊢h-1σ = h. The result follows using (tran). □

Lemma 7.7

Suppose that d(a′ 1, . . . , a′ m) ∈F(Σ, D, A) and suppose a ∈A. Then ∆⊢a#d(a′ 1, . . . , a′ m)-1 if and only if a ∉{a′ 1, . . . , a′ m}.

Proof

Recall our choices of a1, . . . , am and b1, . . . , bm from A and B respectively. By construction d(a′ 1, . . . , a′ m)-1 ≡π′ · X for some X ∈X, were

π′= (a′ 1 b1) · · · (a′ m bm)(b1 a1) · · · (bm am).

By the syntax-directed structure of the rules in Figure 1, ∆⊢a#π′ · X if and only if ∆⊢π′-1(a)#X. The result follows by the construction of ∆. □

Lemma 7.8

Suppose that π(c) = c for all c ∈A \ A. Suppose that g ∈F(Σ, D, A) and suppose that F(Σ, D, A)-1(g) = (∆⊢g-1, σ, B, X). Then:

• ∆⊢a#(π · g)-1 if and only if ∆⊢a#π · (g-1).

• ∆⊢CORE (π · g)-1 = π · g-1 providing that π(c) = c for all c ∈A \ A.

Proof

• We work by induction on g. The only non-trivial case is when g ≡ d(a′ 1, . . . , a′ m) where m is the arity of d. It suffices to show that ∆⊢a#π′ · X if and only if ∆ ⊢a#π′′ · X where X ∈X is our choice of unknown in X to correspond to d ∈D and

π′= (π(a′ 1) b1) · · · (π(a′ m) bm)(b1 a1) · · · (bm am)

and

π′′= π ◦(a′ 1 b1) · · · (a′ m bm)(b1 a1) · · · (bm am).

This follows by easy calculations using the construction of ∆and the assumption that π(bi) = bi for 1 ≤i ≤m.

• We work by induction on g. The only non-trivial case is again when g ≡ d(a′ 1, . . . , a′ m) where m is the arity of d. It suffices to show that ∆⊢CORE π′ · X = π′′ · X for X, π′, and π′′ as in the first part of this result. By Lemma 3.11 it suffices to show ∆ ⊢ ds(π′, π′′)#X. This follows by easy calculations as in the first part.

□

If Π is a nominal algebra derivation, write a ∈ Π when a occurs in the syntax of Π (that is, when there exists some term t in the syntax of Π such that a ∈t). Theorem 7.9 is an important technical result (compare with Lemma 6.18 from [9] and Lemma 3.4.23 from [16]):

Theorem 7.9

Suppose that g, h ∈F(Σ, D, A). Suppose that

F(Σ, D, A)-1(g) = (∆⊢g-1, σ, B, X) and F(Σ, D, A)-1(h) = (∆⊢h-1, σ, B, X).

Then:

• If ⊢a#g then ∆⊢a#g-1.

• If a derivation Π ∈ Π(T, D) exists of ⊢T g = h and {a | a ∈ Π} ⊆A then

∆⊢T g-1 = h-1.
Proof

We inductively transform Π into a derivation of ∆ ⊢T t = u.

• The cases of (#ab), (#[]a), (#[]b), (cong[]), (refl), (symm) and (tran) are easy.

• The case (#f). There are two possibilities:

– Suppose ⊢a#f(g1, . . . , gn) for f ∈ Σ. By assumption ⊢a#gi for 1 ≤i ≤n so ∆⊢a#g-1 i by inductive hypothesis. By construction f(g1, . . . , gn)-1 ≡ f(g-1 1 , . . . , g-1 n ) and the result follows.

– Suppose ⊢a#di(a′ 1, . . . , a′ m) for di ∈D and m the arity of di. By assumption ⊢a#a′ i for 1 ≤i ≤m. It follows that a ∉{a′ 1, . . . , a′ m}. 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 ∈D is impossible, since we assumed that Π does not mention (congd).

• (perm). By inductive hypothesis ∆ ⊢a#g-1 and ∆ ⊢b#g-1. Then ∆ ⊢T (a b) · g-1 = g-1 by (perm). By Lemma 7.8 ∆⊢CORE ((a b) · g)-1 = (a b) · g-1. The result follows.

• (ax∆′⊢v=w). Then ⊢π · ∆′τ and ⊢T π · vτ = π · wτ for some permutation π and substitution τ.

We must show ∆ ⊢T (π · vτ)-1 = (π · wτ)-1 and by inductive hypothesis we may assume ∆ ⊢T (π · ∆τ)-1.

By Lemma 7.8 it suffices to show

∆⊢T π · (vτ)-1 = π · (wτ)-1

given

∆⊢T π · (∆τ)-1.

Define τ ′ by:

τ ′(X) ≡ τ(X)-1(τ(X) ≢X)τ ′(Y ) ≡ id · Y (τ(Y ) ≡id · Y )

Then (vτ)-1 ≡vτ ′, (wτ)-1 ≡wτ ′ and (∆′τ)-1 ≡∆′τ ′, so it suffices to show

∆⊢T π · vτ ′ = π · wτ ′.

By (ax∆′⊢v=w) 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.

Definition 8.1

For Σ-algebras X and Y, a Σ-algebra homomorphism from X to Y is an equivariant function θ : |X| →|Y| such that:

• θaX = aY for every atom.

• θabsX(a, x) = absX(a, θx).

• θfX(x1, . . . , xn) = fY(θx1, . . . , θxn) for every f in Σ.

Suppose X and Y are Σ-algebras. Call Y a homomorphic image of X when there is a Σ-algebra homomorphism θ from X to Y such that θ ∈|X| →|Y| is a surjection onto |Y|.

The following technical lemma establishes a ‘capture-avoidance’ property needed for Corollary 8.4.

Lemma 8.2

Suppose that X and Y are Σ-algebras and suppose that θ ∈|X| →|Y| is equivariant. Then if x ∈|X| and a#θx then there exists x′ ∈|X| such that a#x′ and θx = θx′.

Informally, x′ is a representative of θ-1(θx) which ‘avoids name-clash’ with supp(θx).

Proof

Choose fresh a′ (so a′#x) and choose x′ = (a′ a)x. Then

• (a′ a)(θx) = θx by part 2 of Lemma 4.4 (a′ ∉ supp(θx) by Lemma 4.8) and

• (a′ a)(θx) = θx′ by equivariance.

Also a#x′ follows by part 3 of Lemma 4.4 and the result follows. □

Lemma 8.3

Suppose Σ is a signature and suppose that X and Y are Σ-algebras. Suppose θ is a Σ-algebra homomorphism from X to Y.

Suppose that ς′ is a valuation to X and ς is a valuation to Y. Finally suppose that θ(ς′(X)) = θ(ς(X)) for all unknowns X.

Then θ([[ t ]] ς′) = [[ t ]] ς.
Proof

By an easy induction on t. □

Corollary 8.4

Suppose Σ is a signature and T = (Σ, Ax) is a theory. Suppose that X and Y are Σ-algebras and suppose Y is a homomorphic image of X.

Then if X is a model of T, then so is Y.

Proof

Write θ for the Σ-algebra homomorphism from |X| to |Y|. Recall that by assumption θ is surjective.

Choose any (∆ ⊢t = u) ∈Ax and a valuation ς to Y. It suffices to show that [[ ∆⊢t = u]]Yς is valid.

Suppose [[ ∆]]Yς is valid; unpacking definitions this means that a#ς(X) for every a#X ∈∆.

For each unknown X let X = {x ∈X | θ(x) = ς(X)}. We can verify that for any permutation π, π · X = {x ∈X | θ(x) = π · ς(X)}. Therefore if π·ς(X) = ς(X) then π · X = X and it follows that supp(X) ⊆ supp(ς(X)). We construct a valuation ς′ to X by for each unknown X setting ς′(X) = x for some choice of x ∈X such that a#x for every a#X ∈ ∆. Such a choice exists by Lemma 4.10.

By construction [[ ∆]]Xς′ is valid, and so by assumption [[ t]]Xς′ = [[ u]]Xς′. We apply θ to both sides of the equality and use Lemma 8.3 to conclude that [[ t]]Yς = [[ u]]Yς as required. □

8.2. Subalgebras.

Definition 8.5

For Σ-algebras X and Y, call X a subalgebra of Y when the following conditions are satisfied:

• |X| ⊆|Y|.

• aX = aY for all atoms a.

• absX(a, x) = absY(a, x) for all atoms a and x ∈|X|.

• For every term-former f in signature Σ, if f has arity n and x1, . . . , xn ∈|X| then fX(x1, . . . , xn) = fY(x1, . . . , xn).

In other words, X is closed under the interpretation of the term-formers which it inherits from Y.

Lemma 8.6

For Σ-algebras X, Y and a theory T = (Σ, Ax), if Y is a model of T and X is a subalgebra of Y then X is a model of T.

Proof

Suppose (∆ ⊢t = u) ∈ Ax and suppose ς is a valuation to |X| such that a#ς(X) for every a#X ∈∆. Since ς is also a valuation to |Y|, it follows that [[ t]] ς = [[ u]] ς. Therefore X satisfies all the axioms of T. □

8.3. Products.

Definition 8.7

Let I be a (possibly countably infinite) indexing set and (Xi)i∈I be an I-indexed collection of Σ-algebras. The product algebra Πi∈IXi is the Σ-algebra with:

• Underlying nominal set Πi∈IXi as defined in Definition 4.5, considering each Xi as a nominal set.

Recall that this has the component-wise permutation action; π·(xi)i∈I = (π · xi)i∈I.

• aΠi∈IXi = (aXi)i∈I.

• absΠi∈IXi(a, (xi)i∈I) = Πi∈IabsXi(a, xi).

• For each term-former f of arity n the component-wise interpretation function

fΠi∈IXi((x1 i )i∈I, . . . , (xn i )i∈I) = (fXi(x1 i , . . . , xn i ))i∈I.

It is easy to check that Πi∈IXi is a Σ-algebra:

Lemma 8.8

For any I-indexed collection of Σ-algebras (Xi)i∈I, if Xi is a model of T = (Σ, Ax) for every i ∈I then so is Πi∈IXi.

Proof

Suppose that ς is a valuation to |Πi∈IXi|. Suppose that (∆ ⊢t = u) ∈ Ax and suppose that a#ς(X) for every a#X ∈ ∆. We must show that [[ t]] ς = [[ u]] ς.

For each i ∈I we obtain a valuation ςi to |Xi| projecting to the ith component of ς(X). By Lemma 4.6 we know that a#ςiX for every a#X ∈∆. It follows that the ith projection of [[ t]] ς is equal to the ith projection of [[ u]] ς, and thus that [[ t]] ς = [[ u]] ς. □

8.4. Atoms-abstraction.

Suppose X is a nominal set and suppose x ∈X and a ∈A.

Definition 8.9

Define atoms-abstraction by

[a]x = {(b, (b a) · x) | b#x} ∪{(a, x)}.

Write [A]X for the nominal set such that:

• |[A]X| = {[a]x | a ∈A, x ∈X}.

• π · [a]x = [π(a)]π · x.

(Note that by our permutative convention b ranges over atoms not equal to a.) It is not hard to prove that [A]X 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.

Lemma 8.10

If x′ 1, . . . , x′ n ∈ [A]V then for any fresh c (so c#x′ 1, . . . , x′ n) there exist x1, . . . , xn ∈V such that x′ i = [c]xi for 1 ≤i ≤n.

Proof

By [12, Proposition 5.5]. □

Lemma 8.11

If [c]x = [c]x′ then x = x′.

Proof

By [12, Proposition 5.5]. □

Lemma 8.12

supp([c]x) = supp(x) \ {c}.

Proof

By [12, Proposition 5.2]. □

Lemma 8.13

If c#x and c′#x then [c]x = [c′]x.

Proof

By definition (c′ c) · [c]x = [c′](c′ c) · x. By Lemma 8.12 c′#[c]x and c#[c]x. By assumption c′#x and c#x. The result follows by part 2 of Lemma 4.4. □

Definition 8.14

Suppose that V is a Σ-algebra. Define [A]V by:

• |[A]V| = [A]|V|.

• a[A]V = [c]aV (for any c ≠ a).

• f[A]V([c]x1, . . . , [c]xn) = [c]fV(x1, . . . , xn).

Lemma 8.15

[A]V is a Σ-algebra.

Proof

There are two things to check:

• a[A]V is well-defined. Suppose c, c′ ≠ a. By Lemma 4.8 c#aV and c′#aV. By Lemma 8.13 [c]aV = [c′]aV.

• f[A]V is equivariant. This follows easily from the definitions:

π · f[A]V([c]x1, . . . , [c]xn) =π · [c]fV(x1, . . . , xn) =[π(c)]fV(π · x1, . . . , π · xn) =f[A]V([π(c)]π · x1, . . . , [π(c)]π · xn) =f[A]V(π · [c]x1, . . . , π · [c]xn).□
Definition 8.16

If V is a Σ-algebra and ς is a valuation to |V|, then write [c]ς for the valuation to |[A]V| such that X maps to [c]ς(X).

Lemma 8.17

Suppose that V is a Σ-algebra and ς is a valuation to |V|. Then if c ∉t then

[[ t ]][A]V[c]ς = [c]([[ t ]]Vς).
Proof

By induction on t:

• The case t ≡a. [[ a]][A]V[c]ς = a[A]V = [c]aV = [c]([[ a]]Vς).

• The case t ≡c. Here there is nothing to prove, since we assumed that c ∉t.

• The case t ≡ f(t1, . . . , tn).

[[ f(t1, . . . , tn) ]][A]V[c]ς =[[ f ]][A]V([[ t1 ]][A]V[c]ς, . . . , [[ tn ]][A]V[c]ς)=[[ f ]][A]V([c][[ t1 ]]Vς, . . . , [c][[ tn ]]Vς)=[c][[ f ]]V([[ t1 ]]Vς, . . . , [[ tn ]]Vς).□
Corollary 8.18

Suppose that c ∉t and c ∉u. Then [[ t ]]Vς = [[ u]]Vς if and only if [[ t]][A]V[c]ς = [[ u]][A]V[c]ς.

Proof

Suppose c ∉t and c ∉u.

If [[ t]]Vς = [[ u]]Vς then [c][[ t]]Vς = [c][[ u]]Vς and the result follows by Lemma 8.17.

Conversely suppose [[ t]][A]V[c]ς = [[ u]][A]V[c]ς. By Lemma 8.17 [c][[ t]]Vς = [c][[ u]]Vς. The result follows by Lemma 8.11. □

9. Varieties and Equational Classes of Algebras

Definition 9.1

A (nominal algebra) variety V 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 V ∈V and V′ is a homomorphic image of V, then V′ ∈V.

• If V ∈V and V′ is a subalgebra of V then V′ ∈V.

• If I is any countable indexing set and Vi ∈V for all i ∈I then Πi∈IVi ∈V.

• If V ∈V then [A]V ∈V.

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.

Definition 9.2

Call a collection V of Σ-algebras (nominal algebra) equational when there is some theory T = (Σ, Ax) in nominal algebra such that V 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:

Theorem 9.3

A collection of Σ-algebras V 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 V. In practice we care about the case that V is a variety, but nothing in this subsection depends on that.

Lemma 9.4

Suppose Y is a model of theory T = (Σ, Ax). Suppose D is a set of fresh constructors (so D ∩Σ = ∅). Then the following data determines a Σ-algebra homomorphism from F(T, D) to Y: for each n-ary term-former d ∈D

• a choice of n atoms a1, . . . , an and

• a choice of element θd(a1, . . . , an) ∈|Y| such that

supp(θd(a1, . . . , an)) ⊆{a1, . . . , an}.

This is an initiality property [15] adapted to our particular situation of nominal sets.

Proof

We define a function, by abuse of notation write it θ, from F(Σ, D) to |Y| by:

• θd(π(a1), . . . , π(an)) = π · θd(a1, . . . , an).

• θa = aY.

• θ[a]g = absY(a, g).

• θf(g1, . . . , gn) = fY(θg1, . . . , θgn).

Suppose we could prove that if [g]T = [h]T then θg = θh. Then we can view θ as a function θF(T, D) from |F(T, D)| to |Y|.

Also:

• It is easy to prove by induction on g that π · θg = θ(π · g), and it follows that

π · (θF(T, D)[g]T) = π · θg = θ(π · g) = θF(T, D)[g]T.

• θF(T, D)aF(T, D) = θa = aY.

• θF(T, D)absF(T, D)(a, g) = θ[a]g = abs(a, θg) = abs(a, θF(T, D)[g]T).

• θF(T, D)fF(T, D)([g1]T, . . . , [gn]T) = θf(g1, . . . , gn) = fY(θg1, . . . , θgn) = fY(θF(T, D)[g1]T, . . . , θF(T, D)[gn]T).

It follows that θ viewed as a function from |F(T, D)| to |Y| is also a Σ-algebra homomorphism and we are done.

It remains to prove that [g]T = [h]T implies θg = θh. Suppose Π ∈ Π(T, D) (Definition 6.4) is a derivation of ⊢T g = h. Let A = {a | a ∈ Π} and let D′ be the term-formers mentioned in Π. Let

(∆⊢g-1, σ, B, X) = F(Σ, D′, A)-1(g) and (∆⊢h-1, σ, B, X) = F(Σ, D′, A)-1(h).

Let ς(X) = θ(σ(X)). By an easy inductive argument we deduce that θg = [[ g-1]]Y ς and θh = [[ h-1]]Y ς . By Theorem 7.9 ∆⊢T g-1 = h-1 is derivable. The result follows by Soundness (Theorem 5.6). □

We need some notation for the proof of Theorem 9.8:

Definition 9.5

Suppose that T = (Σ, Ax). Suppose that Σ-algebras X and Yi for i ∈I are models of T. Suppose θi ∈X ⇒Yi is a family of homomorphisms. Then write Πi∈Iθi for the natural map from X to Πi∈IYi, mapping x ∈|X| to (θix)i∈I ∈|Πi∈IYi|.

It is easy to verify that Πi∈Iθi above is a homomorphism.

Theorem 9.6

If V ∈V then there exists some (sufficiently large) set of fresh constructors D such that there exists a Σ-algebra homomorphism θ from F(T, D) to V, such that θ is a surjection on underlying sets.

That is: every element of V is a homomorphic image of some sufficiently large free algebra.

Proof

Write car(V) for the cardinality of |V|. Suppose that D is a set of fresh constructors with at least car(V) constructors of every arity n > 0, and with no constructors of arity 0. We shall exhibit a suitable θ from F(T, D) to V.

For each permutation equivalence class {πv | π ∈P} ⊆|V| choose a representative v ∈|V| . For each v,

• order supp(v) as a1, . . . , an, pick a unique n-ary term-former d ∈D (which has not been assigned to any other v′), and

• assign θd(a1, . . . , an) = v.

For each remaining unassigned d(a, . . .) assign θd(a, . . .) = aV.2 By Lemma 9.4 this assignment extends to a homomorphism from F(T, D) to V.

It remains to show that this is a surjection, but this is easy: Consider any v′ ∈|V|. By construction there exists some representative v such that v′ ∈{πv | π ∈P. So write v′ = πv. By construction v = θd(a1, . . . , an) for some d(a1, . . . , an) and so v′ = θd(πa1, . . . , πan). □

9.2. Injections out of free algebras.

Fix a signature Σ and a set of Σ-algebras V. As in Subsection 9.1 we care most about the case that V is a variety, but nothing in this subsection depends on assuming that.

Definition 9.7

Let T = (Σ, Ax) where Ax is the collection of judgements valid in all V ∈V for all valuations. Call T the theory generated by V.

That is, (∆ ⊢t = u) ∈ Ax when for every V ∈V and every valuation ς to |V|, it is the case that if a#ς(X) for every a#X ∈ ∆then [[ t]]Vς = [[ u]]Vς.

Theorem 9.8

Suppose that V is a collection of Σ-algebras. Let T be the theory generated by V. Suppose D is any set of fresh constructors (so D ∩Σ = ∅).

Then there exists some indexing set I and algebras Vi ∈V for i ∈I such that there exists a Σ-algebra homomorphism θ from F(T, D) to Πi∈IVi such that θ is an injection on underlying sets.

Proof

Let I be the set of pairs (g, h) of ground terms in the signature Σ ∪D such that [g]T ≠ [h]T.

Choose some i = (g, h) ∈I.

Let A = {a | a ∈g} ∪{a | a ∈h}. Let D′ be the set of term-formers in D occurring in g and h. Recalling Lemma 7.4, suppose that

F(Σ, D′, A)-1(g) = (∆⊢t, σ, B, X) and F(Σ, D′, A)-1(h) = (∆⊢u, σ, B, X).

We assumed that ⊬T g = h so by Corollary 7.6 ∆⊬T t = u. By Completeness (Theorem 5.7) there exists some model Vi and valuation ς such that [[ ∆]]Vς i is valid and [[ t]]Viς ≠ [[ u]]Vς i. Let

{c1, . . . , cp} be( ⋃X∈Xsupp(ςX))\ A

in some order. Write V′ i for [A]pVi and write ς′ for [c1] . . . [cp]ς.

V is closed under atoms-abstraction so V′ i ∈V. By Corollary 8.18

[[ t ]]V′ iς′ ≠ [[ u ]]V′ Iς′.

We construct a partial assignment θ by

θd(a1, . . . , an) = ς′X

for each d ∈D′, where X ∈X is the unknown corresponding to d, and a1, . . . , an 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 F(T, D) to V′ i but in order to do so we must verify that supp(ς′X) ⊆{a1, . . . , an}.

Suppose that a ∉{a1, . . . , an}. By the rules in Figure 1 ⊢a#d(a1, . . . , an). By Theorem 7.9 ∆⊢a#d(a1, . . . , an)-1. By assumption [[ ∆]]V′ iς′ so by Soundness (Theorem 5.6) a#[[ d(a1, . . . , an)-1 ]]V′ iς′. Using Lemma 7.3 we deduce that a#ς′X. It follows that supp(ς′X) ⊆{a1, . . . , an} as required.

Note that by construction θ([g]T) ≠ θ([h]T).

It follows by the choice of Vi that Πi∈Iθ from F(T, D) to Πi∈IV′ i is injective as a map on underlying sets. □

Remark 9.9

The reader might ask why we bother with [A]V when we can build this as the subalgebra of V in the image of absV — 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.

Corollary 9.10

Suppose that V is a variety and suppose T is the theory generated by V. Then F(T, D) ∈V for every set of fresh term-formers D.

Proof

By Theorem 9.8 there is some indexing set I, set of Σ-algebras Vi ∈V for i ∈I, and Σ-algebra homomorphism θ from F(T, D) to Πi∈IVi that is an injection on underlying sets. V is closed under products so Πi∈IVi ∈V. The image of |F(T, D)| is a subalgebra of Πi∈IVi, and F(T, D) is a homomorphic image (by inverting θ) of that subalgebra. V is closed under subalgebras and homomorphic images, and the result follows. □

9.3. Proof of the nominal HSP theorem.

Proof

of Theorem 9.3. Suppose that V is equational. By Lemma 8.8 V is closed under products. By Corollary 8.4 V is closed under homomorphic images. By Lemma 8.6 V is closed under subalgebras. Therefore V is a variety.

Conversely, suppose V is a variety. Let T be the theory on Σ generated by V as described in Definition 9.7. Let V be any model of T. By Theorem 9.6 there exists some D such that V is a homomorphic image of F(T, D). By Corollary 9.10 F(T, D) ∈V. Since V is closed under homomorphisms, V ∈V as required. Therefore V 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 V. ↩