Semantics out of context: nominal absolute denotations for first-order logic and computation
Call a semantics for a language with variables absolute when variables map to fixed entities in the denotation. That is, a semantics is absolute when the denotation of a variable is a copy of itself in the denotation.
We give a trio of lattice-based, sets-based, and algebraic absolute semantics to first-order logic. Possibly open predicates are directly interpreted as lattice elements / sets / algebra elements, subject to suitable interpretations of the connectives and quantifiers. In particular, universal quantification is interpreted using a new notion of ‘fresh-finite’ limit ⟦⟧ and using a novel dual to substitution.
The interest of this semantics is partly in the non-trivial and beautiful technical details, which also offer certain advantages over existing semantics—but also the fact that such semantics exist at all suggests a new way of looking at variables and the foundations of logic and computation, which may be well-suited to the demands of modern computer science.
Categories and Subject Descriptors: F.4.1 [Mathematical Logic]: Set Theory; F.4.m [Mathematical Logic]: Universal algebra and first-order logic; F.3.2 [Semantics of Programming Languages]: Algebraic approaches to semantics
Additional Key Words and Phrases: Nominal algebra, semantics, variables, first-order logic, mathematical foundations, sigma-algebra, amgis-algebra, fresh-finite limits, nominal lattices
I am very grateful to Nachum Dershowitz and to two excellent anonymous referees.
1. INTRODUCTION
We give three nominal absolute semantics to first-order logic with equality, based on lattices, sets, and algebra in a nominal universe. Thus we provide alternatives to the de facto standard semantics based on valuations, and in doing this we question deep-seated mathematical habits in syntax and semantics, and give evidence that the correct environment for doing logic in computer science is a mathematical foundation with names, modelling variables, building on the foundational work of Fraenkel and Mostowski.
We treat first-order logic because this is a paradigmatic formal language with variables. It is probably the simplest language with variables of any importance; and, it is of great importance, since it is a language for axiomatising set theory and arithmetic, amongst other things.
The expert and impatient reader, wanting to see just how our models really differ from valuation-based models, might like to skip right to Remark 8.2.16. This is not the most technically advanced part of the paper, but it expresses a point at which we can see one concrete way in which the nominal models are clearly not just a rephrasing of standard constructions. Such a reader might also browse Subsection 1.3, which maps out the underlying mathematics, and consider Example 3.4.11.
We now take a step back and discuss the background issues in more depth.
1.1. What are variables?
Variables and quantifiers (or more generally, binders) are widespread. The integral is a binder which binds , so that in () is bound. The same phenomenon appears in logic and computation, so that e.g. we write (), , let in , and so on.
Our notation for integration has an intended meaning: integration of the function. In logic and computation there are many binders, and much design freedom in interpreting them. The choices we make early on will influence the nature of the mathematics that follows out of them.
We will compare and contrast this in detail in the Conclusions, but for here it is probably fair to say that the main methodology is to treat variables as a look-up to an external context; a quantifier interacts with this context by scanning possible values for the variable. For instance:
— () means “take a value for to be fixed by some context and vary possible values for , taking an integral”.
— () means “take a value for to be fixed by some context and vary possible values for , taking a(n infinite) logical conjunction”.
— () means “input a value from the user, associate that value to , and calculate in that context”.
In logic and computation this context of variable-to-value assignments is called a valuation, and the idea is attributed to Tarski [Tar44].
But here are two other semantics of variables and quantifiers:
— We can treat quantifiers as modalities (operators taking a formula and making a new formula), satisfying certain axiomatic properties. Variables are used to label an infinite family of modalities:
This interpretation is useful for proof—a formula may be too complicated to compute, but we can still prove it equivalent to another formula by axiomatic manipulations. In the context of logic, this is exemplified by cylindric and polyadic algebras due to Halmos and Tarski amongst others [Hal06; HMT85].
— We can treat quantifiers as binding sites (distinguished points in the formula), and variables are links/wires connecting different parts of the formula, via the binding site.
This interpretation is useful in programming. For instance, a method name or function declaration binds the invocations of that method or function to the location where it is defined, and a pointer binds a location in memory to the locations in the program where it is dereferenced.
In this paper we investigate a mathematical semantics which builds on and unifies the three interpretations above. This works by reviving an old alternative to Zermelo–Fraenkel sets, known as Fraenkel-Mostowski sets (FM sets)—we will simply call this nominal techniques. Variables have the properties of look-up, and axiomatic-modality, and binding-sites—depending on how one looks at the nominal semantics.
We can do this because we analyse variables using nominal techniques. Detailed discussions of FM sets and their applications to computing are elsewhere [GP01; Gab11; Pit13]. What matters to us here is that in FM sets, atomic symbols are assumed to exist as urelemente or atoms.
In the language of programming we would say that atoms are a datatype whose job is to contain infinitely many elements that are all symmetric up to permutations, and indeed this is exactly what happens in the Mur system [ID96] and the FreshML programming language [SP05]. In some sense, atoms are a polar opposite to the familiar datatype of natural numbers, which is a datatype whose job is to contain infinitely many elements that are all totally ordered in a single fixed and canonical manner.
Atoms are symmetric up to permutations; symmetry is a primitive property of the mathematical universe. To put this in the context of similar axioms, the Axiom of Infinity assumes the infinitude of the natural numbers, the Axiom of Comprehension assumes that predicates can be used to select subsets of sets, and the Axiom of Replacement assumes that functions can be applied pointwise to sets. In FM sets we assume variable symbols, and their purpose is to be symmetric.
Because symmetry properties are foundationally assumed, they propagate naturally to constructions in FM sets. How this works in full generality is a field of study in its own right. What interests us here is what happens when we try to match up FM sets atoms with , , and . That is, can we model the behaviour of variables and binding as special cases of general FM behaviour? This question was answered positively in previous work on abstract syntax, where FM atoms were used to model -equivalence in syntax [GP01].
But now we want to model the more complex semantic behaviour of variables too. We shall find that this works surprisingly well.
At a high level, we shall see that variables are moved from being a specific property of a formal language, which requires explanation on a per-language/per-quantifier basis, to being a generic property of the mathematical universe on a par with generic concepts such as ‘set’, ‘cardinality’, and ‘function’. These can be handled at a high level of abstraction and generalisation, and then instantiated to specific languages and applications.
Doing this is a technical challenge, of course. Just as important as the technical details is the ideas that motivate them. And, because variables and binders are so common in formal languages, and so fundamental to how they work, such new ideas about general semantics can pay worthwhile dividends. The necessary mathematics is not particularly complicated, once we understand that we are dealing with a symmetric datatype with characteristic, albeit deep, properties. The necessary nominal background is handled in Section 2, with plenty of examples and exposition. We now discuss the specific technical application.
1.2. The three paradigmatic semantics
We study the concrete example of first-order logic (FOL). This is a paradigmatic language with binders, and is of practical importance since it is a base language for set theory and arithmetic. The basic FOL connectives are (false), (conjunction), (negation), and (first-order quantification).
FOL has three standard semantics: lattices, sets, and algebra (a fourth is topology, which is handled in a sister paper [Gab14]). We will briefly summarise how these work:
— In lattices we take a partially ordered set and explain connectives using limits. By this semantics we take some underlying set of truth-values with an entailment ordering and assume greatest
lower bounds (and some other structure). Given we declare to be the greatest lower bound (the limit) of and .
— In sets we take some underlying set and explain connectives by combining subsets of the underlying set (sets intersection, complement, and so on). That is, we take some set and subsets , and we declare to be .
— In algebra we equip an underlying set with functions satisfying equalities, which should be abstractly specified, and explain connectives in terms of those functions (de Morgan laws, commutativity, associativity, and so on). That is, we take some set and functions , , , and on which must insist certain axioms—the correct axioms for is a major contribution of this paper.
All these semantics are supposed to match up in some suitable sense. The relevant theorems have standard names: going from lattices to sets is a representation theorem; going from algebras to sets is a (sets) semantics; and going from sets back to lattices or algebras is a pair of completeness theorems. We will treat these, establishing nominal lattice, nominal set, and nominal algebra treatments of FOL and indicating how to move between them.
As discussed, by the nominal approach we intepret variables directly as atoms. We call the result absolute because the meaning assigned to a term or predicate will not require any context or valuation; contrast this with the traditional Tarski-style valuation semantics, where the meaning of a term or predicate only exists in the context of a valuation assigning (non-nominal) denotations to the variables. We will also give a detailed comparison with Tarski-style valuation semantics in Section 8, showing how to build one of our models out of a Tarski-style model. This translation will be natural, almost obvious, and it will exhibit a Tarski-style model as a particular special case of our framework (the key idea intuitively is that Tarski-style models are complete in a lattice-theoretic sense, whereas our models are in general only fresh-finite complete, which is a weaker condition which is only expressible in a nominal semantics; see Remark 8.2.16).
Returning to our three inter-translatable denotations, how specifically do we address the problem of variables and binding in each of them? Detailed answers are in the body of the paper, but for the reader’s convenience we give here—not a summary but—some precise pointers to where the key points in those answers will appear:
— In lattices, is a fresh-finite limit (Subsection 4.1). This is a new idea.
— In sets, is characterised twice: as a fresh-finite limit in the powerset considered as a lattive, and as an infinite sets intersection of substitution instances. Theorem 6.4.1 notes that these two characterisations are equivalent.
— This raises an interesting question: since has an absolute semantics in sets (so is interpreted as a set, even if has free variables), then what notion of substitution is given to those sets? Our answer uses -algebras (Subsection 3.1). These are also a new idea.
— In algebras, is an equivariant function satisfying certain axioms. This idea is relatively recent, but has also been studied in previous work. The axiomatisation is reminiscent of the cylindric algebra or polyadic algebra axiomatisations, though it exists in a nominal algebra framework and has its own distinct character. We discuss this in Subsection A.3.
— Lemma 6.2.2 and Proposition 6.2.3 are important technical results.
More discussion is in the body of the paper and in the Conclusions.
1.3. Map of the paper
Section 2 introduces the necessary nominal background. This section need not necessarily be read first, because the results are abstract. However, this investment in abstraction will pay dividends later when it is applied. These applications are explained in detail in Section 2, see especially the discussion preceding Theorem 2.3.2.
In Section 3 we introduce the notion of algebra over nominal sets (i.e. a nominal set with functions on it satisfying nominal axioms). Specifically, we consider - and -algebras. A -algebra abstracts those properties of term- and predicate-syntax having to do with substitution; an -algebra is a dual to this.
Section 4 introduces nominal posets (a nominal poset is a partially-ordered set, built in the universe of FM sets), but then does some new things with the idea: we study fresh-finite limits, how -algebra structure interacts with the partial order, we note that simultaneous -action can also easily be modelled, we specify equality in the poset, and we conclude with the notion of FOLeq algebra. This establishes our lattice-theoretic semantics for first-order logic.
Section 5 spells this semantics out, by declaring first-order logic syntax and defining a formal notion of interpretation. We prove soundness in Theorem 5.2.13.
Section 6 notes the important fact that every -powerset (Definition 3.4.6) is a FOLeq algebra—just as every powerset is a Boolean algebra in Zermelo-Fraenkel set theory. This is our sets semantics.
Section 7 proves completeness of the sets semantics for FOLeq algebras (Corollary 7.3.9). The construction visibly parallels the usual ultrafilter construction, but the details are significantly different, due to all the extra structure: the constructions are in nominal sets; points form an -algebra (not just a set); the set of all points forms a -powerset (not just a powerset); and we treat not only quantification but also equality which requires careful design of the structure of points. In short, all the structure of a usual completeness proof is still there and still evident, along with extra structure relating the richer foundations.
We are used to seeing models of first-order logic using valuations, in Zermelo-Fraenkel sets; we attribute this idea to Tarski. Section 8 translates such models to our nominal framework, and we see that Tarski valuation models were a special case of FOLeq algebras all along. The main result is Proposition 8.2.15. The converse is not true: not every FOLeq algebra can be expressed as a Tarski valuation model. This is, intuitively, because Tarski models are very complete whereas FOLeq algebras satisfy a weaker property of being only fresh-finite complete in general. What makes this interesting is that in our lattice semantics, being fresh-finite complete captures exactly what is necessary to model first-order logic; so FOLeq semantics are in this sense canonical, and the extra strength of Tarski-style models is due to the relative inexpressivity of the Zermelo-Fraenkel sets foundation which, implicitly, it assumes.
Another standard semantics is syntax-quotiented-by-derivable-equivalence. We call this a Herbrand (or Lindenbaum-Tarski) semantics and we consider it in Section 9. We do this briefly since, by now, the result should be clear; enough detail is given to reconstruct full proofs if desired.
The algebraisation of FOLeq algebras—their equational axiomatisation—is not without interest or subtlety, but it is also rather easy and has in fact already been treated in previous work [GM06b; GM08c].1 So we treat it in a brief appendix, Appendix A.
2. BACKGROUND ON NOMINAL TECHNIQUES
Intuitively, a nominal set is “a set whose elements may ‘contain’ finitely many names ”. We may call names atoms. The notion of ‘contain’ used here is not the obvious notion of ‘is a set element of’: formally, we say that has finite support (Definition 2.1.8).
For instance, here are some nominal sets:
— The set of finite sets of atoms:
— The set of complements of finite sets of atoms:
Nominal sets are formally defined in Subsection 2.1, and examples are in Subsections 2.2 and 2.4.
What is most important to realise is that the notion of ‘being in the support of ’ is not equal to the notion of ‘being a set element of ’. For instance if we take , then contains infinitely many elements—but its support contains precisely the atom that is not an element of , namely .
Support measures name-symmetry, not name-elementhood. More on this below.
The reader not interested in nominal techniques per se might like to read this section only briefly in the first instance, and use it as a reference for the later sections, where these underlying ideas get applied. More detailed expositions are also in [GP01; Gab11].
In the context of the broader literature, the message of this section is as follows:
— 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 [MM92, Section III.9], [Joh03, A.21, page 79], or [Gab11, 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 (FM sets). A discussion of this sets foundation, tailored to nominal techniques, can be found in [Gab11, Section 10]). FM sets add urelemente or atoms to the sets universe.
— The reader not interested in foundations can note that previous work [GP01; Gab11] has shown that just assuming names as primitive entities in Definition 2.1.1 yields a remarkable clutch of definitions and results, notably Theorem 2.1.11 and Corollary 2.1.12, and Theorems 2.3.2 and 2.3.8. Empirically these properties turn out to be incredibly useful, and they will be just what we need next in Section 3.
2.1. Basic definitions
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 [GP01]) mapping to , to , and all other to themselves, and take (.
If write
(1) 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 .
(2) 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.
The notions of equivariance in Definition 2.1.6 and Theorem 2.3.2 are evidently related; the former existing inside the sets universe and the latter outside out. The notion of equivariance in Definition 2.1.8 looks different, but we shall see in Lemma 2.2.2 how it closely relates to the other two.
Suppose is a nominal set and . Define the support of by
If supp( we call equivariant.
— Write # as shorthand for supp() and read this as is fresh for .
— Given atoms and elements write # as shorthand for supp(. That is: # for every and .
If is finite and supports , and and #, then supports .
Suppose fix(). We assumed # so choose an such that is finite, supports , and . Also, choose some fresh (so ).
Write ). Note that by Definition 2.1.4, because supports and fix(). It is a fact that ()( for every , so fix(). Also by the group action ()(()). Since supports we have (( by Definition 2.1.4.
We apply to both sides, recall that , and conclude that as required.
Suppose is a nominal set and . Then supp() is the unique least finite set of atoms that supports .
(1) If ( for all supp() then .
(2) If (() for every supp() then .
(3) # if and only if (# ()).
By routine calculations from the definitions and from Theorem 2.1.11.
2.2. Examples
Suppose and are nominal sets, and suppose is a set with a permutation action. We consider some examples of sets with a permutation action and of nominal sets. These will be useful later on in the paper.
2.2.1. Atoms.
is a nominal set with the natural permutation action (). For the case of only we will be lax about the difference between (the set of atoms) and () (the nominal set of atoms with its natural permutation action). What that means in practice is that we will write and never write .2
2.2.2. Cartesian product.
is a nominal set with underlying set () and the pointwise action ().
2.2.3. Tensor product.
is a nominal set with underlying set () supp() supp( and the pointwise action. For the pointwise action here to be well-defined depends on being a permutation and the fact (Proposition 2.3.4 below) that supp(supp().
2.2.4. Full function space.
is a set with a permutation action with underlying set all functions from to , and the conjugation permutation action
The conjugation action can be rephrased as ‘permutations distribute’ (cf. Theorem 2.3.2 below):
If then ()().
By easy calculations.
2.2.5. Finitely supported function space.
is a nominal set with underlying set the functions from to with finite support under the conjugation action, and the conjugation permutation action.
We sketch the proof: If then for any we have by Lemma 2.2.1 that (( ()((). Conversely if for any we have ((() then by the conjugation action
2.2.6. Full powerset
Suppose is a set with a permutation action. Give subsets the pointwise permutation action
A useful instance of the pointwise action is for sets of atoms. As discussed in Subsection 2.2.1 above, if then (). Thus if then
Define PowSet() the full powerset of to be the set with a permutation action with
— underlying set (the set of all subsets of ), and
— the pointwise action .
Even if is a nominal set, PowSet() need not be a nominal set. To see why, take to be equal to and consider the set
of ‘every other atom’. This does not have finite support, though permutations still act on it pointwise. For more discussion of this point, see [Gab11, Remark 2.18].
We consider further examples in Subsection 2.4.
2.3. The principle of equivariance and the NEW quantifier
We come to Theorem 2.3.2, a result which is central to the ‘look and feel’ of nominal techniques. It enables a particularly efficient management of renaming and -conversion in syntax and semantics and captures why it is so useful to use names in the foundations of our semantics and not some other infinite set, such as numbers.
Names are by definition symmetric (i.e. can be permuted). Taking names and permutations as primitive implies that permutations propagate to the things we build using them. This is the principle of equivariance (Theorem 2.3.2 below; see also [Gab11, Subsection 4.2] and [GP01, Lemma 4.7]).
The principle of equivariance implies that, provided we permute names uniformly in all the parameters of our definitions and theorems, we then get another valid set of definitions and theorems. This is not true of e.g. numbers because our mathematical foundation equips numbers by construction with numerical properties such as less than or equal to , which can be defined from first principles with no parameters.
So if we use numbers for names then we do not care about because we just needed a countable set of elements, but we repeatedly have to prove that we did not use an asymmetric property like . In contrast, with nominal foundations and atoms, we do not have to explicitly prove symmetry because we can just look at our mathematical foundation and note that it is naturally symmetric under permuting names; we reserve numbers for naturally asymmetric activities, such as counting.
This style of name management is characteristic of nominal techniques. The reader will find it used often, e.g. in Lemmas 3.1.8, 3.4.9, and 6.1.2, Propositions 3.2.6 and 4.2.6, and Definitions 3.3.2, 3.4.1, and 6.3.1.
The languages of ZFA set theory and FM set theory are identical: first-order logic with equality and sets membership .
If is a list , write for . Suppose Φ() is a predicate in the language of ZFA/FM set theory, with free variables . Suppose Υ() is a function specified in the language of ZFA/FM set theory, 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 then supp(Υ()) supp()supp().
See Theorem 4.4, Corollary 4.6, and Theorem 4.7 from [Gab11].
supp(supp() (which means () supp()).
We can read as ‘for all but finitely many ’, ‘for cofinitely 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 [GP01] 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 [Wes89], and is a generalised quantifier [KW96, 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.3.8, which we use implicitly when later we choose a ‘fresh atom’ without proving that it does not matter which one we choose. We will do this often. See for instance the proofs of Lemmas 3.4.9 and 7.1.12 (where we write ‘for fresh ’, we are using the -quantifier) and Definitions 3.3.2, 3.4.1, and 6.3.1 where is made explicit.
It is important to understand that simply means ‘for all but finitely many atoms’. This can be encoded in first-order logic. What makes this quantifier so special is the symmetry property which arises specifically when is applied to symmetric atoms with a background assumption of finite (or more generally, ‘small’) support—i.e. in a nominal context.
So it is not any one piece of the puzzle that makes this work, but how the pieces interact when they are fit together. This is expressed in Theorem 2.3.8:
Suppose Φ() is a predicate in the language of ZFA/FM set theory, with free variables . Suppose denotes elements with finite support. Then the following are equivalent:
Where convenient we may write as .
— Suppose Φ() holds for every atom supp(). By assumption denotes elements with finite support, and it is a fact that a finite union of finite sets is finite, so supp() is cofinite. It follows that Φ() holds.
— Suppose is cofinite and Φ() for every . As in the previous point, there exists some such that # for every 1. It follows that # Φ().
— Now suppose Φ() holds for some supp(). By part 1 of Theorem 2.3.2 Φ(()) holds for any . Choosing # we have by part 1 of Corollary 2.1.12 that () for every 1. Thus # Φ() holds.
It is impossible to overstate the importance and convenience of the -quantifier and Theorem 2.3.8, which appears in the literature for instance as Theorem 6.5 from [Gab11] or Proposition 4.10 from [GP01].
Consider Definition 6.3.1 and the proof of Proposition 6.3.8. In that proof, we use -equivalence to assume is fresh for and . By of the some/any property we can immediately apply Definition 6.3.1.
If we had used a or quantifier in Definition 6.3.1 then we would have had to worry whether the fresh in the proof of Proposition 6.3.8 was the same fresh atom as that used in Definition 6.3.1. ‘Obviously’ this is just a hassle; ‘obviously’ this choice does not matter. Theorem 2.3.8 and the -quantifier capture precisely and succinctly what that word ‘obvious’ means.
2.4. Further examples
We now consider the finitely supported powerset and the strictly finitely supported powerset. These examples are more technically challenging and will be key to the later constructions.
2.4.1. Finitely supported powerset.
NomPow() (the nominal powerset) is a nominal set, with
— underlying set those PowSet() that are finitely supported, and
— with the pointwise action inherited from Definition 2.2.3.
As the name suggests, the nominal powerset is the powerset object in the category of nominal sets [Gab11, Lemma 9.10].
A common source of confusion is to suppose that if supports NomPow() then must support every . This is incorrect:
It is not true in general that if NomPow() and then supp() supp().
It suffices to provide a counterexample. Take (the nominal set of atoms with the natural permutation action, from Subsection 2.2.1) and (the underlying set of the nominal set of all atoms, i.e. the set of all atoms!).
It is easy to check that supp( and and supp(.
Lemma 2.4.1 will lead us to the notion of the strictly finitely supported powerset in a moment. For completeness we take just a moment to mention Lemma 2.4.2, which describes a weaker property than that of Lemma 2.4.1 which is valid in general; see [GM07, Lemma 5.2] and [GM09, Corollary 4.30] for applications, and [Gab13, Lemma 7.6.2] for the more general context.
If NomPow() and # then there exists an with #.
2.4.2. Strictly finitely supported powerset.
Suppose is a nominal set.
Call strictly supported by when
If there exists some finite which strictly supports , then call strictly finitely supported (see [Gab11, Theorem 2.29]).
Write Strict() for the set of strictly finitely supported . That is:
Strict( finite strictly supported by
If Strict() then:
(1) supp() is finite.
(2) supp() supp().
(3) If is strictly finitely supported then it is finitely supported.
(4) implies supp() supp() (contrast this with Lemma 2.4.1).
(5) Strict() with the pointwise permutation action is a nominal set.
The first part is immediate since by assumption there is some finite that bounds supp() for all . The second part follows by an easy calculation using part 3 of Corollary 2.1.12; full details are in [Gab11, Theorem 2.29], of which Lemma 2.4.4 is a special case. The other parts follow by definitions from the first and second parts.
(1) is finitely and strictly finitely supported by .
(2) is finitely supported by and also strictly finitely supported by .
(3) is finitely supported by but not strictly finitely supported.
(4) is finitely supported by but not strictly finitely supported.
3. ALGEBRAS OVER NOMINAL SETS
3.1. Definitions: sigma-algebra and amgis-algebra
Definitions 3.1.1, 3.1.5, and 3.1.6 assemble three key technical structures (see also Definitions 3.2.4 and 3.4.6).
A termlike -algebra is a tuple ) of:
— a nominal set () which we may write just as ; and
— an equivariant -action (), written infix []; and
— an equivariant injection ,
such that the equalities (a), (id), (#), (), and () of Figure 1 hold, where , , and range over elements of . We usually write invisibly (so we write () just as ), and we may omit subscripts (so we may write as sub if we are confident that is clear and understood).
First-order terms form a termlike -algebra:
— Variables are atoms,
— the permutation action is pointwise, and
— the -action is ‘real’ substitution.
Consider for instance a first-order term language for arithmetic: then is a term, () is () (), and ()[2][3] is 2 3. Such a syntax is defined in this paper in Definition 5.1.1 as f()
Similarly, untyped -terms quotiented by -equivalence form a termlike -algebra, where the -action is capture-avoiding substitution. So [([.
Predicates of first-order logic quotiented by -equivalence are not a termlike -algebra under capture-avoiding substitution action for terms because predicates do not belong to the same class as terms . However, predicates do form a (not-necessarily-termlike) -algebra; see Definition 3.1.5.
The ‘’ in -action stands for ‘substitution’. No connection is suggested with the notion of sigma-algebra from measure theory.
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 -action (), written infix [];
such that the equalities (id), (#), (), and () of Figure 1 hold,6 where ranges over elements of and and range over elements of . As for termlike -algebras, we may omit the subscript .
Suppose sub atm) is a termlike -algebra.
An -algebra (spoken: amgis-algebra) over is a tuple ) of:
— a set with a permutation action () which we may write just as ; and
— an equivariant amgis-action (), written infix [],
such that the equality () of Figure 1 holds, where ranges over elements of and and range over elements of . We may omit the subscript .
[] looks like [] written backwards, and a casual glance at () suggests that it is just () written backwards. This is not quite true: we have [] on the right in () and not ‘[]’ (which would make no sense, since has no amgis-action).
Discussion of the origin of the axioms of -algebras is in Subsections 3.2 and 3.4; see also Proposition 3.2.6 and Remark 3.2.7.
We conclude this subsection with some technical lemmas which will be useful later.
Lemma 3.1.8 is a technical corollary of (), and is used in Lemma 5.2.6:
If # then #[]. As a corollary,
The reader should know Lemma 3.1.8 for concrete syntax, which is a -algebra.
For instance, if is a predicate of first-order logic (up to -equivalence) and is a term, then support coincides with free atoms/variables fa(-) and fa([]) (fa()) fa().
But, Lemma 3.1.8 is an abstract property of models of nominal algebra axioms. Syntax is one concrete instance of the abstract class (as natural numbers are a concrete instance of rings).
Lemma 3.1.10 goes back to [GM06a; GM08a], where it was taken as an axiom or the original nominal algebraic treatment of substitution. In the presence of () it is equivalent to (id); it is useful in the proofs of Propositions 4.2.6 and 6.3.5:
If # then [).
By (id) ()))[]. By () (())[[].
Lemma 3.1.11 will be useful to prove Proposition 4.2.6 and 4.2.8. See also the related Lemma 8.2.8:
If is finitely supported and # then #[] . As corollaries, the following freshnesses all hold:
3.2. Duality I: sigma to amgis
In Subsection 3.2 we explore how to move from a -algebra to an -algebra; we explore the other direction in Subsection 3.4.
Given a -algebra we generate an -algebra out of its subsets. This is Proposition 3.2.6.
Suppose is a -algebra over a termlike -algebra . Suppose . Then:
— [] if and only if [] .
— if and only if .
By easy calculations on the pointwise actions in Definition 3.2.1.
We take a moment to suggest intuitively why Definition 3.2.1 is natural.
The pointwise permutation action is the natural action on subsets, also mentioned in Subsection 2.4.1. This comes from the Fraenkel-Mostowski foundations.
The pointwise -action is its natural generalisation from a group to a monoid (which need not necessarily have inverses). But why amgis? Why does [] get turned round to []?
When we take the powerset of a set , is in negative position (i.e. PowSet() is equivalent to a function-space 2 and here is to the left of the arrow). This implies that any modal operations which we assume on elements of , need to be ‘flipped’. Thus, -algebras turn into -algebras and vice versa. This is why an underlying set with a -action gives rise to a ‘flipped’—a dual—-action on the subsets.
Note that need not have finite support in Definition 3.2.4.
Our notion of -algebra (Definition 3.1.6) admits without finite support. We will need this: the -algebras we construct in Definition 7.2.2 need not have finite support; see the discussion in Remark 7.1.2. The action happens in Theorem 7.1.20 where we use Zorn’s Lemma to make infinitely many choices.
If is a -algebra over a termlike -algebra then Pow() (Definition 3.2.4) is an -algebra over .
It has been suggested that if -algebra algebraises substitution on syntax, then -algebra should algebraise pattern-matching on syntax. This is not quite right; pattern-matching does not satisfy (). Suppose a syntax of terms with pairing () and one unary term-former f. Consider the term (f() f()) and interpret [] as substitution and [] as pattern-matching. Then
and () f()).
The natural examples of -algebras are the -powersets as constructed above in Definition 3.2.4.
3.3. Exact amgis-algebra
We now strengthen Proposition 3.2.6 to Proposition 3.3.3, which states that Pow() is an exact -algebra (Definition 3.3.2).
Exactness will be useful later to interpret equality in ; see Subsection 6.3 and in particular Lemma 6.3.4.
To understand exactness, it is interesting to consider an easy property of -algebras:
If # then [[] implies .
Immediate from (#).
We cannot hope to replicate the proof above directly for -algebras using an axiom (#) because, as noted in Remark 3.2.7, we do not want such an axiom.
But is a kind of dual to , and exactness is a kind of dual to Lemma 3.3.1. Recall the definition of -algebra from Definition 3.1.6 and the -quantifier from Definition 2.3.5.
In words, is exact when for every , , and , if [] and [] are equal for most (meaning ‘for all but finitely meany’) then and are equal.
Suppose is a -algebra over a termlike -algebra . Then Pow() is an exact -algebra over .
By Proposition 3.2.6 Pow() is an -algebra over . It remains to prove exactness.
Suppose Pow() and , and suppose [[]. We now check that for all it is the case that if and only if . We reason as follows:
So suppose and [[]. This means that for all but finitely many atoms it is the case that for every , [] if and only if [] . In particular for every there exists some such that if and only if . Thus, and are equal.
Note that exactness is not an algebraic property (it has the form if ...then rather than the form LHS = RHS). So although the class of all -algebras is algebraic, the class of exact -algebras is not.7 This will not be a problem.
3.4. Duality II: amgis to sigma
In Subsection 3.2 we showed how to build an -algebra out of a -algebra. Dually, we can build a -algebra out of an -algebra; this is a little harder because, while we are free to define -algebra to suit ourselves, the notion of -algebra is already quite fixed by the behaviour of substitution, which it is intended to model. The set of all finitely supported subsets is too large, so Definition 3.4.6 cuts this down with additional conditions 1 and 2.
3.4.1. The pointwise sigma-action on subsets of an amgis-algebra
Suppose is an -algebra over a termlike -algebra and suppose . Then if # then [))[].
Lemma 3.4.5 is useful, amongst other things, in Lemma 3.4.9. On syntax it is known as the substitution lemma, but here it is about an action on sets , and the proof is different:
Suppose is an -algebra over a termlike -algebra and suppose . Suppose . Then
We reason as follows, where we write ) ():
3.4.2. The -powerset Pow().
Recall from Subsection 2.4.1 the finitely supported powerset NomPow() of a nominal set .
Lemma 3.4.7 rephrases conditions 1 and 2 of Definition 3.4.6, in a simpler language, albeit one which requires the -action on subsets of an -algebra from Definition 3.4.1:
Suppose (). Then [.
By construction [] , so we now check the properties listed in Definition 3.4.6.
By assumption in Definition 3.4.6, is finitely supported. Finite support of [] is from Theorem 2.3.2.
We check the conditions of Definition 3.4.6 for []:
(1) For fresh (so #), [][[]. We use Lemma 3.4.4 to assume without loss of generality that #. It suffices to reason as follows:
(2) For fresh (so #) [][)([]). It suffices to reason as follows:
If is an -algebra over a termlike -algebra then () (Definition 3.4.6) is a -algebra over .
Consider some set of terms considered as a termlike -algebra over themselves (Example 3.1.3; so [] is with substituted for ). Write this .
By Propositions 3.4.10 and 3.2.6 (Pow()) is a -algebra over .11 It has Boolean structure given by sets intersection and complement, and by design it has a -algebra structure.
So perhaps (Pow()) is a model of first-order logic with equality; it is a -algebra so we might model quantification an infinite sets intersection. How to interpret equality is less obvious ...but we might be lucky.
In the rest of this paper we make this formal, prove it, and put the result in the context of the other models: in nominal posets, using maximally consistent sets (for the completeness result), Tarski-style valuation models, and Herbrand models. If the reader holds on to the idea that
to a first approximation this paper is about abstracting, axiomatising, and analysing the behaviour of (Pow()),
then they should not go too far wrong.
3.5. Brief interlude: simultaneous sigma- and amgis-actions
In Subsection 3.1 we only defined a -action [] for a single atom at a time. From Subsection 4.3 and onwards it will be useful to consider a simultaneous -action. In fact the axioms of Figure 1 give us the power of a simultaneous action, for (but not , that is not [], as we shall observe).
Suppose is a -algebra over a termlike -algebra .
Suppose and suppose are distinct atoms not in supp(). Then for define
We need to show that Definition 3.5.1 does not depend on the order in which we take the . This follows using () and (), and (#), because we assumed that each is not in supp().
Now we extend this to the case where the are not necessarily fresh for the :
Suppose and suppose are any distinct atoms. Then for define
where we choose fresh (so not in supp() supp()).
The choice of fresh and the order of the in Definition 3.5.2, do not matter.
By routine calculations using (), (), and (#).
It is natural to try to duplicate Definition 3.5.2 and Lemma 3.5.3 for -algebras. Suppose is an -algebra over a termlike -algebra . Lemma 3.5.4 is a partial dual to Lemma 3.5.3 and has a simple proof:
Suppose and . Then
We reason as follows:
Lemma 3.5.4 asserts that the atoms provided are ‘sufficiently fresh’, then the order of the -action does not matter. However, we cannot freshen atoms as we can for -action using () from Figure 1— that is, there is no rule () of the form . Lemma 3.5.5 is the closest we can get to such a result. We mention it without proof:
Suppose is a finitely-supported -algebra (so every has finite support) and is a -algebra over a termlike -algebra and suppose . Then:
(1) If () and # and and # then [] if and only if ()([]) .
(2) If and # and Pow() then [] if and only if ()([]).
4. NOMINAL POSETS
4.1. Nominal posets and fresh-finite limits
A nominal poset is a tuple ) where
— () is a nominal set, and
— The relation is an equivariant partial order.12
Call finitely fresh-complete or say it has fresh-finite limits when for every finite subset and every finite set of atoms the set of -fresh lower bounds
has a -greatest element , which we may call the #limit (-fresh limit) or #greatest lower bound of .
Similarly call finitely fresh-cocomplete or say it has fresh-finite colimits when for every finite and as above the set of -fresh upper bounds
has a -least element , which we may call its #colimit or #least upper bound of .
Predicates of first-order logic quotiented by derivable logical equivalence and partially ordered by logical entailment, form a nominal poset; that is [] is the derivable equivalence class of and [] [] when . The permutation action is pointwise on variable symbols.
Then it is a fact that [] is a limit for [] [] and [] is an #limit for []. We sketch this particular example in a little more detail in Section 9.
Suppose ) is nominal poset. Suppose and are finite and suppose .
— Call a limit or greatest lower bound of .
— Call the #limit or #greatest lower bound of and write it . Unpacking Definition 4.1.1,
— Call a colimit or least upper bound of .
— Call the #colimit or #least upper bound of and write it .
— Write for the greatest lower bound and for the least upper bound of the empty set .
— Write for the greatest lower bound and for the least upper bound of .
So #(co)limits generalise (co)limits; if we take then we get a limit (greatest lower bound) just as we are used to.
There is a convenient factoring of ‘finitely fresh-complete’ into three constituent parts:
Suppose is a nominal poset. Then is finitely fresh-complete if and only if it has limits of the following three forms:
— , a greatest element (limit for the empty set ).
— , a limit for .
— , an #limit for .
Similarly finitely fresh-cocomplete is equivalent to having , , and .
The interesting part is the right-to-left implication where is non-empty. Given finite non-empty and , it is not hard to verify that ( ( ) ) is an #limit for .
Suppose is a partial order (it need not be nominal, though we will care most about the case that it is). Call a complement of when and .
If every has a complement say that is complemented, and write the complement of as .
Fresh-finite (co)limits, and complements, are unique if they exist, and .
Using the fact that for a partial order, and imply .
Suppose ) is a nominal poset.
(1) Suppose is finite and , and exists. Then supp()supp() .
(2) Suppose , and suppose exists. Then supp( supp().
Lemma 4.1.9 is -equivalence for fresh-finite limits:
Suppose is a nominal poset and .
If # then () and (), where and exist.
We will concentrate on limits from now on; the case of colimits is dual and in the presence of negation can be obtained directly from limits. A sequel to this subsection—which we postpoone until we need it later—is in Subsection 8.2.2.
4.2. -algebra structure and fresh-finite limits
Suppose a finitely fresh-complete and finitely fresh-cocomplete nominal poset ) is also a -algebra ( ) over a termlike -algebra . Call the -algebra structure monotone when for every and
and compatible when for every finite and and
As standard, negation converts greatest lower bounds to least upper bounds. Thus we obtain as . So the second condition above follows from the first and third.
Given a finitely fresh-complete nominal poset with a compatible -action:
(1) ()[[] ([]) and similarly for .
(2) If then [] [] (so a compatible -action is monotone).
(3) If # then ()[([]) and similarly for .
(4) [ and [.
Parts 1, 3, and 4 are special cases of compatibility.13 Part 2 follows from part 1 using the fact that if and only if .
In a finitely fresh-complete nominal poset:
— If and # then .
— If the -action is monotone then if and # then [] for every , so that is a lower bound for the (in general infinite) set [] .14
The first part is direct from the definition of fresh-finite limit; is by definition a least upper bound for all such that #.
For the second part, since the -action is monotone [] [] for every . By (#) also []. It follows that [] for every .
Clearly, we intend the #limit to model the universal quantifier , just as the finite limit models logical conjunction .
An odd thing about the quantifier rules is that (L) expresses as a greatest lower bound of an infinite set [] all whereas (R) expresses as something else and more finite (these standard derivation rules feature in this paper in Figure 2). Lemma 4.2.4 explains this dual nature of as an equality between
— the limit of a fairly large set of elements [] —nice for an elimination rule, so we can eliminate for many —and
— the (fresh-)finite limit of the singleton set —nice for an introduction rule, giving us but a single proof-obligation.
See also Proposition 4.2.6 and Subsection 6.2.
Proposition 4.2.6 proves an equality between the infinite greatest lower bound [] and the (fresh-)finite greatest lower bound , provided one of these exists and the -action is monotone. That is, the limit of a diagram over infinitely many elements [] is equivalent to the #limit of just .
Suppose is a nominal poset with a monotone -action15 and . Then:
(1) If exists then so does [] the limit for [] , and they are equal. In symbols:
(2) If [] exists then so does , and they are equal.
Suppose exists.
— By Lemma 4.2.4 is a lower bound for [] .
— Now suppose is any lower bound for [] . So [] for every . Note that we do not know a priori that #. Choose fresh (so #) and take . Then [] L (). We assumed that has an #limit so by Theorem 2.3.2 also () has a #limit (which by Lemma 4.1.9 is equal to the #limit of ). Since # it follows that ().
It follows that [].
Now suppose [] exists. By Lemma 3.1.11 and part 2 of Theorem 2.3.2 we have that # [].
— By assumption [] [] . Thus [] is an #lower bound for .
— Now suppose and #; we need to show that []. This is direct from Lemma 4.2.4.
It follows that [.
Note that Proposition 4.2.6 does not mean ‘finitely fresh-complete = complete’, where being complete means having limits for all sets (or rather, all finitely supported sets). Proposition 4.2.6 only shows that ‘finitely fresh-complete’ is the same as ‘complete for sets that can be expressed as a finite union of sets of the form [] ’.
We briefly mention another characterisation of using a ‘smaller’ conjunction, though we never use it:
Suppose is a nominal poset with a monotone -action and . Then:
(1) If exists then so does [] where ranges over all atoms, and they are equal.
(2) If [] exists then so does , and they are equal.16
4.3. Equality
Suppose is a finitely fresh-complete nominal poset17 with a compatible -algebra structure over a termlike -algebra .
An equality is an element () with supp() and such that:
(1) For every ,
(2) For every and ,
It might interest the reader to look briefly ahead to Definition 6.3.1, where a very special and useful equality element will be constructed.
The choice of and is arbitrary (simultaneous -action [] is from Definition 3.5.1).
Anticipating the notation of Definition 5.2.5, if we write ()[] as () then properties 1 and 2 of Definition 4.3.1 can be rewritten in the following more economical form
and this looks like a purely equational rendering of the sequent rules R) and L) of Figure 2 (sequent rules for equality). This is deliberate; see condition 5 of Theorem A.3.1.
In Definition 4.3.1 we talk about an equality. However—in the same spirit as Lemma 4.1.7—if one such element exists then it is unique:
An equality in is unique, up to choice of and , if it exists.
Consider two equalities and . Take ) and and in condition 2 of Definition 4.3.1. Then using (id),
Now by condition 1 for () we know that ()[. It follows that () (). By symmetry also () () and we are done.
It is not hard to similarly prove that equality is reflexive, symmetric, and transitive, if it exists.
4.4. Definition of a FOLeq algebra
Suppose is a finitely fresh-complete and finitely fresh-cocomplete nominal poset (Definition 4.1.1).
Call distributive when:
(1)
(2) If # then (().
These two conditions can be unified into a single condition as follows, for finite and :
Evidently, Definition 4.4.1 generalises the usual notion of distributivity. A dual version of part 1 of Definition 4.4.1 is () () and by a standard argument [DP02, Lemma 4.3] the two are equivalent.
A dual version of part 2 of Definition 4.4.1 is that if # then ((). This is not equivalent to part 2 of Definition 4.4.1 in general, but in the presence of complements it is, just by taking negation.
A FOLeq algebra over a termlike -algebra is a nominal poset with the following properties:
— is finitely fresh-complete and finitely fresh-cocomplete.
— is distributive.
— is complemented.
— has a compatible -algebra structure over .
— has an equality.
If is as above except that it does not have an equality, then we call a FOL algebra.
For the reader’s convenience we break down Definition 4.4.3 with precise references:
— Nominal poset and finitely fresh-(co)complete are Definition 4.1.1.
— Distributive is Definition 4.4.1.
— Complements are Definition 4.1.6.
— -algebra structure is Definition 3.1.5 and
— Compatibility is Definition 4.2.1.
— Having equality is Definition 4.3.1.
As the name suggests, the notion of FOLeq algebra is an abstract nominal specification of what it is to be a model of first-order logic with equality. The connection between this definition and first-order logic is surely clear:
— finitely fresh-(co)complete gives us , , and , which are nominal algebraic versions of conjunction, disjunction, and universal and existential quantification;
— distributivity ensures that fresh-limits and fresh-colimits interact sensibly—generalising the distributivity we expect of Boolean algebras;
— being complemented gives us negation;
— the compatible -algebra structure gives us a ‘substitution action’; and
— equality gives us equality.
We do not actually need to insist that a FOLeq algebra be finitely fresh-cocomplete, because we have complements. However, we still need to insist on distributivity, and this axiom is easier to write down if we assume (no complicated nested negations). We try to optimise for readability, even where this implies a little redundancy.
However, note that Definition 4.4.3 is not just a direct restatement of the axioms of first-order logic. This may be hard to see because the reader will see freshness like ‘#’ and substitution like ‘[]’ and these are properties that, usually, only are applicable to syntax. But now, the things we are operating on , , and are abstract and need not be syntax of terms and predicates. Soon, we shall see models built out of -algebras of Definition 4.4.3 that are definitely not syntax-based. It may be worth noting that in previous work we build some more -algebra models, quite differently, out of models of set theory [Gab09b].
In short, Definition 4.4.3 is an abstract, not a concrete, definition.
Calling a FOLeq algebra an algebra might seem misleading. To this author ‘algebra’ suggests an algebraic (equational) treatment, rather than the poset style of Definition 4.4.3. However, a nominal algebraic rendering of Definition 4.4.3 is possible and is given in Subsection A.3. The interesting axioms are the ones that look like the left- and right-introduction rules for the universal quantifier; see () and () from Figure 4.
Here, we express properties of limits, instead of using nominal algebra axioms as we do in Subsection A.3. The content is the same.
5. INTERPRETATION OF FIRST-ORDER LOGIC IN A FOLEQ ALGEBRA
5.1. Syntax and derivability of first-order logic
A signature is a tuple (Σ Π ar) of disjoint sets of
— function symbols f Σ and
— predicate symbols P Π
to each of which is associated an arity ar(f) ar(P) 0 1 2.
Given a signature, terms and predicates are defined inductively by:
Above, ranges over atoms—atoms play the role of variable symbols in this syntax—and f ranges over elements of Σ, and P ranges over elements of Π.
We take predicates up to -equivalence as standard, and define free atoms fa() fa() and capture-avoiding substitution [] and [] also as standard.18
Since our logic is classical, we use the following standard abbreviations:
— Write for (()()).
— Write for ().
— Write for ()().
Φ and Ψ will range over finite sets of predicates.
We may write Φ for Φ and we may write fa(Φ) for fa().
The derivation rules of first-order logic are as standard:
A sequent is a pair of finite sets of predicates Φ Ψ. The derivable sequents are defined by the rules in Figure 2.
5.2. Sound interpretation in a FOLeq algebra
Definition 5.2.1 elaborates and specialises Subsection 2.2.3 (tensor product):
Define to be the set of -tuples of distinct atoms with the pointwise action (()()).
Suppose is a FOLeq algebra over (from Definition 4.4.3; so is a finitely fresh-complete complemented nominal poset, with a compatible -algebra structure over , and with equality ()). We may write also for () the underlying nominal set of the FOLeq algebra.
An interpretation of a signature (Σ Π ar) over is an assignment
— to each f Σ with arity , an equivariant function f : ,
— to each P Π with arity , an equivariant function P : .
(It is not hard to check from Subsection 4.3 that the equality of also gives us an equivariant function , so equality could have been presented as one of the P in the signature, but we took it to be primitive to instead. The treatments of equality and the P flow together in Definition 5.2.5.)
By Definition 2.1.6, f equivariant means f(()(f(). Because of this, the information we need to calculate the output of f for any input, is contained in its output for any one list of distinct atoms. Similarly for P. This can be viewed as a generalisation of the quantifier and has a surprisingly attractive general theory; see the abstractive functions of [Gab07].
In [Gab07] we considered generalisations of nominal sets to other permutation groups, whereas in this paper we are specifically interested in the monoidal case of a -action (the simultaneous -actions form a monoid). Or, to put this more simply: in this paper we can substitute for atoms and not just permute them. This leads us to Definition 5.2.5, for which we first need a little notation:
If is a nominal set write for .
Extend f and P and to functions f : and P : and : as follows
where we choose to be distinct atoms fresh for supp(). We may write () infix as .
Definition 5.2.5 is independent of the choice of fresh atoms and .
supp(⟦⟧) fa() and supp(⟦⟧) fa().
⟦.
Unpacking Definition 5.2.7 and recalling that is sugar for .
(1) f()[ f([][]).
(2)
(3)
— ⟦[⟧[⟦⟧].
—
By a routine induction on and .
— The case of . [ and by (a) ()[⟦⟧.
— The cases of f(), P(), and . This is Lemma 5.2.10.
— The case of . By Theorem 2.3.2 supp(. By (#) [.
— The cases of and . From parts 1 and 3 of Lemma 4.2.3.
— The case of . Direct from our assumption that the -algebra structure is compatible (Definition 4.2.1).
Extend the interpretation of Definition 5.2.7 to sequents by defining
It suffices to check validity of the rules in Figure 2.
— (L) is valid because ⟦ in Definition 5.2.7.
— R) is valid from condition 1 of Definition 4.3.1.
— L) is valid from condition 2 of Definition 4.3.1.
— (L), (R), (L), and (R) are by standard facts of Boolean algebras (bounded distributive complemented lattices).
6. THE -POWERSET AS A FOLEQ ALGEBRA
Suppose is an -algebra over a termlike -algebra . We know by Proposition 3.4.10 that () from Definition 3.4.6 is a -algebra. It is also very easy to see that () with the pointwise action (Definition 3.4.1), ordered by subset inclusion , is a nominal poset (Definition 4.1.1).
We want now to show that () is a FOLeq algebra (Theorem 6.4.1). That is, we want to show that ()
— is finitely fresh-complete (has ),
— is complemented (),
— has an equality,
— and the -action is compatible (Definition 4.2.1).
It will be obvious that complement is given by sets complement. Equality is non-evident but very natural and is discussed in Subsection 6.3. For we use Proposition 4.1.5 to split the problem into parts. We consider this next.
6.1. Intersection, complement, top element
Suppose ) is an -algebra over a termlike -algebra . Recall the definitions of NomPow() from Subsection 2.4.1 (finitely-supported powerset) and of () from Definition 3.4.6 (the -powerset).
Lemmas 6.1.1 and 6.1.2 are perhaps not entirely obvious, but all the cases follow the same pattern of pointwise calculations on sets. These cover the technically simplest cases; in Subsection 6.2 we move on to quantification.
Suppose is an -algebra over a termlike -algebra . Suppose and NomPow() and suppose NomPow() is strictly finitely supported (Definition 2.4.3). Then:
(1)
In words: commutes with sets complement.
(2) ()[ ([]) and ()[ ([]). In words: commutes with strictly finitely supported sets intersections and unions. In particular, commutes with finite intersection and union.
(3) If then [] []. In words: is monotone.
We reason as follows:
We note that by Lemma 2.4.4, # if and only if # for every . This allows us to swap the and the quantifier, and the result follows.
Part 3 follows using part 2 and the fact that [] [] if and only if [] [[].
— If NomPow() then NomPow() and
— If NomPow() then NomPow(), and if () then ().
— NomPow() and ().
Finite support follows from Theorem 2.3.2. All the results involving finitely-supported powerset NomPow(-) follow immediately.
It remains to check conditions 1 and 2 of Definition 3.4.6 for the -powerset (-). We do this just for :
(1) If is fresh (so #) then ()[ . We reason as follows:
(2) If is fresh (so #) then ()[)(). We reason as follows:
is the bottom element and is the top element in NomPow() and () ordered by subset inclusion. is the greatest lower bound for . is the complement of . Thus NomPow() and () ordered by subset inclusion form Boolean algebras, and by construction () is a subalgebra of NomPow().
By standard sets calculations.
6.2. Quantification
In this subsection we explore what concrete sets operation corresponds to the fresh-finite limits of Notation 4.1.3; in other words we explore quantification.
Suppose ) is an -algebra over a termlike -algebra . Recall the definitions of NomPow() from Subsection 2.4.1 (finitely-supported powerset) and of () from Definition 3.4.6 (the -powerset).
We work towards proving NomPow(); this is Theorem 6.2.5. We need the key technical Lemma 6.2.2 for Proposition 6.2.3:
Suppose and NomPow() and and suppose #. Then
We prove two implications:
— The up-down implication. Assume [][] ()(). Choose . Choose fresh and (so #). Then by assumption (since # and #) [][] ()() so that by () of Figure 1 (since #) [[]][] ()(). Now by (#) [ (since #). Therefore [][] ()().
— The down-up implication. Assume [][] ()().
Choose fresh (so #), choose (for which need not necessarily be fresh), and choose fresh (so #). By Lemma 3.1.8 #[] (since #). Therefore [[]][] ()() and by () of Figure 1 (since #) [][] ()().
We cannot use Lemma 6.1.1(2) to derive Proposition 6.2.3 because [] is not necessarily strictly finitely supported. The result still holds, by a proof using Lemma 6.2.2:
Suppose NomPow() and and #. Then
Consider . We reason as follows:
Suppose NomPow(). Then
As a corollary, # and supp() supp().
Recall () from Definition 3.4.6:
If () then ().
If () then from Definition 6.2.1 is equal to the fresh-finite limit in the lattice () ordered by subset inclusion.
The proofs leading up to Corollary 6.2.6 are somewhat subtle, and it is useful to illustrate how they work by tracing through how a similar ‘proof’ fails:
By Proposition 4.2.8 []. However it does not follow from this that []. This is because Theorem 6.2.5 does not hold of []—it is not in ()—and this is because Proposition 6.2.3 fails, which is because Lemma 6.2.2 fails.
That is, if we replace every in Lemma 6.2.2 with , then Lemma 6.2.2 no longer works (and this is because is not closed under applying substitutions [], whereas is).
6.3. Equality in the -powerset
We have seen how to interpret conjunction, union, negation, truth, false, and quantification in the -powerset of an -algebra. Now we show that we can also interpret equality.
Suppose ) is an exact -algebra (Definition 3.3.2) over a termlike -algebra .
Some motivation for Definition 6.3.1: Suppose is a -algebra over (Definition 3.1.5) and suppose just for this remark that Pow() (Definition 3.2.4). Recall from Proposition 3.3.3 that is indeed exact.
Suppose (), meaning by Definition 6.3.1 that ([[]). Using Proposition 3.2.2 [[] when [] [] for every . Thus
Intuitively this means cannot discern any difference between and . This is in the spirit of Leibnitz equality; two things that equal when they are indiscernible.
More discussion is in Appendix B.
It is not necessarily the case that supp()supp() supp(). For instance, if has the trivial -action that [ for all and (for instance, take the one-element set) then (, which has support .
Lemma 6.3.4 is where we really use the exactness property of (Definition 3.3.2):
()[[([])).
We reason as follows, where we write ) and ) for brevity:
Suppose . Then:
(1) If # then ()[).
(2) If # then ()[)().
As a corollary, ()().
Suppose and suppose #. Then
() if and only if ()[].
A converse to Proposition 6.3.8 is valid for a specific model; see Proposition 7.3.7.
Suppose () and . Then:
(1)
(2)
6.4. Interpreting first-order logic in the -powerset
We can now prove Theorem 6.4.1:
Suppose is an -algebra over a termlike -algebra . Then () is a FOL algebra if we define the following:
If in addition is exact (Definition 3.3.2) then () is a FOLeq algebra if we define the following:
— The Boolean structure (, , and ) is treated in Proposition 6.1.3.
— The -action ([]) is compatible by Lemma 6.1.1 and Proposition 6.2.3.
— We observe by Lemma 4.2.3(2) that the -action is monotone, and by Theorem 6.2.5 that (). We combine these observations with Definition 6.2.1 and Proposition 4.2.6 to conclude that the fresh-finite limit exists in ().
— Equality () is treated in Theorem 6.3.9.
For the reader’s convenience we assemble the maths so far by unpacking what Definitions 5.2.2 and 5.2.7 mean:
— Definition 5.2.2. Given a signature (Σ Π ar) an interpretation maps each f Σ with arity to an equivariant function f : and each P Π with arity to an equivariant function P : () ( is from Definition 5.2.1).
— Definition 5.2.7. The interpretation extends as follows:
Recall also that () comes from Definition 3.1.1, and where is assumed we will usually write it just as .
— Theorem 5.2.13. From Theorem 6.4.1 we conclude that if then with the definitions above, ⟦⟧ ⟦⟧.
7. COMPLETENESS
We now set about proving Theorem 7.3.10, which states that if ⟦Φ Ψ⟧ is true in every interpretation in every FOLeq algebra, then indeed Φ Ψ is derivable in first-order logic. The proof follows the general outline that the reader familiar with such proofs might expect: we build a notion of point out of maximal consistent sets of predicates (Definition 7.2.2), map to a set of points (Definition 7.3.1), show that every consistent is contained in some point, note that maps precisely to the set of points containing , and then use that to prove completeness.
The main results are Theorems 7.1.20, 7.3.6 and 7.3.10. The constructions are subtle:
(1) We have more structure than usual: points form not just a set but an -algebra, and sets of points form not just a set but a -algebra, and not just a lattice but a lattice with fresh-finite limits and equality. This means more properties to verify, and so more proofs.
(2) We are used to seeing valuations being used to build the final semantics; not so here. The semantics, as discussed in the Introduction, is absolute. This requires a certain change of perspective.
(3) We cannot directly use Zorn’s lemma and need to use a carefully designed increasing chain of filter-ideal pairs, and indeed, the definitions of filter and ideal also require careful design.
Detailed exposition follows below; see in particular Remarks 7.1.2, 7.1.10, and 7.1.21, and also Remark 7.3.8.
An argument is possible that the proofs that follow are the real proof, and the usual development is a projection of that proof to a Zermelo-Fraenkel sets (ZF) universe. This is reasonable, since ZF is consistent if and only if FM is, but the ZF construction is not optimal, since FOL syntax interrogates the models just for fresh-finite limits and equality, that is, for , , , and —which is precisely the structure that FOLeq algebras provide using nominal sets.
7.1. Filters and points
7.1.1. Filters.
Recall predicates from Definition 5.1.1 and the entailment relation Φ from
Figure 2:
A filter is a nonempty set of predicates (which need not have finite support) such that:
(1) (we call consistent).
(2) If and then (we call deductively closed).
(3) If and then .
(4) If () then .
above need not have finite support. This means that in Definition 7.1.1 it is not the case that () if and only if (). The ‘standard’ equivalent decompositions of into ‘+freshness’ and ‘+freshness’ (Theorem 2.17 of [Gab14], Theorem 6.5 of [Gab11], or Theorem 9.4.6 of [Gab01]) might not work with respect to . However, in Definition 7.1.1 is still assumed to have finite support, and that gives us all we need.
This is why -algebras (Definition 3.1.6) are not assumed to be nominal sets, but are only assumed to be sets with a permutation action—and why -algebras (Definition 3.1.5) are assumed to be nominal sets.
More discussion of the support of in Remark 7.1.10.
Ideals are dual to filters; Definition 7.1.3 is standard:
An ideal is a nonempty set of predicates (which need not have finite support) such that:
(1) .
(2) If and then (we call down-closed).
(3) If and then .
If is a predicate then define and by
If then from Definition 7.1.5 is a filter and is an ideal.
7.1.2. On universal quantification in filters.
Lemma 7.1.7 is needed for Proposition 7.1.8. It is a fact of syntax related to Lemma 3.1.10.19
Suppose is a predicate and suppose is fresh (so #). Then [] is -equivalent to ().
The substitution [] in [] is the standard capture-avoiding substitution on the syntax of the predicate , from Definition 5.1.1. The permutation () is the permutation acting on the syntax of . But when we write ‘ fresh’, what exactly do we mean; fresh for what? For ? For the -equivalence class of ? Or are we using the -quantifier? In fact, all of these are equivalent. The interested reader can find the key technical devices for a slick proof in [Gab11, Section 5], notably in Lemma 5.16.
Suppose is a filter and is an atom. Then:
(1) The following conditions are equivalent (below, ranges over all atoms, including ):
(2) If furthermore is finitely supported and # then the following conditions are equivalent:
First we prove part 1. Suppose . By (L) from Figure 2 and condition 2 of Definition 7.1.1 also [] for every term . It follows in particular that [] for every atom (i.e. variable symbol) . It follows that [] for all # so by Lemma 7.1.7 also (). Finally if () then by condition 4 of Definition 7.1.1 also .
Part 2 follows from part 1 using Theorem 2.3.8.
It will be useful to have Notation 7.1.9:
Call a filter an ultrafilter when for every , precisely one of and holds.
Proposition 7.1.8 has some interesting ramifications which relate back to Remark 7.1.2.
We will shortly see how to construct ultrafilters (which are also maximally consistent sets of predicates) in Subsections 7.1.5 and 7.1.6, and organise them into an -algebra of points in Subsection 7.2 (see in particular Proposition 7.2.3). We will use this to prove completeness in Subsection 7.3.
Proposition 7.1.8 lets us make some interesting observations about what these ultrafilters look like. It is not hard to prove that if an ultrafilter has finite support then by Proposition 7.1.8 for any # and ,
where is shorthand for (), and so for any (even if it is not fresh for ) and ,
So a finitely supported ultrafilter ‘believes’ that , and so ‘believes’ that quantification is trivial. Quantification motivates this paper, so a finitely supported ultrafilter is for us degenerate and uninteresting.
In that sense Proposition 7.1.8 implies that ultrafilters must have infinite support—at least, the ones we care about must have this property.
Ultrafilters are dual to predicates in the sense of duality theory; the dual notion to ‘must have finite support’ (like predicates and open sets) is evidently ‘must not have finite support’ (like ultrafilters).20
Informally this seems reasonable—but to some extent, Proposition 7.1.8 makes it formal.
7.1.3. Growing filters.
It will be useful to make larger filters out of smaller filters:
Suppose is a set of predicates and is a predicate. Then define:
The corollary follows from the body of this result because since from condition 2 of Definition 7.1.3 , so .
We now consider the body of this result. It is clear from the construction that and . We now check that satisfies conditions 2 to 4 of Definition 7.1.1:
(2) If and then . By construction.
(3) If and then . Suppose and for . Then by condition 3 of Definition 7.1.1 , and it is a fact that ().
(4) If (()) then . Suppose for cofinitely many there exists a such that (). Then there certainly exists some such that # and (). Note by Proposition 7.1.8(2) that also . We apply to both sides and we conclude that
By Lemma 4.1.9 and condition 2 of Definition 7.1.1 we conclude that as required.
7.1.4. Growing ideals.
It will be useful to make larger ideals out of smaller ideals:
Lemma 7.1.14 is a version of Lemma 7.1.12 for ideals. It is the simpler result, because Definition 7.1.3 has nothing corresponding to condition 2 of Definition 7.1.1:
Suppose is an ideal and is some set of predicates. Then:
— and .
— is closed under conditions 2 and 3 of Definition 7.1.3 (so that if then it is an ideal).
By routine calculations.
7.1.5. Prime filters and ultrafilters
— Call a filter prime when implies either or .
— Suppose is a filter and is an ideal. Call maximal with respect to when and for every filter with , if then .
— Call maximal when it is maximal with respect to the ideal . We will use the terms prime filter and point synonymously henceforth (see also Definition 7.2.2). Lemma 7.1.16 is standard, but we still check carefully that being ‘nominal’ does not interfere with the classical propositional structure; it all works. We need the result for Theorem 7.3.6:
A filter is prime if and only if it is an ultrafilter (Notation 7.1.9).
Suppose is prime. We note that () so by condition 2 of Definition 7.1.1 and non-emptiness of , (we use the conditions of Definition 7.1.1 silently henceforth). By primeness of , at least one of and holds. Similarly () so that () . It follows that precisely one of and holds, so that is an ultrafilter.
Conversely suppose is an ultrafilter and suppose and yet and . Then , so that , a contradiction.
Suppose is a filter and is an ideal. If is a maximal filter with respect to then it is prime.
Suppose and . By Lemma 7.1.12 and maximality we have that and . It follows that there exist with and . By condition 3 of Definition 7.1.3
Now we rearrange the left-hand side to deduce that
We now note that (since , and indeed also ) and (since ) and (since ) and by assumption. But then , so that by condition 2 of Definition 7.1.1 , a contradiction.
Lemma 7.1.18 is a technical result which will be useful for proving Theorem 7.1.20:
Suppose
— is a finitely supported filter and is an ideal, and suppose
— and .
Write () (supp()supp() ). Then:
(1)
(2) As a corollary, is an ideal (and by part 1 is disjoint from ).
Suppose and and () . We note the following:
— Since () , there exist # and with ()().
— Since there exists with . By Proposition 7.1.8(2) (since #) , and we see that we may assume without loss of generality that #.
— Since we have ().
By condition 3 of Definition 7.1.1
and therefore by distributivity (Definition 4.4.1)
By assumption # so by Proposition 7.1.8(2) we deduce that
Recall that by assumption #; by properties of first-order logic (including -equivalence and distributivity) we conclude that
This contradicts condition 1 of Definition 7.1.1.
For the corollary, it follows from condition 2 of Definition 7.1.1 that so that . We use Lemma 7.1.14.
7.1.6. The Zorn argument
If is an ascending chain of ideals then is an ideal.
By standard calculations on the three conditions of Definition 7.1.3.
A version of Lemma 7.1.19 for filters does not hold, because condition 4 of Definition 7.1.1 is not closed under ascending chains of filters. We can still make a Zorn-like argument (for a carefully selected chain) to prove the existence of maximal filters:
Suppose is a finitely supported filter and is a finitely supported ideal and suppose . Then there exists a prime filter with and .
As corollaries:
— If then there exists a prime filter such that and .
— If then there exists a prime filter such that .
The corollaries follow by considering and (see Definition 7.1.5 and Lemma 7.1.6). We now consider the main part of this result.
Write Predicates for the set of all predicates from Definition 5.1.1. Enumerate Predicates as a list of pairs (); by assumption in Definition 2.1.1 atoms are countable, and by construction so are predicates, so we can do this.
We define a sequence of (by Theorem 2.3.2) finitely supported disjoint filter-ideal pairs () as follows:
(1) (). By assumption .
(2) Suppose 1 and . Then take
It follows from Lemma 7.1.12 that is a filter and from Theorem 2.3.2 that it is finitely supported.
(3) Suppose 1 and . Then take
It follows from Lemma 7.1.18 that is an ideal and .
We can note the following:
— We note that and . Since we took () and assumed .
— We note that is disjoint from and thus from . By construction.
— We note that is an ideal. This is Lemma 7.1.19.
— We note that is a filter. Conditions 1 to 3 of Definition 7.1.1 are routine. To check condition 4, suppose (); we need to prove . So let be that index in the enumeration above such that (). At stage , when we built (), there were two possibilities:
— If then we must have put into , so that and we are done.
— If then we must have put () into for cofinitely many , so that (). But this is impossible because we assumed that cofinitely many () were in , which is disjoint from .
— We note that is a maximal filter disjoint from the ideal . Consider any and choose some fresh (so #). Note that . Let be that index in the enumeration above such that (). It follows from the structure of the algorithm above that precisely one of or will hold. Maximality follows.
Therefore by Proposition 7.1.17 is a prime filter, and by construction and () .
The proof of Theorem 7.1.20 is unusual in that we consider a chain of filter-ideal pairs instead of a chain of filters.
The reasons for this may not be obvious. Why bother? When we add to , why not add to instead? After all, we have negation.
However if we do this then the set we might write as would fail to be a filter, because it would contain () for cofinitely many , but not . Furthermore we cannot just add because we may not want this to be in —what we want is subtly different: that () not be added for cofinitely many ‘by accident’ at later stages (possibly infinitely many later stages).
Thus the asymmetry between Definitions 7.1.1 and 7.1.3, that Definition 7.1.1 has a condition for (condition 4) whereas Definition 7.1.3 does not, is a useful part of the design.
Perhaps we should write about strong filters and ideals which satisfy a /-condition, and weak ones which need not. In that terminology, we can note the interesting fact that our proof of the existence of maximal strong filters / ideals requires us to consider also weak ideals / filters.
7.2. The amgis-action on (prime) filters
Recall from Definition 3.2.1 the pointwise -action [[] . In this subsection we check that this preserves the property of being a (prime) filter (Definitions 7.1.1 and 7.1.15) of predicates (so is a set of predicates and in the -action is a term from Definition 5.1.1).
The work of this subsection happens in Lemma 7.2.1; Proposition 7.2.3 then puts the result in a some nice packaging.
If is a filter then so is []. Furthermore, if is prime then so is [].
We check the conditions in Definition 7.1.1. We use Proposition 3.2.2 without comment:
— []. Since it is a fact of syntax that [. We use condition 1 of Definition 7.1.1.
— If [] and then []. If then it is a fact of first-order logic derivability that also [] []. We use condition 2 of Definition 7.1.1.
— If [] and [] then []. It is a fact of syntax that ()[ []([]). We use condition 3 of Definition 7.1.1.
— If (()[]) then []. Choose some fresh (so #). By Corollary 2.1.12 ()()) and by () also (). Thus, we may assume without loss of generality that #. Now suppose (())[] for all but finitely many ; so suppose #. By Corollary 2.1.12 (), so that ()([]) for all but finitely many . By condition 4 of Definition 7.1.1 ([]) and since # it follows that ()[] .
Now suppose is prime and suppose ()[] . Then []([]) , so that either [] or [] .
Recall from Definition 7.1.15 that we called prime filters points:
Write Points for the -algebra determined by prime filters and the pointwise actions from Definition 3.2.1. That is:
Points is indeed an -algebra. Furthermore, Points is exact (Definition 3.3.2).
The first part is just Lemma 7.2.1 combined with Proposition 3.2.6.
We now prove exactness. Suppose [[].
Consider some predicate . Note that cofinitely many (all but finitely many) atoms satisfy all of the following properties, since cofinitely many atoms satisfy each of them, and a finite intersection of cofinite sets is cofinite:
— [[] (by assumption),
— #, so that also [] (a fact of syntax),
— [] [] (Proposition 3.2.2), and
— [] [] (Proposition 3.2.2).
So there exists at least one satisfying all the above. Then
7.3. Proof of completeness
Recall from Definition 7.2.2 the set of points Points, which by Proposition 7.2.3 is an exact -algebra. Recall from Definition 3.4.6 the definition of -powerset of an -algebra, for example (Points), and recall that by Theorem 6.4.1 it is a FOLeq algebra.
Recall from Example 3.1.3 and Definition 5.1.1 the syntax of terms with real substitution []. Then:
Define an interpretation (Definition 5.2.2) as follows:
— Take to be the syntax of terms with real substitution, and f( f().
— Take to be (Points) considered as a FOLeq algebra.
— Take P( Points P() .
As we shall see, Definition 7.3.1 is what we need to build a complete model of first-order logic with equality. To check this, it only remains to connect Definition 7.3.1 to the sets machinery we have built so far, and verify what comes out the other end.
If is a term (Definition 5.1.1) then ⟦.
An easy consequence of taking to be syntax with substitution, and of Definition 5.2.5.
We do not have to specify the interpretation of equality because it is fixed by Definition 6.3.1, just as the intepretations of , , , and are fixed. This was observed in Theorem 6.4.1.
We briefly revisit Remark 6.4.2 and simplify it using Lemma 7.3.2, to sum up how the definitions instantiate to our case of (Points):
(1) Points () .
(2) P( Points P() .
For part 1, we prove two implications:
— Suppose () . We will show that (), that is, that [[]. We note by Proposition 3.2.2 that for any atom ,
By assumption () so by properties of first-order logic and condition 2 of Definition 7.1.1
It follows by Proposition 3.2.2 that [] []. Since and were arbitrary, we conclude in particular that [[].
— Suppose (), so [[]. We will show that () . Consider some such that fa() fa() and such that [[]. By condition 2 of Definition 7.1.1, () . Also since fa() we have that ()[], so that ()[] , and by Proposition 3.2.2 () []. Therefore () [] and again by Proposition 3.2.2 and our assumption that fa() we conclude that () as required.
For part 2 we reason as follows:
We should briefly check that Definition 7.3.1 is well-defined, in the sense that P() from clause 3 is indeed an element of from clause 2. This is routine:
Continuing the notation of Definition 7.3.1, P() which is equal to Points P() , is an element of (Points).
Finite support is from Theorem 2.3.2 since the support of P() is bounded by , which is finite. It remains to check conditions 1 and 2 of Definition 3.4.6, namely:
— For fresh (so ) and any term , P()[ P().
— For fresh (so ) and any atom (so possibly ), P()[)P().
For the first condition, by Proposition 3.4.2 P()[] if and only if [] P(). By Definition 7.3.1 this is if and only if P() []. By Proposition 3.2.2 this is if and only if P()[] . It is now a fact of syntax that P()[ P().
The second condition follows much as the first, using the fact of syntax that P()[ ()P().
⟦ Points .
By induction on :
— The case of . By assumption in Definition 7.1.1 Points is consistent (meaning ). Furthermore, ⟦.
— The cases of and P(). This is Lemma 7.3.4.
— The case of . From the inductive hypothesis and conditions 2 and 3 of Definition 7.1.1.
— The case of . By assumption is prime (Definition 7.1.15), and it follows by Lemma 7.1.16 that if and only if . Also by assumption ⟦ Points⟦⟧.
— The case of . Combining Remark 7.3.3 with Proposition 3.4.2 ⟦⟧ means that [] ()⟦⟧ for every . By inductive hypothesis this is if and only if () [] for every , which by Proposition 3.2.2 and -conversion is if and only if [] for every . We use Proposition 7.1.8(1).
By Proposition 6.3.8 ( Points. In Proposition 7.3.7 we show that specifically for the interpretation of Definition 7.3.1, a converse holds:
If ( Points then (that is, and are syntactically identical terms).
It is worth pausing to note, informally but mathematically, why Propositions 6.3.8 and 7.3.7 are remarkable.
We constructed (Points) by taking the -powerset of points. The ‘nominal’ aspects of our construction in this paper allows us to interpret , , and also as three aspects of a single unifying notion of fresh-finite limits—but let us set that aside for now.
In addition to the above, Propositions 6.3.8 and 7.3.7 make formal an idea that even if the underlying notion of predicate did not contain an equality—in the sense of going back to Definition 5.1.1 and erasing equality from predicates, and going to the first-order logic sequent rules in Figure 2 and erasing R) and L)—then even so, (Points) would still have an equality.
In summary: (Points) ‘generates’ a sets-based notion of equality, just as it ‘generates’ sets-based notions of conjunction and universal quantification as fresh-finite limits, and negation as sets complement.
If then ⟦⟧ ⟦⟧.
Theorem 7.3.10 is a converse to Theorem 5.2.13:
If ⟦Φ Ψ⟧ is true for every interpretation in every FOLeq algebra, then Φ Ψ.
From Corollary 7.3.9.
⟦ Points if and only if in FOLeq.
8. TARSKI MODELS
We recall the usual definition of model for first-oder logic, which goes back to [Tar44] and is based on valuations. We will show how to lift this to a nominal model.
The main definition is Definition 8.2.1 and the main proofs are in Corollary 8.2.6 and Proposition 8.2.15.
The reader will probably be familiar with the valuation-based models and may ask: why bother taking something familiar and translating it to something less familiar? Usually, we expect to see it the other way around—the unfamiliar translated to the familiar.
However, we will argue in Remark 8.2.16 that the nominal semantics is more natural.
8.1. Tarski-style model of first-order logic
We briefly sketch the standard model of first-order classical logic, with valuations and without atoms. This model is not intended to be sophisticated; we will just need that one exists.
To avoid the confusion between sets and nominal sets, we may write ordinary set for the former.
Suppose is an ordinary set. Write for the set of functions from atoms to . Let range over elements of and call these valuations (to ).
If then define [:] to be the function on atoms given by:
Define a permutation action on by
is a set with a permutation action (Definition 2.1.4). It is not in general a nominal set because it has elements without finite support.21 For our purposes that will not be a problem.
The action from Definition 8.1.3 is a special case of the conjugation action ()((()) (already mentioned in Subsection 2.2.4), where we use the trivial action for every . This is standard; for a specifically ‘nominal’ discussion see [Gab13, Definition 2.4.2].
Recall from Definition 5.1.1 the notion of signature (Σ Π ar) of function symbols f Σ and predicate symbols P Π with their associated arities ar(f) ar(P). For the rest of this subsection fix some signature.
An ordinary model -) is a tuple such that:
— is some non-empty (ordinary) underlying set.
— - assigns to each term-former f a function f : and to each predicate-former P a function P : .
is a complete Boolean algebra. We use standard definitions, such as , , , and without comment
Recall the syntax of first-order logic from Definition 5.1.1.
Define a (standard) interpretation function - mapping terms and predicates to elements of and (considered as a Boolean algebra) respectively, as follows:
Theorem 8.1.8 expresses the usual soundness and completeness result for first-order logic; for details and proofs see e.g. [vD94, Subsection 1.5]:
Φ Ψ is derivable if and only if for every ordinary model and every valuation to it is the case that implies .
8.2. Lifting to a FOLeq algebra
We now show how to ‘lift’ a model over ordinary sets to a nominal model (Proposition 8.2.15). We then deduce completeness for nominal Boolean algebras (Corollary 8.2.18).
8.2.1. Lifting to a sigma-algebra
Given ordinary sets and define a termlike -algebra Tarski(), and define a -algebra Tarski() over Tarski() by:
as follows:
— Tarski() is the set of functions from to such that there exists a finite set such that
(if then we obtain Tarski()).
— The permutation action is defined by
— If and define
— If then define ()(().
() is a bit of a mouthful so we may just write it as . It will always be clear whether we mean ‘’ or ‘ Tarski()’.
It is routine to verify that the permutation action is a group action. It remains to check finite support.
Suppose ( for every where is the finite set of atoms whose existence for each is assumed in Definition 8.2.1. By Definition 8.2.1 ()((). By Definition 8.1.3 ()((()). Now by assumption ((()) for every . Therefore, ()( () for every , and so ((), and so ()((). Thus, has finite support (and is supported by ).
Suppose Tarski(). Then supp()(() implies (().
It suffices to show that if supp() and then ([:(). Choose fresh (so ). By part 1 of Corollary 2.1.12 (), since supp(). We reason as follows:
Tarski() is indeed a termlike -algebra, and Tarski() is a -algebra over Tarski().
By Definitions 3.1.1 and 8.2.1 and see that we need to check equivariance and the () axioms from Figure 1. This is routine:
— Rule (a) (only for Tarski()). Unpacking definitions, []([:()](().
— Rule (id). Again we unpack definitions: [](([:(().
— Rule (#). Using Lemma 8.2.4.
— Rule (). Suppose Tarski() and #, and Tarski(). Then [](([:()]). Also, unpacking Definitions 8.1.3 and 8.2.1 (())[ ([:()][:()]). We use Lemma 8.2.4.
— Rule (). Suppose Tarski() and Tarski() and #. We just unpack definitions:
The final step is valid using Lemma 8.2.4 since #. (There are two symbols here: and :. [] is ‘ with substituted for ’ from Definition 8.2.1, and [:()] is ‘ with maps to ()’ from Definition 8.1.2.)
8.2.2. Interlude: more on limits in nominal posets.
For this subsection, fix a nominal poset (Definition 4.1.1).
It is useful to continue and extend the maths from Subsection 4.1. Recall from Notation 2.1.3 the definition of fix:
Lemma 8.2.8 is related to Lemma 3.1.11 and Proposition 8.2.9 is related to Propositions 4.2.6 and 4.2.8:
#.
We note by the pointwise action that () fix(supp()). We choose a fresh (so #, that is, supp()) and use Corollary 2.1.12(3) and routine calculations.
Suppose and . Then:
(1) If exists then so does , and they are equal.
(2) Suppose has a monotone -action (Definition 4.2.1). Then if exists, then so does , and they are equal.
(1) By Definition 4.1.1 and #. It follows by equivariance of and Corollary 2.1.12 that for every fix(supp()). Therefore is a lower bound for . Now consider some other lower bound for , so that fix(supp()). Choose fresh (so #); by Theorem 2.3.2 () exists (and by Lemma 4.1.9 it is equal to ). It follows by equivariance of and Corollary 2.1.12 (since #) that () so ().
(2) By Lemma 8.2.8 and Theorem 2.3.2 # so is an #lower bound for . Consider any other such that and #. By (#) [ for every . By monotonicity [] [] for every . It follows using Lemma 3.1.10 that .
We have seen multiple characterisations of quantification:
— Fresh-finite limits from Notation 4.1.3.
— Limits of permutation orbits, above in Proposition 8.2.9.
— Limits of substitution instances (if there is a monotone -action), from Propositions 4.2.6 and 4.2.8.
Note of Proposition 8.2.9 that we only need atom-for-atom substitution (what this author calls a renaming action) in the proof.
Call a nominal poset ) nominally complete when every finitely supported subset has a greatest lower bound.
In another terminology: is nominally complete when it has limits of finitely supported diagrams.
8.2.3. Lifting the logical structure
Suppose Tarski(). Write when () ().
Suppose and Tarski() and . We reason as follows:
(Tarski()) is nominally complete, complemented, and has a compatible -action and an equality.
As a corollary, (Tarski()) is also a FOLeq algebra (Definition 4.4.3).
The greatest lower bound of a finitely supported set Tarski(), and the complement of Tarski(), are defined pointwise by
Equality is defined by
Checking that the -action is compatible and that the definitions above are correct, is routine.
By Lemma 4.2.3(2) the -action is monotone. The corollary follows by Proposition 8.2.12.
By Proposition 8.2.15 every Tarski-style model is a FOLeq algebra. However, not every FOLeq algebra is a Tarski-style model, because by Proposition 8.2.15 Tarski-style models have limits for all, possibly infinite, finitely supported subsets.
In FOLeq algebras the notion of completeness used is fresh-finite completeness (Subsection 4.1); a concept which is natural to express in a nominal universe. This makes FOLeq algebras complete enough to interpret and , and no more.
Thus, Tarski-style models have more limits than first-order logic requires. This is not detectable from inside first-order logic, since first-order logic is sound and complete for the Tarski-style models and this is why Tarski-style models suffice to model first-order logic in a ZF universe.
However, completeness is not the only issue: if it were, we would only ever need the Herbrand model of syntax quotiented by derivable equivalence (Section 9). The issue is to capture in abstract semantic terms exactly that structure necessary to interpret first-order logic. Neither the Tarski models nor indeed the Herbrand models quite do this; but FOLeq algebras do. In this sense, Tarski-style models are less natural than the nominal semantics proposed in this paper.
Before we are done, we need to build an interpretation of term-formers and predicate-formers in the sense of Definition 5.2.2, using the interpretation in ‘ordinary’ sets from Definition 8.1.5. This is not hard:
We obtain an interpretation of first-order logic immediately from Definition 5.2.7 and soundness immediately from Theorem 5.2.13. If we like, we can also leverage the completeness theorem with respect to ordinary models:
If Φ Ψ, then there exists a termlike -algebra and a FOLeq algebra over such that .
9. HERBRAND MODELS (LINDENBAUM-TARSKI ALGEBRAS)
We conclude, briefly, by observing that predicate syntax quotiented by derivable equality is a FOLeq algebra. This construction is variously called a Herbrand, Lindenbaum, or Lindenbaum-Tarski construction, algebra, or model—or just ‘syntax quotiented by derivable equivalence’.
There is not intended to be much new in this observation; just to show how syntax quotiented by derivable equivalence fits with the idea of a FOLeq algebra.
If there is any subtlety it is that we build our model from possibly open syntax, and the familiar syntactic notion of variable will be handled in our nominal abstract machinery as a special case of the background Fraenkel-Mostowski notion of atom. It all works perfectly, which is part of the point.
Recall the syntax of terms and predicates from Definition 5.1.1, and the notion of logical entailment from Figure 2.
Define a logical equivalence relation on predicates by
Write [] for the -equivalence class of .
If and are -equivalence classes then impose a partial order by when and and . It is a fact that this is well-defined (does not depend on the choice of and ).
Give predicates the natural permutation action where acts on by acting on the atoms in . Theorem 2.3.2 tells us the following:
If then .
Give -equivalence classes the pointwise permutation action by [] [].
Give -equivalence classes a pointwise -action by [][[]].
We need to check that [][] is well-defined, that is, if then [] []. This is a fact of first-order logic.
Define to be the termlike -algebra of terms where substitution is real substitution on syntax, and take ) to be -equivalence classes of predicates, with the pointwise permutation and -actions.
is a FOLeq algebra if we take to be [], [] [] to be [], [] to be [], and to be [].
Well-definedness and limit properties are all just properties of first-order logic. Finite support is from Theorem 2.3.2, since syntax is finite.
10. CONCLUSIONS
10.1. Semantics out of context
Traditionally we admit numbers as a primitive datatype, and we emulate names using numbers (since numbers are countably infinite) or functional arguments. This is neatly packaged up by Tarski-style semantics, which broadly speaking has the following shape:
(Natural numbers Semantics of terms) Semantics of predicates
Tarski-style semantics have exerted a powerful, almost subliminal, influence on how semantics have been designed, and how the relationship between syntax and semantics has been understood. Proposing a good alternative to this view is one of our main goals.
In Tarski-style semantics the valuation (mapping numbers to semantics of terms as illustrated above) is a context of variable-to-denotation assignments. The semantics of a predicate exists in the context of a valuation , and we write ⟦. provides the syntax and provides the context, and what Tarski really taught us was that semantics exists in context.
Yet, from our point of view context is only compensating for a mathematical foundation that is too poor to directly represent variables. We would consider the slogan “there is no such thing as a free variable” from [Per82] to be succinct, eloquent—and incorrect.
In this paper we do things differently. We interpret names more-or-less as themselves, using urelemente in Fraenkel-Mostowski foundations. Denotationally speaking there is such a thing as a free variable, and it is an urelement—an atom.
In this paper we apply this idea to give semantics to first-order logic. Given a set, its powerset is naturally a Boolean algebra: in a nutshell, this paper is notes that given a set of terms, the -powerset of its -powerset is naturally a model of first-order logic with equality (see Example 3.4.11)—and furthermore, this concrete powersets model is susceptible to simple and attractive nominal algebraic and lattice characterisations (and a topological treatment is possible too, though not in this paper). More on this in Subsection 10.2.
The Tarski notion of variable context is transmuted into the nominal notion of support (Definition 2.1.8).23 In the terminology of the title of this paper, the semantics we obtain is absolute; we talk about the semantics of , and write ⟦⟧. Once the model is fixed, so is ⟦⟧ the meaning of .
We can recover the minimal relevant context of ⟦⟧ by calculating its support supp(⟦⟧). However, if we do not care about support we can ignore it. This simplifies reasoning; it is easier to talk about ‘an element’ than ‘an element in context’.
But support is more general than ‘the free variables of’. It can be read as expressing what a nominal element depends on—without needing to know what logic, program, or computation represents (if any). If we use our foundations correctly then the support of will relate sensibly to what is being used to represent, and furthermore, the general nominal constructs will give us a useful structure within which to work. For instance in this paper:
— Lemma 5.2.8 notes that supp(⟦⟧) fa()—the nominal element ⟦⟧ is supported by (at most) the atoms free in . This connects support of syntax with the corresponding notion of support of semantics.
— Similarly (#) from Figure 1 expresses that if supp() then substitution [] does not change . This connects nominal support—being affected by a permutation like ()—with the notion of semantic dependency that comes from being in a -algebra and being affected by [].
The two points above are visible in syntax: if is not free in then with substituted for a term is equal to . By the two points above, if is not free in then also ⟦⟧[⟧. In fact, the semantics is ‘compositional’ with respect to substitution; ⟦[⟧[⟦⟧] (Lemma 5.2.11). The reader used to Tarski semantics might recognise the corresponding result ⟦[. From the point of view of this paper, that result is a special case of a more general result for a more general semantics.
Because an element stands on its own, we do not need to label everything with a context, or think or prove lemmas about weakening or strengthening contexts, or about making the contexts of and equal so that we can combine them, or even about -renaming contexts. We do not need valuations, or higher types (though we can have them if we like, as noted in Section 8). This is taken care of in the background.
Name-management is simpler in nominal techniques, and name-management is the thing that separates first-order logic from Boolean algebra, and it should be clear that things other than first-order logic would be susceptible to the mathematical style and nominal semantics we have introduced in this paper; some are suggested in the Future work below.
10.2. Recalling the trio of semantics
In this paper we have considered a trio of semantics: lattices, sets, and algebra.24 Let us recall what they look like:
— A lattice-flavoured semantics specifies the meaning of a logic in terms of a partially-ordered set (a set with a transitive reflexive antisymmetric relation). The order relation models logical entailment; that is, the semantics is designed such that should imply ⟦⟧ ⟦⟧.
We model logical connectives as limits; is modelled as a top element (a greatest lower bound for nothing), is modelled as a greatest lower bound for two elements. This is standard, and in categorical language we say that we assume finite limits of the lattice. The new idea here is to model using fresh-finite limits (Definition 4.1.1; this was proposed in [DG12a]). So by this semantics, ⟦⟧ is an element of a poset with certain fresh-finite limits. Instead of finite limits, we assume fresh-finite limits.
— The nominal algebraic semantics is an algebra not over sets, but over nominal sets.
Nominal algebra enriches the syntax, judgement form, and semantics of universal algebra, while retaining (somewhat surprisingly) a purely equational flavour [GM09; Gab09a; Gab13; Gab12]. Nominal algebra, the nominal algebra axiomatisation of substitution (called -algebras here), and that of first-order logic, were proposed in a sequence of papers [GM06a; GM06b; GM08a; GM08c; Gab14; DG12b]. -algebras are more recent and were created specifically to prove completeness/duality results.
By this semantics, ⟦⟧ is an element of a nominal set which happens to be equipped with operations satisfying certain nominal equalities (see Appendix A.3).
— The sets semantics builds on the semantics of [GLP11; Gab14].25 Conjunction is interpreted as sets intersection and negation as sets complement. This is again standard. We see universal quantification interpreted as an infinite intersection in Definition 6.2.1, and Proposition 4.2.6 notes that this is equal to a fresh-finite limit. Proposition 4.2.6 is one of a family of characterisation results26 and an algebraic one is in Appendix A.3. So by this semantics, ⟦⟧ is a set which thanks to its and structure turns out to be able to interpret universal quantification, and as we saw in Subsection 6.3 also equality. We can write: + powersets = First-Order Logic with equality.
The Stone duality theorem for Boolean algebras adds a fourth framework: topology. A topological duality result for FOL (but not FOLeq) algebras exists and uses technology similar to some of the material in this paper; see a sister paper [Gab14].
10.3. Related work
10.3.1. Nominal precedents.
The idea of nominal axiomatisations of mathematics dates back to nominal algebra which was used to axiomatise in the first instance substitution and first-order logic [GM06a; GM06b; GM08a; GM08c; GM09].
The most developed such logic is at the time of writing permissive-nominal logic [DG10; DG12b] which extends nominal algebra with quantification (of unknowns: ). We use it to finitely axiomatise first-order logic and arithmetic in a first-order setting.
Concerning the sets semantics we see in this paper, precursors are [GG08; Gab09b], which technically have little to do with this paper but which do build families of sets representations of what in this paper we call a -action, and [Gab14] which as mentioned above is a sister paper considering topology and with a slightly different technical treatment (different version of -algebras, no equality, no lattices, and so on; at the time of writing, it has not yet been published).
More distantly related are the term equational systems of [FH08; FH10]. These have no concrete sets representations and the method of axiomatisation is quite different—so technically, this work is not very relevant to what we do in this paper—but it is based on presheaf semantics, and nominal sets admit a presheaf presentation (as noted in Subsection 10.3.7), so there is some overlap.
10.3.2. Tarski-style valuations and Herbrand-style quotiented syntax.
We consider Tarski-style valuation-based semantics in Section 8, and predicates up to derivable equivalence in Section 9. We showed how both can be considered subclasses of FOLeq algebras.
As usual the Herbrand semantics is easy to construct but uninformative; building it is more a ‘sanity check’.
Concerning the valuation semantics, we noted in Remark 8.2.16 that we get more limits than needed. We only really need fresh-finite limits to interpret first-order logic, but valuation semantics will not let us express that. In contrast, FOLeq algebras have only exactly those limits necessary to interpret first-order logic, which seems a significant point in their favour.
10.3.3. Combinators.
Variables are not indispensable. This is the idea behind combinatory logic [Sch67; CF58], and it can be pushed a long way [DBB98; TG87] (the latter paper formalises set theory without using variables).
We see combinatory techniques as orthogonal to this paper. Yes, languages can be constructed without variables; but that does not make variables obsolete. Variables are useful because humans like to use them; combinators do not change that.
Sometimes people talk about combinators ‘reducing’ variables to a simpler problem. Not so. With names (nominal or otherwise) we can talk about a location independently of its site of binding. With combinators we cannot talk about a location except by exhibiting it as being at the other end of a combinator. These may be able to express the same computable functions, but that does not make them equivalent.
10.3.4. Cylindric and polyadic algebras.
Cylindric and polyadic algebras treat quantification as a modality satisfying certain axioms. To model languages with infinitely many variables, we must admit infinitely many modalities.
The interested reader is referred to [Hal06, Chapter 8, page 243] (whose exposition is incredibly clear) and to [Mon00] and [HMT85].
The resemblance to parts of this paper are interesting; for instance, the infinite schemata of axioms (P1) to (P7) of a polyadic algebra in [Hal06, Chapter 8, page 244] are similar to projections of the axioms of Subsection A.3 into a first-order setting (where there is a symbol for every and )—except, that polyadic and cylindric algebras are based on the monoid of finitely supported atoms-substitutions (so: not necessarily bijective functions like permutations), and also, these systems exist in ZF so do not always insist on finite support, or in their terminology on local finite dimensionality.
(Tangentially we can also mention Fine’s notion of arbitrary objects [Fin85], not because it has anything to do with algebra or first-order logic as such, but just because it too is based on a monoid of substitutions.)
Cylindric and polyadic algebras, and Fine’s arbitrary objects, are distinctive because they do not belong to the Tarski family of variables-with-valuations and denotations-in-context. In that sense they are closer to the spirit of this paper.
However, we are not aware of anything like the mathematics of this paper being executed in the frameworks above. This is partly because we take permutations as primitive and so can capture finitely what it takes infinite axiom schemes to capture otherwise.27 It is also because the nominal framework enforces symmetry (as discussed in the opening to Subsection 2.3) and finite support. These are all things that somehow fit together to make possible what we have done in this paper. Perhaps the research above could not do what we have done in this paper, because of the influence of the implicit Zermelo-Fraenkel foundation.
We should also mention hyperdoctrines. These are a categorical framework within which to consider semantics for logics and are very general, so we briefly sketch how hyperdoctrines work for the specific case of a one-sorted first-order classical logic.28
Consider a category T whose objects are natural numbers 0, 1, ...and for each term-former f of arity an arrow fT from to 0. A hyperdoctrine is a functor from T to the category of Boolean algebras, along with an assignment to each P of arity of an element P in ().
In spite of the categorical generality in which this idea is phrased, it really just re-states Tarski-style semantics. Yes, there are no valuations as such, but this is replaced by a finite context and the categorical framework enforces well-formedness (we only give a predicate semantics if its free variables are in the context). Useful as hyperdoctrines are for the reader wanting to work entirely within the vocabulary of categories, all they do is translate—and update—the ideas of Tarski into a new categorical language. The basic nature of the thing has not changed. Nominal techniques as applied in this paper are doing something different.
10.3.5. Boolean algebras with operators.
A Boolean algebra with operators is a Boolean algebra equipped with functions which preserve intersections on each component. These have been studied extensively; first by Jonnson and Tarski [JT52], and then by Goldblatt [Gol89]. A concise and very readable survey is in the Introduction of [Hai00].
It is oversimplistic but reasonable to characterise FOLeq algebras as just being fancy Boolean algebras with operators. The operator concerned is not but the -algebra structure []—which since we are oversimplifying we might as well call substitution, though it is not necessarily syntactic.
Viewed as an operator, the substitution [] is a modality (a unary operator) with special properties: it commutes with meets , joins , and negation . Thus, [] can be viewed as both a modal Box and a modal Diamond operator, which is also a homomorphism of Boolean algebras, and the corresponding Kripke semantics is functional in the sense that each world has precisely one future world.
The flavour of our representation theorem is in keeping with this. Notably, the pointwise actions of Definitions 3.2.1 and 3.4.1
are like the functional preimage under the relevant accessibility relation—though not quite, as we see in the use of on the left above, which hard-wires capture-avoidance and -equivalence (Lemma 3.4.4).
Still, from the point of view of [JT52; Gol89] it is not unreasonable to view this paper as being ‘just’ about a particular kind of Boolean algebra with a particular family of operators satisfying certain axioms described in Figure 1. We mention this because it is not a bad way of viewing how the material of this paper fits in to the broader mathematical context.
Of course there is more going on than just that. Notably: we are working in FM sets so we have to make sure that our constructions preserve finite support; also we do not just have [] but also the universal quantifier ; but perhaps most interestingly, the axioms for are determined by properties of substitution—but the axioms of are not so determined. They emerge from the specific requirements of the specific proofs we need to carry out. So even if a FOLeq algebra is just a Boolean algebra with operators, the operators are organised and axiomatised into a specific and non-trivial structure, and how that structure gets ‘inverted’ under a modified capture-avoiding functional preimage operation, to form -algebras, is subtle and certainly not obvious.
10.3.6. Varieties of FOLeq algebras.
In Appendix A we give a purely nominal equational axiomatisation of FOLeq algebras, using nominal algebra [GM09]. The syntax of nominal algebra is based on equalities between nominal terms subject to syntactic freshness side-conditions which behave a bit like typing conditions. These do not impact on the algebraic flavour of the logic and one way of making that formal is with a version of the HSP theorem, or Birkhoff’s theorem. We get a notion of variety suitable for nominal sets, and a theorem that a nominal algebra theory is precisely characterised by the variety of its models, for a suitable nominal notion of variety. For more details see [GM09; Gab09a].
10.3.7. The Schanuel topos: putting context back in, if we want it.
The reader may know that nominal sets are equivalent to the Schanuel Topos, which can be presented as pullback-preserving presheaves (for a proof with calculations see [Gab11, Theorem 9.14]).
What this means in plain English is that every nominal can be thought of as a family of for such that supp() . In other words, ‘exists’ in a context if and only if the context contains the support of .
So in fact, everything we have done in this paper, admits a ‘contextual’ presentation. Furthermore, it may admit generalisations to presheaves not necessarily preserving pullbacks (to be more precise, not necessarily preserving pullbacks of monos [GH08]).
And yet, even if for the sake of argument we imagine such a generalisation is found and written, the proofs in this paper would be harder to discover, harder to present, and harder to disseminate, if we did not first have the simpler ‘context-free’ sets-based reasoning of nominal sets.
10.4. Future work
(1) Apply the sets semantics to the -calculus. A nominal algebra axiomatisation of the -calculus is in [GM08b; GM10], building on the nominal rewrite systems for the -calculus from [FGM04; FG07]. A sequent logic style presentation of the -calculus is in [GG10], along with a (non-nominal) Kripke style semantics.
In a sequel to the current paper, we build on this work to give for the first time a topological duality result for the -calculus [GG16].
(2) Generalise the language beyond first-order logic. This paper has only scratched the surface of what might be possible with our semantics. First-order logic has binding, but it does not have binding term-formers nor does it have the ability to reason directly on variable names. We do this all the time in informal mathematical practice—e.g. when we specify first-order logic itself. It is a tricky question what kind of logic is being used here, though it seems to be a nominal one. Permissive-nominal logic is one such [DG10; DG12b]; it enriches first-order logic with binding term-formers and we have used it to axiomatise first-order logic and arithmetic [DG12b]. However, there may be much more to say here. We hope that the sets-based semantics of this paper, which is new, will be a good guide to us here.
(3) Category theory in nominal sets. The fresh-finite limit from Subsection 4.1 is natural if we build category theory internally to nominal sets; because a category is a set of objects and a set of arrows, it is natural in a nominal context to talk about ‘the limit object satisfying a freshness side-condition’. Our treatment of posets in this paper begs generalisation to categories, and we look forward to finding out what story might be told here.29 A hint of this is already in the paper; freshness conditions and adjoints (especially the adjoint explanation of quantifiers) are clearly related. This must be the topic of a later paper.
Another interesting generalisation is to take the notion of -algebra seriously as a categorical framework. The clue to this is to view a category as a kind of -algebra in which each arrow has one ‘free variable’ (its source). In a similar spirit, we might consider a (termlike) -algebra as a kind of semigroup in which we consider [] as composition of and ‘at ’. If we do this, it will not just be because we can: in computing, composition often happens at a location, in some sense.
(4) Stone duality. The representation theorem of this paper uses maximally consistent filters (which we call points), for a suitable notion of filter (Definitions 7.1.1 and 7.2.2). Our logic is classical, so maximally consistent filters do indeed coincide with ultrafilters; see Lemma 7.1.16. We can develop this further by characterising the right notion of topology on a (nominal) topological space and obtain a Stone duality result for FOLeq algebras. This has been studied for the simpler case of first-order logic without equality. See [Gab14] (a sister paper to this one) and in particular see Definition 6.18 of [Gab14] where the topology on points is described. See also [For07], which uses different techniques but has similar goals. Adapting [Gab14] to the definitions and results here would probably require a distinct paper.
(5) The many-sorted case. Our definition of termlike -algebra in Definition 3.1.1 is single-sorted; is a single set with a -action over itself. For applications in computer science it would be useful to have a many-sorted version of FOLeq algebras.
This should be quite easy. It would suffice to generalise Definition 3.1.1: instead of we have a type-indexed family along with atoms for each type and a -action of type . The rest of the mathematics in this paper would be orthogonal and should remain unaffected.
10.5. Summary
We hope that the mathematics of this paper supports the following two arguments:
— The correct notion of model of first-order logic is a FOLeq algebra; this contains just what is necessary to model first-order logic and furthermore it supports good sets-based and poset-based characterisations. Underlying these are - and -powersets, which are remarkable structures, and nominal algebra (itself a logic of independent interest). To express these we need nominal techniques—ZF sets and algebras are not expressive enough.
— Nominal foundations give other new, and not necessarily obvious, opportunities in logic and semantics. We study first-order logic in this paper and the untyped -calculus in [GG16]. We hope and suspect that the ideas behind these examples, and many of the tools we had to develop to carry out these examples, will have further uses (cf. the Future work above).
So this paper gives non-trivial answers to some specific technical questions, but stepping back to look at the larger picture, we see this work as one example of an exciting new way in which to apply nominal techniques in logic and semantics.
REFERENCES
[CF58]Haskell B. Curry and R. Feys, Combinatory logic, vol. I, North Holland, 1958.
[DBB98] Wil Dekkers, Martin Bunder, and Henk Barendregt, Completeness of two systems of illative combinatory logic for first-order propositional and predicate calculus, Archive für Mathematische Logik 37 (1998), 327–341.
[DG10]Gilles Dowek and Murdoch J. Gabbay, Permissive Nominal Logic, Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2010) (New York), ACM Press, 2010, pp. 165–176.
[DG12a], Nominal Semantics for Predicate Logic: Algebras, Substitution, Quantifiers, and Limits, Proceedings of the 9th Italian Convention on Computational Logic (CILC 2012), CEUR workshop proceedings, vol. 857, 2012.
[DG12b], Permissive Nominal Logic (journal version), Transactions on Computational Logic 13 (2012), no. 3.
[DP02]B. A. Davey and Hilary A. Priestley, Introduction to lattices and order, 2 ed., Cambridge University Press, 2002.
[FG07]Maribel Fernández and Murdoch J. Gabbay, Nominal rewriting (journal version), Information and Computation 205 (2007), no. 6, 917–965.
[FGM04] Maribel Fernández, Murdoch J. Gabbay, and Ian Mackie, Nominal Rewriting Systems, Proceedings of the 6th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming (PPDP 2004), ACM Press, August 2004, pp. 108–119.
[FH08]Marcelo Fiore and Chung-Kil Hur, Term equational systems and logics, Electronic Notes in Theoretical Computer Science 218 (2008), 171–192.
[FH10], Second-order equational logic, Proceedings of the 19th EACSL Annual Conference on Computer Science Logic (CSL 2010) (Berlin), Lecture Notes in Computer Science, Springer, 2010.
[Fin85]Kit Fine, Reasoning with arbitrary objects, Blackwell, 1985.
[For07]Henrik Forssell, First-order logical duality, Ph.D. thesis, Carnegie Mellon University, December 2007.
[Gab01]Murdoch J. Gabbay, A Theory of Inductive Definitions with alpha-Equivalence, Ph.D. thesis, University of Cambridge, UK, March 2001.
[Gab07], A General Mathematics of Names, Information and Computation 205 (2007), no. 7, 982–1011.
[Gab09a], Nominal Algebra and the HSP Theorem, Journal of Logic and Computation 19 (2009), no. 2, 341–367.
[Gab09b], A study of substitution, using nominal techniques and Fraenkel-Mostowski sets, Theoretical Computer Science 410 (2009), no. 12-13, 1159–1189.
[Gab11], Foundations of nominal techniques: logic and semantics of variables in abstract syntax, Bulletin of Symbolic Logic 17 (2011), no. 2, 161–229.
[Gab12], Unity in nominal equational reasoning: The algebra of equality on nominal sets, Journal of Applied Logic 10 (2012), 199–217.
[Gab13], Nominal terms and nominal logics: from foundations to meta-mathematics, Handbook of Philosophical Logic, vol. 17, Kluwer, 2013, (author’s/publisher’s numbering).
[Gab14], Stone duality for First-Order Logic: a nominal approach, HOWARD-60. A Festschrift on the Occasion of Howard Barringer’s 60th Birthday, Easychair books, 2014.
[GC11]Murdoch J. Gabbay and Vincenzo Ciancia, Freshness and name-restriction in sets of traces with names, Foundations of software science and computation structures, 14th International Conference (FOSSACS 2011), Lecture Notes in Computer Science, vol. 6604, Springer, 2011, pp. 365–380.
[GG08]Murdoch J. Gabbay and Michael Gabbay, Substitution for Fraenkel-Mostowski foundations, Proceedings of the 2008 AISB Symposium on Computing and Philosophy, 2008, pp. 65– 72.
[GG10]Michael J. Gabbay and Murdoch J. Gabbay, A simple class of Kripke-style models in which logic and computation have equal standing, International Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2010), 2010.
[GG16]Murdoch J. Gabbay and Michael J. Gabbay, Representation and duality of the untyped lambda-calculus in nominal lattice and topological semantics, with a proof of topological completeness, Annals of Pure and Applied Logic (2016), submitted 2012. See also arXiv preprint 1305.5968.
[GH08]Murdoch J. Gabbay and Martin Hofmann, Nominal renaming sets, Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2008), Springer, November 2008, pp. 158–173.
[GLP11] Murdoch J. Gabbay, Tadeusz Litak, and Daniela Petrişan, Stone duality for nominal Boolean algebras with NEW, Proceedings of the 4th international conference on algebra and coalgebra in computer science (CALCO 2011), Lecture Notes in Computer Science, vol. 6859, Springer, 2011, pp. 192–207.
[GM06a] Murdoch J. Gabbay and Aad Mathijssen, Capture-avoiding Substitution as a Nominal Algebra, Proceedings of the 3rd International Colloquium on Theoretical Aspects of Computing (ICTAC 2006) (Berlin), Lecture Notes in Computer Science, vol. 4281, Springer, November 2006, pp. 198–212.
[GM06b], One-and-a-halfth-order logic, Proceedings of the 8th ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming (PPDP 2006), ACM, July 2006, pp. 189–200.
[GM07], A Formal Calculus for Informal Equality with Binding, WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, Lecture Notes in Computer Science, vol. 4576, Springer, July 2007, pp. 162–176.
[GM08a], Capture-Avoiding Substitution as a Nominal Algebra, Formal Aspects of Computing 20 (2008), no. 4-5, 451–479.
[GM08b], The lambda-calculus is nominal algebraic, Reasoning in simple type theory: Festschrift in Honour of Peter B. Andrews on his 70th Birthday (Christoph Benzmüller, Chad Brown, Jörg Siekmann, and Rick Statman, eds.), Studies in Logic and the Foundations of Mathematics, IFCoLog, December 2008.
[GM08c], One-and-a-halfth-order Logic, Journal of Logic and Computation 18 (2008), no. 4, 521–562.
[GM09], Nominal universal algebra: equational logic with names and binding, Journal of Logic and Computation 19 (2009), no. 6, 1455–1508.
[GM10], A nominal axiomatisation of the lambda-calculus, Journal of Logic and Computation 20 (2010), no. 2, 501–531.
[GM11]Murdoch J. Gabbay and Dominic P. Mulligan, Nominal Henkin Semantics: simply-typed lambda-calculus models in nominal sets, Proceedings of the 6th International Workshop on Logical Frameworks and Meta-Languages (LFMTP 2011), EPTCS, vol. 71, September 2011, pp. 58–75.
[Gol89]Robert Goldblatt, Varieties of complex algebras, Annals of Pure and Applied Logic 44 (1989), no. 3, 173–242.
[GP01]Murdoch J. Gabbay and Andrew M. Pitts, A New Approach to Abstract Syntax with Variable Binding, Formal Aspects of Computing 13 (2001), no. 3–5, 341–363.
[Hai00]Mariana Haim, Duality for lattices with operators: A modal logic approach, Ph.D. thesis, University of Amsterdam, 2000.
[Hal06]Paul R. Halmos, Algebraic logic, AMS Chelsea Publishing, 2006.
[HMT85] Leon Henkin, J. Donald Monk, and Alfred Tarski, Cylindric algebras, North Holland, 1971 and 1985, Parts I and II.
[ID96]C. Norris Ip and David L. Dill, Better verification through symmetry, Formal Methods in System Design 9 (1996), 41–75.
[Joh03]Peter T. Johnstone, Sketches of an elephant: A topos theory compendium, Oxford Logic Guides, vol. 43 and 44, OUP, 2003.
[JT52]Bjarni Jonnson and Alfred Tarski, Boolean algebras with operators, American Journal of Mathematics 74 (1952), no. 1, 127–162.
[Kel82]Max Kelly, Basic concepts of enriched category theory, London Mathematical Society Lecture Note Series, no. 64, Cambridge University Press, 1982.
[KW96]Edward Keenan and Dag Westerståhl, Generalized quantifiers in linguistics and logic, Handbook of Logic and Language (J. Van Benthem and A. Ter Meulen, eds.), Elsevier, 1996, pp. 837–894.
[MM92] Saunders Mac Lane and Ieke Moerdijk, Sheaves in geometry and logic: A first introduction to topos theory, Universitext, Springer, 1992.
[Mon00] Donald Monk, An introduction to cylindric set algebras, Logic journal of the IGPL 8 (2000), no. 4, 451–492.
[MVF02] William McCune, Robert Veroff, Branden Fitelson, Kenneth Harris, Andrew Feist, and Larry Wos, Short single axioms for boolean algebra, Journal of Automated Reasoning 1 (2002), no. 29, 1–16.
[Per82]Alan J. Perlis, Epigrams on programming, September 1982, Available online www.cs.yale. edu/quotes.html, pp. 7–13.
[Pit13]Andrew M. Pitts, Nominal sets: Names and symmetry in computer science, Cambridge University Press, May 2013.
[Sch67]Moses Schönfinkel, On the building blocks of mathematical logic, From Frege to Gödel: a source book in mathematical logic, 1879-1931 (Jean van Heijenoort, ed.), Harvard University Press, 1967, Translated from the German by Stefan Bauer-Mengelberg.
[SP05]Mark R. Shinwell and Andrew M. Pitts, Fresh objective Caml user manual, Tech. Report UCAM-CL-TR-621, University of Cambridge, 2005.
[Tar44]Alfred Tarski, The semantic conception of truth and the foundations of semantics, Philosophy and Phenomenological Research 4 (1944).
[TG87]Alfred Tarski and Steven Givant, A formalization of set theory without variables, vol. 41, American Mathematical Society Colloquium Publications, 1987.
[vD94]Dirk van Dalen, Logic and structure, Universitext, Springer, 1994, Third, augmented edition.
[Wes89]Dag Westerståhl, Quantifiers in formal and natural languages, Handbook of Philosophical Logic, Synthèse, vol. 4, Reidel, 1989, pp. 1–131.
A. NOMINAL ALGEBRAIC AXIOMATISATION OF FRESH-FINITE LIMITS AND EQUALITY
Definition 4.1.1 set up the notion of a fresh-finite limit . Proposition 4.1.5 split this notion up into three parts which are sometimes more convenient for proofs: , , and . These definitions are ‘poset-flavoured’; that is, we talk about and greatest lower bounds for .
We now set about axiomatising this structure in nominal algebra [GM09]. That is, we will characterise FOLeq algebras in terms of an underlying nominal set and functions on that set satisfying nominal equalities.
It is convenient to do this in three stages: bounded meet-semilattices with , then bounded lattices with , then FOLeq algebras.
A.1. Bounded meet-semilattices with
A bounded meet-semilattice in nominal sets is a tuple ) where () is a nominal set and is an equivariant top element and : () is an equivariant function, such that and form an idempotent monoid:
Here, range over elements of .
As standard, a meet-semilattice acquires a partial order by setting when . A bounded meet-semilattice yields a poset with a top element ().
(Recall that is shorthand for () .)
If then .
means . We apply to both sides and use ().
Suppose is a bounded meet-semilattice with . Then with the partial order from Definition A.1.2 we have the following:
— is a top element.
— is a limit for .
— is an #limit for .
Every bounded meet-semilattice with can be viewed as a nominal poset with fresh-finite limits, and vice versa.
Definition A.1.7 and Proposition A.1.8 merely package the observations above in categorical language:
Given and bounded meet-semilattices with , a homomorphism : is a function on the underlying nominal sets such that:
— ((), meaning that is equivariant (Definition 2.1.6).
— ( and (() () and (.
Given and nominal posets with fresh-finite limits, a homomorphism : is a function on the underlying nominal sets such that:
— (() (so is equivariant).
Write Semi for the category of bounded meet-semilattices with and homomorphisms between them, and Poset for the category of nominal posets with fresh-finite limits.
The natural functors mapping between Semi and Poset define an isomorphism of categories.
A.2. Bounded lattices with
Our version of FOLeq is classical and has negation. This means that it has , but by dualising with negation it also has . This has a minor effect on the natural axiomatisation of . We therefore briefly sketch the case of for bounded lattices, of which FOLeq is a special case.
A bounded lattice in nominal sets is a tuple ) where () is a nominal set which we may just write , and are equivariant top and bottom elements and : () are equivariant functions, such that and form an idempotent monoid and so do and ,
and and satisfy absorption
Here, range over elements of .
Similarly to Definition A.1.2, a bounded lattice is a poset by taking to mean or (the two conditions are provably equivalent).
A generalised universal quantifier on a bounded lattice is an equivariant map : () satisfying the equalities in Figure 4.
Comparing Definitions A.1.3 and Definition A.2.2, we note that (#) has vanished, and that () is not a perfect dual to ().
The disappearance of (#) is explained in Proposition A.2.4.
The lack of duality between () and () is natural; () orients with respect to so it would be surprising (and wrong) if displayed perfectly dual behaviour with respect to .30
Suppose is a bounded lattice with and . Then (#) from Definition A.1.3 follows from the other axioms of a generalised universal quantifier on a bounded lattice.
That is, # implies
We note that () () so that . Furthermore by () , and we are done.
Suppose is a bounded lattice with a generalised universal quantifier . Then is the #limit for .
Axioms of the type presented in Definition A.2.2 underlie the nominal algebraic axiomatisation of first-order quantification in e.g. [GM08c; Gab14].
A.3. FOLeq algebras algebraically
We are now ready to give a full axiomatisation of a FOLeq algebra, in nominal algebra in the sense of the formal language described in [GM09]. This nominal algebra theory builds on the nominal algebra axiomatisations of substitution and first-order logic originally developed in [GM06a; GM06b; GM08a; GM08c].
Suppose is a termlike -algebra. The FOLeq algebras over (Definition 4.4.3) are precisely characterised as an underlying nonempty nominal set along with
— an equivariant -action sub : (), written infix [];
— an equivariant function : ;
— an equivariant function : ,
— an equivariant function : (), and
— an equivariant function : (),
such that:
(1) sub satisfies the axioms of a -action over from Figure 1 and
(2) if we take () (for any ) and () and then , , , and satisfy the axioms of a bounded lattice from Definition A.2.1,
(3) in addition31
(4) satisfies the axioms of a generalised universal quantifier from Figure 4, and finally
(5) satisfies the axioms
We have all the pieces, we just need to put them together.
Suppose is a FOLeq algebra. We take to be the top element, to be the limit of , to be the #limit of , to be the complement of in (which is unique by Lemma 4.1.7), and to be ()[] where is the equality of (the simultaneous -action is from Definition 3.5.2). Then:
— By assumption in Definition 4.4.3 the -action satisfies the axioms of Figure 1.
— By properties of limits and complements , , , and satisfy the axioms of a bounded lattice.
— By assumption is distributive (Definition 4.4.1) and complemented, and it follows that distributes over and .
— By Lemma 4.1.9 satisfies () from Figure 4. By routine calculations on limits satisfies ().32 By assumption is distributive (Definition 4.4.1), so () holds. By the definition of a fresh-finite limit .
Now suppose has all the structure of the statement of this theorem. Definition 4.4.3 defines a FOLeq algebra to be a finitely fresh-complete complemented nominal poset with a compatible -algebra structure and an equality. So we consider each property in turn:
— Finitely fresh-complete. By standard arguments using the axioms is a top element and is a limit for . By Corollary A.2.5 is an #limit for . It follows by Proposition 4.1.5 that is finitely fresh-complete.
— Complements. Again it follows from the axioms that is a complement.
— Compatible -algebra structure. By assumption sub satisfies the axioms from Figure 1, so has a -algebra structure of . By our assumptions (condition 1 in the statement of this theorem) it is compatible.
— Equality. It follows from our assumptions that is an equality in the sense of Definition 4.3.1.33
B. ON THE LEIBNITZ EQUALITY
In Remark 6.3.2 we noted that Definition 6.3.1 is a form of Leibnitz equality: () when it ‘cannot distinguish between and ’.
Could it be that () is also equal to ()? After all, if () then also ‘cannot distinguish and ’.
This notion is too weak. To see this intuitively, consider that the unordered pair is invariant under swapping and , but is not invariant under converting into to obtain .
We note that a strengthened version of Definition 6.3.1 is possible:
() if and only if for all atoms , [[].
Clearly if for all atoms , [[], then for all but finitely many , [ [].
Conversely, suppose [[] for all but finitely many , and consider any atom and element . Now choose one such that # and [[] (this is always possible because all but finitely many satisfy each condition). By () [))[] and [))[] and it follows using Proposition 3.2.2 repeatedly that [] if and only [].
Given Lemma B.0.3, could Definition 6.3.1 use instead of the less familiar ?
Yes, but the use of the -quantifier is preferable. It is a weaker proof-obligation; it is strictly easier to prove [[] than it is to prove [[], because we have to worry about ‘fewer values’ for .
This is exploited immediately after Definition 6.3.1 in Lemma 6.3.4 when we use two -quantifiers, one for and one for . If we had taken Lemma B.0.3 as our definition instead, then we would have had to worry about the case ; something similar happens in Proposition 6.3.8.
Thus, the form used in Definition 6.3.1 is more elementary and convenient, though it is indeed logically equivalent to the form of Lemma B.0.3.
We mention that Definitions 3.3.2 and 6.3.1 have a kind of purely nominal precedent:
Suppose is a nominal set and NomPow() are finitely supported subsets of (Subsection 2.4.1), and suppose # and # . Write # and #. Then
The left-to-right implication is immediate. For the right-to-left implication it suffices to prove that . So suppose . Choose fresh ; then () and by Proposition 2.3.4 #() so () so that .
For more on this, see [Gab11, Subsection 9.5].
Notes
1Chronologically the axioms came first, and this paper emerged from efforts to understand these axioms’ semantics. ↩
2Just sometimes, pedantry has its limit. ↩
3Here is understood to 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 . ↩
4The reasoning in this paper could in principle be fully formalised in a sets foundation with atoms, such as Zermelo-Fraenkel set theory with atoms ZFA. Nominal sets can be implemented in ZFA sets such that nominal sets map to equivariant elements (elements with empty support) and the permutation action maps to ‘real’ permutation of atoms in the model. See [Gab11, Subsection 9.3] and [Gab11, Section 4]. ↩
5There is also a nice proof of this fact by direct calculations; see [Gab11, Theorem 2.19]. However, it just instantiates Theorem 2.3.2 to the particular Υ specifying support. ↩
6That is, the axioms except (a), since we do not assume a function . ↩
7To be precise, the class of all -algebras is a variety in the nominal algebraic sense of [Gab09a], whereas the class of exact -algebras is a quasivariety. ↩
8We care most about the case that NomPow()— is finitely supported—but this result does not depend on that. ↩
9Recall that need not have finite support here; see Remark 3.2.5. ↩
10The proof of Lemma 6.3.6 will be in one line precisely because of this design for Definition 3.4.1. ↩
11Pow is the -powerset and is from Definition 3.2.4. is the -powerset and is from 3.4.6. ↩
12So if and only if . ↩
13Part 4 has an alternative one–line proof from Theorem 2.3.2 and (#); we use this argument in Lemma 5.2.11 for the case of . ↩
14The set [] could be finite: either # so that by (#) [ for all ; or is finite, so that in particular maps every to some constant element in . ↩
15We will only really care about the case that the -action satisfies the stronger property of being compatible (Definition 4.2.1). However, compatibility includes conditions involving , so we prefer to be more precise and only insist on what we need to make the result work, which is monotonicity. ↩
16Strictly speaking we should write [()]. See the notation in Definition 3.1.1. ↩
17In fact we only care about here, not . ↩
18The author is using nominal abstract syntax to do this [GP01; Gab11]. A treatment of this with all definitions and a full proof of equivalence with ‘ordinary’ syntax is in [Gab11, Section 5]. ↩
19It would be easy to hide this with a bit of hand-waving. However, in the context of nominal techniques, we give it its own result and indicate the issues involved. ↩
20Note that as discussed above, the story is more subtle than that. Ultrafilters can have finite support; it is just that the finitely supported ultrafilters represent worlds in which quantification is not interesting. More work could be done to make this discussion fully formal. ↩
21The finitely supported are such that there exists a finite such that for all , ((); it is not worth our while to impose this restriction, though it would do no harm to do so. ↩
22The reverse implication does not hold; having finitely supported limits and substitution is a far stronger condition. ↩
23In [GM11] are nominal Henkin-style semantics for higher-order logic in a typing context, but not a valuation context. We calculated denotation in a context of static (typing) information, but we were not forced to also use an explicit context of valuations—and we did not. ↩
24A pure nominal treatment of syntax-with-binding, rather than its semantics, is also possible. Indeed, that problem is what motivated the initial developments behind nominal techniques [Gab01; GP01; Gab11]. ↩
25Note: The logic of [Gab14] did not include equality and considers duality instead of completeness. ↩
26E.g. supp()supp() and []. ↩
27Polyadic and cylindric algebras are away from us here, but by using monoids instead of groups they cannot guarantee that atoms that were distinct, remain distinct. In this light, our permutative convention from Definition 2.1.1, which goes back to [GM06a; GM06b; GM08c], that in informal mathematical discourse in nominal techniques , , and range over distinct atoms, seems very important. ↩
28...which is what we axiomatise in this paper. We hope it is quite clear by now how a multi-sorted logic, or an intuitionistic logic, would work in our nominal semantics. ↩
29There is a general theory of categories in universes other than ZF sets [Kel82]. But we are not just enriching the notion of category; we are also enriching the notion of limit. So whatever mathematics emerges from that seems unlikely to be just a special case of the general machinery. ↩
30This is to be contrasted with the axiomatisation of and Stone duality result for the quantifier in [GLP11]. The quantifier is self-dual, and is symmetric in its interaction between and . ↩
31This axiomatisation is not minimal, but it is readable. The interested reader is referred elsewhere [MVF02] for what can be achieved in terms of trading off the number of axioms against readability. ↩
32It is not quite that simple; we are using fresh-finite limits. But it all works out. ↩
33Note that the statements are slightly different; Definition 4.3.1 assumes an element whereas above we assume an equivariant function and in condition 1 we assume that substitution distributes over it. ↩