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

FRESH LOGIC: PROOF-THEORY AND SEMANTICS FOR FM AND NOMINAL TECHNIQUES

MURDOCH J. GABBAY

Abstract. In this paper we introduce Fresh Logic, a natural deduction style first-order logic extended with term-formers and quantifiers derived from the FM-sets model of names and binding in abstract syntax. Fresh Logic can be classical or intuitionistic depending on whether we include a law of excluded middle; we present a proof-normalisation procedure for the intuitionistic case and a semantics based on Kripke models in FM-sets for which it is sound and complete.

Contents

1. Introduction 2

2. Semantics I 4

3. Basic definitions and notation 5

3.1. Sorts 5

3.2. Variables and atoms. 6

3.3. (Syntactic) permutations. 6

3.4. Moderated variables. 6

3.5. Terms. 6

3.6. Propositions or formulae. 7

3.7. Contexts. 8

4. Semantics I: Frames 8

4.1. Frames 8

4.2. Semantics of atoms and terms 8

4.3. Comments on the semantics 8

5. Judgements 9

5.1. Inductive definition 9

5.2. Notations used in the inductive definition 9

5.3. Intuition behind the novel aspects of the deduction rules 9

5.4. Slices 11

5.5. Significance of (ExhaustA) 12

6. Example deductions 13

7. Validity and soundness 15

7.1. Semantics II: Models and validity 15

7.2. Basic properties of validity 15

7.3. Validity for some structural rules 16

7.4. Meta-level swapping 17

7.5. Entailment relative to a model and soundness 17

8. Proof normalisation 18

8.1. Overview of the proof 18

8.2. Essential case of ∀ 19

Date: October 9, 2005. This work was inspired by conversations with Dale Miller and Alwen Tiu during a meeting on 11/10/02 at INRIA Rocquencourt. It was funded by INRIA FUTURS, Paris.

8.3. Essential case of π and discussion of (πI) and (πdiff) 20

8.4. Essential case of И 20

8.5. Commutation cases 21

8.6. Proof normalisation 22

9. Completeness 22

9.1. (Small) 22

9.2. (ExhaustA) and (NewA) 24

9.3. Remark on literal equality 25

9.4. Prime theories 25

10. Alternative formulations of Fresh Logic 27

10.1. No swappings or # 27

10.2. Variables x : A in swappings 27

10.3. FM swapping in this document 27

10.4. Иa does not bind a 28

11. Conclusions 29

11.1. Related work 30

11.2. Future work: Proof-terms, higher orders 32

11.3. Self-duality 32

11.4. Vanilla 32

References 32

Appendix A. Formal Inductive Definitions 33

Appendix B. Judgements (sequent style) 34

1. Introduction

In this paper we introduce Fresh Logic, a natural deduction style first-order logic extended with term-formers and quantifiers derived from the FM-sets model of names and binding in abstract syntax [9, 11, 12], developed by the author with A.M. Pitts. We show a proof-normalisation algorithm exists, and demonstrate soundness and completeness with respect to a model in FM-sets.

‘FM’ stands for ‘Fraenkel-Mostowski’, after two authors of papers on set theories very similar to what we call FM-sets (they were interested in proving independence of axioms of set theory [2], in particular the axiom of choice). Recently ‘Nominal’ has replaced ‘FM’ as an umbrella term for the logics and other systems derived from the original FM sets model, probably because it has fewer syllables and no umlauts.

Since this paper is a rock-hard proof-theoretic/semantic macho sets-fest, we keep the umlauts too.

FM-sets models names by a dedicated countably infinite set of names a, b, c ∈A, we give them a technical nomenclature atoms. This appears in Fresh Logic as a dedicated type of atoms A and a countably infinite set of atoms constant symbols a, b, c, . . . (they are not necessarily quite constant symbols, but we shall discuss that in due course).

FM-sets have a swapping action allowing us to rename (by swapping) atoms in sets. Fresh Logic has a corresponding term-former whose behaviour in the deduction system is to swap atoms constant symbols in terms. It is a fact that semantic swapping in FM-sets has excellent logical properties [12, 26]—Fresh Logic is designed to take advantage of this in its proof-theory.

Finally, FM-sets give rise to a derived quantifier И meaning ‘for all but a finite set of names’. Fresh Logic adds a quantifier И to the usual ∀ and ∃ of first-order logic. We shall see how swapping is vital to proof-normalisation for И, lending proof-theoretic support to the FM-sets model.

Fresh Logic can be classical or intuitionistic depending on whether we include a law of excluded middle; we present a proof-normalisation procedure for the intuitionistic case and a semantics based on Kripke models in FM-sets for which it is sound and complete. The core of Fresh Logic is first-order logic, unchanged.

The style of FM techniques has been “to be within ϵ of standard practice”. The most developed FM system is FreshML [6]. FreshML programs look just like the informal specifications we would normally write; issues of α-equivalence and renaming are smoothly delegated to the compiler. In the same spirit, we want

a logic whose judgements look like normal First-Order Logic, whose language is augmented with the FM И-quantifier, and with a good proof theory and semantics.

‘Good’ proof theory here means proof normalisation, Theorem 8.9, and also perhaps that the proof be simple and follow standard lines. Similarly for semantics. Soundness and completeness Theorem 7.7 and Theorem 9.12 follow standard lines, up to a point.

Outline of the paper.

§2 We introduce a selection of relevant basic notions of FM-sets semantics (developed in detail in [12, 28]); semantic atoms A, sets with a swapping action, support as a syntax-free notion of ‘free names of’, the finite support property, the И quantifier, the difference set of two permutations of A, equivariant functions, and freshness #. §3 We define the terms, predicates, and contexts of Fresh Logic. §4 Fresh Logic is intuitionistic. Its semantics consists of Kripke models of so-called ‘possible worlds’, which we call ‘frames’; we define their structure. §5 We define judgements, and inductively define valid judgements. This includes intro- and elim-rules for the И quantifier. §6 We give some example derivations. §7 We develop a notion of validity for judgements with respect to a Kripke model semantics whose possible worlds are frames and whose accessibility is a notion of frame map. §8 We give a proof-normalisation algorithm for Fresh Logic. §9 We discuss how to build a standard model of a Fresh Logic theory out its syntax and use this model to prove completeness. We discover that completeness demands we add an extra axiom (Small), which we analyse. §10 We discuss alternatives to the many design decisions involved in making Fresh Logic.

Aside from a conclusions and related work section, there are also two appendices: Appendix A includes some definitions deferred from the text, Appendix B is a sequent-style presentation of Fresh Logic. We have not proved cut-elimination for the sequent presentation in full detail, but we have investigated it and expect it to work smoothly.

2. Semantics I

Definition 2.1 (The basics).

Fix a countably infinite set of atoms a, b, c, . . . ∈ A. For a, b ∈A a swapping (a b) is a function from A to A defined by

(b a) · adef= b(1)(b a) · bdef= a(b a) · cdef= c c ≢a, b.

Write PA for the set of finite permutations of A; the group generated by the (a b) with functional composition ◦ as the group action. Write Id for the identity function on A, which is of course the unit of the group (PA, ◦).

This concludes the basic notation. We now rehearse some basic FM theory:

Definition 2.2 (Nominal Set).

A Nominal Set is a pair ⟨X, ·⟩ of an underlying set X and permutation action · (written infix) of type PA × X →X. The permutation action satisfies

(2) ∀π, π′, x. π · (π′ · x) = π ◦π′ · x and Id · x = x

(the standard rules for a permutation action) along with a “smallness condition”

(3) ∀x ∈X. ∃S ∈ FinA. S supports x.

We may write just X for ⟨X, ·⟩. Here we write FinA for the set of finite subsets A, B, C, S ⊆A. We define

S supports x means ∀a, b ∉S. (a b) · x = x.

So (3) says every x has a finite supporting set, (3) is also called the finite support property. It can be proved [8, 12] that there is then a smallest supporting set. We call this the support of x and write it S(x). As we would expect we can construct it as ⋂ {S⏐⏐ S supports x}.

• A with the natural functional action of permutations, is an FM set. S(a) = {a}.

• The set of terms t of the λ-calculus up to α-equivalence with variables modelled by atoms in the α-equivalence classes of abstract syntax, is an FM set: S(t) coincides with fv(t). An α-equivalence class of terms does not contain bound names, in the sense that the equivalence class quotients over them.

• The set of terms t of the λ-calculus not up to α-equivalence with variables modelled by atoms in the abstract syntax, is an FM set: S(t) coincides with the names occurring free or bound in t.

• Any set of finitely branching trees with nodes labelled by elements of FM sets, is an FM set. The support is the union of the support of the labels, the swapping action acts pointwise on the labels. We shall see many examples of these in this paper: terms of Fresh Logic, formulae of Fresh Logic, derivations (proofs) of Fresh Logic, even models of Fresh Logic.

• The set of finite subsets of an FM set is an FM set. Swapping acts pointwise on the elements, the support of a finite set is the union of the support of its elements (proof omitted).

• FinA is an FM set with the pointwise set action. For U ⊆A a finite set of atoms, S(U) is equal to U.

• By calculation, for U ⊆A as above, S(A \ U) is also equal to U.

We now introduce the FM И-quantifier: write

(4) Иa. Φ(a) for ∃S ∈ FinA. ∀a ∉S. Φ(a).

Fresh Logic has a syntactic new-quantifier, also written И. Its semantics will be this. (3) can be rephrased as Иa, b. (a b) · x = x, by simple calculation using the fact that if S and S′ are finite, so is S ∪S′.

We now write

(5) a#x for Иb. (b a) · x = x

and read this ‘a is fresh for x’. Fresh Logic also has a # connective, with semantics this one. This definition here is derived in (D5) and (D6) (for # in Fresh Logic) in Figure 4.

