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

Stone duality for nominal Boolean algebras with ‘new’: topologising Banonas

Murdoch J. Gabbay, Tadeusz Litak, and Daniela Petrişan

Abstract. We define Boolean algebras over nominal sets with a function-symbol N mirroring the N ‘fresh name’ quantifier. We also define dual notions of nominal topology and Stone space, prove a representation theorem over fields of nominal sets, and extend this to a Stone duality.

1 Introduction

Na.φ(a) means ‘for fresh a, φ(a) holds’. Here a is intended to be an atomic resource: examples are a variable symbol, memory location, channel name, or (in security) nonce.

N is interesting from both a mathematical and computational point of view. It is self-dual (¬Na.φ(a) ⇔Na.¬φ(a)) and this gives a computationally useful some/any property: to prove N we check φ(a) for some fresh name, but we can then use any fresh b. (Definitions below or in [18,14].)

N also appears to be useful. It has been applied to syntax-with-binding [18], resource generation in functional programming [29], local names in incomplete trees [5], π-calculus name-restriction [3], game semantics [1,33], and domains [32]. See Example 3.6 for more discussion.

Proof-theories for N have been suggested [11,15,7,10], but no equational axiomatisation or representation theorem. Nominal domains have been studied, but not topologies. As we shall see, algebra and topology with N are non-trivial and interesting.

In this paper we study Boolean logic with N in nominal sets. We introduce Banonas (Boolean Algebra, NOminal with Na) and nominal Stone spaces, and prove representation and duality theorems.

Stone’s representation does not generalise easily to nominal sets: the ultra-filter lemma breaks down (since a union of finitely-supported sets need not be finitely-supported). To ‘fix’ this, a name-restriction operation seems to be required. So Banonas seem to arise naturally from the proofs: the mathematics leads us to this structure even if we did not start off with it. On that topic, Banonas are also Boolean algebra objects in the category Res of nominal restriction sets considered recently in [26,27]. There seems to be convergence in the recent literature, on name-restriction as an interesting object of study.

One application of Stone duality relates coalgebras for ‘sufficently well-behaved’ functors on sets, with algebras for ‘sufficently well-behaved’ functors on Boolean algebras (definitions in [21]). This allows a uniform construction of logic(s) for coalgebras. So this paper lays the groundwork for a duality-based approach to nominal coalgebraic logic with built-in name generation. Coalgebras on nominal sets do provide a natural semantics for name-passing calculi such as π-calculus (see e.g. [9, Section 1.2] and [30] for information and references). See Example 3.6 and the Conclusions for more discussion of applications.

The results in this paper describe a natural mathematical building-block of inherent mathematical elegance, which seems to arise spontaneously by considering algebra and topology in a ‘nominal’ setting, and with potential practical interest. We discuss further work in the Conclusions.

2 Basic definitions for nominal sets

A nominal set is a ‘set with names’. The notion of a name being ‘in’ an element is given by support supp(x) (Definition 2.7). For more details of nominal sets, see [18,14]. The reader can reasonably think of supp(x) as ‘the free atoms of x’, but without committing to x being syntax—on the contrary, x could have any structure provided it admits a permutation action, and this includes taking powersets as we see later in Section 5.

Definition 2.1

Fix a countably infinite set of atoms A. We use a permutative convention that a, b, c, . . . range over distinct atoms.

Definition 2.2

A (finite) permutation π is a bijection on atoms such that nontriv(π) = {a | π(a) ≠ a} is finite.

Write id for the identity permutation such that id(a) = a for all a. Write π′ ◦π for composition, so that (π′ ◦π)(a) = π′(π(a)). Write π-1 for inverse, so that π-1 ◦π = id = π ◦π-1. Write (a b) for the swapping (terminology from [18]) mapping a to b, b to a, and all other c to themselves, and take (a a) = id.

Definition 2.3

If A ⊆A define fix(A) = {π | ∀a ∈A.π(a) = a}.

Definition 2.4

A set with a permutation action X is a pair (|X|, ·) of an underlying set |X| and a permutation action written π·x which is a group action on |X|, so that id·x = x and π·(π′·x) = (π ◦π′)·x for all x ∈|X| and permutations π and π′.

Say that A ⊆A supports x ∈|X| when ∀π.π ∈ fix(A) ⇒π·x = x. If a finite A supporting x exists, call x finitely-supported.

Definition 2.5

Call a set with a permutation action X a nominal set when every x ∈|X| has finite support. X, Y, Z will range over nominal sets.

Definition 2.6

Call a function f ∈|X| →|Y| equivariant when π·f(x) = f(π·x) for all permutations π and x ∈|X|. In this case write f : X → Y.

Definition 2.7

Suppose X is a nominal set and x ∈|X|. Define the support of x by supp(x) = ⋂{A | A supports x}. Write a#x as shorthand for a ∉ supp(x) and read this as a is fresh for x.

(Commute) x ∧y = y ∧x(Assoc) (x ∧y) ∧z = x ∧(y ∧z)(Huntington) x = ¬(¬x ∧¬y) ∧¬(¬x ∧y)(Swap)Na.Nb.x =Nb.Na.x(Garbage) a#x ⇒Na.x = x(Distrib)Na.(x ∧y) = (Na.x) ∧(Na.y)(SelfDual) ¬Na.x =Na.¬x(Alpha) b#x ⇒Na.x =Nb.(b a)·x
Fig. 1: Axioms of Banonas.
Theorem 2.8

