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

NOMINAL ALGEBRA

MURDOCH J. GABBAY AND AAD MATHIJSSEN

Abstract. Nominal terms are a term-language used to accurately and expressively represent systems with binding. We present Nominal Algebra (NA), a theory of algebraic equality on nominal terms. Built-in support for binding in the presence of meta-variables allows NA to closely mirror informal mathematical usage and notation, where expressions such as λa.t or ∀a.φ are common, in which meta-variables t and φ explicitly occur in the scope of a variable a. We describe the syntax and semantics of NA, and provide a sound and complete proof system for it. We also give some examples of axioms; other work has considered sets of axioms of particular interest in some detail.

1. Introduction

Universal algebra [6, 18, 5] is the theory of equalities t = u. It is a simple framework within which we can study mathematical structures, for example groups, rings, and fields. It has also been applied to study the mathematical properties of mathematical truth and computability. For example boolean algebras correspond to classical truth, heyting algebras correspond to intuitionistic truth, cylindric algebras correspond to truth in the presence of predicates as well as propositions, combinators correspond to computability, and so on.

Informal mathematical usage and notation often involve binding. In many cases, this involves freshness and α-equivalence in the presence of meta-variables. For example:

• λ-calculus: λx.(tx) = t — if x does not occur free in (is fresh for) t.

• π-calculus: (νa.P) | Q = νa.(P | Q) — if a is fresh for Q.

• First-order logic: (∀x.φ) ∧ψ = ∀x.(φ ∧ψ) — if x is fresh for ψ.

Here t, P, Q, φ and ψ are meta-variables ranging over concrete terms.

Now take any binder ξ ∈{∀, λ, ν}. Then:

• (ξx.t)[y↦ →u] = ξx.(t[y↦ →u]) — if x is fresh for u.

• α-equivalence: ξx.t = ξy.t[x↦ →y] — if y is fresh for t.

Nominal terms [26, 27] are a syntax designed to naturally express binding, freshness and α-equivalence in the presence of these meta-variables. This paper studies the theory of equality between nominal terms. We obtain Nominal Algebra (NA). This permits direct and intuitive axiomatisation of systems with binding and yet we keep the flavour of ‘normal algebra’.

In other published work we have already applied nominal algebra to investigate specific axiomatic systems for truth and computability [12, 13]. In this paper we present a common syntax and semantics for Nominal Algebra, together with a sound and complete proof system.

2. Syntax

2.1. Sorts, terms and signatures.

In this paper we consider a sorted NA; an unsorted version would also be feasible. Fix disjoint collections of base sorts T and atomic sorts A. For our examples we need only one atomic sort, so we may write A for the atomic sort.

Then sorts τ and arities ρ are defined by the following grammars:

τ ::= T | A | [A]τ ρ ::= (τ1, . . . , τn)τ

Here n may be zero, in which case we write ()τ as τ.

For each atomic sort A fix a countably infinite collection of atoms aA, bA, cA, representing object-variables. For each sort τ fix a countably infinite collection of unknowns Xτ, Yτ, Zτ, representing meta-variables. All these collections are assumed disjoint. We may omit the subscripts. We call π · X where π stands for a permutation of atoms a moderated unknown. This represents a permutation of object-variables that is performed when the meta-variable is instantiated to a concrete term. We will explain later how these permutations on unknowns facilitate α-conversion on nominal terms.

Fix term-formers f to each of which is associated some unique arity ρ. We may write f : ρ for ‘f, which has arity ρ’.

Terms t, u, v are inductively defined by:

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

We define sorting assertions inductively by:

aA : A π · Xτ : τt : τ [aA]t : [A]τf : (τ1, . . . , τn)τ t1 : τ1· · · tn : τnf(t1, . . . , tn) : τ

Here [a]t is called an abstractor; it represents a term in which an object-variable is abstracted.

A signature Σ is a triple containing finite sets of base sorts, atomic sorts, and term-formers with associated arities.

Example 2.1

A signature for. . .

• the λ-calculus ΣLAM consists of base sort T, atomic sort A, and term-formers var : (A)T, app : (T, T)T, and λ : ([A]T)T. Note how this mirrors the specification of λ-calculus syntax. var is needed to turn an atom aA into a term of sort T; this is a standard device called a casting function. We generally sugar app(t, u) to tu and λ([a]t) to λ[a]t.

• first-order logic ΣFOL with equality has base sorts F and T, atomic sort A, and term-formers ⊥ : F, ⊃: (F, F)F, ∀ : ([A]F)F, ≈: (T, T)F, and var : (A)T. We sugar ⊃(φ, ψ) to φ ⊃ψ, ∀([a]φ) to ∀[a]φ and ≈(t, u) to t ≈u.

