Nominal semantics for predicate logic: algebras, substitution, quantifiers, and limits Gilles Dowek and Murdoch J. Gabbay Abstract. We define a model of predicate logic in which every term and predicate, open or closed, has an absolute denotation independently of a valuation of the variables. For each variable a, the domain of the model contains an element JaK which is the denotation of the term a (which is also a variable symbol). Similarly, the algebra interpreting predicates in the model directly interprets open predicates. Because of this models must also incorporate notions of substitution and quantification. These notions are axiomatic, and need not be applied only to sets of syntax. We prove soundness and show how every ‘ordinary’ model (i.e. model based on sets and valuations) can be translated to one of our nominal models, and thus also prove completeness. Keywords: Lattices and algebra; First-order logic; Nominal semantics 1 Introduction What is a notion of algebraic truth suitable for interpreting predicate logic? For propositional logic an answer is clear: Heyting algebra for the intuition- istic case, and Boolean algebra for the classical case.1 This is not sufficient for interpreting predicate logic because predicates can contain variable symbols. The standard method, due to Tarski [25], uses valuations. We assume a do- main D and a valuation ς mapping variables to D, and then terms and predicates are given denotation in the context of the valuation: JrKς and JφKς . Intuitively, valuations convert predicates to propositions, which reduces the problem of truth to the infinite propositional case. Thus with the usual notion of model, names denote semantic objects, but semantic objects have no inherent notion of names. We propose an alternative. Allow semantic objects to be aware of names. Then, we can map a variable a to a representation of itself in the denotation. Thus, open terms and open predicates map to open elements of a domain and algebra of truth-values, like so: JrK and JφK. Connectives, including quantifiers, just become operations on the domain. So, the denotation of a is JaK and the denotation of ∀ a.φ is some operation #a applied to JφK. V What it means for an element to be open is given for us by the recently- developed theory of nominal semantics, which was designed to provide seman- tics for variable symbols in inductive syntax-with-binding [20,12]. In this paper 1 Accessible references for Heyting and Boolean algebra are easily found online. For a modern and encyclopaedic treatment, see e.g. [28]. we apply nominal ideas to semantic objects which, unlike the syntax of terms and predicates, need not be inductively defined. We use nominal algebra to ax- iomatise substitution following [17,18] and a simple theory of A#fresh limits in partial orders, which is introduced in this paper. Using A#fresh limits we show how >, ∧, and the quantifier #a are all just greatest A#lower fresh bounds for V suitable finite sets. Specifically: – > is the greatest lower bound for the empty set ∅. V – x ∧ y is the greatest lower bound for the set {x, y}, i.e. {x, V y}. x is the greatest {a}#lower bound for the set {x}, i.e. #{a} {x}. V#a – We use this to construct a nominal algebraic semantics for first-order logic and prove it sound and complete. The completeness proof is a little unorthodox: instead of a direct proof (which is not hard) we give a more general lifting construction from Tarski-style valuation models, to our nominal models. This gives a direct translation of the familiar semantics into our new one and we obtain completeness as a corollary. Map of the paper Section 2 presents the technical background: nominal sets and first-order logic. Section 3 introduces nominal posets V and substitution alge- bras. This material is partly new (nominal posets and #A ) and partly a restate- ment of [17,18] (substitution algebras; though to be fair, the presentation here is significantly simplified and updated). Section 4 introduces nominal Boolean algebras, which is a mathematically precise answer to the question with which we opened this Introduction, and proves soundness. Finally, Section 5 presents the ‘lifting’ operation on models and proves completeness. 2 Technical background 2.1 Background on nominal sets Nominal sets were introduced in [20] (where they were called equivariant Fraenkel- Mostowski sets). The presentation below is quite self-contained; see [20] or [12] for more details. We want names to ‘exist’ in the denotation. We do this by endowing sets with a symmetry group action over name permutations (Definition 2.3). We extract from this the key idea of support (Definition 2.4), which captures the degree of asymmetry of an element under the group action. We use this to define a nominal set X (Definition 2.6) as a set with a group action all of whose elements x are at most finitely asymmetric (have finite support), where a#x and a 6∈ supp(x) mean the same thing: “x is symmetric over/does not depend on the name a”. We do not a priori assume e.g. a substitution action on names; in our framework this is algebraically definable just from the more primitive notion of permutable names and finite asymmetry (see e.g. Figure 2). Definition 2.1. Fix a countably infinite set of atoms A. We use a permuta- tive convention that a, b, c, . . . range over distinct atoms. Definition 2.2. A (finite) permutation π is a bijection on the set A such that nontriv (π) = {a | π(a) 6= a} is finite. Write id for the identity permutation such that id (a) = a for all a. Write π 0 ◦ π for composition, so that (π 0 ◦ π)(a) = π 0 (π(a)). Write π -1 for inverse, so that π -1 ◦ π = id = π ◦ π -1 . Write (a b) for the swapping (terminology from [20]) mapping a to b, b to a, and all other c to themselves, and take (a a) = id . Definition 2.3. 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 π·(π 0 ·x) = (π ◦ π 0 )·x for all x ∈ |X| and permutations π and π 0 . Definition 2.4. Say that A ⊆ A supports x ∈ |X| when for every π, if π(a) = a for every a ∈ A then π·x = x. If some finite A supporting x exists, then call x finitely-supported. Then define the support of x by \ supp(x) = {A | A finite, A supports x}. Write a#x as shorthand for a 6∈ supp(x) and read this as a is fresh for x. Theorem 2.5. Suppose X is a set with a permutation action and x ∈ |X|. Then if x has finite support then supp(x) supports x and is the unique least finite supporting set of x. Proof. See [12, Theorem 2.21]. A different but equivalent formulation of the result is in [20]. Definition 2.6. Suppose X is a set with a permutation action. Call a set with a permutation action X a nominal set when every x ∈ |X| has finite support. X, Y, Z will range over nominal sets. Example 2.7. – A is a nominal set where π·a = π(a). It is easy to check that supp(a) = {a}. – The sets of terms and predicates from Definition 2.12 below, are nominal sets if we let permutation act in the natural way on the atoms (considered as variable symbols) inside them. It is easy to check that supp(r) or supp(φ) is equal to the atoms occurring in r or φ if we do not take terms up to α-equivalence, and supp(r) or supp(φ) is equal to the atoms occurring free in r or φ if we do take r or φ up to α-equivalence. A detailed study of this is in [12, Section 5]; see also [4]. Later on in this paper we shall see more examples. Notably, the sets X • from Definition 5.9 are nominal sets, and the set of valuations from Definition 5.3 is a set with a permutation action but not a nominal set (see Remark 5.8 and associated footnote). For more examples see [12]. Definition 2.8. Call a function f ∈ |X| → |Y| equivariant when π·f (x) = f (π·x) for all permutations π and x ∈ |X|. In this case write f : X → Y. Proposition 2.9. supp(π·x) = {π(a) | a ∈ supp(x)}. Proof. It is not hard to check that A supports x if and only if {π(a) | a ∈ A} supports π·x. We use Theorem 2.5. Corollary 2.10. 1. If π(a) = a for all a ∈ supp(x) then π·x = x. 2. If π(a) = π 0 (a) for every a ∈ supp(x) then π·x = π 0 ·x. 3. a#x if and only if ∃b.b#x ∧ (b a)·x = x. Proof. Parts 1 and 2 follow from the fact that supp(x) supports x (Theorem 2.5). Part 3 follows using Proposition 2.9. 2.2 First-order logic First-order logic is of course standard. The reader can find any number of pre- sentations in the literature, for instance [27]. Definition 2.11. Here and for the rest of this paper fix a signature Σ = (TermFormers, PredicateFormers, arity) of term-formers and predicate-formers and an arity function arity map- ping TermFormers ∪ PredicateFormers to N = {0, 1, 2, . . . }. We let f range over distinct term-formers and P range over distinct predicate-formers. Definition 2.12. Define terms r and predicates φ inductively by: r ::= a | f (r1 , . . . , rarity(ff ) ) ∧φ | ¬ φ | ∀ a.φ φ ::= ⊥ | P(r1 , . . . , rarity(PP) ) | φ∧ Define free atoms inductively by: S fa(a) = {a} fa(ff (r1 , . . . , rn )) = Si fa(ri ) ⊥) = ∅ fa(⊥ fa(PP(r1 , . . . , rn )) = i fa(ri ) ¬φ) = fa(φ) fa(¬ ∀a.φ) = fa(φ)\{a} fa(φ1∧ φ2 ) = fa(φ1 ) ∪ fa(φ2 ) fa(∀ Definition 2.13. We take predicates φ up to α-equivalence as usual (so for instance ∀ a.P P(a) = ∀ b.P P(b) where arity(P P) = 1). We write r[a:=s] and φ[a:=s] for the usual capture-avoiding substitution ∀b.P on terms and predicates. For instance, f (a)[a:=b] = f (b) and (∀ P(a))[a:=b] = ∀ b0 .P P(b). Definition 2.14. Let Φ and Ψ range over finite sets of predicates. A sequent is a pair Φ ` Ψ . We define the derivable sequents as usual for classical first-order logic by the rules in Figure 1. 3 Partial orders and substitution We obtain our nominal semantics for first-order logic by combining two things: a partial order, and a substitution action. We need the partial order to interpret entailment. We need the substitution action to interpret variables and substitu- tions. These are Subsections 3.1 and 3.2. Of course, these V two things interact via quantifiers. Thus we introduce the novel notion of #A X, an A#greatest lower bound for a set X (Notation 3.3). It turns out that this generalises ⊥, ∧, and #a into a single definition. V φ1 , φ 2 , Φ ` Ψ Φ ` ψ1 , Ψ Φ ` ψ2 , Ψ ⊥L) (⊥ ∧L) (∧ ∧R) (∧ Φ, ⊥ ` Ψ φ1 ∧ φ2 , Φ ` Ψ Φ ` ψ1 ∧ ψ2 , Ψ Φ ` φ, Ψ Φ, φ ` Ψ ¬L) (¬ ¬R) (¬ Φ, ¬ φ ` Ψ Φ ` ¬ φ, Ψ Φ, φ[a:=s] ` Ψ Φ ` ψ, Ψ (a 6∈ fa(Φ, Ψ )) ∀L) (∀ ∀R) (∀ Φ, ∀ a.φ ` Ψ Φ ` ∀ a.ψ, Ψ Fig. 1: Derivability in first-order classical logic 3.1 Nominal posets (nominal partially ordered set) We can now begin to ask what happens if we combine the notion of partially ordered set with the notion of nominal set. In particular, we can think about greatest lower and leastVupper bounds W in the presence of nominal freshness. This leads us to the idea of #A X and #A X; greatest lower and least upper bounds amongst elements that do not include A in their support. Definition 3.1. A nominal poset is a tuple L = (|L|, ·, ≤) such that (|L|, ·) is a nominal set and ≤⊆ |L| × |L| is an equivariant partial order.2 Call L finitely fresh-complete when for every finite subset X ⊆ |L| and every finite set of atoms A ⊆ A the set of A-fresh lower bounds {x0 ∈ |L| | A ∩ supp(x0 ) = ∅ ∧ ∀x∈X.x0 ≤x} has a ≤-greatest element #A X. V Similarly call L finitely fresh-cocomplete when for every finite X and A as above the set of A-fresh upper bounds {x0 ∈ |L| | A ∩ supp(x0 ) = ∅ ∧ W#A ∀x∈X.x≤x0 } has a ≤-least element X. V#A W#A Lemma 3.2. X and X are unique if they exist. Proof. From the fact that for a partial order, x ≤ y and y ≤ x imply x = y. Notation 3.3. Suppose L = (|L|, ·, ≤) is a finitely fresh-complete and -cocomplete nominal poset. Suppose X ⊆ |L| and A ⊆ A are finite. Then: – Call #A X an A#greatest lower bound (‘A-fresh greatest lower bound’ ) V of X. If A = ∅ then we may just call this a greatest lower bound. V#aIf A = {a} we may just call this an a#greatest lower bound and write it X. – Call #A X an A#least upper bound of X. If A = ∅ then we may just W W If A = {a} we may just call this an a#least call this a least upper bound. upper bound and write it #a X. Notation 3.4. Suppose L = (|L|, ·, ≤) is a nominal poset. – Write > for the greatest lower bound and ⊥ for the least upper bound of the empty set ∅, where these exist. 2 So x ≤ y if and only if π·x ≤ π·y. (Suba) a[a7→u] = u (Subid) x[a7→a] = x (Sub#) a#x ⇒ x[a7→u] = x (Subα) b#x ⇒ x[a7→u] = ((b a)·x)[b7→u] (Subσ) a#v ⇒ x[a7→u][b7→v] = x[b7→v][a7→u[b7→v]] Fig. 2: Nominal algebra axioms for substitution action – Write x ∧ y for the greatest lower bound and x ∨ y for the least upper bound of {x, y}, where these exist. – Write #a x for the a#greatest lower bound and #a x for the a#least upper V W bound of {x}, where these exist. Definition 3.5. Suppose L is a partial order (it does not matter whether it is nominal). Call x0 ∈ |L| a complement of x ∈ |L| when x ∧ x0 = ⊥ and x ∨ x0 = >. If every x ∈ |L| has a complement say that L has complements, and write the complement of x as ¬x. Lemma 3.6. Complements are unique if they exist. Corollary 3.7. Suppose L = (|L|, ·, ≤) is a nominal poset. V#A 1. Suppose X⊆|L| V#A is finite S and A⊆A, and X exists. Then supp( X)⊆ {supp(x) | x ∈ X}\A. 2. Suppose x∈|L|, and suppose ¬x exists. Then supp(¬x) = supp(x). Proof. We can use symmetry (equivariance) properties of atoms: X) ⊆ {supp(x) | x ∈ X} ∪ A.3 V#A S 1. Using [12, Theorems 2.29 and 4.7] V#Asupp( Since by assumption A ∩ supp( X) = ∅, the result follows. 2. By [12, Theorem 4.7] and since the map x 7→ ¬x is injective. 3.2 Substitution algebra The reader may be used to seeing substitution as a concrete operation on sets. However, using nominal sets we can powerfully (and axiomatically) generalise substitution to be an abstract (nominal) algebraic structure. Definition 3.8. A termlike substitution algebra over Σ is a tuple U = (|U|, ·, atm, sub) where: – (|U|, ·) is a nominal set. – atm : A → |U| is an equivariant injection, usually written invisibly (so we write atm(a) just as a). – sub : |U| × A × |U| → |U| is an equivariant substitution action, written infix v[a7→u]. such that the equalities (Suba) to (Subσ) of Figure 2 hold, where x, u, and v range over elements of |U|. 3 V This is just a fancy way of observing that since the definition of is symmetric in atoms, the the result must be at least as symmetric as the inputs. Definition 3.9. Suppose U = (|U|, ·, sub, atm) is a termlike substitution al- gebra. A substitution algebra over U is a tuple B = (|B|, ·, sub) where: – (|B|, ·) is a nonempty nominal set. – sub : |B| × A × |U| → B is an equivariant substitution function satisfying the axioms (Subid) to (Subσ) of Figure 2, where x ranges over elements of |B| and u and v range over elements of |U|. Example 3.10. 1. The set of atoms A is a termlike substitution algebra where atm(a) = a and a[a7→x] = x and b[a7→x] = b. 2. Terms from Definition 2.12 are a termlike substitution algebra with atm(a) = a and r[a7→s] equal to r[a:=s]. 3. Predicates from Definition 2.12 are not a termlike substitution algebra, be- cause there are no predicate variables or substitution for predicates. Predi- cates are however a substitution algebra over terms. In Corollary 5.13 we will prove that |N |• from Definition 5.11 is a termlike substitution algebra, and X • from Definition 5.11 is a substitution algebra. For different and non-trivial classes of substitution algebras see [11,13]. 4 The model 4.1 Nominal Boolean algebra Definition 4.1 is the culminating definition of this paper; we define a notion of Boolean algebraic structure suitable for giving an ‘absolute’ interpretation of first-order logic. This means that variables, substitution, and quantification must be part of the model just as much as conjunction and negation are part of ordinary Boolean algebras. With our definitions so far, this is now not difficult. Definition 4.1 is not quite enough to interpret first-order logic on its own. For that, we need the notion of model which we develop next in Subsection 4.2. Definition 4.1. Suppose U is a termlike substitution algebra. A nominal Boolean algebra over U is a tuple B = (|B|, ·, ≤, sub) such that: – (|B|, ·, ≤) is a finitely fresh-complete nominal poset with complements. – (|B|, ·, sub) is a substitution algebra over U. – The partial order is compatible with the substitution action: (Compat ) ( #A X)[a7→u] = #A {x[a7→u] | x∈X} if A∩supp(u)=∅, a6∈A V V V (Compat¬) (¬x)[a7→u] = ¬(x[a7→u]). A more accurate name for ‘nominal Boolean algebra’ might be ‘nominal σ #A ¬ V partial order’. But that is a bit of a mouthful.4 It is quite easy to derive some basic properties of nominal Boolean algebras, which are useful for Theorem 4.13. 4 A possibly nice classification is to define a notion of bounded nominal lattice which is equipped with ∧, ∨, ⊥, >—and also with #a x. Then our nominal Boolean algebra V is just a nominal lattice with complements and a compatible substitution action. Lemma 4.2. If b#u then ( #b x)[a7→u] = #b (x[a7→u]). V V V Proof. This is just (Compat ) where A = {b}. Recall that by our permutative convention a 6∈ {b}. Lemma 4.3. x ≤ y if and only if x ∧ y = x. Proof. Both hold if and only if x is a greatest lower bound for {x, y}. Lemma 4.4. 1. (x ∧ y)[a7→u] = x[a7→u] ∧ (y[a7→u]). 2. ⊥[a7→u] = ⊥. V Proof. From (Compat ) and (Compat¬) respectively. Corollary 4.5. If x ≤ y then x[a7→u] ≤ y[a7→u]. As a further corollary, if x ≤ y and a#x then x ≤ y[a7→u] for every u ∈ |U|. Proof. This follows from Lemma 4.3 and part 1 of Lemma 4.4. The further corollary follows using (Sub#) from Figure 2. Lemma 4.6. Suppose x ∈ |B| and u ∈ |U| and a ∈ A. Then x ≤ x[a7→u]. V#a Proof. By Notation 3.4 #a x is the a#greatest lower bound for {x}. This means V that #a x ≤ x and a# #a x. We use Corollary 4.5. V V Lemma 4.7. Suppose x, y∈|B| and a∈A. Then x ≤ y and a#x imply x ≤ V#a y. y with respect to {y}. V#a Proof. This is the a#greatest lower bound property of x is the greatest lower bound of {x[a7→u] | u ∈ |U|} in B. V#a Corollary 4.8. x is a lower bound. Now suppose z ≤ x[a7→u] for every V#a Proof. By Lemma 4.6 (Subid) u ∈ |U|. In particular then, z ≤ x[a7→a] x. By Lemma 4.7 z ≤ V#a = x. 4.2 Soundness Definition 4.9. A model M = (U, B, -M ) consists of: – A termlike substitution algebra U (Definition 3.8). – A nominal Boolean algebra B over U (Definition 4.1). – An assignment -M to each term-former f of an equivariant function f M : |U|arity(ff ) → |U| and to each predicate-former P of an equivariant function PM : |U|arity(PP) → |B| such that (Commff ) f M (u1 , . . . , uarity(ff ) )[a7→u] = f M (u1 [a7→u], . . . , uarity(ff ) [a7→u]) (CommP P) PM (u1 , . . . , uarity(ff ) )[a7→u] = PM (u1 [a7→u], . . . , uarity(ff ) [a7→u]). For the rest of this section fix a model M = (U, B, -M ). Definition 4.10. Define an interpretation function J-KM mapping terms and predicates (Definition 2.12) to elements of |U| and |B| respectively, as follows: JaKM = atm(a) Jff (r1 , . . . , rn )KM = f M (Jr1 KM , . . . , Jrn KM ) ⊥K = ⊥ J⊥ M P(r1 , . . . , rn )KM = PM (Jr1 KM , . . . , Jrn KM ) JP 0 0 M ∀a.φKM = #a JφKM Jφ ∧ φK = Jφ K ∧ JφK M M V J∀ J¬ ¬φK = ¬JφK M M Definition 4.11. Write M  φ when JφKM = > and call φ valid in M. Proposition 4.12. Jr[a:=s]KM = JrKM [a7→JsKM ] and Jφ[a:=s]KM = JφKM [a7→JsKM ]. Proof. By routine inductions on r and φ: – The case of a. Ja[a:=s]KM = JsKM and by (Subid) JaKM [a7→JsKM ] = JsKM . – The case of f (r1 , . . . , rn ). Using (Commff ). – The case of φ0∧ φ. Using part 1 of Lemma 4.4. – The case of ∀ a.φ. Using Lemma 4.2. V W Theorem 4.13. If Φ ` Ψ then φ∈Φ JφKM ≤ ψ∈Ψ JψKM . Proof. – Soundness of (∧ ∧L) and (∧ ∧R) follows from Jφ1 KM ∧ Jφ2 KM being a great- est ≤-lower bound of Jφ1 K and Jφ2 KM . M – Soundness of (¬¬L) and (¬ ¬R) follows from the fact of complements that ¬x ≤ y if and only if ¬y ≤ x. – Soundness of (⊥⊥L) follows from ⊥ being the complement of the greatest lower bound of ∅. ∀L) follows using Lemma 4.6 and Proposition 4.12, and sound- – Soundness of (∀ ∀R) follows from Lemma 4.7. ness of (∀ 5 Lifting ordinary models to nominal models We have to recall the (standard) definition of model for first-oder logic. This is Subsection 5.1. Then in Subsection 5.2 we show how to lift this to a nominal model and obtain completeness as an immediate corollary (Theorem 5.18 and Corollary 5.19). 5.1 Ordinary model of first-order logic We briefly sketch the ordinary model of first-order classical logic, with valuations and without atoms. This model is not intended to be sophisticated; we will just need that one exists. Notation 5.1. To avoid the confusion between sets and nominal sets, we may write ordinary set for the former. Definition 5.2. An ordinary model N = (|N |, -N ) is a tuple such that: – |N | is some non-empty (ordinary) underlying set. – -N assigns to each term-former f a function f N : |N |arity(ff ) → |N | and to each predicate-former P a function PN : |N |arity(PP) → {⊥, >}. Definition 5.3. Write A⇒|N | for the set of functions from atoms to |N |. Let ς range over elements of A⇒|N | and call these valuations (to N ). Also if x ∈ |N | then write ς[a:=x] for the function such that (ς[a:=x])(a) = x and (ς[a:=x])(b) = ς(b). Definition 5.4. {⊥,V>} is aWcomplete Boolean algebra. We use standard defini- tions, such as ∧, ¬, , and without further comment Definition 5.5. Define an interpretation function J-KNς mapping terms and predicates (Definition 2.12) to elements of |N | and {⊥, >} (considered as a Boolean algebra) respectively, as follows: JaKNς = ς(a) Jff (r1 , . . . , rn )KNς = f N (Jr1 KNς , . . . , Jrn KNς ) N ⊥ Kς = ⊥ J⊥ N P(r1 , . . . , rn )KNς = P JP V (Jr1 Kς , . N. . , Jrn Kς ) N N 0 0 N ∀a.φKς = x∈|N | JφKς[a:=x] Jφ ∧ φKς = Jφ Kς ∧ JφKς N N J∀ N J¬ ¬φKNς = ¬JφKNς Theorem 5.6 expresses the usual soundness and completeness result for first- order logic; for details and proofs see e.g. [27, Subsection 1.5]: Theorem 5.6. Φ ` Ψ is derivable if and only W model N and V if for every ordinary every valuation ς to N it is the case that φ∈Φ JφKNς = > implies ψ∈Ψ JψKNς = >. 5.2 Constructing a nominal model from an ordinary model We now show how to ‘lift’ a model over ordinary sets to a nominal model (Propo- sition 5.16). We then deduce completeness for nominal Boolean algebras (Corol- lary 5.19). Definition 5.7. Give valuations ς ∈ A⇒|N | a permutation action by (π·ς)(a) = ς(π -1 (a)). Remark 5.8. A⇒|N | forms a set with a permutation action (Definition 2.3). This is not in general a nominal set because it has elements without finite sup- port5 for our purposes that will not be a problem. In fact, the action from Definition 5.7 is a special case of the standard conju- gation action (π·ς)(a) = π·ς(π -1 (a)) where we use the trivial action π·x = x for every x ∈ |N |. This is standard; for a specifically ‘nominal’ discussion see [14, Definition 2.4.2]. Definition 5.9. Given an ordinary set X write X • = (|X • |, ·) for 5 The finitely-supported ς are such that there exists a finite A ⊆ A such that for all a, b 6∈ A, ς(a) = ς(b); it is not worth our while to impose this restriction, though it would do no harm to do so. – |X • | is the set of functions f from A⇒|N | to X such that there exists a finite set A such that if ς(a) = ς 0 (a) for every a ∈ A then f (ς) = f (ς 0 ), and – the permutation action · is defined by (π·f )(ς) = f (π -1 ·ς). We will be most interested in |N |• and {⊥, >}• . Lemma 5.10. For any ordinary set X, X • from Definition 5.9 determines a nominal set (Definition 2.6). Proof. It is routine to verify that the permutation action is indeed a group action. It remains to check finite support. Suppose π(a) = a for every a ∈ A (notation from Definition 5.9). By Def- inition 5.9 (π·f )(ς) = f (π -1 ·ς). By Definition 5.7 (π -1 ·ς)(a) = ς(π(a)). Now by assumption ς(a) = ς(π(a)) for every a ∈ A. Therefore, (π -1 ·ς)(a) = ς(a) for every a ∈ A, and so f (ς) = f (π -1 ·ς), and so (π·f )(ς) = f (ς). Thus, f has finite support (and is supported by A). Definition 5.11. Suppose N is an ordinary model (Definition 5.2). Specify a tuple (||N |• |, ·, atm, sub) by: – atm is defined by atm(a)(ς) = ς(a). – sub is defined by f [a7→g](ς) = f (ς[a:=g(ς)]). We may write |N |• for (||N |• |, ·, atm, sub).6 Furthermore if X is any ordinary set then (abuse notation again and) write X • = (|X • |, ·, sub) where f [a7→g](ς) = f (ς[a:=g(ς)]) for f ∈ |X • | and g ∈ ||N |• |. Lemma 5.12. Suppose X is an ordinary set and f ∈ |X • |. Then if ς(a) = ς 0 (a) for every a ∈ supp(f ) then f (ς) = f (ς 0 ). Proof. Suppose ς(a) = ς 0 (a) for every a ∈ supp(f ). It suffices to show that if a ∈ A \ supp(f ) and x ∈ |N | then f (ς[a:=x]) = f (ς). Choose fresh b : α (so b 6∈ A). By part 1 of Corollary 2.10 (b a)·f = f , since a, b 6∈ supp(f ). We reason as follows: b6∈A (b a)·f =f b6∈A f (ς[a:=x]) = f (ς[a:=x][b:=ς(a)]) = f (ς[b:=x]) = f (ς) Corollary 5.13. N • from Definition 5.11 is indeed a termlike substitution al- gebra, and X • is indeed a substitution algebra over N • . Proof. We examine Definitions 3.8 and 3.9 and see that we need to check equiv- ariance and the axioms (Suba) (for the termlike case) and (Subid) to (Subσ) from Figure 2. This is routine; we use Lemma 5.12. Definition 5.14. Suppose g 0 , g ∈ |{⊥, >}• |. Write g 0 ≤ g when ∀ς.g 0 (ς) ≤ g(ς). 6 So we abuse notation by overloading with the nominal set, and ||N |• | is: the under- lying set of the substitution algebra obtained from the underlying set of the ordinary model N . What could be simpler? Lemma 5.15. (|{⊥, >}• |, ·, ≤) is a finitely fresh-complete lattice with comple- ments. Proof. It is easy to check that ¬g defined by (¬g)(ς) = ¬(g(ς)) is a complement to g. Now suppose X ⊆ |{⊥, >}• | and A ⊆ A are finite, and suppose A∩supp(u) = ∅ and a ∈ A\A. Define ^ ( #A X)(ς) = {g(ς[a:=xa ]a∈A ) | g ∈ X, ∀a∈A.xa ∈ |N |}. V It is routine to verify that this is an A#greatest lower bound for X. Proposition 5.16. (|{⊥, >}• |, ·, ≤, sub) is a nominal Boolean algebra over |N |• . Proof. We unpack Definition 4.1. – (|{⊥, >}• |, ·) is a nominal set by Lemma 5.10. – (|{⊥, >}• |, ·, ≤) is by Lemma 5.15 a finitely fresh-complete lattice with com- plements. V – (Compat ) and (Compat¬) follow by easy calculations, since Defini- tion 5.14 is pointwise on valuations. Definition 5.17. The interpretation of term-formers and predicate-formers is simple: f I (f1 , . . . , farity(ff ) )(ς) = f N (f1 (ς), . . . , farity(ff ) (ς)) PI (f1 , . . . , farity(ff ) )(ς) = PN (f1 (ς), . . . , farity(ff ) (ς)) Theorem 5.18. (|N |• , {⊥, >}• , -I ) determines a model in the sense of Def. 4.9. Proof. |N |• is a termlike substitution algebra by Corollary 5.13. {⊥, >}• is a nominal Boolean algebra over |N |• by Proposition 5.16. The commutation con- ditions (Commff ) and (CommP P) are by easy calculations. Corollary 5.19. If Φ 6` Ψ , then there exists a termlike V substitution W algebra U and a nominal Boolean algebra M over U such that φ∈Φ JφKM 6≤ ψ∈Ψ JψKM . As a corollary, if Φ is inconsistent (that is, if Φ ` ⊥) then Φ has a model. W modelN N Proof. By completeness of first-order logic thereVexists some ordinary (Definition 5.2) and valuation ς to N such V that φ∈Φ W JφKN ς = > and ψ∈Ψ JψKς = ⊥. It follows from Definition 5.14 that φ∈Φ JφKM 6≤ ψ∈Ψ JψKM . It is also possible give a direct proof of completeness of first-order logic with respect to the models of Definition 4.9, using a model based on syntax quotiented by derivable equality. The advantage of the proof of completeness used here is that it also shows that completeness does not hold just because the only models available are syntax-based. Topological models [13] and set-theoretic models [11] also exist (those papers predate the consideration of lattices and A#fresh limits of this paper). 6 Conclusions The usual Tarski semantics, based on valuations, has names in the syntax but not in the semantics. Names can be used to name semantic objects but these objects do not themselves contain names. We have challenged the prejudice that only syntax contains names, and proposed a framework where names are (also) in denotation. This is related to a broad debate in philosophy about to what extent names are real. One investigation in that literature deserves special mention: Kit Fine’s notion of arbitrary object [8], which corresponds to our notion of ‘names in denotation’ and in particular to our notion of nominal substitution set, though the technical details of Fine’s constructions are quite different from ours.7 This paper is part of a broader research context. For instance in [13] we built a representation theorem for first-order logic (in retrospect this also provides a class of ‘topological’ models for the axioms in this paper, distinct from the ‘lifted’ models of Section 5). In [11] we show that, remarkably, a large subclass of the cumulative hierarchy model of Fraenkel-Mostowski sets forms a substitution algebra. In this paper we apply the technology to the theory of lattices, in particular identifying A#fresh limits as the single unifying notion of greatest lower bound needed to model both conjunction and universal quantification. This is another step towards a ‘nominal’ view of logic and computation whereby names, and associated structures, are treated as integral to denotation. Related and future work A nominal style semantics related to the semantics of this paper has been given for the λ-calculus [19]. Nominal lattices have not been considered to date. The author and collaborators considered a notion of Banona in [16] (Boolean algebra with N) which is tangentially related to this paper. Domain theory in nominal sets is considered in [26] and a notion of FM category is considered in [3,2]. The notion of A#fresh limit seems to be new though, as is the specifically lattice-theoretic treatment. A relative of nominal lattices is cylindric set algebras [22,21], a semantics expressed in terms of relations between elements of the domain of the model, where quantification is interpreted using projection and cylindrification. Instead of designing semantics for first-order logic based on relations, projection, and cylindrification, we have taken the novel approach of giving a direct interpreta- tion to variables in the model. In fact, the ‘ordinary models’ we build in Sub- section 5.1 correspond to locally finite dimensional regular cylindric set algebras [22]. There is no non-nominal precedent to the nominal Boolean algebras from Definition 4.1. There are two natural avenues for future work: 7 Fine did not have permutations or finite support independently of and preceding the notion of substitution. Add binders to the term-language. Part of the challenge of this is to develop a suitable new syntax extending first-order logic with term-formers that can bind. Once we have this, it is easy to interpret binders, because our (nominal) denotation supports atoms-abstraction as primitive.8 In particular, we see this being applied computationally in formalising math- ematics, where binders are everywhere, as an improvement over first-order logic (where term-formers cannot bind) or higher-order logic (which may already be unnecessarily powerful). This would be related to the permissive-nominal logic of [5,6] except that here, we would want to take substitution as primitive. This is related to work by Fiore and his students [10,9] which tries to develop (purely in category the- ory) a unified account of names, binding, and substitution; a non-exhaustive but accessible introduction to these ideas is in [24]. Slightly further afield, Beeson’s lambda-logic [1] enriches first-order logic with a term-language that is specifi- cally the untyped λ-calculus; the denotational assumptions used are completely different, but the spirit of allowing binding term-formers in a first-order logic is similar. Of course this also goes back to the first author’s Binding Logic [7]. Generalise to categories. Another obvious next step is to generalise the con- structions in this paper from lattices to categories, and so obtain an enriched category theory. By this view, we note that lattices are just a special case of cat- egories, and our A#fresh limits are just limits in a subcategory of elements of the lattice for which A is fresh. Much can be done here. For instance, we can try to identify the correct common generalisation of this new view of quantifiers and the standard one based on left- and right-adjoints to projection [23, Section 5.5]. Slightly less ambitiously, we can simply consider a general notion of nominal lattice, which enriches ordinary lattices with #a x (a greatest a#lower bound for V x) but without necessarily assuming a substitution action.9 Clearly, there is a rich theory of nominal preorders which remains to be explored. References 1. Michael Beeson. Lambda logic. In Second International Joint Conference on Automated Reasoning (IJCAR 2004), volume 3097 of Lecture Notes in Computer Science, pages 460–474. Springer, 2004. 2. Ranald Clouston. Equational logic for names and binding. PhD thesis, University of Cambridge, UK, 2009. 3. Ranald Clouston. Nominal Lawvere theories. In Proceedings of the 18th International Workshop on Logic, Language, and Information (WoLLIC), volume 6642 of Lecture Notes in Computer Science. Springer, 2011. 4. Roy L. Crole. α-equivalence equalities. Theoretical Computer Science, 2012. In press. 5. 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. 8 Atoms-abstraction [a]x is the native (non-functional) notion of abstraction in nom- inal techniques. It was introduced in [20]. 9 The Na.x of [16] is not an instance of this because it commutes with negation, but the (dual of) νa.x from [15] is an instance of this. There are two distinct ‘restriction’ operations here. 6. Gilles Dowek and Murdoch J. Gabbay. Permissive Nominal Logic (journal version). Trans- actions on Computational Logic, 2012. In press. 7. Gilles Dowek, Thérèse Hardin, and Claude Kirchner. Binding logic: Proofs and models. In Proceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2002), pages 130–144. Springer, 2002. 8. Kit Fine. Reasoning with Arbitrary Objects. Blackwell, 1985. 9. Marcelo Fiore and Chung-Kil Hur. Term equational systems and logics. Electronic Notes in Theoretical Computer Science, 218:171–192, 2008. 10. Marcelo P. Fiore, Gordon D. Plotkin, and Daniele Turi. Abstract syntax and variable binding. In Proceedings of the 14th IEEE Symposium on Logic in Computer Science (LICS 1999), pages 193–202. IEEE Computer Society Press, 1999. 11. Murdoch J. Gabbay. A study of substitution, using nominal techniques and Fraenkel- Mostowski sets. Theoretical Computer Science, 410(12-13):1159–1189, March 2009. 12. Murdoch J. Gabbay. Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic, 17(2):161–229, 2011. 13. Murdoch J. Gabbay. Stone duality for First-Order Logic: a nominal approach. In Howard Barringer Festschrift. December 2011. 14. Murdoch J. Gabbay. Nominal terms and nominal logics: from foundations to meta- mathematics. In Handbook of Philosophical Logic, volume 17. Kluwer, 2012. 15. Murdoch J. Gabbay and Vincenzo Ciancia. Freshness and name-restriction in sets of traces with names. In Foundations of software science and computation structures, 14th International Conference (FOSSACS 2011), volume 6604 of Lecture Notes in Computer Science, pages 365–380. Springer, 2011. 16. Murdoch J. Gabbay, Tadeusz Litak, and Daniela Petrişan. Stone duality for nominal Boolean algebras with NEW. In Proceedings of the 4th international conference on algebra and coalgebra in computer science (CALCO 2011), volume 6859 of Lecture Notes in Computer Science, pages 192–207. Springer, 2011. 17. 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. 18. Murdoch J. Gabbay and Aad Mathijssen. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing, 20(4-5):451–479, June 2008. 19. Murdoch J. Gabbay and Dominic Mulligan. Nominal Henkin Semantics: simply-typed lambda-calculus models in nominal sets. In Proceedings of the 6th International Workshop on Logical Frameworks and Meta-Languages (LFMTP 2011), volume 71 of EPTCS, pages 58–75, September 2011. 20. 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. 21. Leon Henkin, J. Donald Monk, and Alfred Tarski. Cylindric Algebras. North Holland, 1971 and 1985. Parts I and II. 22. Donald Monk. An introduction to cylindric set algebras. Logic journal of the IGPL, 8(4):451–492, 2000. 23. Andrew M. Pitts. Categorical logic. In S. Abramsky, D. M. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, Volume 5. Algebraic and Logical Struc- tures, chapter 2. Oxford University Press, 2000. 24. John Power. Abstract syntax: Substitution and binders: Invited address. Electronic Notes in Theoretical Computer Science, 173:3–16, 2007. 25. Alfred Tarski. The semantic conception of truth and the foundations of semantics. Phi- losophy and Phenomenological Research, 4, 1944. 26. David C. Turner. Nominal Domain Theory for Concurrency. PhD thesis, University of Cambridge, 2009. 27. Dirk van Dalen. Logic and Structure. Universitext. Springer, 1994. Third, augmented edition. 28. Steve Vickers. Topology via Logic, volume 5 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1989. Acknowledgements. The second author acknowledges the support of the Leverhulme trust.