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

Quantifiers in logic and proof-search using permissive-nominal terms and sets

Murdoch J. Gabbay, Claus-Peter Wirth

Source watermark: DRAFT

Abstract

We investigate models of first-order logic designed to give semantics to reductive proof-search systems, with special attention to the so-called γ- and δ-rules controlling quantifiers. The key innovation is the use of syntax and semantics with (finitely-supported) name-symmetry, in the style of nominal techniques.

Keywords: Proof-search; nominal techniques; name-symmetry; higher-order logic; quantifiers

$The authors are grateful for the detailed input of two anonymous referees and acknowledge the support of the Leverhulme Trust and SICSA.

Preprint submitted to Elsevier November 12, 2012

1. Introduction

1.1. Background on reductive proof search

It is not enough to study proof in principle; we may also want to prove things in practice. This means creating notions of derivation that are succinct and susceptible to automation. Propositional logic is decidable; it is when we introduce variables and quantification ∀ and so come to predicate logic, that things become interesting.1

In brief, this paper presents a new syntax and semantics within which to understand the very special treatment of variables in proof-search. What makes the syntax and semantics special is that we base it on finitely-supported name-symmetry—that is, on nominal terms [UPG04, Gab12b] and nominal sets [GP01, Gab11a].

To see how this works, we need to consider proof-search and some of the difficulties it presents, with special attention to quantifiers. We concentrate on notions of proof-search designed to work backwards from the desired goal towards tautologies; this is often called reductive, analytic, or backward proof-search. Examples include sequent [Gen35], tableau [Fit96], matrix [Wal90], and indexed-formula-tree systems [Die11]. An excellent survey by Fitting is in [DGHP99, Chapter 1]; see also the clearly-written textbooks by Fitting [Fit96] and Smullyan [Smu68].

The quantifier ∀ typically generates a pair of rules. Depending on whether the reader thinks in sequent or tableau style, this pair may be called left-intro and right-intro rules, or (δ∀) and (γ∀) rules (see [Fit96] or the discussion below) respectively. Intuitively:

1. left-intro/(γ∀) means “∀x.φ implies [r/x]φ for any r”, where here [r/x] is the usual capture-avoiding substitution of r for x.2 Call r a witness.

2. right-intro/(δ∀) means “[r/x]φ for some sufficiently generic r implies ∀x.φ”.

Both of these rules are subtle.

The left-intro/(γ∀) intuition has obvious potential for branching and we want to delay the choice of witness as long as possible. This motivates us to introduce a distinct class of variables into our syntax, variously called existential variables, meta-variables, proof-search variables, or (in tableaux) free variables. These are variables whose instantiation transforms the proof as a whole, and this instantiation is typically delayed as long as possible. Free/existential variables3 are written X in this paper and we use some new technology from nominal terms [UPG04] to handle them—but more on that later.

Concerning (δ∀): what should ‘sufficiently generic’ mean? The standard rule, familiar in some form to most readers, is to take a fresh entity variously called a fresh constant, a fresh variable, an eigenvariable, or parameter. Here is the (δ−∀) rule of Figure 3, corresponding to Fitting’s original free-variable4 δ-rule [Fit90, Section 7.4] but written in sequent style:

Γ ⊢ψ, ∆ (x fresh for Γ, ∆) Γ ⊢∀x.ψ, ∆

But this rule is not efficient. A concrete discussion of why, with examples and ref-erences, is in Subsection 3.2.6. For this Introduction we merely note the intuition that x is unnecessarily generic; by just choosing x ‘completely fresh’ we do not record—and so cannot take advantage of—information present in the sequent about exactly what variables exist at the moment x was created.

An industry exists in devising rules to prove ∀a.φ more efficiently:

• Fitting’s free-variable δ-rule from the first edition of his book [Fit90, Section 7.4].

• Its ‘liberalised’ version δ+, introduced by Hähnle in [HS94] and also treated in the second edition of Fitting’s book [Fit96, Section 7.4].

• The rule δ++ from [BHS93] (which also includes a particularly nice exposition).

• The rule δ∗ [BF95]. This had some errors: one was corrected at the TABLEAUX conference by the authors; another was treated later in [CNA07, Subsection 5.3].

• The rule δ∗∗ [CA00]. This had an error which was discussed and corrected in [CNA07, Subsection 5.4].

• The rule δε [GA99, Section 4.1].

Efficiency gains arise from fine-grained analysis of name-generation and name-dependency. Generally speaking, the more parsimoniously a rule can generate names and record de-pendencies, the more efficiently it can be implemented.

These speedups can be significant, and the literature above is computationally well-motivated. The (δ+) of [HS94] allows at least an exponential speedup relative to (δ−) [Fit96], and the (δ++) of [BHS93] allows a further exponential speedup relative to (δ+). For more discussion see [BF95, Section 3].

Names are also what nominal techniques, developed by the first author and others, were created to study. So in this paper we turn our nominal toolkit to model the variable behavior typically seen in reductive proof-search.

Just to be clear: this paper is not about creating a more efficient proof-search system and we make no particular claims to efficiency. However, the syntax and semantics are new and throw a new light on the problem of variables in proof-search, and their semantics.5

Whether this will lead to better algorithms is an open question, but it may well lead to shorter and better mathematical proofs (and perhaps even contribute to avoiding mistakes in algorithms).

We will use two nominal tools: permissive-nominal terms from [DGM10] (a simplification of the nominal terms from [UPG04]) and the nominal sets semantics from [GP01]. For surveys of the applications of permissive-nominal terms and nominal sets to logic and specification in general, see two survey papers [Gab11a, Gab12b].

This paper will be self-contained; for background theory we include pointers to the literature. We will consider a non-Skolemising version of Fitting’s original free-variable δ-rule (see (δ−) in Figure 3) and a novel (δX) rule (see Figure 5). Both rules are expressed using a nominal syntax.

1.2. Summary of the paper

... in a paragraph: rule (δ−∀) in Figure 3 is analogous to the usual ∀-right rule. It generates a fresh symbol (atom, in this paper). As mentioned above, it turns out that this rule (in combination with the other rules) is inefficient for practical proof-search. Rule (δX∀) in Figure 5 is an example of a ‘liberalised δ-rule’, of which many have appeared in the literature as cited above. Rule (δX∀) introduces another kind of variable X. In fact X is existential, in the sense that X can be instantiated globally throughout a derivation (see e.g. Subsection 3.2.2). However, (δX) also adds X to a maximisation condition X↑[a]φ (Definition 4.5). Maximisation conditions allow us to restrict the domain over which X can range. Using negation we can (see Subsection 6.2) restrict X to range over elements that try to falsify φ[a↦→X], giving X a universal flavour with respect to φ[a↦→X].

We will see in this paper that nominal syntax and semantics can simplify material; they can also lead to new ideas. For instance, the contents of this paper are a simplification of [Wir04], which is 102 pages long; see also [Wir11].6 This paper is not just a repeat of the previous work and the nominal terms syntax, the maximising hypersequent syntax and rewrites, and nominal semantics, are different, and the semantics in particular is very different indeed. A qualitative change in complexity is apparent: the nominal syntax, semantics, and presentation are simpler.

Conversely, through a study of reductive proof-search we obtain some new and interesting ‘nominal’ constructions. These include:

• Application of nominal unknowns X from [UPG04, DGM10, Gab12b] directly to proof-search. In nominal unification from [UPG04], unknowns had an existential flavour and ranged over nominal terms. This paper takes the idea much further, making unknowns range over witnesses to higher-order logic predicates. We suspect that this far from exhausts the expressivity and flexibility of permissive-nominal terms, and the application in this paper may be prototypical for many other applications not yet considered. For compatibility with the tableau literature, we call unknowns (free) variables in this paper.

• Interpretation of existential variables, and of universal variables by using maximisation conditions in Section 4. To model what happens in the tableau systems, we use a mechanism (maximisation condition) which can make an existential unknown (free variable) play the role of a universal parameter for a specific predicate. This is entirely new, from a nominal perspective.

• The construction of the functional model in Subsection 7.2. This construction has been known to the first author since 2006, and was first used in [DG10, DG12a]. See also [DG12b].

1.3. Map of the paper

The section and subsection titles should be fairly self-explanatory but it might help to gather up some exposition in an itemised list:

• Subsection 2.1 establishes some of the basic pieces needed for the rest of the paper. This only makes sense in the context of what we will then do with it.

• Nominal terms are discussed in Subsection 2.2. By then we can write down formulae (terms of type o). The term language is just that of higher-order logic, but enriched with proof-search variables which we write X and which are, technically, unknowns from nominal terms.

• In Subsection 2.3 we consider ‘free atoms of’ and α-equivalence for atoms a. This is off-the-shelf from the theory of permissive-nominal terms, but if the reader has not seen this before it will be new because the nominal terms theory of α-equivalence is actually rather powerful, being based on permutations (symmetry).

• In Subsection 2.4 we introduce instantiation of proof-search variables X. Again, this is off-the-shelf from permissive-nominal terms, but again the uninitiated reader will have to pay attention. We illustrate the definitions with plenty of examples.

• We now have enough to define sequents in Subsection 3.1, followed by detailed examples in Subsection 3.2.

• Section 4 mirrors Section 3 but now we treat maximising hypersequents. It is probably fair to say that this is where the material starts to become intrinsically difficult rather than just potentially unfamiliar. Again, we give plenty of examples.

• Section 5 builds the denotation needed to give nominal semantics to the material up to this point: Subsection 5.1 introduces necessary background on nominal sets. The difference from ordinary sets is that atoms and their permutations are taken as primitive so that atoms and binding in the syntax get translated directly to corresponding structure on the nominal sets. Subsection 5.2 takes this further to model the full structure of terms.

• By this point, in Section 6 we have everything we need to interpret sequents and prove soundness of the proof-search ‘algorithms’ from Sections 3 and 4. As is often the case, with the right definitions in place this is not actually particularly hard. But it is the crux of the paper.

• Section 7 builds two models by hand—one model out of syntax, another model out of ‘ordinary’ sets. The interest here is to prove that non-trivial models of the preceding material exist. We can also adapt other work to give yet more models, but the models we consider here are sufficient to make the point and to illustrate the nominal semantics.

• Section 8 considers choice, partly because choice is interesting, partly because much other literature appeals to it, and partly because nominal techniques have a somewhat undeserved reputation for causing difficulty with choice. So, we verify explicitly and by hand that it works, and how it works.

2. Nominal terms

2.1. Atoms, variables, types, and permutations

We describe the elements from which we build our syntax. This is background material; the reader who wants to understand through examples can look at Example 2.18 (example terms) and Subsection 3.2 (example derivations).

Broadly speaking: types are the simple types of higher-order logic with base types for data; atoms a are universal variables; variables X are existential variables; constants are as usual; and permutations are as standard for nominal techniques and represent the symmetry implicit in α-conversion and the ‘freshness side-conditions’ typical of reasoning with α-conversion.

Extensive discussion of these definitions (and why they are generally useful) can be found in [GP01, UPG04, Che05, BU07, Gab11a, Gab12b].

Definition 2.1

Fix a set of base types τ. Define types α inductively by:

α ::= o | τ | α →α
Remark 2.2

In Definition 2.1 o will be a type for truth-values (see the distinguished constants in Definition 2.8). The base types τ are for data, like numbers N. α →β is a function type.

For now these types are just formal elements of an inductively defined set. It is up to us to give them meaning consistent with these intuitions; see for instance the typing rules for terms in Figure 1, and the map from α to a nominal set ⟦α⟧ in Definition 5.12.

A minimal interesting set of types would assume just types o (truth-values), i (individ-uals, to be populated by our favourite data), and function-types. The reader who prefers their types minimal can assume that this is all we have, and no harm will come of it.

Definition 2.3

For each type α fix a disjoint countably infinite set Aα of atoms of that type and define A = ⋃α Aα.

a, b, c, . . . will range over distinct atoms (we call this the permutative convention). Write type(a) for the type of a, so that a ∈Atype(a).

Definition 2.4

Let S, T, and U range over finite sets of atoms, not necessarily all of the same type. So for instance if type(a) = α and type(b) = β then S might be equal to {a, b}.

For each S and type α fix a disjoint countably infinite set of variables Vα,S and define V = ⋃α,S Vα,S. X, Y, Z will range over distinct variables.7

If X ∈Vα,S write pms(X) for S and call this the permission set of X, and write type(X) for α and call this the type of X.

Remark 2.5

We pause to discuss atoms, variables, and permission sets specifically with regards to the literature on proof-search.

• Atoms a are universal variables; in proof-search ∀a.φ gets transformed to φ where a is fresh. See (δ−∀) in Figure 3. In the literature this kind of structure is also called a parameter or eigenvariable. This is the kind of entity that is introduced by the usual (∀R) rules of sequent systems.

• Variables X are existential variables, ‘Skolemised’ over the atoms in their permission set; in proof-search ¬∀a.φ gets transformed to ¬φ[a↦→X]. See (γ¬∀) in Figure 3. This corresponds to the dummy variable of [Pra60, Pra83] and [Kan63] and to the free variable of [Fit96] and footnote 11 of [Pra60], to the meta-variable of planning and constraint solving, and to the free γ-variable of [Wir04].

Atoms enter nominal techniques as set-theoretic urelemente in Fraenkel-Mostowski set theory; for detailed historical notes see [Gab11a] (especially Remark 2.22). They were originally used to represent atomic variable symbols of abstract syntax with binding [GP01]. Atoms are ‘names of which nothing else is known’—just like ‘parameters’ in proof-search. Also like parameters, atoms can be generated fresh (cf. the N-quantifier [GP01, Gab11a]). So structurally, atoms in Fraenkel-Mostowski sets and parameters in proof-search are similar, and using one to model the other makes sense.

One feature that our system has over parameters, eigenvariables, dummy variables, and so on as cited above, is that permissive-nominal terms are embedded in a broader semantic theory of nominal techniques [Gab11a, Gab12b]. This broader theory is the tool that we will use to build our semantics for the quantifier rules and proof-search.

Permutations in nominal techniques are how we express that atoms are symmetric up to permutative renaming. Permutations will feature in the syntax (Definition 2.10) and also in the models (Subsection 5.1):

Definition 2.6

A permutation is a bijection on A such that:

• a ∈Aα if and only if π(a) ∈Aα (so π preserves types).

• nontriv(π) = {a | π(a) ≠ a} is finite.

Notation 2.7

The following notation may be useful:

• Write id for the identity permutation such that id(a) = a for all a.

• Write π′ ◦π for composition, so that (π′ ◦π)(a) = π′(π(a)), and write π-1 for inverse, so that π-1 ◦π = id = π ◦π-1.

• Suppose a, b ∈Aτ for some τ. Then write (a b) for the swapping8 mapping a to b, b to a, and all other c to themselves, and take (a a) = id. As a matter of convenience, wherever we write a swapping this comes with an assumption that the two atoms have the same type.

2.2. Terms and types of terms

The terms here are a species of permissive-nominal term [DGM10] which simplify nominal terms from [UPG04] by eliminating freshness contexts. For intuitions of terms, see Example 2.18.

Definition 2.8

Fix a set of constants, to each of which is associated a type. f, g, h will range over distinct constants; we write type(f) for the type of f.

Assume the following distinguished constants:

⊤: o ¬ : o →o ∧: o →o →o ∀α : (α →o) →o
Remark 2.9

At the moment the distinguished constants above are just formal symbols, which become part of the syntax of terms in Definition 2.10. What makes them ‘distinguished’ is how they are interpreted:

• The rewrite rules in Figure 3 give the distinguished constants operational significance in a proof-search framework. So for instance, the rules (α¬∧) and (β∧) make ∧ behave like a conjunction.

• The nominal algebra axioms in Figure 8 given the distinguished constants significance in a preorder. The axioms make, for instance, ∧ behave like a least upper bound in the preorder.

(Figures 3 and 8 use syntactic sugar from Notation 2.15.)

So the significance of Definition 2.8 is that Definition 2.10 is not just a simply-typed λ-calculus with existential variables (the X)—it is a syntax for higher-order logic with nominal variables.

Definition 2.10

Define (permissive-nominal) terms inductively by:

r ::= a | π·X | f | r′r | [a]r

Above, π·X is a formal pair of a permutation π and a variable X; we discuss this in Remark 2.11.

We let r, s, t range over terms. As is standard, r1r2 associates to the left (so r1r2r3 means (r1r2)r3).

Remark 2.11

We briefly run through the parts of Definition 2.10.

• a is an atom and is discussed in Remark 2.5.

• X is a free or existential variable. As standard for nominal terms [UPG04] we do not inject X directly into the term syntax; X becomes a term only together with a permutation π. We call the pair π·X a moderated variable. We may write id·X just as X (Notation 2.15), but there remains a formal distinction between ‘X the variable’ and ‘id·X the permissive-nominal term’. This moderation is important for the permissive-nominal terms theory of α-equivalence; see Remark 2.14 and Example 2.24.

• f is a constant; examples of constants are in Definition 2.8.

• r′r is an application, and

• [a]r is an abstraction.

Example terms follow shortly in Example 2.18, after we have built a typing relation. First, we discuss why atoms are not the same thing as constant symbols:

Remark 2.12 (Atoms are not constants).

Atoms are not constant symbols. The best way to understand this is in the models; models are subject to a symmetry group action permuting atoms, and atoms get translated from the syntax to the denotation in specific ways. In contrast, there are fewer restrictions on how constants are interpreted.

So note in Definition 5.27 how atoms, permutations, and atoms-abstractions get translated directly to corresponding semantic notions which are assumed as primitive in the model. A constant symbol is just interpreted by some element of the model. No special symmetry properties are assumed.

