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

Stone duality for first-order logic: a nominal approach to logic and topology

Murdoch J. Gabbay∗

Heriot-Watt University, Scotland, UK

http://www.gabbay.org.uk

Abstract

What are variables, and what is universal quantification over a variable?

Nominal sets are a notion of ‘sets with names’, and using equational axioms in nominal algebra these names can be given substitution and quantification actions. So we can axiomatise first-order logic as a nominal logical theory.

We can then seek a nominal sets representation theorem in which predicates are interpreted as sets; logical conjunction is interpreted as sets intersection; negation as complement. Now what about substitution; what is it for substitution to act on a predicate-interpreted-as-a-set, in which case universal quantification becomes an infinite sets intersection?

Given answers to these questions, we can seek notions of topology. What is the general notion of topological space of which our sets representation of predicates makes predicates into ‘open sets’; and what specific class of topological spaces corresponds to the image of nominal algebras for first-order logic?

The classic Stone duality answers these questions for Boolean algebras, representing them as Stone spaces. Nominal algebra lets us extend Boolean algebras to ‘FOL-algebras’, and nominal sets let us correspondingly extend Stone spaces to ‘∀-Stone spaces’. These extensions reveal a wealth of structure, and we obtain an attractive and self-contained account of logic and topology in which variables directly populate the denotation, and open predicates are interpreted as sets rather than functions from valuations to sets.

Keywords: Stone duality, nominal sets, first-order logic, topology, variables.

1 Introduction

We are familiar with Boolean algebras being sets with conjunction and negation actions satisfying certain axioms.1 We are also familiar with the fact that powersets naturally have a Boolean algebra structure, given by interpreting conjunction as sets intersection and negation as sets complement.

Using nominal techniques—specifically nominal sets and nominal algebra—we can axiomatise substitution and first-order logic (just as traditionally we axiomatise Boolean algebra, groups, rings, fields, etc.). This has been done in [12, 14, 15]. The next question is this:

Can we extend the Stone duality theorem from Boolean algebras to the nominal algebras, and to some hitherto unknown class of nominal topological spaces?

(For an accessible introduction to classical Stone duality see [29].) If we can answer this question, then we also obtain a nominal representation of first-order logic. This nominal representation is different because there are no Tarski-style valuations; a variable populates the denotation directly and substitution acts on variables directly in that denotation.

This is a very different view of logical meaning than the one which the reader is most likely accustomed to. We semi-formally sketch the usual representations of first-order logic, side-by-side:

Predicate Boolean Alg. Usual semantics FO logic Nominal semanticsφ ∧ψ ⟦φ⟧ ∩⟦ψ⟧ λς.(⟦φ⟧ς ∩⟦ψ⟧ς) ⟦φ⟧ ∩⟦ψ⟧¬φ U\⟦φ⟧ λς.(U\⟦φ⟧ς) U\⟦φ⟧∀a.φ n/a λς. ⋂x∈U ⟦φ⟧ς[a::=x]⋂x∈U ⟦φ⟧[a↦→x]

Here U is some ‘domain of points’. Boolean algebra does not have a universal quantification so the semantics for ∀a.φ is not applicable. The usual semantics for first-order logic interprets universal quantification, but at the price of introducing valuations ς; thus the structure of the sets interacts only indirectly with the universal quantifier.

In this paper, we show how to interpret predicates without valuations, so that universal quantification is just an infinite intersection. This is sketched in the rightmost column. Of course, to do that, we need to interpret X[a↦→x] where X is a set. We do this too.

For the reader’s convenience we map out where the key definitions are given:

• The logical counterpart to the representation above is the notion of FOL-algebra. This is algebraic in the same way that Boolean algebras are algebraic; however, it uses nominal techniques to axiomatise (abstractly) substitution and binding. See Definition 3.3.

• The topological counterparts to the representation above are notions of topological space and of Stone space with extra structure. These are σ-topological space (Definition 6.1) and ∀-Stone space (Definition 6.18).

• The sets structure which mediates between the logical and topological views is the notion of a σ-powerset. This is the structure that answers the question ‘What is it to substitute x for a in a set X?’. See Definition 4.10.

Thus, we prove a Stone duality between a nominal algebra axiomatisation of first-order logic (FOL-algebras), and a notion of topological space (∀-Stone spaces). The proofs reveal a wealth of interesting structure and give a sense in which variables really can directly inhabit denotations in logic and topology.

Structure of the paper

• Section 2 develops some necessary background on nominal sets and the N-quantifier.

• Section 3 introduces FOL-algebras, which are the nominal algebraic structure corresponding to first-order logic; the presentation here is derived from that in [15].

• Section 4 introduces a notion of ‘powerset with substitution action’ and proves that this is an instance of a FOL-algebra: conjunction is interpreted as sets intersection, negation as sets complement, substitution as a pointwise operation involving a subsidiary notion of amgis-algebra, and universal quantification is interpreted as an infinite sets intersection (just as we would hope).

• Section 5 adapts notions of filters, points, and the canonical extension from Boolean algebra to FOL-algebra. This is where a FOL-algebra gets injected into a suitable σ-powerset.

• Finally Section 6 constructs and proves a Stone duality result.

We conclude with the Conclusions.

We include an indicative map of the key constructions in this paper, in roughly decreasing order of technical complexity:

Definition 5.25 FOL-algebra ⇒ σ-topological spaceDefinition 6.20 σ-topological space ⇒ FOL-algebraTheorem 4.21σ-algebra ⇒ FOL-algebra (by powersets)Proposition 5.21 FOL-algebra ⇒σ-algebra (by set of points)Example 3.2 Concrete σ-algebrasExample 4.3 Further concrete σ-algebras

2 Background on nominal techniques

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.8). For more details of nominal sets, see [18, 10]. Here we just give necessary background information.

The reader with a category-theory background can read this section as stating that we work in the category of nominal sets, or equivalently in the Schanuel topos (more on this in [25, Section III.9], [22, A.21, page 79], or [10, Theorem 9.14]). The reader with a sets background can read this section as stating that our constructions can be carried out in Fraenkel-Mostowski set theory (a discussion of this sets foundation, tailored to nominal techniques, can be found in [10, Section 10]). In both cases the underlying idea is ‘sets indexed over names’ (called urelemente or atoms in the sets literature).

The reader not interested in foundations should simply note that previous work [18, 10] has shown that—merely by taking the apparently inconsequential first step of assuming names as primitive entities in Definition 2.1, instead of taking them to be for instance numbers—we obtain a remarkable clutch of definitions and results, notably Theorems 2.9, 2.13 and 2.16.

It turns out that these properties are just what we need next, in Section 3.

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.

Example 2.6

• A is a nominal set where π·a = π(a).

• If X and Y are nominal sets then X×Y is a nominal set with underlying set {(x, y) | x ∈|X|, y ∈|Y|} and action π·(x, y) = (π·x, π·y).

• If X is a set with a permutation action then powerset(X) is a set with a permutation action with underlying set {U | U ⊆|X|} and the pointwise action π·U = {π·u | u ∈U}.

• If X is a nominal set then pow(X) (the nominal powerset) is a nominal set, with underlying set those U ∈|powerset(X)| that are finitely-supported with the pointwise action. As the name suggests, the nominal powerset is indeed the powerset object in the category of nominal sets [10, Lemma 9.10].

Definition 2.7

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

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.

Theorem 2.9

Suppose X is a nominal set and x ∈|X|. Then supp(x) is the unique least finite set of atoms that supports x.

Proof

See part 1 of Theorem 2.21 of [10].End of proof

Definition 2.10

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

Corollary 2.11

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.

Proof

From part 2 of Theorem 2.21 of [10].End of proof

Proposition 2.12

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

Our reasoning can be formalised in first-order logic with axioms of set theory with atoms (the name for this is Zermelo-Fraenkel with atoms, or ZFA, though in fact we will work more specifically in its extension Fraenkel-Mostowski sets). Because one atom will do as well as any other, we obtain Theorem 2.13, from which concisely follow results about equivariance and support.2 See e.g. proofs of Lemmas 4.20, 5.8, 5.17, and Propositions 5.24 and 5.29.

Theorem 2.13

If x is a list x1, . . . , xn, write π·x for π·x1, . . . , π·xn. Suppose φ(x) is a first-order logic predicate with free variables x. Suppose χ(x) is a function specified using a first-order predicate with free variables x. Then we have the following principles:

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

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

3. Conservation of support. If x denotes elements with finite support

then supp(χ(x)) ⊆supp(x1)∪· · · ∪supp(xn).
Proof

See Theorem 4.4, Corollary 4.6, and Theorem 4.7 from [10].End of proof

Definition 2.14

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

Remark 2.15

We can read N as ‘for all but finitely many a’, ‘for fresh a’, or ‘for new a’. It captures a generative aspect of names, that for any x we can find plenty of atoms a such that a ∉ supp(x). N was designed in [18] to model the quantifier being used when we informally write “rename x in λx.t to be fresh”, or “emit a fresh channel name” or “generate a fresh memory cell”.

N is a ‘for most’ quantifier [30], and is a generalised quantifier [23, Section 1.2.1]. But importantly, N over nominal sets satisfies the some/any property that to prove a N-quantified property we test it for one fresh atom; we may then use it for any fresh atom. This is Theorem 2.16, which we use implicitly when later we choose a ‘fresh atom’ without proving that it does not matter which one we choose. We will use this all the time; see e.g. proofs of Corollary 4.13, Proposition 4.18, and Lemma 6.9.

Theorem 2.16

Suppose φ(z, a) is a predicate with free variables z, a.4 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)
Proof

See Theorem 6.5 from [10] or Proposition 4.10 from [18].End of proof