Another construction of S(x) is {a⏐⏐ ¬a#x}, and (3) may be rephrased as

(6) Иa. a#x.

In view of this, and of the examples above, we see that freshness gives a generalised notion of ‘not in the free variable names of’ and the smallness condition a generalised notion of ‘everything mentions finitely many variables’ — ‘generalised’, because it depends in no way on x being syntax and indeed will be most notably important when this is not the case, for example in the discussion of frames in §4.1.

Definition 2.3

A function f : X →Y is equivariant when

(7) ∀x ∈X, a, b ∈A. (a b) · (f(x)) = f((a b) · x).

Let NOM be the category with objects Nominal Sets and arrows equivariant functions between them.

(It is easy to verify that this is indeed a category.)

Any type T of binary labelled trees (say by a ∈A and n ∈N) is a Nominal Set, with the action on the labels—trivially on n ∈N and functionally on a ∈A. Then π · ⟨t, t′⟩= ⟨π · t, π · t′⟩, so the tree-pairing constructor is equivariant. We see generalising this argument that constructors of all such types are equivariant.

It is a useful observation, which we shall use often, that if a#x and f is equivariant, then a#f(x).

One final useful concept is the difference set of π, π′ ∈PA.

(8) ds(π, π′)def={ n⏐⏐ π(n) ≠ π′(n)}.

For example, ds((a b), Id) = {a, b}.

If S is a finite collection of atoms then write S#x for a#x for every a ∈S. If S is empty, S#x is always true. We shall use the following lemma:

Lemma 2.4

If ds(π, π′)#x then π · x = π′ · x.

Proof

By calculation. □

It is interesting to observe this lemma in action for the example of terms up to α-equivalence above. If t = λf, x.fx then (f x) · [λf, x.fx]=α (is given by the action on representatives and) equals [λx, f.xf]=α, using an obvious notation for equivalence classes.

This concludes all we need of semantics. We use it heavily in the parts of this paper regarding semantics of Fresh Logic.

3. Basic definitions and notation

3.1. Sorts.

We assume a set X, Y, . . . ∈ Sorts of sorts. We assume a distinguished sort of atoms A ∈ Sorts.

There may be sort-formers, e.g. pair-sorts A × B or function-sorts X → X.

3.2. Variables and atoms.

We assume countably infinite sets a, b, c, . . . ∈A of atoms and x, y, z, . . . ∈V of variables V.

Since Fresh Logic has equality we may write identity on A and V as ≡. We assume variables are inherently sorted, so x ∈V has a unique sort X ∈ Sorts. We may write x:X, or we may leave sorts implicit. Atoms a ∈A also have a sort, which is always A.

3.3. (Syntactic) permutations.

For a, b ∈A a (syntactic) swapping (a b) is a pair ⟨a, b⟩. Write π, π′, κ, . . . ∈P stx A for the set of finite lists of swappings and call them (syntactic) permutations. Given π, π′ ∈P stx A write π ◦π′ for their list concatenation. Write Id for the empty list. Write A(π) for the atoms a ∈A appearing in π.

Recall the set of semantic permutations in FM which we wrote PA. A syntactic permutation maps to a semantic permutation in the way obviously suggested by the notation. For a ∈A and π a syntactic permutation, write π(a) for the atom obtained via this semantic interpretation. Recall the notation ds(π, π′) from (8). We may write this also for syntactic permutations, using this semantic interpretation. Thus ds((a b) ◦ (a b), Id) = ∅, though A((a b) ◦ (a b)) = {a, b}.

3.4. Moderated variables.

A moderated variable is a pair ⟨π, x⟩∈P stx A× V, written π · x.

Intuitively π · x is ‘x with the permutation π applied to it’ — but, since we do not yet know what x is, π remains ‘in suspension’ (moderating it) until we find out what x is.

A meaning to ‘finding out what x is’ is provided in the syntax by substitution (40).1 Moderations lead to an interaction between substitution and moderations on variables, which is formally defined in (40), (42), and in the text below. We give one canonical example now:

((a b) · x){x↦→⟨a, b, c, y⟩} ≡⟨b, a, c, (a b) · y⟩.

Define FV(π ·x) def= {x} (‘variables in’) and A(π ·x) def= A(π) (‘atoms in’). Call a moderated variable π · x trivially moderated when π ≡ Id and write x for Id · x. If x : X then π · x : X.

The notions of moderated variable and difference set are due to Urban [28].

3.5. Terms.

Terms are defined by the following grammar:

(9) s, t, . . . ::= a | π · x | c(ts).

Here we introduce a shorthand we shall use again frequently, of writing ts for some list of terms. c has an arity and here (and in the future) we assume the terms have sorts appropriate to that arity in c(ts). We omit the typing rules for terms which are as usual.

We introduce notions A(t) of ‘atoms of t’ and FV(t) of ‘variables of t’. We gather these all similar definitions in an appendix; see (39) and (38). For example: (10)

tdef= c(a, b, x, (a b) · x, y, (c d) · y, z) A(t) = {a, b, c, d} FV (t) = {x, y, z}.

We introduce a substitution action t{x↦→s} defined in the standard way (s and x must have the same sort).

a{x↦→s} = a (π · x){y↦→s} = π · x x ≢y(π · x){x↦→s} = π ·s s c(ts){x↦→s} = c(ts{a↦→s}),

See (40) in the appendix for a fully commented version.

The clause for moderated variables in the definition of substitution above uses a permutation action π ·s t (we mentioned this must happen in the last subsection). It is defined by:

π ·s a = π(a) π ·s (κ · x) = π ◦κ · xπ ·s (κ · x) = κ · x π ·s c(ts) = c(π ·s ts).

π ·s t is an operation on terms whose result is the term obtained by ‘pushing π down to the moderated variables and atoms’. The fully commented definition is in (42). (The s is for ‘sugar’ since (a b) ·s t operates on t.) For example:

(a b) ·s x ≡(a b) · x (a b) ·s ⟨a, b, c, y⟩≡⟨b, a, c, (a b) · y⟩tdef= c(a, b, x, (a b) · x, y, (c d) · y, z) (a b) ·s t ≡c(b, a, (a b) · x, (a b) ◦(a b) · x, (a b) · y, (a b) ◦(c d) · y, (a b) · z).

Permutations act ‘top-down’ and substitutions act ‘bottom-up’. Formally we have the following useful lemma:

Lemma 3.1

π ·s (t{x↦→s}) = (π ·s t){x↦→s} always.

Proof

By induction on terms. The crucial base case is π ·s (x{x↦→t}) = (π · x){x↦→t}, see (40). □

3.6. Propositions or formulae.

We assume predicate constant symbols p, q, r . . . ∈P, each with an arity a list of sorts, for example (X, X), describing the number and sorts of its arguments (two arguments both of sort X). For each X ∈ Sorts we assume distinguished constants =:(X, X) equality and #:(A, X) freshness. Fresh Logic includes special deduction rules for them which we shall come to in due course.

Propositions or formulae are generated by the grammar

(11)P ::= p(ts) | P ∧P | P ∨P | P ⇒P | ⊤| ⊥| ∀x. P | ∃x. P |Иn. P.

P ⇔Q is shorthand for P ⇒Q ∧Q ⇒P and ¬P is shorthand for P ⇒⊥.

Like terms, propositions have notions of free variables and atoms FV(P) and A(P), formally defined in (38) and (39), substitution P{x↦→s} defined in (41), and a permutation action defined in (43). In brief, ∀ binds x in ∀x. P, ∃ binds x in ∃x. P, and И binds n in Иn. P, and we take formulae up to α-equivalence of bound variables ∀/∃x and bound atoms Иn. Substitutions and permutations are capture-avoiding for these bindings, we include the core of the definition without comment:

π·s p(ts) = p(π·s ts) π·s (P ∧Q) = π·s P ∧π·s Q. . . π·s ∀x. P = ∀x. [[ π·s P{x↦→π-1·x} ]] xπ·s ∃x. P = ∃x. [[ π·s P{x↦→π-1·x} ]] xπ·sИn. P =Иn. π·s P.p(ts){x↦→t} = p(ts{x↦→t}) (P ∧Q){x↦→t} = P{x↦→t} ∧Q{x↦→t}. . . (∀x′. P){x↦→t} = ∀x′. (P{x↦→t})(∃x′. P){x↦→t} = ∃x′. (P{x↦→t}) (Иn. P){x↦→t} =Иn. (P{x↦→t}).

For examples, consider P =Иc. ∀x. p(c, (a b) · x, (a c) ◦ (a c) · y). Then FV(P) = {y}, A(P) = {a, b}, and P{x↦→t} = P.

Also (d a) · P =Иc. ∀x. p(c, (d b) · x, (d a) ◦ (a c) ◦ (a c) · y). Note how the permutation acts differently on moderations of bound and free variables. This is necessary for §8.4 to work.

3.7. Contexts.

A (logical) context is a multiset of propositions, usually written Γ.

Write A(Γ) and FV (Γ) for the obvious extensions to many formulae. We may also write Γ{x↦→s} and π ·s Γ.

We shall give judgements and deduction rules in §5. First however we develop part of the semantics of Fresh Logic.

4. Semantics I: Frames

4.1. Frames.

The semantics of Fresh Logic is a Kripke structure [29] of classical models. A classical model is an FM set (or rather a collection of FM sets, since Fresh Logic is typed), along with extra structure. We call this set with structure a frame, it is defined as follows:

Definition 4.1

A frame α for a Fresh Logic language L is assignements:

(i) X ↦→ [[ X ]] ∈ Obj(NOM) of each sort to a Nominal Set (X a sort, not necessarily primitive). To [[ X → Y]] is associated a standard injection into [[ Y ]] [[ X ]] . To [[ A ]] is associated a standard bijection with A.

(ii) c : X ↦→[[ c ]] ∈[[ X ]] (c a constant symbol). a : A ↦→a = [[ a ]] ∈A.

(iii) p : X ↦→[[ p ]] ⊆[[ X ]] (p a predicate constant symbol).

(iv) [[ ⊤]] = {∗}, and [[ ⊥]] = ∅.

(v) A finite set of variable symbols Uα ⊆V.

(vi) A valuation x ∈Uα: X ↦→[[ x ]]α ∈[[ X ]]α.

These assignements must satisfy:

(i) [[ c ]] must be equivariant: (a b) · ([[ c ]] (us)) = [[ c ]] ((a b) · us) (c a constant symbol).

(ii) [[ p ]] must be equivariant: u ∈[[ p ]] =⇒ (a b) · u ∈[[ p ]] .

(iii) Let [[ f ]] :[[ X → Y]] map to f under the standard injection. Then for any t:X, f[[ t ]] = [[ ft ]] .

A frame is an instance of an ‘applicative structure’ or ‘prestructure’ in the category of FM sets [21, 7, 27].

4.2. Semantics of atoms and terms.

A frame α gives rise to a total map on t such that FV (t) ⊆Uα, defined inductively by

[[ c(ts) ]] α = [[ c ]] α([[ ts ]] α).

It is easy to show by induction that:

(12)[[ t ]] = [[ t′ ]] [[ s{x↦→t} ]] = [[ s{x↦→t′} ]][[ t ]] = [[ t′ ]] ⟨[[ ts ]] {x↦→t}⟩∈[[ p ]] ⇐⇒⟨[[ ts ]] {x↦→t′}⟩∈[[ p ]] ⋀ a ∈ds(π, π′). a#u ⟨[[ ts ]] {x↦→π ·s t}⟩∈[[ p ]] ⇐⇒⟨[[ ts ]] {x↦→π′ ·s t}⟩∈[[ p ]]π · [[ t ]] = [[ π ·s t ]]

We drop the α subscript in [[ · ]] where convenient. We shall use the natural semantics of a syntactic permutation and write for example π · [[ t ]] above instead of a stricter [[ π ]] · [[ t ]] .

4.3. Comments on the semantics.

The typical semantics for intuitionistic First-Order Logic is by collecting classical models together in a Kripke (or Beth) model [29]. The domains of these models may increase along accessibility so excluded middle is lost because ‘new’ elements can appear ‘later’. Each classical model is called a ‘world’ and inclusions of models is called ‘accessibility’.

We use this technique: we could extend the valuation on terms above to a valuation on predicates, and see that a frame extends to a classical semantics for Fresh Logic.

Frames are built in FM Sets and not ZF Sets. FM Sets interpret names and binding and are otherwise remarkably ZF-like. The match between transposition and freshness in the model and logic is invited by our notation. The FM Sets semantics though non-standard is very natural.

We have been particularly careful about valuations: a frame α comes packaged with an evaluation x↦ → [[ x ]]α ∈ [[ X ]]α on a specific finite set Uα ⊆V. This is useful for rigorously treating binding in ∀ and ∃, where we need to choose names for the bound variable symbols and would like to do so ‘fresh’.

In intuitionistic logic terms can become equal moving along worlds α ≤β; equality is treated in the model as a binary relation [[ = ]]α ⊆ [[ X ]] 2 α which may grow, but the maps of underlying domains [[ X ]]α↦ → [[ X ]]β are set inclusions. A completeness proof builds a model out of the syntax of a theory by [[ X ]] = {t : X} and interprets equality by a relation of provable equality.

A problem now arises. t and (a b) ·s t are not usually textually identical terms even if they are provably equal. Using the standard method outlined above, [[ t : X ]] would not have finite support and [[ X ]] would not be an FM set.

Therefore, our notion of model interprets equality and apartness as literal equality and literal apartness, and maps of underlying domains may be non-injective. Similar considerations explain why each frame comes equipped with a standard isomorphism [[ A ]] ∼= A.

We shall see that we still get sensible and reasonably familiar-looking soundness and completeness proofs.

5. Judgements

5.1. Inductive definition.

A judgement is a pair ⟨Γ, P⟩ of a context and predicate written Γ ⊢P. Elements of Γ are called hypotheses and P the conclusion.

The valid or derivable judgements are inductively defined by the rules of Figure 1, Figure 2, and Figure 3. We discuss notation and semantics below.

5.2. Notations used in the inductive definition.

In (NewA) FV (Γ, C) denotes ⋃ { FV (P) ⏐⏐ P in Γ or P ≡C}; all variables occurring free in Γ or C. ts is a list of terms t1, t2, . . . (using an already-established convention) and a#ts is a list of assumptions a#t1, a#t2, . . ..

In (πdiff) ds(π, π′)#t denotes a list of predicates a1#t, a2#t, . . . for ds(π, π′) = {a1, a2, . . .}, and Γ ⊢a#ds(π, π′) a list of judgements.

In (ИI) and (ИE) P{n↦→a} denotes that formula obtained by (capture-avoiding) replacing every n in P by a.

In (ExhaustA) the side conditions insist we have a proof of Γ{x↦→a} ⊢P{x↦→a} for every a ∈ A(Γ, P), as well as at least one fresh atom n.

5.3. Intuition behind the novel aspects of the deduction rules.

Fresh Logic contains intuitionistic first-order logic with equality, and we can see from the rules that this core is unchanged.

(#I) and (#E): The semantics defined in §4 interprets syntactic equality judgements as literal equality, and freshness judgements as literal freshness. Atoms are their own semantics and freshness on atoms is inequality.

(πdiff): We know from (12) that [[ π ·s t ]] = π · [[ t ]] . This rule formalises Lemma 2.4 inside Fresh Logic.

Γ, P ⊢P(Axiom)Γ ⊢P Γ ⊢Q Γ ⊢P ∧Q(∧I)Γ ⊢P ∧Q Γ ⊢P(∧E1)Γ ⊢P ∧Q Γ ⊢Q(∧E2)Γ ⊢P Γ ⊢P ∨Q(∨I1)Γ ⊢Q Γ ⊢P ∨Q(∨I2)Γ ⊢P ∨Q Γ, P ⊢C Γ, Q ⊢CΓ ⊢C(∨E)Γ, P ⊢Q Γ ⊢P ⇒Q(⇒I)Γ ⊢P ⇒Q Γ ⊢PΓ ⊢Q(⇒E)Γ ⊢⊥ Γ ⊢P(⊥E)Γ ⊢⊤(⊤I)Γ ⊢P Γ ⊢∀x. Px ∉FV (Γ)(∀I)Γ ⊢∀x. P Γ ⊢P{x↦→t}x ∉FV (Γ)(∀E)Γ ⊢P{x↦→t} Γ ⊢∃x. Px ∉FV (Γ)(∃I)Γ ⊢∃x. P Γ, P ⊢C Γ ⊢Cx ∉FV (Γ, C)(∃E)Figure 1. Core (standard) rules of Fresh Logic
Γ ⊢P Γ ⊢π ·s P(πI)Γ ⊢P{x↦→π′ ·s t} Γ ⊢ds(π, π′)#t Γ ⊢P{x↦→π ·s t}x ∉FV (t)(πdiff)Γ ⊢P{n↦→a} Γ ⊢a#ti (i = 1, . . . , k) Γ ⊢Иn. PP/n = P ′ •yi (ti)k 1a ∉A(P ′)(ИI)Γ ⊢Иn. P Γ ⊢a#ti (i = 1, . . . , k) Γ ⊢P{n↦→a}P/n = P ′ •yi (ti)k 1a ∉A(P ′)(ИE)
Figure 2. π and И rules of Fresh Logic
Γ ⊢P{x↦→t′} Γ ⊢t = t′Γ ⊢P{x↦→t}x ∉FV (t, t′)(EqE)Γ ⊢t = t(EqI)Γ ⊢a#b(#I)Γ ⊢a#ts Γ ⊢a#c(ts)(#c)Γ ⊢a#a Γ ⊢C(#E)Γ, a#ts ⊢C Γ ⊢Ca ∉A(Γ, C)(NewA)⋀ n ∈S. Γ{x↦→n} ⊢P{x↦→n} Γ{x↦→t} ⊢P{x↦→t}A(Γ, P) ⊊S(ExhaustA)Figure 3. =, #, and A rules of Fresh Logic

(NewA): Read bottom-up this rule says we can always introduce a fresh atom a. The idea of ‘we can always find a fresh widget’ turns up frequently ([14], [5], side-conditions on ‘where x is fresh’ in ∀-introduction rules, and a ‘trick’ by Krivine [16, Chapter 2] which is precisely a use of И, are just some examples). A very important difference here is that (NewA) lets us choose a fresh for the current context without having to explicitly say what that context is, or even necessarily what freshness is with respect to that context; this turns out to be very useful.

(πI): This is a version of (12) for predicates. We prove its validity in Lemma 7.5.

(ExhaustA): Here ⊊ just means ⊂, but we reinforce the point that we mean here proper subset, so S \ A(Γ, C) is not empty. Since A(Γ, C) is finite, we can also restrict S to be finite (see §9).

This rule states that the atoms a ∈A exhaust terms of sort A up to equality. To test Γ ⊢P it suffices to test it on all the atoms mentioned in Γ or P, plus (at least) one fresh one acting as a fixed but arbitrary constant. See §5.5 for a further discussion.

The NEW intro- and elim-rules: (ИI) and (ИE) are symmetric and we consider just the first (ИI). A deduction rule should be closed under substitution {x↦→s}, to give us Lemma 8.3 and from it Theorem 8.2 the essential case of ∀.

So at first we take P = P ′ and ti = yi for all i. This rule becomes

Γ ⊢P{n↦→a} Γ ⊢a#yi (i = 1, . . . , k) Γ ⊢Иn. Pa ∉A(P).(13)

Thus “if a#yi for all yi ∈FV(P), and a ∉ A(P), then a is fresh, and if P(a) then Иn. P(n)”. (Similarly the elim-rule says “if a#yi for all yi ∈FV(P), and a ∉ A(P), then a is fresh, and if Иn. P(n) then P(a)”.) We discuss this some/any property from Prop 4.10 onwards in [12]. We now discuss this pair of rules in more detail:

5.4. Slices.

We use slices to specify the deduction rules for the И quantifier (ИI) and (ИE).

Definition 5.1

A slice of a proposition P is a tuple (P, k, (yi)k i=1, P ′, (ti)k i=1) of P, a number k, and:

(i) A choice of variable symbols y1, . . . , yk, taken fresh (for the variables in P, and where convenient for any other variables we do not want accidental name-clashes with).

(ii) A proposition P ′ with FV(P ′) = {y1, . . . , yk}.

(iii) A list of terms t1, . . . , tk such that P ′{y1↦→t1} . . . {yk↦→tk} ≡P.

A slice of P covers n ∈A in P if n ∉ A(ti) for any 1 ≤i ≤k.

It is useful to write

(14) P ′ •yi (ti)k 1 or just P ′ • (ti) for P ′{y1↦→t1} . . . {yk↦→tk}.

(A more suggestive notation for a slice is arguably P ≡ (λy1, . . . , yk.P ′)t1. . . tk; this treats slices as a very specific form of β-expansion. Then (ИI) states that if a ∉ A(λyi.P ′) and a#ti then a is apart from the application P and holds for any fresh a by FM swapping. We see this argument made formal in §8.4. We prefer the • notation partly to not suggest Fresh Logic is second-order, partly because • is typographically more convenient.)

Here are two examples of slices:

p(a, b, (a b) ◦(a b) · x, y) slices as p(a, b, (a b) · y1, y2) •y1,y2 ((a b) · x, y).∀x. p(a, b, (a b) ◦(a b) · x, y) slices as ∀x. p(a, b, (a b) · (a b) · x, y1) •y1 (y).

Slices induce a relation on propositions given by P ′ ≤P if for suitable terms ti, P ≡P ′ •yi (ti). This order is well-founded up to choices of the yi which we shall as discussed assume are chosen fresh, and otherwise ignore.

Given two slices P ′, P ′′ ≤P we can see by the structural properties of abstract syntax trees that there is a natural notion of their intersection (greatest lower bound) P ′′′ ≤P ′, P ′′ ≤P.

For fixed P (and n) the set of slices of P (covering n) inherits this order from the P ′. By the observations above and the fact that syntax is finite, this set also has a least slice with respect to ≤.

Write the least slice of P covering n as P/n. By abuse of notation write P/n = P ′ •yi (ti) for “the least slice of P covering n is P ′, (yi), (ti)”. This corresponds to the Caires-Cardelli notion of ‘free term’ [4, p.7], [5, p.5, §2].

(ИI) and (ИE) take least slices and this is important for §8.4. (ИI) and (ИE) write ‘P{n↦→a}’. We easily see that all the substitutions are really happening in the P ′:

Lemma 5.2

Suppose P/n = P ′ • (ti)k 1. Then for any a,

(P ′ • (ti)){n↦→a} = (P ′{n↦→a}) • (ti).

While on the subject we also notice by inspection that in substitutions P{x↦→s}, if n is suitably fresh for s then the substitution there must really be happening in the terms ti:

Lemma 5.3

Suppose s is a term and x a variable and n ∉ A(s). Suppose P/n = P ′ • (ti). Then

(P{x↦→s})/n = P ′ •yi (ti{x↦→s}).

5.5. Significance of (ExhaustA).

(ExhaustA) formalises the following feature of FM theory: to test a predicate on atoms, it suffices to test it on the (finite number of) atoms in its support, and on one fresh atom. This is implied by (3) the smallness condition on page 4, but does not imply it (see also §9.1).

Rather remarkably (ExhaustA) seems to suffice to derive all of the practically useful consequences of (3). We now explore some derivable judgements which emerge from it:

Lemma 5.4

Let p be a predicate symbol of kind A. Иn. p(n) ⊢∀x. p(x) is a theorem of Fresh Logic.

The intuition why this should be so is that p has kind A and so uses no other free variables or atoms for which n must be fresh.

Proof

P/n = p(n) •∅ () so easily by (ИE), for any a, Иn. p(n) ⊢p(a). Since this is for any a we use (ExhaustA) to derive Иn. p(n) ⊢p(x) for a variable symbol x, and using (∀I) Иn. p(n) ⊢∀x. p(x) as required. □

In intuitionistic logic a separation predicate is one which states explicitly inequality of two elements. # is a separation predicate on A (this does not follow directly from (#E) and (#I) because they address only atoms, not variables).

Fresh Logic is intuitionistic. But equality on A is decidable:

Lemma 5.5

For x, y : A,

x#y ⊢x ≠ y, x ≠ y ⊢x#y, and ⊢x = y ∨x ≠ y

are derivable. As a corollary of the first two judgements, # is symmetric.

Proof

It is easy to derive a#b, a = b ⊢ ⊥ and hence a#b ⊢ a ≠ b, and also a#a ⊢a ≠ a. Using (ExhaustA) twice we derive the first judgement.

It is easy to derive a ≠ b ⊢a#b using (#I), and also a ≠ a ⊢a#a. As in the previous case we use (ExhaustA) to derive the second judgement.

A proof of the third judgement can be constructed similarly. □

We can verify by calculation that the only equivariant f : A →A in NOM is the identity λa.a. The logic reflects this:

Lemma 5.6

For any constant symbol f : A → A in a language L of Fresh Logic, ⊢x = f(x) is derivable.

Proof

Using the previous lemma a ≠ f(a) ⊢ a#f(a). Using (#c) we can also deduce a ≠ f(a) ⊢b#f(a). By (ExhaustA) we conclude a ≠ f(a) ⊢ f(a)#f(a), and again using the previous lemma we conclude a ≠ f(a) ⊢ f(a) ≠ f(a), which is absurd.

□

6. Example deductions

(D1) connects И and # within Fresh Logic. In the instance of (ИI) P/n = (n#y) •y (x). (D2) derives (3) within Fresh Logic.

In (D3) FV(A) and FV(B) are the variables of A and B and a#FV(A, B) is a list of freshness assumptions a#x for each x ∈FV (A) ∪FV(B). In the last instance of (ИI) the slice is A∧B/n = (A∧B)σ•(FV (A), FV(B)), where σ renames x ∈FV(A, B) to yi, as slices demand. We leave it to the reader to calculate the other slices and suchlike.

The reverse entailment Иn. (P ∧Q) ⊢Иn. P ∧Иn. Q is similar. We can also derive similar equivalences for the other connectives such as ⇒ and ∨.

(D4) is one direction of a well-known commutativity property ⊢ (Иa. ∀x. a#x ⇒ P) ⇐⇒∀x.Иa. P. In that proof, vs represents the set of all free variables of P except for x.

(D5) and (D6) are another well-known relation between #, И, and equality [12, Prop. 4.10]:

⊢a#x ⇐⇒Иb. (b a) · x = x.
(D1)(Axiom)a#x⊢a#x(ИI)a#x⊢Иn.n#x(NewA).⊢Иn.n#x(D2)(EqI)a,b#x⊢x=x(πdiff)a,b#x⊢(ab)·x=x(ИI)a,b#x⊢Иm.(am)·x=x(ИI)a,b#x⊢Иn.Иm.(nm)·x=x(NewA),(NewA).⊢Иn.Иm.(nm)·x=x(D5)(EqI)a#x,b#x⊢x=x(πdiff)a#x,b#x⊢(ba)·x=x(ИI),(NewA)a#x⊢Иb.(ba)·x=x(D3)(Axiom)a#FV(A),FV(B),Иn.A∧Иn.B⊢Иn.A∧Иn.B(∧E2)a#FV(A),FV(B),Иn.A∧Иn.B⊢Иn.B(ИE)a#FV(A),FV(B),Иn.A∧Иn.B⊢B{n↦→a}(Axiom)a#FV(A,B),Иn.A∧Иn.B⊢Иn.A∧Иn.B(∧E1)a#FV(A,B),Иn.A∧Иn.B⊢Иn.A(ИE)a#FV(A,B),Иn.A∧Иn.B⊢A{n↦→a}(∧I)a#FV(A,B),Иn.A∧Иn.B⊢A{n↦→a}∧B{n↦→a}(ИI)a#FV(A,B),Иn.A∧Иn.B⊢Иn.(A∧B)(NewA).Иn.A∧Иn.B⊢Иn.(A∧B)(D4)(ИE),(∀E)(Иa.∀x.a#x⇒P),a#x,vs⊢a#x⇒P(Axiom)(Иa.∀x.a#x⇒P),a#x,vs⊢a#x(⇒E)(Иa.∀x.a#x⇒P),a#x,vs⊢P(ИI),(NewA),(∀I),(⇒I)⊢(Иa.∀x.a#x⇒P)⇒∀x.Иa.P(D6)(Axiom)b#x,Иb.(ba)·x=x⊢Иb.(ba)·x=x(ИE)b#x,Иb.(ba)·x=x⊢(ba)·x=x(Axiom)b#x,Иb.(ba)·x=x⊢b#x(EqE)b#x,Иb.(ba)·x=x⊢b#(ba)·x(πI)(π=(ba))b#x,Иb.(ba)·x=x⊢a#(ba)◦(ba)·x(πdiff)b#x,Иb.(ba)·x=x⊢a#x(NewA)Иb.(ba)·x=x⊢a#xFigure4.Exampledeductions

7. Validity and soundness

7.1. Semantics II: Models and validity.

A frame map α ≤β is a collection of functions τ : [[ X ]]α →[[ X ]]β such that

(i) Uα ⊆Uβ.

(ii) ⋀ x ∈Uα. τ[[ x ]]α = [[ x ]]β.

(iii) ⋀ u ∈[[ X ]]α. [[ c ]]β(τu) = τ[[ c(u) ]]α.

(iv) ⋀ u ∈[[ X ]]α. τu ∈[[ p ]]β ⇐⇒u ∈[[ p ]]α.

τ must commute with the isomorphisms [[ A ]] ∼= A associated to the frame. It need not be injective.

Definition 7.1

A model M of Fresh Logic is a set of frames partially ordered by a set of frame maps, satisfying the following closure condition:

If α ∈M, x:X ∈V\Uα, and u ∈[[ X ]]α, then the frame α′ written α, x↦ →u is in M, where Uα′ = Uα∪{x} and [[ x ]]α′ = u. Also, if α ≤τ β then α, x↦ →u ≤τ β, x↦ →τ(u).

Definition 7.2

Define a relation α ⊩P inductively on P such that FV (P) ⊆ Uα by

(i) α ⊩p(t1, . . . , tn) when ⟨[[ t1]] α, . . . ⟩∈[[ p ]]α.

(ii) Amongst the ps above are = and #. We insist additionally that α ⊩t = t′ when [[ t ]] = [[ t′]] and α ⊩t#t′ when [[ t ]] #[[ t′]] .

(iii) α ⊩P ∨Q when α ⊩P or α ⊩Q. Similarly for ∧. α ⊩⊤ always.

(iv) α ⊩P ⇒Q when ∀β ≥α. if β ⊩P then β ⊩Q.

(v) α ⊩∀x : X. P when ∀β ≥α. ∀v ∈[[ X ]]β. β, x↦ →v ⊩P. Here x ∉Uα.

(vi) α ⊩∃x : X. P when ∃u ∈[[ X ]] . α, x↦ →u ⊩P. Here x ∉Uα.

(vii) α ⊩Иn. P when α ⊩P. Here n#α (we can α-convert to guarantee this because α satisfies (3)).

The condition that FV (P) ⊆Uα is merely a well-formedness condition to ensure that, for example, [[ t1]] α is defined. Since ⊩ is derived inductively and no rule derives α ⊩ ⊥, we know α ⊮ ⊥ for all α. Recalling also that ¬P is sugar forP ⇒⊥, we obtain the following:

α ⊩¬P when ∀β ≥α. if β ⊮P.

The condition x ∉Uα formally states that x is chosen fresh. Similarly for the condition n#α. Calculated explicitly for the structure of frames α this condition means that n#[[ x ]]α for every x ∈Uα.

Note that the semantics of equality is literal identity. We see a frame map need not be an inclusion on underlying sets. In Kripke models elements can ‘become’ equal moving along the accessibility relation, just as any other predicate may ‘become’ true.

It is standard in some communities that accessibility be an inclusion on underlying sets ([1, §6 p416 (3)] and [29, p249 3.3(i)]) and equality is not identity but a relation satisfying very special coherence conditions so that the semantics of term-formers and predicates cannot distinguish related elements. Other communities ([7, 27], [22, p6]) allow accessibility to be a non-injective function, so that equality can be modelled by literal equality in the model.

Thus Fresh Logic semantics follow the latter tradition (see for example the second clause in Definition 7.2 above, for equality). A semantics in the former tradition is possible but the completeness proof breaks for it, see §9.3.

7.2. Basic properties of validity.

We may write α ⊩ Γ for ⋀ P ∈ Γ. α ⊩P.

Lemma 7.3

(i) Cofinitely many b satisfy α ⊩b#t.

(ii) If α ⊩P and β ≥α then β ⊩P (call this property persistence).

(iii) If α ⊩P and x : X ∉Uα then α, x↦ →u ⊩P for any u ∈[[ X ]]α.

(iv) α, x↦ →u ⊩P if and only if α, x↦ →π · u ⊩P{x↦→π-1 · x}.

(v) Suppose x ∉Uα and FV (P) ⊆Uα ∪{x}. Then α, x↦ → [[ t ]]α ⊩P if and only if α ⊩P{x↦→t}.

(vi) Suppose x ∉Uα and FV (P) ⊆Uα. Then if α, x↦ →u ⊩P then α ⊩P.

Proof

(i) [[ t ]] is an element of a Nominal Set and so has finite support, so there are cofinitely many b such that b#[[ t ]] α,ϵ.

(ii) By induction on P. We only really need to consider the base cases p(t1, . . . , tk), t = t′, and t#t′, since for the other cases this property is built-in or trivial. We just consider p(t1, . . . , tk). Suppose ⟨[[ t1]] α,ϵ, . . . ⟩∈ [[ p ]]α. Associated to β ≥α is a frame map so [[ p ]]α ⊆ [[ p ]]β and [[ ti]] α,ϵ = [[ ti]] β,ϵ, and evidently ⟨[[ t1]] β,ϵ, . . . ⟩∈[[ p ]]β.

(iii) By very easy induction on P, omitted.

(iv) By very easy induction on P, omitted.

(v) By induction on P. The previous two parts are not corollaries of this one, because we cannot assume u = [[ t ]]α for some t.

(vi) By very easy induction on P, omitted.

□

7.3. Validity for some structural rules.

We prove results which are not quite but but amount to soundness (EqI), (#I), (#E), (#c), (EqE), and (πdiff). This is very simple.

Lemma 7.4

The following deduction rules are (trivially) valid:

(15)α ⊩t = t α ⊩a#bα ⊩a#a α ⊩⊥α ⊩a#ts α ⊩a#c(ts)α ⊩P{x↦→t′}, t = t′α ⊩P{x↦→t}α ⊩P{x↦→t′}, t′ = t α ⊩P{x↦→t} α ⊩P{x↦→π ·s t}, ds(π, π′)#t α ⊩P{x↦→π′ ·s t}.
Proof

Equality is interpreted by literal identity and [[ t ]]α = [[ t ]]α always. Freshness is modelled by literal freshness and on atoms this coincides with inequality, so a#b always (when a ≢b) and a#a never. By definition [[ c(ts) ]] = [[ c ]] ([[ ts ]] ) and [[ c ]] is equivariant. The equality elimination rules are easy, given that equality is interpreted as literal equality. (πdiff) is easy from Lemma 2.4. □

We now prove soundness for (πI):

Lemma 7.5

The following deduction rule is valid:

(16)α ⊩P α ⊩π ·s P
Proof

By induction on P.

(i) P = p(t1, . . . , tk): By (12) π·⟨[[ t1]] , . . . , [[ tk]] ⟩= ⟨[[ π ·s t1]] , . . . , [[ π ·s tk]] ⟩, and by construction [[ p ]] is equivariant.

(ii) P = P1 ⇒P2: Suppose α ⊩P1 ⇒P2. π ·s P = π ·s P1 ⇒π ·s P2, so suppose β ⊩π ·s P1. By induction hypothesis β ⊩π-1 ·s π ·s P1. We know ⊩ is closed under (πdiff) by the previous result so β ⊩P1, whence β ⊩P2. By induction hypothesis β ⊩π ·s P2. This suffices to establish α ⊩π ·s P.

(iii) P = ∀x : X. P ′: Take some β ≥α and u ∈[[ X ]]β; then α, x↦ →π-1 · u ⊩P ′. By hypothesis

α, x↦ →π-1 · u ⊩π ·s P ′so α, x↦ →u ⊩π ·s P ′{x↦→π-1 · x}.

Since u and β were arbitrary, α ⊩π ·s ∀x. P.

(iv) P = ∃x : X. P ′: There is some u ∈ [[ X ]]α such that α, x↦ →u ⊩P ′. By hypothesis

α, x↦ →u ⊩π ·s P ′so α, x↦ →π · u ⊩π ·s P ′{x↦→π-1 · x}

This suffices to conclude α ⊩π ·s ∃x. P.

(v) P =Иn. P ′: n is fresh for π so π ·sИn. P ′ =Иn. π ·s P ′. By induction hypothesis α ⊩π ·s P ′. This suffices to conclude α ⊩π ·sИn. P ′. We omit the remaining cases.

□

7.4. Meta-level swapping.

Our treatment of Fresh Logic uses FM sets for models M, frames α, syntax, and so on. We therefore enjoy a ‘meta-level’ swapping on all of these. We wrote it ·. This is distinct from the swapping action ·s defined in (42) and (43) which acts on terms and formulae.

From equivariance of FM sets [12, Lemma 4.7] meta-level swapping commutes with constructors and term-formers; because, in the notation of that Lemma, they can be specified by some φ in the language of FM logic. Thus the property of being a frame Definition 4.1 can be encoded as some φ for a frame α, the set (a b) · α is also a frame, identical to α except that x ∈U(a b)·α = Uα maps to (a b) · [[ x ]]α.

For a formula P, the set (a b) · P is also a formula, obtained by syntactically swapping a and b.

Relations ⊩ and ⊢ are equivariant with respect to ·, so

Γ ⊢P ⇔(a b)·Γ ⊢(a b)·P and α ⊩P ⇔(a b)·α ⊢(a b)·P.

Very useful corollaries, which we shall use in the next subsection, are as follows:

(a b)·Γ ⊢P ⇔Γ ⊢(a b)·P and (a b)·α ⊩P ⇔α ⊢(a b)·P.

7.5. Entailment relative to a model and soundness.

Notation 7.6

Let M be a model of Fresh Logic. Write Γ ⊩MP when ∀α ∈M. α ⊩ Γ ⇒α ⊩P.

In the proof of soundness below we shall work relative to a fixed but arbitrary M and abbreviate Γ ⊩M P to Γ ⊩P. Later on in the proof of completeness we shall write Γ ⊩P with a different meaning, that ∀M. Γ ⊩M P. We will always make clear which of the two notations we mean. In this subsection, we mean the former.

Theorem 7.7 (Soundness).

Fix some model M. If Γ ⊢P then Γ ⊩M P.

Proof

By induction on the proof of Γ ⊢P.

(i) The rule (⇒I): Suppose Γ, P ⊩Q and α ⊩ Γ. For any β ≥α, if β ⊩P then using persistence β ⊩ Γ, P so β ⊩Q.

(ii) The rule (∀I): Suppose Γ ⊩P and x : X ∉FV (Γ). Suppose α ⊩ Γ. For any β ≥α by persistence β, x↦ →u ⊩ Γ for any u ∈[[ X ]]β. By assumption β, x↦ →u ⊩P, and this suffices to prove α ⊩∀x. P.

(iii) The rule (∀E): Suppose Γ ⊩∀x. P and choose x : X ∉FV (Γ). Suppose α ⊩ Γ, ∀x. P. Then for any t, α, x↦ → [[ t ]]α⊩ P and by Lemma 7.3 α ⊩P{x↦→t}.

(iv) The rule (∃I): Suppose Γ ⊩P{x↦→t}. Suppose α ⊩ Γ. Then α, x↦ → [[ t ]]α ⊩P, so α, x↦ →[[ t ]]α ⊩∃x. P, so α ⊩∃x. P.

(v) The rule (∃E): Suppose Γ ⊩ ∃x : X. P and Γ, P ⊩ C. Now suppose α ⊩ Γ, so α ⊩∃x. P, so for some u ∈ [[ X ]] , α, x↦ →u ⊩P. Also using Lemma 7.3 α, x↦ →u ⊩ Γ, so α, x↦ →u ⊩C and finally α ⊩C.

(vi) (EqI), (#I), (#E), (#c), and (EqE), follow by Lemma 7.4.

(vii) The rule (ИI): Suppose P/n = P ′•(ti) and Γ ⊩P{n↦→a}, a#ti. Suppose α ⊩ Γ so α ⊩P{n↦→a}, a#ti. n is fresh so by Lemma 7.3 α ⊩n#ti and n ∉ A(ti) for all i.

By clauses of the induction hypothesis and Lemma 7.5 α ⊩ (n a) ·s P{n↦→a} so α ⊩P ′ • ((n a) ·s ti), so α ⊩P ′ • (ti) ≡P. We deduce α ⊩Иn. P.

(viii) The rule (ExhaustA): Suppose Γ{x↦→a} ⊩P{x↦→a} for each a ∈ A(Γ, P), and for one atom n not in A(Γ, P). Suppose α ⊩ Γ.

If [[ x ]]α = a ∈ A(Γ, P) then we use Lemma 7.3 to conclude α ⊩ Γ{x↦→a} so α ⊩P{x↦→a} so α ⊩P.

Suppose [[ x ]]α = n′ ∉ A(Γ, P). Using notation and results from §7.4 [[ x ]] (n n′)·α = n and (n n′) · α ⊩ (n n′) · Γ ≡ Γ. We conclude (n n′) · α ⊩ Γ{x↦→n} so (n n′) · α ⊩ P{x↦→n} so (n n′) · α ⊩ P and α ⊩ (n n′) · P ≡P.

Since we have α ⊩P for all atoms, and thus all possible values of [[ x ]]α, we are done.

□

8. Proof normalisation

8.1. Overview of the proof.

The proof-normalisation proof follows standard lines. We establish terminology and sketch it.

As a matter of notation we let Π and Π′ vary over proofs (for example, Π might be2

(Axiom)A ∧B ⊢A ∧B(∧E1)A ∧B ⊢A.

We shall most usually only care about the final rule or few rules of a proof, in which case we write, for example Π′(∧E1)A ∧B ⊢A . Later on, for brevity and fitting proofs neatly into a line of text, we may use notation which would represent the proof just given as Π′, (∧E1) or (Axiom), (∧E1).

In a proof Π a critical pair is a pair of intro-rule followed after n intervening rules by an elim-rule for the same connective in the formulae. It is unseparated when n = 0 (the elim-rule follows immediately) and separated otherwise. This critical pair is separated by a single intervening rule (∨E) (so n = 1):

(17) Γ ⊢P ∨QΓ, P ⊢A Γ, P ⊢B(∧I)Γ, P ⊢A ∧BΓ, Q ⊢A Γ, Q ⊢B(∧I)Γ, Q ⊢A ∧B(∨E)Γ ⊢A ∧B(∧E1)Γ ⊢A

This critical pair is unseparated:

(18)Γ ⊢A Γ ⊢B(∧I)Γ ⊢A ∧B(∧E1)Γ ⊢A

Rules that can occur between critical pairs are those that do not change the top-level connective of their main formula. They are:

(19) (∨E) (C), (∃E) (C), (πI) (P, π ·s P), (πdiff) (P{x↦→π · t}, P{x↦→π′ · t}), (EqE), (NewA), and (ExhaustA) .

Proof-normalisation has two parts: commutation rules commute members of (19) with elimination rules (20), drawing them together. Essential cases then eliminate them entirely. A proof without critical pairs is normalised.

The possible elimination rules are:

(20) (∧E1), (∧E2), (∨E), (∀E), (∃E), (⊥E), (ИE), and (EqE).

We do not consider all the cases!

In a proof, let a closest critical pair be such that the number of intervening rules separating the relevant intro- and elim-rules is no greater than that of any other critical pair.

Definition 8.1

Let the proof-size of a Fresh Logic derivation (we write them Π, Π′, . . ., we may also call them proofs) be the pair (C, S):N×N. C is the number of rules intervening between a closest critical pair, S is the depth of the derivation as a tree. We order proof-size lexicographically left to right.

Say Π is smaller/larger than Π′ when it has lesser/greater size.

Clearly proof-size is well-founded. This section is now a long list of proof-transformations which do not increase, or strictly decrease, proof-size. Applied repeatedly in a natural way (outlined in Theorem 8.9) to a valid derivation, the procedure terminates with a normal form.

8.2. Essential case of ∀.

Theorem 8.2

A derivation Π concluding with (∀I),(∀E) may be transformed to a smaller derivation of the same conclusion.

Proof

Suppose we have a proof

Π =Π′x ∉FV (Γ)Γ ⊢P(∀I)Γ ⊢∀x. P(∀E)Γ ⊢P{x↦→t}

We use Lemma 8.3 to reduce it to Π′′ proving Γ{x↦→t} ≡ Γ ⊢P{x↦→t}. □

Lemma 8.3 (Substitutivity).

For s a term and z ∈V, if Π proves Γ ⊢P then there is a no longer derivation Π′ of Γ{z↦→s} ⊢P{z↦→s}.

So Fresh Logic enjoys the admissible rule

(21)Γ ⊢C Γ{z↦→s} ⊢C{z↦→s}

and it does not increase proof-size.

Proof

By induction on proof-size. If Π is a proof, write the transformed proof Π{z↦→s}.

The case (∀E). Suppose Π, (∀E) (t/x) is a proof, where x ∉FV (Γ, C). We α-convert so also x ≠ z and x ∉FV (s). P{x↦→t}{z↦→s} = P{z↦→s}{x↦→t{z↦→s}} and we see that Π{z↦→s}, (∀E) (t{z↦→s}/x) is the transformed proof.

The case (ИI). α-convert so n ∉ A(s). It suffices to verify that the side-conditions of this rule are preserved under substituting s for z. And indeed they are.

The case (ExhaustA). Suppose x ∉FV(s) and we have proofs Πa of Γ{x↦→a} ⊢ P{x↦→a} for all a ∈ A(Γ, P) and for (at least) one other fresh n. By applying the transposition (b n) to each of these for b ∈ A(s) not amongst the a, we obtain by FM equivariance applied to valid proofs, other valid proofs Πb. These proofs also inherit the induction hypothesis. Therefore we have proofs Πb{z↦→s} for b ∈ A(Γ, P, s), which includes A(Γ{z↦→s}, P{z↦→s}), and also fresh n. Then ⋀ b.Πb, (ExhaustA) is the transformed proof. □

8.3. Essential case of π and discussion of (πI) and (πdiff).

(πI) has no associated elimination rule and therefore no associated essential case. Recall from the formal definition (43) that the action π ·s P in (πI) is in any case a meta-level operation on syntax which does not change the top-level connective of P.

Clearly two consecutive uses of (πI) with π and π′, say, can be concatenated to one of π′ ◦π, and a slightly tidier notion of proof-normalisation can be obtained if we allow this and similar simplifications.

To make proof-normalisation work at all, we need the following result: However (πI) and (πdiff) are invertible in suitable senses made formal in the following two lemmas:

Lemma 8.4

Fresh Logic enjoys the admissible rule

(22)Γ, P{x↦→π′ ·s t} ⊢C Γ, P{x↦→π′ ·s t} ⊢ds(π, π′)#t Γ, P{x↦→π ·s t} ⊢C,

proof-size does not increase.

Proof

By (πdiff). □

Lemma 8.5

Fresh Logic enjoys the ‘elimination’ and ‘left-intro’ admissible rules

Γ ⊢π ·s P Γ ⊢P,(23)Γ, P ⊢C Γ, π ·s P ⊢C ,(24)

proof-size does not increase.

Proof

The first part from (πI) for π-1 then (πdiff) applied individually to every moderated variable in P, observing that ds(π-1 ◦π, Id) = ∅. The second part from (22) applied individually to every moderated variable in P using the same observation. □

8.4. Essential case of И.

Consider a proof of the form

(25)Π′Γ ⊢(P ′ •yi (ti)k i=1){n↦→a} Γ ⊢a#ti (ИI)Γ ⊢Иn. P ′ • (ti) Γ ⊢b#ti (ИE)Γ ⊢(P ′ • (ti)){n↦→b}.

We know (ИI) and (ИE) use the same slice here, because it is the least one covering n. Side-conditions dictate that a, b ∉ A(P ′). Transform this to

Π′Γ ⊢(P ′ •yi (ti)k i=1){n↦→a} ≡(P ′{n↦→a}) • (ti)(πI)Γ ⊢((a b) ·s (P ′{n↦→a})) • (ti) Γ ⊢a, b#ti (#E)∗Γ ⊢(P ′{n↦→b}) • (ti) ≡(P ′ • (ti)){n↦→b}.

Here (#E)∗ denotes many applications of (#E). For each moderated variable in π ·s (P ′{n↦→a}) • (ti) we pull (a b) into the term (conjugating a to b on the way down) to the site of the slice with some ti, then use our proofs that ds((a b), Id) = {a, b}#ti to eliminate the transposition.

The behaviour of π at binders ∀x and ∃x in (43) is carefully chosen so that (a b) is never introduced to a moderation of x. (πdiff) would be useless to reduce π ◦κ ◦π-1 here because it uses capture-avoiding substitution.

We could simplify the definition (43) at the expense of making (πdiff) ‘contextual’; allowing possibly capturing substitution. This is reasonable but would complicate the proof of soundness because (πdiff) then invents names for bound variables. To account for this we would have to quantify over suitable extensions of the valuations associated to frames, which looks complicated.

8.5. Commutation cases.

The other essential cases are easy, standard, or both.

Recall from §8.1 that we work by induction on the closest intro/elim pair, and to bring critical pairs together we must show that (∨E), (∃E), (EqE), (πI), (πdiff), (NewA), and (ExhaustA), commute downwards past (∨E), (∧E1), (∧E2), (⇒E), (∀E), (∃E), (EqE), and (ИE).

A simple and standard example is that a proof-fragment of the form (∨E),(∧E1)

(26)Γ ⊢P ∨Q Γ, P ⊢A ∧B Γ, Q ⊢A ∧B(∨E)Γ ⊢A ∧B(∧E1)Γ ⊢A

can be transformed to one of the form (∧E1),(∨E):

(27)Γ ⊢P ∨QΓ, P ⊢A ∧B(∧E1)Γ, P ⊢AΓ, Q ⊢A ∧B(∧E1)Γ, Q ⊢A(∨E)Γ ⊢A

We do not give all the examples. They do require weakening:

Lemma 8.6 (Weakening).

If Π proves Γ ⊢C then it proves Γ, ∆⊢C for any set of formulae ∆.

Thus the following is an admissible rule:

(28)Γ ⊢C Γ, ∆⊢C
Proof

By induction on proofs. □

Lemma 8.7

(πI) commutes downwards through all elimination rules.

Proof

The case of (∀E) uses the fact that π ·s (P{x↦→t}) ≡ (π ·s P){x↦→t}, the case of (∃E) uses (24) and (22), the case of (ИE) follows since n may be renamed so π ·Иn. P ≡π ·Иn. P. Other cases are easy. □

Lemma 8.8

(πdiff) commutes downwards through all elimination rules.

Proof

The case of (∀E) uses Lemma 8.3, that of (∃E) uses (22). Other rules are easy, except for (ИE) which we consider in more detail. Under consideration is a proof of the form (29)

Π′Γ ⊢P{x↦→π′·s t} Γ ⊢ds(π, π′)#t(πdiff)Γ ⊢P{x↦→π·s t} Γ ⊢a#ti(P{x↦→π·s t})/n = P ′•yi(ti)(ИE)Γ ⊢Иn. (P{x↦→π·s t}).

For brevity write C for P{x↦→π ·s t}. C/n is a least slice and n (chosen fresh) satisfies n ∉ A(π, π′, t). Thus the substitutions π ·s t and π′ ·s t affect parts of C only within the ti and we can write C/n as P ′ • (t′ i{x↦→π ·s t}) for appropriate t′ i. This suffices to allow us to perform the commutation. □

The commutation of (EqE) with (ИE) is similar.

Similar commutation results hold of the other rules; (∃E), (EqE), (NewA), and (ExhaustA). For example, commuting (ExhaustA) with (∀E). Suppose we have a proof of the form

(30)Πn⋀n ∈S. Γ{z↦→n} ⊢∀x. P{z↦→n}(ExhaustA)Γ ⊢∀x. P(∀E)Γ ⊢P{x↦→t}.

Here S contains A(Γ, P) and at least one fresh atom. Let A(t) = S′ and without loss of generality (swapping if necessary) assume the fresh atom(s) a in S are also fresh for S′ (and also assume z ∉FV(t)). Choose one such fresh a. Then for each a′ ∈S′ the proof (a′ a)·Πa is by FM equivariance a valid proof of Γ{z↦→a′} ⊢∀x. P{z↦→a′}. We now construct the following valid proof:

(31)Γ{z↦→n} ⊢∀x. P{z↦→n}(∀E)⋀n ∈S ∪S′. Γ ⊢P{x↦→t}{z↦→n}(ExhaustA)Γ ⊢P{x↦→t}
Πn

We never need to use the following observation in this paper, so we leave it to the reader to check that (NewA) commutes down through all rules — except for (∀I). Thus we can ‘garbage-collect’ all the fresh atoms right at the end of the proof (or reading bottom-up, ‘generate’ them), except for those atoms which are generated fresh for variables which are then consumed by a (∀I).

8.6. Proof normalisation.

Theorem 8.9 (Proof normalisation).

Any derivable judgement of Fresh Logic has a proof in a normal form.

Sketch proof

We proceed in the standard way on proof-size. We bring a closest critical pair closer together with commutation rules, then eliminate it with an essential case. □

9. Completeness

9.1. (Small).

Fresh Logic is not complete with respect to the semantics considered in §7. This is because no axiom insists that there be countably many atoms (as is the case in our class of models); perhaps there are uncountably many, and all elements have countable, rather than finite, support.

In order to make Fresh Logic complete3 we must add an axiom to the effect that ‘atoms are countable’. This is not expressible in First-Order Logic [17], but in the case of Fresh Logic we can get around this, exploiting the fact that we represent atoms by a class of what are, essentially, constants.

We add one axiom:

⋀ L ∈CoFinA. Γ, L#t ⊢P Γ ⊢P.

(Small)

Here t is any term, ⋀ L ∈ CoFinA indicates a(n infinite) conjunction of proofs, one for each cofinite set of atoms L, and L#t denotes the (infinite) list of hypotheses l#t for each l ∈L.

(Small) changes to our notion of proof in two ways: sequents may mention infinitely many assumptions, and instances of proof-rules may have infinitely many hypotheses above the line. To adjust for this, we need to introduce a notion of freshness for sets of formulae, and for derivations.

Recall from §7.4 that given atoms a, b and a formula P we write (a b) · P for the formula obtained by swapping a and b in the syntax of P. Given a (possibly infinite) set of formulae Γ write (a b) · Γ for the same operation applied pointwise.

Then the infinite sequents needed to write (Small) still have finite support in the sense that

Иa. a#(Γ ∪{P})

where a#x means Иb. (b a) · x = x, and И here means ‘for all but finitely many atoms’. Write

S(Γ) for {a ∈A | ¬a#Γ}.

As a matter of notation write S(Γ, P) for S(Γ ∪{P}). Say Γ has finite support when S(Γ) is finite.

We extend the notion of sequent to allow Γ ⊢P to be a sequent even if Γ is infinite provided that:

• Γ has finite support.

• Γ mentions finitely many variable symbols x, y, z (see below for explanation).

To account for possibly infinite sets of assumptions in sequents Γ ⊢ P, modify (NewA) and (ExhaustA) as follows:

Γ, a#ts ⊢C Γ ⊢Ca#Γ, C(32)
⋀ n ∈S. Γ{x↦→n} ⊢P{x↦→n} Γ{x↦→t} ⊢P{x↦→t}S(Γ, P) ⊊S(33)

It is an easy exercise to verify that if Γ is finite, the condition S(Γ, P) ⊊S reduces to the condition A(Γ, P) ⊊S, and a#Γ, C reduces to a ∉ A(Γ, C), and in general that if Γ is finite then S(Γ) is precisely the set of atoms mentioned in Γ which is in our notation written A(Γ).

Given a proof Π write (a b) · Π for the proof obtained by swapping a and b throughout the syntax of Π. Write a#Π when Иb. (b a) · Π ≡ Π. Then proofs (even if they mention (Small)) have finite support in the sense that

Иa. a#Π.

Write S(Π) for {a ∈A | ¬a#Π}.

We now observe that

S({Γ, L#t, P} | L cofinite}) = S(Γ, P),

so that S(Π) is still finite, even if Π mentions (Small).

Note finally that, even in the presence of (Small), proofs remain finitely deep. That is, given any proof there is some number n such that if we traverse the proof from bottom to top, the length of our path is no greater than n.

To prove that Fresh Logic with (Small) is still normalising, it now suffices to observe that (Small) may be commuted down through all the elimination rules in (20), and to observe that ‘most of the time’, formally that means for cofinitely many hypotheses of (Small), if some proof-transformation may be applied to one of those hypothesis, the same proof-transformation may be applied to them all (it suffices to treat en bloc those such that L is disjoint from S(Γ, P)).

The proofs up till now generalise (for example Lemma 8.6, which we stated for sets of formulae in anticipation of this development) and we conduct the rest of the paper in this more general setting, though we will not henceforth specify that we are using the generalised form of a result.

We still insist that Γ mention finitely many different variable symbols x ∈V. Otherwise proofs might break because Γ might mention all of V and we could not guarantee there exists x ∉FV (Γ) (as required by some rules, like (∀I)).

It is now easy to verify that Fresh Logic + (Small) still normalises (and in finitely many steps); since (Small) introduces no new essential cases, we only need check that (Small) commutes down through all elim-rules in (20), and that any proof-transformations occurring in its hypotheses may be treated en bloc for ‘most’ of the time.

Lemma 9.1

(Small) is sound with respect to the semantics of §7.

Proof

Fix some model M and α ∈M. Suppose for all L ∈ CoFinA we know if α ⊩ Γ, L#t then α ⊩P. Suppose also that α ⊩ Γ.

Choose L disjoint from S(x) for all x ∈Uα, and disjoint also from A(t). It is easy to verify by induction on the syntax of t that L#[[ t ]]α so α ⊩L#t. By assumption therefore α ⊩P as required. □

Notation 9.2

Say a context Γ is consistent when Γ ⊬⊥.

(Small) gives us completeness via the following theorem:

Theorem 9.3

Let Γ in some language of Fresh Logic L be consistent and suppose Γ ⊢∃x : X. P is derivable. Then there exists n ∈N and list of n atoms (ai)n 1 such that we may extend L with a fresh constant f : An → X to L′ and in this new language Γ, P{x↦→f(ai)} is consistent.

Similarly, if Γ is consistent and Γ ⊬∀x. P, then there exists n, f, and (ai)n 1 such that we may extend L as above, and in this new language Γ ⊬P{x↦→f(ai)}.

Proof

Consider the context Γ, P{x↦→f(ai)}. f has no axioms so if Γ, P{x↦→f(ai)} ⊢ Q is derivable in L′ where Q is a sentence of L (i.e. does not mention f), then the proof may be transformed into one of Γ, P, L#x ⊢Q, for Ldef= A\{ai⏐⏐ 1 ≤i ≤n}.

Now suppose Γ, P{x↦→f(ai)} ⊢⊥ for all n. Then by the transformed proofs we know for all L ∈ CoFinA that Γ, P, L#x ⊢ ⊥. By (Small) we may deduce Γ, P ⊢⊥. Since Γ ⊢∃x. P we may apply (∃E) to deduce Γ ⊢⊥, contradicting the assumption that Γ is consistent.

The last part is similar. □

9.2. (ExhaustA) and (NewA).

(ExhaustA) and (NewA) give theorems similar in spirit to Theorem 9.3, and also needed for the completeness proof:

Theorem 9.4

Suppose Γ is a consistent context and suppose t : A is any term. Then there exists a ∈A such that Γ, t = a is consistent.

Proof

If Γ, t = a ⊢ ⊥ for every a, then Γ, t = x ⊢ ⊥ by (ExhaustA) (x ∉ FV (Γ, t)). Thus Γ ⊢∀x. x ≠ t and in particular Γ ⊢t ≠ t, whence Γ ⊢⊥, which contradicts consistency of Γ. □

This ties in with our definition of frame α, which insisted that [[ A ]]α ∼= A so that [[ t ]]α = a for some a.

Lemma 9.5

If Γ is consistent then for fresh a#Γ and any list of terms ts, Γ, a#ts is consistent.

Proof

By (NewA). □

9.3. Remark on literal equality.

Recall from §7.1 that we commented on the fact that frame maps need not be injective, and equality is interpreted as literal equality rather than some relation with special properties.

We have to do this. When below we build frames out of so-called prime theories (thus, out of syntax) to prove completeness, we interpret terms by their equivalence class under provable equality. If instead we interpreted terms as themselves, a variable symbol x would not have finite support (necessary for a Nominal Set semantics), since π · x is not the same term as x for any π ≠ Id, though they may be provably equal.

9.4. Prime theories.

Definition 9.6

A set Φ of (possibly open) sentences is a prime theory when

(i) Φ is deductively closed.

(ii) Φ mentions only finitely many variable symbols x ∈V.

(iii) If P ∨Q ∈ Φ then P ∈ Φ or Q ∈ Φ (or both).

(iv) If ∃x. P ∈ Φ then P{x↦→t} ∈ Φ for some term.

(v) If t has sort A then for some a ∈A, t = a ∈ Φ.

(vi) If Иn. P ∈ Φ then, for P/n = P ′ •yi (ti)k 1, there is an a ∈A such that a#ti ∈ Φ for 1 ≤i ≤k, and P{n↦→a} ∈ Φ.

Lemma 9.7

If Γ ⊬P then there is a prime theory Φ ⊇ Γ such that P ∉ Φ.

Proof

Write UΦ for the variables mentioned in Γ and P. We build an ascending chain of theories Γ0=Γ ⊆ Γ1 ⊆. . .. Choose some ordering on constants, predicate symbols, variables, and atoms, with free variables in UΦ. Use that to enumerate terms and formulae of Fresh Logic with free variables in UΦ. At each step, we use this enumeration to extend Γk to Γk+1 according to the following recipe:

(i) Γ0 = Γ.

(ii) Γ4k′↦ → Γ4k′+1: take the least P ∨Q such that P ∨Q ∈ Γ4k′ and P, Q ∉ Γ4k′. Add the least of the two to give Γ4k′+1, let Γ4k′+1 = Γ3k otherwise.

(iii) Γ4k′+1↦ → Γ4k′+2: take the least ∃x. P such that for no t is P{x↦→t} ∈ Γ, if one such exists. If one such exists, adjoin P{x↦→f(ai)} for some fresh constant symbol f and atoms ai preserving consistency if Γ4k′+1 is consistent. This is possible by Theorem 9.3.

(iv) Γ4k′+2↦ → Γ4k′+3: take the least t : A such that for no a ∈A is t = a ∈ Γ, if one such exists. If one such exists, adjoin t = a for an a, preserving consistency. This is possible by Theorem 9.4.

(v) Γ4k′+3↦ → Γ4(k′+1): take the least Иn. P such that Γ4k′+3 does not satisfying the closure condition (which we do not rewrite) for it, if one such exists. If one such exists there is an atom a such that Γ4k′+3, a#FV(ti) is consistent by Lemma 9.5. This new context entails P{n↦→a} by (ИE) and we let Γ4k′+4 be Γ4k′+3, a#ti, P{n↦→a}, or Γ4k′+3, as appropriate.

Take Φ = ⋃i Γi, which we can verify is a prime theory by construction (deductive closure is ‘for free’ because if Φ ⊢P then Φ ⊢P ∨P so P ∈ Φ). □

Lemma 9.8

In a prime theory Φ;

(i) If t : A then Φ ⊢t = a for some a ∈A.

(ii) If x : X ∈UΦ then Φ ⊢x = f(as) for some function symbol f and atoms as.

(iii) For x as above, Φ ⊢a#x for cofinitely many a.

Lemma 9.9

A prime theory Φ in a language L generates a frame, which we also write Φ, as follows:

(i) [[ X ]] is the set of equivalence classes of t : X such that FV (t) ⊆UΦ, up to provable equality t = t′ ∈ Φ. Write such a class [[ t ]] . The permutation

action is given by the action on the representatives; π · [[ t ]] def= [[ π ·s t ]] .

(ii) [[ c ]] is the function mapping ⟨[[ t1]] , . . . ⟩ to [[ c(t1, . . .) ]] .

(iii) The canonical isomorphism [[ A ]] ∼= A is given by [[ t ]] maps to that a such that Φ ⊢t = a.

(iv) [[ p ]] is the set of ⟨[[ t1]] , . . . ⟩ such that p(t1, . . .) ∈ Φ.

(v) [[ ⊤]] = {∗} and [[ ⊥]] = ∅.

Accessibility Φ ⊑ Φ′ holds in a natural way when Φ is a prime theory for L and Φ′ a prime theory for a superlanguage L′ of L, and UΦ ⊆UΦ′, and Φ ⊆ Φ′.

Proof

We verify every clause of Definition 4.1. □

We shall be imprecise and write t ∈ Φ to mean t is a sentence in the language L of Φ, such that FV (t) ⊆UΦ.

Notation 9.10

Take some language L of Fresh Logic. Prime theories Φ in languages L′ ≥L, and their maps, form a Kripke model of L in the sense defined above. Henceforth we shall write Φ ⊩ P, and this will mean model-theoretic entailment with respect to this model.

Lemma 9.11

Φ ⊩P if and only if P ∈ Φ.

Proof

If P ∈ Φ then Φ ⊢P so by soundness Theorem 7.7, Φ ⊩P.

(i) Suppose P ≡p(ts). Φ ⊩P when p(ts) ∈ Φ by definition.

(ii) Suppose P ≡P1 ∨P2. Then either P1 or P2 is in Φ, and we apply the induction hypothesis. The case of ∧ is similar but even simpler.

(iii) Suppose P ≡P1 ⇒P2. Φ ⊩P when

(34)∀Φ′ ⊑Φ. Φ′ ⊩P1=⇒Φ′ ⊩P2P1 ∈Φ′P2 ∈Φ′.

(The second line rewrites parts of the first using the inductive hypothesis.)

If P1 ⇒P2 ∉ Φ then Φ, P1 ⊬P2 and Lemma 9.7 says there is Φ′ ⊑ Φ, P1 such that P2 ∉ Φ′. Therefore Φ ⊮P1 ⇒P2.

(iv) Suppose P ≡∀x : X. P1. Φ ⊩P when

(35)∀Φ′ ⊑Φ. ∀t : X ∈Φ′. Φ′ ⊩P1{x↦→t} P1{x↦→t} ∈Φ′.

If ∀x. P1 ∉ Φ then Φ ⊬∀x. P1 and by Theorem 9.3 for some constant f in a superlanguage L′ ⊑L and atoms as, Φ′ ⊬P{x↦→f(as)}.

(v) Suppose P ≡Иn. P1 where n is chosen fresh. Φ ⊩P when Φ ⊩P1. By induction hypothesis Φ ⊢P1 and by properties of the deduction system and prime theories, Φ ⊢Иn. P1.

(vi) Suppose P ≡t1 = t2: X. Φ ⊩t1 = t2 when [[ t1]] = [[ t2]] ∈[[ X ]] , which is the case precisely when Φ ⊢t1 = t2.

(vii) Suppose P ≡t1: A#t2: X. Suppose Φ ⊩t1#t2. Φ ⊢t1 = a for some a ∈A so Φ ⊩a#t2 and a#[[ t2]] .

Then for cofinitely many b, (b a) · [[ t2]] = [[ t2]] , thus for cofinitely many b, Φ ⊢ (b a) ·s t2 = t2. Choose a b such that we can apply (ИI) to deduce Φ ⊢Иb. (b a) ·s t2 = t2. Using (D6) from Figure 4 we conclude Φ ⊢a#t2 and so Φ ⊢t1#t2.

□

Extending notation from Notation 7.6, write Γ ⊩P when for all models M, Γ ⊩M P.

Theorem 9.12 (Completeness).

Γ ⊢P ⇐⇒ Γ ⊩P.

Proof

Suppose Γ ⊢P. Then Γ ⊩P by soundness Theorem 7.7. Conversely if Γ ⊬P, there is a prime theory Φ ⊇ Γ such that P ∉ Φ by Lemma 9.7 and by Lemma 9.11 Φ ⊮P. □

10. Alternative formulations of Fresh Logic

We made several design decisions in Fresh Logic, we now discuss how we might do things differently, and if that does not work, why.

10.1. No swappings or #.

We might envisage a calculus without swappings and #. The И-intro and elim rules would be controlled by a top-level quantifier context consisting of a list of ∀ and И quantifiers whose ordering encodes freshness information in a way we have already seen in the theory of Fresh Logic in (D4) in §6, and [8].

For example, in such a logic we might axiomatise # as ∀x.Иa. ( ⊢a#x).

In (∀E), x is instantiated for t. For Lemma 8.3 to work we must insist as a side-condition of (∀E) that we only substitute a t which satisfies the freshness conditions encoded in the position of x in the quantifier context, which we can only do with conditions on the positions of where y ∈FV(t) appear in the quantifier context. The details of getting this to work seem to become extremely complex.

The problem is in Lemma 8.3. In the modified logic sketched above {x↦→t} is only admissible when t satisfies the freshness constraints on x encoded in the quantifier context. It is difficult to build a framework to formally deduce when this is so, and would be even more difficult in the presence of term-formers binding atoms, e.g. atoms-abstraction [a]x [12, 26], which for simplicity we omitted from Fresh Logic. See the comparison with Generic Judgements in the Conclusion.

10.2. Variables x : A in swappings.

As it stands Fresh Logic only allows swappings by atoms (a b)—not swappings by variables (of type A), which would be (x y). Note that we can always determine a = b or a ≠ b by whether a ≡b, so we can always simplify an expression of the form (a b) ·s c. This is why Fresh Logic has no moderated atoms. This is not so of x = y or x ≠ y, so we must also consider nested swappings such as (((x′ y′) ·s x) (u v) ·s y).

Having constructed the normalisation and completeness proofs, it appears Fresh Logic would sustain this extension. The difference which would be probably most significant is that (πdiff) changes completely and splits into three (rules implementing) identities

(36) (x x) · u = u (x y) ◦(x y) · u = u (x y) ◦(x′ y′) · u = (x′ y′) · (((x′ y′) · x) ((x′ y′) · y)) · u

which characterise the group generated by the swappings (x y) [15, Beispiel 19.7], [26, p.10].

10.3. FM swapping in this document.

This paper is an analysis of a particular syntax system Fresh Logic. It has two kinds of variable symbol; x ∈V and a ∈A. Both can be bound, by ∀, ∃ and И respectively.

We encounter the usual problems with capture-avoidance and renaming. Sometimes we are ‘traditional’ about it and say “α-rename to assume. . . ”. Sometimes it is more convenient to be rigorous and talk about swapping. This is particularly with (ExhaustA) and because atoms a appear in both Fresh Logic syntax and its semantics, there are points in this document where swappings and freshnesses are rather beautifully applied to judgements and functions with both semantic and syntactic parts, such as ‘α ⊩P’ or ‘[[ t ]]α’ (Theorem 7.7, Lemma 8.3).

Γ ⊢P Γ ⊢a#ti (i = 1, . . . , k) Γ ⊢Иa. PP/a = P ′ •yi (ti)k 1(ИI)Γ ⊢Иa. P Γ ⊢a#ti (i = 1, . . . , k) Γ ⊢PP/a = P ′ •yi (ti)k 1(ИE)Γ ⊢P Γ ⊢∀x. Px ∉FV (Γ)(∀I)Γ ⊢∀x. P Γ ⊢P{x↦→t}x ∉FV (Γ, C), P{x↦→t} defined(∀E)Γ ⊢P{x↦→t} Γ ⊢∃x. Px ∉FV (Γ)(∃I)Γ ⊢∃x. P Γ, P ⊢C Γ ⊢Cx ∉FV (Γ, C), P{x↦→t} defined(∃E)
Figure 5. Rules of Fresh Logic with И non-binding

In fact ‘secretly’ we have used an FM treatment of variables and binding, V and A, throughout, simply because we understand it well, it works, and it is completely rigorous. We still present things traditionally; we write x ∉FV (Γ) in (∀I) instead of ‘x fresh’.

10.4. Иa does not bind a.

In the construction of Fresh Logic syntax, И binds the abstracted atom, so that for example Иn. n#x and Иn′. n′#x are equal formulae just like ∀x. a#x and ∀x′. a#x′.

The essential case of И uses swapping to rename a to b if И was introduced using a and eliminated using b. However, let us backtrack: atoms a, b, c, n, n′. . . are constants. How can you bind a constant?

The answer adopted in the bulk of this paper is: atoms a, b, c, n are not constants but variables of a particular kind which denote distinct elements of A. For brevity write their denotation also a, b, c, n . . . ∈A and call them atoms. Atoms behave like constants in that a ≠ b if a≢b, but they can still be bound.

In this subsection we consider an alternative. Consider a Fresh Logic in whose syntax И does not bind, so Иa. a#x and Иb. b#x are distinct formulae. There is now a notion of ‘syntactic free’ and ‘syntactic bound’ atom of a formula.

Substitution {x↦→t} is problematic because syntactic capture is now possible, e.g. in (Иa. a#x){x↦→a}. We do not introduce syntactic α-renaming of syntactic bound atoms, instead we declare substitution undefined in this case. Similarly permutation (43) changes in the clause of И, so π ·sИa. P is equal to Иa. π ·s P if a ∉ A(π) and is undefined otherwise.

The technical benefit is that the И intro- and elim-rules, and their proof-theory, are simplified. We give the parts of Fresh Logic which must change in Figure 5.

The essential case of И is now just as follows:

(37)Π′Γ ⊢(P ′ •yi (ti)k i=1) Γ ⊢a#ti (ИI)Γ ⊢Иa. P ′ • (ti) Γ ⊢a#ti (ИE)Γ ⊢(P ′ • (ti)).

We just transform this to Π′.

This rule is compellingly simple but the ∀ and ∃ rules change, violating the Slogan of the Introduction—though not completely because for P containing no И quantifiers P{x↦→t} is always defined and as usual.

An equivalent formulation of the same condition was suggested by Pitts, we devote this paragraph to it. Recall from §7.4 the discussion of meta-level swapping. Then we can define α ⊩Иa. P when for fresh n, (n a) · α ⊩ P. The two formulations are equivalent: (n a) ·α ⊩P if and only if α ⊩P{a↦→n}. The proof follows since for fresh n, (n a) · P equals P{a↦→n} because n is fresh and does not occur in P. We use {a↦→n} here because it is more concrete for the reader coming from outside FM theory.

The theory still stands mostly unchanged with non-binding И, but the proofs and definitions do shift a little, and in quite interesting ways. We now discuss how.

The clause for И in Definition 7.2 changes because a is not bound in the formula and so cannot just be chosen fresh, like n was. The solution is simple: α ⊩P when for fresh n, α ⊩P{a↦→n}.

In Lemma 7.5 we must insist that π · P be well-defined, which need not be the case as discussed above. The clause for И becomes: Suppose P ≡Иa. P ′ and α ⊩Иa. P ′. Choose n fresh. Then α ⊩P ′{a↦→n} so by induction hypothesis α ⊩π ·s (P{a↦→n}). Using the assumptions that a, n ∉ A(π), we deduce α ⊩ π ·sИa. P.

We have already discussed the essential case of И in this formulation. The clause for И in Definition 9.6 is unchanged. The one in Lemma 9.11 becomes: suppose P ≡Иa. P1. Choose n fresh. Φ ⊩P when Φ ⊩P1{a↦→n}. By induction hypothesis Φ ⊢P1{a↦→n} and by properties of the deduction system and prime theories, Φ ⊢Иa. P1.

So we see that the only difference using a non-binding Иa is that we have to choose n fresh and explicitly substitute a for n, whenever we unpack the quantifier. The interaction with substitution also engenders side-conditions on ∀-elimination and ∃-introduction rules.

11. Conclusions

We have presented ‘Fresh Logic’, a first-order logic enriched with И (for ‘fresh’), # (for ‘fresh for’), and (a b) (for ‘rename’).

We provide natural-deduction and sequent systems such that the FM-free core is unmodified First-Order Logic. The logic is complete with respect to a natural FM semantics, and (all?) the well-known tautologies of FM theory can be derived in it. To our knowledge this is only the second proof-theory of logics for handling names and binding, in the sense of proof normalisation or cut-elimination. The first was the Tiu-Miller logic of Generic Judgements, discussed below.

The most immediate contribution of this paper is to show that И is not incompatible with proof theory. Looking beneath this result, the essential case for И in proof normalisation teaches us about its relation with # and swapping, whose presence in the logic is necessary for that essential case to work. The other major construction, a sound and complete semantics, relates the logical structure of Fresh Logic to a good notion of validity and leads us to two interesting deduction rules (ExhaustA) and (Small).

There are some beautiful interactions between FM atoms in syntax, proofs, and semantics. Some of them (see also §7.4) are:

(i) Equivariance of validity of deduction trees Π in Lemma 8.3.

(ii) Swapping applied to models α in Theorem 7.7.

(iii) In (ExhaustA) we need only check the atoms appearing in the conclusion and one fresh atom, rather than atoms occurring in the support of the

denotations of the variable symbols in the conclusion (of course not, since denotation is distinct from derivability, but for comparison Generic Judgements build something corresponding to support into derivability via the local and global signatures).

11.1. Related work.

Work based on FM semantics. Pitts’ Nominal Logic [26] and Fresh Logic are both formal systems based on first-order logic and FM-sets semantics. Nominal Logic is classical, Fresh Logic is intuitionistic, but that difference is inessential.

Nominal Logic was created to show that first-order logic can usefully describe FM sets, which previous work had shown can model names and binding in abstract syntax. It is interested in expressivity and soundness, especially with respect to modelling object-level syntax. It is not interested in other things, such a proof-theory; thus for example it uses a Hilbert-style axiom system.

This paper takes the expressivity for granted; we do not, for example, present a Fresh Logic axiomatisation of an abstract machine for evaluating λ-calculus terms, or a π-calculus transition system. We know we could: previous work has done these things outside of a proof-theoretic framework and that work used the same semantics as Fresh Logic, for which Fresh Logic is sound and (suitably strengthened) complete. We are also confident these things could be cleanly expressed, because the syntax of Fresh Logic is not so different from that of existing FM-based systems.

Another Hilbert-style axiomatisation of FM-sets is in [10]. This similar to Nominal Logic, but as a formal development in Isabelle of the full theory of FM-sets as described in [12, 9].

Urban, Pitts, and Gabbay investigate Nominal Unification [28]. We quote that work in technical aspects, in particular the notions of moderated variable π · x and difference set ds(π, π′).

Work based on Higher-Order Abstract Syntax. The basic principles of Higher-Order Abstract Syntax (HOAS) are presented in [24]. This is most concerned with expressivity, and corresponds in the context of HOAS to [12] in the context of FM.

One example of an axiomatic system based on HOAS (there are others) is the Theory of Contexts [13, 19]. This is a consistent [3] set of axioms such as can be stated in COQ and then programmed with. This corresponds to [10] or [25]; proof theory is not the issue. There is a semantics based on presheaves [19]. Fresh Logic semantics is FM-sets, which can also be viewed as presheaves [12]. However, the two presheaf semantics are not directly comparable. A detailed analysis of how and why is not possible here, and is probably slightly premature since the technologies are still maturing.

The HOAS-based work most closely corresponding to Fresh Logic is by Tiu and Miller [20]. They develop a sequent system (with cut-elimination) Generic Judgements. They use it to reasoning on names and binding, so the application domain is similar to that of Fresh Logic. Generic Judgements have a quantifier ∇ which is similar to И in some respects (see self-duality below) and is used in much the same way. Generic judgements lack the complication (?) of anything like # and (a b), though they do enrich sequents with annotations which are essentially meta-level ∇-quantifiers. This makes the intro-rules for ∇ particularly simple; the structure is built into the sequents.

∇ picks a ‘generic’ name. A generic name in Generic Judgements is one such that we ‘promise’ not to use any special properties it may have. A connection to FM is that a fresh name in FM is generic amongst fresh names by the some/any property. It may be that this is the only commonality.

It is interesting to note that Fresh Logic and Generic Judgements approach the same problem from opposite directions. In Generic Judgements the meta-level annotations keep track of which generic elements are in use, whereas in Fresh Logic object-level freshness keeps track of which atoms are not in use.

Of course, in this paper Fresh Logic is interested in proof-theory, soundness, and completeness. We do, therefore, see a lot of proof-theory and models. We have not considered the logic-programming aspects, like Generic Judgements (which would be interesting future work).

Our inspiration to pursue Fresh Logic dates back to a conversation with Miller and Tiu in INRIA in October 2002. Our first attempts to formulate it tried to just use И, imitating the structure of sequents of Generic Judgements; a judgement consisted of a context and a conclusion, wrapped in a top-level list of nested И and ∀ quantifiers, for example ∀x.Иa. ( ⊢a#x).

We found that in the context of FM sets this was inexpressive and furthermore it gave bad proof theory. The underlying reason seems to be in the comment we made above, that HOAS-based techniques keep track of the names in a term (local and global signatures in Generic Judgements), while FM-based techniques keep explicit track of the names not in a term (freshness #). Once we added freshness # and swappings, all the problems vanished; we think this is an interesting observation, that И needs freshness and swapping to proof-theoretically work.

More concretely, there were serious problems with Lemma 8.3 because, in the system sketched above, a substitution of t for x is only admissible when t satisfies all the freshness constraints of x. In the system as it stands those freshness constraints are explicit assumptions of the for a#x. If they no longer hold after substitution, e.g. if t = a, then the judgement as a whole is trivially valid since a#a entails anything.

There are other approaches to syntax and binding and all have papers exploring how well an object-level system (a π- or λ-calculus, usually) can be expressed and programmed on. To our knowledge (and we may be wrong) Fresh Logic and the logic of Generic Judgements are the only work on the proof-theory of names and binding, in the sense of normalisation and cut-elimination.

One possible exception is work by Menni [18]. This analyses a class of И-like quantifiers in the context of categorical logic.

Work derived from logics for structured data and trees. Caires and Cardelli introduced Spatial Logics for reasoning about π-calculus processes [5]. These have two sorts, atoms and processes, and include modalities and constructors specialised to this domain. At its core is a logic with И similar to Fresh Logic. This makes sense since the novel feature of their logics was precisely an FM-style И.

One significant technical difference is that Fresh Logic has atoms a and variables x of sort A where Spatial Logic only allows variables. On the other hand Fresh Logic only allows swappings by atoms (a b), where Spatial Logic (having no atoms) allows swappings by variables (x y), and also (since equality of variables need not be decidable for a given context) nested swappings ((x′ y′) ·s x (u v) ·s y). We discussed extending Fresh Logic with variable swappings à la Spatial Logics in §10.2.

Spatial Logic also has И bind variables, thus Иx rather than Иa. We do not necessarily understand the difference between these two choices, but perhaps there is none in the sense that in either case the datatype describing the choice of fresh atom (concretely, as in Иn, or the atom to which to evaluate the x bound in Иx) is A ⊗−.

11.2. Future work: Proof-terms, higher orders.

An obvious next step is to add proof-terms to Fresh Logic. There is no evident difficulty to this. It will be interesting to see what λ-calculus we get.

It would be interesting to consider higher-order versions of Fresh Logic, and especially to see how this changes (simplifies?) the notion of slice, which we needed to express the И intro- and elim-rules (ИI) and (ИE).

A higher-order Fresh Logic could form the basis of a И-version of the Isabelle/Pure meta-language, suitable for modelling syntax. Isabelle/Pure [23] is a higher-order logic with ⇒, ∀, and = only, consistent with a philosophy of ‘weak meta-language, strong object-language’. The issues involved in implementing an FM object-logic in Isabelle/Pure, and why adding И would be useful though it conflicts with that philosophy, are discussed in [10].

11.3. Self-duality.

Fresh Logic’s И quantifier has proof-theoretic interest in its own right. Consider ∀ and ∃. These are dual in the sense that ¬∀x. P ⇔∃x. ¬P. Call a quantifier ∇ self-dual when ¬∇x. P ⇔∇x. ¬P, or more briefly ¬∇≡∇¬. This makes the quantifier’s rules symmetric.

It is an old observation that И is self-dual [12, (30)]. The FM atoms some/any property is logically composed of self-duality conjoined with (in the same shorthand) ∀⇒И⇒∃.

We named ∇ after Tiu and Miller (see above). To our knowledge self-duality is a new logical phenomenon. The Tiu-Miller ∇ and Gabbay-Pitts И quantifier are the only two so far discovered. (Thanks to this paper, И is now respectable and has a proof-theory!) What is the theory of an arbitrary self-dual quantifier ∇?

Menni [18] inspired by FM considers И-quantifiers in a purely category-theoretic context, taking self-duality as the quantifier’s core feature. This is one answer.

11.4. Vanilla.

Fresh Logic is a meta-language for reasoning on fresh names whose core is unmodified First-Order Logic. We have investigated the effects of this extension of First-Order Logic with ‘vanilla’ FM on proof-theory and semantics. Perhaps this could serve as a basis for modifications in application-specific directions, presumably with object-level names and binding, just as we do in general with First-Order Logic.

Caires-Cardelli Spatial Logics are a first instance of this, retrospectively. We can hope this paper will be of use to them and others in the future.

References

1. John Bell and Moshé Machover, A course in mathematical logic, North-Holland, 1977.

2. N. Brunner, 75 years of independence proofs by fraenkel-mostowski permutation models, 1996.

3. Anna Bucalo, Martin Hofmann, Furio Honsell, Marino Miculan, and Ivan Scagnetto, Consistency of the theory of contexts, (2001), Submitted.

4. Luís Caires and Luca Cardelli, A spatial logic for concurrency (part II), CONCUR’2002 Proceedings, Lecture Notes in Computer Science, no. 2421, 2002.

5.—, A spatial logic for concurrency (part II), Extended version, with proofs, 2003.

6. FreshML, FreshML homepage, , http://www.freshml.org.

7. Harvey Friedman, Equality between functionals, Logic Colloquium 1972-73 (Rohit Parikh, ed.), Lecture Notes in Mathematics, vol. 453, Springer Verlag, 1975, pp. 22–37.

8. Murdoch. J. Gabbay, The π-calculus in FM, Thirty-five years of Automath (Fairouz Kamareddine, ed.), Kluwer, 2003.

9. Murdoch J. Gabbay, A theory of inductive definitions with alpha-equivalence, Ph.D. thesis, Cambridge, UK, 2000.

10.—, Automating fraenkel-mostowski syntax, TPHOLs, 15th International Conference on Theorem Proving in Higher Order Logics, August 2002.

11. Murdoch J. Gabbay and A. M. Pitts, A new approach to abstract syntax involving binders, 14th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, Washington, 1999, pp. 214–224.

12. Murdoch J. Gabbay and A. M. Pitts, A new approach to abstract syntax with variable binding, Formal Aspects of Computing 13 (2001), 341–363.

13. Furio Honsell, Marino Miculan, and Ivan Scagnetto, An axiomatic approach to metareasoning on systems in HOAS, Proceedings of ICALP’O1, vol. 2076, LNCS, 2001, pp. 963–978.

14.—, Theory of contexts for first-order and higher-order abstract syntax, ENTCS, vol. 62, Elsevier/Forum, 2001.

15. B. Huppert, Endliche gruppen i, Grundlehren der mathematischen Wissenschaften 134 (1967), 363–397.

16. J. L. Krivine, Lambda-calculus, types and models, Ellis Horwood, 1993.

17. Daniel Leivant, Higher order logic, Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 2, 1994, pp. 229–322.

18. Matias Menni, About И-quantifiers, Applied categorical structures (2003), Submitted.

19. Marino Miculan and Ivan Scagnetto, A framework for typed HOAS and semantics, Proceedings of PPDP 2003, ACM, 2003, Uppsala.

20. Dale Miller and Alwen Tiu, A proof theory for generic judgments: An extended abstract, Accepted for LICS03. To appear, July 2003.

21. John C. Mitchell, Foundations of Programming Languages, MIT Press, 1996.

22. John C. Mitchell and Eugenio Moggi, Kripke-style models for typed lambda calculus, Proceedings, Symposium on Logic in Computer Science, The Computer Society of the IEEE, 1996, pp. 303–314.

23. Lawrence C. Paulson, The foundation of a generic theorem prover, Journal of Automated Reasoning 5 (1989), no. 3, 363–397.

24. Frank Pfenning and Conal Elliot, Higher-order abstract syntax, SIGPLAN Conference on Programming Language Design and Implementation, 1988, pp. 199–208.

25. A. M. Pitts, Nominal logic: A first order theory of names and binding, Theoretical Aspects of Computer Software, 4th International Symposium, TACS 2001, Sendai, Japan, October 29-31, 2001, Proceedings (N. Kobayashi and B. C. Pierce, eds.), Lecture Notes in Computer Science, vol. 2215, Springer-Verlag, Berlin, 2001, pp. 219–242.

26.—, Nominal logic, a first order theory of names and binding, Information and Computation 186 (2003), 165–193.

27. R. Statman, Equality between functionals, revisited, Harvey Friedman’s Research on the Foundations of Mathematics (Harrington, Morley, Scedrov, and Simpson, eds.), Lecture Notes in Mathematics, North-Holland, 1985, pp. 331– 338.

28. C. Urban, A. M. Pitts, and Murdoch J. Gabbay, Nominal unification, Computer Science Logic and 8th Kurt Gödel Colloquium (CSL’03 & KGC), Vienna, Austria. Proccedings (M. Baaz, ed.), Lecture Notes in Computer Science, vol. 2803, 2003, pp. 513–527.

29. Dirk van Dalen, Intuitionistic Logic. In Vol. III, Handbook of philosophical logic, Dov Gabbay and Franz Günthner eds., Synthese Library, no. 166, D.Reidel Publishing company, 1986.

Appendix A. Formal Inductive Definitions

FV(P) and FV(t) are the variables occurring (free) in P and t respectively:

(38)FV (c(ts)) =FV (ts) FV (π · x) ={x}FV (p(ts)) =FV (ts) FV (P ∧P ′) =FV (P) ∪FV (P ′). . . FV (∀x. P) =FV (P) \ {x}FV (Иa. P) =FV (P).

Here ts is a list of terms (t1, . . . , tk). FV(ts) is the set union ⋃i FV(ti). We shall use this kind of shorthand a lot.

A(P), A(t), and A(π) are the atoms occurring (free) in P, t, and π respectively:

A((a b) ◦π) ={a, b} ∪A(π) A(Id) =∅A(c(ts)) =A(ts) A(π · x) =A(π)(39)A(p(ts)) =A(ts) A(P ∧P ′) =A(P) ∪A(P ′). . . A(∀x. P) =A(P)A(Иa. P) =A(P) \ {a}.

Term-for-variable substitution t{x↦→s}, where s must have the sort of x:

(40)a{x↦→s} = a (π · x){y↦→s} = π · x x ≢y(π · x){x↦→s} = π ·s s c(ts){x↦→s} = c(ts{a↦→s}),

Here π ·s s is defined in (42) below. Term-for-variable substitution on predicates:

p(ts){x↦→t} = p(ts{x↦→t}) (P ∧Q){x↦→t} = P{x↦→t} ∧Q{x↦→t}(41). . . (∀x′. P){x↦→t} = ∀x′. (P{x↦→t})(∃x′. P){x↦→t} = ∃x′. (P{x↦→t}) (Иn. P){x↦→t} =Иn. (P{x↦→t}).

In the clauses for ∀ and ∃ we assume x′ ∉FV(t). In the clause for И we assume n ∉ A(t).

The action of permutations π on terms t is given by:

(42)π ·s a = π(a) π ·s (κ · x) = π ◦κ · xπ ·s c(ts) = c(π ·s ts).

Here π ·s ts is the element-wise application to the list of terms ts. (42) reflects the semantic assumption made in §4.1 that [[ c ]] be equivariant.

The action of permutations π on predicates is given by:

π·s p(ts) = p(π·s ts) π·s (P ∧Q) = π·s P ∧π·s Q(43). . . π·s ∀x. P = ∀x. [[ π·s P{x↦→π-1·x} ]] xπ·s ∃x. P = ∃x. [[ π·s P{x↦→π-1·x} ]] xπ·sИn. P =Иn. π·s P.

In this last clause we take n fresh, so n ∉ A(π). The (rather ad-hoc) notation [[ · ]]x denotes the following operation: for every moderation π ◦κ ◦π-1 · x on x we replace it by κπ · x, where κπ denotes the permutation obtained by applying π as a permutation to the elements of κ (conjugating κ as syntax with π as semantics). Since ds(π ◦κ ◦π-1, κπ) = ∅ and in view of (πdiff), this is reasonable. It is needed in §8.4.

Appendix B. Judgements (sequent style)

. . . are presented in Figure 6, Figure 7, and Figure 8.

M.J.Gabbay, jamie@dcs.kcl.ac.uk, Department of Computer Science, King’s College, London

Γ, P ⊢P(Axiom)Γ ⊢P Γ ⊢Q Γ ⊢P ∧Q(∧RI)Γ, P, Q ⊢C Γ, P ∧Q ⊢C(∧LI)Γ ⊢P Γ ⊢P ∨Q(∨RI1)Γ ⊢Q Γ ⊢P ∨Q(∨RI2)Γ, P ⊢C Γ, Q ⊢C Γ, P ∨Q ⊢C(∨LI)Γ, P ⊢Q Γ ⊢P ⇒Q(⇒RI)Γ ⊢P Γ, Q ⊢C Γ, P ⇒Q ⊢C(⇒LI)Γ ⊢P Γ, P ⊢Q Γ ⊢Q(Cut)Γ, ⊥⊢C(⊥LI)Γ ⊢⊤(⊤RI)Γ ⊢P Γ ⊢∀x. Px ∉FV (Γ)(∀RI)Γ, P{x↦→t} ⊢C Γ, ∀x. P ⊢Cx ∉FV (Γ, C)(∀LI)Γ ⊢P{x↦→t} Γ ⊢∃x. Px ∉FV (Γ)(∃RI)Γ, P ⊢C Γ, ∃x. P ⊢Cx ∉FV (Γ, C)(∃LI)Γ, P, P ⊢C Γ, P ⊢C(Contraction) Figure 6. Core (standard) sequent rules of Fresh Logic, sequent style
Γ ⊢P Γ ⊢π ·s P(πI)Γ ⊢P{x↦→π′ ·s t} Γ, ds(π, π′)#t ⊢P{x↦→π ·s t}x ∉FV (t)(πdiff)Γ ⊢P{n↦→a} Γ, a#ti ⊢Иn. PP/n = P ′ •yi (ti)k 1a ∉A(P ′)(ИRI)Γ, P{n↦→a} ⊢C Γ,Иn. P, a#ti ⊢CP/n = P ′ •yi (ti)k 1a ∉A(P ′)(ИLI)
Figure 7. π and И sequent rules of Fresh Logic
Γ ⊢t = t(EqRI)Γ{x↦→t′} ⊢P{x↦→t′} Γ{x↦→t}, t′ = t ⊢P{x↦→t}x ∉FV (t, t′)(EqLI1)Γ ⊢a#b(#RI)Γ, a#a ⊢C(#LI)Γ ⊢a#ts Γ ⊢a#c(ts)(#c)Γ, a#ts ⊢C Γ ⊢Ca ∉A(Γ, C)(NewA)⋀ n ∈S. Γ{x↦→n} ⊢P{x↦→n} Γ{x↦→t} ⊢P{x↦→t}A(Γ, P) ⊊S(ExhaustA)Figure 8. =, #, and A sequent rules of Fresh Logic

Notes

1. . . in the logic by rules involving substitution such as ∀-elimination rule, and in the model by the valuations. ↩

2Nobody said it had to be interesting. ↩

3— if we care; for many purposes a reasonable-looking sound semantics is quite good enough. ↩