The term [a]r only makes sense because the interpretation of a in the model is specific in such a way that atoms-abstraction [a]- has a specific meaning. It makes no sense to talk about [f]r because there is no restriction on how f is interpreted.

Remark 2.13 (Permissive-nominal syntax).

For the reader familiar with nominal terms, note that the syntax of Definition 2.10 is permissive-nominal [DGM09b, DGM09a, DGM10]. Freshness assertions like a#X are replaced with permission sets (Definition 2.4) and assertions like a ∉ pms(X).

In this paper permission sets happen to be finite.

In Definition 2.10 we also assume a pairing operator rs. We call this application, and Figure 2 defines a relation =αβη which gives it βη behaviour. Thus, atoms-abstraction and application will behave like λ-abstraction and application (with existential variables), up to =αβη.

This is orthogonal to the usual theory of nominal terms and permissive-nominal unification. We also have a notion of α-equivalence =α and we are free to ignore the βη axioms and =αβη—and the type system, if we like—in which case the permissive-nominal syntax up to =α is standard.

So in this paper we do not consider unification up to =α, but if we wished to (perhaps for an implementation) then the permissive-nominal unification algorithms could be used off-the-shelf.

Remark 2.14 (Why moderated variables?).

For the reader unfamiliar with nominal terms, we briefly and intuitively discuss why variables need to be moderated as π·X.

It is not unusual to see quotes of the following form in informal practice:

Consider a λ-term λx.t and a variable y not free in t. Then λx.t is α-equivalent to

λy.(t[y/x]).

In a nutshell, (permissive-)nominal terms give a formal syntax to the informal quote above. The role of t (a meta-variable ranging over terms) is played by the variable X (called an unknown in [UPG04, DGM10]). The role of x and y (object-level variables) is played by atoms a, b (actually identified with urelemente in Fraenkel-Mostowski set theory—but we do not have to care about that).

But that is not enough. We also need to model t[y/x]. That is handled by the moderation (b a)·X where b ∉ pms(X). The permission set describes the free atoms of terms for which X may be instantiated, so if b is not permitted in X then (b a) has the value of “replace a in whatever term X becomes, with b”, which models t[y/x] which has the value “replace x in whatever term t is, with y”.

Now the reader might ask why we use permutations (b a) instead of atoms-renamings [b/a]. The answer is that permutations form a group, are invertible, and have better mathematical and computational properties. More on this in the Conclusions in Subsection 9.2.

Given that, we can model the quote above as follows:

Consider a variable X with b ∉ pms(X). Then [a]id·X =α [b](b a)·X.

That is why we need moderated variables. See Examples 2.18 and 2.24, in particular part 2 of Example 2.24.

Notation 2.15

We may use syntactic sugar as follows:

• We may write ∧rs as r ∧s, and ∀α([a]r) as ∀a.r, and fr as f(r).

• We may write id·X just as X.

• We may write ([a]r)s as r[a↦→s].

• We may write r ∨s for ¬(¬r ∧¬s) and r ⊃s for ¬r ∨s and ∃a.r for ¬(∀α[a]¬r).

In general, we will be very lax about ∨, ⊃, and ∃. Technically, they are not primitive, but this is purely a design choice to reduce the number of cases in proofs; we do not really care since it will always be clear and standard how to expand to ⊥, ∧, and ∀.

Definition 2.16

Define a typing relation r : α inductively by the rules in Figure 1.

Here and elsewhere, we put side-conditions of derivation rules in brackets.

Notation 2.17

If r : o we may call r a formula. We let φ, ψ, and χ range over formulae.

It is clear from the typing rules in Figure 1 that a : α (the term a) has type α if and only if type(a) = α, and similarly f : α if and only if type(f) = α and id·X : α (or X : α, using our syntactic sugar of writing id·X as just X) if and only if type(X) = α. We may therefore be lax about the distinction between ‘type(x) = α’ and ‘x : α’, where x is an atom, constant, or variable. We will usually prefer x : α, since it is shorter.

(type(a) = α) a : α(type(X) = α) π·X : α(type(f) = α) f : αr : β →α s : βrs : αr : α a : α′[a]r : α′ →α
Figure 1: Typing rules for terms
Example 2.18

Suppose a base type τ and atoms a and b of type τ. Suppose constants P : τ→o and Q : τ→o. Finally, suppose a variable X : o and an atom c : o. Then here are some example terms:

• a : τ. Intuitively, this term represents ‘an assumption/datum called a, of type τ’.

• ∀a.(P(a) ∧ Q(a)) : o. Intuitively, this formula represents ‘for all a, P(a) and Q(a)’.

• ∀a.c : o. Intuitively, this formula represents ‘for all a, c’ (which is logically equivalent to just ‘c’).

• ∀a.X : o. Intuitively, this formula represents ‘for all a, the goal X holds’. This X has an existential flavour, and we are supposed to instantiate it. Now ∀a.X is not equivalent to X because, as we shall see, instantiation of X (unlike substitution on a or c) may be capturing. Only the atoms in pms(X) may be captured. To see this happen in example derivations, see Subsection 3.2.

2.3. Free atoms and variables, alpha- and beta-equivalence

Definition 2.19

If A is a set of atoms define π·A = {π(a) | a ∈A}.

Definition 2.20

Define a permutation action π·r and fa(r) the free atoms of r and fv(r) the free variables of r by:

π·a = π(a) π·(π′·X) = (π ◦π′)·X π·f = fπ·(r′r) = (π·r′)(π·r) π·[a]r = [π(a)]π·rfa(a) = {a} fa(π·X) = π·pms(X) fa(f) = ∅fa(r′r) = fa(r′) ∪fa(r) fa([a]r) = fa(r) \ {a}fv(a) = ∅ fv(π·X) = {X} fv(f) = ∅fv(r′r) = fv(r′) ∪fv(r) fv([a]r) = fv(r)

Lemma 2.21 notes some easy basic properties of permissive-nominal terms:

Lemma 2.21

1. π·(π′·r) = (π ◦π′)·r and id·r = r (the permutation action is a group action).

2. fa(π·r) = π·fa(r) (free atoms commutes with the permutation action, or in the terminology of part 2 of Definition 5.10, it is equivariant).

Proof

By routine inductions on r. For details see [DGM09a, Lemmas 15 and 16].9End of proof