(Subid) x[a↦→a] = x(Sub#) a#x ⇒ x[a↦→u] = x(Subα) b#x ⇒ x[a↦→u] = ((b a)·x)[b↦→u](Subσ) a#v ⇒ x[a↦→u][b↦→v] = x[b↦→v][a↦→u[b↦→v]]
Figure 1: Nominal algebra axioms for σ-action
(Commute) x ∧y = y ∧x(Assoc) (x ∧y) ∧z = x ∧(y ∧z)(Huntington) x = ¬(¬x ∧¬y) ∧¬(¬x ∧y)
Figure 2: Axioms for Boolean algebra

3 FOL-algebra

3.1 The definitions: termlike sigma-algebra and FOL-algebra

We introduce the notions of termlike σ-algebra (sigma-algebra) and FOL-algebra.

A termlike σ-algebra generalises the notion of ‘a set of terms’.5 That is, we assume a set, and an action from that set to itself with (nominal algebra) axioms insisting that it ‘be a substitution’. What we do not assume is that this set is a set of terms, or even of syntax; and the action does not actually have to be a syntactic substitution action. It might be that this is so (part 3 of Example 3.2) or it might not (part 6 of Example 3.2).

Likewise a FOL-algebra generalises the notion of ‘a set of predicates’. We assume a set, and actions for substitution of elements of the termlike σ-algebra, and for conjunction, negation, and quantification, satisfying certain axioms. What the underlying representation of this set and these actions is, may be unspecified.

Definition 3.1

A termlike σ-algebra is a tuple U = (|U|, ·, sub, atm) where:

• (|U|, ·) is a nominal set; we may write this just U;

• an equivariant substitution action sub : U × A × U →U, written infix v[a↦→u]; and

• an equivariant injection atm : A →U, usually written invisibly (so we write atm(a) just as a),

such that the equalities of Figure 1 hold.

Example 3.2

1. The set of atoms A is a termlike σ-algebra where atm(a) = a and a[a↦→x] = x and

b[a↦→x] = b.

2. The set A ∪{∗} is a termlike σ-algebra where atm(a) = a, a[a↦→x] = x, b[a↦→x] = b, and ∗[a↦→x] = ∗.

3. First-order syntax generated by the grammar r, s ::= a | f(r, . . . , r) for f drawn from some set of function symbols, is a termlike σ-algebra with atm(a) = a and r[a↦→s] is equal to r with a replaced by s. This is, of course, where we got the name ‘termlike’ from.

4. Predicates of first-order logic over a first-order syntax are not a termlike σ-algebra. This is because there are no predicate variables or substitution for predicates. (They are however an instance of the more general notion of not-necessarily-termlike σ-algebra; see Subsection 4.1.)

5. Predicates of System F [19] do form a termlike σ-algebra, since they have predicate variables and substitution for predicates.

6. The set of finite sets of atoms is a termlike σ-algebra where:

• atm(a) = {a}.

• X[a↦→Y ] = X if a ∉X.

• X[a↦→Y ] = (X\{a}) ∪Y if a ∈X.

(Sub∧) (x ∧y)[a↦→u] = (x[a↦→u]) ∧(y[a↦→u])(Sub¬) (¬x)[a↦→u] = ¬(x[a↦→u])(Sub∀) b#u ⇒ (∀b.x)[a↦→u] = ∀b.(x[a↦→u])
Figure 3: Nominal algebra axioms for σ interacting with FOL
(∀α) b#x ⇒ ∀a.x = ∀b.(b a)·x(∀E) ∀a.x ≤x(∀∧) ∀a.(x ∧y) = (∀a.x) ∧(∀a.y)(∀∨) a#y ⇒ ∀a.(x ∨y) = (∀a.x) ∨y
Figure 4: Nominal algebra axioms for ∀
Definition 3.3

Suppose U = (|U|, ·, sub, atm) is a termlike σ-algebra. A FOL-algebra over U is a tuple B = (|B|, ·, ∧, ¬, U, sub, ∀) where (|B|, ·) is a nonempty nominal set which we may write just B, and equivariant functions (Definition 2.7)

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

• negation ¬ : B →B written ¬x,

• substitution sub : B × A × U →B, and

• forall ∀ : A × B →B written ∀a.x (for ∀(a, x)),

such that the equalities in Figures 1, 2, 3, and 4 hold.

For the rest of this paper unless otherwise stated we fix some termlike σ-algebra U. u and v will range over elements of |U|.

Notation 3.4

We may write:

• ⊥ for x ∧¬x (for some fixed but arbitrary x),

• ⊤ for ¬⊥,

• x ∨y for ¬(¬x ∧¬y),

• ∃a.x for ¬∀a.¬x, and

• x ≤y for x ∧y = x.

(Busid) x[a←↤a] = x(Busσ) a#v ⇒ x[v←↤b][u←↤a] = x[u[b↦→v]←↤a][v←↤b]
Figure 5: Axioms of an amgis-algebra (σ-algebra)

3.2 Basic remarks and properties

The rules (Commute), (Assoc), and (Huntington) are a compact axiomatisation of Boolean algebras [21]. Standard properties of Boolean algebra hold including: absorption, distributivity, and poset properties. Also, x ∧¬x = y ∧¬y for every x and y, thus taking ⊥= x ∧¬x for some x makes sense.

The (Sub∗) group of axioms describes properties of substitution. These are more traditionally treated as facts of a construction involving valuations of atoms to closed elements. Here, they are axiomatised.

The (∀∗) group of axioms describes properties of universal quantification. Again, these properties are axiomatised.

We write down some basic lemmas which will be useful later on in the paper; the proofs are all by routine calculations:

Lemma 3.5

∀a.⊥= ⊥. As a corollary, if a#x then ∀a.x = x.

Proof

By (∀E) ∀a.⊥≤⊥ and by elementary properties of Boolean algebra ⊥≤∀a.⊥. The first part follows. For the corollary we use (∀∨), taking x = ⊥.End of proof

Lemma 3.6

If x ≤y then ∀a.x ≤∀a.y and x[a↦→u] ≤y[a↦→u]. In words: ∀a and [a↦→u] are monotone.

Proof

By x ≤y we mean x ∧y = x. So ∀a.x ≤∀a.y means ∀a.(x ∧y) = ∀a.x. We use (∀∧). The case of [a↦→u] is similar using (Sub∧).End of proof

Lemma 3.7

supp(∀a.x) ⊆ supp(x)\{a}.

Proof

Choose a fresh b (so b#x, ∀a.x). By (∀α) ∀a.x = ∀b.(b a)·x. By equivariance of ∀ : A × B →B, ∀b.(b a)·x = (b a)·∀a.x. By Proposition 2.12 a#(b a)·∀a.x. Thus, a ∉ supp(∀a.x). The result follows using Theorem 2.13.End of proof

Corollary 3.8

1. ∀a.x ≤x[a↦→u].

2. If z ≤x and a#z then z ≤∀a.x.

Proof

For the first part, by (∀E) ∀a.x ≤x. By Lemma 3.6 (∀a.x)[a↦→u] ≤x[a↦→u]. By Lemma 3.7 and (Sub#) we have (∀a.x)[a↦→u] = ∀a.x.

For the second part, we use Lemmas 3.5 and 3.6.End of proof

Proposition 3.9 is an important and a useful sanity check:

Proposition 3.9

∀a.x is a ≤-greatest lower bound for {x[a↦→u] | u ∈|U|}.

Proof

By part 1 of Corollary 3.8 ∀a.x is a lower bound. Now suppose x′ ≤x[a↦→u] for every u ∈|U|. Renaming if necessary using (Subα) suppose without loss of generality that a#x′. By (Subid) taking u = a we have that x′ ≤x. By Lemma 3.6 ∀a.x′ ≤∀a.x. By Lemma 3.5 x′ ≤∀a.x as required.End of proof

Lemma 3.10

a#⊥ and supp(⊥) = ∅.

Proof

By Notation 3.4 ⊥= x∧¬x and by Theorem 2.13 supp(⊥) ⊆ supp(x), so ⊥ is finitely-supported (Definition 2.4).

By basic properties of Boolean algebras x∧¬x = y∧¬y for any other y. In particular by equivariance taking y = π·x we obtain ⊥= x ∧¬x = π·(x ∧¬x) = π·⊥. The result follows using part 3 of Corollary 2.11.End of proof

Proposition 3.11

∀a.∀b.x = ∀b.∀a.x.

Proof

By (∀E) ∀a.∀b.x ≤x. Thus by Lemma 3.6 ∀b.∀a.∀a.∀b.x ≤∀b.∀a.x. Now by Lemma 3.7 and part 3 of Theorem 2.13 b ∉ supp(∀a.∀a.∀b.x) and b ∉ supp(∀a.∀b.x). Thus by Lemma 3.5 ∀b.∀a.∀a.∀b.x = ∀a.∀b.x. It follows that ∀a.∀b.x ≤∀b.∀a.x. By a symmetric argument ∀b.∀a.x ≤∀a.∀b.x, and we are done.End of proof

3.3 Morphisms

Definition 3.12

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

f(x ∧y) = f(x) ∧f(y) f(¬x) = ¬f(x) f(x)[a↦→u] = f(x[a↦→u])f(∀a.x) = ∀a.f(x) f(π·x) = π·f(x)

Write FOLalg for the category of FOL-algebras and morphisms between them.

We conclude with a simple lemma:

Lemma 3.13

If f : B →B′ is a morphism then f(⊥) = ⊥.

Proof

By Notation 3.4 ⊥ is sugar for x ∧¬x (for some choice of x). By the morphism properties, f(x ∧¬x) = f(x) ∧¬f(x). The result follows.End of proof

4 The sigma-powerset as a model of first-order logic

In this section we construct a notion of nominal powerset-with-substitutions. We call this a σ-powerset (Definition 4.10). In the representation theorem of Section 5, what we construct will be a σ-powerset.

4.1 sigma-algebra and amgis-algebra

σ-algebras (sigma-algebras) generalise termlike σ-algebras from Definition 3.1. σ-algebras (amgis-algebras) are a kind of dual to σ-algebras. Why these two notions? The reasons will become clear as we conduct our proofs but here we can note the following sketch; this does not adhere exactly to the proofs which follow, but it captures something of their structure and flavour: If U is a termlike σ-algebra then its powerset will naturally have the structure of an σ-algebra over U. Furthermore, the powerset of its powerset will regain a σ-algebra structure over U. So, σ arises from the fact that in ‘powerset of X’, the X is in a negative position.

Definition 4.1 (σ-algebra).

Suppose U = (|U|, ·, sub, atm) is a termlike σ-algebra. A σ-algebra over U is a tuple X = (|X|, ·, sub) of:

• A nominal set (|X|, ·) which we may write just as X; and

• an equivariant substitution action sub : X × A × U →X, written infix x[a↦→u];

such that the equalities in Figure 1 hold.

Remark 4.2

Definitions 4.1 and 3.1 are similar. In the termlike σ-algebra, x and u are drawn from the same set |U| when we write x[a↦→u]; in the case of Definition 4.1, u is still drawn from |U| but x is drawn from a possibly different set |X|.

Example 4.3

• Predicates of first-order logic (part 4 of Example 3.2) are a σ-algebra, where U is terms and X is predicates. They are not termlike.

• Given σ-algebras X and Y over a termlike σ-algebra U, the nominal set |X| × |Y| with the pointwise action (x, y)[a↦→u] = (x[a↦→u], y[a↦→u]) for x ∈||X|| and y ∈||Y||, is a σ-algebra. Write this just X × Y. In particular, if U is a termlike σ-algebra then U × U is a σ-algebra, but not a termlike one.

• A similar story can be told for disjoint sum X + Y.

Further exploration of the structure of σ-algebras is deferred to a later paper.

Definition 4.4 (σ-algebra).

Suppose U = (|U|, ·, sub, atm) is a termlike σ-algebra (Definition 3.1). A σ-algebra (spoken: amgis-algebra) over U is a tuple P = (|P|, ·,σ, U) of an underlying nominal set (|P|, ·) which we may write just P, and an amgis-action σ : |P| × A × |U| →|P| written infix p[u←↤a], such that the equalities of Figure 5 hold.

We construct an example of an σ-algebra. We will use Definition 4.5 in Subsection 5.3.

Definition 4.5

Suppose that X = (|X|, ·, sub) is a σ-algebra over a termlike σ-algebra U = (|U|, ·, sub, atm) (Definition 4.1). Give finitely-supported subsets X ⊆|X| the pointwise action

X[u←↤a] = {x | x[a↦→u] ∈X}.
Lemma 4.6

Definition 4.5 determines an σ-algebra.

Proof

We verify the two properties in Figure 5:

• Property (Busid). We reason as follows:

X[a←↤a] = {x | x[a↦→a] ∈X} (Subid) = {x | x ∈X} = X.

• Property (Busσ). The proof is similar, using (Subσ). Suppose a#v. We reason as follows:

x ∈X[v←↤b][u←↤a] ⇔x[a↦→u][b↦→v] ∈X Definition 4.5⇔x[b↦→v][a↦→u[b↦→v]] ∈X (Subσ), a#v⇔x ∈X[u[b↦→v]←↤a][v←↤b] Definition 4.5End of proof

We conclude with another important pointwise action:

Definition 4.7

Suppose P = (|P|, ·,σ, U) is an σ-algebra over a termlike σ-algebra U. Suppose X ⊆|P|. Define the pointwise permutation and σ-actions by:

π·X = {π·x | x ∈X} X[a↦→u] = {p | p[u←↤a] ∈X}

For Lemmas 4.8 and 4.9 we continue the notation of Definition 4.7, so that in particular X and Xi range over subsets of |P|.

Lemma 4.8

(⋂i Xi)[a↦→u] = ⋂i(Xi[a↦→u]) and (⋃i Xi)[a↦→u] = ⋃i(Xi[a↦→u]).

Proof

For the first part we note that p ∈ (⋂i Xi)[a↦→u] if and only if ∀i.p[u←↤a] ∈Xi if and only if p ∈⋂(Xi[a↦→u]). The second part is similar.End of proof

Lemma 4.9

(|X|\X)[a↦→u] = |X| \ (X[a↦→u]).

Proof

By a routine argument on sets like that the proof of Lemma 4.8.End of proof

4.2 pow σ(P) is a sigma-algebra

Continuing the notation from the previous subsection, suppose P = (|P|, ·,σ, U) is an σ-algebra over a termlike σ-algebra U. We fix P for the rest of this section.

Definition 4.10

Define an algebra powσ(P) = (|powσ(P)|, ·, sub) by setting |powσ(P)| to be the set of U ⊆|P| with permutation action π·U and substitution action U[a↦→u] from Definition 4.7 such that:

1. U has finite support.

2.Na.∀u∈|U|.U[a↦→u] = U.

3. For every a, Nb.∀u∈|U|.U[a↦→u] = ((b a)·U)[b↦→u].

Remark 4.11

Some comments on Definition 4.10:

•N is the new-quantifier and is defined in Definition 2.14. It means ‘for all fresh / for all but finitely many’.

• We will show later that P is a σ-algebra (Proposition 4.14) and indeed is a FOL-algebra (Theorem 4.21).

• (|powσ(P)|, ·) is equal to pow((|P|, ·)); the nominal powerset of finitely-supported subsets of |P| with the pointwise action defined in Example 2.6.

We first prove that |powσ(P)| is closed under the substitution action; this is Corollary 4.13 and it uses the substitution lemma for powσ(P):

Lemma 4.12

Suppose U ∈|powσ(P)| and u, v ∈|U|. Then

a#v implies U[a↦→u][b↦→v] = U[b↦→v][a↦→u[b↦→v]].
Proof

We reason as follows:

U[a↦→u][b↦→v] = {p | p[v←↤b][u←↤a] ∈U} Definition 4.7= {p | p[u[b↦→v]←↤a][v←↤b] ∈U} (Busσ)= U[b↦→v][a↦→u[b↦→v]] Definition 4.7End of proof
Corollary 4.13

If U is in |powσ(P)| then so is U[a↦→u].

As a corollary, in Definition 4.10, |powσ(P)| is closed under the substitution action from Definition 4.7.

Proof

By construction U[a↦→u] ⊆|P|, so we now check the three properties listed in Definition 4.10. It is convenient to use condition 2 of Definition 4.10 and rename to assume without loss of generality that a#u, v, b, b′.

• Finite support of U[a↦→u] is immediate from Theorem 2.13.

• For fresh b (so b#U, u), U[a↦→u][b↦→v] = U[a↦→u]. We reason as follows:

U[a↦→u][b↦→v] = U[b↦→v][a↦→u[b↦→v]] Lemma 4.12, a#v= U[b↦→v][a↦→u] (Sub#), b#u= U[a↦→u] Defn. 4.10 cond. 2, b#U

• For fresh b′ (so b′#U, u, v) U[a↦→u][b↦→v] = ((b′ b)·(U[a↦→u]))[b′↦→v]. We reason as follows, where we choose a′ and b′ fresh (so a′#U, u, v and b′#U, u, v):

U[a↦→u][b↦→v] = ((a′ a)·U)[a′↦→u][b↦→v] C 3 Def. 4.10, a′#U, u= ((a′ a)·U)[b↦→v][a′↦→u[b↦→v]] Lemma 4.12, a′#v= ((a′ a)·U)[b↦→v][a′↦→((b′ b)·u)[b′↦→v]] (Subα), b′#u= (((b′ b)◦(a′ a))·U)[b′↦→v][a′↦→((b′ b)·u)[b′↦→v]] C 3 Def. 4.10, b′#U, v= (((b′ b) ◦(a′ a))·U)[a′↦→(b′ b)·u][b′↦→v] Lemma 4.12, a′#v= ((b′ b)·(((a′ a)·U)[a′↦→u]))[b′↦→v] Pt 2 Thm. 2.13= ((b′ b)·(U[a↦→u]))[b′↦→v] C 3 Def. 4.10, a′#U, uEnd of proof

Recall from Definition 4.10 the definition of powσ(P), from Definition 4.1 the definition of a σ-algebra, and from Definition 4.7 the pointwise substitution action U[a↦→u]. Then:

Proposition 4.14

powσ(P) is a σ-algebra under the pointwise substitution action.

Proof

By Corollary 4.13 the substitution action does indeed map to |powσ(P)| so it remains to check validity of the axioms (Subid) to (Subσ) from Definition 4.1. Given the maths we already have, this is not hard: Axiom (Subid) is by an easy calculation using the pointwise action and (Busid). Axioms (Sub#) and (Subα) are conditions 2 and 3 of Definition 4.10. Axiom (Subσ) is Lemma 4.12.End of proof

4.3 pow σ(P) and quantification

Now we are able to exhibit universal quantification as an infinite intersection, and existential quantification as an infinite union.

Suppose P = (|P|, ·,σ, U) is an σ-algebra over a termlike σ-algebra U.

Definition 4.15

If X ∈|powσ(P)| then define:

all a.X = ⋂u∈|U| X[a↦→u]exist a.X = ⋃u∈|U| X[a↦→u]

In Definition 4.15 exist could be obtained from all by dualising with sets complement. However, it seems easier to just treat both quantifiers in parallel.

Lemma 4.16

Suppose X ∈|powσ(P)| and v ∈|U|. Suppose a#v. Then:

1. (all a.X)[b↦→v] = all a.(X[b↦→v]).

2. (exist a.X)[b↦→v] = exist a.(X[b↦→v]).

Proof

Suppose a#v. We unpack Definition 4.10 and reason as follows:

all a.(X[b↦→v]) = ⋂u∈|U|(X[b↦→v][a↦→u]) Def. 4.10, Cor. 4.13= ⋂u(X[a↦→u][b↦→v[a↦→u]]) Lemma 4.12= ⋂u(X[a↦→u][b↦→v]) (Sub#), a#v= (⋂u X[a↦→u])[b↦→v] Lemma 4.8= (all a.X)[b↦→v] Def. 4.10

The case of exist a is similar.End of proof

Lemma 4.17

Suppose X ∈|powσ(P)|. Then

b#X implies all a.X = all b.(b a)·X and exist a.X = exist b.(b a)·X

As a corollary, a#all a.X and a#exist a.X.

Proof

The corollary follows by part 3 of Corollary 2.11. For the first part, we reason as follows:

all a.X = ⋂{X[a↦→u] | u∈|U|} Definition 4.15= ⋂{((b a)·X)[b↦→u] | u∈|U|} Condition 3 of Def. 4.10= all b.(b a)·X Definition 4.15

Again, the case of exist a is similar.End of proof

Proposition 4.18

Suppose X ∈|powσ(P)|. Then all a.X, exist a.X ∈|powσ(P)|.

Proof

We need to check the three conditions of Definition 4.10. Let Q represent either all or exist. Then:

1. Finite support is by Theorem 2.13.

2. Suppose b is fresh (so b#X) and suppose v ∈|U|. Using Lemma 4.17 suppose without loss of generality that a#v. Then we can reason as follows:

(Q a.X)[b↦→v] = Q a.(X[b↦→v]) Lemma 4.16= Q a.X Cond. 2 of Def. 4.10, b#X

3. Suppose b′ is fresh (so b′#X) and suppose v ∈|U|. Using Lemma 4.17 suppose without loss of generality that a#v. Then we can reason as follows:

(Q a.X)[b↦→v] = Q a.(X[b↦→v]) Lemma 4.16= Q a.(((b′ b)·X)[b′↦→v]) Cond. 3 of Def. 4.10, b′#X= (Q a.((b′ b)·X))[b′↦→v] Lemma 4.16= ((b′ b)·(Q a.X))[b′↦→v] Theorem 2.13End of proof

4.4 pow σ(P) is a FOL-algebra

In Subsection 4.3 we exhibited ‘forall’ as an infinite intersection. Now, culminating in Theorem 4.21, we put this together with sets intersection and negation to create a model of first-order logic in the sense of Definition 3.3.

Suppose P = (|P|, ·,σ, U) is an σ-algebra over a termlike σ-algebra U.

Lemma 4.19

Suppose X, Y ∈|powσ(P)|.6 Then:

1. all a.(X ∩Y ) = (all a.X) ∩ all a.Y and exist a.(X ∪Y ) = (exist a.X) ∪ exist a.Y .

2. If a#Y then all a.(X ∪Y ) = (all a.X) ∪Y and exist a.(X ∩Y ) = (exist a.X) ∩Y .

3. If X ⊆Y then all a.X ⊆ all a.Y and exist a.X ⊆ exist a.Y .

4. If a#X then all a.X = X and exist a.X = X.

Proof

The first part is by a routine calculation on sets using Lemma 4.8.

The third part follows from the first part, noting that X ⊆Y if and only if X ∩Y = X if and only if X ∪Y = Y .

For the second part we reason as follows:

all a.(X ∪Y ) = ⋂u∈|U|(X ∪Y )[a↦→u] Definition 4.15= ⋂u((X[a↦→u]) ∪(Y [a↦→u])) Lemma 4.8= ⋂u(X[a↦→u] ∪Y ) Cond. 2 of Def. 4.10= (⋂u X[a↦→u]) ∪Y Fact= (all a.X) ∪Y Definition 4.15exist a.(X ∪Y ) = ⋃u∈|U|(X ∩Y )[a↦→u] Definition 4.15= ⋃u((X[a↦→u]) ∩(Y [a↦→u])) Lemma 4.8= ⋃u(X[a↦→u] ∩Y ) Cond. 2 of Def. 4.10= (⋃u X[a↦→u]) ∩Y Fact= (exist a.X) ∪Y Definition 4.15

The fourth part follows immediately from condition 2 of Definition 4.10.End of proof

Lemma 4.20

If X, Y ∈|powσ(P)| then Z ∈|powσ(P)| for every Z ∈ {X ∩Y , |X|\X, X[a↦→u], all a.X}.

Proof

We need to check the three conditions in Definition 4.10 for each construct.

• The case of X ∩Y . By Theorem 2.13 X ∩Y has finite support. Suppose a is fresh, so a#X, Y , and suppose u ∈|U|. By Lemma 4.8 and condition 2 of Definition 4.10 (X ∩Y)[a↦→u] = (X[a↦→u]) ∩ (Y[a↦→u]) = X ∩Y . Now suppose b is fresh, so b#X, Y , and suppose u ∈|U|. We reason as follows:

(X ∩Y )[a↦→u] = (X[a↦→u]) ∩(Y [a↦→u]) Lemma 4.8= ((b a)·X)[b↦→u] ∩(((b a)·Y )[b↦→u]) Cond. 2 of Def. 4.10= ((b a)·(X ∩Y ))[b↦→u] Lem. 4.8, Thm. 2.13

• The case of |X|\X. By Theorem 2.13 |X|\X has finite support. Suppose a is fresh, so a#X, |X|\X, and suppose u ∈|U|. By Lemma 4.9 and condition 2 of Definition 4.10, (|X|\X)[a↦→u] = |X|\(X[a↦→u]) = |X|\X. Suppose b is fresh, so b#X, and suppose u ∈|U|. We reason as follows:

(|X|\X)[a↦→u] = |X|\(X[a↦→u]) Lemma 4.9= |X|\(((b a)·X)[b↦→u]) Cond. 2 of Def. 4.10= (b a)·(|X|\X) Lem. 4.9, Thm. 2.13

In the final step we use the fact that (b a)·|X| = |X|.

• The case of X[a↦→u] is Corollary 4.13.

• The case of all a.X is Proposition 4.18.End of proof

Theorem 4.21

Suppose P = (|P|, ·,σ, U) is an σ-algebra over a termlike σ-algebra U. Then (|pow(P)|, ∩, |X|\-, sub, all) is a FOL-algebra.

Proof

Axioms (Commute), (Assoc), and (Huntington) are facts of sets.

Axioms (Subid), (Sub#), (Subα), and (Subσ) are Proposition 4.14. (Sub∧) is from Lemma 4.8. (Sub¬) is Lemma 4.9. (Sub∀) is Lemma 4.16. (∀α) is Lemma 4.17. (∀E) is by construction in Definition 4.15. (∀∧) and (∀∨) are from Lemma 4.19.End of proof

We will apply Theorem 4.21 in Proposition 5.26, as part of the representation theorem.

5 A representation theorem

We now show how, given a FOL-algebra B, we can embed it in a suitable notion of a ‘powerset of the powerset of B’, or to be more precise: the “σ-powerset of the σ-algebra of maximal filters of B”.

5.1 Filters

Definition 5.1

Suppose B is a FOL-algebra. A 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 ⇒∀a.x ∈p.
Remark 5.2

The first two conditions of Definition 5.1 are standard. Clearly, the third condition accounts for the extra structure of ∀. Interestingly, this is familiar from filters on Banonas (Boolean algebras enriched with an axiomatisation of the N-quantifier)—that is, even though N is a different quantifier than ∀, the notion of filter appears to require the same kind of condition. See [11, Definition 6.1].

But surely the natural condition is (∀u∈|U|.x[a↦→u] ∈p) ⇒∀a.x ∈p? Remarkably, this apparently stronger condition follows: see Proposition 5.6.

In fact the condition Na.∀x.x ∈p ⇒∀a.x ∈p is also familiar from another context. By Theorem 2.16 it is equivalent to ∀x.∀a.a#p ∧x ∈p ⇒∀a.x ∈p.7 This looks like (an abstract version of) the sequent ∀-right introduction rule, especially if we write x ∈p as p ⊢x and think of supp(p) as ‘the free atoms of p’:

p ⊢x (a ∉supp(p))“(∀R)”p ⊢∀a.x

This also suggest a syntactic intuition why (∀u∈|U|.x[a↦→u] ∈p) ⇒∀a.x ∈p is the weaker condition: just because all ground instances of a predicate φ are derivable, does not mean that ∀a.φ is derivable. We need to derive φ with a in it as a generic element. But remember, this is an analogy: p is not a sequent and x is not a predicate.

Notation 5.3

Suppose B is a FOL-algebra. Call X ⊆|B| up-closed when x ≤y and x ∈X implies y ∈X.

Lemma 5.4

If p is a filter then p is up-closed.

Proof

Recall that x ≤y is sugar for x∧y = x. The result follows using condition 2 of Definition 5.1.End of proof

Lemma 5.5

If p is a filter and ∀a.x ∈p then x ∈p.

Proof

From (∀E) and Lemma 5.4.End of proof

Proposition 5.6 is particularly interesting because it connects condition 3 of Definition 5.1 with the closure condition that we might intuitively expect for ∀:

Proposition 5.6

Suppose p is a filter. Then

∀a.x ∈p if and only if ∀u∈|U|.x[a↦→u] ∈p.
Proof

The left-to-right implication follows from Lemma 5.5.

For the right-to-left implication, suppose ∀u∈|U|.x[a↦→u] ∈p. Choose some fresh b, so b#x, u, p; then x[a↦→b] ∈p. By (Subα) x[a↦→b] = ((b a)·x)[b↦→b]. By (Subid) (b a)·x ∈p. By condition 3 of Definition 5.1 ∀b.(b a)·x ∈p. By (∀α) ∀a.x ∈p and we are done.End of proof

5.2 Maximal filter above a filter

The proof of this subsection follows the same general outline as for standard Stone duality. We culminate, as standard, with Theorem 5.18 which states that every filter is contained in a maximal filter. As standard, the existence of this maximal filter is proved using Zorn’s lemma.

The complication is caused by the need to account for ∀ (this is Lemma 5.14) and the need to generate a maximal filter without ‘extra support’ (this is Lemma 5.17). This last point is important because in a nominal universe Zorn’s Lemma need not necessarily hold8 so Lemma 5.17 proves that we are in one of the cases where it still does hold.

Definition 5.7

If z∈|B| then define

z↑= {x | z ≤x}.
Lemma 5.8

If z∈|B| and z ≠ ⊥ then z↑ is a filter.

Proof

We check the three properties of Definition 5.1 for z↑:

1. Suppose z ≤⊥. It follows by Lemma 3.10 and (∀∨) (taking y = ⊥) that z = ⊥, a contradiction.

2. Using axioms of Boolean algebras we have that z ≤x ∧y if and only if z ≤x and z ≤y.

3. Immediate from part 2 of Corollary 3.8.End of proof

Remark 5.9

The interested reader might like to compare Definition 5.7 with [11, Definition 6.5], which gives the right notion of z↑ for a representation theorem for a nominal algebraic axiomatisation of the N-quantifier N. This takes z↑= {x | z ≤Na1. . . an.x, supp(x)\supp(z) = {a1, . . . , an}}. We need Na1. . . an because it is not the case that a#z implies z≤Na.x ⇔z≤x. In contrast, in this paper for ∀, it is the case that a#z implies z≤∀a.x ⇔z≤x.

The axioms that lead to this difference in behaviour are ∀a.x ≤x ((∀E) from Figure 4) versus ¬Na.x =Na.¬x ((Selfdual) from [11, Figure 1]).

Definition 5.10

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

We now set about showing that every filter is contained in a maximal filter (Theorem 5.18). We use Zorn’s lemma.

Lemma 5.11

Suppose q is a filter and a#q. Then ∀a.x ∈q if and only if x ∈q.

Proof

Using Lemma 5.5 and condition 3 of Definition 5.1.End of proof

Definition 5.12

Suppose C ⊆A and x ∈|B|. Define ∀C.x by

∀C.x = ∀c1 . . . ∀cn.x where C ∩supp(x) = {c1, . . . , cn}.
Remark 5.13

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

Lemma 5.14

Suppose q is a filter and suppose x′ ∉q. Define C = supp(x′) \ supp(q) and write q′ = {z | z ∨∀C.x′ ∈q} (Definition 5.12). Then:

1. q′ is a filter.

2. q ⊆q′.

3. ¬x′ ∈q′.

Proof

We check the conditions in Definition 5.1:

• ⊥∉q′. Suppose ⊥∈q′. This implies ⊥∨∀C.x′ = ∀C.x′ ∈q, which by Lemma 5.11 contradicts our assumption that x′ ∉q.

• y1 ∈q′ ∧y2 ∈q′ ⇔y1 ∧y2 ∈q′. Suppose y1, y2 ∈q′. This means that y1 ∨∀C.x′ ∈q and y2∨∀C.x′ ∈q. It is a fact of distributive lattices that this happens if and only if (y1∧y1)∨∀C.x′ ∈q. The reverse implication is similar.

•Na.∀y. y ∈q′ ⇒∀a.y ∈q′. Suppose a is fresh (so a#q, x′) and suppose y ∈q′. By definition, y ∨∀C.x′ ∈q. By Lemma 5.11 ∀a.(y ∨∀C.x′) ∈q. By assumption a#x′, so by Lemma 3.7 and (∀∨) we know ∀a.(y ∨∀C.x′) = (∀a.y) ∨∀C.x′. It follows that ∀a.y ∈q′ as required.

Now suppose x ∈q. By Lemmas 5.4 and 5.11 ∀C.(x ∨x′) ∈q. It follows that x ∈q′. Finally, ⊤∈q and it follows that ∀C.(¬x′ ∨x′) ∈q and so ¬x′ ∈q′.End of proof

Proposition 5.15

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

Proof

Suppose ¬x ∉q and x ∉q; we derive a contradiction. By Lemma 5.14, q′ = {z | z ∨∀C.x ∈q} is a filter and q ⊆q′ and ¬x ∈q′ \ q, a contradiction.End of proof

We mention a nice corollary:

Lemma 5.16

Suppose p ⊆|B| is a maximal filter and c#p. Then ¬∀c.x ∈p if and only if ∀c.¬x ∈p.

Proof

Direct from Proposition 5.15 and Lemma 5.11.End of proof

Lemma 5.17

q is a maximal filter if and only if it is maximal amongst filters with no greater support (that is, if and only if for all 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 filters with no greater support. By Proposition 5.15 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 5.1. Now suppose ¬x ∉q and also x ∉q. We derive a contradiction. Write C = A \ supp(q). By Lemma 5.14, q′ = {z | z ∨∀C.x ∈q} is a filter and q ⊆q′ and ¬x ∈q′. By Theorem 2.13 supp(q′) ⊆ supp(q) and so q = q′, a contradiction.End of proof

Theorem 5.18

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

Proof

If C is a chain in the set of filters on B ordered by subset inclusion, then ⋃ C = {x | ∃p′ ∈C.x ∈ p′} is an upper bound for C. By Zorn’s Lemma [5, page 153] the set p◦ of filters p′ such that p ⊆p′ and supp(p′) ⊆ supp(p) has a maximal element q with respect to inclusion. By Lemma 5.17 q is maximal (Definition 5.10).End of proof

5.3 The amgis-action on filters

Filters are sets of elements with a σ-action. We saw in Definition 4.5 and Lemma 4.6 that such sets have an σ-action; but is this action closed if we restrict to filters?

Fix some FOL-algebra B over a termlike σ-algebra U. Recall from Definition 4.5 the pointwise action, which on filters of B yields p[u←↤a] = {x | x[a↦→u] ∈p}.

Lemma 5.19

If q is a filter of B then so is q[v←↤b] (Definition 4.5). Thus, the action does indeed map from filters to other filters.

Proof

By construction in Definition 4.5, q[v←↤b] ⊆|B|. By Theorem 2.13 supp(q[v←↤b]) ⊆ supp(q) ∪ supp(v) ∪{b} so supp(q[v←↤b]) has finite support. We check the other conditions in Definition 5.1:

• ⊥∉q[v←↤b]. By (Sub#) and Lemma 3.10 ⊥[b↦→v] = ⊥. By assumption ⊥∉q.

• y1 ∈q[v←↤b] ∧y2 ∈q[v←↤b] ⇔y1 ∧y2 ∈q[v←↤b]. Using (Sub∧).
•Na.(x ∈q[v←↤b] ⇒∀a.x ∈q[v←↤b]).

Suppose a is fresh (so a#q, b, v, x[b↦→v]). By Definition 4.5, x ∈q[v←↤b] if and only if x[b↦→v] ∈q. By condition 3 of Definition 5.1 this implies ∀a.(x[b↦→v]) ∈q. By (Sub∀) ∀a.(x[b↦→v]) = (∀a.x)[b↦→v]. The result follows.End of proof

Corollary 5.20

If q is a maximal filter then so is q[u←↤a].

Proof

By Lemma 5.19 q[u←↤a] is a filter. By Proposition 5.15 and (Sub¬) q[u←↤a] is maximal if q is maximal.End of proof

Proposition 5.21

The set of all maximal filters (or points) of B with the action of Definition 4.5 is an σ-algebra.

Proof

By Corollary 5.20 the action is well-defined on maximal filters. By Lemma 4.6 it satisfies the properties of Definition 4.4 and is an σ-action.End of proof

Remark 5.22

Note of σ-algebras two non-theorems:

• It is not necessarily the case that if p is a filter and b#p then p[u←↤a] = ((b a)·p)[u←↤b].

• It is not necessarily the case that if a#p then p[u←↤a] = p.

Thus, comparing Figures 1 and 5 we see that the duality between σ-algebra and σ-algebra is only partial; there are no axioms (Bus#) or (Busα).

The reader familiar with Stone duality may now be puzzled. Given that we have ‘lost properties’ moving from the σ-algebra B to the σ-algebra of points, how will we recover (Sub#) and (Subα)? The answer is in conditions 2 and 3 of Definition 4.10, which by a remarkable coincidence exactly restore what we have lost when we move to sets of points. This is the next subsection.

5.4 The canonical extension -•

For this subsection suppose B is a FOL-algebra over a term-like σ-algebra U. x, y will range over |B| and u will range over |U|.

Our main result is Theorem 5.30, which injects B into the powerset of its points. Exactly as anticipated and desired, ∀ is interpreted as an infinite sets intersection all.

Definition 5.23

Define points(B) to be the σ-algebra with

• underlying set |points(B)| = {p ⊆|B| | p is a maximal filter} and

• the action from Definition 4.5.

We may call a maximal filter in B a point.

Proposition 5.24

points(B) with the pointwise action (Defn. 4.10) is a nominal set.

Proof

Finite support is part of the condition of being a filter in Definition 5.1. By Theorem 2.13 the predicate ‘p is a maximal filter’ holds if and only if the predicate ‘π·p is a maximal filter’ holds.End of proof

Definition 5.25

Define the canonical extension B• = powσ(points(B)) (Definition 4.10) so that:

A ∧B = A ∩B ¬A = |B•| \ AA[a↦→u] = {p | p[u←↤a] ∈A} ∀a.A = ⋂{A[a↦→u] | u ∈|U|}

A and B will range over elements of |B•|.

Note that the definition of A[a↦→u] is the pointwise action from Definition 4.7.

With the results we have so far, we get Proposition 5.26 instantly:

Proposition 5.26

B• is a FOL-algebra.

Proof

This is just a rephrasing of Theorem 4.21.End of proof

Definition 5.27

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

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

-• from Definition 5.27 does indeed map to |B•|.

Proof

We check each of the properties in Definition 4.10:

1. It follows from Theorem 2.13 that supp(x•) ⊆ supp(x).

2. Suppose a#x. Then p ∈ (x•)[a↦→u] if and only if x[a↦→u] ∈p if and only if (by (Sub#)) x ∈p.

3. Suppose b#x, u. Then p ∈ ((b a)·(x•))[b↦→u] if and only if (b a)·(p[u←↤b]) ∈x• if and only if ((b a)·x)[b↦→u] ∈p if and only if (by (Subα)) x[a↦→u] ∈p if and only if x ∈p[u←↤a] if and only if p ∈ (x•)[a↦→u].End of proof

Proposition 5.29

Suppose B is a FOL-algebra over a termlike σ-algebra U and suppose x, y ∈|B| and u ∈|U|. Then:

1. (x ∧y)• = x• ∩y•,

2. (¬x)• = |points(B)|\x• and as a corollary (x ∨y)• = x• ∪y•,

3. (x[a↦→u])• = (x•)[a↦→u],

4. (∀a.x)• = all a.(x•) and (∃a.x)• = exist a.(x•), and

5. (π·x)• = π·(x•).

As a corollary from Definition 3.12, -• is an arrow from B to B• in FOL.

Proof

We consider each property in turn:

1. Proof that (x ∧y)• = x• ∩y•. Since by assumption in Definition 5.1 x ∧y ∈p if and only if x ∈p and y ∈p.

2. Proof that (¬x)• = |points(B)|\x•. We reason as follows:

p ∈(¬x)• ⇔¬x ∈p Definition 5.27⇔x ∉p Proposition 5.15⇔p ∉x•Definition 5.27⇔p ∈|points(B)|\x•Fact

3. Proof that (x[a↦→u])• = x•[a↦→u]. We just unfold definitions:

p ∈(x[a↦→u])• ⇔x[a↦→u] ∈p Definition 5.27⇔x ∈p[u←↤a] Definition 4.5⇔p[u←↤a] ∈x•Definition 4.5⇔p ∈x•[a↦→u] Definition 5.25

4. Proof that (∀a.x)• = all a.(x•) and (∃a.x)• = exist a.(x•). Choose some p ∈ points(B). We reason as follows:

p ∈(∀a.x)• ⇔∀a.x ∈p Definition 5.27⇔∀u∈|U|. x[a↦→u] ∈p Proposition 5.6⇔∀u∈|U|.p ∈(x[a↦→u])•Definition 5.27⇔p ∈⋂u∈|U|(x[a↦→u])•Fact⇔p ∈⋂u∈|U|(x•[a↦→u]) Part 1 of this result⇔p ∈all a.(x•) Definition 4.15

The second part follows by dualising with sets complement, recalling that ∃a.x is shorthand for ¬∀a.¬x.

5. (π·x)• = π·(x•).

By Theorem 2.13.9End of proof

Theorem 5.30 (Representation theorem).

Suppose B is a FOL-algebra over a termlike σ-algebra U and suppose x, y ∈|B| and u ∈|U|.

Then -• is injective and embeds B as a sub-FOL-algebra of B•.

Proof

By Proposition 5.29 -• is a morphism. It remains to check that it is injective.

Suppose x ∈|B| and y ∈|B| are distinct. Suppose without loss of generality that x ≰y, so that x ∧¬y ≠ ⊥. By Lemma 5.8 (x ∧¬y)↑ is a filter. By Theorem 5.18 there exists a point q containing (x ∧¬y)↑. Then x ∧¬y ∈q, hence q ∈x• and q ∉y•.End of proof

We conclude with Lemma 5.31. This will be useful to prove Lemma 6.5 but we place it here because it follows the same general idea as the commutativity properties of Proposition 5.29.

Lemma 5.31

(⋃i∈I x•i)[a↦→u] = ⋃i∈I(xi[a↦→u])•.

Proof

We reason as follows:

p ∈(⋃i∈I x•i)[a↦→u] ⇔p[u←↤a] ∈⋃i∈I x•iDefinition 5.25⇔∃i∈I.p[u←↤a] ∈x•iFact⇔∃i∈I.p ∈(x•i)[a↦→u] Definition 5.25⇔∃i∈I.p ∈(xi[a↦→u])•Proposition 5.29⇔p ∈⋃i∈I(xi[a↦→u])•FactEnd of proof

6 Nominal Stone duality

We have proved Theorem 5.30, a representation theorem which exhibits a FOL-algebra B as a subset of a powerset. We can now extend this to a Stone duality. The extra ingredients this gives us over the representation theorem are:

• We identify those topological spaces that are ‘logical’ in the sense that they come from FOL-algebras.

• We map not only algebras but also morphisms between them.

The proofs follow mostly the same outline as for the case of Boolean algebra. Perhaps most interesting are the definitions: of σ-topological space (Definition 6.1) and of ∀-Stone space (Definition 6.18), which require substantial modification from the classical case and which are non-obvious.

6.1 The basic definitions

Definition 6.1 (σ-Topological space).

Suppose U is a termlike σ-algebra. A σ-topological space T over U is a pair (|T|, OT) of

• an σ-algebra |T| = (||T||, ·, U,σ) (Definition 4.4) and

• a subset OT⊆pow(|T|) of open sets such that:

1. If U ∈OT then π·U, U[a↦→u] ∈OT.

2. ∅∈OT and ||T|| ∈OT

3. If U ∈OT and V ∈OT then U ∩V ∈OT.

4. U ∈ pow(OT) implies ⋃ U ∈OT; we call this a finitely-supported union (recall from Example 2.6 that U ∈ pow(OT) is a finitely-supported set of open sets).

Call f ∈|T1|→|T2| continuous when V ∈OT2 implies f -1(V)∈OT1.

Call f ∈|T1|→|T2| a morphism when:

5. f is equivariant (that is, π·f(x) = f(π·x)).

6. f is continuous.

7. f commutes with the amgis-action (that is, f(x)[u←↤a] = f(x[u←↤a]) for all u ∈|U| and a).

Write σTop for the category of σ-topological spaces and morphisms between them.

Definition 6.2 (Closed and clopen).

Suppose T is a σ-topological space. Suppose U ∈OT.

• Call U closed when |T| \ U ∈OT.

• Call U 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.10

Proposition 6.3 establishes by fairly easy calculations some basic closure properties which will be useful later:

Proposition 6.3

Suppose T is a σ-topological space over a termlike σ-algebra U.

If U, U ′ ∈OT are clopen then so are U ∩U ′, ||T|| \ U, and U[a↦→u] for u ∈|U|.

Proof

Suppose U and U ′ are clopen. We consider each case in turn:

• Intersection U ∩U ′. Since U and U ′ are closed, using condition 3 of Definition 6.1 it follows that U ∩U ′ is too. Since U and U ′ are open, by condition 4 of Definition 6.1 so is U ∩U ′. Thus U ∩U ′ is clopen.

• Complement ||T||\U. This case is similar to the case of intersection.

• Substitution U[a↦→u]. Since U is open, by condition 1 of Definition 6.1 so is U[a↦→u]. Since U is closed, ||T|| \ U is open. By Lemma 4.9 (||T|| \ U)[a↦→u] = ||T|| \ (U[a↦→u]). Therefore U[a↦→u] is also closed.End of proof

6.2 The functor F from FOLalg to σTopop

We are now ready to build a σ-topological space out of the points of a FOL-algebra B. The construction is exactly parallel to the standard case except that (in standard nominal style) instead of closing the topology under all unions, we close it only under finitely-supported unions:

Definition 6.4

Given B in FOLalg define F(B) in σTop by:

• |F(B)| = points(B) (Definition 5.23).

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

Given f : B→B′ in FOLalg define F(f) : F(B′)→F(B) by F(f)(p) = f -1(p), that is:

x ∈F(f)(p) ⇔f(x) ∈p
Lemma 6.5

F(B) is indeed a σ-topological space.

Proof

We consider each of the properties in Definition 6.1 in turn:

• If U ∈OF (B) then π·U ∈OF (B). By Theorem 2.13.

• If U ∈OF (B) then U[a↦→u] ∈OF (B). By construction U ∈OF (B) is equal to some finitely-supported union ⋃i∈I x•i. We use Lemma 5.31.

• It is easy to check that ∅ and |points(B)| are open.

• If U ⊆OF (B) is finitely-supported then ⋃ U ∈OF (B). Each U ∈U is a finitely-supported union ⋃iU x•iU and ⋃ U = ⋃U∈U⋃iU x•iU . By Theorem 2.13 a finitely-supported union of finitely-supported unions is itself finitely-supported, so we are done.End of proof

Lemma 6.6

If f : B →B′ is a morphism (Definition 3.12) then F(f) is indeed a morphism from F(B′) to F(B) (Definition 6.1).

Proof

First, we show that F(f) maps ||F(B′)|| = |points(B′)| to ||F(B)|| = |points(B)|.

Points are maximal filters, and it is convenient to first show that if p ⊆|B′| is a filter (not necessarily maximal) then so is f -1(p), and then show that if p is maximal then so is f -1(p).

Suppose p is a filter. We unpack Definition 5.1 and have three properties to verify, which we state below freely using the fact that by construction x ∈f -1(p) if and only if f(x) ∈p:

1. f(⊥) ∉p. By Lemma 3.13 f(⊥) = ⊥, and by condition 1 of Definition 5.1 ⊥∉p.

2. ∀x, y.(f(x) ∈p ∧f(y) ∈p) ⇔f(x ∧y) ∈p. By assumption f(x ∧y) = f(x) ∧f(y). The result follows by condition 2 of Definition 5.1.

3. Na.∀x.f(x) ∈p ⇒f(∀a.x) ∈p. Suppose a is fresh (so a#p). Choose any x. By assumption f(∀a.x) = ∀a.f(x). The result follows by condition 3 of Definition 5.1.

Now suppose that p is a maximal filter. By Proposition 5.15 it suffices to show that ¬x ∈f -1(p) if and only if x ∉f -1(p). We sketch the relevant reasoning; in step (∗) we use Proposition 5.15 for p:

¬x ∈f -1(p) ⇔f(¬x) ∈p ⇔¬f(x) ∈p (∗) ⇔f(x) ∉p ⇔x ∉f -1(p)

Thus f -1(p) is maximal.

Second, we show that F(f) is a morphism. We need to verify the final three properties of Definition 6.1:

• F(f) is equivariant. We briefly sketch the reasoning; in step (∗) we use the assumption that f is equivariant (Definition 2.7):

x ∈π·(F(f)(p)) ⇔π-1·x ∈F(f)(p) ⇔f(π-1·x) ∈p (∗) ⇔π-1·f(x) ∈p ⇔f(x) ∈π·p ⇔x ∈F(f)(π·p)

• F(f) is continuous. By construction F(f)-1 preserves unions, so it suffices to show that F(f)-1(x•) = f(x)•. Again we briefly sketch the reasoning:

p ∈F(f)-1(x•) ⇔F(f)(p) ∈x• ⇔x ∈F(f)(p) ⇔f(x) ∈p ⇔p ∈f(x)•

• F(f) commutes with the amgis-action. Suppose p′ ∈||F(B′)|| and u ∈|U|. We briefly sketch the reasoning; in step (∗) we use the assumption that f commutes with the σ-action:

x ∈(F(f)(p))[u←↤a] ⇔x[a↦→u] ∈F(f)(p) ⇔f(x[a↦→u]) ∈p (∗) ⇔f(x)[a↦→u] ∈p ⇔f(x) ∈p[u←↤a] ⇔x ∈F(f)(p[u←↤a])End of proof

We conclude with a technical lemma which will be useful later:

Lemma 6.7

If x ∈|B| then x• ⊆||F(B)|| is clopen; that is, x• ∈OF (B) and |points(B)| \ x• ∈OF (B).

Proof

x• ∈OF (B) by construction in Definition 6.4.

Also, by Proposition 5.15 points(B) \ x• = (¬x)•, and by construction (¬x)• ∈OF (B).End of proof

6.3 The functor F maps to σStoneop

Our Stone duality result has to answer the question: what abstract properties must a topology have, to be the image of a FOL-algebra? Being totally separated is one such property; this is standard. Being compact is another; it turns out that we need to tweak this property to what we call being ∃-compact to make Proposition 6.11 work. We will also need another property, of having/being with ∀. It all emerges in this subsection.

6.3.1 Totally separated, compact spaces

Definition 6.8

Suppose T is a σ-topological space.

• Call U ∈ pow(OT) ∃-closed when Na.∀U.(U∈U ⇒ exist a.U∈U).

• Call U ∈ pow(OT) a cover when ⋃ U = ||T||.

• Call U a ∃-cover when U is a cover and is ∃-closed.

• Call T ∃-compact when every ∃-cover has a finite subcover.

Lemma 6.9

If U∈pow(OF (B)) is ∃-closed then so is V = {x• | ∃U∈U.x•⊆U}.

Proof

Choose b fresh (so b#U, V). If x• ∈V then x• ⊆U for some U ∈U. By part 3 of Lemma 4.19 exist b.(x•) ⊆ exist b.U and by assumption exist b.U ∈U.End of proof

Lemma 6.10

Suppose U ∈ pow(OF (B)) is an ∃-cover (Definition 6.8). Then so is V = {x• | ∃U∈U.x• ⊆ U}.

Proof

By construction in Definition 6.4 every U ∈U is equal to ⋃i∈I x•i for some finitely-supported union of x•i, thus V is a cover.

Now suppose a is fresh (so a#V, U) and suppose x• ∈V. It must be that x• ⊆U ∈U. By assumption U is ∃-closed so exist a.U ∈U. By part 4 of Proposition 5.29 (exist form) (¬∀a.¬x)• = exist a.(x•). By part 3 of Lemma 4.19 exist a.(x•) ⊆ exist a.U. It follows that exist a.(x•) ∈V.End of proof

Proposition 6.11 motivates ∃-compactness from Definition 6.8:

Proposition 6.11

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

Proof

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

Now consider an ∃-cover V ∈ pow(OF (B)). By Lemma 6.10 we may assume without loss of generality that every element of V has the form x• for some x ∈|B|. 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. We now check that X ⊆|B| satisfies conditions 2 and 3 of Definition 5.1:

• Proof that x ∈X ∧y ∈X if and only if x ∧y ∈X. By construction X is closed under finite intersections, so x ∈X and y ∈X imply x ∧y ∈X. Also by construction X is up-closed (Notation 5.3), and it follows that x ∧y ∈X implies x ∈X and y ∈X.

• Proof that Na.∀x.x ∈X ⇒∀a.x ∈X. Suppose a is fresh (so a#X, V, X) and x ∈X. Then there exists an x′ with ¬x′ ≤x and (x′)• ∈V. By Lemma 3.6 ∀a.¬x′ ≤∀a.x. Also ∀a.(¬x′) = ¬∃a.x′. Now by part 4 of Proposition 5.29 (∃a.x′)• = exist a.(x′)• and by assumption V is ∃-closed. It follows that ∀a.x ∈X.

If ⊥∉X then X is a filter and by Theorem 5.18 X ⊆p for some point p. It would follow that p ∉⋃ V, a contradiction. Therefore ⊥∈X.End of proof

6.3.2 Clopens in F(B)

Lemma 6.12

• If x• ⊆U and a#U then (∃a.x)• ⊆U and (∀a.x)• ⊆U.

• If x• ∩U = ∅ and a#U then (∃a.x)• ∩U = ∅ and (∀a.x)• ∩U = ∅.

Proof

Suppose x• ⊆U. By part 3 of Lemma 4.19 exist a.x• ⊆ exist a.U. By part 4 of Proposition 5.29 (∃a.x)• = exist a.x• and by part 4 of Lemma 4.19 exist a.U = U since a#U. It follows that (∃a.x)• ⊆U. The case of ∀ is exactly similar.

Suppose x• ∩U = ∅. By part 2 of Lemma 4.19 exist a.x• ∩U = ∅, since a#U and a#∅. We use part 4 of Proposition 5.29 to conclude that (∃a.x)• ∩U = ∅. The case of ∀ is similar, using parts 1 and 4 of Lemma 4.19.End of proof

Proposition 6.13

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

Proof

By construction in Definition 6.4 the open sets of F(B) are unions of finitely-supported sets of sets the form x•. We assumed that U and its complement are open, so that

U =⋃{x• | x• ⊆U} and ||F(B)|| \ U =⋃{x• | x• ⊆||F(B)|| \ U}

(recall that ||F(B)|| = |points(B)|). It follows that

U = {x• | x• ⊆U ∨x• ∩U = ∅} covers F(B).

U is ∃-closed by Lemma 6.12, so by Proposition 6.11 it has a finite subcover, and it follows that there is some finite {x•1, . . . , x•n} ⊆U such that x•1 ∪· · · ∪x•n = U. By part 2 of Proposition 5.29 we have U = (x1 ∨· · · ∨xn)•.End of proof

6.3.3 Closure under all and exist

Lemma 6.14

Suppose T is a σ-topological space. Then if U is open then exist a.U is open, and if U is closed then all a.U is closed.

Proof

Suppose U is open. By condition 1 of Definition 6.1 U[a↦→u] is open for every u ∈|U|. Therefore, exist a.U = ⋃u∈|U| U[a↦→u] is open (it follows from Theorem 2.13 that the set {U[a↦→u] | u ∈|U|} is finitely-supported).

Suppose U is closed. Since U is closed, by Proposition 6.3 U[a↦→u] is closed for every u ∈|U|. The result follows similarly to the case of exist.End of proof

Definition 6.15

Suppose T is a σ-topological space. Say T has ∀ or T is with ∀ when if U is clopen then:

1. all a.U is open, and

2. if t ∈U and a#t then t ∈ all a.U.

Lemma 6.16

If T is a σ-topological space with ∀ then U ∈OT clopen implies that all a.U and exist a.U are also clopen.

Proof

By Lemma 6.14 exist a.U is open and all a.U is closed. By assumption all a.U is open. Also by assumption all a.(||T||\U) is open, and it follows that exist a.U is closed.End of proof

Proposition 6.17

F(B) has ∀.

Proof

Suppose U is clopen. By Proposition 6.13 U = x• for some x ∈|B|. We consider each condition of Definition 6.15 in turn:

1. By part 4 of Proposition 5.29 all a.U = (∀a.x)• and it follows in particular that all a.U is open.

2. Suppose p is a filter in B and p ∈x• and a#p. Thus, x ∈p and a#p. By condition 3 of Definition 5.1 ∀a.x ∈p, that is, p ∈ (∀a.x)•. Again we use part 4 of Proposition 5.29 and the result follows.End of proof

6.3.4 Nominal ∀-Stone space

Definition 6.18

A nominal ∀-Stone space is a nominal σ-topological space with ∀ that is totally separated and ∃-compact. Write σStone for the full subcategory of σTop of nominal ∀-Stone spaces.

Theorem 6.19

F is a functor from FOLalg to σStoneop.

Proof

By Lemma 6.5 F(B) is a σ-topological space. By Proposition 6.11 it is totally separated and ∃-compact. By Proposition 6.17 it has ∀.

Furthermore if f : B →B′ in FOLalg then by Lemma 6.6 F(f) is a morphism from F(B′) to F(B).End of proof

6.4 The functor G from σStoneop to FOLalg

Definition 6.20

Map T ∈σStone to a G(T) ∈ FOLalg defined by:

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

• ∧, ¬, and ∀ are interpreted as intersection, complement, and all.

Given g : T →T′ in σStone define G(g) : G(T′) →G(T) by G(g)(U) = g-1(U), that is:

t ∈G(g)(U) ⇔g(t) ∈U
Lemma 6.21

Suppose T is a nominal ∀-Stone space. Then G(T) is indeed a FOL-algebra.

Proof

By Proposition 6.3 intersection and complement do indeed map from |G(T)| to |G(T)|. By Lemma 6.16 so does all a.

We must also check that the equalities of a FOL-algebra hold. This follows using Theorem 4.21.End of proof

Lemma 6.22

Suppose T and T′ are σ-topological spaces and f : T →T′ is a morphism. Then if U ∈OT′ is clopen then so is G(f)(U) ∈OT.

Proof

By assumption since U is open, so is f -1(U). Also by assumption since ||T|| \ U is open, so is f -1(||T|| \ U) = ||T|| \ f -1(U).End of proof

Lemma 6.23

G is a functor from σStoneop to FOLalg.

Proof

By Lemma 6.21 G maps objects of σStoneop to objects of FOLalg.

Now consider a morphism g : T →T′; we must show that G(g)—that is, g-1—is a morphism of FOL-algebras. So we must show that g-1 maps clopens in OT′ to clopens in OT and satisfies the commutations listed in Definition 3.12.

If U is clopen then by Lemma 6.22 so is g-1(U). It is not hard to check that g-1 preserves intersections and complements. We show that g-1 is equivariant and commutes with all. Suppose U is clopen in T′; we reason as follows:

t ∈π·g-1(U) ⇔π-1·t ∈g-1(U) Definition 4.7 (pointwise act.)⇔g(π-1·t) ∈U Definition 6.20⇔π-1·g(t) ∈U Cond 5 of Def. 6.1⇔g(t) ∈π·U Definition 4.7 (pointwise act.)⇔t ∈g-1(U) Definition 6.20t ∈g-1(all a.U) ⇔g(t) ∈all a.U Definition 6.20⇔∀u∈|U|.g(t) ∈U[a↦→u] Definition 4.15⇔∀u.g(t)[u←↤a] ∈U Definition 4.7⇔∀u.g(t[u←↤a]) ∈U Cond. 7 of Def. 6.1⇔∀u.t[u←↤a] ∈g-1(U) Definition 6.20⇔∀u.t ∈(g-1(U))[a↦→u] Definition 4.15⇔t ∈all a.(g-1(U)) Definition 4.15

Thus G(g) is a morphism in FOLalg.End of proof

6.5 The equivalence

Proposition 6.24

GF(B) is equal to B• and the map -• defines an isomorphism between B and GF(B).

Proof

By Proposition 6.13 {U ∈OF (B) | U is clopen} ⊆||B•||. By Lemma 6.7 ||B•|| ⊆{U ∈ OF (B) | U is clopen}. The result follows by Theorem 5.30.End of proof

Lemma 6.25

Suppose T ∈σTop is ∃-compact. Suppose U is a filter in G(T). Then ⋂ U ≠ ∅.

Proof

We unpack the properties of U. It is a finitely-supported set of clopen sets in T such that:

• ∅∉U.

• If U1, U2 ∈U then U1 ∩U2 ∈U.

• If U ∈U and a#U then all a.U ∈U.

If ⋂ U = ∅ then {||T|| \ U | U ∈U} is an ∃-cover of T. Since T is ∃-compact this ∃-cover has a finite subcover, thus some finite intersection of elements of U is empty, contradicting that ∅∉U.End of proof

Definition 6.26

Suppose T ∈σTop and t ∈||T||. Define

t∗= {U | U ∈|G(T)|, t ∈U},

so that U ∈t∗⇔t ∈U.

Lemma 6.27

Suppose T ∈σTop has ∀ (Definition 6.15). Then t∗ is a filter in G(T).

Proof

By Theorem 2.13 supp(t∗) ⊆ supp(t) and so in particular t∗ has finite support. Conditions 1 and 2 of Definition 5.1 are very easy to check.

For condition 3, suppose a is fresh (so a#t) and suppose U ∈t∗. That is U is a clopen set with t ∈U. By condition 2 of Definition 6.15 t ∈ all a.U, that is, all a.U ∈t∗.End of proof

Lemma 6.28

Suppose T ∈σTop is totally separated and t1, t2 ∈||T||. Then t∗ 1 ⊆t∗ 2 implies t1 = t2.

Proof

By a routine calculation.End of proof

Corollary 6.29

Suppose T ∈σTop has ∀ and is totally separated and ∃-compact; that is, suppose T ∈σStone. Then U is a maximal filter in G(T) if and only if U = t∗ for some t ∈||T||.

Proof

Suppose U is a maximal filter in G(T). By Lemma 6.25 there is some t ∈||T|| such that t ∈U for every U ∈U, so that U ⊆t∗. By Lemma 6.27 t∗ is a filter, so by maximality t∗⊆U, and we are done.

Now consider t∗; by Lemma 6.27 this is a filter and we need to show that it is maximal. Suppose t∗⊆U. By Lemma 6.25 U ⊆ (t′)∗ for some t′ ∈||T||. It follows by Lemma 6.28 that t = t′ and so U = t∗.End of proof

Lemma 6.30

If we give t∗ the pointwise σ-action from Definition 4.5 then t∗[u←↤a] = (t[u←↤a])∗.

Proof

Unpacking Definition 4.5 U ∈t∗[u←↤a] if and only if U[a↦→u] ∈t∗. By definition U[a↦→u] ∈t∗ if and only if t ∈U[a↦→u]. Unpacking the pointwise action from Definition 4.7 t ∈U[a↦→u] if and only if t[u←↤a] ∈U. The result follows.End of proof

Proposition 6.31

If T ∈σStone then -∗ defines an isomorphism between T and FG(T), and is a morphism αT of σ-topological spaces.

Proof

Injectivity is Lemma 6.28. Surjectivity is Corollary 6.29. Commutativity with the σ-action is Lemma 6.30.

We also need to show that α is continuous. The reasoning is standard [3, Section 4] so we just sketch it. First, consider the inverse image under -∗ of a clopen U in FG(T), that is of U • where U is a clopen in G(T).11

t ∈α-1 T (U •) ⇔αT(t) ∈U •⇔{U ′ | t ∈U ′} ∈U •⇔U ∈{U ′ | t ∈U ′} ⇔t ∈U

Thus, α-1 T (U •) = U.

Now by construction any open set in FG(T) is a union of U •, and α-1 T preserves these unions. It follows that the inverse image of an open set is open.End of proof

Theorem 6.32

G : σStoneop → FOLalg defines an equivalence between FOLalg and σStoneop.

Proof

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

• G is essentially surjective on objects. This is Proposition 6.24.

• G is faithful. Suppose g1, g2 : T →T′ ∈σStone and g1 ≠ g2; that is, there exists p ∈||T|| such that g1(p) ≠ g2(p). By assumption T is totally separated, so there is a clopen U ∈OT′ with g1(p) ∈U and g2(p) ∉U. Examining Definition 6.20 we see that p ∈G(g1)(U) and p ∉G(g2)(U). Thus, G(g1) ≠ G(g2).

• G is full. Given T, T′ in σStone and f : G(T′) →G(T) in FOLalg we construct a morphism g : T →T′ in σStone such that G(g) = f. By Proposition 6.31 αT : T →FG(T) mapping t to t∗ is an isomorphism in σStone. Set g = α-1 T′ ◦F(f) ◦αT. By routine calculations we can check that G(g)(U ′) = f(U ′) for every U ′ ∈|G(T′)|.End of proof

7 Conclusions

We have seen how to axiomatise first-order logic as a nominal algebraic theory and how to move between abstract algebraic models, and concrete topological ones.

What makes this unusual is the treatment of variables—the things that get bound by the universal quantifier. These are not handled using valuations. Instead, notions of sigma-algebra and amgis-algebra are introduced and a delicate and rather beautiful dance between them takes place in the proofs. Substitution is carried out on a topological space, in an ‘almost boring’ pointwise manner, and open predicates are directly represented as sets.

This is part of a broader programme by the author to reevaluate how we approach referents in the foundations of logic and computation, and in particular how we handle variables in logic and semantics. The results in this paper make precise a slogan that ‘a variable is a name that populates both the syntax and denotation, and has a substitution action in the denotation’.12

In short, variables of first-order logic can be viewed as first-class denotational entities in logic and topology; they are just another property of truth-values and of the points of a topological space.

Related work. This paper emerges from a thread of previous research. In [12, 14] we axiomatised substitution and in [13, 15] we axiomatised first-order logic. The descendents of these axioms populate this paper; for instance Figures 1 and Figure 4.

It is now natural to ask what concrete representations can be given for the abstract models.

An answer to that question was given for σ-algebras in [9, Section 5], in which it was shown that (in the terminology of this paper) a large subclass of the cumulative hierarchy of Fraenkel-Mostowski sets naturally has σ-algebra structure. This paper, by completely different methods from [9], gives an answer to the same question for first-order logic.

We are aware of one other nominal representation theorem: a previous paper by the author with Litak and Petrişan [11]. This proved a Stone duality for Boolean algebras with (an axiomatisation of) the Gabbay-Pitts N-quantifier—N is defined in this paper in Definition 2.14.

The proofs of this paper follow the same general outline as those in [11], though they are significantly different because ∀ has more structure than N; notably we must account for substitution, which is not relevant in the case of N. This led us to notions such as sigma- and amgis-algebra, σ-topological space, ∀-Stone space, and so on. Still, at a sufficiently high level of abstraction the reader can think of this paper as “[11] plus σ and ∀”.

Further afield are two research threads: representation theorems for cylindric algebras [1] and the PhD thesis of Forssell [7].

Cylindric algebra is a method of axiomatising first-order logic in normal first-order syntax; broadly speaking ∀a here corresponds to a distinct term-former for each a, and several infinite axiom-schemes express their properties.13 Cylindric algebras are a large field; for an extensive treatment see [20] and for a concise treatment concentrating on representation theorems and with a good survey and bibliography see [1]. The Wikipedia article [32], though brief, is a wonderfully clear and accessible exposition on the topic. Broadly speaking, a cylindric algebra is represented as a set of α-sequences, which corresponds to a notion of valuation; thus at a high level we can view the content of [1] as representing an open predicate as the set of valuations that make it true.

Forssell’s PhD thesis [7] extends results of Butz and Moerdijk [4] to a duality which can be thought of as follows: a category of first-order theories on one side, and a category of topological groupoids on the other side. The structure of the proofs is broadly parallel to that of this paper (and indeed of most other such duality proofs): the category FOLalg corresponds to the category BCκ of Boolean coherent categories in [7, page 85]; Theorem 5.30 corresponds to Lemma 2.3.2.1; and Theorem 6.32 corresponds to Theorem 2.4.5.10.

There is currently no obvious sense in which the results of this paper can be used to prove those of Forssell, or vice versa. What we can note is that first-order theories are turned into categories by syntactic methods in Forssell’s work (using the standard notion of syntactic category from categorical logic, explained on [7, page 15]), wheras FOLalg is much more abstract; and conversely our notion of topological space is more elementary than the notion of Forssell’s notion of topological groupoid.

So broadly speaking, Forssell constructs an adjunction between fairly concrete term-based logical entities on the left and fairly highly-structured geometric entities on the right, whereas in this paper we construct an adjunction between fairly abstract axiomatic logical entities on the left (FOL-algebras), and fairly elementary sets-based geometric entities on the right (∀-Stone spaces).

On foundations. One important technical feature of this paper can be phrased in two equivalent ways:

• We work in the category of nominal sets / the Schanuel topos.

• We work in the category of finitely-supported sets / Fraenkel-Mostowski set theory.

This is what Section 2 is all about, and it really matters. The reader not interested in foundations still needs to be alert to what these foundations give us, notably the notions of support, permutation, and Theorems 2.13 and 2.16.

We use these notions when we write the freshness side-conditions in our axioms in Figures 1 to Figure 5; we use them when we write and reason on the N-quantifier in Definition 5.1 and subsequent proofs. If the reader wonders ‘how do you know this fresh name exists?’ or ‘how do you know it does not matter which name you use?’ the answer is: because we are working in a nominal foundation.

If we worked in Zermelo-Fraenkel set theory and represented names as numbers, then the theorems of this paper would still be true.

However, the proofs would be harder, because we would not know a fresh name exists (we would have to carefully prove it) and we would not know it does not matter which name we use (we would have to carefully prove it). These proofs, though necessary, would be a waste of time; an artefact of our clunky definitions rather than a mathematically core concern. We will never use the internal structure of a number-considered-as-a-name, because if we did, we would not be considering it as a name. The nominal foundations are a way of making that intuition formal.

So for comparison, Zermelo-Fraenkel foundations tell us that the functional image of a countable set is countable. We do not need to re-count the image; our foundations give us this theorem for free. By using a sets foundation we committed to sets and operations on them, and we get a toolkit to manipulate them for free. In the same way, nominal foundations give us a toolkit for symmetric reasoning on names in sets. We do not need to re-prove symmetry and finite support properties; our foundations give us the theorems for free, and we can really exploit this to obtain results that would be harder to prove otherwise.

Philosophical literature. We come to the topic of variables and foundations motivated by theoretical computer science where reasoning on logic and programming leads us to consider reasoning on variables. The philosophical literature has independently given such questions much thought—and for a lot longer. The interested reader is referred in particular to Kit Fine’s theory of arbitrary objects [6] and to an essay by John Baldwin on the evolution of the notion of variable in history and modern mathematical education [2], as just two examples. Technically, those works are hardly connected to the material of this paper, but they exemplify thinking which is not beholden to the traditions and assumptions that are typically taken for granted in computer science.

Summary and future work. The technical content of this paper is interesting and the proofs require several technical innovations.

However, for this author the real significance of the results is that they make concrete (literally: as sets-based topological models) a particular, and very distinctive, view of names and variables in logic.

We can naturally ask what other names in logic can be approached using these techniques. In [11] we treated the N-quantifier. In this paper we treated the universal quantification of first-order logic—if it was not surprising that the ‘nominal’ quantifier N has a ‘nominal’ representation, it is more striking that the ‘traditional’ quantifier ∀ has a similar ‘nominal’ representation.

To take this further we can consider λa from the λ-calculus (which has been given a ‘cylindric’ axiomatisation in [26] and a ‘nominal’ one in [16]), second-order logic, higher-order logic (cf. the Henkin semantics below), the propositional quantifier ⋀α from System F [19], and generalised quantifiers [31].

Some partial work here has been done by the author in collaboration.

With Mulligan we constructed a nominal-style Henkin semantics for a nominal axiomatisation of the simply-typed λ-calculus [17]. The axiomatisation is in the same spirit as the nominal axiomatisation of first-order logic here, but it includes simple types. The Henkin models are abstract, not a concrete sets-based representation.

With Michael Gabbay we constructed models of the untyped λ-calculus [8]. These have a topological flavour and are based on concrete sets. However, they are not nominal: variables are handled traditionally using valuations.

We can view this previous work as approaching a certain goal along two branches—nominal on one side, sets-based on the other. This paper brings the two branches together for the case of first-order logic, and is an encouraging sign that the goal is attainable for other systems too.

References

[1] Hajnal Andréka and Richard J. Thompson. A Stone type representation theorem for algebras of relations of higher rank. Transactions of the American Mathematical Society, 309(2):671–682, October 1988.

[2] John Baldwin. Variables: Syntax, semantics, and situations, 2009. Preprint, available at homepages.math. uic.edu/~jbaldwin/pub/var5.pdf.

[3] Stanley N. Burris and H. P. Sankappanavar. A Course in Universal Algebra. Graduate texts in mathematics. Springer, 1981.

[4] Carsten Butz and Ieke Moerdijk. Representing topoi by topological groupoids. Journal of Pure and Applied Algebra, 130:223–235, 1998.

[5] Herbert B. Enderton. Elements of Set Theory. Academic Press, 1977.

[6] Kit Fine. Reasoning with Arbitrary Objects. Blackwell, 1985.

[7] Henrik Forssell. First-Order Logical Duality. PhD thesis, Carnegie Mellon University, December 2007.

[8] Michael J. Gabbay and Murdoch J. Gabbay. A simple class of Kripke-style models in which logic and computation have equal standing. In International Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2010), 2010.

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

[10] Murdoch J. Gabbay. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic, 17(2):161–229, 2011.

[11] Murdoch J. Gabbay, Tadeusz Litak, and Daniela Petrişan. Stone duality for nominal Boolean algebras with NEW. In Proceedings of the 4th international conference on algebra and coalgebra in computer science (CALCO 2011), volume 6859 of Lecture Notes in Computer Science, pages 192–207. Springer, 2011.

[12] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding Substitution as a Nominal Algebra. In ICTAC 2006: Theoretical Aspects of Computing, volume 4281 of Lecture Notes in Computer Science, pages 198–212, November 2006.

[13] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order logic. In Proceedings of the 8th ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming (PPDP 2006), pages 189–200. ACM, July 2006.

[14] Murdoch J. Gabbay and Aad Mathijssen. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing, 20(4-5):451–479, June 2008.

[15] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order Logic. Journal of Logic and Computation, 18(4):521–562, August 2008.

[16] Murdoch J. Gabbay and Aad Mathijssen. A nominal axiomatisation of the lambda-calculus. Journal of Logic and Computation, 20(2):501–531, April 2010.

[17] Murdoch J. Gabbay and Dominic Mulligan. Nominal Henkin Semantics: simply-typed lambda-calculus models in nominal sets. In Proceedings of the 6th International Workshop on Logical Frameworks and Meta-Languages (LFMTP 2011), volume 71 of EPTCS, pages 58–75, September 2011.

[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] Jean-Yves Girard, Paul Taylor, and Yves Lafont. Proofs and types. Cambridge University Press, 1989.

[20] Leon Henkin, J. Donald Monk, and Alfred Tarski. Cylindric Algebras. North Holland, 1971 and 1985. Parts I and II.

[21] Edward V. Huntington. New sets of independent postulates for the algebra of logic with special reference to Whitehead and Russell’s “Principia Mathematica”. Transactions of the American Mathematical Society, 35(1):274âĂŞ304, January 1933.

[22] Peter T. Johnstone. Sketches of an Elephant: A Topos Theory Compendium, volume 43 and 44 of Oxford Logic Guides. OUP, 2003.

[23] 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.

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

[25] Saunders Mac Lane and Ieke Moerdijk. Sheaves in Geometry and Logic: A First Introduction to Topos Theory. Universitext. Springer, 1992.

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

[27] Walter Rudin. Real and Complex Analysis. International Series in Pure and Applied Mathematics. McGraw Hill, third edition, 1987.

[28] Lynn Arthur Steen and J. Arthur Seebach Jr. Counterexamples in topology. Springer, 1978. See 1995 Dover reprint.

[29] Steve Vickers. Topology via Logic, volume 5 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1989.

[30] Dag Westerståhl. Quantifiers in formal and natural languages. In Handbook of Philosophical Logic, volume 4 of Synthèse, chapter 2, pages 1–131. Reidel, 1989.

[31] Dag Westerståhl. Generalized quantifiers. In Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Metaphysics research lab, CSLI, Stanford University, summer 2011 edition, 2011.

[32] http://en.wikipedia.org/wiki/Cylindric_algebra, retrieved 1 December 2011.

Notes

∗Thanks to Gilles Dowek, Henrik Forssell, Alexander Kurz, Nicholas Oury, Per Martin-Löf, Dominic Mulligan, and Alex Simpson for comments and advice. Thanks also to Margarita Korovina, Andrei Voronkov, and special congratulations to Howard Barringer. We acknowledge the support of the Leverhulme trust and of grant RYC-2006-002131 at the Polytechnic University of Madrid. ↩

1Various equivalent axiomatisations are available. We use a particularly compact one due to Huntington; see Figure 2. ↩

2Nominal 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. See [10, Subsection 9.3] and [10, Section 4]. ↩

3x 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. ↩

4φ should not use the axiom of choice. Every φ used in this paper will satisfy this property. ↩

5The σ-algebra here has nothing to do with the Σ-algebra used in measure theory [27, Definition 1.3, page 8]. Our σ stands for σubstitution. ↩

6Recall from Definition 4.10 that powσ(P) is a σ-algebra with underlying set certain ‘good’ subsets of |P|, with the pointwise substitution and permutation actions. So writing ‘X ∈|powσ(P)|’ is just a fancy way of saying “X is a well-behaved subset of |P|, with pointwise permutation and substitution actions”. ↩

7The version using N is preferable over the version using ∀ and #, because N leaves us free to choose a fresh for any other variables in our reasoning context at the time we need to verify the condition. This is the advantage of N: it allows us to use a fresh atom, without having to either choose a particular fresh atom or consider all fresh atoms. ↩

8Or rather, Zorn’s lemma still holds but may take us outside the finitely-supported universe. ↩

9A proof by concrete calculations is of course also possible, but not very interesting. ↩

10The reader should be familiar with topologies and closed sets, e.g. the real numbers R with its standard topology, in which the interval [0, 1] is closed. R with the discrete topology (in which every subset is clopen) is a trivial example of a totally separated space. The Cantor set is an example of a non-trivial totally separated space [28, Example 29, page 57]. The topological space which we construct out of a FOL algebra will be another example (Lemma 6.5). ↩

11U • is the set of maximal filters of clopens of T that contain U. ↩

12Rather than the slogan that ‘a variable is that thing that populates only syntax and points to an arbitrary element in a denotation’ made formal by valuations ς and a definition with a structure of the form ‘⟦φ⟧ς’. ↩

13Nota bene: the term-formers of cylindric algebras correspond to ∃a, not ∀a. Also, the axiomatisations in this paper, from Figure 1 to Figure 5, are finite. ↩