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

Semantics out of context: nominal absolute denotations for first-order logic and computation

Murdoch J. Gabbay, Heriot-Watt University, Scotland, UK http://www.gabbay.org.uk

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 a 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 ∀a.φ is interpreted using a new notion of ‘fresh-finite’ limit ⋀#a⟦φ⟧ 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 ∫a is a binder which binds a, so that a in ∫a f(a, b) is bound. The same phenomenon appears in logic and computation, so that e.g. we write ∀a.P(a, b), λa.ab, let a=2 in a+b, 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:

— ∫a f(a, b) means “take a value for b to be fixed by some context and vary possible values for a, taking an integral”.

— ∀a.P(a, b) means “take a value for b to be fixed by some context and vary possible values for a, taking a(n infinite) logical conjunction”.

— λa.f(a) means “input a value from the user, associate that value to a, and calculate f 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:

∫a,∫b,∫c or ∀a, ∀b, ∀c, ...

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 ∫a, ∀a, and λa. 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 ∀a (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 X of truth-values with an entailment ordering ≤ and assume greatest

lower bounds (and some other structure). Given x, y ∈X we declare x ∧y to be the greatest lower bound (the limit) of x and y.

— 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 X and subsets U, V ⊆X, and we declare U ∧V to be U ∩V .

— 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 X and functions ⊥, ∧, ¬, and ∀ on X 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 x ∈𝒳 may ‘contain’ finitely many names a, b, c ∈𝔸”. 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 x has finite support (Definition 2.1.8).

For instance, here are some nominal sets:

— The set of finite sets of atoms:

{∅, {a}, {b}, {c}, . . . , {a, b}, {a, c}, . . .} .

— The set of complements of finite sets of atoms:

{𝔸, 𝔸\{a}, 𝔸\{b}, 𝔸\{c}, . . . , 𝔸\{a, b}, 𝔸\{a, c}, . . .} .

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 x’ is not equal to the notion of ‘being a set element of x’. For instance if we take x = 𝔸\{a}, then x contains infinitely many elements—but its support contains precisely the atom that is not an element of x, namely a.

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

Definition 2.1.1

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

Definition 2.1.2

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

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

Notation 2.1.3

If A ⊆𝔸 write

fix(A) = {π | ∀a∈A.π(a) = a}.
Definition 2.1.4

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

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

Definition 2.1.5

Call a set with a permutation action 𝒳 a nominal set when every x∈|𝒳| has finite support. 𝒳, 𝒴, 𝒵 will range over nominal sets.

Definition 2.1.6

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

The category of nominal sets and equivariant functions between them is usually called the category of nominal sets [Gab01; GP01; Gab11; Pit13].

Remark 2.1.7

‘Equivariant’ appears in Definition 2.1.6 referring to functions between nominal sets, in Definition 2.1.8 referring to elements of nominal sets, and in Theorem 2.3.2 referring to predicates and functions in the language of ZFA set theory.

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.

Definition 2.1.8

Suppose 𝒳 is a nominal set and x∈|𝒳|. Define the support of x by

supp(x) =⋂{A | A finite and supports x}.

If supp(x) = ∅ we call x equivariant.

Notation 2.1.9

— Write a#x as shorthand for a ∉ supp(x) and read this as a is fresh for x.

— Given atoms a1, . . . , an and elements x1, . . . , xm write a1, . . . , an#x1, . . . , xm as shorthand for {a1, . . . , an} ∩⋃1≤j≤m supp(xj) = ∅. That is: ai#xj for every i and j.

Proposition 2.1.10

If A ⊆𝔸 is finite and supports x, and a ∈𝔸 and a#x, then A\{a} supports x.

Proof

Suppose π ∈ fix(A\{a}). We assumed a#x so choose an A′ ⊆𝔸 such that A′ is finite, A′ supports x, and a ∉A′. Also, choose some fresh a′ (so a′ ∉A∪{a}∪A′).

Write τ = (a′ a). Note that τ·x = x by Definition 2.1.4, because A′ supports x and τ ∈ fix(A′). It is a fact that (τ ◦π ◦τ)(a) = a for every a∈A, so τ ◦π ◦τ ∈ fix(A). Also by the group action (τ ◦π ◦τ)·x = τ·(π·(τ·x)). Since A supports x we have τ·(π·(τ·x)) = x by Definition 2.1.4.

We apply τ to both sides, recall that τ·x = x, and conclude that π·x = x as required.End of proof

Theorem 2.1.11

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

Proof

Consider a permutation π ∈ fix(supp(x)) and write {a1, . . . , an} = nontriv(π). Choose any finite A⊆𝔸 that supports x, so by construction supp(x)⊆A.

By Proposition 2.1.10 A\nontriv(π) supports x. By construction π ∈ fix(A\nontriv(π)), so by Definition 2.1.4 π·x = x as required.End of proof

Corollary 2.1.12

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

(2) If π(a) = π′(a) for every a∈supp(x) then π·x = π′·x.

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

Proof

By routine calculations from the definitions and from Theorem 2.1.11.End of proof

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 π·a = π(a). 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 a ∈𝔸 and never write a∈|𝔸|.2

2.2.2. Cartesian product.

𝒳 × 𝒴 is a nominal set with underlying set {(x, y) | x∈|𝒳|, y∈|𝒴|} and the pointwise action π·(x, y) = (π·x, π·y).

2.2.3. Tensor product.

𝒳⊗𝒴 is a nominal set with underlying set {(x, y) | x∈|𝒳|, y∈|𝒴|, supp(x)∩ supp(y) = ∅} 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(π·x) = π·supp(x).

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

(π·f)(x) = π·(f(π-1·x)).

The conjugation action can be rephrased as ‘permutations distribute’ (cf. Theorem 2.3.2 below):

Lemma 2.2.1

If f∈|𝒳→𝒴| then π·f(x) = (π·f)(π·x).

Proof

By easy calculations.End of proof

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.

Lemma 2.2.2

f ∈|𝒳⇒𝒴| is equivariant in the sense of Definition 2.1.6 if and only if it is equivariant in the sense of Definition 2.1.8.

Proof

We sketch the proof: If π·f = f then for any x∈𝒳 we have by Lemma 2.2.1 that π·(f(x)) = (π·f)(π·x) = f(π·x). Conversely if for any x∈𝒳 we have π·(f(x)) = f(π·x) then by the conjugation action

(π·f)(x) = π·(f(π-1·x)) = f(π·(π-1·x)) = f(x).End of proof

2.2.6. Full powerset

Definition 2.2.3

Suppose 𝒳 is a set with a permutation action. Give subsets X ⊆|𝒳| the pointwise permutation action

π·X = {π·x | x ∈X}.
Example 2.2.4

A useful instance of the pointwise action is for sets of atoms. As discussed in Subsection 2.2.1 above, if a ∈𝔸 then π·a = π(a). Thus if A ⊆𝔸 then

π·A means {π(a) | a ∈A}.
Lemma 2.2.5

Continuing the notation of Definition 2.2.3,

X is equivariant in the sense of Definition 2.1.8 ⇔ ∀π.∀x∈|𝒳|.(x ∈X ⇔π·x ∈X).

Proof

If X is equivariant then by Corollary 2.1.12 ∀π.π·X = X. It follows that x ∈X ⇔x ∈ π-1·X ⇔π·x ∈X.

Conversely if ∀π.∀x∈|𝒳|.(x ∈X ⇔π·x ∈X) then also x ∈X ⇔π-1·x ∈X ⇔x ∈π·X, so that π·X = X. This is for any π, so using Corollary 2.1.12 we have that supp(X) = ∅.End of proof

Definition 2.2.6

Define PowSet(𝒳) the full powerset of 𝒳 to be the set with a permutation action with

— underlying set {X | X ⊆|𝒳|} (the set of all subsets of |𝒳|), and

— the pointwise action π·X = {π·x | x ∈X}.

Remark 2.2.7

Even if 𝒳 is a nominal set, PowSet(𝒳) need not be a nominal set. To see why, take 𝒳 to be equal to 𝔸 = {a, b, c, d, e, f, . . . } and consider the set

comb = {a, c, e, . . . }

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.

Remark 2.3.1

The languages of ZFA set theory and FM set theory are identical: first-order logic with equality = and sets membership ∈.

Theorem 2.3.2

If x is a list x1, . . . , xn, write π·x for π·x1, . . . , π·xn. Suppose Φ(x) is a predicate in the language of ZFA/FM set theory, with free variables x. Suppose Υ(x) is a function specified in the language of ZFA/FM set theory, with free variables x. Then we have the following principles:

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

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

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

Proof

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

Remark 2.3.3

Theorem 2.3.2 is three fancy ways of observing that if a specification is symmetric in atoms, the the result must be at least as symmetric as the inputs. The benefit of using atoms (instead of e.g. numbers) to model names makes this a one-line argument.4

Proposition 2.3.4

supp(π·x) = π·supp(x) (which means {π(a) | a ∈ supp(x)}).

Proof

Immediate consequence of part 2 of Theorem 2.3.2.5End of proof

Definition 2.3.5

Write Иa.Φ(a) for ‘{a | ¬Φ(a)} is finite’. We call this the И quantifier.

Remark 2.3.6

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

Remark 2.3.7

И 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 a’, 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:

Theorem 2.3.8

Suppose Φ(z, a) is a predicate in the language of ZFA/FM set theory, with free variables z, a. Suppose z denotes elements with finite support. Then the following are equivalent:

∀a.(a ∈𝔸 ∧a#z) ⇒Φ(z, a)Иa.Φ(z, a) ∃a.a ∈𝔸 ∧a#z ∧Φ(z, a)
Proof

Where convenient we may write z as z1, . . . , zn.

— Suppose Φ(z, a) holds for every atom a ∈𝔸\ ⋃1≤i≤n supp(zi). By assumption z denotes elements with finite support, and it is a fact that a finite union of finite sets is finite, so 𝔸 \ ⋃1≤i≤n supp(zi) is cofinite. It follows that Иa.Φ(z, a) holds.

— Suppose A ⊆𝔸 is cofinite and Φ(z, a) for every a∈A. As in the previous point, there exists some a∈A such that a#zi for every 1≤i≤n. It follows that ∃a∈𝔸.(a#z ∧ Φ(z, a)).

— Now suppose Φ(z, a) holds for some a ∈𝔸\ ⋃1≤i≤n supp(zi). By part 1 of Theorem 2.3.2 Φ((a′ a)·z, a′) holds for any a′∈𝔸. Choosing a′#z we have by part 1 of Corollary 2.1.12 that (a′ a)·zi = zi for every 1≤i≤n. Thus ∀a∈𝔸.(a#z ⇒ Φ(z, a)) holds.End of proof

Remark 2.3.9

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 a is fresh for u and v. 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 a 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 X∈|PowSet(𝒳)| that are finitely supported, and

— with the pointwise action π·X = {π·x | x ∈X} 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 A supports X∈|NomPow(𝒳)| then A must support every x ∈X. This is incorrect:

Lemma 2.4.1

It is not true in general that if X∈|NomPow(𝒳)| and x ∈X then supp(x) ⊆ supp(X).

Proof

It suffices to provide a counterexample. Take 𝒳 = 𝔸 (the nominal set of atoms with the natural permutation action, from Subsection 2.2.1) and X = 𝔸 ⊆|𝔸| (the underlying set of the nominal set of all atoms, i.e. the set of all atoms!).

It is easy to check that supp(X) = ∅ and a ∈X and supp(a) = {a} ⊈∅.End of proof

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.

Lemma 2.4.2

If X∈|NomPow(𝒳)| and a#X then there exists an x ∈X with a#x.

Proof

Choose x′ ∈X and fresh b (so b#x′, X). By Corollary 2.1.12 (b a)·X = X, so (b a)·x ∈X. By Proposition 2.3.4 a#(b a)·x.End of proof

2.4.2. Strictly finitely supported powerset.

Suppose 𝒳 is a nominal set.

Definition 2.4.3

Call X ⊆|𝒳| strictly supported by A ⊆𝔸 when

∀x∈X.supp(x) ⊆A.

If there exists some finite A which strictly supports X, then call X strictly finitely supported (see [Gab11, Theorem 2.29]).

Write Strict(𝒳) for the set of strictly finitely supported X ⊆|𝒳|. That is:

Strict(𝒳) = {X ⊆|𝒳| | ∃A⊆𝔸.A finite ∧X strictly supported by A}

Lemma 2.4.4

If X ∈ Strict(𝒳) then:

(1) ⋃{supp(x) | x∈X} is finite.

(2) ⋃{supp(x) | x∈X} = supp(X).

(3) If X ⊆|𝒳| is strictly finitely supported then it is finitely supported.

(4) x ∈X implies supp(x) ⊆ supp(X) (contrast this with Lemma 2.4.1).

(5) Strict(𝒳) with the pointwise permutation action is a nominal set.

Proof

The first part is immediate since by assumption there is some finite A⊆𝔸 that bounds supp(x) for all x ∈X. 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.End of proof

Example 2.4.5

(1) ∅⊆|𝔸| is finitely and strictly finitely supported by ∅.

(2) {a} is finitely supported by {a} and also strictly finitely supported by {a}.

(3) 𝔸 ⊆|𝔸| is finitely supported by ∅ but not strictly finitely supported.

(4) 𝔸\{a} is finitely supported by {a} but not strictly finitely supported.

(σa) a[a↦→x] = x(σid) x[a↦→a] = x(σ#) a#x ⇒ x[a↦→u] = x(σα) b#x ⇒ x[a↦→u] = ((b a)·x)[b↦→u](σσ) a#v ⇒ x[a↦→u][b↦→v] = x[b↦→v][a↦→u[b↦→v]](σσ) a#v ⇒ p[v←↤b][u←↤a] = p[u[b↦→v]←↤a][v←↤b]
Fig. 1: Nominal algebra axioms for σ and σ

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

Definition 3.1.1

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

— a nominal set (|𝒰|, ·) which we may write just as 𝒰; and

— an equivariant σ-action sub𝒰: (𝒰 × 𝔸 × 𝒰)⇒𝒰, written infix v[a↦→u]; and

— an equivariant injection atm𝒰: 𝔸⇒𝒰,

such that the equalities (σa), (σid), (σ#), (σα), and (σσ) of Figure 1 hold, where x, u, and v range over elements of |𝒰|. We usually write atm𝒰 invisibly (so we write atm𝒰(a) just as a), and we may omit subscripts (so we may write sub𝒰 as sub if we are confident that 𝒰 is clear and understood).

Remark 3.1.2

We unpack what equivariance from Definition 2.1.6 means for the σ-action from Definition 3.1.5: for every x∈|𝒳|, atom a, and u∈|𝒰|, and for every permutation π, we have that

π·(x[a↦→u]) = (π·x)[π(a)↦→π·u].

Similarly for the equivariant σ-action in Definition 3.1.6 below.

Example 3.1.3

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 a ∗b is a term, π·(a ∗b) is π(a) ∗π(b), and (a ∗b)[a↦→2][b↦→3] is 2 ∗ 3. Such a syntax is defined in this paper in Definition 5.1.1 as r ::= a | f(r1, . . . , rar(f)).

Similarly, untyped λ-terms quotiented by α-equivalence form a termlike σ-algebra, where the σ-action is capture-avoiding substitution. So [(λa.b)]α[b↦→a] = [λa′.a]α.

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 u. However, predicates do form a (not-necessarily-termlike) σ-algebra; see Definition 3.1.5.

Remark 3.1.4

The ‘σ’ in σ-action stands for ‘substitution’. No connection is suggested with the notion of sigma-algebra from measure theory.

Definition 3.1.5

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 sub𝒳: (𝒳 × 𝔸 × 𝒰)⇒𝒳, written infix x[a↦→u];

such that the equalities (σid), (σ#), (σα), and (σσ) of Figure 1 hold,6 where x ranges over elements of |𝒳| and u and v range over elements of |𝒰|. As for termlike σ-algebras, we may omit the subscript 𝒳.

Definition 3.1.6

Suppose 𝒰 = (|𝒰|, ·, sub, atm) is a termlike σ-algebra.

An σ-algebra (spoken: amgis-algebra) over 𝒰 is a tuple 𝒫 = (|𝒫|, ·, 𝒰, amgis𝒫) of:

— a set with a permutation action (|𝒫|, ·) which we may write just as 𝒫; and

— an equivariant amgis-action amgis𝒫: (𝒫 × 𝒰 × 𝔸)⇒𝒫, written infix p[u←↤a],

such that the equality (σσ) of Figure 1 holds, where p ranges over elements of |𝒫| and u and v range over elements of |𝒰|. We may omit the subscript 𝒫.

Remark 3.1.7

[u←↤a] looks like [a↦→u] written backwards, and a casual glance at (σσ) suggests that it is just (σσ) written backwards. This is not quite true: we have u[b↦→v] on the right in (σσ) and not ‘u[v←↤b]’ (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:

Lemma 3.1.8

If a#u then a#x[a↦→u]. As a corollary,

supp(x[a↦→u]) ⊆(supp(x)\{a}) ∪supp(u).
Proof

Choose fresh b (so b#x, u). By (σα) x[a↦→u] = ((b a)·x)[b↦→u]. Also by part 1 of Corollary 2.1.12 (b a)·u = u and by Theorem 2.3.2 (b a)·(x[a↦→u]) = ((b a)·x)[b↦→(b a)·u]. We put this all together and we deduce that (b a)·(x[a↦→u]) = x[a↦→u]. It follows by part 3 of Corollary 2.1.12 that a ∉ supp(x[a↦→u]).

The corollary follows since by Theorem 2.3.2 supp(x[a↦→u]) ⊆ supp(x)∪{a}∪supp(u).End of proof

Remark 3.1.9

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 r is a term, then support coincides with free atoms/variables fa(-) and fa(φ[a↦→r]) ⊆ (fa(φ)\{a}) ∪ fa(r).

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:

Lemma 3.1.10

If b#x then x[a↦→b] = (b a)·x.

Proof

By (σid) (b a)·x = ((b a)·x)[b↦→b]. By (σα) ((b a)·x)[b↦→b] = x[a↦→b].End of proof

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:

Lemma 3.1.11

If U⊆|𝒰| is finitely supported and a#U then a#{x[a↦→u] | u∈U}. As corollaries, the following freshnesses all hold:

a#{x[a↦→u] | u∈|𝒰|} a#{x[a↦→n] | n∈𝔸}
Proof

We use part 3 of Corollary 2.1.12. Choose fresh b (so b#x, U). Note by Corollary 2.1.12 (since a, b#U) that (b a)·U = U so that by Lemma 2.2.5 ∀u∈|𝒰|.u ∈U ⇔ (b a)·u ∈U. Then we reason as follows:

(b a)·{x[a↦→u] | u∈U} = {(b a)·(x[a↦→u]) | u∈U} Pointwise action= {((b a)·x)[b↦→(b a)·u] | u∈U} Theorem 2.3.2= {((b a)·x)[b↦→u] | u∈U} (b a)·U = U= {x[a↦→u] | u∈|𝒰|} (σα), b#x

The proof for a#{x[a↦→n] | n∈𝔸} is similar.End of proof

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.

Definition 3.2.1

Suppose 𝒳 = (|𝒳|, ·, 𝒰, sub𝒳) is a σ-algebra over a termlike σ-algebra 𝒰.

Give subsets p ⊆|𝒳| pointwise actions as follows:

π·p = {π·x | x ∈p} p[u←↤a] = {x∈|𝒳| | x[a↦→u] ∈p} u∈|𝒰|
Proposition 3.2.2

Suppose 𝒳 is a σ-algebra over a termlike σ-algebra 𝒰. Suppose p ⊆|𝒳|. Then:

— x ∈p[u←↤a] if and only if x[a↦→u] ∈p.

— x ∈π·p if and only if π-1·x ∈p.

Proof

By easy calculations on the pointwise actions in Definition 3.2.1.End of proof

Remark 3.2.3

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 [a↦→u] get turned round to [u←↤a]?

When we take the powerset of a set V , V is in negative position (i.e. PowSet(V) is equivalent to a function-space V →2 and here V is to the left of the arrow). This implies that any modal operations which we assume on elements of V , 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.

Definition 3.2.4

Suppose 𝒳 is a σ-algebra over a termlike σ-algebra 𝒰.

Define the σ-powerset algebra Powσ(𝒳) by setting

— |Powσ(𝒳)| to be the set of all subsets p ⊆|𝒳| (Definition 2.2.6) with

— permutation action π·p and

— amgis-action p[u←↤a] from Definition 3.2.1.

Remark 3.2.5

Note that p ⊆|𝒳| need not have finite support in Definition 3.2.4.

Our notion of σ-algebra (Definition 3.1.6) admits p 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.

Proposition 3.2.6

If 𝒳 is a σ-algebra over a termlike σ-algebra 𝒰 then Powσ(𝒳) (Definition 3.2.4) is an σ-algebra over 𝒰.

Proof

By Theorem 2.3.2 the operations are equivariant. We verify rule (σσ) from Figure 1:

— Property (σσ). We use (σσ). Suppose a#v. Then:

x ∈p[v←↤b][u←↤a] ⇔x[a↦→u][b↦→v] ∈p Proposition 3.2.2⇔x[b↦→v][a↦→u[b↦→v]] ∈p (σσ), a#v⇔x ∈p[u[b↦→v]←↤a][v←↤b] Proposition 3.2.2End of proof
Remark 3.2.7

It is interesting to note a non-result of Powσ(𝒳). Consider (σ#); let us try to dualise it as we dualised (σσ) to (σσ) in Proposition 3.2.6.

(σ#) a#p ⇒p[u←↤a] = p Bad axiom

Suppose a#p. Then

x ∈p[u←↤a] ⇔x[a↦→u] ∈p Proposition 3.2.2⇔????

and now we are stuck: a#p does not imply that a#x, so we cannot use (σ#) (e.g. if p = 𝔸 then b ∈𝔸 and b ∈ supp(b); more on this in [Gab11, Subsection 9.5]).

Remark 3.2.8

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 (r1, r2) and one unary term-former f. Consider the term (f(c), f(b)) and interpret [a↦→r] as substitution and [r←↤a] as pattern-matching. Then

(f(c), f(b))[c←↤b][f(b)←↤a] = (f(b), f(b))[f(b)←↤a] = (a, a) and (f(c), f(b))[f(b)[b↦→c]←↤a][c←↤b] = (f(c), f(b))[f(c)←↤a][c←↤b] = (a, f(b))[c←↤b] = (a, f(b))

and (a, a) ≠ (a, f(b)).

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 Powσ; see Subsection 6.3 and in particular Lemma 6.3.4.

To understand exactness, it is interesting to consider an easy property of σ-algebras:

Lemma 3.3.1

If a#x, y then x[a↦→u] = y[a↦→u] implies x = y.

Proof

Immediate from (σ#).End of proof

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.

Definition 3.3.2

Call an σ-algebra 𝒫 exact when if p, q∈|𝒫| and u∈|𝒰| then

Иc.p[u←↤c] = q[u←↤c] implies p = q.

In words, 𝒫 is exact when for every p, q, and u, if p[u←↤c] and q[u←↤c] are equal for most (meaning ‘for all but finitely meany’) c then p and q are equal.

Proposition 3.3.3

Suppose 𝒳 is a σ-algebra over a termlike σ-algebra 𝒰. Then Powσ(𝒳) is an exact σ-algebra over 𝒰.

Proof

By Proposition 3.2.6 Powσ(𝒳) is an σ-algebra over 𝒰. It remains to prove exactness.

Suppose p, q∈|Powσ(𝒳)| and u∈|𝒰|, and suppose Иc.p[u←↤c] = q[u←↤c]. We now check that for all x∈|𝒳| it is the case that x ∈p if and only if x ∈q. We reason as follows:

x ∈p ⇔Иc.x[c↦→u] ∈p (σ#), c#x⇔Иc.x ∈p[u←↤c] Proposition 3.2.2⇔Иc.x ∈q[u←↤c] Assumption⇔Иc.x[c↦→u] ∈q Proposition 3.2.2⇔x ∈q (σ#), c#xEnd of proof
Example 3.3.4

The set of atoms 𝔸 is a termlike σ-algebra over itself (so a[a↦→c] = c and a[b↦→c] = a). By Proposition 3.2.6 the full powerset of 𝔸 is an σ-algebra over 𝔸, and by Proposition 3.3.3 this σ-algebra is exact.

So suppose p, q ⊆𝔸 and Иc.p[a←↤c] = q[a←↤c]. This means that for all but finitely many atoms c it is the case that for every x∈𝔸, x[c↦→a] ∈p if and only if x[c↦→a] ∈q. In particular for every x there exists some c ≠ x such that x ∈p if and only if x ∈q. Thus, p and q 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

Definition 3.4.1

Suppose 𝒫 = (|𝒫|, ·, 𝒰, amgis𝒫) is an σ-algebra over a termlike σ-algebra 𝒰. Give subsets X ⊆|𝒫| pointwise actions as follows:

π·X = {π·x | x ∈X} X[a↦→u] = {p∈|𝒫| |Иc.p[u←↤c] ∈(c a)·X} u∈|𝒰|
Proposition 3.4.2

Suppose 𝒫 is an σ-algebra over a termlike σ-algebra 𝒰 and suppose X ⊆|𝒫|.8 Suppose p∈|𝒫| and u∈|𝒰| and a#u. Then:

(1) p ∈X[a↦→u] if and only if Иc.p[u←↤c] ∈ (c a)·X.9

(2) p ∈π·X if and only if π-1·p ∈X.

Proof

(1) Direct from Definition 3.4.1.

(2) Direct from Theorem 2.3.2.End of proof

Remark 3.4.3

Definitions 3.2.1 and 3.4.1 are not perfectly symmetric; Definition 3.4.1 contains a И-quantifier. It is there specifically to make Lemma 3.4.4 true; in other words we guarantee axiom (σα) from Figure 1 by construction:10

Lemma 3.4.4 (α-equivalence).

Suppose 𝒫 is an σ-algebra over a termlike σ-algebra 𝒰 and suppose X ⊆|𝒫|. Then if b#X then X[a↦→u] = ((b a)·X)[b↦→u].

Proof

By part 1 of Proposition 3.4.2 p ∈X[a↦→u] if and only Иc.p[u←↤c] ∈ (c a)·X, and p ∈ ((b a)·X)[b↦→u] if and only if Иc.p[u←↤c] ∈ (c b)·((b a)·X). By Corollary 2.1.12 (c a)·X = (c b)·((b a)·X) since b#X. The result follows.End of proof

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 X, and the proof is different:

Lemma 3.4.5

Suppose 𝒫 is an σ-algebra over a termlike σ-algebra 𝒰 and suppose X ⊆|𝒫|. Suppose u, v∈|𝒰|. Then

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

We reason as follows, where we write π = (a′ a) ◦ (b′ b):

p ∈X[a↦→u][b↦→v] ⇔Иa′, b′.p[v←↤b′][(b′ b)·u←↤a′] ∈π·X Proposition 3.4.2⇔Иa′, b′.p[((b′ b)·u)[b′↦→v]←↤a′][v←↤b′] ∈π·X (σσ) a′#v⇔Иa′, b′.p[u[b↦→v]←↤a′][v←↤b′] ∈π·X (σα) b′#u⇔Иa′.p[u[b↦→v]←↤a′] ∈((a′ a)·X)[b↦→v] Proposition 3.4.2⇔Иa′.p[u[b↦→v]←↤a′] ∈((a′ a)·X)[b↦→(a′ a)·v] Corollary 2.1.12 a′, a#v⇔Иa′.p[u[b↦→v]←↤a′] ∈(a′ a)·(X[b↦→v]) Theorem 2.3.2⇔p ∈X[b↦→v][a↦→u[b↦→v]] Proposition 3.4.2End of proof

3.4.2. The σ-powerset Powσ(𝒫).

Recall from Subsection 2.4.1 the finitely supported powerset NomPow(𝒳) of a nominal set 𝒳.

Definition 3.4.6

Suppose 𝒫 is an σ-algebra over a termlike σ-algebra 𝒰. Define the σ-powerset algebra Powσ(𝒫) by setting

— |Powσ(𝒫)| to be those X∈|NomPow(𝒫)| (finitely supported subsets of |𝒫|; see Subsection 2.4.1) with

— the actions π·X and X[a↦→u] from Definition 3.4.1,

satisfying conditions 1 and 2 below, where u∈|𝒰| and p∈|𝒫|:

(1) ∀u.Иa.∀p.(p[u←↤a] ∈X ⇔p ∈X).(2) ∀a.Иb.∀p.(p[b←↤a] ∈X ⇔(b a)·p ∈X).

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:

Lemma 3.4.7

Continuing the notation of Definition 3.4.6, if X∈|Powσ(𝒫)| then

(1) If a#X then X[a↦→u] = X.

(2) If b#X then X[a↦→b] = (b a)·X.

Proof

(1) Suppose a#X. By part 1 of Lemma 3.4.2 p ∈X[a↦→u] if and only if Иc.p[u←↤c] ∈ (c a)·X. By Corollary 2.1.12 (c a)·X = X and by condition 1 of Definition 3.4.6 p[u←↤c] ∈X if and only if p ∈X, so this is if and only if Иc.(p ∈X), that is p ∈X.

(2) We combine Proposition 3.4.2 with condition 2 of Definition 3.4.6, since a#b.End of proof

Corollary 3.4.8

Suppose X∈|Powσ(𝒫)|. Then X[a↦→a] = X.

Proof

Suppose b#X. By Lemma 3.4.4 X[a↦→a] = ((b a)·X)[b↦→a]. Note that by Proposition 2.3.4 a#(b a)·X. By part 2 of Lemma 3.4.7 ((b a)·X)[b↦→a] = (b a)·((b a)·X) = X.End of proof

Lemma 3.4.9

If X∈|Powσ(𝒫)| and u∈|𝒰| then also X[a↦→u]∈|Powσ(𝒫)|.

As a corollary, in Definition 3.4.6, |Powσ(𝒫)| is closed under the σ-action from Definition 3.4.1.

Proof

By construction X[a↦→u] ⊆|𝒫|, so we now check the properties listed in Definition 3.4.6.

By assumption in Definition 3.4.6, X is finitely supported. Finite support of X[a↦→u] is from Theorem 2.3.2.

We check the conditions of Definition 3.4.6 for X[a↦→u]:

(1) For fresh b (so b#u, X), X[a↦→u][b↦→v] = X[a↦→u]. We use Lemma 3.4.4 to assume without loss of generality that a#u. It suffices to reason as follows:

X[a↦→u][b↦→v] = X[b↦→v][a↦→u[b↦→v]] Lemma 3.4.5, a#v= X[b↦→v][a↦→u] (σ#), b#u= X[a↦→u] Part 1 of Lemma 3.4.7, b#X

(2) For fresh b′ (so b′#u, v, X) X[a↦→u][b↦→b′] = (b′ b)·(X[a↦→u]). It suffices to reason as follows:

X[a↦→u][b↦→b′] = X[b↦→b′][a↦→u[b↦→b′]] Lemma 3.4.5, a#b′= ((b′ b)·X)[a↦→(b′ b)·u] Lemma 3.4.7, b′#u, X= (b′ b)·(X[a↦→u]) Part 2 of Theorem 2.3.2End of proof
Proposition 3.4.10

If 𝒫 is an σ-algebra over a termlike σ-algebra 𝒰 then Powσ(𝒫) (Definition 3.4.6) is a σ-algebra over 𝒰.

Proof

By Lemma 3.4.9 the σ-action does indeed map to |Powσ(𝒫)|. By Theorem 2.3.2 so does the permutation action. It remains to check validity of the axioms from Definition 3.1.5.

— Axiom (σid) is Corollary 3.4.8.

— Axiom (σ#) is part 1 of Lemma 3.4.7.

— Axiom (σα) is Lemma 3.4.4.

— Axiom (σσ) is Lemma 3.4.5.End of proof

Example 3.4.11

Consider some set of terms considered as a termlike σ-algebra over themselves (Example 3.1.3; so s[a↦→t] is s with t substituted for a). Write this 𝒯ℛℳ.

By Propositions 3.4.10 and 3.2.6 Powσ(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σ(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σ(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 x[a↦→u] 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 p[u←↤a], as we shall observe).

Suppose 𝒳 is a σ-algebra over a termlike σ-algebra 𝒰.

Definition 3.5.1

Suppose u1, . . . , un∈|𝒰| and suppose a1, . . . , an are n distinct atoms not in ⋃i supp(ui). Then for x∈|𝒳| define

x[a1↦→u1, . . . , an↦→un] = x[a1↦→u1] . . . [an↦→un].

We need to show that Definition 3.5.1 does not depend on the order in which we take the ui. This follows using (σσ) and (σσ), and (σ#), because we assumed that each ai is not in ⋃i supp(ui).

Now we extend this to the case where the ai are not necessarily fresh for the ui:

Definition 3.5.2

Suppose u1, . . . , un∈|𝒰| and suppose a1, . . . , an are any n distinct atoms. Then for x∈|𝒳| define

x[a1↦→u1, . . . , an↦→un] = (((a′ 1 a1) ◦· · · ◦(a′ n an))·x)[a′ 1↦→u1] . . . [a′ n↦→un].

where we choose a′ 1, . . . , a′ n fresh (so not in {a1, . . . , an} ∪ supp(x) ∪⋃i supp(ui)).

Lemma 3.5.3

The choice of fresh a′ i and the order of the ui in Definition 3.5.2, do not matter.

Proof

By routine calculations using (σα), (σσ), and (σ#).End of proof

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:

Lemma 3.5.4

Suppose u, v∈|𝒰| and p∈|𝒫|. Then

a#v, b#u ⇒p[u←↤a][v←↤b] = p[v←↤b][u←↤a].
Proof

We reason as follows:

p[v←↤b][u←↤a] = p[u[b↦→v]←↤a][v←↤b] (σσ), a#v= p[u←↤a][v←↤b] (σ#), b#uEnd of proof

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 b#p ⇒p[u←↤a] = (b a)·(p[u←↤b]). Lemma 3.5.5 is the closest we can get to such a result. We mention it without proof:

Lemma 3.5.5

Suppose 𝒫 is a finitely-supported σ-algebra (so every p∈|𝒫| has finite support) and 𝒳 is a σ-algebra over a termlike σ-algebra 𝒰 and suppose u∈|𝒰|. Then:

(1) If X∈|Powσ(𝒫)| and b#X, p, u and p∈|𝒫| and a#p, u then p[u←↤a] ∈X if and only if (b a)·(p[u←↤b]) ∈X.

(2) If x∈|𝒳| and b#x and p∈|Powσ(𝒳)| then x ∈p[u←↤a] if and only if x ∈ (b a)·(p[u←↤b]).

4. NOMINAL POSETS

4.1. Nominal posets and fresh-finite limits

Definition 4.1.1

A nominal poset is a tuple L = (|L|, ·, ≤) where

— (|L|, ·) is a nominal set, and

— The relation ≤⊆|L|×|L| is an equivariant partial order.12

Call L finitely fresh-complete or say it has fresh-finite limits when for every finite subset X ⊆|L| and every finite set of atoms A ⊆𝔸 the set of A-fresh lower bounds

{x′∈|L| | A ∩supp(x′) = ∅∧∀x∈X.x′≤x}

has a ≤-greatest element ⋀#AX, which we may call the A#limit (A-fresh limit) or A#greatest lower bound of X.

Similarly call L finitely fresh-cocomplete or say it has fresh-finite colimits when for every finite X and A as above the set of A-fresh upper bounds

{x′∈|L| | A ∩supp(x′) = ∅∧∀x∈X.x≤x′}

has a ≤-least element ⋁#A X, which we may call its A#colimit or A#least upper bound of X.

Example 4.1.2

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 [∀a.φ] is an a#limit for {[φ]}. We sketch this particular example in a little more detail in Section 9.

Notation 4.1.3

Suppose L = (|L|, ·, ≤) is nominal poset. Suppose X ⊆|L| and A ⊆𝔸 are finite and suppose x∈|L|.

— Call ⋀#∅X a limit or greatest lower bound of X.

— Call ⋀#{a}{x} the a#limit or a#greatest lower bound of x and write it ⋀#ax. Unpacking Definition 4.1.1,

⋀#ax is the greatest element of {x′∈|L| | x′≤x ∧a#x′}.

— Call ⋁#∅X a colimit or least upper bound of X.

— Call ⋁#{a}{x} the a#colimit or a#least upper bound of x and write it ⋁#ax.

— Write ⊤ for the greatest lower bound and ⊥ for the least upper bound of the empty set ∅.

— Write x ∧y for the greatest lower bound and x ∨y for the least upper bound of {x, y}.

Remark 4.1.4

So A#(co)limits generalise (co)limits; if we take A = ∅ 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:

Proposition 4.1.5

Suppose L is a nominal poset. Then L is finitely fresh-complete if and only if it has limits of the following three forms:

— ⊤, a greatest element (limit for the empty set ∅).

— x ∧y, a limit for {x, y}.

— ⋀#ax, an a#limit for {x}.

Similarly finitely fresh-cocomplete is equivalent to having ⊥, x ∨y, and ⋁#ax.

Proof

The interesting part is the right-to-left implication where X is non-empty. Given finite non-empty {x1, . . . , xn} ⊆|L| and {a1, . . . , an} ⊆𝔸, it is not hard to verify that ⋀#a1 . . . ⋀#an(. . . (x1 ∧ x2) . . . ∧xn) is an A#limit for X.End of proof

Definition 4.1.6

Suppose L is a partial order (it need not be nominal, though we will care most about the case that it is). Call x′∈|L| a complement of x∈|L| when x ∧x′ = ⊥ and x ∨x′ = ⊤.

If every x∈|L| has a complement say that L is complemented, and write the complement of x as ¬x.

Lemma 4.1.7

Fresh-finite (co)limits, and complements, are unique if they exist, and ¬¬x = x.

Proof

Using the fact that for a partial order, x ≤y and y ≤x imply x = y.End of proof

Corollary 4.1.8

Suppose L = (|L|, ·, ≤) is a nominal poset.

(1) Suppose X⊆|L| is finite and A⊆𝔸, and ⋀#AX exists. Then supp(⋀#AX)⊆⋃{supp(x) | x∈X}\A.

(2) Suppose x∈|L|, and suppose ¬x exists. Then supp(¬x) = supp(x).

Proof

(1) By part 3 of Theorem 2.3.2 supp(⋀#AX) ⊆⋃{supp(x) | x ∈X} ∪A. Since by assumption A ∩ supp(⋀#AX) = ∅, the result follows.

(2) By part 3 of Theorem 2.3.2 observing that the map x↦ →¬x is its own inverse.End of proof

Lemma 4.1.9 is α-equivalence for fresh-finite limits:

Lemma 4.1.9

Suppose L is a nominal poset and x∈|L|.

If b#x then ⋀#ax = ⋀#b(b a)·x and ⋁#ax = ⋁#b(b a)·x, where ⋀#ax and ⋁#ax exist.

Proof

By Corollary 4.1.8 a, b#⋀#ax, so by part 1 of Corollary 2.1.12 ⋀#ax = (b a)·⋀#ax. By part 2 of Theorem 2.3.2 (b a)·⋀#ax = ⋀#b(b a)·x. The case of ⋁#ax is similar.End of proof

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

Definition 4.2.1

Suppose a finitely fresh-complete and finitely fresh-cocomplete nominal poset L = (|L|, ·, ≤) is also a σ-algebra (|L|, ·, 𝒰, sub𝒰) over a termlike σ-algebra 𝒰. Call the σ-algebra structure monotone when for every x, y∈|L| and u∈|𝒰|

x ≤y implies x[a↦→u] ≤y[a↦→u]

and compatible when for every finite X ⊆|ℒ| and A ⊆𝔸 and u∈|𝒰|

(⋀#AX)[a↦→u] = ⋀#A{x[a↦→u] | x ∈X} provided A ∩(supp(u) ∪{a}) = ∅ (⋁#AX)[a↦→u] = ⋁#A{x[a↦→u] | x ∈X} provided A ∩(supp(u) ∪{a}) = ∅ (¬x)[a↦→u] = ¬(x[a↦→u]).
Remark 4.2.2

As standard, negation converts greatest lower bounds to least upper bounds. Thus we obtain ⋁#AX as ¬⋀#A{¬x | x ∈X}. So the second condition above follows from the first and third.

Lemma 4.2.3

Given a finitely fresh-complete nominal poset with a compatible σ-action:

(1) (x ∧y)[a↦→u] = x[a↦→u] ∧ (y[a↦→u]) and similarly for ∨.

(2) If x ≤y then x[a↦→u] ≤y[a↦→u] (so a compatible σ-action is monotone).

(3) If b#a, u then (⋀#bx)[a↦→u] = ⋀#b(x[a↦→u]) and similarly for ⋁#b.

(4) ⊤[a↦→u] = ⊤ and ⊥[a↦→u] = ⊥.

Proof

Parts 1, 3, and 4 are special cases of compatibility.13 Part 2 follows from part 1 using the fact that x ≤y if and only if x ∧y = x.End of proof

Lemma 4.2.4

In a finitely fresh-complete nominal poset:

— If z ≤x and a#z then z ≤⋀#ax.

— If the σ-action is monotone then if z ≤x and a#z then z ≤x[a↦→u] for every u, so that z is a lower bound for the (in general infinite) set {x[a↦→u] | u∈|𝒰|}.14

Proof

The first part is direct from the definition of fresh-finite limit; ⋀#ax is by definition a least upper bound for all z ≤x such that a#z.

For the second part, since the σ-action is monotone z[a↦→u] ≤x[a↦→u] for every u∈|𝒰|. By (σ#) also z = z[a↦→u]. It follows that z ≤x[a↦→u] for every u∈|𝒰|.End of proof

Remark 4.2.5

Clearly, we intend the a#limit ⋀#ax to model the universal quantifier ∀a.φ, just as the finite limit x ∧y models logical conjunction φ ∧ψ.

An odd thing about the quantifier rules is that (∀L) expresses ∀a.φ as a greatest lower bound of an infinite set {φ[a↦→r] | all r} whereas (∀R) expresses ∀a.φ 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 {x[a↦→u] | u∈|𝒰|}—nice for an elimination rule, so we can eliminate for many u—and

— the (fresh-)finite limit of the singleton set {x}—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 ⋀u x[a↦→u] and the (fresh-)finite greatest lower bound ⋀#ax, provided one of these exists and the σ-action is monotone. That is, the limit of a diagram over infinitely many elements x[a↦→u] is equivalent to the a#limit of just x.

Proposition 4.2.6

Suppose L is a nominal poset with a monotone σ-action15 and x∈|L|. Then:

(1) If ⋀#ax exists then so does ⋀u∈|𝒰| x[a↦→u] the limit for {x[a↦→u] | u∈|𝒰|}, and they are equal. In symbols:

⋀#ax =⋀u∈|𝒰|x[a↦→u].

(2) If ⋀u x[a↦→u] exists then so does ⋀#ax, and they are equal.

Proof

Suppose ⋀#ax exists.

— By Lemma 4.2.4 ⋀#ax is a lower bound for {x[a↦→u] | u∈|𝒰|}.

— Now suppose z is any lower bound for {x[a↦→u] | u∈|𝒰|}. So z ≤x[a↦→u] for every u∈|𝒰|. Note that we do not know a priori that a#z. Choose b fresh (so b#z, x) and take u = b. Then z ≤x[a↦→b] L3.1.10= (b a)·x. We assumed that x has an a#limit so by Theorem 2.3.2 also (b a)·x has a b#limit (which by Lemma 4.1.9 is equal to the a#limit of x). Since b#z it follows that z ≤⋀#b(b a)·xL4.1.9=⋀#ax.

It follows that ⋀#ax = ⋀u x[a↦→u].

Now suppose ⋀u x[a↦→u] exists. By Lemma 3.1.11 and part 2 of Theorem 2.3.2 we have that a# ⋀u x[a↦→u].

— By assumption ⋀u x[a↦→u] ≤x[a↦→a] (σid) = x. Thus ⋀u x[a↦→u] is an a#lower bound for x.

— Now suppose z ≤x and a#z; we need to show that z ≤⋀u x[a↦→u]. This is direct from Lemma 4.2.4.

It follows that ⋀u x[a↦→u] = ⋀#ax.End of proof

Remark 4.2.7

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 {x[a↦→u] | u∈|𝒰|}’.

We briefly mention another characterisation of ⋀#ax using a ‘smaller’ conjunction, though we never use it:

Proposition 4.2.8

Suppose L is a nominal poset with a monotone σ-action and x∈|L|. Then:

(1) If ⋀#ax exists then so does ⋀n x[a↦→n] where n ranges over all atoms, and they are equal.

(2) If ⋀n x[a↦→n] exists then so does ⋀#ax, and they are equal.16

Proof

As the proof of Proposition 4.2.6. The important point is that by Lemma 3.1.11 and part 2 of Theorem 2.3.2 we have a# ⋀n x[a↦→n].End of proof

4.3. Equality

Suppose L is a finitely fresh-complete nominal poset17 with a compatible σ-algebra structure over a termlike σ-algebra 𝒰.

Definition 4.3.1

An equality is an element (a=Lb)∈|L| with supp(a=Lb) ⊆{a, b} and such that:

(1) For every u∈|𝒰|,

(a=Lb)[a↦→u, b↦→u] = ⊤.

(2) For every u, v∈|𝒰| and z∈|L|,

(a=Lb)[a↦→u, b↦→v] ∧z[a↦→u] = (a=Lb)[a↦→u, b↦→v] ∧z[a↦→v].

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.

Remark 4.3.2

The choice of a and b is arbitrary (simultaneous σ-action [a↦→u, b↦→v] is from Definition 3.5.1).

Anticipating the notation of Definition 5.2.5, if we write (a=Lb)[a↦→u, b↦→v] as (u=Lv) then properties 1 and 2 of Definition 4.3.1 can be rewritten in the following more economical form

(u=Lu) = ⊤ (u=Lv) ∧z[a↦→u] = (u=Lv) ∧z[a↦→v]

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:

Proposition 4.3.3

An equality in L is unique, up to choice of a and b, if it exists.

Proof

Consider two equalities a=L1b and a=L2b. Take z = (a=L2b) and u = a and v = b in condition 2 of Definition 4.3.1. Then using (σid),

(a=L1b) ∧(a=L2b) = (a=L1b) ∧(a=L2b)[b↦→a].

Now by condition 1 for (a=L2b) we know that (a=L2b)[b↦→a] = ⊤. It follows that (a=L1b) ≤ (a=L2b). By symmetry also (a=L2b) ≤ (a=L1b) and we are done.End of proof

It is not hard to similarly prove that equality is reflexive, symmetric, and transitive, if it exists.

4.4. Definition of a FOLeq algebra

Definition 4.4.1

Suppose L is a finitely fresh-complete and finitely fresh-cocomplete nominal poset (Definition 4.1.1).

Call L distributive when:

(1) x ∨(y ∧z) = (x ∨y) ∧(x ∨z).

(2) If a#x then x ∨ (⋀#ay) = ⋀#a(x ∨y).

These two conditions can be unified into a single condition as follows, for finite A ⊆𝔸 and X ⊆|L|:

A∩supp(x)=∅⇒x ∨⋀#AX = ⋀#A{x∨x′ | x′∈X}
Remark 4.4.2

Evidently, Definition 4.4.1 generalises the usual notion of distributivity. A dual version of part 1 of Definition 4.4.1 is x ∧ (y ∨z) = (x ∧y) ∨ (x ∧z) 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 a#x then x ∧ (⋁#ay) = ⋁#a(x ∧y). 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.

Definition 4.4.3

A FOLeq algebra over a termlike σ-algebra 𝒰 is a nominal poset L with the following properties:

— L is finitely fresh-complete and finitely fresh-cocomplete.

— L is distributive.

— L is complemented.

— L has a compatible σ-algebra structure over 𝒰.

— L has an equality.

If L is as above except that it does not have an equality, then we call L a FOL algebra.

Remark 4.4.4

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 ∧, ∨, ⋀#a and ⋁#a, 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 ‘a#x’ and substitution like ‘x[a↦→u]’ and these are properties that, usually, only are applicable to syntax. But now, the things we are operating on x, a, and u 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.

Remark 4.4.5

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.

(Hyp)Φ, φ ⊢φ, Ψ(⊥L)Φ,⊥⊢ΨΦ, r=r ⊢Ψ(=R)Φ ⊢ΨΦ, φ1, φ2 ⊢Ψ(∧L)Φ, φ1∧φ2 ⊢ΨΦ ⊢ψ1, Ψ Φ ⊢ψ2, Ψ(∧R)Φ ⊢ψ1∧ψ2, ΨΦ, r′=r, φ[a↦→r′] ⊢Φ(=L)Φ, r′=r, φ[a↦→r] ⊢ΦΦ ⊢ψ, Ψ(¬L)Φ,¬ψ ⊢ΨΦ, φ ⊢Ψ(¬R)Φ ⊢¬φ, ΨΦ, φ[a↦→r] ⊢Ψ(∀L)Φ,∀a.φ ⊢ΨΦ ⊢ψ, Ψ (a ∉fa(Φ ∪Ψ))(∀R)Φ ⊢∀a.ψ, Ψ
Fig. 2: Derivation rules of first-order logic with equality (FOLeq)

5. INTERPRETATION OF FIRST-ORDER LOGIC IN A FOLEQ ALGEBRA

5.1. Syntax and derivability of first-order logic

Definition 5.1.1

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:

r ::= a | f(r1, . . . , rar(f)) φ ::= ⊥| r=r | P(r1, . . . , rar(P)) | φ∧φ | ¬φ | ∀a.φ

Above, a 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(r), fa(φ) and capture-avoiding substitution r[a↦→s] and φ[a↦→s] also as standard.18

Notation 5.1.2

Since our logic is classical, we use the following standard abbreviations:

— Write φ∨ψ for ¬((¬φ)∧(¬ψ)).

— Write φ⇒ψ for (¬φ)∨ψ.

— Write φ⇔ψ for (φ⇒ψ)∧(ψ⇒φ).

Notation 5.1.3

Φ 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:

Definition 5.1.4

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):

Definition 5.2.1

Define ⊗n𝔸 to be the set of n-tuples of distinct atoms with the pointwise action π·(a1, . . . , an) = (π(a1), . . . , π(an)).

⟦a⟧ = atm𝒰(a) ⟦⊥⟧ = ⊥⟦f(r1, . . . , rn)⟧ = fℐ(⟦r1⟧, . . . , ⟦rn⟧) ⟦r=s⟧ = ⟦r⟧=ℐ⟦s⟧ ⟦P(r1, . . . , rn)⟧ = Pℐ(⟦r1⟧, . . . , ⟦rn⟧) ⟦φ∧ψ⟧ = ⟦φ⟧ ∧⟦ψ⟧ ⟦¬φ⟧ = ¬⟦φ⟧ ⟦∀a.φ⟧ = ⋀#a⟦φ⟧
Fig. 3: The interpretation of terms and predicates
Definition 5.2.2

Suppose L is a FOLeq algebra over 𝒰 (from Definition 4.4.3; so L is a finitely fresh-complete complemented nominal poset, with a compatible σ-algebra structure over 𝒰, and with equality (a=Lb)). We may write L also for (|L|, ·) the underlying nominal set of the FOLeq algebra.

An interpretation ℐ of a signature (Σ, Π, ar) over L is an assignment

— to each f ∈ Σ with arity n, an equivariant function fℐ : ⊗n𝔸⇒𝒰,

— to each P ∈ Π with arity n, an equivariant function Pℐ : ⊗n𝔸⇒L.

(It is not hard to check from Subsection 4.3 that the equality a=Lb of L also gives us an equivariant function ⊗2𝔸⇒L, so equality could have been presented as one of the P in the signature, but we took it to be primitive to L instead. The treatments of equality and the P flow together in Definition 5.2.5.)

Remark 5.2.3

By Definition 2.1.6, fℐ equivariant means fℐ(π(a1), . . . , π(an)) = π·fℐ(a1, . . . , an). 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 n 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:

Notation 5.2.4

If 𝒰 is a nominal set write 𝒰n for n times 𝒰 × · · · × 𝒰.

Definition 5.2.5

Extend fℐ and Pℐ and =L to functions fℐ : 𝒰n⇒𝒰 and Pℐ : 𝒰n⇒L and =ℐ: 𝒰2⇒L as follows

fℐ(u1, . . . , un) = fℐ(a1, . . . , an)[a1↦→u1, . . . , an↦→un] Pℐ(u1, . . . , un) = Pℐ(a1, . . . , an)[a1↦→u1, . . . , an↦→un] =ℐ(u1, u2) = (a=Lb)[a↦→u1, b↦→u2]

where we choose a1, . . . , an to be n distinct atoms fresh for ⋃n 1 supp(ui). We may write =ℐ(u1, u2) infix as u1=ℐu2.

Lemma 5.2.6

Definition 5.2.5 is independent of the choice of fresh atoms a1, . . . , an and a, b.

Proof

A proof by direct calculations is not hard, or we can see this directly from [Gab07, Theorem 27] since by Lemma 3.1.8 fℐ and Pℐ are purely abstractive (terminology of Theorem 27).End of proof

Definition 5.2.7

Extend the interpretation ℐ of Definition 5.2.5 to terms and predicates as shown in Figure 3.

Much as for fℐ and Pℐ above, we technically need to check that Definition 5.2.7 does not depend on the choice of bound atom a in ∀a.φ. This follows by easy calculations using the fact that by assumption, a ∉ supp(⋀#a⟦φ⟧).

Lemma 5.2.8

supp(⟦r⟧) ⊆ fa(r) and supp(⟦φ⟧) ⊆ fa(φ).

Proof

From Theorem 2.3.2 using the fact that the support of the abstract syntax of r is equal to fa(r) and the support of the (nominal, since we have a binder ∀) abstract syntax of φ is equal to fa(φ) (see [Gab11, Section 5] for a detailed treatment of the nominal abstract syntax of the untyped λ-calculus).End of proof

Lemma 5.2.9

⟦⊤⟧ = ⊤∈|L|.

Proof

Unpacking Definition 5.2.7 and recalling that ⊤ is sugar for ¬⊥.End of proof

Lemma 5.2.10

(1) fℐ(u1, . . . , un)[a↦→u] = fℐ(u1[a↦→u], . . . , un[a↦→u]).

(2) (u1=ℐu2)[a↦→u] = (u1[a↦→u]=ℐu2[a↦→u]).

(3) Pℐ(u1, . . . , un)[a↦→u] = Pℐ(u1[a↦→u], . . . , un[a↦→u]).

Proof

By definition fℐ(u1, . . . , un)[a↦→u] is equal to fℐ(a1, . . . , an)[a1↦→u1] . . . [an↦→un][a↦→u] where we are free to choose a1, . . . , an fresh. We use Lemma 3.4.5 to rewrite this as

fℐ(a1, . . . , an)[a↦→u][a1↦→u1[a↦→u]] . . . [an↦→un[a↦→u]].

By Theorem 2.3.2 a#fℐ(a1, . . . , an) so by (σ#) we can garbage–collect the innermost [a↦→u]. The result follows.

The cases of =ℐ and Pℐ are similar.End of proof

Lemma 5.2.11

— ⟦t[a↦→r]⟧ = ⟦t⟧[a↦→⟦r⟧].

— ⟦φ[a↦→r]⟧ = ⟦φ⟧[a↦→⟦r⟧].

Proof

By a routine induction on t and φ.

— The case of a. a[a↦→r] = r and by (σa) atm𝒰(a)[a↦→⟦r⟧] = ⟦r⟧.

— The cases of f(r1, . . . , rn), P(r1, . . . , rn), and r1=r2. This is Lemma 5.2.10.

— The case of ⊥. By Theorem 2.3.2 supp(⊥) = ∅. By (σ#) ⊥[a↦→x] = ⊥.

— The cases of φ∧ψ and ∀a.φ. 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).End of proof

Definition 5.2.12

Extend the interpretation ℐ of Definition 5.2.7 to sequents by defining

⟦Φ ⊢Ψ⟧ is the assertion⋀{⟦φ⟧ | φ∈Φ} ≤⋁{⟦ψ⟧ | ψ ∈Ψ}.
Theorem 5.2.13 (Soundness).

If Φ ⊢ Ψ is derivable then ⟦Φ ⊢ Ψ⟧ is true.

Proof

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

— (∀R) and (∀L) are from Lemma 4.2.4 and Lemma 5.2.8.End of proof

6. THE σ-POWERSET AS A FOLEQ ALGEBRA

Suppose 𝒫 is an σ-algebra over a termlike σ-algebra 𝒰. We know by Proposition 3.4.10 that Powσ(𝒫) from Definition 3.4.6 is a σ-algebra. It is also very easy to see that Powσ(𝒫) with the pointwise action π·X = {π·p | p ∈X} (Definition 3.4.1), ordered by subset inclusion X ⊆Y , is a nominal poset (Definition 4.1.1).

We want now to show that Powσ(𝒫) is a FOLeq algebra (Theorem 6.4.1). That is, we want to show that Powσ(𝒫)

— is finitely fresh-complete (has ⋀#AX),

— is complemented (|𝒫| \ X),

— 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 ⋀#AX we use Proposition 4.1.5 to split the problem into parts. We consider this next.

6.1. Intersection, complement, top element

Suppose 𝒫 = (|𝒫|, ·, 𝒰, amgis𝒫) is an σ-algebra over a termlike σ-algebra 𝒰. Recall the definitions of NomPow(𝒫) from Subsection 2.4.1 (finitely-supported powerset) and of Powσ(𝒫) 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.

Lemma 6.1.1

Suppose 𝒫 is an σ-algebra over a termlike σ-algebra 𝒰. Suppose u∈|𝒰| and Y, Y ′∈|NomPow(𝒫)| and suppose X ⊆|NomPow(𝒫)| is strictly finitely supported (Definition 2.4.3). Then:

(1) (|𝒫|\Y )[a↦→u] = |𝒫| \ (Y [a↦→u]).

In words: σ commutes with sets complement.

(2) (⋂X∈X X)[a↦→u] = ⋂X∈X (X[a↦→u]) and (⋃X∈X X)[a↦→u] = ⋃X∈X (X[a↦→u]). In words: σ commutes with strictly finitely supported sets intersections and unions. In particular, σ commutes with finite intersection and union.

(3) If Y ⊆Y ′ then Y[a↦→u] ⊆Y ′[a↦→u]. In words: σ is monotone.

Proof

We reason as follows:

p ∈(|𝒫|\X)[a↦→u] ⇔Иc.p[u←↤c] ∈(c a)·(|𝒫|\X) Proposition 3.4.2⇔Иc.p[u←↤c] ∈|𝒫|\(c a)·X Theorem 2.3.2⇔Иc.p[u←↤c] ∉(c a)·X Fact⇔p ∉X[a↦→u] Proposition 3.4.2⇔p ∈|𝒫|\(X[a↦→u]) Factp ∈(⋂X∈X X)[a↦→u] ⇔Иc.p[u←↤c] ∈⋂X∈X (c a)·X Prop 3.4.2, Thm 2.3.2⇔Иc.∀X∈X.p[u←↤c] ∈(c a)·X Factp ∈⋂X∈X (X[a↦→u]) ⇔∀X∈X.p ∈X[a↦→u] Fact⇔∀X∈X.Иc.p[u←↤c] ∈(c a)·X Proposition 3.4.2

We note that by Lemma 2.4.4, c#X if and only if c#X for every X ∈X. This allows us to swap the ∀ and the И quantifier, and the result follows.

Part 3 follows using part 2 and the fact that Y[a↦→u] ⊆Y ′[a↦→u] if and only if Y[a↦→u] ∩ Y ′[a↦→u] = Y[a↦→u].End of proof

Lemma 6.1.2

— If X, Y ∈|NomPow(𝒫)| then X ∩Y ∈|NomPow(𝒫)| and

if X, Y ∈|Powσ(𝒫)| then X ∩Y ∈|Powσ(𝒫)|.

— If X∈|NomPow(𝒫)| then |𝒫|\X∈|NomPow(𝒫)|, and if X∈|Powσ(𝒫)| then |𝒫|\X∈|Powσ(𝒫)|.

— |𝒫|∈|NomPow(𝒫)| and |𝒫|∈|Powσ(𝒫)|.

Proof

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 Powσ(-). We do this just for X ∩Y :

(1) If a is fresh (so a#X, Y, u) then (X ∩Y)[a↦→u] = X ∩Y . We reason as follows:

(X ∩Y )[a↦→u] = (X[a↦→b]) ∩(Y [a↦→u]) Lemma 6.1.1= X ∩Y Cond 1 of Def 3.4.6

(2) If b is fresh (so b#X, Y) then (X ∩Y)[a↦→b] = (b a)·(X ∩Y). We reason as follows:

(X ∩Y )[a↦→b] = (X[a↦→b]) ∩(Y [a↦→b]) Lemma 6.1.1= ((b a)·X) ∩((b a)·Y ) Cond 2 of Def 3.4.6= (b a)·(X ∩Y ) Theorem 2.3.2End of proof
Proposition 6.1.3

∅ is the bottom element and |𝒫| is the top element in NomPow(𝒫) and Powσ(𝒫) ordered by subset inclusion. X ∩Y is the greatest lower bound for {X, Y }. |𝒫|\X is the complement of X. Thus NomPow(𝒫) and Powσ(𝒫) ordered by subset inclusion form Boolean algebras, and by construction Powσ(𝒫) is a subalgebra of NomPow(𝒫).

Proof

By standard sets calculations.End of proof

6.2. Quantification

In this subsection we explore what concrete sets operation corresponds to the fresh-finite limits ⋀#a of Notation 4.1.3; in other words we explore quantification.

Suppose 𝒫 = (|𝒫|, ·, 𝒰, amgis𝒫) is an σ-algebra over a termlike σ-algebra 𝒰. Recall the definitions of NomPow(𝒫) from Subsection 2.4.1 (finitely-supported powerset) and of Powσ(𝒫) from Definition 3.4.6 (the σ-powerset).

Definition 6.2.1

If X ∈|NomPow(𝒫)| then define

⋂#aX =⋂{X[a↦→u] | u∈|𝒰|}.

We work towards proving ⋂#aX ∈|NomPow(𝒫)|; this is Theorem 6.2.5. We need the key technical Lemma 6.2.2 for Proposition 6.2.3:

Lemma 6.2.2

Suppose p ∈|𝒫| and X∈NomPow(𝒫) and v∈|𝒰| and suppose a#v. Then

Иb′.∀u∈|𝒰|.Иa′.p[v←↤b′][u←↤a′] ∈(b′ b)·(a′ a)·X if and only if∀u∈|𝒰|.Иb′.Иa′.p[u←↤a′][v←↤b′] ∈(b′ b)·(a′ a)·X.
Proof

We prove two implications:

— The up-down implication. Assume Иb′.∀u∈|𝒰|.Иa′.p[v←↤b′][u←↤a′] ∈ (b′ b)·(a′ a)·X. Choose u∈|𝒰|. Choose fresh b′ and a′ (so b′, a′#X, v, u). Then by assumption (since b′#X, v and a′#X, v, u) p[v←↤b′][u←↤a′] ∈ (b′ b)·(a′ a)·X so that by (σσ) of Figure 1 (since a′#v) p[u[b′↦→v]←↤a′][v←↤b′] ∈ (b′ b)·(a′ a)·X. Now by (σ#) u[b′↦→v] = u (since b′#u). Therefore p[u←↤a′][v←↤b′] ∈ (b′ b)·(a′ a)·X.

— The down-up implication. Assume ∀u∈|𝒰|.Иb′.Иa′.p[u←↤a′][v←↤b′] ∈ (b′ b)·(a′ a)·X.

Choose fresh b′ (so b′#X, v), choose u∈|𝒰| (for which b need not necessarily be fresh), and choose fresh a′ (so a′#X, v, u). By Lemma 3.1.8 b′#u[b′↦→v] (since b′#v). Therefore p[u[b′↦→v]←↤a′][v←↤b′] ∈ (b′ b)·(a′ a)·X and by (σσ) of Figure 1 (since a′#v) p[v←↤b′][u←↤a′] ∈ (b′ b)·(a′ a)·X.End of proof

We cannot use Lemma 6.1.1(2) to derive Proposition 6.2.3 because {X[a↦→u] | u∈|𝒰|} is not necessarily strictly finitely supported. The result still holds, by a proof using Lemma 6.2.2:

Proposition 6.2.3

Suppose X∈|NomPow(𝒫)| and v∈|𝒰| and a#v. Then

(⋂#aX)[b↦→v] = ⋂#a(X[b↦→v]).
Proof

Consider p∈|𝒫|. We reason as follows:

p ∈(⋂#a X)[b↦→v] ⇔Иb′.p[v←↤b′] ∈⋂#a(b′ b)·X Prop 3.4.2, Thrm 2.3.2⇔Иb′.p[v←↤b′] ∈⋂u∈|𝒰|((b′ b)·X)[a↦→u] Definition 6.2.1⇔Иb′.∀u∈|𝒰|.Иa′.p[v←↤b′][u←↤a′] ∈(b′ b)·(a′ a)·X Proposition 3.4.2⇔∀u∈|𝒰|.Иb′.Иa′.p[u←↤a′][v←↤b′] ∈(b′ b)·(a′ a)·X Lemma 6.2.2⇔∀u∈|𝒰|.Иa′.p[u←↤a′] ∈((a′ a)·X)[b↦→v] Proposition 3.4.2⇔∀u∈|𝒰|.Иa′.p[u←↤a′] ∈(a′ a)·(X[b↦→v]) T2.3.2, C2.1.12, a′, a#v⇔∀u∈|𝒰|.p ∈X[b↦→v][a↦→u] Proposition 3.4.2⇔p ∈⋂#a(X[b↦→v]) Definition 6.2.1End of proof
Lemma 6.2.4

Suppose X ∈|NomPow(𝒫)|. Then

b#X implies⋂#aX = ⋂#b(b a)·X.

As a corollary, a#⋂#aX and supp(⋂#aX) ⊆ supp(X)\{a}.

Proof

The corollary follows by part 3 of Corollary 2.1.12 and by Theorem 2.3.2. For the first part, we reason as follows:

⋂#aX = ⋂{X[a↦→u] | u∈|𝒰|} Definition 6.2.1= ⋂{((b a)·X)[b↦→u] | u∈|𝒰|} Lemma 3.4.4= ⋂#b(b a)·X Definition 6.2.1End of proof

Recall Powσ(𝒫) from Definition 3.4.6:

Theorem 6.2.5

If X∈|Powσ(𝒫)| then ⋂#aX∈|Powσ(𝒫)|.

Proof

Finite support of ⋂#aX is by Theorem 2.3.2. It remains to check conditions 1 and 2 of Definition 3.4.6:

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

(⋂#aX)[b↦→v] = ⋂#a(X[b↦→v]) Proposition 6.2.3= ⋂#aX Cond 1 of Def 3.4.6, b#X

(2) Suppose b′ is fresh (so b′#X). Then we reason as follows:

(⋂#aX)[b↦→b′] = ⋂#a(X[b↦→b′]) Proposition 6.2.3= ⋂#a((b′ b)·X) Cond 2 of Def 3.4.6, b′#X= (b′ b)·(⋂#aX) Theorem 2.3.2End of proof
Corollary 6.2.6

If X∈|Powσ(𝒫)| then ⋂#aX from Definition 6.2.1 is equal to ⋀#aX the fresh-finite limit in the lattice Powσ(𝒫) ordered by subset inclusion.

Proof

By Theorem 6.2.5 ⋂#aX ∈|Powσ(𝒫)|. We use Proposition 4.2.6.End of proof

Remark 6.2.7

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 ⋀#aX = ⋀n∈𝔸 X[a↦→n]. However it does not follow from this that ⋂#aX = ⋂n∈𝔸 X[a↦→n]. This is because Theorem 6.2.5 does not hold of ⋂n∈𝔸 X[a↦→n]—it is not in Powσ(𝒫)—and this is because Proposition 6.2.3 fails, which is because Lemma 6.2.2 fails.

That is, if we replace every ∀u∈|𝒰| in Lemma 6.2.2 with ∀n∈𝔸, then Lemma 6.2.2 no longer works (and this is because 𝔸 is not closed under applying substitutions [a↦→u], 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 𝒫 = (|𝒫|, ·, 𝒰, amgis𝒫) is an exact σ-algebra (Definition 3.3.2) over a termlike σ-algebra 𝒰.

Definition 6.3.1

If u, v∈|𝒰| then define (u=𝒫v) ⊆|𝒫| by

(u=𝒫v) = {p∈|𝒫| |Иc.(p[u←↤c] = p[v←↤c])}.
Remark 6.3.2

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 p ∈ (u=𝒫v), meaning by Definition 6.3.1 that Иc.(p[u←↤c] = p[v←↤c]). Using Proposition 3.2.2 p[u←↤c] = p[v←↤c] when x[c↦→u] ∈p ⇔x[c↦→v] ∈p for every x∈|𝒳|. Thus

p ∈(u=𝒫v) ⇔Иc.∀x∈𝒳.(x[c↦→u] ∈p ⇔x[c↦→v] ∈p).

Intuitively this means p cannot discern any difference between u and v. This is in the spirit of Leibnitz equality; two things that equal when they are indiscernible.

More discussion is in Appendix B.

Remark 6.3.3

It is not necessarily the case that supp(u)∪supp(v) ⊆ supp(u=𝒫v). For instance, if 𝒫 has the trivial σ-action that p[u←↤a] = p for all u and a (for instance, take |𝒫| = {∗} the one-element set) then (a=𝒫b) = |𝒫|, which has support ∅.

Lemma 6.3.4 is where we really use the exactness property of 𝒫 (Definition 3.3.2):

Lemma 6.3.4

(u1=𝒫u2)[a↦→v] = ((u1[a↦→v])=𝒫(u2[a↦→v])).

Proof

We reason as follows, where we write u′ 1 = (a′ a)·u1 and u′ 2 = (a′ a)·u2 for brevity:

p∈(u1=𝒫u2)[a↦→v] ⇔Иa′. p[v←↤a′] ∈(u′ 1=𝒫u′ 2) Prop 3.4.2⇔Иa′, c. p[v←↤a′][u′ 1←↤c] = p[v←↤a′][u′ 2←↤c] Def 6.3.1⇔Иa′, c. p[u′ 1[a′↦→v]←↤c][v←↤a′] = p[u′ 2[a′↦→v]←↤c][v←↤a′] (σσ), c#v⇔Иa′, c. p[u′ 1[a′↦→v]←↤c] = p[u′ 2[a′↦→v]←↤c] Exactness⇔Иc. p[u1[a↦→v]←↤c] = p[u2[a↦→v]←↤c] (σα), a′#u1, u2⇔p ∈((u1[a↦→v])=𝒫u2[a↦→v]) Def 6.3.1End of proof
Proposition 6.3.5

Suppose u, v∈|𝒰|. Then:

(1) If a#u, v then (u=𝒫v)[a↦→w] = (u=𝒫v).

(2) If b#u, v then (u=𝒫v)[a↦→b] = (a b)·(u=𝒫v).

As a corollary, (u=𝒫v)∈|Powσ(𝒫)|.

Proof

The first part is from Lemma 6.3.4 and (σ#). The second part is from Lemmas 6.3.4 and 3.1.10 and Theorem 2.3.2.

For the corollary, finite support is from Theorem 2.3.2 and conditions 1 and 2 of Definition 3.4.6 are just the first two parts of this result.End of proof

Lemma 6.3.6

Suppose u, v, w∈|𝒰| and suppose b#u, v. Then

(u=𝒫v)[a↦→w] = ((b a)·u=𝒫(b a)·v)[b↦→v].
Proof

From Lemma 6.3.4 and (σα) (a direct proof by Lemma 3.4.4 is also possible).End of proof

Corollary 6.3.7

p ∈ (u=𝒫v) if and only if p ∈ (a=𝒫b)[a↦→u, b↦→v].

Proof

Using Lemma 6.3.6 we may assume without loss of generality that a, b#u, v so that (a=𝒫b)[a↦→u, b↦→v] = (a=𝒫b)[a↦→u][b↦→v]. It follows by Lemma 6.3.4 that (a=𝒫b)[a↦→u, b↦→v] = (u=𝒫v).End of proof

A converse to Proposition 6.3.8 is valid for a specific model; see Proposition 7.3.7.

Proposition 6.3.8

Suppose X∈|Powσ(𝒫)| and u, v∈|𝒰|. Then:

(1) (u=𝒫u) = |𝒫|.

(2) (u=𝒫v) ∩(X[a↦→u]) = (u=𝒫v) ∩(X[a↦→v]).

Proof

Part 1 follows from the fact that p[u←↤c] = p[u←↤c] for every p and every c.

For part 2, using condition 2 of Definition 3.4.6 to rename if necessary, suppose a#u, v. By Definition 6.3.1 p ∈ (u=𝒫v) means Иa.p[u←↤a] = p[v←↤a]. Using Proposition 3.4.2 and part 2 of Proposition 6.3.5 and part 2 of Lemma 6.1.1 we have

p ∈(u=𝒫v) ∩(X[a↦→u]) ⇔Иa.(p[u←↤a] = p[v←↤a] ∧p[u←↤a] ∈X)⇔Иa.(p[u←↤a] = p[v←↤a] ∧p[v←↤a] ∈X)⇔p ∈(u=𝒫v) ∩(X[a↦→v]).End of proof
Theorem 6.3.9

If 𝒫 is an exact σ-algebra then (a=𝒫b) from Definition 6.3.1 is an equality in Powσ(𝒫) in the sense of Definition 4.3.1.

Proof

By Proposition 6.3.5 (a=𝒫b) is in Powσ(𝒫), and (a=𝒫b) is an equality by Corollary 6.3.7 and Proposition 6.3.8.End of proof

6.4. Interpreting first-order logic in the σ-powerset

We can now prove Theorem 6.4.1:

Theorem 6.4.1

Suppose 𝒫 is an σ-algebra over a termlike σ-algebra 𝒰. Then Powσ(𝒫) is a FOL algebra if we define the following:

⟦⊥⟧ = ∅ ⟦φ∧ψ⟧ = ⟦φ⟧ ∩⟦ψ⟧ ⟦¬φ⟧ = |𝒫| \ ⟦φ⟧ ⟦∀a.φ⟧ = ⋂#a⟦φ⟧ (Def 6.2.1)

If in addition 𝒫 is exact (Definition 3.3.2) then Powσ(𝒫) is a FOLeq algebra if we define the following:

⟦a=b⟧ = {p |Иc.(p[a←↤c] = p[b←↤c])}
Proof

— The Boolean structure (⊥, ∧, and ¬) is treated in Proposition 6.1.3.

— The σ-action ([a↦→u]) 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 ⋂#aX ∈ |Powσ(𝒫)|. We combine these observations with Definition 6.2.1 and Proposition 4.2.6 to conclude that the fresh-finite limit ⋀#aX exists in Powσ(𝒫).

— Equality (=) is treated in Theorem 6.3.9.End of proof

Remark 6.4.2

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 n to an equivariant function fℐ : ⊗n𝔸⇒𝒰 and each P ∈ Π with arity n to an equivariant function Pℐ : ⊗n𝔸⇒Powσ(𝒫) (⊗n is from Definition 5.2.1).

— Definition 5.2.7. The interpretation extends as follows:

⟦a⟧ = atm𝒰(a) Def 3.1.1⟦f(r1, . . . , rn)⟧ = fℐ(a1, . . . , an)[a1↦→⟦r1⟧, . . . , an↦→⟦rn⟧] Defs 5.2.5 & 5.2.7⟦⊥⟧ = ∅ Prop 6.1.3⟦r=s⟧ = {p |Иc.(p[⟦r⟧←↤c] = p[⟦s⟧←↤c])} Def 6.3.1⟦P(r1, . . . , rn)⟧ = Pℐ(a1, . . . , an)[a1↦→⟦r1⟧, . . . , an↦→⟦rn⟧] Defs 5.2.5 & 5.2.7⟦φ∧ψ⟧ = ⟦φ⟧ ∩⟦ψ⟧ Prop 6.1.3⟦¬φ⟧ = |𝒫| \ ⟦φ⟧ Prop 6.1.3⟦∀a.φ⟧ = ⋂#a⟦φ⟧ = ⋂u∈|𝒰| ⟦φ⟧[a↦→u] Def 6.2.1

Recall also that atm𝒰(a) comes from Definition 3.1.1, and where 𝒰 is assumed we will usually write it just as a.

— Theorem 5.2.13. From Theorem 6.4.1 we conclude that if φ1, . . . , φn ⊢ψ1, . . . , ψm then with the definitions above, ⋂i ⟦φi⟧ ⊆⋃j ⟦ψj⟧.

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 ⊤, ∧, ∀a, 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:

Definition 7.1.1

A filter is a nonempty set p of predicates (which need not have finite support) such that:

(1) ⊥∉p (we call p consistent).

(2) If φ ∈p and φ ⊢φ′ then φ′ ∈p (we call p deductively closed).

(3) If φ ∈p and φ′ ∈p then φ∧φ′ ∈p.

(4) If Иb.(b a)·φ ∈p then ∀a.φ ∈p.

Remark 7.1.2

p above need not have finite support. This means that in Definition 7.1.1 it is not the case that Иb.(b a)·φ ∈p if and only if ¬Иb.(b a)·φ ∉p. 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 p. However, x 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 p in Remark 7.1.10.

Ideals are dual to filters; Definition 7.1.3 is standard:

Definition 7.1.3

An ideal is a nonempty set Z of predicates (which need not have finite support) such that:

(1) ⊤∉Z.

(2) If ψ ∈Z and ψ′ ≤ψ then ψ′ ∈Z (we call Z down-closed).

(3) If ψ ∈Z and ψ′ ∈Z then ψ∨ψ′ ∈Z.

Remark 7.1.4

Definition 7.1.3 is not a perfect dual to Definition 7.1.1: we do not have a fourth condition corresponding to condition 4 of Definition 7.1.1.

This is deliberate and will be important; see Remark 7.1.21.

Definition 7.1.5

If φ is a predicate then define φ↑ and φ↓ by

φ↑= {ξ | φ ⊢ξ} and φ↓= {ξ | ξ ⊢φ}.
Lemma 7.1.6

If φ ⊬⊥ then φ↑ from Definition 7.1.5 is a filter and φ↓ is an ideal.

Proof

It is routine to verify conditions 1 to 3 of Definition 7.1.1. We now consider condition 4. Suppose φ ⊢ (b a)·ξ for all but finitely many b. We take one particular b#φ, ξ and conclude using (∀R) that φ ⊢∀a.ξ. The case of φ↓ is no harder.End of proof

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

Lemma 7.1.7

Suppose φ is a predicate and suppose b is fresh (so b#φ). Then φ[a↦→b] is α-equivalent to (b a)·φ.

Sketch proof

The substitution [a↦→b] in φ[a↦→b] is the standard capture-avoiding substitution on the syntax of the predicate φ, from Definition 5.1.1. The permutation (b a)·φ is the permutation acting on the syntax of φ. But when we write ‘b 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.End of proof

Proposition 7.1.8

Suppose p is a filter and a is an atom. Then:

(1) The following conditions are equivalent (below, n ranges over all atoms, including a):

∀a.φ ∈p ⇔ ∀u.φ[a↦→u] ∈p ⇔ ∀n∈𝔸.φ[a↦→n] ∈p ⇔Иb.(b a)·φ ∈p

(2) If furthermore p is finitely supported and a#p then the following conditions are equivalent:

∀a.φ ∈p ⇔ φ ∈p
Proof

First we prove part 1. Suppose ∀a.φ ∈p. By (∀L) from Figure 2 and condition 2 of Definition 7.1.1 also φ[a↦→u] ∈p for every term u. It follows in particular that φ[a↦→n] ∈p for every atom (i.e. variable symbol) n. It follows that φ[a↦→b] ∈p for all b#φ so by Lemma 7.1.7 also Иb.(b a)·φ ∈p. Finally if Иb.(b a)·φ ∈p then by condition 4 of Definition 7.1.1 also ∀a.φ ∈p.

Part 2 follows from part 1 using Theorem 2.3.8.End of proof

It will be useful to have Notation 7.1.9:

Notation 7.1.9

Call a filter p an ultrafilter when for every φ, precisely one of φ ∈p and ¬φ ∈p holds.

Remark 7.1.10

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 p has finite support then by Proposition 7.1.8 for any a#p and φ,

∀a.φ ∈p ⇔φ ∈p ⇔∃a.φ ∈p

where ∃a.φ is shorthand for ¬(∀a.¬φ), and so for any a (even if it is not fresh for p) and φ,

((∀a.φ) ⇔∃a.φ) ∈p.

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:

Definition 7.1.11

Suppose p is a set of predicates and ψ is a predicate. Then define:

p+ψ = {ξ | φ∧ψ ⊢ξ, φ ∈p}
Lemma 7.1.12

Suppose p is a finitely supported filter and suppose ψ is a predicate. Then:

— p ⊆p+ψ.

— ψ ∈p+ψ.

— p+ψ is closed under conditions 2 to 4 of Definition 7.1.1.

As a corollary, if Z is an ideal and p+y ∩Z = ∅ then p+y is a filter.

Proof

The corollary follows from the body of this result because since from condition 2 of Definition 7.1.3 ⊥∈Z, so ⊤∉p.

We now consider the body of this result. It is clear from the construction that p ⊆p+ψ and ψ ∈p+ψ. We now check that p+ψ satisfies conditions 2 to 4 of Definition 7.1.1:

(2) If ξ ∈p+ψ and ξ ⊢ξ′ then ψ′ ∈p+ψ. By construction.

(3) If ξ ∈p+ψ and ξ′ ∈p+ψ then ξ∧ξ′ ∈p+ψ. Suppose φ∧ψ ⊢ξ and φ′∧ψ ⊢ξ′ for φ, φ′ ∈p. Then by condition 3 of Definition 7.1.1 φ∧φ′ ∈p, and it is a fact that (φ∧φ′)∧ψ ⊢ξ∧ξ′.

(4) If Иb.((b a)·ξ ∈p+ψ) then ∀a.ξ ∈p+ψ. Suppose for cofinitely many b there exists a φb ∈p such that φb∧ψ ⊢ (b a)·ξ. Then there certainly exists some b such that b#ψ, ξ, p and φb∧ψ ⊢ (b a)·ξ. Note by Proposition 7.1.8(2) that also ∀b.φb ∈p. We apply ∀b to both sides and we conclude that

(∀b.φb)∧ψ ⊢∀b.(b a)·ξ = ∀a.ξ.

By Lemma 4.1.9 and condition 2 of Definition 7.1.1 we conclude that ∀a.ξ ∈p+ψ as required.End of proof

7.1.4. Growing ideals.

It will be useful to make larger ideals out of smaller ideals:

Definition 7.1.13

Suppose Z and Y are sets of predicates. Then define Z+Y by

Z+Y = {ξ′ | ∃ξ∈Z, n∈ℕ, ψ1, . . . , ψn∈Y.ξ′ ≤ξ∨ψ1∨. . .∨ψn}.

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:

Lemma 7.1.14

Suppose Z is an ideal and Y is some set of predicates. Then:

— Z ⊆Z+Y and Y ⊆Z+Y .

— Z+Y is closed under conditions 2 and 3 of Definition 7.1.3 (so that if ⊤∉Z+Y then it is an ideal).

Proof

By routine calculations.End of proof

7.1.5. Prime filters and ultrafilters

Definition 7.1.15

— Call a filter p prime when φ1∨φ2 ∈p implies either φ1 ∈p or φ2 ∈p.

— Suppose p is a filter and Z is an ideal. Call p maximal with respect to Z when p∩Z = ∅ and for every filter p′ with p′∩Z = ∅, if p ⊆p′ then p = p′.

— Call p 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:

Lemma 7.1.16

A filter p is prime if and only if it is an ultrafilter (Notation 7.1.9).

Proof

Suppose p is prime. We note that (ξ∨¬ξ) ⇔⊤ so by condition 2 of Definition 7.1.1 and non-emptiness of p, ξ∨¬ξ ∈p (we use the conditions of Definition 7.1.1 silently henceforth). By primeness of p, at least one of ξ ∈p and ¬ξ ∈p holds. Similarly (ξ∧¬ξ) ⇔⊥ so that (ξ∧¬ξ) ∉p. It follows that precisely one of ξ ∈p and ¬ξ ∈p holds, so that p is an ultrafilter.

Conversely suppose p is an ultrafilter and suppose ξ∨ξ′ ∈p and yet ξ ∉p and ξ′ ∉p. Then ¬ξ∧¬ξ′ ∈p, so that ⊥∈p, a contradiction.End of proof

Proposition 7.1.17

Suppose p is a filter and Z is an ideal. If p is a maximal filter with respect to Z then it is prime.

Proof

Suppose ψ1∨ψ2 ∈p and ψ1, ψ2 ∉p. By Lemma 7.1.12 and maximality we have that p+ψ1 ∩Z ≠ ∅ and p+ψ2 ∩Z ≠ ∅. It follows that there exist φ1, φ2 ∈p with φ1∧ψ1 ∈Z and φ2∧ψ2 ∈Z. By condition 3 of Definition 7.1.3

(φ1∧ψ1)∨(φ2∧ψ2) ∈Z.

Now we rearrange the left-hand side to deduce that

ζ = (φ1∨φ2)∧(φ1∨ψ2)∧(ψ1∨φ2)∧(ψ1∨ψ2) ∈Z.

We now note that φ1∨φ2 ∈p (since φ1 ∈p, and indeed also φ2 ∈p) and φ1∨ψ2 ∈p (since φ1 ∈p) and ψ1∨φ2 ∈p (since φ2 ∈p) and ψ1∨ψ2 ∈p by assumption. But then ζ ∈p, so that by condition 2 of Definition 7.1.1 ζ ∈p∩Z, a contradiction.End of proof

Lemma 7.1.18 is a technical result which will be useful for proving Theorem 7.1.20:

Lemma 7.1.18

Suppose

— p is a finitely supported filter and Z is an ideal, and suppose

— ⊥∈p+∀a.ψ and p∩Z = ∅.

Write Y = {(b a)·ψ | b ∈𝔸 \ (supp(p)∪supp(ψ) ∪{a})}. Then:

(1) p ∩(Z+Y ) = ∅.

(2) As a corollary, Z+Y is an ideal (and by part 1 is disjoint from p).

Proof

Suppose ⊥∈p+∀a.ψ and p∩Z = ∅ and p ∩ (Z+Y) ≠ ∅. We note the following:

— Since p∩(Z+Y) ≠ ∅, there exist b1, . . . , bn#p, ψ and ξ∈Z with ξ∨(b1 a)·ψ∨. . .∨(bn a)·ψ ∈p.

— Since ⊥∈p+∀a.ψ there exists φ∈p with ⊢φ∧∀a.ψ ⇔⊥. By Proposition 7.1.8(2) (since b1, . . . , bn#p) ∀b1. . .∀bn.φ ∈p, and we see that we may assume without loss of generality that b1, . . . , bn#φ.

— Since p∩Z = ∅ we have ∀φ′∈p, ξ′∈Z. (φ′∧ξ′=⊥).

By condition 3 of Definition 7.1.1

φ∧(ξ∨(b1 a)·ψ∨. . .∨(bn a)·ψ) ∈p

and therefore by distributivity (Definition 4.4.1)

(φ∧ξ)∨(φ∧(b1 a)·ψ)∨. . .∨(φ∧(bn a)·ψ)φ∧ξ=⊥= (φ∧(b1 a)·ψ)∨. . .∨(φ∧(bn a)·ψ) ∈p.

By assumption b1, . . . , bn#p so by Proposition 7.1.8(2) we deduce that

∀b1 . . . bn.((φ∧(b1 a)·ψ)∨. . .∨(φ∧(bn a)·ψ))∈p.

Recall that by assumption b1, . . . , bn#φ, ψ; by properties of first-order logic (including α-equivalence and distributivity) we conclude that

φ∧∀a.ψ ∈p and so that ⊥∈p.

This contradicts condition 1 of Definition 7.1.1.

For the corollary, it follows from condition 2 of Definition 7.1.1 that ⊤∈p so that ⊤∉Z+Y . We use Lemma 7.1.14.End of proof

7.1.6. The Zorn argument

Lemma 7.1.19

If Z1 ⊆Z2 ⊆Z3 ⊆. . . is an ascending chain of ideals then ⋃i Zi is an ideal.

Proof

By standard calculations on the three conditions of Definition 7.1.3.End of proof

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:

Theorem 7.1.20

Suppose p is a finitely supported filter and Z is a finitely supported ideal and suppose p ∩Z = ∅. Then there exists a prime filter q with p ⊆q and q ∩Z = ∅.

As corollaries:

— If φ ⊬ψ then there exists a prime filter q such that φ ∈q and ψ ∉q.

— If φ ⊬⊥ then there exists a prime filter q such that φ ∈q.

Proof

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 (ai, φi)i∈ℕ; 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 (pi, Zi)i∈ℕ as follows:

(1) (p0, Z0) = (p, Z). By assumption p ∩Z = ∅.

(2) Suppose i≥1 and pi-1+∀ai.φi ∩Zi-1 = ∅. Then take

(pi, Zi) = (pi-1+∀ai.φi, Zi-1).

It follows from Lemma 7.1.12 that pi is a filter and from Theorem 2.3.2 that it is finitely supported.

(3) Suppose i≥1 and pi-1+∀ai.φi ∩Zi-1 ≠ ∅. Then take

Y = {(b ai)·φi | b∈𝔸 \ (supp(pi-1)∪supp(φi)∪{ai})} and(pi, Zi) = (pi-1, Zi-1+Y ).

It follows from Lemma 7.1.18 that Zi is an ideal and pi ∩Zi = ∅.

We can note the following:

— We note that p ⊆⋃i pi and Z ⊆⋃i Zi. Since we took (p0, Z0) = (p, Z) and assumed p ∩Z = ∅.

— We note that ⋃i pi is disjoint from ⋃i Zi and thus from Z. By construction.

— We note that ⋃i Zi is an ideal. This is Lemma 7.1.19.

— We note that ⋃i pi is a filter. Conditions 1 to 3 of Definition 7.1.1 are routine. To check condition 4, suppose Иb.(b a)·φ ∈⋃i pi; we need to prove ∀a.φ ∈⋃i pi. So let j be that index in the enumeration above such that (a, φ) = (aj, φj). At stage j, when we built (pj, Zj), there were two possibilities:

— If pj-1+∀a.φ ∩Z = ∅ then we must have put ∀a.φ into pj, so that ∀a.φ ∈⋃i pi and we are done.

— If pj+∀a.φ ∩Z ≠ ∅ then we must have put (b a)·φ into Zj for cofinitely many b, so that Иb.(b a)·φ ∈⋃i Zi. But this is impossible because we assumed that cofinitely many (b a)·φ were in ⋃i pi, which is disjoint from ⋃i Zi.

— We note that ⋃i pi is a maximal filter disjoint from the ideal ⋃i Zi. Consider any φ and choose some fresh a (so a#φ). Note that ⊢∀a.φ ⇔φ. Let j be that index in the enumeration above such that (a, φ) = (aj, φj). It follows from the structure of the algorithm above that precisely one of φ ∈pj or φ ∈Zj will hold. Maximality follows.

Therefore by Proposition 7.1.17 ⋃i pi is a prime filter, and by construction p ⊆⋃i pi and (⋃i pi) ∩ Z = ∅.End of proof

Remark 7.1.21

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 Y to Zi-1, why not add Y ′ = {¬ψ | ψ ∈Y } to pi-1 instead? After all, we have negation.

However if we do this then the set we might write as p+Y ′ would fail to be a filter, because it would contain (b a)·¬φ for cofinitely many b, but not ∀a.¬φ. Furthermore we cannot just add ∀a.¬φ because we may not want this to be in p—what we want is subtly different: that (b a)·φ not be added for cofinitely many b ‘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 p[u←↤a] = {x | x[a↦→u] ∈p}. 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 p is a set of predicates and u 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.

Lemma 7.2.1

If p is a filter then so is p[u←↤a]. Furthermore, if p is prime then so is p[u←↤a].

Proof

We check the conditions in Definition 7.1.1. We use Proposition 3.2.2 without comment:

— ⊥∉p[u←↤a]. Since it is a fact of syntax that ⊥[a↦→u] = ⊥. We use condition 1 of Definition 7.1.1.

— If φ∈p[u←↤a] and φ ⊢φ′ then φ′∈p[u←↤a]. If φ ⊢φ′ then it is a fact of first-order logic derivability that also φ[a↦→u] ⊢φ′[a↦→u]. We use condition 2 of Definition 7.1.1.

— If φ∈p[u←↤a] and φ′∈p[u←↤a] then φ∧φ′ ∈p[u←↤a]. It is a fact of syntax that (φ∧φ′)[a↦→u] = φ[a↦→u]∧(φ′[a↦→u]). We use condition 3 of Definition 7.1.1.

— If Иb′.((b′ b)·φ ∈p[u←↤a]) then ∀b.φ ∈p[u←↤a]. Choose some fresh c (so c#x, u). By Corollary 2.1.12 (b′ c)·(c b)·φ = (b′ b)·φ and by (∀α) also ∀b.φ = ∀c.(c b)·φ. Thus, we may assume without loss of generality that b#u. Now suppose ((b′ b)·φ)[a↦→u] ∈p for all but finitely many b′; so suppose b′#u. By Corollary 2.1.12 (b′ b)·u = u, so that (b′ b)·(φ[a↦→u]) ∈p for all but finitely many b′. By condition 4 of Definition 7.1.1 ∀b.(φ[a↦→u]) ∈p and since b#u it follows that (∀b.φ)[a↦→u] ∈p.

Now suppose p is prime and suppose (ψ1∨ψ2)[a↦→u] ∈p. Then ψ1[a↦→u]∨(ψ2[a↦→u]) ∈p, so that either ψ1[a↦→u] ∈p or ψ2[a↦→u] ∈p.End of proof

Recall from Definition 7.1.15 that we called prime filters points:

Definition 7.2.2

Write Points for the σ-algebra determined by prime filters and the pointwise actions from Definition 3.2.1. That is:

— |Points| = {p | p is a prime filter}. — π·p = {π·φ | φ ∈p} and p[u←↤a] = {φ | φ[a↦→u] ∈p}.
Proposition 7.2.3

Points is indeed an σ-algebra. Furthermore, Points is exact (Definition 3.3.2).

Proof

The first part is just Lemma 7.2.1 combined with Proposition 3.2.6.

We now prove exactness. Suppose Иc.p[u←↤c] = q[u←↤c].

Consider some predicate φ. Note that cofinitely many (all but finitely many) atoms c satisfy all of the following properties, since cofinitely many atoms satisfy each of them, and a finite intersection of cofinite sets is cofinite:

— p[u←↤c] = q[u←↤c] (by assumption),

— c#φ, so that also φ = φ[c↦→u] (a fact of syntax),

— φ[c↦→u] ∈p ⇔φ ∈p[u←↤c] (Proposition 3.2.2), and

— φ[c↦→u] ∈q ⇔φ ∈q[u←↤c] (Proposition 3.2.2).

So there exists at least one c satisfying all the above. Then

φ ∈p ⇔φ[c↦→u] ∈p ⇔φ ∈p[u←↤c] ⇔φ ∈q[u←↤c] ⇔φ[c↦→u] ∈q ⇔φ ∈q.End of proof

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 Powσ(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 r with real substitution r[a↦→t]. Then:

Definition 7.3.1

Define an interpretation ℐ (Definition 5.2.2) as follows:

— Take 𝒰 to be the syntax of terms with real substitution, and fℐ(a1, . . . , an) = f(a1, . . . , an).

— Take L to be Powσ(Points) considered as a FOLeq algebra.

— Take Pℐ(a1, . . . , an) = {p ∈ Points | P(a1, . . . , an) ∈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.

Lemma 7.3.2

If r is a term (Definition 5.1.1) then ⟦r⟧ = r.

Proof

An easy consequence of taking 𝒰 to be syntax with substitution, and of Definition 5.2.5.End of proof

Remark 7.3.3

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 Powσ(Points):

⟦⊥⟧ = ∅ ⟦r=s⟧ = {p∈Points |Иc.(p[r←↤c] = p[s←↤c])} ⟦φ∧ψ⟧ = ⟦φ⟧ ∩⟦ψ⟧ = {p∈Points | p∈⟦φ⟧ ∧p∈⟦ψ⟧} ⟦¬φ⟧ = Points \ ⟦φ⟧ = {p∈Points | p∉⟦φ⟧} ⟦∀a.φ⟧ = ⋂#a⟦φ⟧ = ⋂r ⟦φ⟧[a↦→r]
Lemma 7.3.4

(1) r1=ℐr2 = {p ∈ Points | (r1=r2) ∈p}.

(2) Pℐ(r1, . . . , rn) = {p ∈ Points | P(r1, . . . , rn) ∈p}.

Proof

For part 1, we prove two implications:

— Suppose (r1=r2) ∈p. We will show that p ∈ (r1=ℐr2), that is, that Иc.p[r1←↤c] = p[r2←↤c]. We note by Proposition 3.2.2 that for any atom c,

φ ∈p[r1←↤c] ⇔φ[c↦→r1] ∈p and φ ∈p[r2←↤c] ⇔φ[c↦→r2] ∈p.

By assumption (r1=r2) ∈p so by properties of first-order logic and condition 2 of Definition 7.1.1

φ[c↦→r1] ∈p if and only if φ[c↦→r2] ∈p.

It follows by Proposition 3.2.2 that φ ∈p[r1←↤c] ⊢φ ⇔φ ∈p[r2←↤c]. Since φ and c were arbitrary, we conclude in particular that Иc.p[r1←↤c] = p[r2←↤c].

— Suppose p ∈ (r1=ℐr2), so Иc.p[r1←↤c] = p[r2←↤c]. We will show that (r1=r2) ∈p. Consider some c such that c ∉ fa(r1) ∪ fa(r2) and such that p[r1←↤c] = p[r2←↤c]. By condition 2 of Definition 7.1.1, (r1=r1) ∈p. Also since c ∉ fa(r1) we have that (r1=r1) = (r1=c)[c↦→r1], so that (r1=c)[c↦→r1] ∈p, and by Proposition 3.2.2 (r1=c) ∈p[r1←↤c]. Therefore (r1=c) ∈p[r2←↤c] and again by Proposition 3.2.2 and our assumption that c ∉ fa(r2) we conclude that (r1=r2) ∈p as required.

For part 2 we reason as follows:

P(r1, . . . , rn) ∈p ⇔Иa1, . . . , an.P(a1, . . . , an)[a1↦→r1, . . . , an↦→rn] ∈p Fact of syntax⇔Иa1, . . . , an.P(a1, . . . , an) ∈p[r1←↤a1] . . . [rn←↤an] Prop 3.2.2⇔Иa1, . . . , an.p[r1←↤a1] . . . [rn←↤an] ∈Pℐ(a1, . . . , an) Def 7.3.1⇔Иa1, . . . , an.p ∈Pℐ(a1, . . . , an)[a1↦→r1, . . . , an↦→rn] Prop 3.4.2⇔p ∈Pℐ(r1, . . . , rn) Def 5.2.5End of proof

We should briefly check that Definition 7.3.1 is well-defined, in the sense that Pℐ(a1, . . . , an) from clause 3 is indeed an element of L from clause 2. This is routine:

Lemma 7.3.5

Continuing the notation of Definition 7.3.1, Pℐ(a1, . . . , an) which is equal to {p ∈ Points | P(a1, . . . , an) ∈p}, is an element of Powσ(Points).

Proof

Finite support is from Theorem 2.3.2 since the support of Pℐ(a1, . . . , an) is bounded by {a1, . . . , an}, which is finite. It remains to check conditions 1 and 2 of Definition 3.4.6, namely:

— For fresh a (so a ∉{a1, . . . , an}) and any term r, Pℐ(a1, . . . , an)[a↦→r] = Pℐ(a1, . . . , an).

— For fresh b (so b ∉ {a1, . . . , an}) and any atom m (so possibly m ∈ {a1, . . . , an}), Pℐ(a1, . . . , an)[m↦→r] = (b m)·Pℐ(a1, . . . , an).

For the first condition, by Proposition 3.4.2 p ∈ Pℐ(a1, . . . , an)[a↦→r] if and only if Иa′.p[r←↤a′] ∈ Pℐ(a1, . . . , an). By Definition 7.3.1 this is if and only if Иa′.P(a1, . . . , an) ∈p[r←↤a′]. By Proposition 3.2.2 this is if and only if Иa′.P(a1, . . . , an)[a′↦→r] ∈p. It is now a fact of syntax that P(a1, . . . , an)[a↦→r] = P(a1, . . . , an).

The second condition follows much as the first, using the fact of syntax that P(a1, . . . , an)[m↦→b] = (b m)·P(a1, . . . , an).End of proof

Theorem 7.3.6

⟦φ⟧ = {p ∈ Points | φ ∈p}.

Proof

By induction on φ:

— The case of ⊥. By assumption in Definition 7.1.1 p ∈ Points is consistent (meaning ⊥∉p). Furthermore, ⟦⊥⟧ = ∅.

— The cases of r1=r2 and P(r1, . . . , rn). 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 p is prime (Definition 7.1.15), and it follows by Lemma 7.1.16 that ¬φ ∈p if and only if φ ∈p. Also by assumption ⟦¬φ⟧ = Points\⟦φ⟧.

— The case of ∀a.φ. Combining Remark 7.3.3 with Proposition 3.4.2 p ∈ ⟦∀a.φ⟧ means that Иc.p[r←↤c] ∈ (c a)·⟦φ⟧ for every r. By inductive hypothesis this is if and only if Иc.(c a)·φ ∈ p[r←↤c] for every r, which by Proposition 3.2.2 and α-conversion is if and only if φ[a↦→r] ∈p for every r. We use Proposition 7.1.8(1).End of proof

By Proposition 6.3.8 (u=ℐu) = Points. In Proposition 7.3.7 we show that specifically for the interpretation of Definition 7.3.1, a converse holds:

Proposition 7.3.7

If (r1=ℐr2) = Points then r1 = r2 (that is, r1 and r2 are syntactically identical terms).

Proof

Suppose (r1=ℐr2) = Points and r1 ≠ r2. It is a fact of first-order logic that ¬(r1=r2) ⊬⊥ (easily proved using cut-elimination and the syntax-directed nature of the derivation rules). By Theorem 7.1.20 there exists a point p such that ¬(r1=r2) ∈p. Now by assumption p ∈ (r1=ℐr2), so by Theorem 7.3.6 (r1=ℐr2) ∈p. Thus ⊥∈p, a contradiction.End of proof

Remark 7.3.8

It is worth pausing to note, informally but mathematically, why Propositions 6.3.8 and 7.3.7 are remarkable.

We constructed Powσ(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, Powσ(Points) would still have an equality.

In summary: Powσ(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.

Corollary 7.3.9

If φ ⊬ψ then ⟦φ⟧ ⊈ ⟦ψ⟧.

Proof

Suppose φ ⊬ψ. By Theorem 7.1.20 there exists a point q with ψ ∉q and φ↑⊆q so that φ ∈q. By Theorem 7.3.6 it follows that q ∈ ⟦φ⟧ and q ∉ ⟦ψ⟧, and the result follows.End of proof

Theorem 7.3.10 is a converse to Theorem 5.2.13:

Theorem 7.3.10 (Completeness).

If ⟦Φ ⊢ Ψ⟧ is true for every interpretation in every FOLeq algebra, then Φ ⊢ Ψ.

Proof

From Corollary 7.3.9.End of proof

Corollary 7.3.11

⟦φ⟧ = 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.

Notation 8.1.1

To avoid the confusion between sets and nominal sets, we may write ordinary set for the former.

Definition 8.1.2

Suppose X is an ordinary set. Write 𝔸⇒X for the set of functions from atoms to X. Let ς range over elements of 𝔸⇒X and call these valuations (to X).

If x ∈X then define ς[a:=x] to be the function on atoms given by:

(ς[a:=x])(a) = x (ς[a:=x])(b) = ς(b) for all other b
Definition 8.1.3

Define a permutation action on ς ∈𝔸⇒X by

(π·ς)(a) = ς(π-1(a)).
Remark 8.1.4

𝔸⇒X 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 (π·ς)(a) = π·ς(π-1(a)) (already mentioned in Subsection 2.2.4), where we use the trivial action π·x = x for every x ∈X. 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.

Definition 8.1.5

An ordinary model N = (|N|, -𝒩) is a tuple such that:

— |N| is some non-empty (ordinary) underlying set.

— -𝒩 assigns to each term-former f a function f𝒩 : |N|ar(f)⇒|N| and to each predicate-former P a function P𝒩 : |N|ar(P)⇒{⊥, ⊤}.

Definition 8.1.6

{⊥, ⊤} 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.

Definition 8.1.7

Define a (standard) interpretation function ⟦-⟧N ς mapping terms and predicates to elements of |N| and {⊥, ⊤} (considered as a Boolean algebra) respectively, as follows:

⟦a⟧N ς = ς(a) ⟦f(r1, . . . , rn)⟧N ς = f𝒩(⟦r1⟧N ς , . . . , ⟦rn⟧N ς )⟦⊥⟧N ς = ⊥ ⟦P(r1, . . . , rn)⟧N ς = P𝒩(⟦r1⟧N ς , . . . , ⟦rn⟧N ς )⟦φ′∧φ⟧N ς = ⟦φ′⟧N ς ∧⟦φ⟧N ς⟦∀a.φ⟧N ς = ⋀x∈|N|⟦φ⟧N ς[a:=x]⟦¬φ⟧N ς = ¬⟦φ⟧N ς

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]:

Theorem 8.1.8

Φ ⊢ Ψ is derivable if and only if for every ordinary model N and every valuation ς to |N| it is the case that ⋀φ∈Φ⟦φ⟧N ς = ⊤ implies ⋁ψ∈Ψ⟦ψ⟧N ς = ⊤.

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

Definition 8.2.1

Given ordinary sets X and Y define a termlike σ-algebra Tarski(X, X), and define a σ-algebra Tarski(X, Y) over Tarski(X, X) by:

Tarski(X, X) = (|Tarski(X, X)|, ·, subTarski(X,Y ), atmTarski(X,X)) Tarski(X, Y ) = (|Tarski(X, Y )|, ·, subTarski(X,Y ))

as follows:

— |Tarski(X, Y)| is the set of functions f from 𝔸⇒X to Y such that there exists a finite set Af ⊆𝔸 such that

∀a∈Af.ς(a) = ς′(a) implies f(ς) = f(ς′) (1)

(if X = Y then we obtain |Tarski(X, X)|).

— The permutation action · is defined by

(π·f)(ς) = f(π-1·ς).

— If f ∈𝔸⇒Y and u ∈𝔸⇒X define

(f[a↦→u])(ς) = f(ς[a:=u(ς)]).

— If X = Y then define atmTarski(X,X)(a)(ς) = ς(a).

Notation 8.2.2

atmTarski(X,X)(a) is a bit of a mouthful so we may just write it as a. It will always be clear whether we mean ‘a ∈𝔸’ or ‘a ∈ Tarski(X, X)’.

Lemma 8.2.3

(|Tarski(X, Y)|, ·) from Definition 8.2.1 is indeed a nominal set (Definition 2.1.5).

Proof

It is routine to verify that the permutation action is a group action. It remains to check finite support.

Suppose π(a) = a for every a ∈Af where Af is the finite set of atoms whose existence for each f is assumed in Definition 8.2.1. By Definition 8.2.1 (π·f)(ς) = f(π-1·ς). By Definition 8.1.3 (π-1·ς)(a) = ς(π(a)). Now by assumption ς(a) = ς(π(a)) for every a ∈Af. Therefore, (π-1·ς)(a) = ς(a) for every a ∈Af, and so f(ς) = f(π-1·ς), and so (π·f)(ς) = f(ς). Thus, f has finite support (and is supported by Af).End of proof

Lemma 8.2.4

Suppose f ∈|Tarski(X, Y)|. Then ∀a∈supp(f).ς(a)=ς′(a) implies f(ς) = f(ς′).

Proof

It suffices to show that if a ∈Af\supp(f) and x ∈X then f(ς[a:=x]) = f(ς). Choose fresh b (so b ∉Af). By part 1 of Corollary 2.1.12 (b a)·f = f, since a, b ∉ supp(f). We reason as follows:

f(ς[a:=x])b∉Af= f(ς[a:=x][b:=ς(a)])(b a)·f=f= f(ς[b:=x])b∉Af= f(ς)End of proof
Remark 8.2.5

Lemma 8.2.4 does not follow from Lemma 8.2.3: to see this, take X=Y ={0, 1} and f(ς) = min{ς(a) | a∈𝔸}. Then by Theorem 2.3.2 supp(f)=∅ so that ∀a∈supp(f).ς(a)=ς′(a) for any ς and ς′, yet f(ς) ≠ f(ς′) where ς = λa∈𝔸.0 and ς′ = λa∈𝔸.1.

What makes Lemma 8.2.4 work is the interaction of support with condition (1) of Definition 8.2.1.

Corollary 8.2.6

Tarski(X, X) is indeed a termlike σ-algebra, and Tarski(X, Y) is a σ-algebra over Tarski(X, X).

Proof

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(X, X)). Unpacking definitions, a[a↦→u](ς) = ς[a:=u(ς)](a) = u(ς).

— Rule (σid). Again we unpack definitions: f[a↦→a](ς) = f(ς[a:=ς(a)]) = f(ς).

— Rule (σ#). Using Lemma 8.2.4.

— Rule (σα). Suppose f ∈ Tarski(X, Y) and b#f, and u ∈ Tarski(X, X). Then f[a↦→u](ς) = f(ς[a:=u(ς)]). Also, unpacking Definitions 8.1.3 and 8.2.1 ((b a)·f)[b↦→u] = f(ς[a:=u(ς)][b:=ς(a)]). We use Lemma 8.2.4.

— Rule (σσ). Suppose f ∈ Tarski(X, Y) and u, v ∈ Tarski(X, X) and a#v. We just unpack definitions:

f[a↦→u][b↦→v](ς) = f[a↦→u](ς[b:=v(ς)]) = f(ς[a:=u(ς[b:=v(ς)])][b:=v(ς)]) f[b↦→v][a↦→u[b↦→v]](ς) = f[b↦→v](ς[a:=u(ς[b:=v(ς)])]) = f(ς[a:=u(ς[b:=v(ς)])][b:=v(ς[a:=u(ς[b:=v(ς)])])]) = f(ς[a:=u(ς[b:=v(ς)])][b:=v(ς)])

The final step is valid using Lemma 8.2.4 since a#v. (There are two symbols here: ↦→ and :=. f[a↦→u] is ‘f with u substituted for a’ from Definition 8.2.1, and ς[a:=u(ς)] is ‘ς with a maps to u(ς)’ from Definition 8.1.2.)End of proof

8.2.2. Interlude: more on limits in nominal posets.

For this subsection, fix a nominal poset L (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:

Definition 8.2.7

Following [Gab09b; GC11] define x↶a by

x↶a = {π·x | π ∈fix(supp(x)\{a})}. = {x} ∪{(b a)·x | b#x}

Write ⋀ x↶a for the ≤-greatest lower bound of x↶a, if this exists.

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:

Lemma 8.2.8

a#x↶a.

Proof

We note by the pointwise action that π′·x↶a = {(π′ ◦π)·x | π ∈ fix(supp(x)\{a})}. We choose a fresh b (so b#x, that is, b∉supp(x)) and use Corollary 2.1.12(3) and routine calculations.End of proof

Proposition 8.2.9

Suppose a∈𝔸 and x∈|L|. Then:

(1) If ⋀#ax exists then so does ⋀ x↶a, and they are equal.

(2) Suppose L has a monotone σ-action (Definition 4.2.1). Then if ⋀ x↶a exists, then so does ⋀#ax, and they are equal.

Proof

(1) By Definition 4.1.1 ⋀#ax ≤x and a#⋀#ax. It follows by equivariance of ≤ and Corollary 2.1.12 that ⋀#ax ≤π·x for every π ∈ fix(supp(x)\{a}). Therefore ⋀#ax is a lower bound for x↶a. Now consider z some other lower bound for x↶a, so that ∀π∈fix(supp(x)\{a}).z ≤π·x. Choose fresh b (so b#x, z); by Theorem 2.3.2 ⋀#b(b a)·x exists (and by Lemma 4.1.9 it is equal to ⋀#ax). It follows by equivariance of ≤ and Corollary 2.1.12 (since a, b#z) that z ≤ (b a)·x so z ≤⋀#b(b a)·xL4.1.9=⋀#ax.

(2) By Lemma 8.2.8 and Theorem 2.3.2 a# ⋀ x↶a so ⋀ x↶a is an a#lower bound for x. Consider any other z such that z ≤x and a#z. By (σ#) z[a↦→n] = z for every n∈𝔸. By monotonicity z = z[a↦→n] ≤x[a↦→n] for every n∈𝔸. It follows using Lemma 3.1.10 that z ≤⋀ x↶a.End of proof

Remark 8.2.10

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.

Definition 8.2.11

Call a nominal poset L = (|L|, ·, ≤) nominally complete when every finitely supported subset X ⊆|L| has a greatest lower bound.

In another terminology: L is nominally complete when it has limits of finitely supported diagrams.

Proposition 8.2.12

If L is nominally complete and has a monotone σ-action, then it is finitely fresh-complete (Definition 4.1.1).

In other words: having finitely supported limits and substitution implies having fresh-finite limits.22

Proof

We use Proposition 4.1.5. By Theorem 2.3.2 ∅⊆|L| and {x, y}⊆|L| and x↶a are finitely supported. By Proposition 8.2.9 the a#limit ⋀#ax exists in L if and only if the limit of x↶a does. The result follows.End of proof

8.2.3. Lifting the logical structure

Definition 8.2.13

Suppose f ′, f ∈|Tarski(X, {⊥, ⊤})|. Write f ′ ≤f when ∀ς.f ′(ς) ≤f(ς).

Lemma 8.2.14

With the partial order f ′ ≤f of Definition 8.2.13, the σ-action from Definition 8.2.1 is monotone.

Proof

Suppose f ′ ≤f and u ∈|Tarski(X, X)| and ς ∈𝔸⇒X. We reason as follows:

(f ′[a↦→u])(ς) = f ′(ς[a:=u(ς)]) Definition 8.2.1≤f(ς[a:=u(ς)] Definition 8.2.13 f ′ ≤f= (f[a↦→u])(ς) Definition 8.2.1End of proof
Proposition 8.2.15

(|Tarski(X, {⊥, ⊤})|, ·, ≤) is nominally complete, complemented, and has a compatible σ-action and an equality.

As a corollary, (|Tarski(X, {⊥, ⊤})|, ·, ≤) is also a FOLeq algebra (Definition 4.4.3).

Proof

The greatest lower bound of a finitely supported set X ⊆|Tarski(X, {⊥, ⊤})|, and the complement of f∈|Tarski(X, {⊥, ⊤})|, are defined pointwise by

(⋀X)(ς) =⋀f∈Xf(ς) and (¬f)(ς) = ¬(f(ς)).

Equality is defined by

(u1=Tarski(X,{⊥,⊤})u2)(ς) ={⊤ u1(ς) = u2(ς)⊥ u1(ς) ≠ u2(ς).

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.End of proof

Remark 8.2.16

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:

Definition 8.2.17

Suppose N is an ordinary model (Definition 8.1.5), so that by Proposition 8.2.15 we have that Tarski(|N|, {⊥, ⊤}) is a FOLeq algebra.

Define an interpretation ℐ over Tarski(|N|, {⊥, ⊤}) in the sense of Definition 5.2.2 as follows:

fℐ(a1, . . . , aar(f))(ς) = f𝒩(ς(a1), . . . , ς(aar(f))) Pℐ(a1, . . . , aar(P))(ς) = P𝒩(ς(a1), . . . , ς(aar(P)))

where the ai are distinct atoms (the ai above left are short for atmTarski(X,X)(ai) from Definition 8.2.1).

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:

Corollary 8.2.18

If Φ ⊬ Ψ, then there exists a termlike σ-algebra 𝒰 and a FOLeq algebra ℳ over 𝒰 such that ⋀φ∈Φ⟦φ⟧ℐ ≰⋁ψ∈Ψ⟦ψ⟧ℐ.

Proof

By completeness of first-order logic there exists some ordinary model N (Definition 8.1.5) and valuation ς to N such that ⋀φ∈Φ⟦φ⟧N ς = ⊤ and ⋁ψ∈Ψ⟦ψ⟧N ς = ⊥.

So consider Tarski(|N|, {⊥, ⊤}) and consider the interpretation ℐ from Definition 8.2.17. It follows from Definition 8.2.13 that ⋀φ∈Φ⟦φ⟧ℐ ≰⋁ψ∈Ψ⟦ψ⟧ℐ.End of proof

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.

Definition 9.0.19

Define a logical equivalence relation ∼ on predicates by

φ ∼φ′when φ ⊢φ′ ∧φ′ ⊢φ.

Write [φ]∼ for the ∼-equivalence class of φ.

If x and x′ are ∼-equivalence classes then impose a partial order by x ≤x′ when φ ∈x and φ′ ∈x′ 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:

Lemma 9.0.20

If φ ∼φ′ then π·φ ∼π·φ′.

Definition 9.0.21

Give ∼-equivalence classes the pointwise permutation action by π·[φ]∼= [π·φ]∼.

Definition 9.0.22

Give ∼-equivalence classes a pointwise σ-action by [φ]∼[a↦→u] = [φ[a↦→u]]∼.

We need to check that [φ]∼[a↦→u] is well-defined, that is, if φ ∼φ′ then φ[a↦→u] ∼φ′[a↦→u]. This is a fact of first-order logic.

Definition 9.0.23

Define 𝒰 to be the termlike σ-algebra of terms where substitution is real substitution on syntax, and take L = (|L|, ·, ≤, 𝒰, sub𝒰) to be ∼-equivalence classes of predicates, with the pointwise permutation and σ-actions.

Theorem 9.0.24

L is a FOLeq algebra if we take ⊤ to be [⊤]∼, [φ]∼∧ [φ′]∼ to be [φ∧φ′]∼, ⋀#a[φ]∼ to be [∀a.φ]∼, and r=s to be [r=s]∼.

Proof

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.End of proof

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 x depends on—without needing to know what logic, program, or computation x represents (if any). If we use our foundations correctly then the support of x will relate sensibly to what x 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 a∉supp(x) then substitution [a↦→u] does not change x. This connects nominal support—being affected by a permutation like (b a)—with the notion of semantic dependency that comes from being in a σ-algebra and being affected by [a↦→u].

The two points above are visible in syntax: if a is not free in φ then φ with a substituted for a term r is equal to φ. By the two points above, if a is not free in φ then also ⟦φ⟧[a↦→u] = ⟦φ⟧. In fact, the semantics is ‘compositional’ with respect to substitution; ⟦φ[a↦→r]⟧ = ⟦φ⟧[a↦→⟦r⟧] (Lemma 5.2.11). The reader used to Tarski semantics might recognise the corresponding result ⟦φ[a↦→r]⟧ς = ⟦φ⟧ς[a↦→⟦r⟧ς]. 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 x 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 x and y 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 ∀a using fresh-finite limits ⋀#a (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: ∀X). 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 ∀a)—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 n an arrow fT from n to 0. A hyperdoctrine is a functor F from T to the category of Boolean algebras, along with an assignment to each P of arity n of an element PF in F(n).

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 |ℬ|n →|ℬ| 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 [a↦→u]—which since we are oversimplifying we might as well call substitution, though it is not necessarily syntactic.

Viewed as an operator, the substitution [a↦→u] is a modality (a unary operator) with special properties: it commutes with meets ∧, joins ∨, and negation ¬. Thus, [a↦→u] 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

X[a↦→u] = {p |Иc.p[u←↤c] ∈(c a)·X} and p[u←↤a] = {x | x[a↦→u] ∈X}

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 [a↦→u] 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 x∈|𝒳| can be thought of as a family of A ⊢x for A ⊆𝔸 such that supp(x) ⊆A. In other words, x ‘exists’ in a context if and only if the context contains the support of x.

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 x[a↦→y] as composition of x and y ‘at a’. 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.

[MVF+02] 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 ⋀#AX. Proposition 4.1.5 split this notion up into three parts which are sometimes more convenient for proofs: ⊤, ∧, and ⋀#a. 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 ∀

Definition A.1.1

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:

(x ∧y) ∧z = x ∧(y ∧z) x ∧y = y ∧x x ∧x = x x ∧⊤= x

Here, x, y, z range over elements of |ℳ|.

Definition A.1.2

As standard, a meet-semilattice acquires a partial order by setting x ≤y when x ∧y = x. A bounded meet-semilattice yields a poset with a top element (⊤).

Definition A.1.3

A generalised universal quantifier ∀ on a bounded meet-semilattice ℳ is an equivariant map ∀ : (𝔸 × ℳ)⇒ℳ such that:

(∀α) b#x ⇒ ∀b.(b a)·x = x(∀∧) ∀a.(x ∧y) = (∀a.x) ∧(∀a.y)(∀#) a#x ⇒ ∀a.x = x(∀≤) ∀a.x ≤x

(Recall that ∀a.x ≤x is shorthand for (∀a.x) ∧x = ∀a.x.)

Lemma A.1.4

If x ≤y then ∀a.x ≤∀a.y.

Proof

x ≤y means x ∧y = x. We apply ∀a to both sides and use (∀∧).End of proof

Proposition A.1.5

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.

— x ∧y is a limit for {x, y}.

— ∀a.x is an a#limit for {x}.

Proof

The first two parts are standard; the interesting case is part 3.

From (∀α) and part 3 of Corollary 2.1.12 we derive that a#∀a.x. With this and (∀≤) we have that ∀a.x is an a#lower bound for x.

Now suppose z ≤x and a#z. By Lemma A.1.4 and (∀#) we deduce z ≤∀a.x.End of proof

Corollary A.1.6

Every bounded meet-semilattice with ∀ can be viewed as a nominal poset with fresh-finite limits, and vice versa.

Proof

Using the constructions of Propositions 4.1.5 and A.1.5.End of proof

Definition A.1.7 and Proposition A.1.8 merely package the observations above in categorical language:

Definition A.1.7

Given ℳ and ℳ′ bounded meet-semilattices with ∀, a homomorphism F : ℳ⇒ℳ′ is a function on the underlying nominal sets such that:

— F(π·x) = π·F(x), meaning that F is equivariant (Definition 2.1.6).

— F(⊤ℳ) = ⊤ℳ′ and F(x ∧ℳ y) = F(x) ∧ℳ′ F(y) and F(∀ℳa.x) = ∀ℳ′a.x.

Given 𝒩 and 𝒩′ nominal posets with fresh-finite limits, a homomorphism G : 𝒩⇒𝒩′ is a function on the underlying nominal sets such that:

— G(π·x) = π·G(x) (so G is equivariant).

— G(⋀#AX) = ⋀#A{G(x) | x ∈X}.

Write Semi∀ for the category of bounded meet-semilattices with ∀ and homomorphisms between them, and Poset⋀#A for the category of nominal posets with fresh-finite limits.

Proposition A.1.8

The natural functors mapping between Semi∀ and Poset⋀#A 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.

(∀α) b#x ⇒ ∀b.(b a)·x = x(∀∧) ∀a.(x ∧y) = (∀a.x) ∧(∀a.y)(∀∨) a#y ⇒ ∀a.(x ∨y) = (∀a.x) ∨y(∀≤) ∀a.x ≤x
Fig. 4: Nominal algebra axioms for ∀ in a bounded lattice
Definition A.2.1

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 ⊥,

(x ∧y) ∧z = x ∧(y ∧z) x ∧y = y ∧x x ∧x = x x ∧⊤= x(x ∨y) ∨z = x ∨(y ∨z) x ∨y = y ∨x x ∨x = x x ∨⊥= x

and ∧ and ∨ satisfy absorption

x ∧(x ∨y) = x x ∨(x ∧y) = x.

Here, x, y, z range over elements of |ℒ|.

Similarly to Definition A.1.2, a bounded lattice is a poset by taking x ≤y to mean x ∧y = x or x ∨y = y (the two conditions are provably equivalent).

Definition A.2.2

A generalised universal quantifier ∀ on a bounded lattice ℒ is an equivariant map ∀ : (𝔸 × ℒ)⇒ℒ satisfying the equalities in Figure 4.

Remark A.2.3

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

Proposition A.2.4

Suppose ℒ is a bounded lattice with ∀ and x∈|ℒ|. Then (∀#) from Definition A.1.3 follows from the other axioms of a generalised universal quantifier on a bounded lattice.

That is, a#x implies ∀a.x = x

Proof

We note that ∀a.x = ∀a.(x ∨x) (∀∨) = (∀a.x) ∨x so that x ≤∀a.x. Furthermore by (∀≤) ∀a.x ≤x, and we are done.End of proof

Corollary A.2.5

Suppose ℒ is a bounded lattice with a generalised universal quantifier ∀. Then ∀a.x is the a#limit for {x}.

Proof

By Proposition A.2.4 (∀#) holds, so the restriction of ℒ to ⊤, ∧, and ∀ forms a bounded meet-semilattice, and it is a fact that this has the same partial order. We use Proposition A.1.5.End of proof

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

Theorem A.3.1

Suppose 𝒰 is a termlike σ-algebra. The FOLeq algebras over 𝒰 (Definition 4.4.3) are precisely characterised as an underlying nonempty nominal set L along with

— an equivariant σ-action sub : (L × 𝔸 × 𝒰)⇒ℒ, written infix x[a↦→u];

— an equivariant function ∧ : L × L⇒L;

— an equivariant function ¬ : L⇒L,

— an equivariant function ∀ : (𝔸 × L)⇒L, and

— an equivariant function =L: (𝒰 × 𝒰)⇒L,

such that:

(1) sub satisfies the axioms of a σ-action over 𝒰 from Figure 1 and

(x ∧y)[a↦→u] = (x[a↦→u]) ∧(y[a↦→u]) (¬x)[a↦→u] = ¬(x[a↦→u]) b#u ⇒(∀b.y)[a↦→u] = ∀b.(y[a↦→u]), (v′=Lv)[a↦→u] = (v′[a↦→u]) =L (v[a↦→u])

(2) if we take ⊤= ¬(x ∧¬x) (for any x) and x ∨y = ¬(¬x ∧¬y) and ⊥= ¬⊤ then ⊤, ∧, ⊥, and ∨ satisfy the axioms of a bounded lattice from Definition A.2.1,

(3) in addition31

x ∧(y ∨z) = (x ∧y) ∨(x ∧z) ¬¬x = x,

(4) ∀ satisfies the axioms of a generalised universal quantifier from Figure 4, and finally

(5) =L satisfies the axioms

(u=Lu) = ⊤ (u=Lv) ∧z[a↦→u] = (u=Lv) ∧z[a↦→v]
Proof

We have all the pieces, we just need to put them together.

Suppose L is a FOLeq algebra. We take ⊤ to be the top element, x∧y to be the limit of {x, y}, ∀a.x to be ⋀#ax the a#limit of {x}, ¬x to be the complement of x in L (which is unique by Lemma 4.1.7), and u=Lv to be (a=b)[a↦→u, b↦→v] where =L is the equality of L (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 L is distributive (Definition 4.4.1) and complemented, and it follows that ∧ distributes over ∨ and ¬¬x = x.

— By Lemma 4.1.9 ∀ satisfies (∀α) from Figure 4. By routine calculations on limits ∀ satisfies (∀∧).32 By assumption L is distributive (Definition 4.4.1), so (∀∨) holds. By the definition of a fresh-finite limit ∀a.x ≤x.

Now suppose L 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 x ∧y is a limit for {x, y}. By Corollary A.2.5 ∀a.x is an a#limit for {x}. It follows by Proposition 4.1.5 that L 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 L 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 a=Lb is an equality in the sense of Definition 4.3.1.33End of proof

B. ON THE LEIBNITZ EQUALITY

Remark B.0.2

In Remark 6.3.2 we noted that Definition 6.3.1 is a form of Leibnitz equality: p ∈ (a =𝒫 b) when it ‘cannot distinguish between a and b’.

Could it be that (a =𝒫 b) is also equal to {p∈|𝒫| | (a b)·p = p}? After all, if (a b)·p = p then p also ‘cannot distinguish a and b’.

This notion is too weak. To see this intuitively, consider that the unordered pair {a, b} is invariant under swapping a and b, but is not invariant under converting b into a to obtain {a}.

We note that a strengthened version of Definition 6.3.1 is possible:

Lemma B.0.3

p ∈ (u =𝒫 v) if and only if for all atoms c, p[u←↤c] = p[v←↤c].

In symbols: (u =𝒫 v) = {p∈|𝒫| | ∀c.p[u←↤c] = p[v←↤c]}.
Proof

Clearly if for all atoms c, p[u←↤c] = p[v←↤c], then for all but finitely many c, p[u←↤c] = p[v←↤c].

Conversely, suppose p[u←↤c] = p[v←↤c] for all but finitely many c, and consider any atom a and element x. Now choose one c such that c#u, v, x and p[u←↤c] = p[v←↤c] (this is always possible because all but finitely many c satisfy each condition). By (σα) x[a↦→u] = ((c a)·x)[c↦→u] and x[a↦→v] = ((c a)·x)[c↦→v] and it follows using Proposition 3.2.2 repeatedly that x ∈p[u←↤a] if and only x ∈p[v←↤a].End of proof

Remark B.0.4

Given Lemma B.0.3, could Definition 6.3.1 use ∀c instead of the less familiar Иc?

Yes, but the use of the И-quantifier is preferable. It is a weaker proof-obligation; it is strictly easier to prove Иc.p[u←↤c] = p[u←↤c] than it is to prove ∀c.p[u←↤c] = p[u←↤c], because we have to worry about ‘fewer values’ for c.

This is exploited immediately after Definition 6.3.1 in Lemma 6.3.4 when we use two И-quantifiers, one for a′ and one for c. If we had taken Lemma B.0.3 as our definition instead, then we would have had to worry about the case a′ = c; 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:

Lemma B.0.5

Suppose 𝒳 is a nominal set and X, Y ∈|NomPow(𝒳)| are finitely supported subsets of 𝒳 (Subsection 2.4.1), and suppose a#X and a#Y . Write X#a = {x∈X | a#x} and Y#a = {y∈Y | a#y}. Then

X = Y if and only if X#a = Y#a.
Proof

The left-to-right implication is immediate. For the right-to-left implication it suffices to prove that X ⊆Y . So suppose x ∈X. Choose fresh b; then (b a)·x ∈X and by Proposition 2.3.4 a#(b a)·x so (b a)·x ∈Y so that x ∈Y .End of proof

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 x is understood to contain all the variables mentioned in the predicate. It is not the case that a = a if and only if a = b—but it is the case that a = b if and only if b = a. ↩

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 atm𝒳. ↩

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 X ∈|NomPow(𝒫)|—X is finitely supported—but this result does not depend on that. ↩

9Recall that p 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. Powσ is the σ-powerset and is from 3.4.6. ↩

12So x ≤y if and only if π·x ≤π·y. ↩

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 {x[a↦→u] | u∈|𝒰|} could be finite: either a#x so that by (σ#) x[a↦→u] = x for all u; or |𝒰| is finite, so that in particular atm𝒰 maps every a 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 ⋀#a, 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 ⋀n x[a↦→atm𝒰(n)]. See the notation in Definition 3.1.1. ↩

17In fact we only care about ∧ here, not ⋀#a. ↩

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 A ⊆𝔸 such that for all a, b ∉A, ς(a) = ς(b); 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. {x′∈|L| | supp(x′)⊆supp(x)\{a} ∧x′≤x} and ⋀n∈𝔸 x[a↦→n]. ↩

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 a, b, and c 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 [MVF+02] 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 a=Lb whereas above we assume an equivariant function =L and in condition 1 we assume that substitution distributes over it. ↩