A permutation π of atoms is a bijection A →A with finite support. That means that for some finite set of atoms (which may be empty) π(a) ≠ a, and for all other atoms π(a) = a. For further discussion of permutations of atoms see elsewhere ([15], [27], and [10, Section 5.4]). Write Id for the identity permutation, π-1 for the inverse of π, and π◦π′ for the composition of π and π′, i.e. (π◦π′)(a) = π(π′(a)). Id is also the identity of composition, i.e. Id ◦π = π and π ◦ Id = π. Write (a b) for the permutation that swaps a and b, i.e. the permutation that maps a to b, b to a and all other c to themselves. We abbreviate Id · X to X.

In the presence of multiple atomic sorts we assume that π(a) must have the same sort as a; so permutations are sort-respecting.

Write t ≡u for syntactic identity of terms. There is no quotient by abstraction so for example [a]a ≢ [b]b. Say that a term t is closed when it does not contain any unknowns. Write a ∈t for ‘a occurs in (the syntax of) t’, and X ∈t for ‘X occurs in (the syntax of) t’. Occurrence is literal, e.g. a ∈ [a]a and a ∈π · X when π(a) ≠ a. Similarly write a ∉t and X ∉t for ‘does not occur in the syntax of t’.

2.2. Judgements, axioms and theories.

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 of the same sort. Call a freshness 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 }.

A judgement is a pair ∆ →A of a freshness context and an assertion. We may call it an equality (or freshness) judgement, if A is an equality (or freshness) assertion. We may write ∅→A as A.

We allow equality judgements ∆ →t = u as axioms (made formal later). We do not allow freshness judgements as axioms; we shall see that they can be easily expressed using equalities instead.

A theory T = (Σ, Ax) is a pair of a signature Σ and a possibly infinite set of axioms Ax on that signature. We name theories in sans serif font.

Example 2.2

• CORE is a theory with an atomic sort A and one axiom

(perm) a#X, b#X →(b a) · X = X

This theory expresses α-equivalence in the presence of meta-variables (made formal by Theorem 4.5). Henceforth we shall consider only theories containing (perm).

• SUB has a signature with a base sort T, a sort of atoms A, a substitution term-former sub : ([A]τ, T)τ for each τ ∈{T, [A]T}, additional term-formers (say) app : (T, T)T and lam : ([A]T)T, and a variable casting term-former var : (A)T. We sugar sub([a]t, u) to t[a↦ →u]. SUB has the following axioms:

var(a)[a↦ →X] = Xa#Y → Y [a↦ →X] = Yb#X → ([b]Y )[a↦ →X] = [b](Y [a↦ →X])f(Y1, . . . , Yn)[a↦ →X] = f(Y1[a↦ →X], . . . , Yn[a↦ →X])b#Y → Y [a↦ →var(b)] = (b a) · YHere f ∈{app, lam, sub}.

A detailed study of SUB can be found in [12].

• LAM takes SUB and adds the axiom (λ[a]Y)X = Y[a↦ →X]. Here we use sugar from Example 2.1.

• In other work we investigate a theory FOL for the signature of first-order logic ΣFOL mentioned above [13].

We are not concerned in whether the above theories have some other base data sorts, so the reader should consider these examples to be parametric over such choices. As mentioned above, we only consider theories extending CORE.

3. Semantics

Nominal sets are the natural model of nominal terms (the sets came first [15]). Write P for the set of all permutations. A permutation action on a set X is a function · : P × X →X, write it infix as π · x, such that Id · x = x and π · (π′ · x) = (π ◦π′) · x. It is easy to prove that π is always bijective as a function on X. Call a pair (X, ·) of a set and a permutation action on it a set with a permutation action. We generally write X both for the set and for (X, ·).

Example 3.1

• A has the natural permutation action given by π · a = π(a).

• The powerset of A, write it P = {U | U ⊆A} has the natural permutation action given by the pointwise action π · U = {π · u | u ∈U}.

• Call U ⊆A cofinite when A\U is finite. The set of finite and cofinite subsets of A, write it Pfs = {U | U ⊆A, U finite or cofinite} inherits the pointwise action from P. (fs stands for finite support; more on this soon.)

We assume these permutation actions on these sets henceforth. Given a formula φ on atoms, write Иa.φ(a) (the Gabbay-Pitts NEW quantifier [8, 15]) for the assertion ‘φ(a) is false for finitely many atoms a ∈A (perhaps none), and true for all other atoms’. This is a mathematical notion of ‘φ(a) for most a’. For a ∈A and x ∈X write a#x when Иb.(b a) · x = x. Read this as a is fresh for x.

Example 3.2

• For X = A, a#x when a ≠ x.

