Stone duality for first-order logic: a nominal approach to logic and topology
Heriot-Watt University, Scotland, 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:
Here is some ‘domain of points’. Boolean algebra does not have a universal quantification so the semantics for 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 [] where 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 for in a set ?’. 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 -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:
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() (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.
Fix a countably infinite set of atoms . We use a permutative convention that range over distinct atoms.
A (finite) permutation is a bijection on atoms such that nontriv(() is finite.
Write id for the identity permutation such that id( for all . Write for composition, so that ()((()). Write for inverse, so that . Write () for the swapping (terminology from [18]) mapping to , to , and all other to themselves, and take (.
If define fix((.
A set with a permutation action is a pair () of an underlying set and a permutation action written which is a group action on , so that id and ( () for all and permutations and . Say that supports when fix() . If a finite supporting exists, call finitely-supported.
Call a set with a permutation action a nominal set when every has finite support. , , will range over nominal sets.
is a nominal set where ().
If and are nominal sets then is a nominal set with underlying set () and action ().
If is a set with a permutation action then powerset() is a set with a permutation action with underlying set and the pointwise action .
If is a nominal set then pow() (the nominal powerset) is a nominal set, with underlying set those powerset() 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].
Call a function equivariant when (() for all permutations and . In this case write : .
Suppose is a nominal set and . Define the support of by supp( supports Write # as shorthand for supp() and read this as is fresh for .
Suppose is a nominal set and . Then supp() is the unique least finite set of atoms that supports .
See part 1 of Theorem 2.21 of [10].
Write for the partial function which is restricted to .
1. If ( for all supp() then .
2. If then .
3. # if and only if # ().
From part 2 of Theorem 2.21 of [10].
supp(() supp() (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.
If is a list , write for . Suppose () is a first-order logic predicate with free variables . Suppose () is a function specified using a first-order predicate with free variables . Then we have the following principles:
1. Equivariance of predicates. () ().3
2. Equivariance of functions. (().
3. Conservation of support. If denotes elements with finite support
See Theorem 4.4, Corollary 4.6, and Theorem 4.7 from [10].
We can read as ‘for all but finitely many ’, ‘for fresh ’, or ‘for new ’. It captures a generative aspect of names, that for any we can find plenty of atoms such that supp(). was designed in [18] to model the quantifier being used when we informally write “rename in to be fresh”, or “emit a fresh channel name” or “generate a fresh memory cell”.
is a ‘for most’ quantifier [30], and is a generalised quantifier [23, Section 1.2.1]. But importantly, over nominal sets satisfies the some/any property that to prove a -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.
Suppose () is a predicate with free variables .4 Suppose denotes elements with finite support. Then the following are equivalent:
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.
A termlike -algebra is a tuple sub atm) where:
() is a nominal set; we may write this just ;
an equivariant substitution action sub : , written infix []; and
an equivariant injection atm : , usually written invisibly (so we write atm() just as ),
such that the equalities of Figure 1 hold.
1. The set of atoms is a termlike -algebra where atm( and [ and
2. The set is a termlike -algebra where atm(, [, [, and [.
3. First-order syntax generated by the grammar f() for f drawn from some set of function symbols, is a termlike -algebra with atm( and [] is equal to with replaced by . 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(.
[ if .
[) if .
Suppose sub atm) is a termlike -algebra. A FOL-algebra over is a tuple sub) where () is a nonempty nominal set which we may write just , and equivariant functions (Definition 2.7)
conjunction : written (for ()),
negation : written ,
substitution sub : , and
forall : written (for ()),
For the rest of this paper unless otherwise stated we fix some termlike -algebra . and will range over elements of .
We may write:
for (for some fixed but arbitrary ),
for ,
for (),
for , and
for .
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, for every and , thus taking for some 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:
. As a corollary, if # then .
By (E) and by elementary properties of Boolean algebra . The first part follows. For the corollary we use (), taking .
If then and [] []. In words: and [] are monotone.
By we mean . So means (. We use (). The case of [] is similar using (Sub).
supp() supp().
1. [].
2. If and # then .
Proposition 3.9 is an important and a useful sanity check:
is a -greatest lower bound for [] .
# and supp(.
.
3.3 Morphisms
Call a function a morphism when:
Write FOLalg for the category of FOL-algebras and morphisms between them.
We conclude with a simple lemma:
If : is a morphism then (.
By Notation 3.4 is sugar for (for some choice of ). By the morphism properties, (() (). The result follows.
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 is a termlike -algebra then its powerset will naturally have the structure of an -algebra over . Furthermore, the powerset of its powerset will regain a -algebra structure over . So, arises from the fact that in ‘powerset of ’, the is in a negative position.
Suppose sub atm) is a termlike -algebra. A -algebra over is a tuple sub) of:
A nominal set () which we may write just as ; and
an equivariant substitution action sub : , written infix [];
such that the equalities in Figure 1 hold.
Predicates of first-order logic (part 4 of Example 3.2) are a -algebra, where is terms and is predicates. They are not termlike.
Given -algebras and over a termlike -algebra , the nominal set with the pointwise action ()[[][]) for and , is a -algebra. Write this just . In particular, if is a termlike -algebra then is a -algebra, but not a termlike one.
A similar story can be told for disjoint sum .
Further exploration of the structure of -algebras is deferred to a later paper.
We construct an example of an -algebra. We will use Definition 4.5 in Subsection 5.3.
Suppose that ( sub) is a -algebra over a termlike -algebra sub atm) (Definition 4.1). Give finitely-supported subsets the pointwise action
Definition 4.5 determines an -algebra.
We verify the two properties in Figure 5:
Property (Busid). We reason as follows:
Property (Bus). The proof is similar, using (Sub). Suppose #. We reason as follows:
We conclude with another important pointwise action:
For Lemmas 4.8 and 4.9 we continue the notation of Definition 4.7, so that in particular and range over subsets of .
()[([]) and ()[([]).
For the first part we note that ()[] if and only if [] if and only if ([]). The second part is similar.
()[ ([]).
By a routine argument on sets like that the proof of Lemma 4.8.
4.2 pow () is a sigma-algebra
Continuing the notation from the previous subsection, suppose ) is an -algebra over a termlike -algebra . We fix for the rest of this section.
Define an algebra (() sub) by setting () to be the set of with permutation action and substitution action [] from Definition 4.7 such that:
1. has finite support.
3. For every , [))[].
Some comments on Definition 4.10:
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 is a -algebra (Proposition 4.14) and indeed is a FOL-algebra (Theorem 4.21).
(()) is equal to pow(()); the nominal powerset of finitely-supported subsets of with the pointwise action defined in Example 2.6.
We first prove that () is closed under the substitution action; this is Corollary 4.13 and it uses the substitution lemma for ():
Suppose () and . Then
We reason as follows:
By construction [] , 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 #.
Finite support of [] is immediate from Theorem 2.13.
For fresh (so #), [][[]. We reason as follows:
For fresh (so #) [][)([]))[]. We reason as follows, where we choose and fresh (so # and #):
Recall from Definition 4.10 the definition of (), from Definition 4.1 the definition of a -algebra, and from Definition 4.7 the pointwise substitution action []. Then:
() is a -algebra under the pointwise substitution action.
By Corollary 4.13 the substitution action does indeed map to () 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.
4.3 pow () and quantification
Now we are able to exhibit universal quantification as an infinite intersection, and existential quantification as an infinite union.
Suppose ) is an -algebra over a termlike -algebra .
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.
Suppose () and . Suppose #. Then:
1. (all )[ all ([]).
2. (exist )[ exist ([]).
Suppose (). Then
As a corollary, #all and #exist .
The corollary follows by part 3 of Corollary 2.11. For the first part, we reason as follows:
Again, the case of exist is similar.
Suppose (). Then all exist ().
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 is fresh (so #) and suppose . Using Lemma 4.17 suppose without loss of generality that #. Then we can reason as follows:
3. Suppose is fresh (so #) and suppose . Using Lemma 4.17 suppose without loss of generality that #. Then we can reason as follows:
4.4 pow () 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 ) is an -algebra over a termlike -algebra .
Suppose ().6 Then:
1. all (all ) all and exist (exist ) exist .
2. If # then all (all ) and exist (exist ) .
3. If then all all and exist exist .
4. If # then all and exist .
If () then () for every [] all .
We need to check the three conditions in Definition 4.10 for each construct.
The case of . By Theorem 2.13 has finite support. Suppose is fresh, so # , and suppose . By Lemma 4.8 and condition 2 of Definition 4.10 ()[[]) ([ . Now suppose is fresh, so # , and suppose . We reason as follows:
The case of . By Theorem 2.13 has finite support. Suppose is fresh, so #, and suppose . By Lemma 4.9 and condition 2 of Definition 4.10, ()[([. Suppose is fresh, so #, and suppose . We reason as follows:
In the final step we use the fact that ().
The case of [] is Corollary 4.13.
The case of all is Proposition 4.18.
Suppose ) is an -algebra over a termlike -algebra . Then (pow()- sub all) is a FOL-algebra.
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 , we can embed it in a suitable notion of a ‘powerset of the powerset of ’, or to be more precise: the “-powerset of the -algebra of maximal filters of ”.
5.1 Filters
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 -quantifier)—that is, even though 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 ([] ) ? Remarkably, this apparently stronger condition follows: see Proposition 5.6.
In fact the condition is also familiar from another context. By Theorem 2.16 it is equivalent to #.7 This looks like (an abstract version of) the sequent -right introduction rule, especially if we write as and think of supp() as ‘the free atoms of ’:
This also suggest a syntactic intuition why ([] ) is the weaker condition: just because all ground instances of a predicate are derivable, does not mean that is derivable. We need to derive with in it as a generic element. But remember, this is an analogy: is not a sequent and is not a predicate.
Suppose is a FOL-algebra. Call up-closed when and implies .
If is a filter then is up-closed.
Recall that is sugar for . The result follows using condition 2 of Definition 5.1.
If is a filter and then .
From (E) and Lemma 5.4.
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 :
Suppose is a filter. Then
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.
If and then is a filter.
The interested reader might like to compare Definition 5.7 with [11, Definition 6.5], which gives the right notion of for a representation theorem for a nominal algebraic axiomatisation of the -quantifier . This takes supp()supp(. We need because it is not the case that # implies . In contrast, in this paper for , it is the case that # implies .
The axioms that lead to this difference in behaviour are ((E) from Figure 4) versus ((Selfdual) from [11, Figure 1]).
We now set about showing that every filter is contained in a maximal filter (Theorem 5.18). We use Zorn’s lemma.
Suppose is a filter and #. Then if and only if .
By assumption has finite support so supp() is finite even if is not. Also, by Proposition 3.11 the order of the does not matter.
Suppose is a filter and suppose . Define supp() supp() and write (Definition 5.12). Then:
1. is a filter.
2. .
3. .
We check the conditions in Definition 5.1:
. Suppose . This implies , which by Lemma 5.11 contradicts our assumption that .
. Suppose . This means that and . It is a fact of distributive lattices that this happens if and only if (). The reverse implication is similar.
. Suppose is fresh (so #) and suppose . By definition, . By Lemma 5.11 () . By assumption #, so by Lemma 3.7 and () we know () . It follows that as required.
Now suppose . By Lemmas 5.4 and 5.11 () . It follows that . Finally, and it follows that () and so .
is maximal if and only if .
Suppose and ; we derive a contradiction. By Lemma 5.14, is a filter and and , a contradiction.
We mention a nice corollary:
Suppose is a maximal filter and #. Then if and only if .
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 , and supp() supp() imply ).
The left-to-right implication is trivial. Now suppose is maximal amongst filters with no greater support. By Proposition 5.15 it suffices to show that if and only if .
and is impossible by conditions 1 and 2 of Definition 5.1. Now suppose and also . We derive a contradiction. Write supp(). By Lemma 5.14, is a filter and and . By Theorem 2.13 supp() supp() and so , a contradiction.
For every filter , there is a maximal filter with .
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 over a termlike -algebra . Recall from Definition 4.5 the pointwise action, which on filters of yields [[] .
If is a filter of then so is [] (Definition 4.5). Thus, the action does indeed map from filters to other filters.
By construction in Definition 4.5, [] . By Theorem 2.13 supp([]) supp() supp() so supp([]) has finite support. We check the other conditions in Definition 5.1:
[]. By (Sub#) and Lemma 3.10 [. By assumption .
Suppose is fresh (so #[]). By Definition 4.5, [] if and only if [] . By condition 3 of Definition 5.1 this implies ([]) . By (Sub) ([ ()[]. The result follows.
If is a maximal filter then so is [].
The set of all maximal filters (or points) of with the action of Definition 4.5 is an -algebra.
Note of -algebras two non-theorems:
It is not necessarily the case that if is a filter and # then [))[].
It is not necessarily the case that if # then [.
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 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 is a FOL-algebra over a term-like -algebra . will range over and will range over .
Our main result is Theorem 5.30, which injects into the powerset of its points. Exactly as anticipated and desired, is interpreted as an infinite sets intersection all.
Define points() to be the -algebra with
underlying set points() is a maximal filter and
the action from Definition 4.5.
We may call a maximal filter in a point.
points() with the pointwise action (Defn. 4.10) is a nominal set.
Define the canonical extension (points()) (Definition 4.10) so that:
and will range over elements of .
Note that the definition of [] is the pointwise action from Definition 4.7.
With the results we have so far, we get Proposition 5.26 instantly:
is a FOL-algebra.
This is just a rephrasing of Theorem 4.21.
- from Definition 5.27 does indeed map to .
We check each of the properties in Definition 4.10:
1. It follows from Theorem 2.13 that supp() supp().
2. Suppose #. Then ()[] if and only if [] if and only if (by (Sub#)) .
3. Suppose #. Then (()())[] if and only if ()([]) if and only if (())[] if and only if (by (Sub)) [] if and only if [] if and only if ()[].
Suppose is a FOL-algebra over a termlike -algebra and suppose and . Then:
1.
2. () points() and as a corollary () ,
3.
4. () all () and () exist (), and
5.
As a corollary from Definition 3.12, - is an arrow from to in FOL.
We consider each property in turn:
1. Proof that () . Since by assumption in Definition 5.1 if and only if and .
2. Proof that () points(). We reason as follows:
3. Proof that ([]) []. We just unfold definitions:
4. Proof that () all () and () exist (). Choose some points(). We reason as follows:
The second part follows by dualising with sets complement, recalling that is shorthand for .
5.
Suppose is a FOL-algebra over a termlike -algebra and suppose and .
Then - is injective and embeds as a sub-FOL-algebra of .
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.
()[([]).
We reason as follows:
6 Nominal Stone duality
We have proved Theorem 5.30, a representation theorem which exhibits a FOL-algebra 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
Suppose is a termlike -algebra. A -topological space over is a pair () of
an -algebra ) (Definition 4.4) and
a subset pow() of open sets such that:
1. If then [] .
2. and
3. If and then .
4. pow() implies ; we call this a finitely-supported union (recall from Example 2.6 that pow() is a finitely-supported set of open sets).
Call continuous when implies -1().
Call a morphism when:
5. is equivariant (that is, (()).
6. is continuous.
7. commutes with the amgis-action (that is, ()[([]) for all and ).
Write Top for the category of -topological spaces and morphisms between them.
Suppose is a -topological space. Suppose .
Call closed when .
Call clopen when is open and closed.
Call totally separated when for every there is a clopen with and .10
Proposition 6.3 establishes by fairly easy calculations some basic closure properties which will be useful later:
Suppose is a -topological space over a termlike -algebra .
If are clopen then so are , , and [] for .
Suppose and are clopen. We consider each case in turn:
Intersection . Since and are closed, using condition 3 of Definition 6.1 it follows that is too. Since and are open, by condition 4 of Definition 6.1 so is . Thus is clopen.
Complement . This case is similar to the case of intersection.
Substitution []. Since is open, by condition 1 of Definition 6.1 so is []. Since is closed, is open. By Lemma 4.9 ()[ ([]). Therefore [] is also closed.
6.2 The functor from FOLalg to Topop
We are now ready to build a -topological space out of the points of a FOL-algebra . 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:
() is indeed a -topological space.
We consider each of the properties in Definition 6.1 in turn:
If then . By Theorem 2.13.
If then [] . By construction is equal to some finitely-supported union . We use Lemma 5.31.
It is easy to check that and points() are open.
If is finitely-supported then . Each is a finitely-supported union and . By Theorem 2.13 a finitely-supported union of finitely-supported unions is itself finitely-supported, so we are done.
First, we show that () maps ()points() to ()points().
Points are maximal filters, and it is convenient to first show that if is a filter (not necessarily maximal) then so is -1(), and then show that if is maximal then so is -1().
Suppose 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 -1() if and only if () :
1. () . By Lemma 3.13 (, and by condition 1 of Definition 5.1 .
2. (() () ) () . By assumption (() (). The result follows by condition 2 of Definition 5.1.
3. () () . Suppose is fresh (so #). Choose any . By assumption ((). The result follows by condition 3 of Definition 5.1.
Now suppose that is a maximal filter. By Proposition 5.15 it suffices to show that -1() if and only if -1(). We sketch the relevant reasoning; in step () we use Proposition 5.15 for :
Thus -1() is maximal.
Second, we show that () is a morphism. We need to verify the final three properties of Definition 6.1:
() is equivariant. We briefly sketch the reasoning; in step () we use the assumption that is equivariant (Definition 2.7):
() is continuous. By construction ()-1 preserves unions, so it suffices to show that ()-1((). Again we briefly sketch the reasoning:
() commutes with the amgis-action. Suppose () and . We briefly sketch the reasoning; in step () we use the assumption that commutes with the -action:
We conclude with a technical lemma which will be useful later:
If then () is clopen; that is, and points().
6.3 The functor 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
Suppose is a -topological space.
Call pow() -closed when ( exist ).
Call pow() a cover when .
Call a -cover when is a cover and is -closed.
Call -compact when every -cover has a finite subcover.
If pow() is -closed then so is .
Choose fresh (so #). If then for some . By part 3 of Lemma 4.19 exist () exist and by assumption exist .
Suppose pow() is an -cover (Definition 6.8). Then so is .
By construction in Definition 6.4 every is equal to for some finitely-supported union of , thus is a cover.
Now suppose is fresh (so #) and suppose . It must be that . By assumption is -closed so exist . By part 4 of Proposition 5.29 (exist form) () exist (). By part 3 of Lemma 4.19 exist () exist . It follows that exist () .
Proposition 6.11 motivates -compactness from Definition 6.8:
() is totally separated and -compact.
Consider distinct (). Without loss of generality take . By Definition 5.25, and . So is an open set separating and . By Proposition 5.15 points() ), so is also closed. Thus () is totally separated.
Now consider an -cover pow(). By Lemma 6.10 we may assume without loss of generality that every element of has the form for some . Write
where denotes closure under finite intersections. So has a finite subcover if and only if . We now check that satisfies conditions 2 and 3 of Definition 5.1:
Proof that if and only if . By construction is closed under finite intersections, so and imply . Also by construction is up-closed (Notation 5.3), and it follows that implies and .
Proof that . Suppose is fresh (so #) and . Then there exists an with and (). By Lemma 3.6 . Also (. Now by part 4 of Proposition 5.29 () exist () and by assumption is -closed. It follows that .
If then is a filter and by Theorem 5.18 for some point . It would follow that , a contradiction. Therefore .
6.3.2 Clopens in ()
If and # then () and ().
If and # then () and ().
Suppose . By part 3 of Lemma 4.19 exist exist . By part 4 of Proposition 5.29 () exist and by part 4 of Lemma 4.19 exist since #. It follows that (). The case of is exactly similar.
Suppose . By part 2 of Lemma 4.19 exist , since # and #. We use part 4 of Proposition 5.29 to conclude that (). The case of is similar, using parts 1 and 4 of Lemma 4.19.
If is clopen then for some .
By construction in Definition 6.4 the open sets of () are unions of finitely-supported sets of sets the form . We assumed that and its complement are open, so that
(recall that ()points()). It follows that
is -closed by Lemma 6.12, so by Proposition 6.11 it has a finite subcover, and it follows that there is some finite such that . By part 2 of Proposition 5.29 we have ).
6.3.3 Closure under all and exist
Suppose is a -topological space. Then if is open then exist is open, and if is closed then all is closed.
Suppose is a -topological space. Say has or is with when if is clopen then:
1. all is open, and
2. if and # then all .
If is a -topological space with then clopen implies that all and exist are also clopen.
By Lemma 6.14 exist is open and all is closed. By assumption all is open. Also by assumption all () is open, and it follows that exist is closed.
() has .
Suppose is clopen. By Proposition 6.13 for some . We consider each condition of Definition 6.15 in turn:
1. By part 4 of Proposition 5.29 all ) and it follows in particular that all is open.
2. Suppose is a filter in and and #. Thus, and #. By condition 3 of Definition 5.1 , that is, (). Again we use part 4 of Proposition 5.29 and the result follows.
6.3.4 Nominal -Stone space
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.
is a functor from FOLalg to Stoneop.
6.4 The functor from Stoneop to FOLalg
Map Stone to a () FOLalg defined by:
() is clopen.
, , and are interpreted as intersection, complement, and all.
Given : in Stone define () : () () by ()((), that is:
Suppose is a nominal -Stone space. Then () is indeed a FOL-algebra.
Suppose and are -topological spaces and : is a morphism. Then if is clopen then so is ()() .
By assumption since is open, so is -1(). Also by assumption since is open, so is -1( -1().
is a functor from Stoneop to FOLalg.
By Lemma 6.21 maps objects of Stoneop to objects of FOLalg.
Now consider a morphism : ; we must show that ()—that is, —is a morphism of FOL-algebras. So we must show that maps clopens in to clopens in and satisfies the commutations listed in Definition 3.12.
If is clopen then by Lemma 6.22 so is (). It is not hard to check that preserves intersections and complements. We show that is equivariant and commutes with all. Suppose is clopen in ; we reason as follows:
Thus () is a morphism in FOLalg.
6.5 The equivalence
() is equal to and the map - defines an isomorphism between and ().
Suppose Top is -compact. Suppose is a filter in (). Then .
We unpack the properties of . It is a finitely-supported set of clopen sets in such that:
.
If then .
If and # then all .
If then is an -cover of . Since is -compact this -cover has a finite subcover, thus some finite intersection of elements of is empty, contradicting that .
Suppose Top has (Definition 6.15). Then is a filter in ().
Suppose Top is totally separated and . Then implies .
By a routine calculation.
Suppose Top has and is totally separated and -compact; that is, suppose Stone. Then is a maximal filter in () if and only if for some .
Suppose is a maximal filter in (). By Lemma 6.25 there is some such that for every , so that . By Lemma 6.27 is a filter, so by maximality , and we are done.
Now consider ; by Lemma 6.27 this is a filter and we need to show that it is maximal. Suppose . By Lemma 6.25 () for some . It follows by Lemma 6.28 that and so .
If we give the pointwise -action from Definition 4.5 then [[]).
If Stone then - defines an isomorphism between and (), and is a morphism of -topological spaces.
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 in (), that is of where is a clopen in ().11
Thus, (.
Now by construction any open set in () is a union of , and preserves these unions. It follows that the inverse image of an open set is open.
: Stone FOLalg defines an equivalence between FOLalg and Stoneop.
We use [24, Theorem 1, Chapter IV, Section 4].
is essentially surjective on objects. This is Proposition 6.24.
is faithful. Suppose : Stone and ; that is, there exists such that () (). By assumption is totally separated, so there is a clopen with () and () . Examining Definition 6.20 we see that ()() and ()(). Thus, () ().
is full. Given in Stone and : () () in FOLalg we construct a morphism : in Stone such that (. By Proposition 6.31 : () mapping to is an isomorphism in Stone. Set () . By routine calculations we can check that ()(() for every ().
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 -quantifier— 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 ; notably we must account for substitution, which is not relevant in the case of . 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 here corresponds to a distinct term-former for each , 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 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 -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 -quantifier. In this paper we treated the universal quantification of first-order logic—if it was not surprising that the ‘nominal’ quantifier has a ‘nominal’ representation, it is more striking that the ‘traditional’ quantifier has a similar ‘nominal’ representation.
To take this further we can consider 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]. ↩
must contain all the variables mentioned in the predicate. It is not the case that if and only if —but it is the case that if and only if . ↩
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 () is a -algebra with underlying set certain ‘good’ subsets of , with the pointwise substitution and permutation actions. So writing ‘()’ is just a fancy way of saying “ is a well-behaved subset of , with pointwise permutation and substitution actions”. ↩
7The version using is preferable over the version using and #, because leaves us free to choose fresh for any other variables in our reasoning context at the time we need to verify the condition. This is the advantage of : 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 with its standard topology, in which the interval [0 1] is closed. 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). ↩
is the set of maximal filters of clopens of that contain . ↩
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 , not . Also, the axiomatisations in this paper, from Figure 1 to Figure 5, are finite. ↩