(stxα) a, b ∉fa(r) ⇒ (b a)·r =α r(stxa) a[a↦→t] =αβη t(stx#) a ∉fa(r) ⇒ r[a↦→t] =αβη r(stxapp) (r′r)[a↦→t] =αβη (r′[a↦→t])(r[a↦→t])(stx[]) c ∉fa(t) ⇒ ([c]r)[a↦→t] =αβη [c](r[a↦→t])(stxid) r[a↦→a] =αβη r(stxη) a ∉fa(r) ⇒ [a](ra) =αβη r
Figure 2: Rules for αβη-equivalence
Definition 2.22

A congruence is a relation R on terms such that r R r′ and s R s′ imply [a]r R [a]r′ and rs R r′s′. Let α-equivalence be the least congruence =α that includes (stxα) from Figure 2. Let αβη-equivalence be the least congruence that includes (stxα), (stxa) to (stxid), and (stxη) from Figure 2.

Lemma 2.23

α-equivalence can be characterised as the least relation such that:

• a =α a and f =α f.

• If π(a) = π′(a) for every a ∈ pms(X) then π·X =α π′·X.

• If r =α r′ and s =α s′ then rs =α r′s′ and [a]r =α [a]r′.

• If (b a)·r =α s and b ∉ fa(r) then [a]r =α [b]s.

The characterisation of =α in Definition 2.22 follows [GM07, GM09a]. Lemma 2.23 is modelled on the equivalent definition from [UPG03, UPG04].

Example 2.24

1. [a]a =α [b]b.

2. If b ∉ pms(X) then [a]X =α [b](b a)·X.

3. If a, b ∈ pms(X) then (((((((( [a]X =α [b](b a)·X is not the case.

4. ([a]a)t =αβη t and ([a]b)t =αβη b. This is just (stxa) and (stx#).

5. However, if a ∈ pms(X) then ((((((( ([a]X)t =αβη X is not the case. Even though a does not occur syntactically in X, it is considered to be ‘free’ in X if a ∈ pms(X). This is because X might be instantiated to a; see Subsection 2.4.

Proposition 2.25

If r : α and r =αβη r′ then r′: α.

2.4. Variable instantiation

The variables X and Y are variables in our syntax and they can be instantiated. However, they are associated with a permission set which as we shall see in Subsection 3.2.5 is important for soundness. We briefly consider the theory of instantiation for variables:

Definition 2.26

An instantiation θ is a function from variables to terms such that:

• If X : α then θ(X) : α.

• fa(θ(X)) ⊆ pms(X). If r : type(X) and fa(r) ⊆ pms(X) then let [X:=r] be the instantiation mapping X to r and all other Y to id·Y .

Definition 2.27

Define an instantiation action on terms by:

aθ = a (π·X)θ = π·(θ(X)) fθ = f(r′r)θ = rθ(r′θ) ([a]r)θ = [a](rθ)
Remark 2.28

It is important to realise that instantiation is capturing for atoms in pms(X). For instance, suppose a ∈ pms(X) and b ∉ pms(X). Then:

• ([a]X)[X:=a] = [a]a. The a in the instantiation [X:=a] has been captured by the [a]X.

• ([b]X)[X:=a] = [b]a.

• It is impossible to even ask what ([b]X)[X:=b] is equal to because [X:=b] is not an instantiation, since b ∉ pms(X). So b ∉ pms(X) cannot be captured by an instantiation [X:=b], because that instantiation does not exist.

• Also, recall from Example 2.24 that [b](b a)·X =α [a]X. By construction,

([b](b a)·X)[X:=a] = [b](b a)·a = [b]b =α [a]a.

That is, the choice of representative of [a]X does not matter for capture to occur.

We can only substitute for X a term whose free atoms are in the permission set of X. For instance, if pms(X) = {a} and a : α and b : α and X : α then [X:=a] is an instantiation and [X:=b] is not.

Think of X : α as ranging over terms of type α with free atoms in pms(X). This latter restriction matters for soundness: see Subsection 3.2.5.

Proposition 2.29 notes some familiar properties of permissive-nominal terms:

Proposition 2.29

1. fa(rθ) ⊆ fa(r).

2. π·(rθ) = (π·r)θ.

3. If r =α s then π·r =α π·s and rθ =α sθ.

4. If r =αβη s then π·r =αβη π·s and rθ =αβη sθ.

Proof

1. By a routine induction on r. The interesting base case is π·X, where we use our assumpion that fa(θ(X)) ⊆ pms(X) and part 2 of Lemma 2.21.

2. By a routine induction on r. The interesting base case is π′·X, where we use part 1 of Lemma 2.21.

3. By inductions on the derivation of r =α s. The interesting case is rule (stxα). We use parts 1 and 2 of this result, and Lemma 2.21.

4. By an easy induction on the derivation of r =αβη s, as for =α.End of proof

3. Sequents and hypersequents

We now use hypersequents (Definition 3.1) to define a rewrite system for proof-search.

The word hypersequent follows Avron [Avr96, Avr91], and our hypersequents are essentially identical to the ones he considered—see the first definition of Section 2 of [Avr91]—though the use we put hypersequents to here is different.10

A hypersequent is intuitively a conjunction of disjunctions of formulae. In Figures 3 and 4 we define a rewrite system which, intuitively, reduces hypersequents to simpler hypersequents.

If we squint, then we recognise the rules in Figures 3 and 4 as the usual sequent rules [GTL89, Subsection 5.1.5]. They are just written in a ‘disjunctive’ instead of a ‘sequent’ form: (γ¬∀) corresponds to (∀L); (δ−∀) corresponds to (∀R); (α¬∧) corresponds to (∧L); (β∧) corresponds to (∧R); (αEM) corresponds to the axiom rule; (ᬬ) to the negation rules; and so on. The difference is that this presentation is somewhat better for the mechanics of proof-search.

If we squint again, then the hypersequent rewrite rules are an abstract rendering of a tableau derivation system (specifically, a set-labelled tableau system). For more on tableaux see [Smu68] or [DGHP99].

So Definition 3.1 seems to be quite a nice compromise between the worlds of sequents and tableaux, and the reader can view our hypersequent rewrite system as either a slightly mangled sequent system, or a rather inefficiently-presented set-labelled tableau system, depending on which set of ideas is most familiar, and no harm will come of it. Example derivations are given in Subsection 3.2.

3.1. The basic definition

Definition 3.1

• A sequent Φ is a set of formulae φ1 ∨. . . ∨φn. Φ will range over sequents.

• A hypersequent H is a set of sequents Φ1 ∧. . . ∧ Φm. H will range over hypersequents.

The symbol ∧ looks like ∧ and ∨ looks like ∨, and indeed they are interpreted equally (Definition 6.1). However, ∧ and ∨ are part of the structure of hypersequents, not part of the structure of formulae.11

In Definition 3.3 we give rewrite/derivation rules for converting a formula into an equivalent hypersequent.

Notation 3.2

Write fa(φ1 ∨. . . ∨φn) = ⋃i fa(φi) and fa(Φ1 ∧. . . ∧ Φm) = ⋃i fa(Φi).

Definition 3.3

We define schemas of hypersequent pairs in Figure 3.

The rules determine a rewrite system on hypersequents, where H ⇒H′ when H H′ is an

instance of a rule(-schema). We call a sequence of such rewrites a derivation.

(¬¬φ ∨Φ) ∧H(ᬬ)(φ ∨Φ) ∧H(⊤∨Φ) ∧H(α⊤)H(φ ∨¬φ ∨Φ) ∧H(αEM)H(φ ∨Φ) ∧H (φ =αβη φ′)(=αβη)(φ′ ∨Φ) ∧H(¬(φ′ ∧φ) ∨Φ) ∧H(α¬∧)(¬φ′ ∨¬φ ∨Φ) ∧H((φ′ ∧φ) ∨Φ) ∧H(β∧)(φ′ ∨Φ) ∧(φ ∨Φ) ∧H(¬∀a.φ ∨Φ) ∧H (r : type(a))(γ¬∀)(¬φ[a↦→r] ∨¬∀a.φ ∨Φ) ∧H(∀a.φ ∨Φ) ∧H (a ∉fa(Φ))(δ−∀)(φ ∨Φ) ∧H
Figure 3: Rules for rewriting hypersequents
((φ′ ∨φ) ∨Φ) ∧H(α∨)(φ′ ∨φ ∨Φ) ∧H((φ′ ⊃φ) ∨Φ) ∧H(α⊃)(¬φ′ ∨φ ∨Φ) ∧H(¬(φ′ ∨φ) ∨Φ) ∧H(β¬∨)(¬φ′ ∨Φ) ∧(¬φ ∨Φ) ∧H(¬(φ′ ⊃φ) ∨Φ) ∧H(β¬⊃)(φ′ ∨Φ) ∧(¬φ ∨Φ) ∧H(∃a.φ ∨Φ) ∧H (r : type(a))(γ∃)(φ[a↦→r] ∨∃a.φ ∨Φ) ∧H(¬∃a.φ ∨Φ) ∧H (a ∉fa(Φ))(δ−¬∃)(¬φ ∨Φ) ∧H
Figure 4: Derived rules for ∨, ⊃, ∃ in hypersequents
Remark 3.4

Recall from Notation 2.15 that we treat ∨, ⊃, and ∃α as syntactic sugar. For the reader’s convenience in Figure 4 we give derived rules for them—we will use them without comment, just as is convenient.

Remark 3.5

We fix no choice of reduction strategy. We tend to write the ‘active formula’ at the head of the hypersequent in Figures 3 and 4 and in the examples of Subsection 3.2, but this is just a convention. Sequents and hypersequents are sets, they are not ordered, and hypersequent rewriting can rewrite any sequent within a hypersequent,

3.2. Example derivations

We now give a few simple but illustrative example derivations. We may elide rule (=αβη). The object of the exercise is to rewrite the hypersequent to ∅, the empty hypersequent. A precise semantic justification for why this is ‘good’ is given in Theorems 6.6 and 6.18.

3.2.1. Derivation of (∀a.φ)⊃φ[a↦→r].

This corresponds to (∀L) (forall left-introduction) and to part 1 of Lemma 5.23:

(∀a.φ)⊃φ[a↦→r] =⇒(α⊃)¬∀a.φ ∨φ[a↦→r] =⇒(γ¬∀)¬φ[a↦→r] ∨¬∀a.φ ∨φ[a↦→r] =⇒(αEM)∅

Here and below ∅ is the empty hypersequent.

It is not hard to transform this derivation into a sequent derivation of (∀a.φ)⊃φ[a↦→r]. The sequent rules are (⊃R), (∀L), and (Axiom) corresponding precisely to (α⊃), (γ¬∀), and (αEM). It is not hard to do the same for the examples that now follow.

3.2.2. Forall implies Exists

We derive the formula (∀a.P(a))⊃∃a.P(a) as follows:

(∀a.P(a))⊃∃a.P(a) =⇒(α⊃)¬∀a.P(a) ∨∃a.P(a) =⇒(γ∃), pms(X)=∅P(X) ∨¬∀a.P(a) ∨∃a.P(a) =⇒(γ¬∀), pms(Y )=∅¬P(Y ) ∨P(X) ∨¬∀a.P(a) ∨∃a.P(a)

We implicitly assume above that type(X) = type(Y ) = type(a), and we will make similar implicit assumptions in the examples below. There will always be one clear correct choice of type for the variables we introduce in these examples, and other choices will clearly lead to ill-typed syntax.

We also explicitly choose pms(X) = pms(Y ) = ∅. This is just because we have to choose some permission sets of X and Y .

If we instantiate X to Y then ¬P(X) and P(X) would match the premises of (αEM).

Remark 3.6

The instantiation of X to Y in the derivation above is not a rewrite rule. It is an operation transforming one complete derivation (like the one above this paragraph) into another complete derivation (like the one below this paragraph). The general case is treated in Proposition 6.25. Sometimes it is possible to extend the instantiated derivation, and sometimes not; we will see examples of both cases.

We obtain another valid derivation and in this case we can extend it as follows:

(∀a.P(a))⊃∃a.P(a) =⇒(α⊃), (γ∃), pms(Y )=∅P(Y ) ∨¬∀a.P(a) ∨∃a.P(a) =⇒(γ¬∀)¬P(Y ) ∨P(Y ) ∨¬∀a.P(a) ∨∃a.P(a) =⇒(αEM)∅

3.2.3. Forall implies Exists (again)

Another derivation is possible, as follows:

(∀a.P(a))⊃∃a.P(a) =⇒(α⊃), (γ¬∀), pms(Y )=∅¬P(Y ) ∨¬∀a.P(a) ∨∃a.P(a) =⇒(γ∃), pms(X)=∅P(X) ∨¬P(Y ) ∨¬∀a.P(a) ∨∃a.P(a)

Again we instantiate X to Y and use (αEM).

3.2.4. A derivation that fails because atoms are distinct

We try to derive (∃a.P(a))⊃∀a.P(a). As standard and as expected, we will fail:

(∃a.P(a))⊃∀a.P(a) =⇒(α⊃), (δ−¬∃)¬P(a) ∨∀a.P(a) =⇒(=αβη)¬P(a) ∨∀b.P(b) =⇒(δ−∀)¬P(a) ∨P(b)

Recall that we will usually elide (=αβη), but for clarity just this once we wrote it out in full.

Now we are stuck. We cannot use (αEM) because a and b are distinct.

3.2.5. A derivation that fails because of permission sets

We have not included equality in our system, but suppose we did, with a rule (α≈) allowing us to delete sequents with (r≈r) (similar to (α⊤)).

We derive ∀a.∃b.a≈b (and succeed):

∀a.∃b.a≈b =⇒(δ−∀)∃b.a≈b =⇒(γ−∃)a≈a ∨∃b.a≈b =⇒(α≈)∅

Now we try to derive ∃a.∀b.a≈b:

∃a.∀b.a≈b =⇒(γ−∃), pms(X)=∅∀b.X≈b ∨∃a.∀b.a≈b =⇒(δ−∀)X≈b ∨∃a.∀b.a≈b

Now we are stuck. We cannot use (α≈) because X is not the same term as b. We cannot globally transform the derivation to instantiate X to b because b ∉ pms(X) so that [X:=b] is not an instantiation (Definition 2.26). It would not help to try to re-run the derivation with an X′ with pms(X′) = {b} because (δ−∀) would just force us to choose a fresh b′ ∉ pms(X′).

For an example without equality, try to derive (∀a.∃b.P(a, b)) ⊃∃b.∀a.P(a, b). The attempted derivation (which fails) is a little longer, but illustrates the same point.

Here, the nominal support restriction on instantiations in Definition 2.26 reflects an important soundness criterion: variables can only vary over terms with free atoms they ‘know about’, and must not vary over terms with free atoms that were subsequently generated fresh by a (δ−∗) rule, and thus that they do not ‘know about’.

3.2.6. Plato’s principle

Plato’s principle [MV95, Subsection 3.3] is represented in our syntax by the formula ∃a.((∃b.P(b))⊃P(a)).

This can be derived as follows, where we elide rule (=αβη):

∃a.((∃b.P(b))⊃P(a)) =⇒(γ∃), pms(X)=∅(∃b.P(b))⊃P(X) ∨∃a.((∃b.P(b))⊃P(a)) =⇒(α⊃)(¬∃b.P(b)) ∨P(X) ∨∃a.((∃b.P(b))⊃P(a)) =⇒(δ−¬∃)¬P(b) ∨P(X) ∨∃a.((∃b.P(b))⊃P(a)) =⇒(γ∃), pms(Y )={b}, (α⊃) P(Y ) ∨¬P(b) ∨P(X) ∨(¬∃b.P(b)) ∨∃a.((∃b.P(b))⊃P(a))

Now if we instantiate Y to b then P(b) and ¬P(b) would match the premises of (αEM). So we instantiate Y in the derivation so far and extend as follows:

∃a.((∃b.P(b))⊃P(a)) =⇒(γ∃), pms(X)=∅(∃b.P(b))⊃P(X) ∨∃a.((∃b.P(b))⊃P(a)) =⇒(α⊃)(¬∃b.P(b)) ∨P(X) ∨∃a.((∃b.P(b))⊃P(a)) =⇒(δ−¬∃)¬P(b) ∨P(X) ∨∃a.((∃b.P(b))⊃P(a)) =⇒(γ∃), (α⊃) P(b) ∨¬P(b) ∨P(X) ∨(¬∃b.P(b)) ∨∃a.((∃b.P(b))⊃P(a)) =⇒(αEM)∅

Note how we apply (γ∃) twice; the first time to get ¬P(b), and the second time to get P(b). This is because (δ−¬∃) introduces b fresh for pms(X)—just as (∀R) introduces a ‘fresh variable’. This is related to the issue that we touched on in Subsection 3.2.5.

The reader can find excellent expositions about just how inefficient (δ−) can be in [HS94, BHS93, CA00]. In the Introduction we noted that exponential and non-elementary speedups are possible with so-called ‘liberalised’ δ-rules. This motivates the (δX) rules, which we consider next in Section 4.

4. Maximising hypersequents

We now extend the hypersequents and hypersequent rewriting from Section 3 with maximisation conditions. These are subtle, so we provide plenty of exposition in Subsection 4.1 and example derivations follow in Subsection 4.2.

4.1. The basic definition

Definition 4.1

A primitive maximisation condition is a pair X↑[a]φ where X : α and a : α and φ : o such that fa([a]φ) ⊆ pms(X).

Remark 4.2

The intuition of X↑[a]φ is: take X to be a value making φ[a↦→X] true. We can read this as a weak form of choice—weak, since we do not necessarily assign the value a term in the syntax. The value is allowed to depend on the atoms in pms(X), and must not depend on any other atoms. Technically, we use nominal techniques to give ‘depends on’ a precise formal meaning: it means ‘has in its support’.

Example maximisers are in Example 4.9. The formal semantic interpretation of X↑[a]φ is the first equation of Definition 6.12; it interprets X↑[a]φ as (∃a.φ) ⊃φ[a↦→X]. This can be read as the following slightly more detailed rendering of the intuition of the previous paragraph: “If there exists a value making φ true, then X is one of those values”.

Definition 4.3

A set of primitive maximisation conditions C induces a relation ≺ on variables by letting ≺ be the least transitive relation such that

Y ≺X if (X↑[a]φ) ∈C and Y ∈fv(φ).12
Remark 4.4

Intuitively Y ≺X expresses that the value chosen for Y can influence the choice of maximiser for X—so we can read Y ≺X as the assertion “You need to fix the value for Y before you calculate a value for X”.

Definition 4.5

A maximisation condition is a set of primitive maximisation conditions C = (Xi↑[ai]φi)n 1 such that:

1. ≺ from Definition 4.3 is a well-founded strict partial order (a well-founded transitive irreflexive relation) on C.

2. C is functional, in the sense that X↑r ∈C and X↑s ∈C imply that r and s are syntactically identical.

Define dom(C) = {X1, . . . , Xn} and call this set the domain of C. We let C range over maximisation conditions.

Remark 4.6

In Definition 4.5 we insist that ≺ should be well-founded. This is used in Lemma 4.7, and in Proposition 6.17 where we use well-foundedness to ‘work our way up’ ≺ and so generate a maximiser. To see a concrete example of what goes wrong without well-foundedness see Subsection 4.2.3.

Lemma 4.7 is a technical result which is useful for Proposition 6.17. It makes Remark 4.6 formal, and illustrates how well-foundedness of ≺ controls the free variables of the predicates in the maximisation condition:

Lemma 4.7

Suppose C is a maximisation condition and ≺ is the well-founded strict partial order on variables induced by C. Then if X↑[a]φ ∈C and X is ≺-minimal in dom(C) then fv(φ) ∩ dom(C) = ∅.

Proof

If X ∈ fv(φ)∩dom(C) then X ≺X, contradicting strictness of ≺ (and indeed also well-foundedness of ≺ and ≺-minimality of X in dom(C)).

If Y ∈ fv(φ)∩dom(C) then Y ≺X and Y ∈ dom(C), contradicting ≺-minimality of X in dom(C).End of proof

Definition 4.8

A maximising hypersequent P is a pair C ⊢H of a maximisation condition and a hypersequent. We may write ∅⊢H just as H.

Example 4.9

In ordinary hypersequents, variables X have an existential flavour and atoms a have a universal flavour. This is why the (δ−∗) rules create a fresh atom—this is a fresh ‘universal’ variable.

A maximisation condition X↑[a]φ restricts X to range over elements making φ[a↦→X] as true as possible. Dually, a maximisation condition X↑[a]¬φ restricts X to range over elements making φ[a↦→X] as false as possible—so X↑[a]¬φ makes X behave like a universal variable (the words universal and existential are a useful intuition but they have their limits: see Remark 6.20 for discussion). We exploit this duality in rules (δX∀) and (δX¬∃) of Figures 5 and 6.

Let us consider some concrete examples of maximisers. These are based on the model which we build in Subsection 7.2, but we will sketch the technical details, which we hope will anyway be fairly self-explanatory:

1. Take φ to be a : o so that [a]φ is just [a]a, and take pms(X) = ∅. We use the model I from Subsection 7.2. There, truth-values are interpreted as ⟦o⟧ which is inhabited by maps from atoms-valuations ς, to the set {⊥, ⊤}. In symbols, valuations ς and truth-values have types

Πα(Aα→⟦α⟧) and Πα(Aα→⟦α⟧)→{⊥, ⊤}

respectively. The maximisation condition X↑[a]a restricts X to range over the following rather small set:

{λς.⊤}

This is not a very interesting example, since φ is so simple.

2. Now take φ to be a ∨b : o and take pms(X) = {b}. Then X↑[a](a ∨b) restricts X to be in the set

{λς.⊤, λς.if ς(b)=⊥then ⊤else ⊥}.

This is because there are two functions f on valuations ς, that examine only ς(b) and that make f(ς) ∨ς(b) true: either take f(ς) to be ⊤ always, or let f(ς) be the negation of ς(b). Both are valid maximisers.

3. Suppose (without writing out full definitions) we assume a type for numbers N, and a predicate for equality. Suppose a, b, X : N and pms(X) = {b}. Then X↑[a](a=b) restricts X to be equal to λς.ς(b). Also, X↑[a](a≠b) restricts X to be any one of the many functions mapping a valuation ς to an element of N\{ς(b)}.

4. Note that in the previous example, pms(X) does not have to be equal to {b}, though by Definition 4.1 it must be that b ∈ pms(X). If we ignore this and see what happens if we try to create a maximiser using X where b ∉ pms(X) then we see that no such thing exists: to make (X=b) (or (X≠b)) true, the meaning we give to X must depend on the value of ς at b.

Remark 4.10

The (δX) rules are descended from the liberalised δ-rule of [Wir04, page 14], which itself can be understood as a non-Skolemising version of (δ+) from [HS94], where instead of Skolemisation we use variable-conditions [Wir04]. Still, it is probably fair to say that the δX rules and maximisation conditions have an independent existence.

As we hope is now clear, our ‘maximisation condition’ is a kind of choice, but it is not a unique one. Thus in Example 4.9 we saw that many maximisers can exist for the same maximisation condition.

A perennial problem of Hilbert’s choice ϵa.φ is that expressions tend to explode exponentially as choices get nested; our syntax is less prone to that. We do not introduce choice ϵa.φ into the syntax or semantics, our maximisation conditions do not force a specific choice of maximiser in the semantics, and the syntax manages to remain relatively compact.

Later on in Section 5 onwards we will see how our system admits a semantics in nominal sets.

As a nice side-effect of this—and as was also the case in [Wir04]—we can accommodate both δ− and δX in a single syntax, and later on in a single semantics too. This gives us a convenient way of constrasting and understanding what different systems have in common and what sets them apart.

C ⊢(¬¬φ ∨Φ) ∧H(ᬬ)C ⊢(φ ∨Φ) ∧HC ⊢(⊤∨Φ) ∧H(α⊤)C ⊢HC ⊢(φ ∨¬φ ∨Φ) ∧H(αEM)C ⊢HC ⊢(φ ∨Φ) ∧H (φ =αβη φ′)(=αβη)C ⊢(φ′ ∨Φ) ∧HC ⊢(¬(φ′ ∧φ) ∨Φ) ∧H(α¬∧)C ⊢(¬φ′ ∨¬φ ∨Φ) ∧HC ⊢((φ′ ∧φ) ∨Φ) ∧H(β∧)C ⊢(φ′ ∨Φ) ∧(φ ∨Φ) ∧HC ⊢(¬∀a.φ ∨Φ) ∧H (r : type(a))(γ¬∀)C ⊢(¬φ[a↦→r] ∨¬∀a.φ ∨Φ) ∧HC ⊢(∀a.φ ∨Φ) ∧H(δX∀)C, X↑[a]¬φ ⊢(φ[a↦→X] ∨Φ) ∧H
Figure 5: Rules for rewriting maximising hypersequents
Definition 4.11

We define rewrites on maximising hypersequents in Figures 5 and 6. (δX∀) and (δX¬∃) are subject to the well-formedness conditions that C, X↑[a]¬φ and C, X↑[a]φ respectively must be valid maximisation conditions (see Remark 4.13).

Remark 4.12

The reader can check that the rewrites of Figures 5 and 6 (for maximising hypersequents) are obtained from those of Figures 3 and 4 (for ‘plain’ hypersequents) by the following procedure:

• Delete the rules (δ−∀) and (δ−¬∃).

• Add ‘C ⊢’ to all the remaining rules.

• Replace (δ−∀) and (δ−¬∃) with (δX∀) and (δX¬∃) respectively.

Remark 4.13

We unpack what the well-formedness condition of Definition 4.11 means:

1. type(X) = type(a)

2. fa(φ)\{a} ⊆ pms(X) (that is, fa([a]φ) ⊆ pms(X))

3. The well-foundedness and functionality conditions (conditions 1 and 2 of Definition 4.5) cannot be violated by adding X↑[a]¬φ or X↑[a]φ to C.

If any of these conditions fail then we do not have a valid instance of a (δX∗) rule. Note, however, that X may occur in Φ or H; an example of this is in Subsection 4.2.1.

4.2. Example derivations using maximising hypersequents

4.2.1. Plato’s Principle

We give a derivation of Plato’s Principle using (δX∗) rules:

C ⊢((φ′ ∨φ) ∨Φ) ∧H(α∨)C ⊢(φ′ ∨φ ∨Φ) ∧HC ⊢((φ′ ⊃φ) ∨Φ) ∧H(α⊃)C ⊢(¬φ′ ∨φ ∨Φ) ∧HC ⊢(¬(φ′ ∨φ) ∨Φ) ∧H(β¬∨)C ⊢(¬φ′ ∨Φ) ∧(¬φ ∨Φ) ∧HC ⊢(¬(φ′ ⊃φ) ∨Φ) ∧H(β¬⊃)C ⊢(φ′ ∨Φ) ∧(¬φ ∨Φ) ∧HC ⊢(∃a.φ ∨Φ) ∧H (r : type(a))(γ∃)C ⊢(φ[a↦→r] ∨∃a.φ ∨Φ) ∧HC ⊢(¬∃a.φ ∨Φ) ∧H(δX¬∃)C, X↑[a]φ ⊢(¬φ[a↦→X] ∨Φ) ∧H
Figure 6: Derived rules for ∨, ⊃, ∃ in maximising hypersequents
∃a.((∃b.P(b)) ⊃P(a)) =⇒(γ∃), pms(X)=∅(∃b.P(b)) ⊃P(X) ∨∃a.((∃b.P(b)) ⊃P(a)) =⇒(α⊃)(¬∃b.P(b)) ∨P(X) ∨∃a.((∃b.P(b)) ⊃P(a)) =⇒(δX¬∃), pms(Y )=∅Y ↑[b]P(b) ⊢¬P(Y ) ∨P(X) ∨∃a.((∃b.P(b)) ⊃P(a))

We now instantiate X to Y in the rewrites above and extend with (αEM):

∃a.((∃b.P(b)) ⊃P(a)) =⇒(γ∃), pms(Y )=∅(∃b.P(b)) ⊃P(Y ) ∨∃a.((∃b.P(b)) ⊃P(a)) =⇒(α⊃)(¬∃b.P(b)) ∨P(Y ) ∨∃a.((∃b.P(b)) ⊃P(a)) =⇒(δX¬∃)Y ↑[b]P(b) ⊢¬P(Y ) ∨P(Y ) ∨∃a.((∃b.P(b)) ⊃P(a)) =⇒(αEM)Y ↑[b]P(b) ⊢∅

Compare this derivation with the one using (δ−∗) rules in Subsection 3.2.6. As promised at the end of Subsection 3.2.6, the derivation here is shorter; more complex because of the maximisation conditions, but shorter.

4.2.2. Exists does not imply Forall

We try to derive the formula (∃a.P(a)) ⊃∀a.P(a):

(∃a.P(a)) ⊃∀a.P(a) =⇒(α⊃), (δX¬∃), pms(Y )=∅Y ↑[a]P(a) ⊢¬P(Y ) ∨∀a.P(a) =⇒(δX∀), pms(X)=∅Y ↑[a]P(a), X↑[a]¬P(a) ⊢¬P(Y ) ∨P(X)

We note that ¬P(Y) and P(X) match the premises of (αEM) if we instantiate Y to X. Unfortunately if we try to do this then we run foul of functionality of maximisation conditions (condition 2 of Definition 4.5); {X↑[a]¬P(a), X↑[a]P(a)} is not functional, since [a]¬P(a) and [a]P(a) are not syntactically identical.

So we are stuck: we cannot use (αEM) because ¬P(Y) and P(X) are distinct. We cannot instantiate Y to X because then the instance of (δX∀) ceases to be an instance.

4.2.3. A derivation that fails because of the well-foundedness condition

We illustrate what can go wrong if we drop the well-foundedness condition on ≺ from Definition 4.5. Consider the following partial derivation of ∀a.(a ∨¬X), where type(a) = type(X) = o and pms(X) = ∅:

∀a.(a ∨¬X) =⇒(δX∀), (=αβη)Y ↑[a](a ∨¬X) ⊢Y ∨¬X

It would be quite nice if we could instantiate Y to X. So we do so, to obtain the following incorrect derivation of ∀a.(a ∨¬X):

∀a.(a ∨¬X) =⇏̸̸(δX∀), (=αβη)X↑[a](a ∨¬X) ⊢X ∨¬X =⇒(α∨)X↑[a](a ∨¬X) ⊢X ∨¬X =⇒(αEM)X↑[a](a ∨¬X) ⊢∅ Incorrect!

We note that the relation ≺ induced on variables by {X↑[a](a ∨¬X)} is not well-founded, since X ≺X.

5. Nominal models

In Subsection 5.1 we set up the basic definitions of nominal sets and in Subsection 5.2 we set up the basic ideas of models that we will need.

For more on nominal sets see [GP01, Gab11a, Gab12b]; to see the notions of model from which the ideas in this paper are derived—though the presentation here is tailored to our application—see [GM11] (nominal Henkin semantics) and [GM08b] or [DG10, DG12a] (nominal algebraic axiomatisations of first-order logic). A specific discussion of how this paper relates to [GM11] and [DG12a] is in Subsection 9.1.

The reader may grant that we want to axiomatise logic to build our models, but why do we need nominal sets? What do e.g. Definition 5.3 or Lemma 5.11 have to do with anything at all?

Nominal sets give us atoms, their permutative symmetries (i.e. equivariance properties), and the notion of finite support. It turns out—this is not obvious, but it is true—that this is just sufficient to give a nice, concise, well-behaved notion of model for systems with names and binding; substitution and quantification are two examples of such systems.

So note

• the conditions on support in Figures 7 and 8;

• how our treatment of atoms allows us to concisely state that ∀ is a congruence in Definition 5.16;

• how we impose a condition a ∉ supp([a]x) in Definition 5.12 and we use that condition Lemma 5.15;

• and how we use α-renaming in Corollary 5.24.

These are just examples of a close dance that takes place between the nominal sets semantics, the notion of model, and (in the background) the syntax developed above. It all fits together beautifully, and Subsection 5.1 is (by some magic, it might seem) just what is needed to make this work.

5.1. Background on nominal sets

Definition 5.1

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

Definition 5.2

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

Say that A ⊆A supports x ∈|X| when ∀π.π ∈ fix(A) ⇒π·x = x. If there exists a finite set S supporting x then call x supported and say that x has finite support.

Definition 5.3

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

Example 5.4

1. A forms a nominal set where π·a = π(a). The atom a is supported by {a}.

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

3. If X is a set with a permutation action then pow′(X) is a set with a permutation action, where pow′(X) has underlying set the full powerset of |X| and permutation action π·U = {π·u | u ∈U}. For example both {a} and A\{a} are in pow′(A) and are supported by {a}. The set comb = {a, c, e, g, . . . } of ‘every other atom’ is also in pow′(A) and supported only by A. In particular, comb has no finite supporting set.

4. If X is a nominal set then pow(X) is a nominal set with underlying set the subset of |pow′(X)| of elements with support. Note that {a} and A\{a} are both supported by {a}. So ‘a is in the support of x’ does not mean the same thing as ‘a is a set element of x’. Support measures asymmetry, not sets membership. It is a fact that |pow′(A)| is the set of all subsets of atoms whereas |pow(A)| is the set of subsets of atoms U such that U or A \ U is finite.

5. Permissive-nominal terms up to α-equivalence (Definition 2.22) with the permutation action from Definition 2.20, form a nominal set. The term r is supported by its free atoms fa(r). For more comment on this see [DGM09b, DGM10].

6. Permissive-nominal terms up to αβη-equivalence (Definition 2.22) with the same permutation action, also form a nominal set. As it happens, the term r is supported by the intersection of the free atoms of all terms αβη-equivalent to r.

Remark 5.5

The nominal notion of finite support is subtle, but a good starting intuition is that ‘a is in the support of x’ means ‘x depends on a’ or ‘x is asymmetric with respect to permuting a’.

It is important to realise that support does not depend on an a priori assumption that there is substitution, functional application, abstraction, or sets membership. Support is more elementary than these notions.

However, substitution, application, abstraction, and sets membership can interact with support in rich and interesting ways. See for instance the freshness side-conditions in Figure 7.

This is part of what makes nominal semantics so interesting. More extensive discus-sions of support are in [Gab11a, Gab12b].

Definition 5.6

Suppose X is a nominal set and x ∈|X|. Define the support of x by supp(x) = ⋂{A | A supports x}.

For the rest of this subsection we recall basic properties of nominal sets which will help us later, with pointers to full proofs.

Proposition 5.7

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

Proof

See [Gab11a, Theorem 2.19].End of proof

Theorem 5.8

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

Proof

See [Gab11a, Theorem 2.21].End of proof

Corollary 5.9

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 ∉ supp(x) if and only if ∃b.b ∉ supp(x) ∧ (b a)·x = x.

Proof

Parts 1 and 2 are just reformulations of Theorem 5.8. Part 3 follows (for details see [Gab12b, Corollary 2.2.7]).End of proof

Definition 5.10

• Call x ∈|X| equivariant when supp(x) = ∅.

• Call a function f ∈|X| →|Y| equivariant when π·f(x) = f(π·x) for all permutations π and x ∈|X|.

Lemma 5.11

• x ∈|X| is equivariant if and only if π·x = x for all π.

• If f ∈|X| →|Y| is equivariant (Definition 5.10) then supp(f(x)) ⊆ supp(x) for all x ∈|X|.

Proof

The first part is from parts 1 and 3 of Corollary 5.9. For the second part, see [Gab12b, Lemma 2.3.3].End of proof

5.2. Models

We now construct a notion of model. Henkin models [BBK04, Hen50] assume functions, and application in the syntax is translated directly to function application in the semantics. Our model is similar except that we are in a nominal setting, so we have names and binding in the semantics, and we translate atoms a and atoms-abstraction [a] directly to atoms and atoms-abstraction in our model.

Definition 5.12

An interpretation I is an assignment to each type α of a nominal set ⟦α⟧ together with the following data:

1. For each atom a ∈Aα and constant f : α elements aI ∈⟦α⟧ and fI ∈⟦α⟧.

2. For each x ∈⟦β⟧ and a ∈Aα, an element [a]x ∈⟦α→β⟧ such that a ∉ supp([a]x).

3. For each x ∈⟦α→β⟧ and y ∈⟦α⟧, an element x • y ∈⟦β⟧.

4. A preorder ⪅ on ⟦o⟧.

I must be equivariant in the sense that:

π·aI = (π(a))Iπ·fI = fIπ·[a]x = [π(a)]π·xπ·(x • y) = (π·x) • (π·y) x ⪅y ⇒π·x ⪅π·y
Remark 5.13

A few words on Definition 5.12.

• The atom a ∈Aα in the range of the interpretation is an atom of type α; we used these atoms in Definitions 2.3 and 2.10 to build permissive-nominal terms. The element aI is not an atom, it is just an element of ⟦α⟧, but the notation is designed to suggest that we think of aI as a model or copy of a in I, and thus the equivariance condition implies that supp(aI) ⊆{a}.
So for instance, supp(aI) = ∅ is possible, in which case all atoms of type α map to the same element in ⟦α⟧ and I has a trivial, but perfectly valid, interpretation of atoms.

• Similarly [a]x is not equal to ‘abstract a in x’ in the sense of Definition 2.10, simply because x ∈⟦β⟧ is not syntax but semantics. However, [a]x is intended to model ‘abstract a in x’, and if x happens to be the denotation of a term r then indeed [a]x will model [a]r. See Definition 5.27.

• Note that we do not assume that [a]x is literally equal to the nominal atoms-abstraction of a in x in the sense of equation (35) of [GP01]. Here, [a]x is just the model of abstract in I.13 The condition a ∉ supp([a]x) is therefore necessary. To be precise, the map a, x↦ → [a]x is an instance of an abstractive function in the sense of [Gab07b]. See Lemma 5.15.

• By the equivariance condition of Definition 5.12 and part 1 of Lemma 5.11, supp(fI) = ∅. So in our interpretations, constant symbols must be interpreted as elements with empty support. Treatments of non-equivariant term-formers in nominal terms syntax are in [Gab12c, Subsection 6.3.2] and [Gab12b].

Notation 5.14

For brevity we introduce the following notation:

• We may sugar ([a]x) • y to x[a↦→y] and ∀Iα • [a]x to ∀a.x.

• We may sugar (∧I • x) • y to x ∧I y or x ∧y, and ¬I • x to ¬x.

• We may sugar ¬⊤I to ⊥I.

• We may sugar ¬(¬x∧¬y) to x∨Iy or x∨y, and ¬x∨y to x ⊃y, and (x ⊃y)∧(y ⊃x) to x ⇔I y.

• We may write “e ≈e′” for “e ⪅e′ and e′ ⪅e”.

Lemma 5.15

Suppose z ∈⟦o⟧ and a, b : α and x ∈⟦α⟧. Then:

1. If b ∉ supp(z) then z[a↦→x] = ((b a)·z)[b↦→x].

2. If b ∉ supp(z) then ∀a.z = ∀b.(b a)·z.

Proof

Unpacking the syntactic sugar of Notation 5.14 it suffices to show that [b](b a)·z = [a]z. Now by assumption a, b ∉ supp([a]z) and by part 1 of Corollary 5.9 (b a)·[a]z = [a]z. The result follows by equivariance of the interpretation.End of proof

(moda) aI[a↦→x] = x(mod#) a ∉supp(z) ⇒ z[a↦→x] = z(modapp) (z′ •z)[a↦→x] = (z′[a↦→x]) • (z[a↦→x])(mod[]) c ∉supp(x) ⇒ ([c]z)[a↦→x] = [c](z[a↦→x])(modid) z[a↦→aI] = z(modη) a ∉supp(z) ⇒ [a](z • aI) = z
Figure 7: Equality in models
(Commute) x ∧y ≈y ∧x(Assoc) (x ∧y) ∧z ≈x ∧(y ∧z)(Huntington) x ≈¬(¬x ∧¬y) ∧¬(¬x ∧y)(∀E) ∀a.x ⪅x(∀∧) ∀a.(x ∧y) ≈(∀a.x) ∧(∀a.y)(∀∨) a ∉supp(y) ⇒ ∀a.(x ∨y) ≈(∀a.x) ∨y
Figure 8: Preorder on truth-values
Definition 5.16

Call an interpretation I a model when:

• The axioms in Figure 7 hold.

• The axioms in Figure 8 hold.

• ⪅ is a congruence in the sense that for x, y ∈⟦o⟧ and u ∈⟦α⟧ and a ∈Aα, if x ⪅x′ and y ⪅y′ then

¬x′ ⪅¬x, x ∧y ⪅x′ ∧y′, ∀a.x ⪅∀a.x′, and x[a↦→u] ⪅x′[a↦→u].
Remark 5.17

Models have a part to model the simply-typed λ-calculus, and a part to model the logic at type o.

• The axioms of Figure 7 handle the simply-typed λ-calculus. Compare with the nominal Henkin semantics from [GM11].

• The axioms in Figure 8 handle the logic taking place at type o. These axioms are evolved from [GM08b], where (first-order) logic was axiomatised in nominal algebra. We are using nominal algebra [GM09a] in this paper, but ‘secretly’ in the sense that we do not develop its formal syntax and semantics.

Broadly speaking, this subsection is obtained by combining [GM11] with [GM08b]. The combination is not off-the-shelf; the systems have been adapted, simplified, and improved; see Subsection 9.1.

Remark 5.18

Our notion of truth in ⟦o⟧ is intensional in the sense that for z′, z ∈⟦o⟧, z′ ≈z does not imply z′ = z. That is, our model allows truth-values to have properties that can distinguish them but do not relate to entailment.

We give an intuitive example; it will be made completely formal in Definition 7.1. Take ⟦o⟧ to be some set of predicates, preordered by logical entailment, and take any two distinct predicates φ and ψ. Then we expect φ ∧ψ ≈ψ ∧φ to hold, but φ ∧ψ and ψ ∧φ are not equal predicates and so will not be equal elements of ⟦o⟧.

This modest increase in complexity (and generality) makes it easier to build some models later. In particular, the syntactic model of Subsection 7.1 is easier to construct, because by distinguishing ≈ and = we avoid having to take a quotient by logical equivalence, which would be inconvenient. In fact, intensional semantics also have more general justi-fications from linguistics and computing amongst other fields; see for instance [BBK04] or [Sha85].

Remark 5.19

Following on from Remark 5.18, note that models themselves are still extensional in the sense that we assume η-equivalence ((modη) in Figure 7 and, in the syntax, (stxη) in Figure 2). This is not absolutely necessary but it does make things easier because every z ∈⟦α→β⟧ has the form [a]z′ for z′ = z • a, where a ∉ supp(z). (Such an a always exists because by assumption supp(z) is finite.)

These are purely design decisions, made to keep the definitions and proofs as simple as possible.

Lemmas 5.20 to 5.23 are basic corollaries of the axioms of being a model:

Lemma 5.20

The following all hold:

• supp(aI) ⊆{a}.

• supp(fI) = ∅.

• supp([a]x) ⊆ supp(x)\{a}.

• supp(x′ • x) ⊆ supp(x′) ∪ supp(x).

Proof

Using the equivariance condition on I and part 3 of Corollary 5.9, and our assumption that a ∉ supp([a]x).End of proof

Corollary 5.21

supp(∀a.x) ⊆ supp(x)\{a} and supp(z[a↦→x]) ⊆ (supp(z)\{a})∪supp(x).

Proof

From Lemma 5.20 recalling the syntactic sugar of Notation 5.14.End of proof

Lemma 5.22

1. ∀a.⊤I ≈⊤I and ∀a.⊥I ≈⊥I.

2. If z ∈⟦o⟧ and a ∉ supp(z) then ∀a.z ≈z.

Proof

To prove ∀a.⊤I ≈⊤I we reason as follows, where we use facts of Boolean algebras and congruence properties without comment:

∀a.⊤I ≈∀a.(⊤I ∨⊤I)(∀∨)≈ (∀a.⊤I) ∨⊤I ≈⊤I.

Here we can use (∀∨) because by assumption in Definition 5.12 ⊤I is equivariant.

By properties of Boolean algebra ⊥I ⪅∀a.⊥I. Conversely by (∀E) ∀a.⊥I ⪅⊥I. For the second part we use the first part. Suppose a ∉ supp(z). Then we reason as follows:

∀a.z ≈∀a.(⊥I ∨z)(∀∨)≈ (∀a.⊥I) ∨zPart 1≈ ⊥I ∨z ≈zEnd of proof
Lemma 5.23

Suppose a : α.

1. If z ∈⟦o⟧ then ∀a.z ⪅z[a↦→x] for any x ∈⟦α⟧.

2. If z′ ⪅z[a↦→x] for all x ∈⟦α⟧ and a ∉ supp(z′) then z′ ⪅∀a.z.

Proof

For the first part, by (∀E) ∀a.z ⪅z. By congruence from Definition 5.16 (∀a.z)[a↦→x] ⪅ z[a↦→x]. By Corollary 5.21 and (mod#) (∀a.z)[a↦→x] = ∀a.z. It follows that ∀a.z ≤ z[a↦→x].

For the second part, it follows taking x = aI and using (modid) that z′ ⪅z. By congruence from Definition 5.16 ∀a.z′ ⪅∀a.z and by part 2 of Lemma 5.22 z′ ⪅∀a.z.End of proof

Corollary 5.24

Suppose a : α and z ∈⟦o⟧. Then ∀a.z is a ⪅-greatest lower bound for {z[a↦→x] | x ∈⟦α⟧}.

Proof

By part 1 of Lemma 5.23 ∀a.z is a lower bound. Now suppose z′ ⪅z[a↦→x] for every x ∈⟦α⟧. Renaming if necessary using Lemma 5.15 suppose a ∉ supp(z′). We use part 2 of Lemma 5.23.End of proof

We mention another nice corollary of Lemma 5.23:

Lemma 5.25

If z ∈⟦o⟧ then ∀a.∀b.z ≈∀b.∀a.z.

Proof

By (∀E) ∀a.∀b.z ⪅z. By congruence of ∀ in Definition 5.16 ∀b.∀a.∀a.∀b.z ⪅∀b.∀a.z. By definition ∀b.∀a.∀a.∀b.z = ∀• [b]∀• [a]∀• [a]∀• [b]z. Now from Lemma 5.11 and equivariance of I in Definition 5.12 it follows that b ∉ supp(∀• [a]∀• [a]∀• [b]z) and a ∉ supp(∀• [a]∀• [b]z). Thus using (∀E) we have ∀b.∀a.∀a.∀b.z = ∀a.∀b.z.

So ∀a.∀b.z ⪅∀b.∀a.z and by symmetry we are done.End of proof

5.3. Valuations

Definition 5.26

Given a model I, a valuation ζ to I is a map on variables such that for every variable X, ζ(X) ∈⟦type(X)⟧ and supp(ζ(X)) ⊆ pms(X).

Definition 5.27

Suppose ζ is a valuation to a model I and suppose r : α. Define an interpretation ⟦r⟧ζ ∈⟦α⟧ by:

⟦a⟧ζ = aI⟦f⟧ζ = fI⟦π·X⟧ζ = π·ζ(X)⟦rs⟧ζ = ⟦r⟧ζ • ⟦s⟧ζ⟦[a]r⟧ζ = [a]⟦r⟧ζ

In the rest of this subsection we prove some standard results which will be useful later. The most complex of these is probably Proposition 5.31.

Notation 5.28

Suppose X : α and x ∈⟦α⟧. Define ζ[X:=x] by:

(ζ[X:=x])(X) = x (ζ[X:=x])(Y ) = ζ(Y )
Lemma 5.29

1. ⟦π·r⟧ζ = π·⟦r⟧ζ

2. ⟦r[X:=s]⟧ζ = ⟦r⟧ζ[X:=⟦s⟧ζ]

3. ⟦r[a↦→s]⟧ζ = ⟦r⟧ζ[a↦→⟦s⟧ζ]

Proof

The first part is a routine induction on r. The second part is by a routine induction on r, using the first part for the case r = π·X.

The third part is by unpacking Definition 5.27, recalling from Notation 2.15 that r[a↦→s] is syntactic sugar for ([a]r)s and from Notation 5.14 that ⟦r⟧ζ[a↦→⟦s⟧ζ] is syntactic sugar for ([a]⟦r⟧ζ) • ⟦s⟧ζ.End of proof

Lemma 5.30

supp(⟦r⟧ζ) ⊆ fa(r).

Proof

By induction on r.

• The case of a. By Lemma 5.20 supp(aI) ⊆{a} = fa(a).

• The case of π·X. By assumption supp(ζ(X)) ⊆ pms(X). So using Proposition 5.7 we have supp(π·ζ(X)) = π·supp(ζ(X)) ⊆π·pms(X) = fa(π·X).

• The case of f. By Lemma 5.20 supp(fI) = ∅= fa(f).

• The case of r′r. We reason as follows:

supp(⟦r′r⟧ζ) = supp(⟦r′⟧ζ • ⟦r⟧ζ) Definition 5.27⊆supp(⟦r′⟧ζ) ∪supp(⟦r⟧ζ) Lemma 5.20⊆fa(r′) ∪fa(r) Ind. Hyp.= fa(r′r) Definition 2.20

• The case of [a]r. We reason as follows:

supp(⟦[a]r⟧ζ) = supp([a]⟦r⟧ζ) Definition 5.27⊆⟦r⟧ζ \ {a} Condition 2, Def. 5.27⊆fa(r) \ {a} Ind. Hyp.= fa([a]r) Definition 2.20End of proof
Proposition 5.31

1. If r =α r′ then ⟦r⟧ζ = ⟦r′⟧ζ.

2. If r =αβη r′ then ⟦r⟧ζ = ⟦r′⟧ζ.

Proof

Both parts are by induction on the derivation of =α and =αβη respectively. The interesting cases are:

• Rule (stxα). Suppose a, b ∉ fa(r). By Lemma 5.30 a, b ∉ supp(⟦r⟧ζ). By part 2 of Corollary 5.9 (b a)·⟦r⟧ζ = ⟦r⟧ζ. It follows by part 1 of Lemma 5.29 that ⟦(b a)·r⟧ζ = ⟦r⟧ζ.

• Rule (stxa). By (moda).

• Rule (stx#). Suppose a ∉ fa(r). By Lemma 5.30 a ∉ supp(⟦r⟧ζ). By (mod#) ⟦r⟧ζ[a↦→⟦t⟧ζ] = ⟦r⟧ζ. The result follows since by construction in Definition 5.27, ⟦r⟧ζ[a↦→⟦t⟧ζ] = ⟦r[a↦→t]⟧ζ.

• Similarly, (stx•) follows from (modapp), (stx[]) follows from (mod[]), and (stxid) follows from (modid).End of proof

Lemma 5.32

If ζ(X) = ζ′(X) for every X ∈ fv(r) then ⟦r⟧ζ = ⟦r⟧ζ′.

Proof

By a routine induction on r.End of proof

6. Interpretation of (maximising) hypersequents

6.1. Interpretation of hypersequents

For this subsection fix some model I (Definition 5.16). ζ will range over valuations (Definition 5.26) to I. Recall also that φ ranges over formulae, that is, over terms of type o.

Hypersequents are conjunctions of disjunctions of formulae; we now show how to interpret hypersequents and the notion of hypersequent rewriting (derivations) from Definition 3.3 (we treat maximising hypersequents in Subsection 6.2) in I, culminating with a soundness result Theorem 6.6.

Definition 6.1

Extend the interpretation of Definition 5.27 to sequents and hypersequents as follows:

⟦φ1 ∨. . . ∨φn⟧ζ = ⟦φ1⟧ζ ∨I · · · ∨I ⟦φn⟧ζ⟦∅⟧ζ = ⊥I⟦Φ1 ∧. . . ∧Φm⟧ζ = ⟦Φ1⟧ζ ∧I · · · ∧I ⟦Φm⟧ζ⟦∅⟧ζ = ⊤I

So ∨ and ∧ in hypersequents are interpreted as conjunction and disjunction in the model. The right-hand column may seem confusing, but ∅ at the top is an empty sequent, whereas ∅ at the bottom is an empty hypersequent;14 by convention, if a sequent is empty its denotation is ⊥I and if a hypersequent is empty its denotation is ⊤I.

Proposition 6.2

If H H′ is an instance of an (α∗) rule or of (β∧) then ⟦H⟧ζ ≈⟦H′⟧ζ.

Proof

(ᬬ), (α⊤), (αEM), (α¬∧), and (β∧) follow from (Commute), (Assoc), and (Huntington) (see [McC97] or [Hun33, Postulate 6, page 179]). (=αβη) follows from Proposition 5.31.End of proof

Lemma 6.3

Suppose a : α and t : α. Then ⟦φ[a↦→t]⟧ζ ⪅⟦∃a.φ⟧ζ and ⟦∀a.φ⟧ζ ⪅⟦φ[a↦→t]⟧ζ.

Proof

We consider just the ∀ part; the ∃ part follows taking duals. We reason as follows:

⟦∀a.φ⟧ζ = ∀Iα • [a]⟦φ⟧ζDefinition 5.27

⪅⟦φ⟧ζ[a↦→⟦t⟧ζ] Part 1 Lemma 5.23

= ⟦φ[a↦→t]⟧ζPart 3 Lemma 5.29End of proof
Corollary 6.4

If H H′ is an instance of (γ¬∀) or (γ∃) then ⟦H′⟧ζ ≈⟦H⟧ζ.

Proof

We consider just the case of (γ∃); the case of (γ¬∀) is dual. Elements of a sequent in a hypersequent are interpreted disjunctively, so it suffices to prove that ⟦φ[a↦→r]⟧ζ ⪅ ⟦∃a.φ⟧ζ. This follows by Lemma 6.3.End of proof

Lemma 6.5

If H H′ is an instance of (δ−∀) or (δ−¬∃) then ⟦H′⟧ζ ≈⊤I implies ⟦H⟧ζ ≈⊤I.

Proof

We consider just the case of (δ−∀); the case of (δ−¬∃) is dual. Suppose H = (φ ∨ Φ) ∧H′ where φ is the focal formula of the instance of (δ−∀) so that a ∉ fa(Φ).

Suppose ⟦(φ ∨ Φ) ∧H′⟧ζ ≈⊤I. By part 1 of Lemma 5.22 ⊤I ≈∀a.⊤I. Using (∀∧) and (∀∨) and Lemma 5.30 and part 2 of Lemma 5.22, we calculate that ∀a.⟦φ ∨ Φ⟧ζ ≈⟦(∀a.φ) ∨ Φ⟧ζ. Now we did not assume in (δ−∀) that a ∉ fa(H) (where we take fa(⋀ ⋁ φ) = ⋃ fa(φ)), but we do know by (∀E) that ∀a.⟦H⟧ζ ⪅⟦H⟧ζ. The result follows.End of proof

Theorem 6.6

If H rewrites to H′ by the rules in Definition 3.3 and Figure 3 then ⟦H′⟧ζ ≈⊤I implies ⟦H⟧ζ ≈⊤I.

As a corollary, if H rewrites to ∅ then ⟦H⟧ζ ≈⊤I.

Proof

From Proposition 6.2, Corollary 6.4, and Lemma 6.5, and the fact that ⟦∅⟧ζ = ⊤I.End of proof

The result corresponding to Theorem 6.6 for maximising hypersequents is Theorem 6.18. Before considering maximising hypersequents, we need to tie up one small loose end:

Lemma 6.7

If z ≈⊤I then z ≈∀a.z. Also, z ≈⊤I if and only if ∀a.z ≈⊤I.

Proof

Suppose z ≈⊤I. Then ∀a.z ≈∀a.⊤I and by part 1 of Lemma 5.22 ∀a.z ≈⊤I. It follows by transitivity of ≈ that z ≈∀a.z.

Now suppose ∀a.z ≈⊤I. By (∀E) ∀a.z ⪅z. It follows that z ≈⊤I.End of proof

Remark 6.8

In Theorem 6.6 we discuss ⟦H⟧ζ ≈⊤I. By Lemma 6.7 this equality has the value of a universally quantified closure.

The use of nominal models buys us some simplicity in that we do not need to explicitly quantify or λ-abstract over free atoms. In Theorem 6.6 we do not have to say something of the form ‘for all valuations of atoms to denotational elements ⟦H⟧ = ⊤’ or ‘⟦λx1, . . . , xn.H⟧ = λx1, . . . , xn.⊤ where {x1, . . . , xn} include the variables free in H’. This is all handled automatically when we write ⟦H⟧ζ = ⊤I.

Also, nothing in the models so far insists that there be anything specifically non-nominal to quantify over. (This echoes an observation made in a slightly different context in [GM11, Theorem 3.15] that the nominal models of [GM11] always have ‘sufficiently many points’.)

It is traditional to add fresh constant symbols or parameters to the signature of a language to help us interpret universally quantified formulae. In nominal techniques the need for this structure is fulfilled by the specific and rich structure of atoms.

6.2. Interpretation of maximising hypersequents

We now show how to interpret the maximising hypersequents of Section 4 in models. This extra power corresponds nicely to extra structure in the models, which we now discuss:

Definition 6.9

Suppose a : α and z ∈⟦α→o⟧. Call x ∈⟦α⟧ a maximiser for z, and say that the element x maximises z, when

1. supp(x) ⊆ supp(z) and

2. z • x ≈∃Iα • z.

Say that I has maximisers for every type α, when every z ∈⟦α→o⟧ has at least one maximiser. Conversely we can say that x ∈⟦α⟧ minimises z ∈⟦α→o⟧ when supp(x) ⊆ supp(z) and z • x ≈∀Iα • z.

Remark 6.10

We insist on supp(x) ⊆ supp(z) in condition 1 of Definition 6.9 to ensure that in Proposition 6.17 when we build ζ[Xi:=xi]n 1, this will be a valuation (Definition 5.26).

By part 2 of Lemma 5.23 (and extensionality (modη)) the condition z • x ≈∃Iα • z is just a fancy way of saying that z • x′ ⪅z • x for all x′, in other words, that x is an element that maximises z • x.

Another way to understand the condition supp(x) ⊆ supp(z) is to view z as an open predicate: open, and thus parameterised over the atoms in its support. Then, whatever values x assumes should depend only on those parameters.

We note here, as we noted in Remark 6.8, that there is nothing in the model to insist that the atoms ever get instantiated to ‘actual values’. The point of the nominal models is that we can and do reason directly on open elements, and indeed the distinction between open and closed is no longer equal to the distinction between syntax and semantics.

In particular there is no need to explicitly abstract over the free atoms of z and write ‘for all closing λ-abstractions’ or ‘for all substitutions’. The nominal models make it possible to talk about maximising elements directly and without lifting them to higher types to account for syntactic parameters.

We now take a moment to unpack and verify the dualisation of ∀ and ∃ with respect to maximisation/minimisation:

Proposition 6.11

Suppose z′ ∈⟦o⟧ and a : α and x ∈⟦α⟧. Then x minimises [a]z′ if and only if x maximises [a]¬z′.

Proof

Suppose supp(x) ⊆ supp(z′) \ {a}. It suffices to show that z′[a↦→x] ≈∀a.z′ if and only if (¬z′)[a↦→x] ≈∃a.¬z′. But ∃a.z′ is syntactic sugar for ¬∀a.¬z′. The result follows using (modapp) and (mod#), and facts of Boolean algebra.End of proof

For the rest of this subsection suppose I is a model (Definition 5.16), and I has maximisers.

Definition 6.12

Extend the interpretation of Definition 6.1 to maximising hypersequents as follows:

⟦X↑[a]φ⟧ζ = ⟦∃a.φ⟧ζ ⊃I ⟦φ[a↦→X]⟧ζ⟦(Xi↑[ai]φi)n 1⟧ζ = ⟦X1↑[a1]φ1⟧ζ ∧I · · · ∧I ⟦Xn↑[an]φn⟧ζ⟦(Xi↑[ai]φi)n 1 ⊢H⟧ζ = ⟦(Xi↑[ai]φi)n 1⟧ζ ∧⟦H⟧ζ
Remark 6.13

In Definition 4.1 we took fa([a]φ) ⊆ pms(X). From the point of view of the models, it might also suffice to take fa([a]φ) = pms(X). We allow a subset inclusion because Lemma 5.30 is a subset inclusion, not an equality; it might be that some atoms that appear in a term do not feature in its denotation (think of first projection(a, b)). It does no harm to leave ourselves a little leeway.

Remark 6.14

In Remarks 4.2 and 4.10 we described maximisers as a form of choice. Now that we have defined the formal semantics we can be more precise about this. Definition 6.12 does not make a choice, in the sense of choosing an element. It simply takes the conjunction of ⟦X↑[a]φ⟧ζ (a truth-value) with ⟦H⟧ζ (another truth-value). This is why we described maximisers as non-Skolemising.

What gives this conjunction the effect of a choice is, specifically, the ∃ζ in Theorem 6.18 and Corollary 6.19.

It might help to think of maximisers as a form of delayed choice.

We mention this particularly in case the reader is tempted to imagine that maximisers are just a syntactic repackaging of Hilbert’s choice ϵ. They are not, and this is made semantically precise in Section 8.

Lemma 6.15

Suppose a : α and X : α. Then

⟦X↑[a]φ⟧ζ ∧⟦∃a.φ⟧ζ ⪅⟦φ[a↦→X]⟧ζ⟦X↑[a]¬φ⟧ζ ∧⟦φ[a↦→X]⟧ζ ⪅⟦∀a.φ⟧ζ
Proof

We just unpack Definition 6.12 and use Definition 5.27 and properties of Boolean algebra.End of proof

Corollary 6.16

If P P′ is an instance of (δX∀) or (δX¬∃) then ⟦P′⟧ζ ⪅⟦P⟧ζ.

Proof

We consider just the case of (δX∀); the case of (δX¬∃) is dual. Suppose

P = (Xi↑[ai]φi)n 1 ⊢(∀a.φ ∨Φ) ∧H andP′ = (Xi↑[ai]φi)n 1, X↑[a]¬φ ⊢(φ[a↦→X] ∨Φ) ∧H.

We unpack Definition 6.12 and use Lemma 6.15.End of proof

Proposition 6.17

Suppose C is a maximisation condition. Then there exists a valuation ζ such that ⟦C⟧ζ ≈⊤I.

Proof

Choose any valuation ζ1. We work by induction on the partial order ≺ on variables induced by C (Definition 4.5) to construct a sequence ζ1, ζ2, ..., ζn such that ζn is the required valuation.

Start with a ≺-minimal element Xi ∈ dom(C), so that by functionality of C (Definition 4.5), C = {Xi↑[ai]φi} ∪C′ where C′ = C\{Xi↑[ai]φi}. We assumed Xi is ≺-minimal so by Lemma 4.7 we have fv(φi) ∩ dom(C) = ∅. By assumption I has maximisers so there exists an xi maximising ⟦φi⟧ζ1. Set ζ2 = ζ1[Xi:=xi].

Repeat this process for C′ and work our way up ≺ to arrive at ζn = ζ1[Xi:=xi]n 1 where n is the cardinality of dom(C). Using Lemma 5.32 we can verify that xi maximises ⟦[ai]φi⟧ζn for each 1≤i≤n, as required.

We must also check that ζn is a valuation; it suffices to show that supp(xi) ⊆ pms(Xi) for each i. This follows from condition 1 of Definition 6.9, Lemma 5.30, and Definition 4.1.End of proof

Theorem 6.18 is to maximising hypersequents as Theorem 6.6 was to hypersequents:

Theorem 6.18

If P rewrites to P′ by the rules of Definition 4.11 then

∃ζ.⟦P′⟧ζ≈⊤Iimplies ∃ζ.⟦P⟧ζ≈⊤I.

As a corollary, if P rewrites to C ⊢∅ then ∃ζ.⟦P⟧ζ≈⊤I.

Proof

From Proposition 6.2, Corollary 6.4, Corollary 6.16, and Proposition 6.17 (existence of maximisers).End of proof

Corollary 6.19

If ∅⊢H rewrites to C ⊢∅ by the rules of Definition 4.11 then ∃ζ.⟦H⟧ ≈⊤I.

Proof

Direct from Theorem 6.18 using the fact that any ζ satisfies the empty maximisation condition.End of proof

Remark 6.20

When nominal unknowns X, Y , Z were introduced in [UPG03, UPG04] as unification variables, they had a flavour of existential variables; that is, variables ranging over elements that we try to ‘find’ to ‘make something true’. This is made formal in Theorem 6.18 by the use of ∃ζ; we try to find values that make the denotation of the problem be true.

Atoms are ‘universal’ in a sense made formal by the following lemma: if ⟦P⟧ζ = ⊤I and a ∈Aα then by (mod#) from Figure 7 also ⟦P⟧ζ[a↦→x] = ⊤I for every x ∈⟦α⟧. Part 3 of Lemma 5.29 relates this semantic substitution to a natural notion of substituting atoms for terms in problems.

Condition 2 of Definition 6.9 and Definition 6.12 make formal a sense in which maximisation conditions restrict existential variables X to make a predicate φ[a↦→X] as true as possible. Using negation, we can then give X a universal flavour, by restricting it to range over elements that try to make ¬φ[a↦→X] as true as possible, i.e. φ[a↦→X] as false as possible. This is happens in (δX∀) in Figure 5.

Thus, two distinct notions of ‘universal’ variable are explained in our nominal semantics— we easily map this to the syntax in Subsection 6.3. Note that variables do not obsolete atoms. We still need atoms to name lemmas, or, in λ-calculus terminology, we still need to be able to write [a]r and apply this to s to make ([a]r) • s, or write [a]φ and apply ∀ to it to make ∀• [a]φ.

In view of the above, the reader should take the tag ‘universal’ for atoms a, and ‘existential’ for variables X, with a pinch of salt.15 We can always form ∃a.φ or insert a maximisation condition X↑[a]¬φ. Ultimately, the precise meanings of atoms and variables are given by the semantics. For the reader’s convenience we recall the critical definitions: 5.27, 6.1, 6.9, and 6.12.

6.3. Instantiating X in (maximising) hypersequents

We can now come full circle and show how the existential flavour of X can be folded back down into the syntax. In other words, we show how to instantiate X in a hypersequent or maximising hypersequent. With the maths we have so far, this is not hard.

We need a little notation:

Definition 6.21

Suppose s : type(X) and fa(s) ⊆ pms(X) so that [X:=s] is an instantiation (Definition 2.26). Suppose H = ⋀ ⋁ φi is a hypersequent. Then define

H[X:=s] = ⋀ ⋁(φi[X:=s]).

If C = (Xi↑[ai]φi)n 1 and X ∉ dom(C) (so X ∉{Xi | 1≤i≤n}) then define

C[X:=s] = (Xi↑[ai](φi[X:=s]))n 1.

Suppose P = (C ⊢H) and X ∉ dom(C). Define

P[X:=s] = (C[X:=s] ⊢H[X:=s]).

Finally, if X ∉ fv(φ) define16

(C, X↑[a]φ ⊢H)[X:=s] =(C[X:=s] ⊢((∃a.φ) ⊃(φ[a↦→s])) ∧H[X:=s]).

We take a moment to state the obvious:

Lemma 6.22

Suppose s : type(X) and fa(s) ⊆ pms(X), so that [X:=s] is an instantiation. Suppose C ⊢H is a maximising hypersequent.

Then if C[X:=s] is a valid maximisation condition then (C ⊢H)[X:=s] is a maximising hypersequent.

Lemma 6.22 is interesting not for the logical content (which is almost directly tautolog-ical) but for highlighting the condition that C[X:=s] be a valid maximisation condition. Recall from Subsection 4.2.3 that this depends on ≺ remaining well-founded. Whether that holds depends on the precise structures of C and s.

Lemma 6.23

Suppose s : type(X) and fa(s) ⊆ pms(X) so that [X:=s] is an instantiation. Suppose P = (C ⊢H) is a maximising hypersequent and C[X:=s] is a valid maximisation condition.

Then ⟦P[X:=s]⟧ζ = ⟦P⟧ζ[X:=⟦s⟧ζ].

Proof

By unpacking Definitions 6.12 and 6.21 and using part 2 of Lemma 5.29.End of proof

Theorem 6.24

Suppose s : type(X) and fa(s) ⊆ pms(X) so that [X:=s] is an instantiation. Suppose P = (C ⊢H) is a maximising hypersequent and C[X:=s] is a valid maximisation condition. Then:

1. If ∃ζ.⟦P[X:=s]⟧ζ = ⊤I then ∃ζ.⟦P⟧ζ = ⊤I.

2. If ∀ζ.⟦P⟧ζ ⪅⟦P′⟧ζ then ∀ζ.⟦P[X:=s]⟧ζ ⪅⟦P′[X:=s]⟧ζ.

Proof

Both parts are from Lemma 6.23.End of proof

With what we now have, we can put the instantiations of Subsections 3.2 and 4.2 (see Remark 3.6) in a more general context:

Proposition 6.25

Suppose s : type(X) and fa(s) ⊆ pms(X) so that [X:=s] is an instantiation.

1. Suppose H and H′ are hypersequents. Then H ⇒H′ implies H[X:=s] ⇒H′[X:=s].

2. Suppose C and C′ are maximisation conditions and X ∉ dom(C) ∪ dom(C′). Suppose C[X:=s] and C′[X:=s] are valid maximisation conditions.

Then (C ⊢H) ⇒(C′ ⊢H′) implies (C ⊢H)[X:=s] ⇒(C′ ⊢H′)[X:=s].
Proof

For part 1 of this result we check each of the rules in Figure 3 and see that they are preserved by instantiating variables: By part 4 of Proposition 2.29 the side-condition φ =αβη φ′ in (=αβη) is preserved . By Proposition 2.25 the side-condition r : type(a) in (γ¬∀) is preserved. Using part 1 of Proposition 2.29 the side-condition a ∉ fa(Φ) is preserved.

Part 2 of this result follows using Lemma 6.22 and some routine calculations on syntax.End of proof

7. Building models by hand

We set about building some concrete instances of the notion of model given in Subsection 5.2. Two possibilities naturally present themselves: build a model out of quotiented syntax; or build a nominal model out of some standard model of higher-order logic over ordinary (non-nominal) sets. These are Subsections 7.1 and 7.2 respectively. We also return to these in Subsection 8.3, when we consider choice.

7.1. The syntactic model

Recall from Definition 2.22 the definition of =αβη as the least congruence containing (stxα), rules (stxa) to (stxid), and (stxη).

Definition 7.1

Let ⪅ be the least preorder congruence containing =αβη and also such that:

φ ∧ψ ≈ψ ∧φ (φ ∧ψ) ∧χ ≈φ ∧(ψ ∧χ)φ ≈¬(¬φ ∧¬ψ) ∧¬(¬φ ∧ψ)∀a.φ ⪅φ ∀a.(φ ∧ψ) ≈(∀a.φ) ∧(∀a.ψ) a ∉fa(ψ) ⇒∀a.(φ ∨ψ) ≈(∀a.φ) ∨ψ

Here, as before in Notation 5.14, we write “φ ≈ψ” as shorthand for “φ ⪅ψ and ψ ⪅φ”.

Definition 7.2

Define ⟦α⟧S = {[r]αβη | r : α}. Give this the pointwise permutation action π·[r]αβη = [π·r]αβη.

It is easy to check that Definition 7.2 determines a nominal set, in which [r]αβη is supported by fa(r).

Definition 7.3

Define an interpretation S (Definition 5.12) by assigning to each type α the nominal set ⟦α⟧S, along with the following data:

• aS = [a]αβη and f S = [f]αβη.

• [a][r]αβη = [[a]r]αβη.

• [r]αβη • [s]αβη = [rs]αβη.

• [φ]αβη ⪅ [ψ]αβη if φ ⪅ψ.

Lemma 7.4

r =αβη s if and only if π·r =αβη π·s. As a corollary, Definition 7.3 is equivariant in the sense of Definition 5.12.

Proof

We note that Definition 2.22 is symmetric in permuting atoms, and therefore so is the relation =αβη that it defines.End of proof

Remark 7.5

One of the fundamental observations of nominal techniques is that atoms are symmetric, and this can be exploited to give fast, convenient, and fully-rigorous proofs of real theorems in real maths papers, such as in [Gab07a],17 or here in Lemma 7.4. This is made formal by the general nominal meta-principle of equivariance for symmetric predicates [Gab11a, Theorem 4.4]. A concrete proof of Lemma 7.4 by induction on the derivation of r =αβη s is also possible; that would amount to verifying the symmetries inductively.

Lemma 7.6

a ∉ supp([[a]r]αβη).

Proof

By (stxα) if b is fresh (so b ∉ fa(r)∪supp([[a]r]αβη)) then [a]r =α [b](b a)·r. It follows that (b a)·[[a]r]αβη = [[a]r]αβη and so by part 3 of Corollary 5.9 that a ∉ supp([[a]r]αβη).18End of proof

Corollary 7.7

Definition 7.3 is an interpretation.

Proof

From Lemmas 7.6 and 7.4.End of proof

We will need Lemma 7.8 in a moment. This is a special case of a more general result [Gab12b, Lemma 7.6.2]:

Lemma 7.8

If a ∉ supp([r]αβη) then there exists some r′ ≈r such that a ∉ fa(r′).

Proof

Suppose a ∉ supp([r]αβη). Choose fresh b, so b ∉ fa(r) ∪ supp([r]αβη). By part 1 of Corollary 5.9 (b a)·[r]αβη = [r]αβη and it follows that (b a)·r ∈ [r]αβη, that is, (b a)·r =αβη r. We take r′ = (b a)·r and note by Lemma 2.21 that a ∉ fa(r′).End of proof

Proposition 7.9 looks like a trivial replay of (stxa) to (stxid) and (stxη) from Figure 2, but this is deceptive. The freshness side-conditions of the model equalities refer to support of equivalence classes of terms; the freshness side-conditions of the syntactic equalities refer to free atoms of a term.

Proposition 7.9

The axioms (moda) to (modid) and (modη) from Figure 7 are valid in S.

Proof

We consider just the case of (mod#); the other axioms are no harder. Suppose a ∉ supp([r]αβη). By Lemma 7.8 there exists some r′ such that r′ =αβη r and a does not occur at all in r′. In particular, it is not hard to prove that a ∉ fa(r′). By (stx#) r′[a↦→t] =αβη r′. By congruence of =αβη, also r[a↦→t] =αβη r and so [r[a↦→t]]αβη = [r]αβη as required.End of proof

Proposition 7.10

The axioms (Commute) to (∀∨) from Figure 8 are valid in S.

Proof

Most follow directly from the preorder on terms in Definition 7.1. As for Proposition 7.9 we just have to be a little careful about the freshness side-conditions.

There is only one of these: we must show that if a ∉ supp([ψ]αβη) then ∀a.([φ]αβη ∨ [ψ]αβη) ≈ (∀a.[φ]αβη) ∨ [ψ]αβη.

So suppose a ∉ supp([ψ]αβη). Using Lemma 7.8 let ψ′ be such that ψ′ =αβη ψ and a ∉ fa(ψ′). By assumption ∀a.(φ ∨ψ′) =αβη (∀a.φ) ∨ψ′. By the congruence properties of =αβη we are done.End of proof

The arguments above suffice to prove that we have a model:

Theorem 7.11

S is a model in the sense of Definition 5.16.

7.2. The functional model F

We now show how to obtain a model in the sense of Definition 5.16 from an ‘ordinary’ functional model of higher-order logic.

Definition 7.12

A functional model F is an assignment as follows:

• To each base type τ assign a non-empty ‘ordinary’ set ⟦τ⟧F.

• To each constant f assign an element fF ∈⟦type(f)⟧F.

We extend ⟦-⟧F to all types by

⟦o⟧F = {⊥, ⊤} (Booleans) and ⟦α→β⟧F = ⟦α⟧F⇒⟦β⟧F (function space).

Fix some functional model F. We now work towards Definition 7.19, in which we construct a nominal model I in the sense of Definition 5.16, out of F:

Definition 7.13

For each type α write Aα⇒⟦α⟧F for the set of functions from atoms of type α to ⟦α⟧F. We let ς range over elements of ∏α Aα⇒⟦α⟧F (product over all types) and give ς a permutation action by

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

It is a fact that the set ∏α Aα⇒⟦α⟧F forms a set with a permutation action (Definition 5.2), but it is not necessarily a nominal set (Definition 5.3). Because of how we use the ς in what follows, this will not be a problem.

Where does the action in Definition 7.13 come from, anyway? It is a special case of the standard conjugation action (π·ς)(a) = π·ς(π-1(a)) where we use the trivial action π·x = x for every x ∈⟦α⟧F. This is entirely standard; one place where this is discussed specifically in a ‘nominal’ context is [Gab12b, Definition 2.4.2].

Definition 7.15

Write ⟦β⟧ for

• the set of functions f from ∏α Aα⇒⟦α⟧F to ⟦β⟧F such that for each f there exists a finite set Af such that if ς(a) = ς′(a) for every a ∈Af then f(ς) = f(ς′),

• with a permutation action defined by

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

⟦β⟧ from Definition 7.15 determines a nominal set.

Proof

It is routine to verify that the permutation action is indeed a group action.

Suppose π(a) = a for every a ∈Af (Definition 7.15). By Definition 7.15 (π·f)(ς) = f(π-1·ς). By Definition 7.13 (π-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

Notation 7.17 is clearly in the same spirit as Notation 5.28:

Notation 7.17

Suppose a : α and x ∈⟦α⟧F. Define ς[a:=x] by:

(ς[a:=x])(a) = x (ς[a:=x])(b) = ς(b)
Lemma 7.18

If ς(a) = ς′(a) for every a ∈ supp(f) then f(ς) = f(ς′).

Proof

Suppose ς(a) = ς′(a) for every a ∈ supp(f). Recall the definition of Af from Definition 7.15. It suffices to show that if a ∈Af \ supp(f) and a : α and x ∈⟦α⟧F then f(ς[a:=x]) = f(ς).

Choose fresh b : α (so b ∉Af). By part 1 of Corollary 5.9 (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
Definition 7.19

We define an interpretation I (Definition 5.12) by assigning to each type α the nominal set ⟦α⟧ from Definition 7.15, along with the following data:

• aI(ς) = ς(a).

• fI(ς) = fF.

• If f ∈⟦β⟧ and a ∈Aα then ([a]f)(ς) = λx∈⟦α⟧F.f(ς[a:=x]).

• If f ∈⟦α→β⟧ and g ∈⟦α⟧ then (f • g)(ς) = f(ς)(g(ς)).

• If f, g ∈⟦o⟧ then define f ⪅g when for every ς, f(ς) = ⊤ implies g(ς) = ⊤.

Also, we interpret ⊥, ⊤, ¬, ∧, and ∀α from Definition 2.8 as follows:

⊥I(ς) = ⊥ (f ∧I g)(ς) = f(ς) ∧g(ς)⊤I(ς) = ⊤ (¬If)(ς) = ¬(f(ς)) (∀Iα)(ς) = λy∈⟦α→β⟧F. ⋀x∈⟦α⟧F yx

Above, ∧ and ⋀ refer to the standard greatest lower bound operation on the set {⊥, ⊤}. We now set about checking that Definition 7.19 determines a model in the sense of Definition 5.16. We sketch the non-trivial parts.

Lemma 7.20

Suppose a ∈Aα and f ∈⟦β⟧. Then a ∉ supp([a]f).

Proof

Using Lemma 7.18 it suffices to show that ([a]f)(ς[a:=x]) = ([a]f)(ς) for all ς. This follows from the definitions, because the information in ς(a) gets overwritten by [a]f.End of proof

Lemma 7.21

Definition 7.19 is equivariant, that is:

• π·aI = (π(a))I.

• π·fI = fI for f one of ⊥, ∧, or ∀α.

• π·[a]f = [π(a)]π·f.

• π·(f • g) = (π·f) • (π·g).

Proof

We consider each case in turn:

• (π·aI)(ς) = (π-1·ς)(a) = ς(π(a)) and (π(a))I(ς) = ς(π(a)).

• We consider just the case of ∀α. We note that ∀Iα(ς) = ∀Iα(ς′) for all ς and ς′. It follows that π·∀Iα = ∀Iα.

• We reason as follows:

(π·[a]f)(ς) = ([a]f)(π-1·ς) = λx∈⟦α⟧F.f((π-1·ς)[π(a):=x]) ([π(a)]π·f)(ς) = λx∈⟦α⟧F.f((π-1·ς)[π(a):=x])

• The case of f • g is routine.End of proof

Recall from Notation 5.14 that f[a↦→g] is syntactic sugar for ([a]f) • g. We unpack this concretely:

Lemma 7.22

Suppose f ∈⟦α→β⟧ and a ∈Aα and g ∈⟦α⟧. Then (f[a↦→g])(ς) = f(ς[a:=g(ς)]).

Proof

We just unpack Definition 7.19:

(([a]f) • g)(ς) = ([a]f)(ς)(g(ς)) = f(ς[a:=g(ς)])End of proof
Remark 7.23

Note in passing that if f, g ∈⟦o⟧ then f ≈g if and only if f = g so the functional model (unlike the syntactic model of Subsection 7.1) is extensional on truth-values (cf. Remark 5.18).

Proposition 7.24

Definition 7.19 satisfies the axioms of Figures 7 and Figure 8.

Proof

We use Lemma 7.22 without comment:

• Rule (moda). (aI[a↦→h])(ς) = (ς[a:=h(ς)])(a) = h(ς).

• Rule (mod#). Suppose a ∉ supp(f). By Lemma 7.18 f(ς) = f(ς[a:=h(ς)]).

• Rule (modapp). (f ′ • f)(ς[a:=h(ς)]) = f ′(ς[a:=h(ς)])(f(ς[a:=h(ς)])).

• Rule (mod[]). Suppose c ∉ supp(h).

(([c]f)[a↦→h])(ς) =λg.f(ς[c:=g(ς), a:=h(ς)]) Def. 7.19, Lem. 7.22([c](f[a↦→h]))(ς) =λg.f(ς[c:=g(ς), a:=h(ς[c:=g(ς))]) Def. 7.19, Lem. 7.22=λg.f(ς[c:=g(ς), a:=h(ς)]) Lemma 7.18

• Rule (modid). (f[a↦→aI])(ς) = f(ς[a:=ς(a)]) = f(ς).

• (Commute), (Assoc), and (Huntington) are routine.

• Rules (∀E) and (∀∧) are routine.

• Rule (∀∨). Suppose a : α and a ∉ supp(g) and f, g ∈⟦o⟧. Then

(∀α • [a](f ∨g))(ς) =⋀x∈⟦α⟧F(f(ς[a:=x]) ∨g(ς[a:=x]))Definition 7.19=⋀x∈⟦α⟧F(f(ς[a:=x]) ∨g(ς)) Lemma 7.18=(⋀x∈⟦α⟧F f(ς[a:=x])) ∨g(ς) Fact=((∀α • [a]f) ∨g)(ς) Definition 7.19End of proof
Theorem 7.25

Definition 7.19 determines a model in the sense of Definition 5.16.

Proof

This is Lemmas 7.20 and 7.21 and Proposition 7.24.End of proof

8. Choice

We consider how Hilbert’s ϵ can be accommodated in our framework.

A word on notation: we write ϵ for the choice constant in syntax (Definition 8.1), and the ever-so-slightly-more-italic ε for a choice function in semantics (Definition 8.6).

8.1. Syntax and axiom

In Definition 2.8 we assumed a fixed but arbitrary set of constants (so long as it contained ⊥, ∧, and ∀α). Now we add to this list:

Definition 8.1

For each type α assume a constant ϵα: (α→o)→o. Write ϵα[a]r as ϵαa.r or ϵa.r.

Add to the definition of =αβη in Figure 2 the following axiom (and change =αβη to =αβηε accordingly):

(stxϵ) ∀a.φ =αβηε φ[a↦→ϵa.¬φ]

We call this syntax and the notion of equality =αβηε a syntax with choice.

Remark 8.2

Recall from Notation 2.15 that ∃a.φ is syntactic sugar for ¬(∀α[a]¬φ) (for some α), so an alternative to (stxϵ) is ∃a.φ =αβηε φ[a↦→ϵa.φ]. These expressions are recognisable as Hilbert and Bernays’ formulae (ε2) (for ∀) and (ε1) (for ∃) of [HB70, page 15].

Remark 8.3

The reader familiar with nominal techniques might wonder: are nominal techniques not supposed to be inconsistent with choice? For instance [Gab11a, Theorem 10.11] proves that the axiom of choice is inconsistent with the axioms underlying nominal techniques.19

The choice used here is an equivariant choice, which is consistent with nominal techniques; see Example 8.5. This makes Lemma 8.4 particularly relevant:

Lemma 8.4

Suppose a : α. Then:

• π·(ϵa.φ) = ϵπ(a).π·φ.

• (ϵa.φ)[b↦→s] =αβηε ϵa.(φ[b↦→s]) provided a ∉ fa(s).

Proof

For the first part we unpack Definition 2.20, bearing in mind that ϵα is just a constant symbol (one of the f from Definition 2.8):

π·(ϵa.φ) = π·(ϵα[a]φ) = (π·ϵα)π·[a]φ = ϵα[π(a)]π·φ = ϵπ(a).π·φ.

For the second part we unpack Figure 2, reasoning as follows:

(ϵa.φ)[b↦→s] = (ϵα[a]φ)[b↦→s] Definition= ϵα[b↦→s](([a]φ)[b↦→s]) (stxapp)= ϵα([a](φ[b↦→s])) (stx#), (stx[]), a∉fa(s)= ϵa.(φ[b↦→s]) DefinitionEnd of proof
Example 8.5

We give concrete examples of equivariant and non-equivariant choice:

1. Non-equivariant choice. Consider the set of all unordered pairs of distinct atoms P ⊆ pow(A) (pow is from Example 5.4). So for example {a, b} ∈P and {a} ∉P and {a, b, c} ∉P. Then it is a fact that no choice function f from P to A is equivariant. That is, for every choice function f there exist π and a and b such that π(f({a, b})) ≠ f({π(a), π(b)}).

2. Equivariant choice. Consider the set of all unordered pairs of distinct natural numbers N ⊆N. So for example {1, 2} ∈N and {1} ∉N and {1, 2, 3} ∉N. Give N the trivial permutation action π·x = x. Then every choice function g from N to N (e.g. g mapping {x, y} to the lesser of x and y) is equivariant. That is, π·(g({x, y})) = g({π·x, π·y}). Here, the choice function is equivariant because the permutation actions are trivial, or more loosely: there are no atoms to permute.

3. Equivariant choice, with atoms. Consider the nominal set A ⊗A of ordered pairs of distinct atoms, thought of as a two-element lists. Then there is a natural equivariant choice function which maps (a, b) to a.

Examples 2 and 3 might look silly, but in fact they are not. There is nothing inherently non-equivariant about choice, even choosing elements involving atoms—if we do so symmetrically, that is, if we do not have to create order on atoms to do so. In example 2 above, numbers are inherently ordered; in example 3 we assumed the order was packaged with the input as a pair, so that we can canonically and equivariantly choose the ‘first element’ of the pair.

Two more elaborate examples of equivariant choice functions are in Subsections 8.3.1 and 8.3.2. However, the principle on which they work remains the same (see Remark 8.11).

8.2. Denotation

Now we show how choice gets interpreted denotationally. Fix a model I.

Definition 8.6

A choice function εα is an equivariant function in ⟦α→o⟧ →⟦α⟧ which satisfies:

1. (∀Iα • [a]z) ≈z[a↦→εα([a]¬z)] for every z ∈⟦o⟧ and a : α.

2. εα([a]z)[b↦→y] = εα([a](z[b↦→y])) for every z ∈⟦o⟧ and a : α, and every β, b : β, and y ∈⟦β⟧.

Say that I has choice functions when it has a choice function for every α.

Remark 8.7

It may or may not be the case that εα can be represented internally in I in the sense that there exists some family of elements xα ∈⟦(α→o)→α⟧ such that

xα • f = εα(f) for every f ∈⟦α→o⟧.

Suppose there is. Then we can interpret ϵα from Subsection 8.1 by taking ϵIα = xα:

Theorem 8.8

If I has choice functions then it has maximisers (Definition 6.9).

Proof

It suffices to show that for every a : α and z ∈⟦o⟧ there exists some x with z[a↦→x] = ∀Iα • [a]z. We take x = εα([a]¬z).End of proof

8.3. The syntactic and functional models with choice functions

Theorems 7.11 and 7.25 suffice for interpreting hypersequents and the rules (α∗), (β∗), (γ∗), and (δ−∗)—that is, up to but not including Section 4.

To interpret the (δX∗) rules from Definition 4.11, and thus to interpret maximising hypersequents, we need models with maximisers. By Theorem 8.8 it suffices to show a model has choice functions (Definition 8.6).

This can be accommodated in the syntactic model and is already present in the functional model.20

8.3.1. Choice in the syntactic model

For the syntactic model, we use the syntax with choice ϵα from Definition 8.1. By Theorem 8.8 it suffices to show that S has choice functions. We obtain this by replay-ing the proofs of Subsection 7.1 for syntax and syntactic equivalence with choice =αβηε from Definition 8.1; the extra axiom (stxϵ) from Definition 8.1 changes nothing in the proofs above, and by construction we get a choice function, which maps [[a]φ]αβηε ∈⟦o⟧S equivariantly (by part 1 of Lemma 8.4) to [ϵa.φ]αβηε ∈⟦type(a)⟧S.

8.3.2. Choice in the functional model

For the functional model (Definition 7.19) we construct a choice function by hand as follows:

Definition 8.9

For each y ∈⟦α→o⟧F make some choice ϵ(y) of element x ∈⟦α⟧F such that y(x) = ⊤, if such an x exists, and otherwise let ϵ(y) be any element of ⟦α⟧F.

Define εα to map f ∈⟦α→o⟧ to λς.ϵ(f(ς)) ∈⟦α⟧. Thus,

εα(f)(ς) = ϵ(f(ς)).
Theorem 8.10

The family of functions εα : ⟦α→o⟧→⟦o⟧ is a choice function in the sense of Definition 8.6.

Proof

It suffices to check the following:

1. Proof that π·(εα • f) = εα • (π·f). We just manipulate definitions, as follows:

(π·(εα • f))(ς) = (εα • f)(π-1·ς) Definition 7.15= ϵ(f(π-1·ς)) Definition 8.9= ϵ((π·f)(ς)) Definition 7.15= εα • (π·f). Definition 8.9

2. Proof that (∀a.z) ≈z[a↦→εα([a]¬z)]. It suffices to show that (∀a.z)(ς) = ⊤ implies (z[a↦→εα([a]¬z)])(ς) = ⊤. This follows by construction from Definition 8.9.

3. Proof that εα(f)[a↦→g] = εα(f[a↦→g]).

(εα(f)[a↦→g])(ς) = εα(f)(ς[a:=g(ς)]) = ϵ(f(ς[a:=g(ς)]))(εα(f[a↦→g]))(ς) = εα(f[a:=g])(ς) = ϵ(f(ς[a:=g(ς)]))End of proof
Remark 8.11

From the point of view of equivariant choice, the construction of the maximising element εα(f) in Definition 8.9 is a glorified version of part 2 of Example 8.5: ⟦α⟧F from Definition 7.12 is an ‘ordinary set’ (or if the reader prefers; it is a nominal set with the trivial action π·x = x), and we can choose elements from it freely without affecting equivariance.

In contrast, the construction of the maximising element [ϵa.φ]αβηε in Subsection 8.3.1 resembles part 3 of Example 8.5: terms may certainly contain atoms and have a non-trivial permutation action, but we can still choose a canonical maximising term ϵa.φ, and indeed, that is precisely what ϵ is designed to provide.

9. Conclusions

We have presented a new, more abstract syntax and semantics for δ-rules. We are not trying to be algorithmically efficient, but we are optimising for nice and compact syntax and semantics. This is quite hard to get right using ordinary syntax and semantics (e.g. using simply-typed λ-calculus and sets and functions between them). Instead we used nominal terms and nominal sets.

The ‘nominal’ approach is based not on functions but on symmetric names. Thus, nominal sets are sets with a group action, and nominal terms include variables X with free atoms pms(X) that are considered to occur in X (e.g. the free atoms of X is pms(X)) but they occur in no particular order.21 As discussed in Remark 4.10, this gives the nominal syntax an expressivity usually attained by Skolemisation or raising, but pms(X) is not ordered (unlike arguments to a function) and the nominal semantics are first-order.

Nominal semantics may be unfamiliar, but they are fairly elementary; the technical requirements are no greater than for other semantics. Open terms map directly to open elements; and name-related aspects of nominal terms, like permutations and atoms-abstraction, map directly to corresponding semantic operations on nominal sets.

Because of this, operations that we are accustomed to seeing only on syntax, like substitution and binding, now also occur in the semantics.

The similarity of syntax and semantics can make it look like nothing is happening: Definition 5.16 could be mistaken for a Hilbert axiomatisation; Definition 5.27 might seem to just translate syntax trivially to semantics. But this is deceptive: Subsection 7.2 constructed a functional model, and if that model is least somewhat familiar, in [GM11] and even more so in [Gab11b] we build (topological) models that are not derived from either syntax or functions, in which substitution and abstraction are interpreted completely independently of the apparatus of syntax and functions—and yet they still satisfy the axioms and have a natural construction.

Thus when we have written z[a↦→x] in this paper and read this ‘z with a replaced by x’, this is an algebraic generalisation of substitution22 which operates on semantic objects.

What this contributes to proof-search is simplicity: proof-search is by design full of different kinds of variables that interact in complex ways. Our denotation allows us to interpret this directly—and in an implementation and algorithm-independent manner—in semantics.

9.1. Nominal provenance of this paper

Proof-search. This paper pulls together ideas from a number of sources, notably the specific view of proof-search represented for instance in [Wir04] (which uses a broadly higher-order semantics for variable-dependency) and [Wir11] (which takes a more nominal perspective).

Setting the specific application to proof-search aside for now: where does the underlying nominal machinery of this paper come from?

Nominal algebra and one-and-a-halfth order logic. The idea of equational axiomatisations of mathematics in a nominal context goes back to nominal algebra, which was developed to axiomatise capture-avoiding substitution and first-order logic [GM06b, GM06a], which in turn goes back to the nominal rewrite systems of [FGM04, FG07].

This was developed further in [GM08b, GM08a]. In particular, the axiomatisation in Figures 7 and 8 is a direct descendent of the one-and-a-halfth order logic of [GM06b, GM08b]. This technology was used in [GM08c, GM10] to represent schemas of first-order derivations.

In a nutshell: [GM08b] considered derivability in the presence of nominal unknowns X, whereas [GM08c] also treated the proof-theory. This paper considers both of these, and adds semantics for how we look for instantiations of the X.23

Permissive-nominal syntax. The work in [GM08c, GM10] motivated the development of permissive-nominal terms, an idea which goes back to [DGM09b, DGM09a, DGM10]. This is pulled together in [DG12a] to give a finite axiomatisation of substitution, first-order logic, and arithmetic in permissive-nominal logic.

In all the above, there had been no explicit consideration of proof-search. It is simplistic, but reasonable, to sum things up as follows: this paper uses the same basic syntactic (and semantic; see below) ideas, but instead of studying, say, incomplete derivation schemas (one-and-a-halfth order logic) or r = s (nominal algebra) or ∀X (permissive-nominal logic), we study hypersequents and maximisation conditions X↑[a]φ, making X behave explicitly like a proof-search variable.

Models. An investigation of models followed, in several styles. This includes translations of theories in permissive-nominal syntax to higher-order terms [GM09b, DG12b]—see also [LV12], which translates a simpler syntax and does not consider theories, but follows the same general idea—and it includes the topological model of first-order logic [Gab11b] mentioned above (essentially, a topological treatment of [GM08b] and of a first-order version of Figures 7 and 8 from this paper).

Nominal Henkin semantics and permissive-nominal logic. Of most relevance to this paper is the nominal Henkin semantics of [GM11], which considered nominal models of αβ-equivalence. That and permissive-nominal logic [DG10, DG12a] are the most immediate ancestors of this paper. So for the expert in nominal techniques we conclude with a brief technical comparison of some specific design choices of these papers.

In [GM11] atoms and variables do not have a fixed type, so we need typing contexts. This paper fixes a global typing context in Definition 2.3. Concretely that means that Definitions 3.3 and 5.9 of [GM11] and the associated proofs have subscripts Γ (typing contexts), whereas Definition 5.12 of this paper and the associated proofs, do not. This is purely a design issue. The choice made here suffices for our needs and gives a cleaner presentation.

Permissive-nominal logic syntax [DG10, DG12a] has, like this paper, a single fixed typing (we called it a sorting). For instance Definition 3.20 of [DG12a] has no Γ subscripts, like Definition 5.12 here. The major difference is that permissive-nominal logic sorts are first-order: permissive-nominal logic has no function-sorts, and it has α-equivalence but not the βη-equivalence from Figure 2. This is deliberate: permissive-nominal logic has a quantifier ∀X and β- and η-equivalence are axiomatisable, which was part of the design brief of permissive-nominal logic.

Of course the specifics of hypersequents, maximisation conditions, and application to proof-search considered in this paper, are new to nominal techniques.

Variables as well-orderings of atoms. A word on the broader mathematical context. In [Gab12a] we identify X with a well-ordering of pms(X). From this perspective, the instantiation action for variables (Definition 2.27, in this paper) is a compact way to present an infinite Skolemisation (Subsections 4.2 and 4.3 of Chapter 1 of [DGHP99] or Definition 53 of Chapter 3 of [DGHP99]) or infinite raising (Section 5 of [Mil92]), or a de Bruijn index [dB72].

Indeed if we take a1, . . . , an to be pms(X) in some order then intuitively X =αβη fa1. . . an where f = λa1. . . . λan.X. Instantiating X is like substituting f for a ‘closed term’ of higher order (a term r with fa(r) = ∅).

However, X is not identical to Skolemisation:

• There is no order on pms(X) and the type of X does not change depending on its permission set.

• The nominal semantics for atoms and atoms-abstraction are inherently first-order. In [GM11] we illustrate this with a sound and complete Henkin semantics for higher-order logic, resembling the semantics in Section 5. See also the first-order meaning given to nominal atoms-abstraction in [GP01, Lemma 5.1].

For a more general view see [DG10, DG12a, Gab12b]. To see nominal instantiation viewed as an equivariant function see [Gab12b, Lemma 3.4.3] or [Gab12a, Lemma 2.33].

To see explicit translations of permissive-nominal theories to higher-order theories based on these ideas, see [GM09b, DG12b]—in which it is clear how the nominal permutative properties of atoms are lost in the translation [DG12b, Subsection 1.2].

9.2. Why permutations

In Remark 2.14 we justified the use of moderated variables π·X, and noted that (b a)·X where b ∉ pms(X) models the informal vernacular ‘t[y/x] where we take y not free in t’.

We noted that nominal techniques use permutations (b a) rather than the (more natural—or rather, more familiar) atoms-renaming [b/a], or even substitution [a↦→b].

Why? What are the advantages of the permutative model of names and binding? The underlying point is that groups are a more restricted structure than monoids, and they have inverses. Atoms-renamings and substitutions form monoids, and do not always have inverses. As is often the case, favouring the more restricted class of structures gives us better behaviour and more theorems.

We take a moment to list just two concrete ways in which that helps us: Thanks to the use of a group of permutations instead of a monoid of atoms-renamings, atoms can conveniently be identified with urelemente and their natural permutation action on the Fraenkel-Mostowski sets universe. This is a fancy way of saying that nominal sets from Section 5 are nice to work with.

Also, the permutation action of Definition 2.20 is directly definable on permissive-nominal syntax without triggering α-conversions. Thus, the use of permutations allows us to modularise the definitions; first defining the permutation action and then defining α-equivalence (Definition 2.22), rather than having to define both by a simultaneous induction, as would be the case if we used atoms-renamings.

This does not exhaust the advantages of the nominal treatment of names and bindings. It gives a flavour of its convenience. In two words these are: modularity and foundations.

9.3. Future work

We hope this paper will provide a lingua franca for expressing constructs in proof-search, and more generally for meta-variables in proofs. We can also hope that our nominally symmetric models might help to develop new and improved algorithms, to cross-check soundness of algorithms that are independently developed, or even to help with the general design of theorem-provers.

In [DGM10, Gab12b] we allow infinite permission sets in terms (in this paper pms(X) is taken to be a finite set of atoms). The benefit of allowing ‘larger’ permission sets is not visible in this paper, but when we come to consider induction an infinite stock of atoms may be useful to generate and name as many intermediate lemmas in inductive derivations as we like. That is: in the presence of more complicated notions of derivation, we may not discover all the atoms we require until after we have started constructing a derivation. Thus, it might be useful to allow larger, infinite, permission sets. We might even permit infinite permission sets directly in the semantics.

This is not a problem. Permissive-nominal techniques from [DGM10, DG12a, Gab12b] already assume infinite permission sets. The finite permission sets of this paper are a useful simplification of that idea and they are all we need for now, but if required there should be no difficulty in generalising to ‘larger’ infinite permission sets.

We have not considered completeness. The logic of this paper is higher-order, for which incomplete semantics are standard. However our semantics resembles the nominal Henkin semantics of [GM11] and our semantics might be complete for our rules—perhaps modulo some simple adaptations.

In this paper we tried to be accessible to a broad spectrum of readers, who are not necessarily experts in nominal techniques or even expert in proof-search. Attempting a proof of completeness would have detracted from that, but it remains an interesting question. Thus, for the mathematically and logically inclined, as well as for the implementor, there remains much work to be done to extend and develop on these ideas.

We conclude with a technical point, but one which illustrates the flexibility of our techniques. Our analysis of substitution is fairly simple-minded; we assume atoms-abstraction [a]r and application rs and take r[a↦→s] to be just ([a]r)s. This is fine for some situations—for instance in a mathematical model such as this paper, or in a tactics-driven theorem-prover—but there are other situations—for instance for a confluence proof, or in a dependent type theory—where we might wish to distinguish between those reducts that are there because we are trying to reduce, and those reducts that are there because we have not yet reduced them. Then, we might like to introduce an explicit substitution. This raises the question of what X[a↦→r] should reduce to.

One answer is to allow simultaneous substitutions of atoms of terms and suspend these on X (just as we currently suspend permutations as π·X). Another, equivalent but perhaps more elegant answer, is to treat X as a tuple of the atoms in its permission set and X[a↦→r] as that tuple with a replaced by r. More on this in [Gab12a].

For us, these questions are a feature and not a bug: our nominal syntax lets us be as abstract, or as concrete, as we like. We can think about implementation if we want to, or ignore it insouciantly if we do not. This is up to us.

Bibliography

[Avr91] Arnon Avron. Hypersequents, logical consequence and intermediate logics for concurrency. Annals of mathematics and artificial intelligence, 4(3–4):225–248, 1991.

[Avr96] Arnon Avron. The method of hypersequents in the proof theory of propositional non-classical logics. In Wilfrid Hodges, Martin Hyland, Charles Steinhorn, and John Truss, editors, Logic: from foundations to applications, pages 1–32. Oxford University Press, 1996.

[BBK04] Christoph Benzmüller, Chad E. Brown, and Michael Kohlhase. Higher-order semantics and extensionality. Journal of Symbolic Logic, 69:1027–1088, 2004.

[BF95] Matthias Baaz and Christian G. Fermüller. Non-elementary speedups between different versions of tableaux. In Proceedings of the 4th International Workshop on Theorem Proving with Analytic Tableaux and Related Methods (TABLEAUX’95), pages 217–230. Springer, 1995.

[BHS93] Bernhard Beckert, Reiner Hähnle, and Peter H. Schmitt. The even more liberalized delta-rule in free variable semantic tableaux. In Georg Gottlob, Alexander Leitsch, and Daniele Mundici, editors, Proceedings of the third Kurt Gödel Colloquium (KGC’93), volume 713 of Lecture Notes in Computer Science, pages 108–119. Springer, 1993.

[BU07] Stefan Berghofer and Christian Urban. A head-to-head comparison of de Bruijn indices and names. Electronic Notes in Theoretical Computer Science, 174(5):53–67, 2007.

[CA00] Domenico Cantone and Marianna Asmundo. A further and effective liberalization of the δ-rule in free variable semantic tableaux. In Ricardo Caferra and Gernot Salzer, editors, Automated Deduction in Classical and Non-Classical Logics, volume 1761 of Lecture Notes in Computer Science, pages 408–414. Springer, 2000.

[Che05] James Cheney. Nominal logic and abstract syntax. SIGACT News (logic column 14), 36(4):47–69, 2005.

[CNA07] Domenico Cantone and Marianna Nicolosi-Asmundo. A sound framework for delta-rule variants in free variable semantic tableaux. Journal of Automated Reasoning, 38:31–56, 2007.

[dB72] Nicolaas G. de Bruijn. Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indagationes Mathematicae,

5(34):381–392, 1972.

[DG10] Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic. In Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2010), pages 165–176. ACM Press, 2010.

[DG12a] Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic (journal version). Transactions on Computational Logic, 13(3), 2012.

[DG12b] Gilles Dowek and Murdoch J. Gabbay. PNL to HOL: from the logic of nominal sets to the logic of higher-order functions. Theoretical Computer Science, 451:38–69, 2012.

[DGHP99] Marcello D’Agostino, Dov M. Gabbay, Reiner Hähnle, and Joachim Posegga, editors. Handbook of Tableau Methods. Kluwer, 1999.

[DGM09a] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification. Technical Report HW-MACS-TR-0062, Heriot-Watt, February 2009.

[DGM09b] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification. In Proceedings of the 24th Italian Conference on Computational Logic (CILC’09), 2009.

[DGM10] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification: an infinite, co-infinite approach to nominal techniques (journal version). Logic Journal of the IGPL, 18(6):769–822, 2010.

[Die11] Dominik Dietrich. Proof Planning with Compiled Strategies. Phd thesis, Dept. Informatics, Saarland University, 2011.

[FG07] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting (journal version). Information and Computation, 205(6):917–965, June 2007.

[FGM04] Maribel Fernández, Murdoch J. Gabbay, and Ian Mackie. Nominal Rewriting Systems. In Proceedings of the 6th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming (PPDP 2004), pages 108–119. ACM Press, August 2004.

[Fit90] Melvin Fitting. First-order Logic and Automated Theorem Proving. Texts and monographs in computer science. Springer, 1 edition, 1990. Second edition is [Fit96].

[Fit96] Melvin Fitting. First-order Logic and Automated Theorem Proving. Texts and monographs in computer science. Springer, 2 edition, 1996. First edition is [Fit90].

[GA99] Martin Giese and Wolfgang Ahrendt. Hilbert’s ϵ-terms in automated theorem proving. In Neil Murray, editor, Automated Reasoning with Analytic Tableaux and Related Methods, volume 1617 of Lecture Notes in Computer Science, pages 662–662. Springer, 1999.

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

[Gab07b] Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205(7):982–1011, July 2007.

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

[Gab11b] Murdoch J. Gabbay. Stone duality for First-Order Logic: a nominal approach. In Howard Barringer Festschrift. December 2011.

[Gab12a] Murdoch J. Gabbay. Meta-variables as infinite lists in nominal terms unification and rewriting. Logic Journal of the IGPL, 2012.

[Gab12b] Murdoch J. Gabbay. Nominal terms and nominal logics: from foundations to meta-mathematics. In Handbook of Philosophical Logic, volume 17. Kluwer, 2012.

[Gab12c] Murdoch J. Gabbay. Unity in nominal equational reasoning: The algebra of equality on nominal sets. Journal of Applied Logic, 10:199–217, June 2012.

[Gen35] Gerhard Gentzen. Untersuchungen über das logische Schließen [Investigations into logical deduction]. Mathematische Zeitschrift 39, pages 176–210,405–431, 1935. Translated in [Sza69], pages 68–131.

[GL09] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus (extended version). Information and computation, 207:1369–1400, December 2009.

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

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

[GM07] Murdoch J. Gabbay and Aad Mathijssen. A Formal Calculus for Informal Equality with Binding. In

WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of Lecture Notes in Computer Science, pages 162–176. Springer, July 2007.

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

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

[GM08c] Murdoch J. Gabbay and Dominic P. Mulligan. One-and-a-halfth Order Terms: Curry-Howard for Incomplete Derivations. In Proceedings of 15th Workshop on Logic, Language and Information in Computation (WoLLIC 2008), volume 5110 of Lecture Notes in Artificial Intelligence, pages 180–194. Springer, June 2008.

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

[GM09b] Murdoch J. Gabbay and Dominic P. Mulligan. Universal algebra over lambda-terms and nominal terms: the connection in logic between nominal techniques and higher-order variables. In Proceedings of the 4th International Workshop on Logical Frameworks and Meta-Languages (LFMTP 2009), pages 64–73. ACM, August 2009.

[GM10] Murdoch J. Gabbay and Dominic P. Mulligan. One-and-a-halfth Order Terms: Curry-Howard for Incomplete Derivations (journal version). Information and Computation, 208:230–258, March 2010.

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

[GP99] Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax Involving Binders. In Proceedings of the 14th Annual Symposium on Logic in Computer Science (LICS 1999), pages 214–224. IEEE Computer Society Press, July 1999.

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

[GTL89] Jean-Yves Girard, Paul Taylor, and Yves Lafont. Proofs and types. Cambridge University Press, 1989.

[HB70] David Hilbert and Paul Bernays. Grundlagen der Mathematik (volume II). Number 50 in Grundlehren der mathematischen Wissenschaften. Springer, second edition, 1970.

[Hen50] Leon Henkin. Completeness in the theory of types. Journal of Symbolic Logic, 15:81–91, 1950.

[HS94] Reiner Hähnle and Peter H. Schmitt. The liberalized δ-rule in free variable semantic tableaux. Journal of Automated Reasoning, 13(2):211–222, 1994.

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

[Kan63] Stig Kanger. A simplified proof method for elementary logic. In Jörg Siekmann and Graham Wrightson, editors, Automation of Reasoning volume 1 - classical papers on Computational Logic 1957-1966, pages 364–371. Springer, 1963.

[LV12] Jordi Levy and Mateu Villaret. Nominal unification from a higher-order perspective. Transactions on Computational logic (TOCL), 13(2), 2012.

[McC97] William McCune. Solution of the Robbins problem. Journal of Automated Reasoning, 19:263–276, 1997.

[Mil92] Dale Miller. Unification under a mixed prefix. Journal of Symbolic Computation, 14(4):321–358, 1992.

[MV95] Wilfried Meyer-Viol. Instantial Logic — An Investigation into Reasoning with Instances. PhD thesis, University of Utrecht, 1995. ILLC dissertation series 1995–11.

[Pra60] Dag Prawitz. An improved proof procedure. Theoria: A Swedish Journal of Philosophy, 26:102–139, 1960.

[Pra83] Dag Prawitz. An improved proof procedure. In Jörg Siekmann and Graham Wrightson, editors, Automation of Reasoning volume 1 - classical papers on Computational Logic 1957-1966, pages 159–199. Springer, 1983.

[Sha85] Stewart Shapiro, editor. Intensional mathematics. North-Holland, 1985.

[Smu68] Raymond Smullyan. First-order logic. Springer, 1968. Reprinted by Dover, 1995.

[Sza69] M. E. Szabo, editor. Collected Papers of Gerhard Gentzen. North Holland, 1969.

[UPG03] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. In Proceedings of the 17th International Workshop on Computer Science Logic (CSL 2003), volume 2803 of Lecture Notes in Computer Science, pages 513–527. Springer, December 2003.

[UPG04] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, September 2004.

[Urb08] Christian Urban. Nominal reasoning techniques in Isabelle/HOL. Journal of Automatic Reasoning, 40(4):327–356, 2008.

[Wal90] Lincoln A. Wallen. Automated Proof Search in Non-Classical Logics — efficient matrix proof methods for modal and intuitionistic logics. MIT Press, 1990. Phd thesis.

[Wir04] Claus-Peter Wirth. Descente infinie + Deduction. Logic Journal of the IGPL, 12(1):1–96, 2004.

[Wir11] Claus-Peter Wirth. A simplified and improved free-variable framework for Hilbert’s epsilon as an operator of indefinite committed choice. CoRR, abs/1104.2444, 2011.

Notes

1This paper will consider classical logic, so ∃ is considered a dual of ∀. Nothing in this paper will depend on that, and a separate treatment of ∃ would be quite possible. ↩

2Like this: (∀y.P(y, x))[y/x] = ∀y′.P(y′, y). For the specific definitions on the syntax of this paper, see Subsection 2.2 and in particular Figure 2. ↩

3There is a potentially confusing terminology clash here. The first author was brought up on sequents, λ-calculi, and semantics, and calls X an existential variable. The second author grew up in the theorem proving community where Smullyan’s α, β, γ, and δ provides a lingua franca, in which X is called a free variable. This clashes with the notion of ‘free variables of’ of a predicate or λ-term. Since we are trying to straddle two communities, we give both possible names where there is any possibility of doubt. In any case, wherever the reader sees X in this paper, this is a variable we try to instantiate to make a proof work out. ↩

4In our notation in this paper, based on variable-conditions and permission sets instead of Skolemisation, there is no obvious difference from the rule for a calculus without free variables [Fit90, Section 6.1], because our notion of ‘free atoms of’ includes the permission sets of the free/existential variables in Γ, ∆. ↩

5This paper is not about Nominal Isabelle [Urb08], which is an implementation of nominal abstract syntax from [GP99, GP01] in Higher-Order Logic. This paper is about proof-search using nominal terms (which is not the same thing as nominal abstract syntax) with semantics in nominal sets. What these applications have in common is a requirement to handle rich name-based behaviour, which in both cases is addressed with nominal techniques. ↩

6[Wir11] simplifies [Wir04] using ‘nominal’ ideas, and documents this process in successive revisions (the authors are grateful to a SICSA grant which supported this work). The current paper follows a similar project but from the other direction by adding ideas from [Wir04] to nominal syntax and semantics. ↩

7In [UPG04, DGM10] variables are called unknowns. ↩

8This terminology is consistent with [GP01]. This is also called a transposition. ↩

9Permissive-nominal terms were presented in [DGM09b] (conference paper), [DGM09a] (technical report), and [DGM10] (journal paper). The conference and journal papers versions probably have the better exposition, but the technical report includes exhaustive proofs. ↩

10Hypersequents were independently invented by Michael Gabbay, who approached the first author in great excitement at his new discovery/invention, which he called ‘hypersequents’. Sadly, he had committed the sin of being born too late; older people get all the fun. ↩

11This is just like the comma , and ⊢ of ordinary logic sequents φ1, . . . , φm ⊢ψ1, . . . , ψn, where ⊢ is interpreted as implication and comma on the left is interpreted as conjunction and on the right as disjunction. ↩

12Recall that by permutative convention X and Y are distinct. ↩

13The notion of model in Definition 5.16 will impose futher nominal algebra axioms to make [a]x not just an α-abstractor, but also give it βη-style behaviour. Thus, [a] is destined to model λa. Still, [a]x is no more equal to a functional abstraction than it is equal to a nominal atoms-abstraction. It is just a model. ↩

14Both are empty sets, but of different types. ↩

15A thread of research is devoted to giving X, Y , Z a universal flavour: we can generalise nominal terms with λX or ∀X [GL09, DG12a], or make X behave like a schema variable [GM10] (in the sense of ‘an axiom-schema’). More on this in Subsection 9.1. The interaction between a and X is really about names and capture, and such notions arise in a great number of situations—one of which is proof-search. ↩

16We will know X ∉ fv(φ) by condition 1 in Definition 4.5 (well-foundedness) so (∃a.φ)[X:=s] = ∃a.φ and (φ[a↦→X])[X:=s] = φ[a↦→s]. ↩

17This paper was submitted in 2003. ↩

18Technically, we also need to check that [[a]r]αβη has finite support, so that we can choose a b fresh for it. This also follows from the symmetries of atoms; for the general statement of the relevant nominal meta-principle, see [Gab11a, Theorem 4.7]. ↩

19This observation has an excellent pedigree. Nominal techniques are based on Fraenkel-Mostowski set theory, which was developed specifically to prove the independence of the axiom of choice from the other axioms of set theory (with atoms). Historical notes to the earlier literature are in [Gab11a, Remark 2.22]. ↩

20...provided that your mathematical foundation includes the axiom of choice. If you are not sure whether your foundation includes choice, then it does. ↩

21In [Gab12a] we argue that X is, in some abstract mathematical sense that we make formal, actually a symmetry-breaking operation. ↩

22The axioms are in Figure 7. When reading this figure it is useful to recall the notation used in it, from Notation 5.14. ↩

23There is a little more to it than that. This paper treats a higher-order syntax; that is, we assume βη. ↩