• For both X = P and X = Pfs, a#U when U is finite and a ∉U, or when U is cofinite and a ∈U. For example, a#{b} but not a#A\{a}.

We can think of a#x as an abstract notion of ‘does not occur in any distinguished manner’. We say ‘distinguished’, because the last example of Pfs shows that # is not the same as ∉: for example a ∉ (A\{a}) but not a#(A\{a}).

Call X a nominal set when ∀x∈X.Иa.a#x, i.e. ∀x∈X.Иa.Иb.(b a) · x = x. This property expresses finite support [15, 23]. Henceforth X and Y range over nominal sets. Of the examples above, all except for P are nominal sets [8].

Write X × Y for the set {(x, y) | x ∈X, y ∈Y} with the pointwise permutation action π · (x, y) = (π · x, π · y). The abstraction set [A]X is A × X quotiented by a relation ∼ given by (a, x) ∼ (a′, x′) when Иb.(b a) · x = (b a′) · x′. Write [a]x for the ∼-equivalence class of (a, x). The elements of [A]X validate the characteristic property of α-equivalence that if a′#x then [a]x = [a′](a′ a) · x (detailed accounts of this are elsewhere [15, 8]). Both X × Y and [A]X are a nominal sets.

Functions f : X →Y (on the underlying sets) have a natural conjugation permutation action given by (π · f)(x) = π · (f(π-1 · x)). Call f equivariant if π · f = f for all π, i.e. if π · (f(x)) = f(π · x) always.

We can now give a semantics to NA theories. An interpretation I of a signature assigns a nominal set TI to each base sort T and an equivariant function fI ∈ (⟦τ1⟧I × · · · × ⟦τn⟧I) →τ I to each term-former f : (τ1, . . . , τn)τ.

⟦τ⟧I is inductively defined by:

⟦T⟧I = TI⟦A⟧I = A ⟦[A]τ⟧I = [A]⟦τ⟧I

An evaluation ς maps unknowns Xτ to elements ς(Xτ) ∈⟦τ⟧I. An interpretation and evaluation extend to terms ⟦t⟧I ς:

⟦a⟧I ς = a ⟦π·X⟧I ς = π·ς(X) ⟦[a]t⟧I ς = [a]⟦t⟧I ς⟦f(t1, . . . , tn)⟧I ς = fI(⟦t1⟧I ς , . . . , ⟦tn⟧I ς )

We can now define validity of assertions, freshness contexts and judgements:

⟦a#t⟧I ς (is valid) when a#⟦t⟧I ς⟦t = u⟧I ς when ⟦t⟧I ς = ⟦u⟧I ς

⟦∆⟧I ς when a#ς(X) for each a#X ∈∆

⟦∆→A⟧I ς when ⟦∆⟧I ς implies ⟦A⟧I ς

⟦∆→A⟧I when ⟦∆→A⟧I ς for all evaluations ς

Then a model M of a theory T is an interpretation of its signature such that ⟦∆→t = u⟧M for all axioms ∆ →t = u of T. So a model of an NA theory is just like a model of any other algebraic theory, but we must interpret atoms by atoms, permutations by permutations, abstractions by abstractions, and term-formers by equivariant functions on underlying sets.

Write ∆ |=T A if ⟦∆→A⟧M for all models M of T. Say that ∆ validates A in theory T.

4. Derivability

4.1. Permutation and substitution actions.

Substitution is the mechanism by which unknowns X become terms, and is necessary in algebra in order to define instances of axioms. Formally a substitution σ is a finitely supported function from unknowns to terms of the same sort. 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, 1 ≤i ≤n.

In order to define the inference rules of NA, we need to be able to apply permutations and substitutions to terms. Write π · t for the action of a permutation π on a term t, defined by:

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

Composition and identity of permutations also extend to terms.

Lemma 4.1

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

Proof

By straightforward induction on the structure of t, using the definition of π · . □

Write the action of a substitution σ on a term t as tσ and define it by:

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

Note that substitution does not avoid capture, i.e. ([a]X)[a/X] ≡ [a]a. It reduces parentheses to give substitution a higher priority than permutation and abstraction, so we do. Write σ ◦σ′ for composition, i.e. t(σ ◦σ′) ≡ (tσ)σ′.

The following commutation is easy to prove [27, 7]:

Lemma 4.2

π · tσ ≡ (π · t)σ.

Proof

By straightforward induction on the structure of t, using the definitions of π · and σ. □

Another permutation action is useful. Write tπ for the meta-level action of π on t, inductively defined by:

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

Also for this permutation action, composition and identity of permutations extend to terms.

Lemma 4.3

tπ◦π′ ≡tπ′π and tId ≡t.

Proof

By straightforward induction on the structure of t, using the definition of π. □