Suppose X is a nominal set and x ∈|X|. Then supp(x) is the unique least finite set of atoms that supports x. (Proofs in [18,14].)

Definition 2.9

Write π|A for the partial function which is π restricted to A.

Corollary 2.10

1. If π(a) = a for all a ∈ supp(x) then π·x = x.

2. If π|supp(x) = π′|supp(x) then π·x = π′·x.

3. a#x if and only if ∃b.b#x ∧ (b a)·x = x.

Proposition 2.11

supp(π·x) = {π(a) | a ∈ supp(x)} (cf. Definition 5.1).

3 Nominal Boolean algebra with N

Definition 3.1

A nominal Boolean algebra with N (with a new-binder) or Banona is a tuple (B, ∧, ¬,N) of a nonempty nominal set B, and equivariant functions (Definition 2.6)

– conjunction ∧ : B × B → B written x ∧y (for ∧(x, y)),

– negation ¬ : B → B written ¬x, and

– new N : A × B → B written Na.x (for N(a, x)),

such that the equalities in Figure 1 hold.

Banonas arise naturally as nominal powersets (Section 5), just as Boolean algebras arise naturally as ‘ordinary’ powersets. For an example consider any (for simplicity) unary predicate P on some syntax, represented as the set of terms of which it is true. Then asserting that P holds ‘if a is fresh’ (as in ‘if a is fresh then for all u, t[a::=u] = t) is an instance of Na.P.

Remark 3.2

(Commute), (Assoc), and (Huntington) axiomatise Boolean algebra (see, e.g., [25]). We write ⊥ for x ∧¬x, x ∨y for ¬(¬x ∧¬y), and x ≤y for x ∧y = x. With these definitions, the axioms ensure standard properties of Boolean algebra including: absorption, distributivity, and poset properties.

N is a name-restriction operation in the sense of [26, Definition 1] since it satisfies (Swap), (Garbage), and (Alpha). So each Banona has an underlying nominal restriction set. (Distrib), (SelfDual) imply that ∧ and ¬ are morphisms in the category Res [27], thus Banonas are Boolean algebra objects in Res.

All these axioms are valid properties of the N-quantifier [18] (Definition 4.3, in this paper). See Theorem 5.9 for a proof.1

Lemma 3.3

If x ≤y then Nb.x ≤Nb.y. In words: N is monotone.

Proof

By x ≤y we mean x ∧y = x. So Nb.(x ∧y) =Nb.x. We use (Distrib).

Lemma 3.4

a#Na.x. As a corollary, Na.Na.x =Na.x.

Proof

