Nominal Henkin Semantics: simply-typed lambda-calculus models in nominal sets
H. Geuvers, G. Nadathur (Eds): LFMTP 2011
EPTCS 71, 2011, pp. 58–75, doi:10.4204/EPTCS.71.5
Gabbay & Mulligan
We investigate a class of nominal algebraic Henkin-style models for the simply typed λ-calculus in which variables map to names in the denotation and λ-abstraction maps to a (non-functional) name-abstraction operation. The resulting denotations are smaller and better-behaved, in ways we make precise, than functional valuation-based models.
Using these new models, we then develop a generalisation of λ-term syntax enriching them with existential meta-variables, thus yielding a theory of incomplete functions. This incompleteness is orthogonal to the usual notion of incompleteness given by function abstraction and application, and corresponds to holes and incomplete objects.
1 Introduction
In this paper we develop a Henkin-style semantics for the simply-typed λ-calculus in nominal sets. The simply-typed λ-calculus (STLC) has notions of typed variable, substitution, and function abstraction. Correspondingly, our models in nominal sets will enrich ‘ordinary’ sets with typed names, a substitution action, and name-abstraction. Thus, concepts that are normally characteristic of syntax—like variable, substitution, and variable-binding—are explicitly represented as nominal algebraic structure [22].
The resulting models have different properties from traditional valuation-style (‘closed’) semantics. Intuitively this is because leaving names in the denotation gives the models more structure—we have more information about ‘where an element came from’.
For instance, Proposition 3.6 (the rule) and Theorem 3.15 (well-pointedness) are properties that hold of the nominal models of this paper, and fail for ‘classical’ treatments (see Examples 3.7 and 3.16). This is because the direct inclusion of names into the denotation forces there to be ‘enough’ elements of the model, and naturality requirements of the models require these elements to be ‘sufficiently distinguishable’. These conditions cannot be expressed without names in the denotation.
Furthermore, we find that we can extend this to a syntax and semantics for existential variables. That is, we will extend STLC syntax with ‘holes’. The technique used is essentially the same as the nominal terms of [40] (a permissive variant thereof, following [6, 7]) but taking semantics in nominal models of STLC instead of in datatypes of abstract syntax with binding.
Because λ-abstraction maps to atoms-abstraction, the denotation of functions does not involve function spaces. Because variables map to themselves, valuations are not used either; their role is taken by the substitution for names. Thus we obtain a simple ‘first-order flavoured’ completeness proof (Theorem 3.11).
In summary, nominal Henkin models differ from ‘ordinary’ Henkin models by including variables and substitution in the underlying domain of the denotation as nominal algebraic structure. This yields a new class of models which seems to not display certain pathologies of the ‘ordinary’ models, and which can be leveraged to design novel calculi with applications e.g. to existential variables.
2 Background
Background on simply-typed λ-calculus
1. Fix a nonempty set of base types τ BaseTypes. Define (simple) types by φ :: τ φ φ. Let φ, ψ, χ range over types.
2. Fix a set of constants C Constants, to each of which is associated a type type Define terms by: r :: a C λa:φr rr. Let r, s, t range over terms. λa binds a in λa:φs and we take terms up to α-equivalence as usual.
Define free atoms fa by fa(a
Give terms a capture-avoiding substitution action r[:]n1 (side-conditions can be guaranteed by α-renaming):
Let be the least equivalence on terms (up to α-equivalence) such that:
A type environment Γ is a set of atomic typings a : φ which is functional in the sense that if a : φ and a : then φ .
Derivable typing judgements Γ r : φ are defined using the (standard) rules in Figure 1.
Define the domain of Γ by dom(Γa φ(a:φ Γ). Write Γa:φ for the type environment obtained by adding a:φ to Γ; if we write this, we impose a condition that a dom
A typing judgement is a tuple Γ r : φ. The derivable typing judgements are defined in Figure 1.
Background on nominal sets
The cumulative hierarchy of ZFA sets U is the least fixed point of U powerset. This can be constructed by starting from atoms and transfinitely adding all subsets (a construction going back to Von Neumann [32]).
Given ab write (a b) for the swapping bijection on atoms mapping a to b, b to a, and any other c ab to c.
If π is a bijection on atoms define nontriv(πa π(a) a.
Write for the group of bijections (finitely) generated by swappings, and call these bijections permutations.
Write π for the composition of π and (so (π )(a π((a))). Write id for the identity permutation (so id(a a always).
A bijection π on atoms is a permutation if and only if nontriv(πa π(a) a is finite.
Give U a permutation action πx inductively defined by πa π(a) for a , and πX πx x X for X U .
If A write fix(Aπ aAπ(a a.
Say that A supports x U when πfixπx x.
Call an element x U finitely-supported when it has a unique least finite supporting set supp. Write a#x for a supp and read this as ‘a is fresh for x’.
If x U has a finite supporting set A, then supp exists.
Our reasoning can be formalised in first-order logic, enriched with the axioms of Zermelo-Fraenkel set theory with atoms (ZFA). This is just a formal way of stating that we have assumed atoms and sets and we reason about them mathematically, but stating it in terms of formal logic lets us express an important observation, that our reasoning is symmetric under permutation:
We will appeal to equivariance repeatedly to quickly yet rigorously rename atoms, usually while retaining an inductive hypothesis. See for instance Lemma 3.5.2
Say that X U has the trivial action when supp(x for every x X (equivalently: when πx x for every x X and permutation π).
If XY U then a function(-set) from X to Y is a subset of X Y such that xXyY(xy) f and xy((xy) f (x) f )y . Write XY for the set of all functions from X to Y. Write XY for the set of all functions from X to Y with finite support.
The permutation action from Definition 2.10 gives f XY the conjugation permutation action specified by π( f (xπ f )(πx).
If X and Y in U have the trivial permutation action (Definition 2.14), then so does XY, and XY XY. (If underlying sets have empty support then so do functions between them.)
3 Nominal models for simple type theory
3.1 Nominal λ-model
Write πΓ :φ a:φ Γ.
A model consists of an assignment for each type environment Γ and type φ of a finitely-supported set together with the following data:
1. For every a:φ Γ an element a
2. For every constant C an element Ctype.
3. If x
4. For x φψ and y
5.
6. If x
must be equivariant in the sense that:
We write x[a y] as sugar for ([a:φ]x) y. In addition, must be a nominal algebra for substitution by satisfying rules (Suba), (Sub#), (SubApp), and (Subλ); we fill in types as appropriate (we discuss (SubId) below):
For the rest of this subsection fix a model .
Let us break down the design of Definition 3.2. Obviously names inhabit the denotation in a very direct and literal sense that a
But a also behaves like a variable: It can be renamed by πx, and bound by [a:φ]x, and it can also be substituted for. The rules (Suba) to (Subλ) do the job that valuations do in ‘normal’ models; they replace a name a by an(other) element of the model. The significant difference is that in standard models we pick a valuation and then form a denotation; in nominal models we form a denotation and then—if we wish—substitute for the free variables.
The axioms (Suba) to (SubId) can be made formal in nominal algebra [22]. These particular axioms are taken from [20].3 Instead of (Sub#) we could take a weaker axiom b[ax b. Conversely, we could safely add (SubId) and thus exclude certain arguably pathological models. The language of Definition 2.2 is not expressive enough to detect these choices, but the language of Definition 4.3 is (see Example 5.10).
Aside from the inclusion of names, our notion of model resembles Henkin models, which have an applicative structure in which abstractions have a well-defined interpretation [26].
Just as is the case for Henkin models, Definition 3.2 specifies what a model must look like but does not build one. We do build a concrete model out of syntax as part of the completeness proof in Subsection 3.3.
The equivariance conditions are standard for nominal techniques; our models must be symmetric up to permuting atoms.
Finally, conditions 1 to 6 specify the structure of a model that makes it into a model of the λ-calculus, by interpreting names (as themselves), constants, λ-abstraction (as a function of the name a and the element x)4 and a Henkin-models style application.
We now come to our first soundness theorem; if a term is typable then its denotation inhabits the denotation of its type:
If Γ r : φ then
As a corollary using condition 5 of Definition 3.2, if Γ r : φ then supp() fa
By a straightforward induction on the derivation of Γ r : φ:
By the definition of model (Definition 3.2), if a : φ Γ then a
Suppose Γa:φ r : ψ so that by Γ λa:φr : φψ and by inductive hypothesis . By assumpion λa:φrφψ.
If φψ and
3.2 Soundness for β-conversion
Suppose Γa:φ r : ψ and Γ s : φ, where a dom
Then r[a : s]
By a routine induction on the derivation of Γa:φ r : ψ:
The case of for a. By (Suba) a[a s
The case of for c:χ Γ. By (Sub#) c[a s c. Also c[a : s s.
The case of for λc:χr. By equivariance (Theorem 2.13) suppose c domsupp().5 The result follows using (Subλ).
The case of uses (SubApp).
Suppose Γa:φ r : ψ and Γa:φ s : ψ.
If
Immediate since by Definition 3.3 λa:φr a:φ], and similarly for s.
Proposition 3.6 does not hold in a valuation semantics of ‘ordinary’ models. For instance, consider a (valuation-based) semantics with one base type τ with denotation 01 (a two-element set). Consider x and y and a valuation ρ mapping x and y both to 0. Then 0
If r s (Defn. 2.4) and Γ r : φ then
3.3 Completeness
Write ;Γ rs when there exists φ (which is unique if it exists) such that Γ r:φ and Γ s:φ, and and
We need one technical fact about nominal sets, for Theorem 3.11:
Suppose Γ r : φ. If a supp(β) then there exists s such that T;Γ r s and a fa
Using [15, Lemma 7.6.2].
Γ r s implies r s.
We take as our model where
If a : φ Γ then we take a
If
Similarly, we take srs.
It is a fact that r and s imply λa:φr λa:φ and rs , and it follows that the definition above is well-defined.
We must also check validity of rules (Suba) to (Subλ). We consider two cases:
The case of (Suba). It is a fact that (λa:φa)s s.
The case of (Sub#). Suppose a#β. By Lemma 3.10 there exists t such that a fa(). So [a : r and thus T;Γ [a : r . It follows that t[a : r]
Furthermore, by construction if
The proof of Theorem 3.11 resembles the proof of completeness for Henkin models, with moderate changes to handle the ‘nominal’ models. Our models are not necessarily extensional (that is, we do not insist that r λa(ra) for a not free in r) whereas Henkin semantics usually are [26]; nevertheless it is reasonable to think of this as ‘Henkin semantics with names’. A survey of complete non-extensional semantics for STLC is in [2].
Theorem 3.11 is simpler than it could be; we could generalise it to completeness for arbitrary theories (i.e. we allow a set of equality axioms and prove completeness for the class of models that validate those axioms). We expect this generalisation to be an easy replay of the existing proof. We do not do this because the simpler case already illustrates the main points, and has useful features which we can now explore.
3.4 Well-pointedness
In Proposition 3.6 and Example 3.7 we saw that our nominal Henkin models have a desirable property that ‘ordinary’ models do not. We now come to another; to state it we need a definition:
A homomorphism F from to is a collection of functions FΓφ mapping to which are:
Equivariant in the sense that π(FΓφ (x Fπ(πx) (Notation 3.1).
Natural in the sense that F commutes with atoms, constants, abstraction, and . So for example, FΓ(a a and FΓ([a:ψ]xa:ψ]FΓ
The notion of validity from Definition 3.9 is local in that it checks validity at one model. There is also a global notion, which checks validity at the model and all ‘larger’ ones:
Suppose Γ r:φ and Γ s:φ. Say that ;Γ r s when ;Γ r s in the sense of Definition 3.9 for every such that there exists a homomorphism F : .
Suppose Γ r : φ and F : is a homomorphism. Then FΓφ (
By a routine induction on the derivation of Γ r : φ, using naturality.
Suppose Γ r : φ and Γ s : φ. Then ;Γ r s if and only if ;Γ r s.
By considering the identity homomorphism from to itself, mapping x
Conversely, suppose ;Γ r s and suppose F is a homomorphism from to . By assumption
Theorem 3.15 fails for traditional models. For instance, consider a functional model in which all terms are equal because every type has just one element. So Γ r s is locally true, but not globally true.
Nominal Henkin semantics exclude this, because they have elements to interpret variables. It is impossible to compress them all down to one element, as we did in the previous paragraph for ‘ordinary’ models.
4 Existential variables
Nominal terms introduced to nominal techniques the idea of two levels of variable; atoms (as above) and unknowns X, which are existential variables and in [40] were used in a unification algorithm. The first author proposed combining nominal unknowns with non-trivial logical theories, e.g. with first-order logic [19, 21]. Since in this paper we have a nominal semantics for the STLC, it is natural to extend Definition 2.2 with nominal unknowns and so to add existential variables.
The motivation for doing this is that STLC underlies many interesting logics and programming languages, so that our semantics and syntax with existential variables have potential— not exploited in this paper but motivating the constructions—to provide syntax and semantics for ‘incomplete terms’. In common with all other such treatments, a difficulty is the delicacy of maintaining well-typedness under instantiation (which for nominal terms may be capturing; see Remark 4.16). Our solution has elements of previous work, but it retains a distinct identity and remains typically ‘nominal’.
We will use permissive nominal terms [7], which improve on the theory of α-equivalence of nominal terms by allowing us to ‘just quotient’ syntax (nominal terms require a freshness context and freshness context update, which are harder to manage in the presence of non-trivial equalities/reductions on terms).
4.1 Syntax
Fix a partition of the set of atoms from Definition 2.1 into two disjoint countably infinite sets and , so that
Splitting in two is key to the syntax, but not to the semantics: the notion of model in Definition 5.3 is identical to Definition 3.2 and is based on finitely-supported nominal sets as usual. Only the syntax uses the more powerful notions of and (and it is more powerful; see e.g. Example 5.10). This echoes the formal distinction between ‘names that exist to be bound’ and ‘names that exist to be free’ used in some treatments of logic [25, 39], though this distinction is not so rigid here; e.g. a ‘standalone atom’ a can appear either from or and via a permutation or substitution ‘migrate’ between them.
Fix a countably infinite set of unknowns. X, Y, Z will range over distinct unknowns.
Types are as in Definition 2.2. Terms are defined by:
[ ] is a (level 1) substitution, which is a finite partial function from atoms to terms, mapping to and undefined elsewhere (so finite substitutions are directly in this syntax, just like finite permutations on unknowns πX are directly part of nominal terms). We call X[:]n1 a moderated unknown.
The condition c may seem odd—so λa:φa is not well-formed syntax if a —but since a is supposed to be bound we can intuitively always α-convert it to be in . This is a useful ‘hygiene’ simplification, since just by looking at an atom a we can tell if it could be bound (a ) or captured by an instantiation (a ). We can always move between one world and the other using a moderating substitution, as in λa:φX[b:a] where a and b .
An incomplete term. The typing ab:φX:φ λa:φX[b:a] : φφ where a and b represents an incomplete typing ‘λx:φt where t has type φ’. This is an term for a function on one argument.
Looking forward to the level 1 and 2 substitutions in Definitions 4.10 and 5.1, we will be able to complete λa:φX to a complete term, by applying the substitution [X : b]. We get the identity λa:φa. Without unknowns, both the incomplete and the complete terms would be represented by λa:φ fa for a higher-order f : φφ (whereas X has type φ).
An incomplete HOL predicate. Assume base types ι and o and constants : ooo and : (ιo)o. The typing X : o Y : ι b:ι (λb:ιX)X[b :Y] : o represents an incomplete HOL predicate.
Without level 2 variables, both the incomplete and the complete terms would be represented by b:ι f : ιo (λb:ι fa) fa.
Suppose a permutation π (Definition 2.8) is such that nontriv(π) . Define a permutation action πr on terms by:
Intuitively, the reason that we restrict nontriv to atoms in is so that we only rename the atoms that can be λ-abstracted. This restriction could be removed, and the syntax made ‘more equivariant’, but at the price of complicating the syntax X[ ]n1 to (πX)[ ]n1 so that we could write π(X [ ]πX)[π():π]. There would be nothing wrong with this—it just makes our basic syntax slightly more complicated. Since there is no change in expressivity, we leave this out.
We could also emulate π using the substitution [ ]n1, but then we must add (SubId).
α-equivalence r s is the least congruence such that if b fa(r) then λa:φr λb:φ(b a)r. Henceforth we quotient terms by α-equivalence.
Define free atoms fa and free unknowns fv by:
We give terms a capture-avoiding substitution action r[ ]n1 as follows:
Note above that if then it gets garbage-collected (eliminated) on X, as we see from the condition ‘ ’ in ‘i BA ’. So for instance X[b:][: X[b::] where b and X[b:a][a: X[b:] where a .
Let β-equivalence be the least congruence (Definition 4.7) such that (λa:φr)t r[a : t].
4.2 Environments and typing
A type environment Γ is a set of atomic typings a : φ or X : φ which is functional in the sense that if a : φ and a : then φ , and similarly for X (i.e. ‘add X:φ to Definition 2.5’).
Define dom(Γa φa:φ ΓX φX:φ Γ.
Define a typing relation by the rules in Figure 2.
One interesting feature of Figure 2 is that must be typed in Γ in (Meta). This means that we can strengthen only for atoms in (the ‘abstractable’ atoms); see Lemma 4.15. See Remarks 4.16 and 4.19 for discussions of why. Also, the are typed in a context in which the occur. There is no problem with circularities; in the models the are just elements (with special properties).
If Γ r : ψ and c dom then Γc:χ r : ψ.
By induction on the derivation of Γ r : ψ. For the case of we may rename using equivariance (Theorem 2.13).
If Γc:χ r : ψ and c fa then Γ r : ψ.
(Meta) states that if X:φ Γ and : Γ for 1in then Γ for 1in implies Γ X[:] : φ. We must insist on : Γ, for suppose otherwise: Then for a and b we could derive X:φa:χ λb:φX[a : b] : φφ; the types of a and b are inconsistent.
fa(r[a : t]) (fa
Γ(:)n r : φ and Γ(:)n for 1 jn imply Γ(:)n r[ ]n1 : φ.
As a corollary, if c fa then Γc:χ r : φ and Γ s : χ imply Γ r[c : s] : φ.
Lemma 4.18 does not state Γc:χ r : φ and Γ s : χ imply Γ r[c : s] : φ, for c . For instance X:φc:φ X : φ and X:φ X : φ but it is not the case that X:φ X[c : X] : φ.
5 Level 2 substitution
A level 2 substitution is a map θ from unknowns to terms.7 Write [X : t] for the substitution mapping X to t and all other Y to Y.
If ΓX:ξ r:φ and Γ t:ξ then Γ r[X : t]:φ.
By induction on the derivation of ΓX:ξ r:φ. The cases of and are routine:
The case of (Meta) for X. Suppose ΓX:ξ(:)n X[:]n1 : ξ because ΓX:ξ(:)n for 1 jn.
Suppose Γ(:)n t : ξ. By inductive hypothesis Γ(:)n [X:t] : for 1 jn. By definition X[:]n1[X:t t[:[X:t]]n1. So it suffices to show that Γ(:)n t[:[X:t]]n1 : ξ. We use Lemma 4.18.
The case of Renaming if necessary using equivariance (Theorem 2.13), assume a fa. By definition (λa:φr)[X:t λa:φ(r[X:t]). We use the inductive hypothesis for ΓX:ξa:φ r : ψ.
5.1 Models
A model consists of an assignment for each type environment Γ and type φ of a finitely-supported set together with the same data as in Definition 3.2, satisfying the same equivariance conditions and (Suba) to (Subλ) except that in addition:
8. If Γ(a (a) for every a then
Suppose : Γ and for 1in. Suppose x
If x
Direct from equivariance (Theorem 2.13).
By Lemma 5.5 syntax is equivariant for atoms in , because the predicate we use to define it in Definition 4.3 uses a partition . The notion of model of Definition 5.3 does not use this partition however, so it is equivariant for all π, and not just those with nontriv
Suppose :ψ Γ and for 1in, and suppose z
A valuation ς is a function on unknowns such that supp(ς(X)) for every X.
Write Γ ς when X:φ Γ implies
Definition 5.7 seems harmless, but it carries some real meaning. By condition 6 of Definitions 3.2 and 5.3, if x
This is related to a celebrated topic of continuing debate in the philosophy of language that assertions like ‘the King of France is bald’ name and assert properties of apparently non-existent objects; they have meaning but do not denote [36]. In the same way, the variable X asserts a property of all atoms in —that they may appear in the denotation of X—but this does not imply that these atoms exist in the possible world determined by the typing Γ. The typing context determines which of the atoms in have existential import [29]. The extra twist to this story here, is that in nominal techniques atoms name themselves.
This is another way of looking at the fine detail of the rule (Meta), that : Γ even though fa(X[:]n1]) in general. In order to be substituted for, the atom must exist, and to exist it must be typed.
Suppose Γ ς and Γ r : φ. Define an interpretation function mapping r to , by induction on r:
A few brief words on the case of λa:φr: The condition a dom prevents a:φ from overwriting typing information in Γ. The condition a ensures that the clause is well-defined, since otherwise a might ‘accidentally capture’ an atom in for X fv. The effect of a capturing an atom in X can be attained e.g. as λa:φ(X[:a]) where .
The language with holes (Definition 4.3) is more expressive than the language without it (Definition 2.2). For instance, a:φ r[aa r (Definition 3.9) is true for r without unknowns, but otherwise may be false. This is because without unknowns, we can use (Suba) to (Subλ) to push substitution down to the atoms until it either vanishes or substitutes. With unknowns this cannot be done; we may get ‘stuck’ on a moderated unknown.
Put another way, X really does range over arbitrary elements of the model whereas a can only be substituted for an arbitrary element of the model—and these are two distinct concepts.
Consider one base type and no constants and a nominal model such that a01, where supp(0 supp(1. Set a[ax x, 0[ax 0, and 1[ax 0.
In STLC we cannot detect the element 1 and its sensitivity to [ax] even though a supp(1). In STLC extended with unknowns, we can. Thus, we use (Sub#) instead of a weaker axiom that b[ax x.
If Γ ς and Γ r : φ then
We consider two cases; the rest is as proof of Theorem 3.4:
The case of Suppose Γa:φ r : ψ and a so that by Γ λa:φr : φψ. By inductive hypothesis
The case of (Meta). Suppose Γ and X:φ Γ and : Γ for 1in, so that by (Meta) Γ X [:]i : φ.
By inductive hypothesis and by assumption
5.2 Soundness for β-conversion
Suppose : Γ for i A and Γ r : ψ and Γ for i A. Suppose Γ ς. Then
By a routine induction on the derivation of Γ r : ψ. We consider two cases:
The case of for λc:χr. Renaming if necessary, suppose c is fresh (so that c (supp() fa()) dom). We reason as follows:
The case of (Meta). We reason as follows, where B 1n and j B :
Some detailed calculations are hidden in the ‘fact’ used above. This follows using (Subλ) and (SubApp) from Definition 5.4, and is one reason that in that definition we ‘freshened’ the to ; to avoid clash.
Write ‘Γ rs : φ’ as shorthand for ‘Γ r : φ and Γ s : φ’. Suppose Γ ς.
1. Suppose Γ r φ and Γ s φ. If and then rs.
2. Suppose Γa:φ r ψ. If then λa:φr λa:φ.
3. Suppose X:φ Γ and : 1in Γ. Suppose Γ and for 1 jn.
These are facts of equality in sets.
If r s (Defn. 4.11) and Γ r : φ and Γ ζ then
We would expect a completeness result like Theorem 3.11 to hold and have a similar proof. Details will be in a journal version. We should verify soundness under instantiating unknowns:
Suppose ΓX:χ r : φ and Γ t : ψ. Suppose Γ ς.
Then r[X:t]
We consider (Meta) for X. Suppose Γ X:χ(:)n1 and Γ : for 1in so that by (Meta) X:χ(:)n X [:]i. Then X [:]
6 Conclusions
We have built a semantics for the simply-typed λ-calculus (STLC), based on nominal sets. In keeping with the ‘nominal’ philosophy, variables (names) are denoted by themselves. This draws certain structure that is normally external to the denotation inside it, and this extra structure excludes some arguably pathological homomorphisms between models. We also exploit the semantics to existential variables, or ‘holes’ (suggesting that we do not just get more models out of this nominal semantics, but also more languages).
The constructions are not really any harder than for traditional STLC semantics. When reading for instance Definition 3.2, the reader should mentally place this side-by-side with a full specification of traditional STLC semantics, including for instance a precise definition of valuations as graphs (these are functions with the general shape ( X) X). Our nominal semantics for STLC is no harder than what the reader already knows; it is just different.
Atypically for nominal techniques so far as exemplified e.g. by [40, 38, 3, 5], atoms have non-trivial types. These, if they assign atoms any type information at all, assign them ‘the type of atoms’. There has been some work assigning more interesting types to atoms [8], but not in denotations.
In the course of doing all these things, we note echoes of other strands of research. The distinction between b and b : φ Γ is an instance of the distinction between meaning and denotation (only finitely many of the atoms in the permission set of an unknown have existential import in the denotation) [36, 29]. Our use of and , which is borrowed from [6, 7], is reminiscent of the two kinds of variable used by Frege [25] (for a more modern presentation see e.g. [39, Chapter IV, Section 1]). This is more an analogy than a precise correspondence and we will discuss matters further in a longer paper where we have more space to develop the syntax. We still have only one set of atoms and the ‘nominal’ constructions, notably the notions of support, binding, freshness, and nominal set, are unchanged. We have freely imported ideas from (permissive) nominal terms, notably in our treatment of existential variables.
6.1 Related work
Valuations and unknowns. We gave unknowns a semantics using valuations in Definition 5.9. Arguably it is disappointing: why map atoms to themselves in a denotation but then switch to another (more traditional) methodology for unknowns? One answer is that atoms are universal variables (could be replaced by anything) whereas unknowns are existential variables (must be replaced by something), so it is reasonable to interpret them using a valuation, and perhaps we should. Indeed there is a precedent for this: atoms correspond to δ-variables and unknowns to γ-variables from [42]. Making this formal by considering a paper similar to this one but aimed at first-order logic is a topic of current research.
Still, there is an interesting alternative. In [16] a direct nominal semantics is explored for unknowns X, analogous to how atoms a map to themselves in this paper, called two-level nominal sets. Two-level nominal sets with substitutions would provide a theory of incompleteness in which holes are directly represented in the semantics. There is no need for that in this paper because we have no level 3 variables (in the style e.g. of the λ-context calculus [18]); but if there were, two-level nominal sets might be not only interesting, but necessary.
Models as presheafs. The reader familiar with category theory will recognise in Definition 3.2 a presheaf. In fact, we have enriched the usual presheaf Sets (presheaves over finite sets and injections between them) to a presheaf over an indexing category enriched with types. Condition 5 of the two definitions (for ) states that these presheaves should preserve pullbacks of monos; this is the critical property required for the sets-based presentation of this paper to work [17]. Presheaves enriched over types have appeared in [43], without the nominal sets style presentation and written for a different audience (one stemming from view of syntax and substitution based on [11]). The presheaves are used differently: by considering initial objects, inductive datatypes of well-typed syntax-with-binding are constructed.
Other theories of functions. Combinatory algebra (CA) assumes constants S, K, and I. Axioms allow them to model the λ-calculus. However, CA is strictly weaker than the theory of β-conversion; the rule cannot be equationally axiomatised, because λ cannot be directly expressed (though any given λ-term can be compiled to combinators). This can be fixed using explicit indeterminates which, from the point of view of this paper, look a lot like atoms [37].
Alternatively, lambda-abstraction algebras (LAAs) are a first-order axiomatisation which does satisfy ξ [30]; again, from the point of view of this paper LAAs look much like the axioms we have considered. LAAs are not typed; a ‘nominal’ equivalent of them was considered by the first author with Mathijssen [23]. So this paper is significantly different from both since, as we see comparing this paper with [23], the addition of types makes a real difference to the models. LAAs take semantics in ‘ordinary’ sets, so their semantics is not well-pointed in the sense of this paper, and we do not obtain the language with meta-variables which we have developed here or relate so directly with a wider research context (e.g. into nominal techniques). One further subtle feature of LAA models is that they do not have finite support (we do not argue whether this is good or bad; we merely observe this as a significant difference).
Salibra and others have thought deeply about the lattice properties of λ-calculus models. As a final note we mention that nominal algebra satisfies an HSPA theorem [13], and permissive-nominal algebra satisfies an HSP theorem [15]. This has also been considered by Kurz and others [28]. The deeper theory here—how theorems of universal algebra applied to λ-calculus adapt to the nominal context—remains unexplored.
Other theories of existential variables. In implemented systems like LF and Isabelle [33] these are handled as a special syntactic category of higher-order variable. That is, an unknown of type ι depending on (universal) variables of type τ and is modelled by a variable of type τ ι. We make no claim that our model of existential variables is better in implementation—it is simply too early to tell—but generally speaking we are against solving problems by moving to higher orders. Plenty of complexity can be encoded in function spaces, and this is fine for implementation, but encoding something is not the same as having a good mathematical model of it. Jojgov includes a excellent and detailed discussion of this issue in [27], which is his own analysis of incompleteness; intuitively, by conflating β-conversion with incompleteness it becomes impossible to distinguish between a complete derivation of higher type, and an incomplete derivation of lower type. We add that the denotation of τ ι is uncountable, even if the denotations of τ, , and ι are countable. We would not immediately expect there to be uncountably many existential variables of type ι, so if only on the grounds of size we would hope for something smaller. Our denotations deliver this: an existential variable of type ι is just an unknown X : ι.
Contextual modal type theory (CMTT) has two levels of variable; it enriches STLC with ‘modal types’ representing open code [31]. However, level 2 variables of CMTT are not existential variables; they are a species of intensional variable ranging over code. Making this formal using a nominal semantics related to the semantics of this paper, is current research by the first author.
6.2 Future work
We note that, as it stands, there is no general mathematical framework for the study of incomplete terms in type theory. Implementors of proof assistants invent ad hoc methods for representing incomplete terms, representing incomplete proof states, in their systems. Methods evolve more through trial and error than deep mathematical insight. For instance, early versions of Coq used a complex system involving two syntactic classes—‘existential variables’ and ‘metavariables’—for representing incomplete proof states. Matita [1], whose design was influenced by lessons learned in Coq’s development, used from the outset a much simpler scheme where the concepts of ‘existential variable’ and ‘metavariable’ are unified [4].
We hope that the work presented in Section 4 forms the basis for further, mathematical study of incomplete terms in type theory. For instance, the model of STLC in Definition 3.2 could be extended to a dependent type theory like e.g. compact λP [41, Subsection 14.2, Figure 14.1] (with or without incompleteness).
It should be fairly easy to internalise the substitution action for unknowns by adding λX, thus obtaining a two-level system with logic and computation at both levels—the result should resemble the first two levels of the lambda-context calculus [18], but with a stronger theory of α-equivalence and more reductions. One concrete application of this may be to expressing tactics—functions from incomplete derivations to incomplete derivations—in type-theory based theorem-provers, which need to program on terms (considered as computation or proof respectively). More goes into such a design than metavariables, but the character of metavariables is key to that of existing implementations [34].
Notions of incompleteness can be motivated by efficiency and speed; notably [35] was motivated by optimising unification in LF. These ideas have led to several implementations; an up-to-date overview is in [34]. Note that the details of the syntax are different: the work uses a two-level type system with special types for closed code, and ‘meta-variables’ range over closed elements of the domain (i.e. supp(ς(X, intuitively). No general semantic theory has been given for this line of research, and we suspect that the nominal denotations of this paper could be turned to that task.
References
[1] Andrea Asperti, Claudo Sacerdoti Coen, Enrico Tassi & Stefano Zacchiroli (2007): Crafting a Proof Assistant, pp. 18–32. Lecture Notes in Computer Science, Springer, doi:10.1007/978-3-540-74464-.
[2] Christoph Benzmüller, Chad E. Brown & Michael Kohlhase (2004): Higher-order semantics and extensionality. Journal of Symbolic Logic 69, pp. 1027–1088, doi:10.2178/jsl/1102022211.
[3] James Cheney & Christian Urban (2004): Alpha-Prolog: A Logic Programming Language with Names, Binding and Alpha-Equivalence. In Bart Demoen & Vladimir Lifschitz, editors: Proceedings of the 20th International Conference on Logic Programming (ICLP 2004), Lecture Notes in Computer Science 3132, Springer, pp. 269–283, doi:10.1007/978-3-540-27775-.
[4] Claudio Sacerdoti Coen (2004): Mathematical Knowledge Management and Interactive Theorem Proving. Ph.D. thesis, University of Bologna.
[5] Gilles Dowek & Murdoch J. Gabbay (2010): Permissive Nominal Logic. In: Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2010), pp. 165–176, doi:10.1145/1836089.1836111.
[6] Gilles Dowek, Murdoch J. Gabbay & Dominic P. Mulligan (2009): Permissive Nominal Terms and their Unification. In: Proceedings of the 24th Italian Conference on Computational Logic (CILC’09).
[7] Gilles Dowek, Murdoch J. Gabbay & Dominic P. Mulligan (2010): Permissive Nominal Terms and their Unification: an infinite, co-infinite approach to nominal techniques (journal version). Logic Journal of the IGPL 18(6), pp. 769–822, doi:10.1093/jigpal/jzq006.
[8] Maribel Fernández & Murdoch J. Gabbay (2007): Curry-style types for nominal terms. In: Types for Proofs and Programs (TYPES 06), Lecture Notes in Computer Science 4502, Springer, pp. 125–139, doi:10.1007/978-3-540-74464-.
[9] Maribel Fernández & Murdoch J. Gabbay (2007): Nominal rewriting (journal version). Information and Computation 205(6), pp. 917–965, doi:10.1016/j.ic.2006.12.002.
[10] Maribel Fernández & Murdoch J. Gabbay (2010): Closed nominal rewriting and efficiently computable nominal algebra equality. In: Electronic Proceedings in Theoretical Computer Science, 34, pp. 37–51, doi:10.4204/EPTCS.34.5.
[11] Marcelo P. Fiore, Gordon D. Plotkin & Daniele Turi (1999): Abstract Syntax and Variable Binding. In: Proceedings of the 14th IEEE Symposium on Logic in Computer Science (LICS 1999), IEEE Computer Society Press, pp. 193–202, doi:10.1109/LICS.1999.782615.
[12] Murdoch J. Gabbay (2007): Fresh Logic. Journal of Applied Logic 5(2), pp. 356–387, doi:10.1016/j.jal.2005.10.012.
[13] Murdoch J. Gabbay (2009): Nominal Algebra and the HSP Theorem. Journal of Logic and Computation 19(2), pp. 341–367, doi:10.1093/logcom/exn055.
[14] Murdoch J. Gabbay (2011): Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic 17(2), pp. 161–229, doi:10.2178/bsl/1305810911.
[15] Murdoch J. Gabbay (2011): Nominal terms and nominal logics: from foundations to meta-mathematics. In: Handbook of Philosophical Logic, 17, Kluwer.
[16] Murdoch J. Gabbay (2011): Two-level nominal sets and semantic nominal terms: an extension of nominal set theory for handling meta-variables. Mathematical Structures in Computer Science doi:10.1017/S0960129511000272. Published online.
[17] Murdoch J. Gabbay & Martin Hofmann (2008): Nominal renaming sets. In: Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2008), Springer, pp. 158–173, doi:10.1007/978-3-540-89439-.
[18] Murdoch J. Gabbay & Stéphane Lengrand (2009): The lambda-context calculus (extended version). Information and computation 207, pp. 1369–1400, doi:10.1016/j.ic.2009.06.004.
[19] Murdoch J. Gabbay & Aad Mathijssen (2006): One-and-a-halfth-order logic. In: Proceedings of the 8th ACM-SIGPLAN International Symposium on Principles and Practice of Declarative Programming (PPDP 2006), ACM, pp. 189–200, doi:10.1145/1140335.1140359.
[20] Murdoch J. Gabbay & Aad Mathijssen (2008): Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing 20(4-5), pp. 451–479, doi:10.1007/.
[21] Murdoch J. Gabbay & Aad Mathijssen (2008): One-and-a-halfth-order Logic. Journal of Logic and Computation 18(4), pp. 521–562, doi:10.1093/logcom/exm064.
[22] Murdoch J. Gabbay & Aad Mathijssen (2009): Nominal universal algebra: equational logic with names and binding. Journal of Logic and Computation 19(6), pp. 1455–1508, doi:10.1093/logcom/exp033.
[23] Murdoch J. Gabbay & Aad Mathijssen (2010): A nominal axiomatisation of the lambda-calculus. Journal of Logic and Computation 20(2), pp. 501–531, doi:10.1093/logcom/exp049.
[24] Murdoch J. Gabbay & Andrew M. Pitts (2001): A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing 13(3–5), pp. 341–363, doi:10.1007/s001650200016.
[25] Jean van Heijenoort (1967): From Frege to Gödel: a source book in mathematical logic, 1879-1931. Harvard University Press.
[26] Leon Henkin (1950): Completeness in the Theory of Types. Journal of Symbolic Logic 15, pp. 81–91.
[27] Gueorgui I. Jojgov (2002): Holes with Binding Power. In: TYPES, Lecture Notes in Computer Science 2646, Springer, pp. 162–181, doi:doi:10.1007/3-540-39185-.
[28] Alexander Kurz & Daniela Petrişan (2010): On Universal Algebra over Nominal Sets. Mathematical Structures in Computer Science 20, pp. 285–318, doi:10.1017/S0960129509990399.
[29] Karel Lambert (1963): Existential Import Revisited. Notre Dame Journal of Formal Logic 4(4), pp. 288–292.
[30] Giulio Manzonetto & Antonino Salibra (2010): Applying Universal Algebra to Lambda Calculus. Journal of Logic and computation 20(4), pp. 877–915, doi:10.1093/logcom/exn085.
[31] Aleksandar Nanevski, Frank Pfenning & Brigitte Pientka (2008): Contextual modal type theory. ACM Transactions on Computational Logic (TOCL) 9(3), pp. 1–49, doi:10.1145/1352582.1352591.
[32] John von Neumann (1929): Über eine Widerspruchsfreiheitsfrage in der axiomatischen Mengenlehre. Journal für die reine und angewandte Mathematik 160.
[33] Lawrence C. Paulson (1989): The Foundation of a Generic Theorem Prover. Journal of Automated Reasoning 5(3), pp. 363–397, doi:10.1007/BF00248324.
[34] Brigitte Pientka & Joshua Dunfield (2010): Beluga: A Framework for Programming and Reasoning with Deductive Systems (System Description). In: Proceedings of the 5th International Joint Conference on Automated Reasoning (IJCAR 2010), Lecture Notes in Computer Science 6173, Springer, pp. 15–21.
[35] Brigitte Pientka & Frank Pfenning (2003): Optimizing Higher-Order Pattern Unification. In: Proceedings of the 19th International Conference on Automated Deduction (CADE 2003), Lecture Notes in Computer Science 2741, Springer, pp. 473–487.
[36] Bertrand Russell (1905): On Denoting. Mind, New Series 14(56), p. 479493.
[37] Peter Selinger (2002): The lambda calculus is algebraic. Journal of Functional Programming 12(6), pp. 549–566, doi:10.1017/S0956796801004294.
[38] Mark R. Shinwell, Andrew M. Pitts & Murdoch J. Gabbay (2003): FreshML: Programming with Binders Made Simple. In: Proceedings of the 8th ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), 38, ACM Press, pp. 263–274, doi:10.1145/944705.944729.
[39] Raymond Smullyan (1968): First-order logic. Springer. Reprinted by Dover, 1995.
[40] Christian Urban, Andrew M. Pitts & Murdoch J. Gabbay (2004): Nominal Unification. Theoretical Computer Science 323(1–3), pp. 473–497, doi:10.1016/j.tcs.2004.06.016.
[41] Pawel Urzyczyn & Morten Sørensen (2006): Lectures on the Curry-Howard isomorphism. Studies in Logic 149, Elsevier.
[42] Claus-Peter Wirth (2004): Descente Infinie + Deduction. Logic Journal of the IGPL 12(1), pp. 1–96, doi:10.1093/jigpal/12.1.1.
[43] Julianna Zsidó (2010): Typed abstract syntax. Ph.D. thesis, University of Nice.
Notes
We are very grateful to Peter Selinger and to two anonymous referees for their useful and constructive comments. We acknowledge the support of the Leverhulme trust. We acknowledge the support of grant RYC-2006-002131 at the Polytechnic University of Madrid. The project CerCo acknowledges the financial support of the Future and Emerging Technologies (FET) programme within the Seventh Framework Programme for Research of the European Commission, under FET-Open grant number: 243881.
1 must contain all the variables mentioned in the predicate. It is not the case that a a if and only if a b—but it is the case that a b if and only if b a. ↩
2This technique was used in pencil-and-paper mathematics instead of long inductive proofs, e.g. in [12]. ↩
3(Suba) to (SubId) soundly and completely characterise the syntactic model of substitution. In this paper we are also interested in non-syntactic models, so weaker axioms—and thus more models—are reasonable. We chose the axioms above because they are closed, in the sense of [9, 10], which gives better computational properties (if we ever design an abstract machine using this semantics). ↩
4So [a:φ]x need not be precisely equal to the Gabbay-Pitts atoms-abstraction x from [24]. ↩
5In fact by Theorem 3.4 c supp() follows from c dom. But that does not matter; we can just rename c ‘fresh’, without having to engage in detailed calculations about how fresh it is. ↩
6The condition is there to guarantee that X[:] and X[:] are well-formed terms. ↩
7The reader familiar with nominal techniques might expect a condition that fa(θ(X)) always. This would be necessary if moderations were permutations, but is not if they are substitutions. See [15, Proposition 3.4.3]. ↩
8Definition 5.3 only provides substitution for one atom at a time. We need simultaneous substitution in the semantics to give meaning to level 2 variables (see Definition 5.9). The minor difficulty is that it might be that supp(). So we ‘rename atoms fresh’ first, and then substitute for these atoms one at a time. Certain detailed but routine verifications are necessary to make sure this works and is well-defined (depends neither on the fresh choice of , nor on the order in which the substitutions are then carried out). The relevant maths is described in [14, Section 6]. ↩