Permutation actions π · and π are interdefinable; sometimes one is more convenient than the other.

Lemma 4.4

Given a term t let σ and σ′ be substitutions that map each X ∈t to π · X and π-1 · X, respectively. Then π · t ≡tπσ and tπ ≡ (π · t)σ′.

Proof

By straightforward induction on the structure of t, using the definitions of π · ,π and σ. The only interesting case is when t ≡π′ · X. Then we need to show π · (π′ · X) ≡ (π′ · X)πσ. Using the definitions of π and σ, we obtain (π′ · X)πσ ≡ (π ◦π′ ◦π-1) · (π · X) for the right-hand-side. By the definition of π · this is equivalent to (π ◦π′ ◦π-1 ◦π) · X, which is equivalent to (π ◦π′) · X by basic permutation group theory. Again by the definition of π · , this is equivalent to π · (π′ · X), which we needed to show. The proof of Xπ ≡ (π · X)σ′ follows similar lines. □

Extend notation for permutation actions π · and π and substitution action σ to assertions A and freshness contexts ∆in a pointwise fashion.

4.2. Inference rules.

Define derivability on freshnesses by:

(#ab)a#bπ-1(a)#X(#X)a#π · X(#[]a)a#[a]ta#t(#[]b)a#[b]ta#t1 · · · a#tn (#f) a#f(t1, . . . , tn)

Here π ≠ Id, and a and b permutatively range over atoms, which means that they represent any two distinct atoms. Write ∆ ⊢T a#t when a#t may be derived from ∆using the signature from T. Say that ∆ entails a#t in T.

Define derivability on equalities by:

(refl)t = tt = u(symm)u = tt = u u = v(tran)t = vt = u(congabs)[a]t = [a]ut = u(congf)f(. . . , t, . . .) = f(. . . , u, . . .)∆πσ(ax∆→t=u)tπσ = uπσ[a#X1, . . . , a#Xn] ∆··· t = u(fr)t = u

Here (fr) is subject to a condition that a ∉t, u, ∆and the square brackets denote discharge of assumptions in natural deduction style [16].

Write ∆ ⊢T t = u when we may derive t = u from ∆, using the signature from theory T and admitting only the axioms it contains. For any assertion A, we may write ∅⊢T A as ⊢T A.

In (ax∆→t=u) the actions π and σ make formal an intuition that in axioms we are supposed to permute atoms and instantiate unknowns. Take e.g. the theory (ΣLAM, {A, B, C}) where A stands for var(a) = var(b), B for λ[a]X = λ[b]Y , and C for a#X →λ[a]X = λ[b]X. Then these derivations

(axA)var(c) = var(a)(axB)λ[b]var(b) = λ[a]var(a)

are valid taking π = (c a) and any σ, and π = (a b) and σ = [var(b)/X, var(a)/Y], respectively. But it is not possible to derive var(a) = var(a) using (axA) because no matter what π we try to use, it must be bijective. Furthermore in

(#ab)a#b(#f)a#var(b)(axC)λ[a]var(b) = λ[b]var(b)a#a(#f)a#var(a)(axC)λ[a]var(a) = λ[b]var(a)

the left derivation is valid but the right one is not, because a#a is not derivable.

With reference to the discussion of π · versus π above, another version of the rule (ax∆→t=u) is possible:

π · ∆σ(ax′ ∆→t=u)π · tσ = π · uσ

however in this case, atoms in the substitution σ are renamed according to π. For example, from an axiom [a]X = [b]X it is immediate that [b]a = [a]a is derivable with (ax) where we choose π = (b a) and σ = [a/X]. It is also derivable with (ax′) but we must choose π = (b a) and σ = [b/X]. We find this version less natural.

Note that we assumed above that theories contain the axiom (perm); we could alternatively add (axperm) as a derivation rule.

We have not set up facilities to allow freshness axioms (ax∆→a#t). Such a thing is possible but we gain no expressivity; the same effect can be obtained by an equality axiom ∆, b#X1, . . . , b#Xn → (b a) · t = t where b is fresh and X1, . . . , Xn are the unknowns mentioned in ∆and t.

(fr) introduces a fresh atom into the derivation. To illustrate the extra power this gives, note that in a theory with an axiom c#X →X = c, we can derive X = Y with (fr), but cannot without it. (fr) guarantees that some atom fresh for X exists. Further examples are derivations of ⊢SUB X[a↦ → var(a)] = X and a#P ⊢FOL P ⊃ (Q ⊃∀[a]P), which arise in the papers dedicated to the theories SUB [12, part 2 of Example 4.1] and FOL [13, 6th derivation of Figure 2].

Here are some derivations in CORE:

(#ab)a#b(#[]b)a#[b]b(#[]a)b#[b]b(axperm)[a]a = [b]ba#X(#[]b)a#[b]X(#[]a)b#[b]X(axperm)[a](a b) · X = [b]X

We may use (axperm) since [a]a ≡ (a b) · [b]b and [a](a b) · X ≡ (a b) · [b]X.

As mentioned before, CORE is a theory of α-equivalence — in the presence of meta-variables (represented by unknowns). It is an interesting algebraic version of work originally presented in nominal unification [27], and this can be made formal:

Theorem 4.5

∆⊢CORE t = u iff ∆⊢t = u holds in the sense of [27, 7].

Proof

The left-to-right direction is by induction on the structure of NA derivations of t = u from ∆, as defined on page 7. The right-to-left direction is by induction on the structure on derivations of ∆ ⊢t = u, as defined in [27, Figure 2] or [7, p.13]. The result follows by detailed calculations. □

4.3. Proof theoretical results.

We naturally extend the meta-level action of permutations to theories: given a theory T = (Σ, Ax), write Tπ for (Σ, Ax π) such that ∆π →tπ = uπ ∈ Ax π if and only if ∆ →t = u ∈ Ax.

Lemma 4.6

If ∆⊢T A then ∆⊢Tπ A.

Proof

By induction on derivations. The only nontrivial case is (ax∆′→t=u), where we need to show that ∆ ⊢Tπ ∆′π′σ implies ∆ ⊢Tπ tπ′σ = uπ′σ. By Lemma 4.3, this is equivalent to showing that

∆⊢Tπ ∆′ππ′◦π-1σ implies ∆⊢Tπ tππ′◦π-1σ = uππ′◦π-1σ.

This follows by (ax∆′π→tπ=uπ) taking permutation π′ ◦π-1 and substitution σ. □

Theorem 4.7

If ∆⊢T A then ∆⊢T π · A.

Proof

By induction on the structure of derivations. We consider the most interesting cases only. Suppose the derivation of ∆ ⊢T A concludes in. . .

(1) (#X). Suppose a#π′ · X is derived from π′-1(a)#X using (#X), where π′ ≠ Id. Then we need to show π(a)#π · (π′ · X). By Lemma 4.1, this is equivalent to π(a)#(π ◦π′) · X.

We continue by case distinction. Suppose π ◦π′ = Id. Then the proof obligation is equivalent to the assumption π′-1(a)#X, since π = π′-1 by basic permutation group theory.1 The result follows.

Now suppose π ◦π′ ≠ Id. Then by (#X) (which may now be applied), the proof obligation follows from (π ◦π′)-1(π(a))#X. Since we also have (π ◦π′)-1(π(a)) = π′-1(a), this is equivalent to the assumption π′-1(a)#X, and again the result follows.

(2) (ax∆′→t=u). Then A is tπ′σ = uπ′σ and ∆ ⊢T ∆′π′σ.

We need to derive π · tπ′σ = π · uπ′σ from ∆. By Lemma 4.2, this is equivalent to (π · tπ′)σ = (π · uπ′)σ. By Lemma 4.4 it suffices to derive tπ′π(σ′ ◦σ) = uπ′π(σ′ ◦σ), where substitution σ′ maps each X ∈∆′, t, u to π · X. By Lemma 4.3, this is equivalent to tπ◦π′(σ′ ◦σ) = uπ◦π′(σ′ ◦σ). Then by (ax∆′→t=u) with permutation π ◦π′ and substitution σ′ ◦σ, this follows from ∆′π◦π′(σ′ ◦σ). Again by Lemmas 4.2, 4.4 and 4.3 this is equivalent to π · ∆′π′σ and we are done since by inductive hypothesis ∆ entails this.

(3) (fr). Then ∆, a#X1, . . . , a#Xn ⊢T A for some a ∉∆, A and we assume the inductive hypothesis of this derivation. If π(a) = a there is no problem since then a ∉∆, π · A and we may extend the derivation with (fr).

However, suppose π(a) ≠ a and so (possibly) a ∈π · A. We observe that the predicate “if the labelled tree Π is a valid derivation of ∆ ⊢T A, then for all permutations π′ there are derivations of ∆ ⊢T π′ · A” has free variables Π, ∆, T, and A.

We now use the principle of logical (FM) equivariance: if an assertion is true of some arguments, then it is also true of those arguments with some atoms permuted providing the axiom of choice is not used (in the cases we are interested in, it is not). For a proof of this beautiful and useful meta-principle see elsewhere [8, 15]. So the predicate above holds of Π(a′ a), ∆(a′ a), T(a′ a), and A(a′ a) and using Lemma 4.6 we deduce the inductive hypothesis of ∆, a′#X1, . . . , a′#Xn ⊢T A for any a′ ∉∆, A, π. Then ∆, a′#X1, . . . , a′#Xn ⊢T π · A and we extend the derivation with (fr) to deduce ∆ ⊢T π · A as required.

□

We may substitute terms for unknowns, provided the substitution on the freshness context is consistent:

Theorem 4.8

If ∆⊢T A then ∆′ ⊢T Aσ for all ∆′ such that ∆′ ⊢T ∆σ.

Proof

We note that the structure of natural deduction derivations is such that the conclusion of one derivation may simply be ‘plugged in’ to an assumption in another derivation if assumption and conclusion are syntactically identical. We also note that the structure of all the rules except for (#X) is such that if unknowns are instantiated by σ, nothing need change. For the case of (#X) we use Theorem 4.7.

□

4.4. Soundness and completeness.

Theorem 4.9 (Soundness).

If ∆⊢T A then ∆|=T A.

Proof

Let M be a model of T. We work by induction on the derivation rules in Subsection 4.2. Most cases are very easy. We just give a sketch:

(#ab) is immediate, since by construction ⟦a⟧M ς= a for any ς. (#f) follows because we assume fM is equivariant. a#[a]x is a basic property of nominal sets [15, Corollary 5.2] and (#[]a) follows. a#x if and only if a#[b]x, and a#π ·x if and only if π-1(a)#x are also basic properties, and (#[]b) and (#X) follow.

For (ax∆→t=u) suppose ⟦∆πσ⟧M ς for any ς. Then π(a)#ς(σ(X)) holds for all a#X ∈ ∆. By logical equivariance then also a#ς′(X) for all a#X ∈ ∆where ς′ is defined as ς′(X) = π-1 · ς(σ(X)) for all X. So ⟦∆⟧M ς′ holds. Since ∆ →t = u is an axiom of T, also ⟦t⟧M ς′ = ⟦u⟧M ς′ holds. Then ⟦tπσ⟧M ς= ⟦uπσ⟧M ς follows by logical equivariance again. □

Given a theory T we construct a term model T of T as follows:

• For each sort τ and n > 0 introduce a term-former dn τ : (n A, . . . , A)τ.

• For each sort T take as TT the set of closed terms of sort T (terms without unknowns) in the enriched signature, quotiented by provable equality, with the permutation action given pointwise.

• For each term-former f take as fT the function defined as

fT (x1, . . . , xn) = {t | ⊢T t = f(t1, . . . , tn), t closed, ti ∈xi}.

We must enrich the signature with the dn τ to ensure that our term model has enough elements. Since term-formers must be interpreted by equivariant functions, the usual method of adding constants c (0-ary term-formers) would add only elements such that ⊢T π · c = c always, which would not suffice. This idea goes back to [9].

It is not hard to prove the definition above well-defined, and that T is an interpretation: that each TT is a nominal set, and that each fT is equivariant.

Lemma 4.10

If a#⟦t⟧T ς then there is some t′ ∈⟦t⟧T ς such that ⊢T a#t′.

This result looks obvious, but it is not: let T have one base sort T and one term-former ι : (A)T. Let it have one axiom ι(a) = ι(b). It is easy to verify that a#⟦ι(a)⟧T ς but a#ι(a) is not derivable. Of course, a#ι(b) and ι(a) = ι(b) are derivable.

Proof

Since a#⟦t⟧T ς we do know that for fresh a′ we have (a′ a) · ⟦t⟧T ς = ⟦t⟧T ς, that is ⊢T (a′ a) · t = t. Take t′ ≡ (a′ a) · t. □

Lemma 4.11

The term model T of T is a model.

Proof

We show that if ∆ →t = u is an axiom of T then ⟦∆→t = u⟧T ς is valid for any ς. Let X1, . . . , Xn be the unknowns mentioned in ∆ →t = u and suppose that ς is such that ai#ς(Xi) for all ai#Xi ∈ ∆. Use Lemma 4.10 to choose ti ∈ς(Xi) such that ⊢T ai#ti for each ai#Xi ∈∆. By Theorem 4.8 taking σ(Xi) ≡ti we have that ⊢T tσ = uσ is derivable, because it is an instance of an axiom. By construction ⟦t⟧T ς = ⟦tσ⟧T ς — ς is irrelevant on the right since tσ is closed — and similarly ⟦u⟧T ς = ⟦uσ⟧T ς. So ⟦t⟧T ς = ⟦u⟧T ς.

□

Theorem 4.12 (Completeness).

If ∆|=T t = u then ∆⊢T t = u.

Proof

By assumption we have ⟦∆→t = u⟧M ς for any model M of T and any evaluation ς. Let M be T , the term model of T. In order to choose a suitable ς, we introduce the following:

• Let A be the set of atoms mentioned anywhere in ∆, t, and u.

• Let X1 τ1, . . . , Xn τn be the set of unknowns mentioned anywhere in ∆, t, or u, (not just in ∆!) in some arbitrary order.

• For each 1 ≤i ≤n let Ai be the set of all atoms a ∈A such that a#Xi τi ∉∆.

• For each 1 ≤i ≤n let σ(Xi τi) ≡ dniτi (a1, . . . , ani) where Ai = {a1, . . . , ani}.

Assume the dniτi we use are distinct; if necessary we ‘pad’ with extra fresh atoms, or use a richer term model with extra d.

Let ς map Xi τi to ⟦σ(Xi τi)⟧T ς, for 1 ≤i ≤n. By construction ⟦∆⟧T ς, so by assumption ⟦t⟧T ς = ⟦u⟧T ς, and by definition this means that tσ = uσ is derivable. This derivation can be transformed rule by rule into a derivation of ∆ ⊢T t = u, since the only freshnesses and equalities we can assert of the d are those we can also assert of the X — the only complication is when perhaps for some fresh b we use a freshness derivation to derive b#vσ for some fresh b; then we modify the derivation to use (fr) instead. □

Completeness only holds for equalities, not freshnesses:

Theorem 4.13

∆⊢T t = u and ∆⊢T a#t does not necessarily imply ∆⊢T a#u. As a corollary ∆|=T a#t need not imply derivability of ∆⊢T a#t.

Proof

A counterexample is the theory mentioned in Lemma 4.10. □

So by Theorem 4.9 if a#t is derivable then a#⟦t⟧M ς is valid, but the converse of Theorem 4.9 does not hold for freshness assertions. Recall that a#⟦t⟧M ς when Иb.(b a) · ⟦t⟧M ς= ⟦t⟧M ς. To express this semantic notion we check derivability of ∆, b#X1, . . . , b#Xn ⊢T (b a) · t = t for some b ∉t and the Xi the unknowns in ∆ and t. The complexity of deciding this depends on T, as it should.

5. Conclusions and related work

Nominal terms model the instantiation behaviour of meta-variables, e.g. in informal notation instantiating t to x in λx.t yields λx.x, reflected formally in this paper by the syntactic equality (λ[a]X)[var(a)/X] ≡λ[a]var(a). NA stakes a claim to nominal terms as a logical system, and the support for binding allows us to reflect binding in logic in a direct fashion. Other work [12, 13, 11] demonstrates the flavour of nominal algebra applied to specific theories.

Nominal Algebra has similarities to Nominal Logic [23]: our (axperm) and (fr) correspond to axioms (F1) and (F4) of Nominal Logic. These come from the shared semantics in nominal sets, as ‘normal’ algebra shares a sets semantics with first-order logic. There are also significant differences. Nominal logic does not use nominal terms (they came later [26]) and freshness contexts, and this difference shows in the technical detail; for example the treatment of freshness in Nominal Logic is semantic in the sense of the discussion following Theorem 4.13 [23, p.175 ‘Freshness’].

Since the conception of Nominal Algebra, Pitts and Clouston have been developing ‘Nominal Equational Logic’ (publication in preparation at the time of writing). This seems closer than Nominal Algebra to being the pure equality fragment of Nominal Logic. In particular it features a semantic, not syntactic, treatment of freshness.

The theory of contexts [20] can be used to axiomatise systems with binding. So, differently, can higher-order algebra [19]. So indeed can simply-typed λ-calculus [22, Figures 6 and 7]. These systems are different and for different purposes but they share a core which is in essence simply-typed λ-terms up to αβ-equivalence. As for nominal terms this richer term-language gives more expressivity which can be used to give stronger axioms. However, these approaches do not (so we argue) accurately capture our intention for the meta-variables t and φ when we write ‘λa.t’ or ‘∀a.φ’; Nominal Algebra was designed with that in mind from the start. Also, moving to higher orders engenders certain computational difficulties [17].2 Still, quotienting terms by αβ is convenient, as exploited by theorem-provers such as Isabelle — but this is not algebra for binding any more than quotienting arithmetic terms by arithmetic equality constitutes an algebra for arithmetic. Syntactic equivalence and provable equality — two quite different things!

Lambda-abstraction algebras [24] and cylindric algebras [5, 1] algebraically axiomatise systems with binding (λ-calculus and first-order predicate logic). They indirectly code freshness conditions; e.g. the use of Sy z ξ throughout rule (β6) just before definition 3 in [24, page 203] obtains the effect of ‘y is not free in ξ’. Likewise the use of ciy throughout rule C4 in [5, page 29] in example 13 obtains the effect of ‘i not free in y’. In this connection we should also mention polyadic algebras; a brief but clear discussion of the design of these and related systems is in [4, Appendix C]. These systems are effective for their particular application but we see Nominal Algebra as parameterising the ‘binding’ part as an orthogonal structure (and of course in a new way involving the nominal terms). Sun has authored [25] a monumental study in doing just that; it is way ahead of us in terms of pure algebra.3 That work is be based on a functional semantics for binding [25, Definition 2.2.3], whereas we work according to the (relatively newer) nominal semantics, which is decidedly non-functional; currently the two strands are essentially independent and it remains to see what ideas might flow between them.

Combinators [3] make binding of variables ‘go away’. Algebras over (untyped) combinators can then express first-order predicate logic [2]. This interesting and difficult enterprise is more foundational/semantic than proof-theoretic/algebraic (the flavour of this work), because the extreme self-reflective power of untyped combinators makes contradictions hard to avoid.

References

[1] H. Andréka, I. Németi, and I. Sain. Algebraic logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 2, pages 133–249. Kluwer, 2001.

[2] H. Barendregt, W. Dekkers, and M. Bunder. Completeness of two systems of illative combinatory logic for first-order propositional and predicate calculus. Archive für Mathematische Logik, 37:327–341, 1998.

[3] H. P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.), volume 103 of Studies in Logic and the Foundations of Mathematics. North-Holland, 1984.

[4] W. J. Blok and D. Pigozzi. Algebraizable logics. Memoirs of the A.M.S., 77(396), 1989.

[5] S. Burris and H. Sankappanavar. A Course in Universal Algebra. Springer, 1981. Available online.

[6] P. Cohn. Universal Algebra. Harper and Row, New York, 1965.

[7] M. Fernández and M. J. Gabbay. Nominal rewriting. Information and Computation, 2005. In press.

[8] M. J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.

[9] M. J. Gabbay. Fresh logic. Journal of Logic and Computation, 2006. In press.

[10] M. J. Gabbay and J. Cheney. A sequent calculus for nominal logic. In Proc. 19th IEEE Symposium on Logic in Computer Science (LICS 2004), pages 139–148. IEEE Computer Society, 2004.

[11] M. J. Gabbay, A. Marin, and S. Rota Bulò. A nominal semantics for simple types. Submitted STACS’07, 2006.

[12] M. J. Gabbay and A. Mathijssen. Capture-avoiding substitution as a nominal algebra. In ICTAC’2006, 2006.

[13] M. J. Gabbay and A. Mathijssen. One-and-a-halfth-order logic. In PPDP ’06: Proceedings of the 8th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming, pages 189–200, New York, NY, USA, 2006. ACM Press.

[14] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax involving binders. In 14th Annual Symposium on Logic in Computer Science, pages 214–224. IEEE Computer Society Press, Washington, 1999.

[15] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13(3–5):341–363, 2001.

[16] W. Hodges. Elementary predicate logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 1–131. Kluwer, 2001.

[17] D. Leivant. Higher order logic. In D. Gabbay, C. Hogger, and J. Robinson, editors, Handbook of Logic in Artificial Intelligence and Logic Programming, volume 2, pages 229–322. Oxford University Press, 1994.

[18] J. Loeckx, H. Ehrich, and M. Wolf. Specification of Abstract Data Types. Wiley, 1996.

[19] K. Meinke. Universal algebra in higher types. Theoretical Computer Science, 100(2):385–417, june 1992.

[20] M. Miculan. Developing (meta)theory of lambda-calculus in the theory of contexts. ENTCS, 1(58), 2001.

[21] D. Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Extensions of Logic Programming, 475:253–281, 1991.

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

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

[24] A. Salibra. On the algebraic models of lambda calculus. Theoretical Computer Science, 249(1):197–240, 2000.

[25] Y. Sun. An algebraic generalization of frege structures - binding algebras. Theoretical Computer Science, 211:189–232, 1999.

[26] C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. In CSL’03 & KGC, volume 2803 of LNCS, pages 513–527, 2003.

[27] C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. Theoretical Computer Science, 323(1–3):473–497, 2004.

School of Mathematical and Computer Sciences, Heriot-Watt University, Edinburgh EH14 4AS, Scotland, Great Britain

E-mail address: murdoch.gabbay@gmail.com

Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

E-mail address: A.H.J.Mathijssen@tue.nl

Notes

1Composing both sides of π ◦π′ = Id with π-1, we obtain π′ = π-1. Inverting both sides, we obtain π′-1 = π. ↩

2For example unification up to αβ-equivalence is not decidable (restrictions of it are in [21]). Unification up to CORE is decidable [27]. ↩

3Ironically, this paper was published the same year as [14] and several other papers we know of on binding. ↩