Choose a fresh b (so b#x). By (Alpha) Na.x =Nb.(b a)·x. By equivariance Nb.(b a)·x = (b a)·Na.x. By Proposition 2.11 a#(b a)·Na.x. The result follows. The corollary follows using (Garbage).

Definition 3.5

Call a function f ∈|B′| →|B| a (Banona) morphism when:

f(x ∧y) = f(x) ∧f(y) f(¬x) = ¬f(x) f(Na.x) =Na.f(x) f(π·x) = π·f(x)

Write BAnona for the category of Banonas and Banona morphisms.

Example 3.6

– Call a set X ⊆A cofinite when A \ X is finite. The set of finite or cofinite sets of atoms is a Banona where conjunction and negation are interpreted as intersection and complement respectively, and Na.X = X \ {a} if X is finite, and Na.X = X ∪{a} if X is cofinite (cf. Example 5.3). In Section 5 we exhibit a class of Banonas given by nominal powersets; The results in Section 6 prove this class complete for all possible examples in a certain formal sense.

– The discrete nominal restriction set B = {True, False} from [27, Section 3.2] is also a Banona.

– The term model for nominal logic constructed by Cheney and Urban in [8] is a Banona where we interpret conjunction as conjunction, negation as negation, and Na.φ as ‘for fresh a, φ’ as specified in Figure 9 of [8].

– Predicates of Cardelli and Gordon’s ambient calculus up to logical equivalence form a (very richly-structured) Banona where N is interpreted as N as defined in Definition 4.3 of [6] (see [6, Corollary 4.5]).

– Formulas of hybrid logic with downarrow ↓x.φ (see, e.g, [2]) up to logical equivalence, where atoms serve as world variables, permutation is syntactic permutation and freshness is ‘not free in’, are a Banona where N maps to ↓. A broader class of Banonas (with additional operators) can be constructed by adapting an abstract equational class of algebras including sets denotations for hybrid logic defined in [22] to nominal setting.

4 Equivariance and the N-quantifier

Our reasoning can be formalised in Zermelo-Fraenkel set theory with atoms (ZFA). Nominal sets can be implemented in ZFA sets such that nominal sets map to equivariant elements (elements with empty support) and the permutation action maps to ‘real’ permutation of atoms in the model [14, Subsection 9.3]. From this, follow short and elegant proofs of theorems about equivariance and support. For more details, see [14, Section 4].

Definition 4.1

If x denotes a list x1, . . . , xn, write π·x for π·x1, . . . , π·xn.

Theorem 4.2

Suppose φ(x) is a ZFA predicate on variables included in x. Suppose χ(x) is a ZFA function specified using a list of variables included in x. Then we have the following principles:

1. Equivariance of predicates. φ(x) ⇔φ(π·x).2

2. Equivariance of functions. π·χ(x) = χ(π·x).

3. Conservation of support. If x denotes elements with finite support then supp(χ(x)) ⊆ supp(x1)∪· · · ∪supp(xn).

Definition 4.3

Write Na.φ(a) for ‘{a | ¬φ(a)} is finite’.

Remark 4.4

We can read N as ‘for all but finitely many a’, ‘for fresh a’, or ‘for new a’. This is like a ‘for most’ quantifier [35], and is a generalised quantifier [19, Section 1.2.1]. However, N over nominal sets satisfies additional properties:

Theorem 4.5

Suppose φ(z, a) is a predicate on variables included in z, a.3 Suppose z denotes elements with finite support. Then the following are equivalent:

∀a.(a ∈A ∧a#z) ⇒φ(z, a)Na.φ(z, a) ∃a.a ∈A ∧a#z ∧φ(z, a)

This is the some/any property: to prove a N-quantified property we test it for one fresh atom; we may then use it for any fresh atom.

5 The nominal powerset as an algebra

Definition 5.1

Define the nominal powerset pow(X) by:

– U ⊆|X| has the pointwise action π·U = {π·x | x ∈U}.

– |pow(X)| is the set of finitely-supported U ⊆|X|.

Definition 5.2

If X∈|pow(X)| then define na.X = {x |Nb.(b a)·x ∈X}.

Example 5.3

|pow(A)| is the set of finite and cofinite subsets of atoms and na.X is characterised on pow(A) by:

– If X is finite then na.X = X\{a}.

– If X is cofinite then na.X = X∪{a}.

In the case of X ∈|pow(X)| for general X, the elements added/removed by n are called crucial elements in [13, Subsection 4.2] and correspond to adding/removing elements from a-orbits [13, Subsection 4.1]. In fact na. is equal to the operation X−a described in [13, Subsection 4.2], used there for different purposes.

Remark 5.4

Definition 5.2 is the sets-based interpretation of N which we will prove sound and complete for the axioms in Definition 3.1. Visibly, n is defined using N. Conversely, Na.φ(a) if and only if a ∈ na.{x ∈A | φ(x)}.

Lemma 5.5

If X ∈|pow(X)| then na.X ∈|pow(X)|.

Proof

By Theorem 4.2 supp(na.X) ⊆ supp(X) ∪{a}.

Lemma 5.6

1. If a#X then na.X = X.

2. na.(X ∩Y ) = (na.X) ∩(na.Y ).

3. na.(|X| \ X) = |X| \ na.X.

As a corollary, if X ⊆Y then na.X ⊆ na.Y .

Proof (Sketch).

Suppose a#X. Choose x∈|X| and fresh b (so b#x, X). By the pointwise action and Corollary 2.10 (b a)·x∈X if and only if x∈X.

Choose x ∈|X| and fresh b (so b#x, X, Y). Then (b a)·x ∈X ∩Y if and only if (b a)·x ∈X and (b a)·x ∈Y .

Choose x ∈|X| and fresh b (so b#x, X, |X|\X). Then (b a)·x ∈|X| \ X if and only if (b a)·x ∉X.

Lemma 5.7

b#X implies na.X = nb.(b a)·X. As a corollary, a#na.X.

Proof (Sketch).

Choose fresh b (so b#X) and x∈|X|. By the pointwise action (b c)·x∈(a b)·X if and only if x∈(b c)·(a b)·X. By Corollary 2.10 (b c)·(a b)·X = (a c)·X. The result follows.

Lemma 5.8

na.nb.X = nb.na.X.

Proof

By routine calculations using the fact that (a′ a)·(b′ b)·x = (b′ b)·(a′ a)·x.

Theorem 5.9

(pow(X), ∩, |X|\-, n) is an object of BAnona.

Proof

Validity of (Commute), (Assoc), and (Huntington) is by routine sets calculations. Validity of (Alpha) and (Swap) is by Lemmas 5.7 and 5.8. Validity of (Garbage), (Distrib), and (SelfDual) is by Lemma 5.6.

Proposition 5.10

If a#x then x ∈X if and only if x ∈ na.X.

Proof

Choose b fresh (so b#x, X). By definition x ∈ na.X when (b a)·x ∈X. By Corollary 2.10 (b a)·x = x. The result follows.

6 A representation theorem

We introduce n-filters of a Banona B (Definition 6.1). We define the canonical extension B• as the nominal powerset of its maximal n-filters (Definition 6.20). Finally we prove B isomorphic to a subalgebra of B• (Theorem 6.25).

6.1 n-Filters

Definition 6.1

An n-filter is a finitely-supported subset p ⊆|B| such that:

1. ⊥∉p 2. ∀x, y.(x ∈p ∧y ∈p) ⇔(x ∧y ∈p) 3.Na.∀x.x∈p ⇒Na.x∈p
Remark 6.2

The first two conditions of Definition 6.1 are as standard. The third condition corresponds to a property of nominal sets (Proposition 5.10) in a sense made formal in the proof of Lemma 6.12.

Definition 6.3

Given C ⊆A and x ∈|B| define NC.x by:

NC.x =Nc1 . . .Ncn.x where C ∩supp(x) = {c1, . . . , cn}

By assumption x has finite support so C ∩supp(x) is finite even if C is not. Also, by (Swap) the order of the ci does not matter.

Lemma 6.4

Suppose C ⊆A and a ∈C. Then:

1.NC.⊥= ⊥ 2.NC.(x ∧y) = (NC.x) ∧NC.y 3.NC.x =NC.Na.x
Proof

1. Follows from (Garbage). 2. Follows from (Distrib),(Swap) and (Garbage).

3. If a#x then x =Na.x by Lemma 3.4. If a ∈ supp(x), then a ∈C ∩ supp(x) and the result follows from the second part of Lemma 3.4 and (Swap).

Definition 6.5

Suppose z ∈|B|. Write C = A \ supp(z). Define z↑ by

z↑= {x | z ≤NC.x}.
Remark 6.6

The standard definition of z↑ is {x | z ≤x}. This definition seems to not work, and proofs based on it break. We can view Definition 6.5 as elaborating the standard definition to respect property 3 of Definition 6.1.

Lemma 6.7

If z∈|B| and z ≠ ⊥ then supp(z↑) ⊆ supp(z) and z↑ is an n-filter.

Proof

Write C = A \ supp(z). The first part is by Theorem 4.2 and the fact that supp(C) = supp(z).4 That z↑ is an n-filter follows from Lemma 6.4.

Definition 6.8

Call an n-filter p ⊆|B| maximal when for all n-filters p′ ⊆|B| if p ⊆p′ then p′ = p.

We now show that every n-filter is contained in a maximal n-filter (Theorem 6.17). We use Zorn’s lemma, but this requires a bound on support. Thus we consider n-filters maximal amongst n-filters with smaller support. Surprisingly, these n-filters are the maximal n-filters (Lemma 6.13).

Lemma 6.9

Suppose q is an n-filter and suppose x ∉q. Write q′ for the set q′ = {z | z ∨x ∈q}. Then q′ is an n-filter.

Proof

That ⊥∉q′ and ∀z1, z2.(z1 ∈q′ ∧z2 ∈q′) ⇔ (z1 ∧z2 ∈q′) is routine. Na.∀z.(z ∈q′ ⇒Na.z ∈q′) follows from the fact that if a is fresh (so a#q, x) then by (Garbage), (SelfDual), and (Distrib), Na.(z ∨x) = (Na.z) ∨Na.x = (Na.z) ∨x.

Proposition 6.10

q is maximal if and only if ∀x.¬x ∈q ⇔x ∉q.

Proof

For q maximal, suppose ¬x ∉q and x ∉q. By Lemma 6.9, q′ = {z | z∨x∈q} is an n-filter. Also, ¬x∈q′ whereas ¬x∉q, so q ⊊q′, contradicting maximality of q. The rest follows from conditions 1 and 2 of Definition 6.1.

Lemma 6.11

If q is an n-filter and C=A\supp(q) then so is q′ = {z |NC.z∈q}.

Proof

Follows from Lemma 6.4.

Lemma 6.12

Suppose q is an n-filter such that for all n-filters q′, q ⊆q′ and supp(q′) ⊆ supp(q) imply q = q′. Then Na.(∀x.x ∈q ⇔Na.x ∈q).

Proof

The left-to-right implication is condition 3 of Definition 6.1. Write C = A \ supp(q). The set q′ = {z |NC.z ∈q} (Definition 6.3) is an n-filter by Lemma 6.11. By condition 3 of Definition 6.1 q ⊆q′, by Theorem 4.2 supp(q′) ⊆ supp(q), hence q′ = q (note that supp(C) = supp(q)). The right-to-left implication follows.

Lemma 6.13

q is a maximal n-filter if and only if for all n-filters q′, q ⊆q′ and supp(q′) ⊆ supp(q) imply q = q′.

Proof

The left-to-right implication is trivial. Now suppose q is maximal amongst n-filters with smaller support. By Proposition 6.10 it suffices to show that ¬x ∈q if and only if x ∉q.

¬x ∈q and x ∈q is impossible by conditions 1 and 2 of Definition 6.1.

Now suppose ¬x ∉q and also x ∉q. Write C = A \ supp(q) and x′ =NC.x. By definition, (SelfDual), and Lemma 6.12 x′ ∉q and ¬x′ ∉q.

By Lemma 6.9, q′ = {z | z ∨x′ ∈q} is an n-filter. Also, ¬x′ ∈q′ whereas ¬x′ ∉q, so q ⊊q′. By Theorem 4.2 supp(q′) ⊆ supp(q). This contradicts the existence of x.

Definition 6.14

Given a nominal set X, call Y ⊆|X| bounded-supported when ⋃{supp(x) | x ∈Y } is finite.

Remark 6.15

By [14, Theorem 2.29] if Y is bounded-supported then Y is finitely-supported and supp(Y ) = ⋃{supp(x) | x ∈Y }. See also [32, Definition 3.4.2.3] and subsequent discussion.

Lemma 6.16

Consider a nominal set X and ≤ a partial order on X (≤ need not be equivariant, but when we use this in Theorem 6.17, it will be). If every chain C ∈ pow(X) has an upper bound b(C) with supp(b(C)) ⊆ supp(C) then for every x ∈|X| the set x◦= {y ∈|X| | y ≥x, supp(y) ⊆ supp(x)} has a maximal element.

Proof

By Remark 6.15 every chain C in x◦ is finitely-supported and supp(C) ⊆ supp(x). Then C has an upper bound b(C) such that supp(b(C)) ⊆ supp(C). Thus b(C) ∈x◦. The result follows using Zorn’s lemma for x◦.

Theorem 6.17

For every n-filter p, there is a maximal n-filter q with p ⊆q.

Proof

If C is a finitely-supported chain in the nominal set of n-filters on B ordered by subset inclusion, then an upper bound for C is defined by ⋃ C = {x | ∃p′ ∈C.x ∈p′}, and by Theorem 4.2 supp(⋃ C) ⊆ supp(C). By Lemma 6.16 the set p◦ of n-filters p′ such that p ⊆p′ and supp(p′) ⊆ supp(p) has a maximal element q with respect to inclusion.

Then q is a maximal amongst n-filters with smaller support and p ⊆q. Indeed, if q′ is such that q ⊆q′ and supp(q′) ⊆ supp(q) then q′ ∈p◦, hence q = q′. By Lemma 6.13 q is a maximal n-filter (Definition 6.8).

6.2 The canonical extension -•

Definition 6.18

Define points(B) = {p ⊆|B| | p is a maximal n-filter}.

Lemma 6.19

points(B) is a nominal set.

Proof

By Theorem 4.2 the predicate ‘p is a maximal n-filter’ holds if and only if the predicate ‘π·p is a maximal n-filter’ holds.

Definition 6.20

Define the canonical extension B•=(pow(points(B)), ∧, ¬,N):

A ∧B = A ∩B ¬A = |B•| \ ANa.A = na.A

A and B will range over elements of |B•|. (na.A defined in Definition 5.2.)

Proposition 6.21

B• is a nominal Boolean algebra with N.

Proof

From Theorem 5.9.

Definition 6.22

Define a map -• ∈|B| →|B•| by:

x• = {p ∈|points(B)| | x ∈p}

We need to check that -• does map to |B•|. It suffices to show that supp(x•) ⊆ supp(x). This follows by Theorem 4.2.

Proposition 6.23

-• is an arrow in BAnona (Definition 3.5).

Proof

Equivariance is by Theorem 4.2.

1. (x ∧y)• = {p ∈|points(B)| | x ∧y ∈p}. By assumption in Definition 6.1 x ∧y ∈p if and only if x ∈p and y ∈p and it follows that (x ∧y)• = x• ∧y•.

2. (¬x)• = {p ∈|points(B)| | ¬x ∈p}. We use Proposition 6.10.

3. (Na.x)• = {p ∈|points(B)| |Na.x ∈p}. Suppose p ∈ (Na.x)•. Choose fresh a′ (so a′#x, x•, p). By (Alpha) Na.x =Na′.(a′ a)·x. By definition Na′.(a′ a)·x ∈ p. By Lemma 6.12 (a′ a)·x ∈p. By definition p ∈ (a′ a)·x•. By Proposition 5.10 p ∈ na′.(a′ a)·x•. By Lemma 5.7 na′.(a′ a)·x• = na.x•.

Remark 6.24

Note the ‘internal’ and ‘external’ names in part 3 of the proof of Proposition 6.23. We begin with a ‘internally restricted’ with N. We use (Alpha) to apply an ‘external’ renaming of a to ‘externally’ fresh a′. This is picked up by the definition of n-filter and Proposition 5.10 moves to the ‘external’ N.

In part 3 a#x implies a#x•—but this does not matter; we choose a fresh.

Theorem 6.25

-• is injective, thus B is isomorphic to a subalgebra of B•.

Proof

Suppose x ∈|B| and y ∈|B| are distinct. Suppose without loss of generality that x ≰y, so that x ∧¬y ≠ ⊥. By Lemma 6.7 (x ∧¬y)↑ is an n-filter. By Theorem 6.17 there exists a point q containing (x ∧¬y)↑. Then x ∧¬y ∈q, hence q ∈x• and q ∉y•. The result follows by Proposition 6.23.

7 Nominal Stone duality

We introduce nominal topological spaces. As expected, the carrier set and topology are nominal sets and open sets are finitely-supported (this can restrict— sometimes considerably; see Example 5.3—the available open sets). Thus we cannot take arbitrary unions of open sets, but only finitely-supported unions. Banonas correspond to nominal topological spaces with additional properties which we call nominal Stone spaces with N (Definition 7.4). To the new-binder N corresponds on the topological side the semantic n (Definition 5.2); elements correspond to clopen sets (sets that are both open and closed), so clopens must be closed under n. The notion of compactness must also be subtly tweaked to take into account the role of n. We conclude with a duality theorem.

Definition 7.1

A nominal topological space T is a pair (|T|, OT) of a carrier nominal set |T| and equivariant set of open sets OT⊆pow(|T|) such that:

– ∅∈OT and |T| ∈OT

– U ∈OT ∧V ∈OT implies U ∩V ∈OT.

– U ∈ pow(OT) implies ⋃ U ∈OT; we call this a finitely-supported union.

Call equivariant f ∈|T1|→|T2| continuous when V ∈OT2 implies f -1(V )∈OT1. Write nTop for the category of nominal topological spaces and continuous maps.

Definition 7.2

Call U n-closed when Na.∀U.(U ∈U ⇒ na.U ∈U). Call U ∈ pow(OT) a cover when ⋃ U = |T|. If U is a cover and is n-closed then call U an n-cover. Call T n-compact when every n-cover has a finite subcover.

Lemma 7.3

If U ∈ pow(OT) is finite then Na.∀U.U ∈U ⇒a#U. As a corollary, T is n-compact when every n-cover has an n-closed finite subcover.

Proof

For finite U, supp(U) = ⋃{supp(U) | U ∈U} [14, Theorem 2.29]. We use part 1 of Lemma 5.6.

Definition 7.4

Call U closed when |T|\U ∈OT, and clopen when U is open and closed. Call T totally separated when for every x, y ∈|T| there is a clopen U with x ∈U and y ∉U.

Say T is a nominal topological space with N when na.U ∈OT for every clopen U.5 Write nTopN for the full subcategory of nTop on T with N.

A nominal Stone space with N is a totally separated n-compact nominal topological space with N. Write nStoneN for the full subcategory of nTopN on nominal Stone spaces with N.

Definition 7.5

Given B in BAnona define F (B) in nTop by:

– |F (B)| = points(B) (Definition 6.18).

– OF (B) is the closure of {x• | x ∈|B|} (Definition 6.22) under finitely-supported unions. So U ∈OF (B) when ∃M ∈ pow(|B|).U = ⋃{x• | x ∈M}.

Given f : B→B′ in BAnona define F(f) : F (B′)→F (B) by F(f)(p) = f -1(p).

F (B) is indeed a nominal topological space, for if U ∈ pow(OF (B)) then ⋃ U = ⋃{x• | ∃U∈U.x•⊆U} is open. The next lemma shows that F(f) is well-defined.

Lemma 7.6

For f : B → B′ in BAnona and p ∈ points(B′), f -1(p) ∈ points(B).

Proof

It is not hard to use the homomorphism properties of f and Theorem 4.2 to show that f -1(p) is an n-filter. Using Proposition 6.10 ¬x ∈f -1(p) if and only if x ∉f -1(p), and it follows that f -1(p) is also maximal.

Lemma 7.7

If U is n-closed then so is V = {x• | ∃U∈U.x• ⊆U}.

Proof

Choose b fresh (so b#U, V). If x• ∈V then x• ⊆U ∈U. By Lemma 5.6 nb.(x•) ⊆ nb.U and by assumption nb.U ∈U.

Proposition 7.8

F (B) is totally separated and n-compact.

Proof

Consider distinct p, q ∈|F (B)|. Without loss of generality take x ∈p \ q. By Definition 6.20, p ∈x• and q ∉x•. So x• is an open set separating p and q. By Proposition 6.10 points(B) \ x• = (¬x)•, so x• is also closed.

Consider an n-cover U ∈ pow(OF (B)). It suffices to find a finite subcover of V = {x• | ∃U∈U.x• ⊆U}, since for every x• ∈V there exists x• ⊆U ∈U.

Write X = ⋀fin{x′ | ∃x.¬x≤x′ ∧x•∈V} where ⋀fin denotes closure under finite intersections. So V has a finite subcover if and only if ⊥∈X. By Proposition 6.23 and Lemma 7.7 X satisfies conditions 2 and 3 of Definition 6.1. If X satisfied also ⊥∉X then X would be an n-filter; by Theorem 6.17 X ⊆p for some point p; it would follow that p ∉⋃ V, a contradiction. Therefore ⊥∈X.

Lemma 7.9

If U ∈F (B) is clopen then U = x• for some x ∈|B|.

Proof

By assumption U = ⋃{x• | x• ⊆U} and |F (B)| \ U = ⋃{x• | x• ⊆ |F (B)| \ U}. It follows that {x• | x• ⊆U ∨x• ∩U = ∅} covers F (B). This cover is also n-closed, by part 1 and the corollary in Lemma 5.6. So it has a finite subcover by Proposition 7.8. The result follows by Proposition 6.23.

Proposition 7.10

F is a functor from BAnona to nStoneopN.

Proof

If U∈OF(B) is clopen then U=x• for some x∈|B| by Lemma 7.9. By part 3 of Proposition 6.23 na.(x•)=(Na.x)•∈OF(B). By Proposition 7.8 F(B) is a nominal Stone space with N.

Consider f : B → B′ in BAnona. By Lemma 7.6 F(f) maps |F(B′)| to |F(B)|. Continuity of F(f) follows using the fact that F(f)-1(x•) = (f(x))•.

Definition 7.11

Map T ∈ nStoneN to a G(T) ∈ BAnona defined by:

– |G(T)| = {U ∈OT | U is clopen}.

– ∧, ¬, and N are interpreted as intersection, complement, and n.

Given f : T → T′ in nStoneN define G(f) : G(T′) →G(T) by G(f)(U) = f -1(U).

Lemma 7.12

G is a functor from nStoneopN to BAnona.

Proof

If U is clopen then na.U is open by Definition 7.4. na.U is closed from the fact that na.(|T| \ U) = |T| \ na.U, immediate from part 3 of Lemma 5.6. It is routine to check that G(T) is an object of BAnona.

Consider continuous f : T → T′. If U is clopen then so is f -1(U). G(f) is equivariant because f is, and preserves intersections and complements. Given U ∈OT′ a clopen, G(f)(na.U) = na.G(f)(U) follows from Definitions 5.2 and 7.11 and the equivariance of f. Thus G(f) is a morphism in BAnona.

Lemma 7.13

Suppose T ∈ nTopN is n-compact and U is a finitely-supported set of closed sets with the finite intersection property: the intersection of finitely many sets in U is nonempty. Then Nb.∀U.U∈U ⇒ nb.U∈U implies ⋂ U ≠ ∅.

Theorem 7.14

G defines an equivalence between BAnona and nStoneopN.

Proof

We use [23, Theorem 1, Chapter IV, Section 4].

G is essentially surjective on objects. Given B in BAnona and x ∈|B|, x• ∈OF (B) is clopen. By Lemma 7.9 if U ∈OF (B) is clopen then U = x• for some x ∈|B|. By Theorem 6.25, the map -• defines an isomorphism between GF (B) and B.

G is faithful. From the fact that nominal Stone spaces are totally separated.

G is full. Given T, T′ in nStoneN and u : G(T′) →G(T) in BAnona we construct a morphism v : T → T′ in nStoneN, such that G(v) = u.

Define αT: T →FG(T) by t↦ →{U ∈G(T) | t ∈U}.

αT is well defined: αT(t) is supported by supp(t), and is indeed a maximal n-filter. We must also show that a#t and U ∈α(t) imply na.U ∈α(t); this follows from Proposition 5.10.

That αT is injective follows, as in for the classical Stone duality, from the totally separatedness of the spaces. For surjectivity, consider a maximal n-filter U ∈FG(T). This is a finitely-supported set of closed sets of T with the finite intersection property such that U ∈U and b#U imply nb.U ∈U. By Lemma 7.13 there exists some t ∈⋂ U ⊆|T|. That U = α(t) follows from maximality of U. αT and α-1 T are continuous. The proof is analoguous to the classical case, see [4].

We set v = α-1 T′ ◦F(u) ◦αT. This is continuous and G(v) = u.

8 Conclusions

We have seen how Boolean algebras in nominal sets naturally support an operation corresponding to the N-quantifier from [18]. So nominal sets are sufficiently different that this paper is not a pure ‘replay’ of the standard proofs—on the contrary, the fine detail is extremely subtle.

In particular, as an empirical observation the proofs seem to ‘want’ N. They break for nominal Boolean algebras without N (remove N and its axioms from Definition 3.1, presumably to obtain a Bano). Without N we would need to use finitely-supported filters, rather than n-filters. But then the proofs of Lemma 6.13 and Theorem 6.17 would break. Banonas seem to be natural; a representation theorem for Banos is future work.

That our results are consistent with the full structure of classical logic (if we want it) is interesting, but note that our proofs do not depend on it. We believe that they should adapt to subreducts (e.g., Heyting algebras, distributive lattices) and expansions with operations/operators. A concrete example of a Hanona (Heyting algebras with N; weaken the initial three axioms appropriately and add Na.(x⇒y) = (Na.x)⇒(Na.y) in Figure 1) is a intuitionistic hybrid logic with ↓ (cf. Example 3.6 and [28]). We believe that, modulo an easy syntactic translation, the logic LG by Tiu [31] is another.

On related work, Sections 5.3 and 5.4 of [34] outline the Jónsson-Tarski representation of Boolean algebras with operators, i.e., normal modalities. Does it suffice to consider N and permutations as families of modalities? Yes, but this paper gives a strictly stronger result. Nominal sets have an ‘external’ theory of names and freshness given by permutations and support (extending the ‘external’ set intersection and complement corresponding to ‘internal’ conjunction and negation of Boolean algebra). An ‘internal’ notion of freshness is x =Na.x; a similar idea is used in cylindric/polyadic algebras and Lambda Abstraction Algebras [24]. Our challenge has been to make ‘internal’ and ‘external’ theories coincide for boolean connectives, and to represent N as n (Definition 5.2), permutation as permutation, and to satisfy e.g. a#x implies x =Na.x.

Some speculation on computational applications: fresh names create symmetry, since ‘it does not matter’ which are chosen. It is known by those working in satisfiability checkers (e.g. SMT solvers) that symmetry is important in reducing search space. Domain-specific symmetries are a major theme. Banonas and nominal sets give an explanatory foundation for freshly generated resources—a fairly common case. We might use this to extend problem input languages with explicit statements of these symmetries, thus improving and automating their recognition. Then this paper guarantees that a satisfiability checker based on nominal sets and n would be adequate for any classical logic with a N.

On pow(A), n is the unique function satisfying the axioms of Definition 3.1. We do not know whether n is uniquely determined by those axioms on arbitrary nominal powersets. (The map X↦ → if a#X then X else ∅ fails (SelfDual).)

Nominal powersets (Definition 5.1) have rich structure. In particular, function-symbols could be added to reflect freshness X#a = {x ∈X | a#x} and name-restriction νa.X = {π·x | x ∈X, π ∈ fix(supp(X)\{a})} [16]. We do not believe that these can be represented using n. Note that n does not equal ν. For instance X ⊆νa.X is true, but X ⊆ na.X is false in general.6 So there are two natural name-restrictions on nominal sets. Nominal sets have been around for a decade, but their structure is not fully understood. For future work we hope to characterise the structure of nominal powersets, as complete atomic Boolean algebras do for ‘ordinary’ powersets.

References

1. Samson Abramsky, Dan R. Ghica, Andrzej S. Murawski, C.-H. Luke Ong, and Ian D. B. Stark. Nominal games and full abstraction for the nu-calculus. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), pages 150–159. IEEE Computer Society Press, 2004.

2. Carlos Areces and Balder ten Cate. Hybrid logics. In P. Blackburn, J. van Benthem, and F. Wolter, editors, Handbook of Modal Logic. Elsevier, 2007.

3. Jesper Bengtson and Joachim Parrow. Formalising the π-calculus using nominal logic. In FOSSACS’07: Proceedings of the 10th international conference on Foundations of software science and computational structures, pages 63–77. Springer, 2007.

4. S. Burris and H. Sankappanavar. A Course in Universal Algebra. Graduate texts in mathematics. Springer, 1981.

5. Luís Caires and Luca Cardelli. A spatial logic for concurrency (part I). Information and Computation, 186(2):194–235, 2003.

6. Luca Cardelli and Andrew Gordon. Logical properites of name restriction. In Typed Lambda Calculi and Applications, volume 2044 of Lecture Notes in Computer Science, pages 46–60. Springer, 2001.

7. James Cheney. A simpler proof theory for nominal logic. In FoSSaCS, volume 3441 of Lecture Notes in Computer Science, pages 379–394. Springer, 2005.

8. James Cheney and Christian Urban. Nominal logic programming. ACM Transactions on Programming Languages and Systems (TOPLAS), 30(5):1–47, 2008.

9. C. Cirstea, A. Kurz, D. Pattinson, L. Schröder, and Y. Venema. Modal logics are coalgebraic. The Computer Journal, 2009.

10. Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic. In Principles and Practice of Declarative Programming, 12th International ACM SIGPLAN Symposium (PPDP 2010), 2010.

11. Murdoch J. Gabbay. Fresh Logic. Journal of Applied Logic, 5(2):356–387, June 2007.

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

13. Murdoch J. Gabbay. A study of substitution, using nominal techniques and Fraenkel-Mostowski sets. Theoretical Computer Science, 410(12-13):1159–1189, March 2009.

14. Murdoch J. Gabbay. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic, 2011. In press.

15. Murdoch J. Gabbay and James Cheney. A Sequent Calculus for Nominal Logic. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), pages 139–148. IEEE Computer Society, July 2004.

16. Murdoch J. Gabbay and Vincenzo Ciancia. Freshness and name-restriction in sets of traces with names. In Foundations of software science and computation structures, 14th International Conference, 2011.

17. Murdoch J. Gabbay and Aad Mathijssen. Nominal universal algebra: equational logic with names and binding. Journal of Logic and Computation, 19(6):1455–1508, December 2009.

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

19. Edward Keenan and Dag Westerståhl. Generalized quantifiers in linguistics and logic. In J. Van Benthem and A. Ter Meulen, editors, Handbook of Logic and Language, pages 837–894. Elsevier, 1996.

20. Alexander Kurz and Daniela Petrişan. On universal algebra over nominal sets. Mathematical Structures in Computer Science, 20:285–318, 2010.

21. Alexander Kurz and Jirí Rosický. The Goldblatt-Thomason theorem for coalgebras. In Till Mossakowski, Ugo Montanari, and Magne Haveraaen, editors, CALCO, volume 4624 of Lecture Notes in Computer Science, pages 342–355. Springer, 2007.

22. Tadeusz Litak. Algebraization of hybrid logic with binders. In Renate Schmidt, editor, Relations and Kleene Algebra in Computer Science, volume 4136 of Lecture Notes in Computer Science, pages 281–295. Springer Berlin / Heidelberg, 2006.

23. Saunders Mac Lane. Categories for the Working Mathematician, volume 5 of Graduate Texts in Mathematics. Springer, 1971.

24. Giulio Manzonetto and Antonino Salibra. Applying universal algebra to lambda calculus. Journal of Logic and computation, 20(4):877–915, August 2010.

25. William McCune. Solution of the Robbins problem. Journal of Automated Reasoning, 19:263–276, 1997. 10.1023/A:1005843212881.

26. Andrew M. Pitts. Nominal system T. In Proceedings of the 37th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2010), pages 159–170. ACM Press, January 2010.

27. Andrew M. Pitts. Structural recursion with locally scoped names. submitted for publication, September 2010.

28. Jason Reed. Hybridizing a logical framework. Electronic Notes in Theoretical Computer Science, 174(6):135 – 148, 2007. Proceedings of the International Workshop on Hybrid Logic (HyLo 2006).

29. Mark R. Shinwell, Andrew M. Pitts, and Murdoch J. Gabbay. FreshML: Programming with Binders Made Simple. In Proceedings of the 8th ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), volume 38, pages 263–274. ACM Press, August 2003.

30. Sam Staton. Name-passing process calculi: operational models and structural operational semantics. Technical Report UCAM-CL-TR-688, University of Cambridge, Computer Laboratory, June 2007.

31. Alwen Tiu. A logic for reasoning about generic judgments. Electronic Notes in Theoretical Computer Science, 174(5):3–18, 2007.

32. David C Turner. Nominal Domain Theory for Concurrency. PhD thesis, University of Cambridge, 2009.

33. Nikos Tzevelekos. Full abstraction for nominal general references. In Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), pages 399–410. IEEE Computer Society Press, 2007.

34. Yde Venema. Algebras and coalgebras. In P. Blackburn, J. Van Benthem, and P. Wolter, editors, Handbook of modal logic, volume 3 of Studies in logic and practical reasoning, chapter 6. Elsevier, 2007.

35. Dag Westerståhl. Quantifiers in formal and natural languages. In Gabbay and Günthner, editors, Handbook of Philosophical Logic, volume 4 of Synthèse, chapter 2, pages 1–131. Reidel, 1989.

Acknowledgements. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.

Notes

1 The axioms are nominal algebraic because of their freshness side-conditions. In a sense which has been made formal, nominal algebra is an equational logic [17,12,20], and is sound and complete for nominal sets. ↩

2 x must contain all the variables mentioned in the predicate. It is not the case that a = a if and only if a = b—but it is the case that a = b if and only if b = a. ↩

3 φ has to be expressible in the language of ZFA set theory without choice. Every φ used in this paper will satisfy this property. ↩

4 In fact it can be proved by a further calculation that supp(z↑) = supp(z). ↩

5 We need not require na.U to be open for all U; of course, we do not forbid it either. ↩

6 The ν of [26], which Pitts calls name-restriction, is purely axiomatic and does not commit to any concrete representation. ↩