Intersection Types. Intersection types [11 ] were introduced as a refinement of simple types for the λ \lambda λ -calculus where arrow types σ → τ \sigma\to\tau σ → τ are replaced with
{ σ 1 , … , σ n } → τ , \{\sigma_1,\ldots,\sigma_n\} \to\tau, { σ 1 , … , σ n } → τ ,
i.e. the domain of the arrow becomes a finite set of types (presented as an intersection σ 1 ∩ ⋯ ∩ σ n \sigma_1 \cap\cdots\cap\sigma_n σ 1 ∩ ⋯ ∩ σ n in the original formalism, hence the terminology). The key feature of intersection type systems is that they enjoy not only subject reduction, as any reasonable type system, but also subject expansion : if M → β N M \to_\beta N M → β N , any typing of N N N can be turned backwards into a typing of M M M . As a consequence, intersection types have given rise to neat semantic counterparts (in particular as filter models [1 ] ) and, on the operational side, to characterisations of computational properties: while simple types only guarantee termination, intersection types allow to characterise , e.g. , weak [11 , 20 ] or head [22 , 23 ] normalisation.
Non-idempotent intersection types [15 , 19 ] renewed this approach by relaxing indempotence of intersection, i.e. σ ∩ σ = σ \sigma\cap\sigma= \sigma σ ∩ σ = σ no longer holds; equivalently arrow types are presented with a finite multiset of types as a domain, as in
[ σ 1 , … , σ n ] → τ . [\sigma_1,\ldots,\sigma_n] \to\tau. [ σ 1 , … , σ n ] → τ .
This shift unveiled a strong connexion with various program analysis tools related to linear logic: in particular, non-idempotent typings are in close correspondence with the standard relational model of the λ \lambda λ -calculus [2 , 8 , 9 ] , and with the multilinear approximation of λ \lambda λ -terms given by Taylor expansion [14 , 25 ] . As a consequence, the characterisations of operational properties (that are made much simpler to prove in a non-idempotent setting, thanks to linearity) could be turned into resource-sensitive results providing quantitative information and exact bounds on, e.g. , resource usage or execution time [9 ] .
Graded Types. In the same years, another thread of the literature studied a different enrichment of the domain of arrow types allowing to control the usage of resources by functional programs. Grounded in linear logic again [16 ] and in its decomposition of the arrow σ → τ \sigma\to\tau σ → τ into ! σ ⊸ τ !\sigma\multimap\tau ! σ ⊸ τ (where the exponential modality ! ! ! allows for erasure or duplication of its content while the linear arrow ⊸ \multimap ⊸ requires a single use of the argument), bounded linear logic [18 ] introduced annotated exponentials, as in
! a σ ⊸ τ , !^{a}\sigma\multimap\tau, ! a σ ⊸ τ ,
where a a a is intuitively a quantity indicating how many times the argument of a program may be used. Graded types [6 , 17 ] then simplified and generalised this idea by allowing the annotation a a a to be taken in any semiring, providing control on various aspects of the input of programs; this gave rise to a rich literature on graded coeffects .
Contribution. The present work aims at reconciling these two threads along the lines of a simple observation: the domains of the arrow in idempotent and non-idempotent intersection types (i.e., sets and multisets of types) can be seen as maps from types to booleans and from types to natural numbers, respectively, i.e. as maps associating grades to types. We introduce graded intersection types, a generalisation of intersection types where arrow types can be written as
[ σ 1 : a 1 , … , σ n : a n ] ⊸ τ . [\sigma_1 : a_1, \ldots, \sigma_n : a_n] \multimap\tau. [ σ 1 : a 1 , … , σ n : a n ] ⊸ τ .
The standard idempotent and non-idempotent settings are the instances where the grades a i a_i a i are taken to be booleans or natural integers, respectively.
In Section 1 we first discuss some algebraic properties of the grading semiring S \mathrm{S} S , and we introduce what we call S \mathrm{S} S -multisets; then we define the graded intersection type system I S \mathrm{I}_{\mathrm{S}} I S and its relevant fragment. In Section 2 we establish that, under suitable algebraic conditions on S \mathrm{S} S , the system enjoys subject reduction and subject expansion. In Section 3 we extend all the previous work to infinitary graded intersection types relaxing finite support of multisets of types (we consider locally finite support instead) as well as inductive type formation (we consider guarded coinductive formation instead), giving rise to locally finite graded intersection types ; their instance with grades taken in the tropical semiring has been thoroughly studied in another work [10 ] . In Section 4 we introduce the graded counterpart to switching from idempotent to non-idempotent intersection types: we replace single grades with multisets of grades . This can actually be done within the formalism, since these multisets themselves form a semiring with all desired properties. This lifting offers all the usual benefits of non-idempotency and linearity (which is mostly left for future work in the current version of this note). Finally in Section 5 we provide or recall some operational characterisations allowed by graded intersection types. In particular, as expected, unrestricted finite typing in I S \mathrm{I}_{\mathrm{S}} I S characterises head normalisation.
Related Work. Previous investigations already provided a partial semantic counterpart to this work. In particular Carraro, Ehrhard, and Salibra [12 ] showed that the graded exponential comonad associated to a resource semiring gives rise to a relational model of the λ \lambda λ -calculus (the standard relational model being built for the semiring of natural integers). Breuvart and Pagani [BP15] showed how the models generated this way allow to interpret graded types, and Breuvart, Kerjean, and Mirwässer [3 ] extended this approach to graded types for the differential λ \lambda λ -calculus. Although it is not explored yet, there should be a direct connection between these semantics and the syntax we introduce in this paper. Extending these semantic approaches to weak resource semirings, e.g. finding a relational model for boolean or tropical grades, is the subject of ongoing work. Extending our syntax with differentiation, or designing a graded Taylor approximation, is another promising perspective.
The infinitary intersection types that we introduce are reminiscent of the ones by Vial [Vial17; Via21], and actually gives rise to a characterisation of the same property of hereditary head normalisation [10 ] . As opposed to the rather involved external machinery in Vial’s work, our guarded coinductive definition already provides all needed ingredients for the proof.
It is outside the scope of this note to recall the wide literature on graded type systems controlling the coefficients of functional programs in order to ensure good behaviours, or to bound quantitative measures of these behaviours. Let us only mention that one long-term goal of the present work is to build on this literature so as to provide characterisations or exact bounds by putting into work the good properties of intersection types.
Finite Graded Intersection Type Systems
Algebraic Preliminaries
Definition 1 (Semiring). A semiring is a tuple ( S , + , 0 , × , 1 ) (\mathrm{S}, +, 0, \times, 1) ( S , + , 0 , × , 1 ) , where ( S , + , 0 ) (\mathrm{S}, +, 0) ( S , + , 0 ) is a commutative monoid, ( S , × , 1 ) (\mathrm{S}, \times, 1) ( S , × , 1 ) is a monoid, multiplication distributes over addition on both sides, and 0 0 0 is
absorbing for multiplication. Throughout this note we also assume that 0 ≠ 1 0 \ne1 0 = 1 . We define the algebraic preorder ≤ \le ≤ on S S S by writing a ≤ b a \le b a ≤ b whenever ∃ c \exists c ∃ c , b = a + c b = a + c b = a + c .
Standard examples include the natural, boolean and tropical semirings, respectively defined by:
N : = ( N , + , 0 , × , 1 ) , 2 : = ( { 0 , 1 } , ∨ , 0 , ∧ , 1 ) , T : = ( N ∪ { ∞ } , min , ∞ , + , 0 ) . \mathbb{N} := (\mathbb{N}, +, 0, \times, 1), \qquad\mathbf{2} := (\{0,1\}, \lor, 0, \land, 1), \qquad\mathbf{T} := (\mathbb{N} \cup\{\infty\}, \min, \infty, +, 0). N := ( N , + , 0 , × , 1 ) , 2 := ({ 0 , 1 } , ∨ , 0 , ∧ , 1 ) , T := ( N ∪ { ∞ } , min , ∞ , + , 0 ) .
where N \mathbb{N} N denotes the set of natural integers.
For a semiring to give rise to a well-behaved intersection type system enjoying, in particular, subject reduction (see § 2 ), we need to enforce some algebraic conditions.
Definition 2 (Resource Semiring). Given a semiring ( S , + , 0 , × , 1 ) (S, +, 0, \times, 1) ( S , + , 0 , × , 1 ) , consider the conditions:
Positivity a + b = 0 ⟹ a = b = 0 , No Zero Divisors a × b = 0 ⟹ a = 0 or b = 0 , Discreteness a + b = 1 ⟹ a = 0 or b = 0 , Weak Discreteness a + b = 1 ⟹ a ≥ 1 or b ≥ 1 , Additive Refinement a 1 + a 2 = b 1 + b 2 ⟹ ∃ c 11 , c 12 , c 21 , c 22 ∈ S , ∀ i ∈ { 1 , 2 } , a i = c i 1 + c i 2 , ∀ j ∈ { 1 , 2 } , b j = c 1 j + c 2 j , Mixed Refinement a × b = c 1 + c 2 ⟹ ∃ L finite , ∃ ( a l ) l ∈ L , ∃ ( b i l ) i ∈ { 1 , 2 } , l ∈ L , a = ∑ l ∈ L a l , ∀ l ∈ L , b = b 1 l + b 2 l , ∀ i ∈ { 1 , 2 } , c i = ∑ l ∈ L a l × b i l . \begin{aligned}
\textit{Positivity}\quad&a + b = 0 \quad\Longrightarrow\quad a = b = 0,\\
\textit{No Zero Divisors}\quad&a \times b = 0 \quad\Longrightarrow\quad a = 0 \text{ or } b = 0,\\
\textit{Discreteness}\quad&a + b = 1 \quad\Longrightarrow\quad a = 0 \text{ or } b = 0,\\
\textit{Weak Discreteness}\quad&a + b = 1 \quad\Longrightarrow\quad a \ge1 \text{ or } b \ge1,\\
\textit{Additive Refinement}\quad&a_1 + a_2 = b_1 + b_2 \quad\Longrightarrow\quad\exists c_{11},c_{12},c_{21},c_{22} \in S,\\
&\qquad\forall i \in\{1,2\},\ a_i = c_{i1} + c_{i2},\qquad\forall j \in\{1,2\},\ b_j = c_{1j} + c_{2j},\\
\textit{Mixed Refinement}\quad&a \times b = c_1 + c_2 \quad\Longrightarrow\quad\exists L\ \text{finite},\ \exists(a_l)_{l\in L},\ \exists(b_{il})_{i\in\{1,2\},l\in L},\\
&\qquad a = \sum_{l\in L} a_l,\qquad\forall l \in L,\ b = b_{1l} + b_{2l},\qquad\forall i \in\{1,2\},\ c_i = \sum_{l\in L} a_l \times b_{il}.
\end{aligned} Positivity No Zero Divisors Discreteness Weak Discreteness Additive Refinement Mixed Refinement a + b = 0 ⟹ a = b = 0 , a × b = 0 ⟹ a = 0 or b = 0 , a + b = 1 ⟹ a = 0 or b = 0 , a + b = 1 ⟹ a ≥ 1 or b ≥ 1 , a 1 + a 2 = b 1 + b 2 ⟹ ∃ c 11 , c 12 , c 21 , c 22 ∈ S , ∀ i ∈ { 1 , 2 } , a i = c i 1 + c i 2 , ∀ j ∈ { 1 , 2 } , b j = c 1 j + c 2 j , a × b = c 1 + c 2 ⟹ ∃ L finite , ∃ ( a l ) l ∈ L , ∃ ( b i l ) i ∈ { 1 , 2 } , l ∈ L , a = l ∈ L ∑ a l , ∀ l ∈ L , b = b 1 l + b 2 l , ∀ i ∈ { 1 , 2 } , c i = l ∈ L ∑ a l × b i l .
Then S S S is said to be a (weak) resource semiring whenever it is positive, has no zero divisors, is (weakly) discrete, additive refining and mixed refining. When contrasting the two notions, we also say strong resource semiring for a resource semiring.
The conditions for a resource semiring are already well-known in the literature: they ensure that the S S S -semimodule monad distributes over the powerset monad [13 , 7 ] , and they play a crucial role in the construction of an exponential comonad when designing graded versions of the relational and coherent models of linear logic [12 BP15, 21 ] .
We depart from the terminology coined by Carraro, Ehrhard, and Salibra [12 ] where resource semirings, additive refinement and mixed refinement were called “multiplicity semirings”, “additive splitting” and “multiplicative splitting”, respectively. The first change aims at avoiding ambiguities with existing notions, and is borrowed from Breuvart, Kerjean, and Mirwasser [3 ] ; the latter two bring back the original and standard algebraic terminology [24 ] .
The weak discreteness condition, as far as we know, is new; investigating how it can enter the semantic picture is ongoing work.
Lemma 3 (n n n -ary Properties). Let S S S be a semiring that is positive and has no zero divisors. The following properties hold, with all the considered index sets being finite. Then:
If S S S has discreteness, then it has n n n -ary discreteness: if ∑ i ∈ I a i = 1 \sum_{i\in I} a_i = 1 ∑ i ∈ I a i = 1 , then exactly one a i a_i a i is non-zero (and is equal to 1 1 1 ).
If S S S has weak discreteness and additive refinement, then it has n n n -ary weak discreteness: if ∑ i ∈ I a i ≥ 1 \sum_{i\in I} a_i \ge1 ∑ i ∈ I a i ≥ 1 , then ∃ i , a i ≥ 1 \exists i,\ a_i \ge1 ∃ i , a i ≥ 1 .
If S S S has additive refinement, then it has n n n -ary additive refinement:
∑ i ∈ I a i = ∑ j ∈ J b j ⟹ ∃ ( c i j ) i ∈ I , j ∈ J , ∀ i ∈ I , a i = ∑ j ∈ J c i j , ∀ j ∈ J , b j = ∑ i ∈ I c i j . \sum_{i\in I} a_i = \sum_{j\in J} b_j \quad\Longrightarrow\quad\exists(c_{ij})_{i\in I,j\in J},\ \forall i \in I,\ a_i = \sum_{j\in J} c_{ij},\ \ \forall j \in J,\ b_j = \sum_{i\in I} c_{ij}. i ∈ I ∑ a i = j ∈ J ∑ b j ⟹ ∃ ( c ij ) i ∈ I , j ∈ J , ∀ i ∈ I , a i = j ∈ J ∑ c ij , ∀ j ∈ J , b j = i ∈ I ∑ c ij .
If S S S has additive and mixed refinement, then it has n n n -ary mixed refinement:
a × b = ∑ i ∈ I c i ⟹ ∃ L , ∃ ( a l ) l ∈ L , ∃ ( b i l ) i ∈ I , l ∈ L , a \times b = \sum_{i\in I} c_i \Longrightarrow\exists L,\ \exists(a_l)_{l\in L},\ \exists(b_{il})_{i\in I,l\in L}, a × b = i ∈ I ∑ c i ⟹ ∃ L , ∃ ( a l ) l ∈ L , ∃ ( b i l ) i ∈ I , l ∈ L ,
a = ∑ l ∈ L a l , ∀ l ∈ L , b = ∑ i ∈ I b i l , ∀ i ∈ I , c i = ∑ l ∈ L a l × b i l . a = \sum_{l\in L} a_l,\qquad\forall l\in L,\ b = \sum_{i\in I} b_{il},\qquad\forall i\in I,\ c_i = \sum_{l\in L} a_l \times b_{il}. a = l ∈ L ∑ a l , ∀ l ∈ L , b = i ∈ I ∑ b i l , ∀ i ∈ I , c i = l ∈ L ∑ a l × b i l .
as well as simultaneous n n n -ary mixed refinement:
∀ x ∈ X , a × b x = ∑ i ∈ I x c x i ⟹ ∃ L , ∃ ( a l ) l ∈ L , ∃ ( b x i l ) x ∈ X , i ∈ I x , l ∈ L , \forall x\in X,\ a\times b_x = \sum_{i\in I_x} c_{xi} \Longrightarrow\exists L,\ \exists(a_l)_{l\in L},\ \exists(b_{xil})_{x\in X,i\in I_x,l\in L}, ∀ x ∈ X , a × b x = i ∈ I x ∑ c x i ⟹ ∃ L , ∃ ( a l ) l ∈ L , ∃ ( b x i l ) x ∈ X , i ∈ I x , l ∈ L ,
a = ∑ l ∈ L a l , ∀ x ∈ X , ( ∀ l ∈ L , b x = ∑ i ∈ I x b x i l , ∀ i ∈ I x , c x i = ∑ l ∈ L a l × b x i l ) . a = \sum_{l\in L} a_l,\qquad\forall x\in X,\ \left(\forall l\in L,\ b_x = \sum_{i\in I_x} b_{xil},\ \forall i\in I_x,\ c_{xi} = \sum_{l\in L} a_l\times b_{xil}\right). a = l ∈ L ∑ a l , ∀ x ∈ X , ( ∀ l ∈ L , b x = i ∈ I x ∑ b x i l , ∀ i ∈ I x , c x i = l ∈ L ∑ a l × b x i l ) .
S S S is a (weak) resource semiring iff it has n n n -ary (weak) discreteness, n n n -ary additive refinement, and n n n -ary mixed refinement.
Proof. For Items 1 and 2 the proof is a straightforward induction on the size of the considered index sets, by writing ∑ i a i = a i 0 + ∑ i ≠ i 0 a i \sum_i a_i = a_{i_0} + \sum_{i\ne i_0} a_i ∑ i a i = a i 0 + ∑ i = i 0 a i and using the corresponding binary hypotheses on S S S . The case where I I I (or J J J ) is the empty set is trivial for for Item 1 and given by positivity for Item 2.
For Item 3, we first prove n n n -ary mixed refinement, by induction. Write a × b = c i 0 + ∑ i ≠ i 0 c i a\times b=c_{i_0}+\sum_{i\ne i_0}c_i a × b = c i 0 + ∑ i = i 0 c i . Mixed refinement and n n n -ary additive refinement give families of elements of S S S such that:
a = ∑ l a l , ∀ l , b = b i 0 l + b i 0 l ′ , c i 0 = ∑ l a l × b i 0 l , a=\sum_l a_l,\qquad\forall l,\ b=b_{i_0l}+b'_{i_0l},\qquad c_{i_0}=\sum_l a_l\times b_{i_0l}, a = l ∑ a l , ∀ l , b = b i 0 l + b i 0 l ′ , c i 0 = l ∑ a l × b i 0 l ,
∀ i ≠ i 0 , c i = ∑ l d i l , ∀ l , a l × b i 0 l ′ = ∑ i ≠ i 0 d i l . \forall i\ne i_0,\ c_i=\sum_l d_{il},\qquad\forall l,\ a_l\times b'_{i_0l}=\sum_{i\ne i_0}d_{il}. ∀ i = i 0 , c i = l ∑ d i l , ∀ l , a l × b i 0 l ′ = i = i 0 ∑ d i l .
Apply induction on the last equality. The case where I I I is the empty set is given by the absence of zero divisors. For simultaneous n n n -ary mixed refinement, apply n n n -ary mixed refinement separately for each x x x , then take a common additive refinement of the finitely many decompositions of a a a .
For Item 4, there only remains to notice that positivity and absence of zero divisors correspond to the 0 0 0 -ary versions of additive and mixed refinement, respectively.
The finite set L L L in (binary) mixed refinement cannot in general be restricted to two indices. For example, in N [ u 1 , u 2 , u 3 , v 1 , v 2 ] \mathbb{N}[u_1,u_2,u_3,v_1,v_2] N [ u 1 , u 2 , u 3 , v 1 , v 2 ] , put
a = u 1 + u 2 + u 3 , b = v 1 + v 2 , c 1 = u 1 v 1 + u 2 v 2 , c 2 = u 1 v 2 + u 2 v 1 + u 3 v 1 + u 3 v 2 . a=u_1+u_2+u_3,\qquad b=v_1+v_2,\qquad c_1=u_1v_1+u_2v_2,\qquad c_2=u_1v_2+u_2v_1+u_3v_1+u_3v_2. a = u 1 + u 2 + u 3 , b = v 1 + v 2 , c 1 = u 1 v 1 + u 2 v 2 , c 2 = u 1 v 2 + u 2 v 1 + u 3 v 1 + u 3 v 2 .
Suppose that these admit a mixed refinement. Since each u i u_i u i has coefficient 1 in a a a , it would belong to exactly one component a l a_l a l . The corresponding b 1 l b_{1l} b 1 l must be v 1 v_1 v 1 if this component contains u 1 u_1 u 1 , v 2 v_2 v 2 if it contains u 2 u_2 u 2 , and 0 if it contains u 3 u_3 u 3 . These requirements are incompatible within a single component, so at least three components are necessary.
Requiring L = { 1 , 2 } L=\{1,2\} L = { 1 , 2 } is exactly condition (MS4) of [12 ] and is therefore strictly stronger than our mixed-refinement condition, which instead corresponds to (MS4’) in the later [BP15].
For n n n -ary mixed refinement, the bound ∣ L ∣ ≤ 2 ∣ I ∣ − 1 |L|\le2^{|I|-1} ∣ L ∣ ≤ 2 ∣ I ∣ − 1 from [12 Lemma 2] assumes the stronger binary condition (MS4), and does not hold under our assumptions.
Lemma 5. N \mathbb{N} N is a resource semiring. 2 \mathbf{2} 2 and T \mathbb{T} T are weak resource semirings.
For another example, the polynomial semiring N [ X ] \mathbb{N}[X] N [ X ] is a strong resource semiring: apply Lemma 29 to the free monoid on one generator. The same argument applies to any set of commuting indeterminates, using the free commutative monoid.
Finally, the usual notion of multisets can be generalised to functions having a semiring as their codomain, as follows:
Definition 6 (S-Multisets). For any set X X X , an S S S -multiset on X X X is a map m : X → S \mathrm{m}:X\to S m : X → S . It is finite if its support supp ( m ) : = { x ∈ X ∣ m ( x ) ≠ 0 } \operatorname{supp}(\mathrm{m}) := \{x\in X\mid\mathrm{m}(x)\ne0\} supp ( m ) := { x ∈ X ∣ m ( x ) = 0 } is finite. We denote the set of finite S S S -multisets by M S f ( X ) \mathcal{M}^{\mathrm{f}}_{S}(X) M S f ( X ) . Given finite families ( x i ) i ∈ I (x_i)_{i\in I} ( x i ) i ∈ I in X X X and ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I in S S S , we write [ x i : a i ] i ∈ I [x_i:a_i]_{i\in I} [ x i : a i ] i ∈ I for the S S S -multiset m : x ↦ ∑ i ∈ I , x i = x a i \mathrm{m}:x\mapsto\sum_{i\in I,x_i=x}a_i m : x ↦ ∑ i ∈ I , x i = x a i . In the following we always try to keep the x i x_i x i pairwise distinct, so that the definition boils down to m ( x i ) : = a i \mathrm{m}(x_i):=a_i m ( x i ) := a i , and m ( x ) : = 0 \mathrm{m}(x):=0 m ( x ) := 0 for x ∉ { x i ∣ i ∈ I } x\notin\{x_i\mid i\in I\} x ∈ / { x i ∣ i ∈ I } . When I = { 1 , … , n } I=\{1,\ldots,n\} I = { 1 , … , n } , we also write [ x 1 : a 1 , … , x n : a n ] [x_1:a_1,\ldots,x_n:a_n] [ x 1 : a 1 , … , x n : a n ] . In particular, [ ] [] [ ] is the empty S S S -multiset .
The operations of S S S induce an internal sum and an external product on M S f ( X ) \mathcal{M}^{\mathrm{f}}_{S}(X) M S f ( X ) :
( m + n ) ( x ) : = m ( x ) + n ( x ) , ( a × m ) ( x ) : = a × m ( x ) . (\mathrm{m}+\mathrm{n})(x):=\mathrm{m}(x)+\mathrm{n}(x),\qquad(a\times\mathrm{m})(x):=a\times\mathrm{m}(x). ( m + n ) ( x ) := m ( x ) + n ( x ) , ( a × m ) ( x ) := a × m ( x ) .
These operations preserve finite support. For N \mathbb{N} N and 2 2 2 , M N f ( X ) \mathcal{M}^{\mathrm{f}}_{\mathbb{N}}(X) M N f ( X ) and M 2 f ( X ) \mathcal{M}^{\mathrm{f}}_{2}(X) M 2 f ( X ) are the sets of finite multisets and finite subsets of X X X , respectively.
The Typing Systems
Let Λ \Lambda Λ be the set of pure λ \lambda λ -terms, taken up to α \alpha α -conversion, built from a countable set V \mathcal{V} V of variables. We write M [ N / x ] M[N/x] M [ N / x ] for capture-avoiding substitution, M → β N M\to_{\beta}N M → β N for one β \beta β -reduction step, and M → β ∗ N M\to_{\beta}^{*}N M → β ∗ N for a finite β \beta β -reduction sequence.
We now introduce a variant of intersection type systems where intersections of types, instead of being sets of types (idempotent intersections) or multisets of types (non-idempotent intersections), are finite S S S -multisets of types.
Definition 7 (S-Intersection Types). Let A \mathcal{A} A be a countable set of atoms. The sets I S \mathbb{I}_{S} I S of (finite) S S S -intersection types and ! I S ⊂ M S f ( I S ) ! \mathbb{I}_{S}\subset\mathcal{M}^{\mathrm{f}}_{S}(\mathbb{I}_{S}) ! I S ⊂ M S f ( I S ) of S S S -intersection multi-types are defined by mutual induction by the following formation rules:
α ∈ A α ∈ I S ( A ) m ∈ ! I S τ ∈ I S m ⊸ τ ∈ I S ( ⊸ ) [ ( σ i ∈ I S ) : a i ] i ∈ I [ σ i : a i ] i ∈ I ∈ ! I S ( ! ) \frac{\alpha\in\mathcal{A}}{\alpha\in\mathbb{I}_{S}}\;(\mathcal{A})
\qquad
\frac{\mathrm{m}\in!\mathbb{I}_{S}\qquad\tau\in\mathbb{I}_{S}}{\mathrm{m}\multimap\tau\in\mathbb{I}_{S}}\;(\multimap)
\qquad
\frac{[(\sigma_i\in\mathbb{I}_{S}):a_i]_{i\in I}}{[\sigma_i:a_i]_{i\in I}\in!\mathbb{I}_{S}}\;(!) α ∈ I S α ∈ A ( A ) m ⊸ τ ∈ I S m ∈ ! I S τ ∈ I S ( ⊸ ) [ σ i : a i ] i ∈ I ∈ ! I S [( σ i ∈ I S ) : a i ] i ∈ I ( !) where I I I is finite. Notice that the formation rule (!) has a finite S S S -multiset of hypotheses.
Typing judgments are of the shape Γ ⊢ M : σ \Gamma\vdash M:\sigma Γ ⊢ M : σ , with auxiliary judgments of the shape Γ ⊢ M : m \Gamma\vdash M:\mathrm{m} Γ ⊢ M : m . The context Γ \Gamma Γ is a map V → ! I S \mathcal{V}\to!\mathbb{I}_{S} V → ! I S whose support { x ∈ V ∣ Γ ( x ) ≠ [ ] } \{x\in\mathcal{V}\mid\Gamma(x)\ne[]\} { x ∈ V ∣ Γ ( x ) = [ ]} is a finite set { x 1 , … , x n } \{x_1,\ldots,x_n\} { x 1 , … , x n } . We will present Γ \Gamma Γ in the usual way, as a list x 1 : m 1 , … , x n : m n x_1:\mathrm{m}_1,\ldots,x_n:\mathrm{m}_n x 1 : m 1 , … , x n : m n with pairwise distinct x i x_i x i . The operations induced on M S f ( I S ) \mathcal{M}^{\mathrm{f}}_{S}(\mathbb{I}_{S}) M S f ( I S ) by the operations of S S S are again mapped on contexts:
( Γ + Γ ′ ) : x ↦ Γ ( x ) + Γ ′ ( x ) ( a × Γ ) : x ↦ a × Γ ( x ) . (\Gamma+\Gamma'):x\mapsto\Gamma(x)+\Gamma'(x)\qquad(a\times\Gamma):x\mapsto a\times\Gamma(x). ( Γ + Γ ′ ) : x ↦ Γ ( x ) + Γ ′ ( x ) ( a × Γ ) : x ↦ a × Γ ( x ) .
Definition 8 (Typing). A λ \lambda λ -term M M M is typable in I S \mathbb{I}_{S} I S whenever there is a derivation D \mathcal{D} D with conclusion Γ ⊢ M : σ \Gamma\vdash M:\sigma Γ ⊢ M : σ in the following (inductive) system of typing rules:
Γ + x : [ σ : 1 ] ⊢ x : σ ( a x ) Γ , x : m ⊢ M : τ Γ ⊢ λ x . M : m ⊸ τ ( ⊸ i ) \frac{}{\,\Gamma+x:[\sigma:1]\vdash x:\sigma\,}\;(\mathrm{ax})
\qquad
\frac{\Gamma,x:\mathrm{m}\vdash M:\tau}{\Gamma\vdash\lambda x.M:\mathrm{m}\multimap\tau}\;(\multimap_i) Γ + x : [ σ : 1 ] ⊢ x : σ ( ax ) Γ ⊢ λ x . M : m ⊸ τ Γ , x : m ⊢ M : τ ( ⊸ i ) Γ ⊢ M : m ⊸ τ Γ ′ ⊢ N : m Γ + Γ ′ ⊢ M N : τ ( ⊸ e ) [ ( Γ i ⊢ N : σ i ) : a i ] i ∈ I ∑ i ∈ I a i × Γ i ⊢ N : [ σ i : a i ] i ∈ I ( ! ) \frac{\Gamma\vdash M:\mathrm{m}\multimap\tau\qquad\Gamma'\vdash N:\mathrm{m}}{\Gamma+\Gamma'\vdash MN:\tau}\;(\multimap_e)
\qquad
\frac{[(\Gamma_i\vdash N:\sigma_i):a_i]_{i\in I}}{\sum_{i\in I}a_i\times\Gamma_i\vdash N:[\sigma_i:a_i]_{i\in I}}\;(!) Γ + Γ ′ ⊢ M N : τ Γ ⊢ M : m ⊸ τ Γ ′ ⊢ N : m ( ⊸ e ) ∑ i ∈ I a i × Γ i ⊢ N : [ σ i : a i ] i ∈ I [( Γ i ⊢ N : σ i ) : a i ] i ∈ I ( !) where I I I is finite, for some context Γ \Gamma Γ and S S S -intersection type σ \sigma σ . We then write D ▶ Γ ⊢ M : σ \mathcal{D}\blacktriangleright\Gamma\vdash M:\sigma D ▶ Γ ⊢ M : σ , and simply ▶ Γ ⊢ M : σ \blacktriangleright\Gamma\vdash M:\sigma ▶ Γ ⊢ M : σ to say that such a D \mathcal{D} D exists.
Definition 9 (Relevant Typing). A λ \lambda λ -term M M M is typable in the relevant system I S \mathbb{I}_{S} I S whenever there is D ▶ Γ ⊢ M : σ \mathcal{D}\blacktriangleright\Gamma\vdash M:\sigma D ▶ Γ ⊢ M : σ in the system where (ax) is replaced with the following typing rule:
x : [ σ : 1 ] ⊢ x : σ ( r a x ) \frac{}{x:[\sigma:1]\vdash x:\sigma}\;(\mathrm{rax}) x : [ σ : 1 ] ⊢ x : σ ( rax )
We use ⊢ \vdash ⊢ and ▶ \blacktriangleright ▶ for both systems, specifying the system when necessary.
Thus I S \mathrm{I_S} I S permits unused resources, including additional types on the variable in an axiom; r I S \mathrm{rI_S} r I S does not. For example, the original idempotent system from Coppo and Dezani-Ciancaglini [11 ] is I 2 \mathrm{I_2} I 2 , while the non-idempotent system presented in the survey by Bucciarelli, Kesner, and Ventura [4 ] is r I N \mathrm{rI_N} r I N . Both systems derive, e.g. ,
⊢ λ x . x ( x x ) : [ [ α : 1 ] ⊸ α : 1 + 1 , α : 1 ] ⊸ α . \vdash\lambda x.x(xx) : [[\alpha: 1] \multimap\alpha: 1 + 1, \alpha: 1] \multimap\alpha. ⊢ λ x . x ( xx ) : [[ α : 1 ] ⊸ α : 1 + 1 , α : 1 ] ⊸ α .
Over N \mathbb{N} N the coefficient 1 + 1 1 + 1 1 + 1 counts two uses; over 2 \mathbf{2} 2 these uses are identified. In the tropical instance of the above typing, both 1 1 1 and 1 + 1 1 + 1 1 + 1 become 0 0 0 .
Lemma 10 (Weakening and Relevance). The following properties hold:
In I S \mathrm{I_S} I S , if ▶ Γ ⊢ M : σ \blacktriangleright\ \Gamma\vdash M : \sigma ▶ Γ ⊢ M : σ , then ▶ Γ + Δ ⊢ M : σ \blacktriangleright\ \Gamma+ \Delta\vdash M : \sigma ▶ Γ + Δ ⊢ M : σ .
In I S \mathrm{I_S} I S , if ▶ Γ , x : m ⊢ M : σ \blacktriangleright\ \Gamma, x : m \vdash M : \sigma ▶ Γ , x : m ⊢ M : σ and x ∉ f v ( M ) x \notin\mathrm{fv}(M) x ∈ / fv ( M ) , then ▶ Γ ⊢ M : σ \blacktriangleright\ \Gamma\vdash M : \sigma ▶ Γ ⊢ M : σ .
In r I S \mathrm{rI_S} r I S , if ▶ Γ ⊢ M : σ \blacktriangleright\ \Gamma\vdash M : \sigma ▶ Γ ⊢ M : σ , then supp ( Γ ) ⊆ f v ( M ) \operatorname{supp}(\Gamma) \subseteq\mathrm{fv}(M) supp ( Γ ) ⊆ fv ( M ) .
Proof. For Item 1, propagate Δ \Delta Δ through abstractions and through the left premise of applications, adding it to the axiom context. Choose bound variables outside supp ( Δ ) \operatorname{supp}(\Delta) supp ( Δ ) , using α \alpha α -equivalence. Items 2 and 3 are by induction on the derivation. □ \square □
Notice that Item 1 concerns typing judgements only: arbitrary weakening of multi-typing judgements is not admissible. More precisely, the only contexts that can be added to a derivation whose conclusion is the typing rule (!) are of the form ∑ i ∈ I a i × Δ i \sum_{i \in I} a_i \times\Delta_i ∑ i ∈ I a i × Δ i . In particular a derivation ▶ ⊢ M : [ ] \blacktriangleright\ \vdash M : [] ▶ ⊢ M : [ ] cannot be weakened (unless S S S lacks positivity). One can easily show that Items 2 and 3, instead, also apply to multi-typing judgements.
Subject Reduction and Expansion
The key feature of usual intersection types is that they enjoy not only subject reduction, but also subject expansion. We now show that this is still the case for S S S -intersection types, relying on the algebraic conditions introduced in § 1.1 . We first show how these conditions come into play in the proof theory of our typing systems (§ 2.1 ). Then we prove subject reduction and expansion for I S \mathrm{I_S} I S (§ 2.2 ). Finally we show how the proof restricts to the relevant system r I S \mathrm{rI_S} r I S , using strong discreteness (§ 2.3 ).
Refining Typing Derivations
We work in I S \mathrm{I_S} I S ; in particular, all types, all families and all index sets considered below are finite. The following three lemmas transport the three items of Lemma 3 to (contexts of) multi-types derivations. We isolate these properties in order to highlight where the algebraic conditions will come into play in the subject reduction proof that will follow (in § 2.2 ).
Lemma 11 (Discreteness on Derivations). If S S S is positive, weakly discrete, and has additive refinement, then in I S \mathrm{I_S} I S , ▶ Δ ⊢ N : [ σ : 1 ] \blacktriangleright\ \Delta\vdash N : [\sigma: 1] ▶ Δ ⊢ N : [ σ : 1 ] implies ▶ Δ ⊢ N : σ \blacktriangleright\ \Delta\vdash N : \sigma ▶ Δ ⊢ N : σ . If S S S is positive and discrete, the same holds in r I S \mathrm{rI_S} r I S . In addition, the converse implications hold without any hypothesis on S S S .
Proof. Start from a derivation
[ ( Δ i ⊢ N : σ ) : a i ] i ∈ I Δ ⊢ N : [ σ : 1 ] ( ! ) \frac{[(\Delta_i \vdash N : \sigma) : a_i]_{i \in I}}{\Delta\vdash N : [\sigma: 1]}
\quad(!) Δ ⊢ N : [ σ : 1 ] [( Δ i ⊢ N : σ ) : a i ] i ∈ I ( !) for some finite set I I I , where ∑ i ∈ I a i = 1 \sum_{i \in I} a_i = 1 ∑ i ∈ I a i = 1 and Δ = ∑ i ∈ I a i × Δ i \Delta= \sum_{i \in I} a_i \times\Delta_i Δ = ∑ i ∈ I a i × Δ i . Lemma 3 (1) gives i 0 ∈ I i_0 \in I i 0 ∈ I with a i 0 ≥ 1 a_{i_0} \geq1 a i 0 ≥ 1 . Write a i 0 = 1 + c a_{i_0} = 1 + c a i 0 = 1 + c . Then
Δ = Δ i 0 + c × Δ i 0 + ∑ i ∈ I ∖ { i 0 } a i × Δ i , \Delta= \Delta_{i_0} + c \times\Delta_{i_0} + \sum_{i \in I \setminus\{i_0\}} a_i \times\Delta_i, Δ = Δ i 0 + c × Δ i 0 + i ∈ I ∖ { i 0 } ∑ a i × Δ i ,
and Lemma 10(1) gives ▶ Δ ⊢ N : σ \blacktriangleright\ \Delta\vdash N : \sigma ▶ Δ ⊢ N : σ . If S \mathbf{S} S is (strongly) discrete, the same reasoning gives a unique nonzero coefficient a i 0 = 1 a_{i_0}=1 a i 0 = 1 , so Δ = Δ i 0 \Delta=\Delta_{i_0} Δ = Δ i 0 and weakening is unnecessary. Conversely just apply the typing rule (!).
Lemma 12 (Additive Refinement on Derivations). Assume that S \mathbf{S} S is positive and has additive refinement. For every finite family ( m j ) j ∈ J (\mathbf{m}_j)_{j\in J} ( m j ) j ∈ J , in both ∣ S \mathord{\mid\!\mathbf{S}} ∣ S and r ∣ S \mathord{\mathbf{r}\mid\!\mathbf{S}} r ∣ S ,
if ▶ Δ ⊢ N : ∑ j ∈ J m j , then ∃ ( Δ j ) j ∈ J , Δ = ∑ j ∈ J Δ j , ∀ j ∈ J , ▶ Δ j ⊢ N : m j . \text{if }\ \blacktriangleright\ \Delta\vdash N:\sum_{j\in J}\mathbf{m}_j,\quad\text{then }\ \exists(\Delta_j)_{j\in J},\quad\Delta=\sum_{j\in J}\Delta_j,\quad\forall j\in J,\ \blacktriangleright\ \Delta_j\vdash N:\mathbf{m}_j. if ▶ Δ ⊢ N : j ∈ J ∑ m j , then ∃ ( Δ j ) j ∈ J , Δ = j ∈ J ∑ Δ j , ∀ j ∈ J , ▶ Δ j ⊢ N : m j . In addition, the converse implication holds without any hypothesis on S \mathbf{S} S .
Proof. For the left-to-right implication, the hypothesis is obtained by the typing rule (!) with premises Θ i ⊢ N : σ i \Theta_i\vdash N:\sigma_i Θ i ⊢ N : σ i and coefficients a i a_i a i , so that
∀ σ ∈ I S , ∑ i ∈ I σ i = σ a i = ∑ j ∈ J m j ( σ ) , Δ = ∑ i ∈ I a i × Θ i . \forall\sigma\in\mathbf{I}_{\mathbf{S}},\quad\sum_{\substack{i\in I\\ \sigma_i=\sigma}}a_i=\sum_{j\in J}\mathbf{m}_j(\sigma),\qquad\Delta=\sum_{i\in I}a_i\times\Theta_i. ∀ σ ∈ I S , i ∈ I σ i = σ ∑ a i = j ∈ J ∑ m j ( σ ) , Δ = i ∈ I ∑ a i × Θ i .
Apply n n n -ary additive refinement (Lemma 3 (2)) to the first equality, for each σ ∈ I S \sigma\in\mathbf{I}_{\mathbf{S}} σ ∈ I S . We obtain ( c i j ) i ∈ I , j ∈ J (c_{ij})_{i\in I,j\in J} ( c ij ) i ∈ I , j ∈ J such that
∀ i ∈ I , a i = ∑ j ∈ J c i j , ∀ j ∈ J , ∀ σ ∈ I S , m j ( σ ) = ∑ i ∈ I σ i = σ c i j . \forall i\in I,\ a_i=\sum_{j\in J}c_{ij},\qquad\forall j\in J,\ \forall\sigma\in\mathbf{I}_{\mathbf{S}},\ \mathbf{m}_j(\sigma)=\sum_{\substack{i\in I\\ \sigma_i=\sigma}}c_{ij}. ∀ i ∈ I , a i = j ∈ J ∑ c ij , ∀ j ∈ J , ∀ σ ∈ I S , m j ( σ ) = i ∈ I σ i = σ ∑ c ij .
Put Δ j : = ∑ i ∈ I c i j × Θ i \Delta_j:=\sum_{i\in I}c_{ij}\times\Theta_i Δ j := ∑ i ∈ I c ij × Θ i and form, for every j ∈ J j\in J j ∈ J ,
[ ( Θ i ⊢ N : σ i ) : c i j ] i ∈ I Δ j ⊢ N : m j ( ! ) \frac{\left[(\Theta_i\vdash N:\sigma_i):c_{ij}\right]_{i\in I}}{\Delta_j\vdash N:\mathbf{m}_j}\ (!) Δ j ⊢ N : m j [ ( Θ i ⊢ N : σ i ) : c ij ] i ∈ I ( !)
Distributivity gives ∑ j ∈ J Δ j = ∑ i ∈ I ( ∑ j ∈ J c i j ) × Θ i = Δ \sum_{j\in J}\Delta_j=\sum_{i\in I}(\sum_{j\in J}c_{ij})\times\Theta_i=\Delta ∑ j ∈ J Δ j = ∑ i ∈ I ( ∑ j ∈ J c ij ) × Θ i = Δ .
For the converse, each Δ j ⊢ N : m j \Delta_j\vdash N:\mathbf{m}_j Δ j ⊢ N : m j is obtained by the typing rule (!) with premises Θ j i ⊢ N : σ j i \Theta_{ji}\vdash N:\sigma_{ji} Θ j i ⊢ N : σ j i and coefficients a j i a_{ji} a j i , indexed by i ∈ I j i\in I_j i ∈ I j . Write:
[ ( Θ j i ⊢ N : σ j i ) : a j i ] j ∈ J , i ∈ I j ∑ j ∈ J Δ j ⊢ N : ∑ j ∈ J m j ( ! ) \frac{\left[(\Theta_{ji}\vdash N:\sigma_{ji}):a_{ji}\right]_{j\in J,i\in I_j}}{\sum_{j\in J}\Delta_j\vdash N:\sum_{j\in J}\mathbf{m}_j}\ (!) ∑ j ∈ J Δ j ⊢ N : ∑ j ∈ J m j [ ( Θ j i ⊢ N : σ j i ) : a j i ] j ∈ J , i ∈ I j ( !)
Lemma 13 (Mixed Refinement on Derivations). Assume that S \mathbf{S} S is positive, has no zero divisors, and has additive and mixed refinement. For all finite families ( a k ) k ∈ K (a_k)_{k\in K} ( a k ) k ∈ K and ( m k ) k ∈ K (\mathbf{m}_k)_{k\in K} ( m k ) k ∈ K , in both ∣ S \mathord{\mid\!\mathbf{S}} ∣ S and r ∣ S \mathord{\mathbf{r}\mid\!\mathbf{S}} r ∣ S ,
if ▶ Δ ⊢ N : ∑ k ∈ K a k × m k , \text{if }\ \blacktriangleright\ \Delta\vdash N:\sum_{k\in K}a_k\times\mathbf{m}_k, if ▶ Δ ⊢ N : k ∈ K ∑ a k × m k , then ∃ ( L k ) k ∈ K finite sets , ∃ ( a k l ) k ∈ K , l ∈ L k , ∃ ( Δ k l ) k ∈ K , l ∈ L k , \text{then }\ \exists(L_k)_{k\in K}\text{ finite sets},\ \exists(a_{kl})_{k\in K,l\in L_k},\ \exists(\Delta_{kl})_{k\in K,l\in L_k}, then ∃ ( L k ) k ∈ K finite sets , ∃ ( a k l ) k ∈ K , l ∈ L k , ∃ ( Δ k l ) k ∈ K , l ∈ L k , ∀ k ∈ K , a k = ∑ l ∈ L k a k l , Δ = ∑ k ∈ K l ∈ L k a k l × Δ k l , ∀ k ∈ K , l ∈ L k , ▶ Δ k l ⊢ N : m k . \forall k\in K,\ a_k=\sum_{l\in L_k}a_{kl},\qquad\Delta=\sum_{\substack{k\in K\\ l\in L_k}}a_{kl}\times\Delta_{kl},\qquad\forall k\in K,\ l\in L_k,\ \blacktriangleright\ \Delta_{kl}\vdash N:\mathbf{m}_k. ∀ k ∈ K , a k = l ∈ L k ∑ a k l , Δ = k ∈ K l ∈ L k ∑ a k l × Δ k l , ∀ k ∈ K , l ∈ L k , ▶ Δ k l ⊢ N : m k . In addition, the converse implication holds without any hypothesis on S \mathbf{S} S .
Proof. For the left-to-right implication, the hypothesis is obtained by the typing rule (!) with premises Δ i ⊢ N : σ i \Delta_i\vdash N:\sigma_i Δ i ⊢ N : σ i and coefficients c i c_i c i . Put X : = { σ i ∣ i ∈ I } ∪ ⋃ k ∈ K supp ( m k ) X:=\{\sigma_i\mid i\in I\}\cup\bigcup_{k\in K}\operatorname{supp}(\mathbf{m}_k) X := { σ i ∣ i ∈ I } ∪ ⋃ k ∈ K supp ( m k ) . Then
∀ σ ∈ X , ∑ k ∈ K a k × m k ( σ ) = ∑ i ∈ I σ i = σ c i , Δ = ∑ i ∈ I c i × Δ i . (1) \forall\sigma\in X,\quad\sum_{k\in K}a_k\times\mathbf{m}_k(\sigma)=\sum_{\substack{i\in I\\ \sigma_i=\sigma}}c_i,\qquad\Delta=\sum_{i\in I}c_i\times\Delta_i. \tag*{(1)} ∀ σ ∈ X , k ∈ K ∑ a k × m k ( σ ) = i ∈ I σ i = σ ∑ c i , Δ = i ∈ I ∑ c i × Δ i . (1)
Apply n n n -ary additive refinement (Lemma 3 (2)) to the first equality, for all σ ∈ X \sigma\in X σ ∈ X . There are coefficients e k i e_{ki} e k i such that
∀ σ ∈ X , k ∈ K , a k × m k ( σ ) = ∑ i ∈ I σ i = σ e k i , ∀ i ∈ I , c i = ∑ k ∈ K e k i . \forall\sigma\in X, k \in K,\ a_k \times m_k(\sigma) = \sum_{\substack{i \in I\\ \sigma_i=\sigma}} e_{ki}, \qquad\forall i \in I,\ c_i = \sum_{k \in K} e_{ki}. ∀ σ ∈ X , k ∈ K , a k × m k ( σ ) = i ∈ I σ i = σ ∑ e k i , ∀ i ∈ I , c i = k ∈ K ∑ e k i .
For each k ∈ K k \in K k ∈ K , apply simultaneous n n n -ary mixed refinement (Lemma 3 (3)) to the family of equations indexed by σ ∈ X \sigma\in X σ ∈ X , with fibres I σ : = { i ∈ I ∣ σ i = σ } I_\sigma:= \{i \in I \mid\sigma_i = \sigma\} I σ := { i ∈ I ∣ σ i = σ } . Since these fibres partition I I I , we index the resulting right coefficients by i i i alone, writing them b i k l b_{ikl} b ik l . There are finite sets L k L_k L k and coefficients a k l , b i k l a_{kl}, b_{ikl} a k l , b ik l such that for all k ∈ K k \in K k ∈ K ,
a k = ∑ l ∈ L k a k l , ∀ σ ∈ X , ∀ l ∈ L k , m k ( σ ) = ∑ i ∈ I σ i = σ b i k l , ∀ i ∈ I , e k i = ∑ l ∈ L k a k l × b i k l . a_k = \sum_{l \in L_k} a_{kl}, \qquad\forall\sigma\in X,\ \forall l \in L_k,\ m_k(\sigma) = \sum_{\substack{i \in I\\ \sigma_i=\sigma}} b_{ikl}, \qquad\forall i \in I,\ e_{ki} = \sum_{l \in L_k} a_{kl} \times b_{ikl}. a k = l ∈ L k ∑ a k l , ∀ σ ∈ X , ∀ l ∈ L k , m k ( σ ) = i ∈ I σ i = σ ∑ b ik l , ∀ i ∈ I , e k i = l ∈ L k ∑ a k l × b ik l .
Finally, put Δ k l : = ∑ i ∈ I b i k l × Δ i \Delta_{kl} := \sum_{i \in I} b_{ikl} \times\Delta_i Δ k l := ∑ i ∈ I b ik l × Δ i and form
[ ( Δ i ⊢ N : σ i ) : b i k l ] i ∈ I Δ k l ⊢ N : m k ( ! ) \frac{\left[(\Delta_i \vdash N : \sigma_i) : b_{ikl}\right]_{i \in I}}{\Delta_{kl} \vdash N : m_k}
\quad(!) Δ k l ⊢ N : m k [ ( Δ i ⊢ N : σ i ) : b ik l ] i ∈ I ( !)
Distributivity gives
∑ k , l a k l × Δ k l = ∑ i ∈ I ( ∑ k , l a k l × b i k l ) × Δ i = ∑ i ∈ I c i × Δ i = Δ . \sum_{k,l} a_{kl} \times\Delta_{kl} = \sum_{i \in I} \left(\sum_{k,l} a_{kl} \times b_{ikl}\right) \times\Delta_i = \sum_{i \in I} c_i \times\Delta_i = \Delta. k , l ∑ a k l × Δ k l = i ∈ I ∑ k , l ∑ a k l × b ik l × Δ i = i ∈ I ∑ c i × Δ i = Δ.
Conversely, each Δ k l ⊢ N : m k \Delta_{kl} \vdash N : m_k Δ k l ⊢ N : m k is obtained by the typing rule (!) with premises Θ k l i ⊢ N : τ k l i \Theta_{kli} \vdash N : \tau_{kli} Θ k l i ⊢ N : τ k l i and coefficients b i k l b_{ikl} b ik l , indexed by i ∈ I k l i \in I_{kl} i ∈ I k l . Flatten the promotions:
[ ( Θ k l i ⊢ N : τ k l i ) : a k l × b i k l ] k ∈ K , l ∈ L k , i ∈ I k l Δ ⊢ N : ∑ k ∈ K a k × m k ( ! ) \frac{\left[(\Theta_{kli} \vdash N : \tau_{kli}) : a_{kl} \times b_{ikl}\right]_{k \in K,l \in L_k,i \in I_{kl}}}{\Delta\vdash N : \sum_{k \in K} a_k \times m_k}
\quad(!) Δ ⊢ N : ∑ k ∈ K a k × m k [ ( Θ k l i ⊢ N : τ k l i ) : a k l × b ik l ] k ∈ K , l ∈ L k , i ∈ I k l ( !)
Subject Reduction and Expansion for IS
In this subsection we work in IS, for which we prove subject reduction and subject expansion, relying as usual on two substitution lemmas. While the latter holds under no additional condition, the former needs S to be a weak resource semiring – as made apparent in the results of the previous Section.
Lemma 14 (Forward Substitution). Assume that S S S is a weak resource semiring. If ▶ Γ , x : m ⊢ M : σ \blacktriangleright\ \Gamma, x : m \vdash M : \sigma ▶ Γ , x : m ⊢ M : σ and ▶ Δ ⊢ N : m \blacktriangleright\ \Delta\vdash N : m ▶ Δ ⊢ N : m , then ▶ Γ + Δ ⊢ M [ N / x ] : σ \blacktriangleright\ \Gamma+ \Delta\vdash M[N/x] : \sigma ▶ Γ + Δ ⊢ M [ N / x ] : σ . The same holds when the first hypothesis is a multi-type judgment.
Proof. By induction on the first hypothesis.
If the last rule is (ax) and M = x M = x M = x , then m = [ σ : 1 ] + m ′ m = [\sigma: 1] + m' m = [ σ : 1 ] + m ′ for some m ′ m' m ′ . By Lemma 12 , write Δ = Δ 0 + Δ 1 \Delta= \Delta_0 + \Delta_1 Δ = Δ 0 + Δ 1 with ▶ Δ 0 ⊢ N : [ σ : 1 ] \blacktriangleright\ \Delta_0 \vdash N : [\sigma: 1] ▶ Δ 0 ⊢ N : [ σ : 1 ] . By Lemma 11 , ▶ Δ 0 ⊢ N : σ \blacktriangleright\ \Delta_0 \vdash N : \sigma ▶ Δ 0 ⊢ N : σ . By Lemma 10 (1), i.e. weakening, we can conclude.
If the last rule is (ax) and M = y ≠ x M = y \ne x M = y = x , replace Γ + ( y : n ) , x : m \Gamma+ (y : n), x : m Γ + ( y : n ) , x : m with Γ + Δ + ( y : n ) \Gamma+ \Delta+ (y : n) Γ + Δ + ( y : n ) in the context of the rule.
If the last rule is (⊸ \multimap ⊸ i), σ = n ⊸ τ \sigma= n \multimap\tau σ = n ⊸ τ , and M = λ y . P M = \lambda y.P M = λ y . P (choosing y ∉ { x } ∪ fv ( N ) ∪ supp ( Δ ) y \notin\{x\} \cup\operatorname{fv}(N) \cup\operatorname{supp}(\Delta) y ∈ / { x } ∪ fv ( N ) ∪ supp ( Δ ) ), apply induction to the premise, then apply the rule again:
Γ , y : n , x : m ⊢ P : τ (I.H.) Γ + Δ , y : n ⊢ P [ N / x ] : τ ( ⊸ i ) Γ + Δ ⊢ λ y . P [ N / x ] : n ⊸ τ \begin{aligned}
\Gamma, y : n, x : m &\vdash P : \tau&& \text{(I.H.)}\\
\Gamma+ \Delta, y : n &\vdash P[N/x] : \tau&& (\multimap i)\\
\Gamma+ \Delta&\vdash\lambda y.P[N/x] : n \multimap\tau
\end{aligned} Γ , y : n , x : m Γ + Δ , y : n Γ + Δ ⊢ P : τ ⊢ P [ N / x ] : τ ⊢ λ y . P [ N / x ] : n ⊸ τ (I.H.) ( ⊸ i )
If the last rule is ( ⊸ e ) (\multimap e) ( ⊸ e ) and M = P Q M = P Q M = P Q , its premises have contexts Γ P , x : m P \Gamma_P, x : m_P Γ P , x : m P and Γ Q , x : m Q \Gamma_Q, x : m_Q Γ Q , x : m Q , where Γ = Γ P + Γ Q \Gamma= \Gamma_P + \Gamma_Q Γ = Γ P + Γ Q and m = m P + m Q m = m_P + m_Q m = m P + m Q . By Lemma 12 , write Δ = Δ P + Δ Q \Delta= \Delta_P + \Delta_Q Δ = Δ P + Δ Q with ▶ Δ P ⊢ N : m P \blacktriangleright\Delta_P \vdash N : m_P ▶ Δ P ⊢ N : m P and ▶ Δ Q ⊢ N : m Q \blacktriangleright\Delta_Q \vdash N : m_Q ▶ Δ Q ⊢ N : m Q . Apply induction and form
Γ P + Δ P ⊢ P [ N / x ] : n ⊸ σ Γ Q + Δ Q ⊢ Q [ N / x ] : n Γ + Δ ⊢ ( P Q ) [ N / x ] : σ ( ⊸ e ) \frac{\Gamma_P + \Delta_P \vdash P[N/x] : n \multimap\sigma\qquad\Gamma_Q + \Delta_Q \vdash Q[N/x] : n}{\Gamma+ \Delta\vdash(P Q)[N/x] : \sigma}\;(\multimap e) Γ + Δ ⊢ ( P Q ) [ N / x ] : σ Γ P + Δ P ⊢ P [ N / x ] : n ⊸ σ Γ Q + Δ Q ⊢ Q [ N / x ] : n ( ⊸ e )
[ ( Γ k , x : m k ⊢ M : τ k ) : a k ] k ∈ K Γ , x : m ⊢ M : n ( ! ) \frac{[(\Gamma_k, x : m_k \vdash M : \tau_k) : a_k]_{k\in K}}{\Gamma, x : m \vdash M : n}\;(!) Γ , x : m ⊢ M : n [( Γ k , x : m k ⊢ M : τ k ) : a k ] k ∈ K ( !)
where Γ = ∑ k ∈ K a k × Γ k \Gamma= \sum_{k\in K} a_k \times\Gamma_k Γ = ∑ k ∈ K a k × Γ k , m = ∑ k ∈ K a k × m k m = \sum_{k\in K} a_k \times m_k m = ∑ k ∈ K a k × m k , and n = [ τ k : a k ] k ∈ K n = [\tau_k : a_k]_{k\in K} n = [ τ k : a k ] k ∈ K , then by Lemma 13 , there are a k l a_{kl} a k l and Δ k l \Delta_{kl} Δ k l such that
∀ k ∈ K , a k = ∑ l ∈ L k a k l , Δ = ∑ k , l a k l × Δ k l , ∀ k ∈ K , l ∈ L k , ▶ Δ k l ⊢ N : m k . \forall k \in K,\ a_k = \sum_{l\in L_k} a_{kl}, \qquad\Delta= \sum_{k,l} a_{kl} \times\Delta_{kl}, \qquad\forall k \in K,l \in L_k,\ \blacktriangleright\Delta_{kl} \vdash N : m_k. ∀ k ∈ K , a k = l ∈ L k ∑ a k l , Δ = k , l ∑ a k l × Δ k l , ∀ k ∈ K , l ∈ L k , ▶ Δ k l ⊢ N : m k .
Apply induction to each premise ▶ Γ k , x : m k ⊢ M : τ k \blacktriangleright\Gamma_k, x : m_k \vdash M : \tau_k ▶ Γ k , x : m k ⊢ M : τ k , using ▶ Δ k l ⊢ N : m k \blacktriangleright\Delta_{kl} \vdash N : m_k ▶ Δ k l ⊢ N : m k as the second hypothesis, and form the rule (!) again:
[ ( Γ k + Δ k l ⊢ M [ N / x ] : τ k ) : a k l ] k ∈ K , l ∈ L k Γ + Δ ⊢ M [ N / x ] : n ( ! ) \frac{[(\Gamma_k + \Delta_{kl} \vdash M[N/x] : \tau_k) : a_{kl}]_{k\in K,l\in L_k}}{\Gamma+ \Delta\vdash M[N/x] : n}\;(!) Γ + Δ ⊢ M [ N / x ] : n [( Γ k + Δ k l ⊢ M [ N / x ] : τ k ) : a k l ] k ∈ K , l ∈ L k ( !)
since ∑ k , l a k l × ( Γ k + Δ k l ) = Γ + Δ \sum_{k,l} a_{kl} \times(\Gamma_k + \Delta_{kl}) = \Gamma+ \Delta ∑ k , l a k l × ( Γ k + Δ k l ) = Γ + Δ and [ τ k : a k l ] k , l = [ τ k : a k ] k [\tau_k : a_{kl}]_{k,l} = [\tau_k : a_k]_k [ τ k : a k l ] k , l = [ τ k : a k ] k .
□□
Lemma 15 (Backward Substitution). Let x ∉ fv ( N ) ∪ supp ( Γ ) x \notin\operatorname{fv}(N) \cup\operatorname{supp}(\Gamma) x ∈ / fv ( N ) ∪ supp ( Γ ) . If ▶ Γ ⊢ M [ N / x ] : σ \blacktriangleright\Gamma\vdash M[N/x] : \sigma ▶ Γ ⊢ M [ N / x ] : σ , then there are Γ M \Gamma_M Γ M , Γ N \Gamma_N Γ N and m m m such that
Γ = Γ M + Γ N , ▶ Γ M , x : m ⊢ M : σ , ▶ Γ N ⊢ N : m , \Gamma= \Gamma_M + \Gamma_N,\qquad\blacktriangleright\Gamma_M, x : m \vdash M : \sigma,\qquad\blacktriangleright\Gamma_N \vdash N : m, Γ = Γ M + Γ N , ▶ Γ M , x : m ⊢ M : σ , ▶ Γ N ⊢ N : m ,
with Γ M ( x ) = Γ N ( x ) = [ ] \Gamma_M(x) = \Gamma_N(x) = [] Γ M ( x ) = Γ N ( x ) = [ ] . The same holds for multi-type judgments.
Proof. By induction on the input derivation and case distinction on M M M .
If M = x M = x M = x and the conclusion has an ordinary type σ \sigma σ , take m = [ σ : 1 ] m = [\sigma: 1] m = [ σ : 1 ] , Γ M = ∅ \Gamma_M = \varnothing Γ M = ∅ , Γ N = Γ \Gamma_N = \Gamma Γ N = Γ , and form
x : [ σ : 1 ] ⊢ x : σ ( a x ) Γ ⊢ N : σ Γ ⊢ N : [ σ : 1 ] ( ! ) \frac{}{x : [\sigma: 1] \vdash x : \sigma}\;(\mathrm{ax})
\qquad
\frac{\Gamma\vdash N : \sigma}{\Gamma\vdash N : [\sigma: 1]}\;(!) x : [ σ : 1 ] ⊢ x : σ ( ax ) Γ ⊢ N : [ σ : 1 ] Γ ⊢ N : σ ( !)
If M = y ≠ x M = y \ne x M = y = x and the last rule is ( a x ) (\mathrm{ax}) ( ax ) , take Γ M = Γ \Gamma_M = \Gamma Γ M = Γ , Γ N = ∅ \Gamma_N = \varnothing Γ N = ∅ , m = [ ] m = [] m = [ ] , and use the nullary (!) rule to type N N N .
If M = λ y . P M = \lambda y.P M = λ y . P (choosing y ∉ { x } ∪ fv ( N ) y \notin\{x\} \cup\operatorname{fv}(N) y ∈ / { x } ∪ fv ( N ) ), the last rule is ( ⊸ i ) (\multimap i) ( ⊸ i ) , and σ = n ⊸ τ \sigma= n \multimap\tau σ = n ⊸ τ , apply induction to the premise ▶ Γ , y : n ⊢ P [ N / x ] : τ \blacktriangleright\Gamma, y : n \vdash P[N/x] : \tau ▶ Γ , y : n ⊢ P [ N / x ] : τ and obtain:
Γ = Γ P + Γ N n = n P + n N ▶ Γ P , y : n P , x : m ⊢ P : τ ▶ Γ N , y : n N ⊢ N : m . \Gamma= \Gamma_P + \Gamma_N \qquad n = n_P + n_N \qquad\blacktriangleright\Gamma_P, y : n_P, x : m \vdash P : \tau\qquad\blacktriangleright\Gamma_N, y : n_N \vdash N : m. Γ = Γ P + Γ N n = n P + n N ▶ Γ P , y : n P , x : m ⊢ P : τ ▶ Γ N , y : n N ⊢ N : m .
Apply respectively Lemma 10 (1) and Lemma 10 (2) to the derivations for P P P and N N N , obtaining ▶ Γ P , y : n , x : m ⊢ P : τ \blacktriangleright\Gamma_P, y : n, x : m \vdash P : \tau ▶ Γ P , y : n , x : m ⊢ P : τ and ▶ Γ N ⊢ N : m \blacktriangleright\Gamma_N \vdash N : m ▶ Γ N ⊢ N : m . Conclude by forming the rule ( ⊸ i ) (\multimap i) ( ⊸ i ) again.
Γ P ⊢ P [ N / x ] : n ⊸ σ Γ Q ⊢ Q [ N / x ] : n Γ ⊢ ( P Q ) [ N / x ] : σ ( ⊸ e ) , \frac{\Gamma_P \vdash P[N/x] : n \multimap\sigma\qquad\Gamma_Q \vdash Q[N/x] : n}{\Gamma\vdash(P Q)[N/x] : \sigma}\;(\multimap e), Γ ⊢ ( P Q ) [ N / x ] : σ Γ P ⊢ P [ N / x ] : n ⊸ σ Γ Q ⊢ Q [ N / x ] : n ( ⊸ e ) ,
first observe that ( Γ P + Γ Q ) ( x ) = Γ ( x ) = [ ] (\Gamma_P + \Gamma_Q)(x) = \Gamma(x) = [] ( Γ P + Γ Q ) ( x ) = Γ ( x ) = [ ] , so either by positivity (if S S S has it) or by Lemma 10 (2) we can assume that Γ P ( x ) = Γ Q ( x ) = [ ] \Gamma_P(x) = \Gamma_Q(x) = [] Γ P ( x ) = Γ Q ( x ) = [ ] . Induction gives
Γ P , x : m P ⊢ P : n ⊸ σ Γ Q , x : m Q ⊢ Q : n Γ P + Γ Q , x : m P + m Q ⊢ P Q : σ ( ⊸ e ) \frac{\Gamma_P, x : m_P \vdash P : n \multimap\sigma\qquad\Gamma_Q, x : m_Q \vdash Q : n}{\Gamma_P + \Gamma_Q, x : m_P + m_Q \vdash P Q : \sigma}\;(\multimap e) Γ P + Γ Q , x : m P + m Q ⊢ P Q : σ Γ P , x : m P ⊢ P : n ⊸ σ Γ Q , x : m Q ⊢ Q : n ( ⊸ e )
and ▶ Γ N , R ⊢ N : m R \blacktriangleright\Gamma_{N,R} \vdash N : m_R ▶ Γ N , R ⊢ N : m R for R ∈ { P , Q } R \in\{P,Q\} R ∈ { P , Q } , with Γ = Γ P + Γ Q + Γ N , P + Γ N , Q \Gamma= \Gamma_P + \Gamma_Q + \Gamma_{N,P} + \Gamma_{N,Q} Γ = Γ P + Γ Q + Γ N , P + Γ N , Q . The converse implication of Lemma 12 gives ▶ Γ N , P + Γ N , Q ⊢ N : m P + m Q \blacktriangleright\Gamma_{N,P} + \Gamma_{N,Q} \vdash N : m_P + m_Q ▶ Γ N , P + Γ N , Q ⊢ N : m P + m Q .
[ ( Γ i ⊢ M [ N / x ] : τ i ) : c i ] i ∈ I Γ ⊢ M [ N / x ] : n \frac{[(\Gamma_i \vdash M[N/x] : \tau_i) : c_i]_{i\in I}}{\Gamma\vdash M[N/x] : n} Γ ⊢ M [ N / x ] : n [( Γ i ⊢ M [ N / x ] : τ i ) : c i ] i ∈ I
where Γ = ∑ i ∈ I c i × Γ i \Gamma= \sum_{i\in I} c_i \times\Gamma_i Γ = ∑ i ∈ I c i × Γ i and n = [ τ i : c i ] i ∈ I n = [\tau_i : c_i]_{i\in I} n = [ τ i : c i ] i ∈ I , then first Lemma 10 (2) in each hypothesis as in the previous case. Then by induction, for all i ∈ I i \in I i ∈ I , Γ i = Γ M , i + Γ N , i \Gamma_i = \Gamma_{M,i} + \Gamma_{N,i} Γ i = Γ M , i + Γ N , i with ▶ Γ M , i , x : m i ⊢ M : τ i \blacktriangleright\Gamma_{M,i}, x : m_i \vdash M : \tau_i ▶ Γ M , i , x : m i ⊢ M : τ i , and ▶ Γ N , i ⊢ N : m i \blacktriangleright\Gamma_{N,i} \vdash N : m_i ▶ Γ N , i ⊢ N : m i . Put
Γ M : = ∑ i ∈ I c i × Γ M , i , Γ N : = ∑ i ∈ I c i × Γ N , i , m : = ∑ i ∈ I c i × m i . \Gamma_M := \sum_{i\in I} c_i \times\Gamma_{M,i}, \qquad\Gamma_N := \sum_{i\in I} c_i \times\Gamma_{N,i}, \qquad m := \sum_{i\in I} c_i \times m_i. Γ M := i ∈ I ∑ c i × Γ M , i , Γ N := i ∈ I ∑ c i × Γ N , i , m := i ∈ I ∑ c i × m i .
The first desired derivation is form using the rule (!) again:
[ ( Γ M , i , x : m i ⊢ M : τ i ) : c i ] i ∈ I Γ M , x : m ⊢ M : [ τ i : c i ] i ∈ I \frac{[(\Gamma_{M,i}, x : m_i \vdash M : \tau_i) : c_i]_{i\in I}}{\Gamma_M, x : m \vdash M : [\tau_i : c_i]_{i\in I}} Γ M , x : m ⊢ M : [ τ i : c i ] i ∈ I [( Γ M , i , x : m i ⊢ M : τ i ) : c i ] i ∈ I
The second one can be obtained using the converse implication of Lemma 13 , giving ▶ Γ N ⊢ N : m \blacktriangleright\Gamma_N \vdash N : m ▶ Γ N ⊢ N : m . Distributivity gives Γ M + Γ N = ∑ i ∈ I c i × Γ i = Γ \Gamma_M + \Gamma_N = \sum_{i\in I} c_i \times\Gamma_i = \Gamma Γ M + Γ N = ∑ i ∈ I c i × Γ i = Γ .
Theorem 16 (Subject Reduction and Subject Expansion). For all weak resource semiring S \mathbf{S} S , I S \mathbf{I}_{\mathbf{S}} I S enjoys subject reduction and subject expansion, i.e., for all M → β N M \to_\beta N M → β N , Γ \Gamma Γ and σ \sigma σ ,
▶ Γ ⊢ M : σ i f f ▶ Γ ⊢ N : σ . \blacktriangleright\Gamma\vdash M : \sigma\quad\mathit{iff} \quad\blacktriangleright\Gamma\vdash N : \sigma. ▶ Γ ⊢ M : σ iff ▶ Γ ⊢ N : σ . The same holds for multi-type judgments.
Proof. By induction on M → β N M \to_\beta N M → β N . In the base case, i.e. ( λ x . P ) Q → β P [ Q / x ] (\lambda x.P)Q \to_\beta P[Q/x] ( λ x . P ) Q → β P [ Q / x ] , apply Lemmas 14 and 15. The induction cases are straightforward.
In particular I 2 \mathbf{I}_2 I 2 , I N \mathbf{I}_N I N and I T \mathbf{I}_T I T enjoy subject reduction and expansion.
Extension to the Relevant System
Weak discreteness does not suffice for relevant subject reduction. For example, using the semiring 2 2 2 , put τ 0 = [ ] ⊸ α \tau_0 = [] \multimap\alpha τ 0 = [ ] ⊸ α , τ 1 = [ α : 1 ] ⊸ α \tau_1 = [\alpha: 1] \multimap\alpha τ 1 = [ α : 1 ] ⊸ α , Δ 0 = y : [ τ 0 : 1 ] \Delta_0 = y : [\tau_0 : 1] Δ 0 = y : [ τ 0 : 1 ] and Δ 1 = y : [ τ 1 : 1 ] , z : [ α : 1 ] \Delta_1 = y : [\tau_1 : 1], z : [\alpha: 1] Δ 1 = y : [ τ 1 : 1 ] , z : [ α : 1 ] . We have ▶ Δ i ⊢ y z : α \blacktriangleright\Delta_i \vdash yz : \alpha ▶ Δ i ⊢ y z : α for i = 0 , 1 i = 0, 1 i = 0 , 1 , hence
∅ ⊢ λ x . x : [ α : 1 ] ⊸ α Δ 0 ⊢ y z : α Δ 1 ⊢ y z : α Δ 0 + Δ 1 ⊢ y z : [ α : 1 ] Δ 0 + Δ 1 ⊢ ( λ x . x ) ( y z ) : α \frac{\varnothing\vdash\lambda x.x : [\alpha: 1] \multimap\alpha\qquad
\frac{\Delta_0 \vdash yz : \alpha\qquad\Delta_1 \vdash yz : \alpha}
{\Delta_0 + \Delta_1 \vdash yz : [\alpha: 1]}}
{\Delta_0 + \Delta_1 \vdash(\lambda x.x)(yz) : \alpha} Δ 0 + Δ 1 ⊢ ( λ x . x ) ( y z ) : α ∅ ⊢ λ x . x : [ α : 1 ] ⊸ α Δ 0 + Δ 1 ⊢ y z : [ α : 1 ] Δ 0 ⊢ y z : α Δ 1 ⊢ y z : α
But Δ 0 + Δ 1 ⊢ y z : α \Delta_0 + \Delta_1 \vdash yz : \alpha Δ 0 + Δ 1 ⊢ y z : α is not derivable: the single occurrence of the head variable uses only one of τ 0 \tau_0 τ 0 , τ 1 \tau_1 τ 1 , and the argument z z z cannot consume the other entry at y y y . To remove this obstruction, we need to consider a strong resource semiring .
Theorem 17. For all strong resource semiring S \mathbf{S} S , the relevant system r I S \mathbf{rI}_{\mathbf{S}} rI S enjoys subject reduction and subject expansion.
Proof. The proof is as for Theorem 16 , except for the following changes.
In the proof of forward substitution (Lemma 14 ):
For the case M = y ≠ x M = y \ne x M = y = x , the rule (rax) implies that m = [ ] m = [] m = [ ] , and the 0-ary instance of Lemma 12 gives Δ = ∅ \Delta= \varnothing Δ = ∅ , so that we can just keep the initial derivation untouched.
In the proof of backward substitution (Lemma 15):
In particular r I N \mathbf{rI}_N rI N enjoys subject reduction and expansion.
An Extension to Infinitary Types
Locally Finite Sums and Multisets
Definition 18 (Topological Semiring). A topological semiring is a semiring S \mathbf{S} S equipped with a Hausdorff topology making both addition and multiplication continuous.
We give N \mathbb{N} N and 2 \mathbf{2} 2 the discrete topology. On T \mathbf{T} T we consider the topology induced by the ultrametric
d T ( a , b ) : = { 0 if a = b , 2 − min ( a , b ) otherwise. d_{\mathbf{T}}(a,b) :=
\begin{cases}
0 & \text{if } a=b,\\
2^{-\min(a,b)} & \text{otherwise.}
\end{cases} d T ( a , b ) := { 0 2 − m i n ( a , b ) if a = b , otherwise.
We use the topology on S \mathbf{S} S to accommodate infinite sums in a controlled way, namely by imposing a condition of local finiteness .
Definition 19 (Locally Finite Families and Sums). A family ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I in a topological semiring S \mathbf{S} S is locally finite if for all neighbourhood U U U of 0 0 0 , the set { i ∈ I ∣ a i ∉ U } \{i\in I \mid a_i\notin U\} { i ∈ I ∣ a i ∈ / U } is finite. Its sum, when it exists, is
∑ i ∈ I a i : = lim F ⊆ f I ∑ i ∈ F a i . \sum_{i\in I} a_i := \lim_{F\subseteq_{\mathrm{f}} I}\sum_{i\in F}a_i. i ∈ I ∑ a i := F ⊆ f I lim i ∈ F ∑ a i . where F ⊆ f I F\subseteq_{\mathrm{f}} I F ⊆ f I means that F F F is a finite subset of I I I , hence the limit ranges over finite subsets directed by inclusion. We say that S \mathbf{S} S admits locally finite sums if:
every locally finite family has a sum;
for all locally finite family ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I and partition I = ⨆ j ∈ J I j I=\bigsqcup_{j\in J}I_j I = ⨆ j ∈ J I j , the family ( ∑ i ∈ I j a i ) j ∈ J \left(\sum_{i\in I_j}a_i\right)_{j\in J} ( ∑ i ∈ I j a i ) j ∈ J is locally finite and ∑ i ∈ I a i = ∑ j ∈ J ∑ i ∈ I j a i \sum_{i\in I}a_i=\sum_{j\in J}\sum_{i\in I_j}a_i ∑ i ∈ I a i = ∑ j ∈ J ∑ i ∈ I j a i ;
if ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I and each ( b i j ) j ∈ J (b_{ij})_{j\in J} ( b ij ) j ∈ J are locally finite, then ( a i × b i j ) i ∈ I , j ∈ J (a_i\times b_{ij})_{i\in I,j\in J} ( a i × b ij ) i ∈ I , j ∈ J is locally finite.
Hausdorffness gives uniqueness of the sum of a family: two distinct limits would have disjoint neighbourhoods, whereas convergence would force every sufficiently late finite partial sum to belong to both.
A finitely supported family is locally finite; the converse holds for the discrete topology. In particular, this construction is of no consequence for N \mathbb{N} N and 2 \mathbf{2} 2 .
Continuity of the semiring operations and Item 3 in the above Definition give distributivity over locally finite sums: a × ∑ i b i = ∑ i a × b i a\times\sum_i b_i=\sum_i a\times b_i a × ∑ i b i = ∑ i a × b i (and similarly on the right side).
Definition 20 (Locally Finite Resource Semiring). Given a semiring S \mathbf{S} S admitting locally finite sums, consider the following conditions:
Locally finite additive refinement: For all locally finite families ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I , ( b j ) j ∈ J (b_j)_{j\in J} ( b j ) j ∈ J , and labellings λ : I → X \lambda:I\to X λ : I → X , μ : J → X \mu:J\to X μ : J → X ,
( ∀ x ∈ X , ∑ λ ( i ) = x i ∈ I a i = ∑ μ ( j ) = x j ∈ J b j ) ⟹ ∃ ( c i j ) i ∈ I , j ∈ J locally finite , \left(
\forall x\in X,\ \sum_{\lambda(i)=x\atop i\in I}a_i=\sum_{\mu(j)=x\atop j\in J}b_j
\right)
\Longrightarrow\exists(c_{ij})_{i\in I,j\in J}\text{ locally finite}, ∀ x ∈ X , i ∈ I λ ( i ) = x ∑ a i = j ∈ J μ ( j ) = x ∑ b j ⟹ ∃ ( c ij ) i ∈ I , j ∈ J locally finite , ∀ i ∈ I , a i = ∑ j ∈ J c i j , ∀ j ∈ J , b j = ∑ i ∈ I c i j , ∀ i ∈ I , j ∈ J , λ ( i ) ≠ μ ( j ) ⟹ c i j = 0. \forall i\in I,\ a_i=\sum_{j\in J}c_{ij},\quad
\forall j\in J,\ b_j=\sum_{i\in I}c_{ij},\quad
\forall i\in I,j\in J,\ \lambda(i)\ne\mu(j)\Longrightarrow c_{ij}=0. ∀ i ∈ I , a i = j ∈ J ∑ c ij , ∀ j ∈ J , b j = i ∈ I ∑ c ij , ∀ i ∈ I , j ∈ J , λ ( i ) = μ ( j ) ⟹ c ij = 0.
Simultaneous locally finite mixed refinement: For all locally finite families ( a k ) k ∈ K (a_k)_{k\in K} ( a k ) k ∈ K , ( b x k ) x ∈ X (b_{xk})_{x\in X} ( b x k ) x ∈ X for every k ∈ K k\in K k ∈ K , and ( c i ) i ∈ I (c_i)_{i\in I} ( c i ) i ∈ I , and for all labelling λ : I → X \lambda:I\to X λ : I → X ,
( ∀ x ∈ X , ∑ k ∈ K a k × b x k = ∑ i ∈ I λ ( i ) = x c i ) ⟹ \left(\forall x\in X,\ \sum_{k\in K}a_k\times b_{xk}=\sum_{\substack{i\in I\\\lambda(i)=x}}c_i\right)\Longrightarrow ∀ x ∈ X , k ∈ K ∑ a k × b x k = i ∈ I λ ( i ) = x ∑ c i ⟹
∃ ( L k ) k ∈ K , ∃ ( a k l ) k ∈ K , l ∈ L k locally finite , ∃ ( b i k l ) i ∈ I , k ∈ K , l ∈ L k such that ( b i k l ) i ∈ I is locally finite for all k ∈ K and l ∈ L k , \exists(L_k)_{k\in K},\quad
\exists(a_{kl})_{k\in K,l\in L_k}\text{ locally finite},\quad
\exists(b_{ikl})_{i\in I,k\in K,l\in L_k}\text{ such that }(b_{ikl})_{i\in I}\text{ is locally finite for all }k\in K\text{ and }l\in L_k, ∃ ( L k ) k ∈ K , ∃ ( a k l ) k ∈ K , l ∈ L k locally finite , ∃ ( b ik l ) i ∈ I , k ∈ K , l ∈ L k such that ( b ik l ) i ∈ I is locally finite for all k ∈ K and l ∈ L k ,
∀ k ∈ K , a k = ∑ l ∈ L k a k l , ∀ x ∈ X , k ∈ K , l ∈ L k , b x k = ∑ i ∈ I λ ( i ) = x b i k l , \forall k\in K,\ a_k=\sum_{l\in L_k}a_{kl},\qquad
\forall x\in X,k\in K,l\in L_k,\ b_{xk}=\sum_{\substack{i\in I\\\lambda(i)=x}}b_{ikl}, ∀ k ∈ K , a k = l ∈ L k ∑ a k l , ∀ x ∈ X , k ∈ K , l ∈ L k , b x k = i ∈ I λ ( i ) = x ∑ b ik l ,
∀ i ∈ I , c i = ∑ k ∈ K l ∈ L k a k l × b i k l . \forall i\in I,\ c_i=\sum_{\substack{k\in K\\l\in L_k}}a_{kl}\times b_{ikl}. ∀ i ∈ I , c i = k ∈ K l ∈ L k ∑ a k l × b ik l .
Then S is said to be a (weak) locally finite resource semiring whenever it enjoys locally finite (weak) discreteness, locally finite additive refinement, and simultaneous locally finite mixed refinement.
In general, these locally finite axioms do not imply the finite ones from Definition 2 and Lemma 3 : under the hypotheses of finite mixed refinement, locally finite mixed refinement does not always produce a finite refining family. We will build an example in Remark 42. Nonetheless, when S is equipped with the discrete topology, the finite and locally finite definitions coincide again. In particular, every (weak) resource semiring equipped with the discrete topology is a (weak) locally finite resource semiring. This is the topology we use for N \mathbb{N} N and 2 \mathbf{2} 2 .
Observe that in a weak locally finite resource semiring, positivity and absence of zero divisors are consequences of additive and mixed refinement, respectively. One can actually get a locally finite version of the former, namely ∑ i a i = 0 ⟹ ∀ i , a i = 0 \sum_i a_i=0\Longrightarrow\forall i,\ a_i=0 ∑ i a i = 0 ⟹ ∀ i , a i = 0 , by applying additive refinement to the empty family.
Lemma 21. T is a weak locally finite resource semiring .
Proof. A neighbourhood basis of ∞ \infty ∞ is U d : = { ∞ } ∪ { n ∈ N ∣ n > d } U_d:=\{\infty\}\cup\{n\in\mathbb{N}\mid n>d\} U d := { ∞ } ∪ { n ∈ N ∣ n > d } . Thus ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I is locally finite iff { i ∈ I ∣ a i ≤ d } \{i\in I\mid a_i\le d\} { i ∈ I ∣ a i ≤ d } is finite for every d d d . Its sum is min i ∈ I a i \min_{i\in I}a_i min i ∈ I a i . Using these characterisations, checking that the requirements of Definitions 19 and 20 hold are straightforward algebraic manipulations.
Definition 22 (Locally Finite S-Multisets). An S-multiset m : X → S \mathsf{m}:X\to S m : X → S is locally finite if, for all neighbourhood U U U of 0, the set { x ∈ X ∣ m ( x ) ∉ U } \{x\in X\mid\mathsf{m}(x)\notin U\} { x ∈ X ∣ m ( x ) ∈ / U } is finite. We denote the set of locally finite S-multisets by M S l f ( X ) \mathcal{M}^{\mathrm{lf}}_S(X) M S lf ( X ) . Given a family ( x i ) i ∈ I (x_i)_{i\in I} ( x i ) i ∈ I of elements of X X X and a locally finite family ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I of coefficients, we write [ x i : a i ] i ∈ I [x_i:a_i]_{i\in I} [ x i : a i ] i ∈ I for the S-multiset m : x ↦ ∑ i ∈ I , x i = x a i \mathsf{m}:x\mapsto\sum_{i\in I,x_i=x}a_i m : x ↦ ∑ i ∈ I , x i = x a i .
Only locally finite multisets occur in the following: we do not consider unrestricted maps X → S X\to S X → S . For N \mathbb{N} N and 2 \mathbf{2} 2 , local finiteness and finiteness coincide, so that M N f ( X ) \mathcal{M}^{\mathrm{f}}_{\mathbb{N}}(X) M N f ( X ) and M N l f ( X ) \mathcal{M}^{\mathrm{lf}}_{\mathbb{N}}(X) M N lf ( X ) (resp. M 2 f ( X ) \mathcal{M}^{\mathrm{f}}_{\mathbf{2}}(X) M 2 f ( X ) and M 2 l f ( X ) ) \mathcal{M}^{\mathrm{lf}}_{\mathbf{2}}(X)) M 2 lf ( X )) are both equal to the set of finite multisets (resp. finite sets) of elements of X X X . For T, a map m : X → T \mathsf{m}:X\to T m : X → T is locally finite whenever
∀ d ∈ N , { x ∈ X ∣ m ( x ) ≤ d } is finite. \forall d\in\mathbb{N},\qquad\{x\in X\mid\mathsf{m}(x)\le d\}\text{ is finite.} ∀ d ∈ N , { x ∈ X ∣ m ( x ) ≤ d } is finite.
If S admits locally finite sums, the pointwise sum and external product from Definition 6 preserve local finiteness; so do weighted sums ∑ i ∈ I a i × m i \sum_{i\in I}a_i\times m_i ∑ i ∈ I a i × m i with ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I locally finite.
Locally Finite Intersection Types
We now allow types to be infinite in two different directions:
the syntax tree of the types may be infinitely deep, i.e. coinductive (which is not the case for standard intersection types, but has already been considered in the literature [26 , 27 , 10 ] ): this kind of infinity is controlled by a mechanism inspired by guarded recursion, namely, coinductive recursion is allowed in an element σ \sigma σ of an S-multiset of types m whenever its grade m ( σ ) \mathrm{m}(\sigma) m ( σ ) is “guarding”, which motivates the following Definition.
Definition 23 (Guarding Set). A guarding set of S is a subset G ⊆ S G \subseteq\mathbf{S} G ⊆ S such that, for all a , b ∈ S a,b \in\mathbf{S} a , b ∈ S ,
0 ∈ G , 1 ∉ G , a + b ∈ G ⟺ a , b ∈ G , a × b ∈ G ⟺ a ∈ G or b ∈ G . 0 \in G,\qquad1 \notin G,\qquad a+b \in G \Longleftrightarrow a,b \in G,\qquad a \times b \in G \Longleftrightarrow a \in G \text{ or } b \in G. 0 ∈ G , 1 ∈ / G , a + b ∈ G ⟺ a , b ∈ G , a × b ∈ G ⟺ a ∈ G or b ∈ G .
Equivalently, G = γ − 1 ( { 0 } ) G = \gamma^{-1}(\{0\}) G = γ − 1 ({ 0 }) for a unital semiring morphism γ : S → 2 \gamma: \mathbf{S} \to\mathbf{2} γ : S → 2 ; this morphism is uniquely determined by G G G . We additionally assume that γ \gamma γ is continuous, or equivalently that G G G is clopen.
We take G = { 0 } G = \{0\} G = { 0 } for N \mathbf{N} N and 2 \mathbf{2} 2 ; more generally we can do so for any resource semiring equipped with the discrete topology. For T \mathbf{T} T we take G = { 1 , 2 , … , ∞ } G = \{1,2,\ldots,\infty\} G = { 1 , 2 , … , ∞ } .
Definition 24 (Locally Finite S-Intersection Types). Let S be a semiring admitting locally finite sums, equipped with a guarding set G G G , and let A \mathcal{A} A be a countable set of atoms. The sets I S l f \mathcal{I}^{\mathrm{lf}}_{\mathbf{S}} I S lf of locally finite S-intersection types and ! I S l f ⊂ M S l f ( I S l f ) !\mathcal{I}^{\mathrm{lf}}_{\mathbf{S}} \subset\mathcal{M}^{\mathrm{lf}}_{\mathbf{S}}(\mathcal{I}^{\mathrm{lf}}_{\mathbf{S}}) ! I S lf ⊂ M S lf ( I S lf ) of locally finite S-intersection multi-types are defined by mutual induction and coinduction by the following system of formation rules:
α ∈ A α ∈ I S l f ( A ) m ∈ ! I S l f τ ∈ I S l f m ⊸ τ ∈ I S l f ( ⊸ ) \frac{\alpha\in\mathcal{A}}{\alpha\in\mathcal{I}^{\mathrm{lf}}_{\mathbf{S}}}\;(\mathcal{A})
\qquad
\frac{\mathrm{m} \in!\mathcal{I}^{\mathrm{lf}}_{\mathbf{S}}\qquad\tau\in\mathcal{I}^{\mathrm{lf}}_{\mathbf{S}}}{\mathrm{m} \multimap\tau\in\mathcal{I}^{\mathrm{lf}}_{\mathbf{S}}}\;(\multimap) α ∈ I S lf α ∈ A ( A ) m ⊸ τ ∈ I S lf m ∈ ! I S lf τ ∈ I S lf ( ⊸ )
[ ( σ i ∈ a i I S l f ) : a i ] i ∈ I [ σ i : a i ] i ∈ I ∈ ! I S l f ( ! ) σ ∈ I S l f a ∈ G σ ∈ a I S l f ( c o i n d ) σ ∈ I S l f σ ∈ a I S l f ( i n d ) \frac{\left[(\sigma_i \in_{a_i} \mathcal{I}^{\mathrm{lf}}_{\mathbf{S}}) : a_i\right]_{i\in I}}{\left[\sigma_i : a_i\right]_{i\in I} \in!\mathcal{I}^{\mathrm{lf}}_{\mathbf{S}}}\;(!)
\qquad
\frac{\sigma\in\mathcal{I}^{\mathrm{lf}}_{\mathbf{S}}\qquad a \in G}{\sigma\in_a \mathcal{I}^{\mathrm{lf}}_{\mathbf{S}}}\;(\mathrm{coind})
\qquad
\frac{\sigma\in\mathcal{I}^{\mathrm{lf}}_{\mathbf{S}}}{\sigma\in_a \mathcal{I}^{\mathrm{lf}}_{\mathbf{S}}}\;(\mathrm{ind}) [ σ i : a i ] i ∈ I ∈ ! I S lf [ ( σ i ∈ a i I S lf ) : a i ] i ∈ I ( !) σ ∈ a I S lf σ ∈ I S lf a ∈ G ( coind ) σ ∈ a I S lf σ ∈ I S lf ( ind )
where single-bar rules are treated inductively whereas double-bar rules are treated coinductively: concretely, every infinite branch must traverse infinitely many instances of (coind). Notice again that the formation rule (!) has a (locally finite) S-multiset of hypotheses.
Typing judgements keep the same shape as in the finite system, with contexts being finitely supported maps V → ! I S l f \mathcal{V} \to!\mathcal{I}^{\mathrm{lf}}_{\mathbf{S}} V → ! I S lf .
Definition 25 (Typing). A λ \lambda λ -term M M M is typable in I S l f \mathcal{I}^{\mathrm{lf}}_{\mathbf{S}} I S lf whenever there is a derivation D \mathcal{D} D with conclusion Γ ⊢ M : σ \Gamma\vdash M : \sigma Γ ⊢ M : σ in the following (inductive) system of typing rules:
Γ + x : [ σ : 1 ] ⊢ x : σ ( a x ) Γ , x : m ⊢ M : τ Γ ⊢ λ x . M : m ⊸ τ ( ⊸ i ) \frac{}{\Gamma+ x : [\sigma: 1] \vdash x : \sigma}\;(\mathrm{ax})
\qquad
\frac{\Gamma, x : \mathrm{m} \vdash M : \tau}{\Gamma\vdash\lambda x.M : \mathrm{m} \multimap\tau}\;(\multimap_i) Γ + x : [ σ : 1 ] ⊢ x : σ ( ax ) Γ ⊢ λ x . M : m ⊸ τ Γ , x : m ⊢ M : τ ( ⊸ i )
Γ ⊢ M : m ⊸ τ Γ ′ ⊢ N : m Γ + Γ ′ ⊢ M N : τ ( ⊸ e ) [ ( Γ i ⊢ N : σ i ) : a i ] i ∈ I ∑ i ∈ I a i × Γ i ⊢ N : [ σ i : a i ] i ∈ I ( ! ) \frac{\Gamma\vdash M : \mathrm{m} \multimap\tau\qquad\Gamma' \vdash N : \mathrm{m}}{\Gamma+ \Gamma' \vdash MN : \tau}\;(\multimap_e)
\qquad
\frac{\left[(\Gamma_i \vdash N : \sigma_i) : a_i\right]_{i\in I}}{\sum_{i\in I} a_i \times\Gamma_i \vdash N : [\sigma_i : a_i]_{i\in I}}\;(!) Γ + Γ ′ ⊢ M N : τ Γ ⊢ M : m ⊸ τ Γ ′ ⊢ N : m ( ⊸ e ) ∑ i ∈ I a i × Γ i ⊢ N : [ σ i : a i ] i ∈ I [ ( Γ i ⊢ N : σ i ) : a i ] i ∈ I ( !)
for some context Γ \Gamma Γ and S-intersection type σ \sigma σ . We then write D ▶ Γ ⊢ M : σ \mathcal{D} \blacktriangleright\Gamma\vdash M : \sigma D ▶ Γ ⊢ M : σ , and simply ▶ Γ ⊢ M : σ \blacktriangleright\Gamma\vdash M : \sigma ▶ Γ ⊢ M : σ to say that such a D \mathcal{D} D exists.
A look at this typing system motivates our restriction to guarded corecursive types: removing the guard makes the typing unsound in general. For instance in I 2 l f \mathcal{I}^{\mathrm{lf}}_2 I 2 lf , the unguarded definition τ : = [ τ : 1 ] ⊸ α \tau:= [\tau: 1] \multimap\alpha τ := [ τ : 1 ] ⊸ α makes λ x . x x \lambda x.xx λ x . xx typable at τ \tau τ and hence makes Ω : = ( λ x . x x ) ( λ x . x x ) \Omega:= (\lambda x.xx)(\lambda x.xx) Ω := ( λ x . xx ) ( λ x . xx ) typable at α \alpha α .
The relevant system r l S l f \mathrm{rl}^{\mathrm{lf}}_{\mathbf{S}} rl S lf is obtained by replacing (ax) with (rax), as in the finite system. The weakening and relevance properties of Lemma 10 extend to these systems, by the same proofs.
The full system I T l f \mathcal{I}^{\mathrm{lf}}_{\mathbf{T}} I T lf is the tropical intersection type system that we previously studied [10 ] .
Theorem 26. For all weak locally finite resource semiring S \mathbf{S} S , the full system I S l f \mathcal{I}_{\mathbf{S}}^{\mathrm{lf}} I S lf enjoys subject reduction and subject expansion.
Proof. We extend the three lemmas of § 2.1 as follows.
In Lemma 12 , keep J J J finite. In the decomposition of the last rule (!), the index set I I I becomes infinite, with a locally finite family ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I . The family ( m j ( σ ) ) ( j , σ ) ∈ J × I S l f (m_j(\sigma))_{(j,\sigma)\in J\times\mathcal{I}_{\mathbf{S}}^{\mathrm{lf}}} ( m j ( σ ) ) ( j , σ ) ∈ J × I S lf is locally finite by Definition 22. Apply locally finite additive refinement to these two families, with labellings
λ : I → I S l f , i ↦ σ i , μ : J × I S l f → I S l f , ( j , σ ) ↦ σ . \lambda: I \to\mathcal{I}_{\mathbf{S}}^{\mathrm{lf}},\ i \mapsto\sigma_i,\qquad\mu: J \times\mathcal{I}_{\mathbf{S}}^{\mathrm{lf}} \to\mathcal{I}_{\mathbf{S}}^{\mathrm{lf}},\ (j,\sigma) \mapsto\sigma. λ : I → I S lf , i ↦ σ i , μ : J × I S lf → I S lf , ( j , σ ) ↦ σ .
The resulting c i , ( j , σ ) c_{i,(j,\sigma)} c i , ( j , σ ) are equal to 0 0 0 unless σ = σ i \sigma=\sigma_i σ = σ i ; put c i j : = c i , ( j , σ i ) c_{ij}:=c_{i,(j,\sigma_i)} c ij := c i , ( j , σ i ) , which defines a locally finite family.
In Lemma 13 , take ( a k ) k ∈ K (a_k)_{k\in K} ( a k ) k ∈ K locally finite and each m k m_k m k locally finite. Write the given rule (!) with locally finite coefficients ( c i ) i ∈ I (c_i)_{i\in I} ( c i ) i ∈ I and premises Δ i ⊢ N : σ i \Delta_i\vdash N:\sigma_i Δ i ⊢ N : σ i . Put X : = I S l f X:=\mathcal{I}_{\mathbf{S}}^{\mathrm{lf}} X := I S lf and λ : I → X \lambda:I\to X λ : I → X , i ↦ σ i i\mapsto\sigma_i i ↦ σ i ; observe that ( a k ) k ∈ K (a_k)_{k\in K} ( a k ) k ∈ K , each ( m k ( σ ) ) σ ∈ X (m_k(\sigma))_{\sigma\in X} ( m k ( σ ) ) σ ∈ X , and ( c i ) i ∈ I (c_i)_{i\in I} ( c i ) i ∈ I are locally finite families, and that
∀ σ ∈ X , ∑ k ∈ K a k × m k ( σ ) = ∑ i ∈ I λ ( i ) = σ c i . \forall\sigma\in X,\quad\sum_{k\in K}a_k\times m_k(\sigma)=\sum_{\substack{i\in I\\\lambda(i)=\sigma}}c_i. ∀ σ ∈ X , k ∈ K ∑ a k × m k ( σ ) = i ∈ I λ ( i ) = σ ∑ c i .
Apply simultaneous locally finite mixed refinement. It gives ( L k ) k ∈ K (L_k)_{k\in K} ( L k ) k ∈ K , a locally finite family ( a k l ) k ∈ K , l ∈ L k (a_{kl})_{k\in K,l\in L_k} ( a k l ) k ∈ K , l ∈ L k , and families ( b i k l ) i ∈ I (b_{ikl})_{i\in I} ( b ik l ) i ∈ I locally finite for every k , l k,l k , l , with
∀ k , a k = ∑ l ∈ L k a k l , ∀ σ , k , ∀ l ∈ L k , m k ( σ ) = ∑ i ∈ I σ i = σ b i k l , ∀ i , c i = ∑ k , l a k l × b i k l . \forall k,\quad a_k=\sum_{l\in L_k}a_{kl},\qquad\forall\sigma,k,\ \forall l\in L_k,\quad m_k(\sigma)=\sum_{\substack{i\in I\\\sigma_i=\sigma}}b_{ikl},\qquad\forall i,\quad c_i=\sum_{k,l}a_{kl}\times b_{ikl}. ∀ k , a k = l ∈ L k ∑ a k l , ∀ σ , k , ∀ l ∈ L k , m k ( σ ) = i ∈ I σ i = σ ∑ b ik l , ∀ i , c i = k , l ∑ a k l × b ik l .
The conclusion of the proof is as in the finite case.
Once these adaptions are performed, the proof of forward and backward substitution are exactly the same; all flattenings and regroupings in these proofs are justified by Definition 19 ; positivity and absence of zero divisors in S \mathbf{S} S are needed to justify that forward and backward substitution preserve finitely supported typing contexts.
In particular I T l f \mathcal{I}_{\mathbf{T}}^{\mathrm{lf}} I T lf enjoys subject reduction and expansion.
Theorem 27. For all (strong) locally finite resource semiring S \mathbf{S} S , the relevant system r I S l f \mathrm{r}\mathcal{I}_{\mathbf{S}}^{\mathrm{lf}} r I S lf enjoys subject reduction and subject expansion.
Proof. Apply the proof of Theorem 26 with the relevant axiom. The changes in the substitution lemmas are those of Theorem 17 ; locally finite discreteness replaces n n n -ary discreteness in the proof of Lemma 11 . The converse constructions still require only the semiring laws and the properties of locally finite sums.
Remark 28 (Intermediary Fragments). One can also consider some fragments lying between the finite system I S \mathcal{I}_{\mathbf{S}} I S and the locally finite system I S l f \mathcal{I}_{\mathbf{S}}^{\mathrm{lf}} I S lf .
Subject reduction and expansion hold in the finite-multiset (resp. inductive) fragment under the hypotheses of Theorem 16 (resp. Theorem 26 ), i.e. if S \mathbf{S} S is a weak resource semiring (resp. weak locally finite resource semiring).
The intersection of the finite-multiset and inductive fragments is the finite system I S \mathcal{I}_{\mathbf{S}} I S from § 1.3 . The same restrictions define fragments of r I S l f \mathrm{r}\mathcal{I}_{\mathbf{S}}^{\mathrm{lf}} r I S lf , whose intersection is r I S \mathrm{r}\mathcal{I}_{\mathbf{S}} r I S .
The Multiset Lifting
In this section we describe the following construction: instead of taking coefficients in S \mathbf{S} S as grades (as in I S \mathbf{I}_{\mathbf{S}} I S and I S f \mathbf{I}_{\mathbf{S}}^{\mathrm{f}} I S f ), we take multisets of (non-zero) coefficients : whenever a same abstracted variable x x x (in some term λ x . M \lambda x.M λ x . M ) has occurrences typed by σ \sigma σ with grades, say, a a a and b b b , the type of λ x . M \lambda x.M λ x . M is not any more [ σ : a + b ] ⊸ τ [\sigma: a+b] \multimap\tau [ σ : a + b ] ⊸ τ but [ σ : [ a , b ] ] ⊸ τ [\sigma: [a,b]] \multimap\tau [ σ : [ a , b ]] ⊸ τ . This is reminiscent of the shift from idempotent to non-idempotent intersection types; actually it is an instance of the construction (for S = 2 \mathbf{S} = 2 S = 2 , see Example 34 below).
The Finite Lifting of the Finite System
In the finite case, the construction relies on the following observation, already made in [BP15, Proposition 3].
Lemma 29. For every monoid ( M , × , 1 ) (\mathbf{M}, \times, 1) ( M , × , 1 ) , equipping M N f ( M ) \mathcal{M}_{\mathbb{N}}^{\mathrm{f}}(\mathbf{M}) M N f ( M ) with the following operations:
( a ⊕ b ) ( c ) : = a ( c ) + b ( c ) , ( a ⊙ b ) ( c ) : = ∑ a , b ∈ M a × b = c a ( a ) b ( b ) , (a \oplus b)(c) := a(c) + b(c), \qquad(a \odot b)(c) := \sum_{\substack{a,b \in\mathbf{M} \\ a \times b = c}} a(a)b(b), ( a ⊕ b ) ( c ) := a ( c ) + b ( c ) , ( a ⊙ b ) ( c ) := a , b ∈ M a × b = c ∑ a ( a ) b ( b ) , with respective neutral elements [ ] [] [ ] and [ 1 ] [1] [ 1 ] , defines a resource semiring.
Proof. The support of a sum is included in the union of the supports, and the support of a product is included in their pointwise product. Thus both operations preserve finite support. The semiring laws follow from the monoid laws and the semiring laws on N \mathbb{N} N .
Positivity, absence of zero divisors, discreteness and additive refinement follow from the pointwise application of the corresponding properties in N \mathbb{N} N . For mixed refinement, suppose that a ⊙ b = c 1 ⊕ c 2 a \odot b = c_1 \oplus c_2 a ⊙ b = c 1 ⊕ c 2 . Write a = [ a l ] l ∈ L a = [a_l]_{l \in L} a = [ a l ] l ∈ L with L L L finite. For each c ∈ M c \in\mathbf{M} c ∈ M , put J c : = { ( l , b ) ∣ l ∈ L , b ∈ supp ( b ) , a l × b = c } J_c := \{(l,b) \mid l \in L, b \in\operatorname{supp}(b), a_l \times b = c\} J c := {( l , b ) ∣ l ∈ L , b ∈ supp ( b ) , a l × b = c } . The hypothesis gives
∑ ( l , b ) ∈ J c b ( b ) = c 1 ( c ) + c 2 ( c ) . \sum_{(l,b) \in J_c} b(b) = c_1(c) + c_2(c). ( l , b ) ∈ J c ∑ b ( b ) = c 1 ( c ) + c 2 ( c ) .
Apply n n n -ary additive refinement in N \mathbb{N} N . For each ( l , b ) ∈ J c (l,b) \in J_c ( l , b ) ∈ J c it gives coefficients b 1 l ( b ) , b 2 l ( b ) b_{1l}(b), b_{2l}(b) b 1 l ( b ) , b 2 l ( b ) such that
b ( b ) = b 1 l ( b ) + b 2 l ( b ) , ∀ i ∈ { 1 , 2 } , c i ( c ) = ∑ ( l , b ) ∈ J c b i l ( b ) . b(b) = b_{1l}(b) + b_{2l}(b), \qquad\forall i \in\{1,2\},\ c_i(c) = \sum_{(l,b) \in J_c} b_{il}(b). b ( b ) = b 1 l ( b ) + b 2 l ( b ) , ∀ i ∈ { 1 , 2 } , c i ( c ) = ( l , b ) ∈ J c ∑ b i l ( b ) .
Every pair ( l , b ) ∈ L × supp ( b ) (l,b) \in L \times\operatorname{supp}(b) ( l , b ) ∈ L × supp ( b ) belongs to exactly one J c J_c J c , so these choices define b i l ( b ) : = b i l ( b ) b_{il}(b) := b_{il}(b) b i l ( b ) := b i l ( b ) unambiguously; put b i l ( b ) : = 0 b_{il}(b) := 0 b i l ( b ) := 0 for b ∉ supp ( b ) b \notin\operatorname{supp}(b) b ∈ / supp ( b ) . Each b i l b_{il} b i l has finite support, and
a = ⨁ l ∈ L [ a l ] , ∀ l ∈ L , b = b 1 l ⊕ b 2 l , ∀ i ∈ { 1 , 2 } , c i = ⨁ l ∈ L [ a l ] ⊙ b i l . a = \bigoplus_{l \in L}[a_l], \qquad\forall l \in L,\ b = b_{1l} \oplus b_{2l}, \qquad\forall i \in\{1,2\},\ c_i = \bigoplus_{l \in L}[a_l] \odot b_{il}. a = l ∈ L ⨁ [ a l ] , ∀ l ∈ L , b = b 1 l ⊕ b 2 l , ∀ i ∈ { 1 , 2 } , c i = l ∈ L ⨁ [ a l ] ⊙ b i l .
Observe that ⊕ \oplus ⊕ is just multiset union, and the convolution product ⊙ \odot ⊙ gives pointwise product of multiset elements: [ a l ] l ⊙ [ b r ] r = [ a l × b r ] l , r [a_l]_l \odot[b_r]_r = [a_l \times b_r]_{l,r} [ a l ] l ⊙ [ b r ] r = [ a l × b r ] l , r .
Let S \mathbf{S} S be a semiring with no zero divisors. Its nonzero elements form a multiplicative monoid S ∗ : = ( S ∖ { 0 } , × , 1 ) \mathbf{S}^{*} := (\mathbf{S} \setminus\{0\}, \times, 1) S ∗ := ( S ∖ { 0 } , × , 1 ) .
Definition 30 (Finite Multiset Lifting). We put [ S ] : = M N f ( S ∗ ) [\mathbf{S}] := \mathcal{M}_{\mathbb{N}}^{\mathrm{f}}(\mathbf{S}^{*}) [ S ] := M N f ( S ∗ ) , with the sum and product of Lemma 29 . We denote multisets of grades by a a a , b b b , etc., whereas multisets of types (e.g., in [ S ] [\mathbf{S}] [ S ] ) are still denoted by m m m , n n n , etc.
Corollary 32 (of Lemma 29 ). [ S ] [\mathbf{S}] [ S ] is a resource semiring.
Consequently I [ S ] I_{[S]} I [ S ] and r I [ S ] rI_{[S]} r I [ S ] enjoy subject reduction and expansion, by Theorems 16 and 17 .
Theorem 33 (Collapse). The collapse map κ : [ S ] → S \kappa: [S] \to S κ : [ S ] → S defined by
κ : [ a l ] l ∈ L ⟼ ∑ l ∈ L a l \kappa: [a_l]_{l\in L} \longmapsto\sum_{l\in L} a_l κ : [ a l ] l ∈ L ⟼ l ∈ L ∑ a l is a surjective semiring morphism. It extends to finite types and multi-types by
κ ( α ) : = α , κ ( m ⊸ τ ) : = κ ( m ) ⊸ κ ( τ ) , ( κ ( m ) ) ( τ ) : = ∑ σ ∈ I [ S ] κ ( σ ) = τ κ ( m ( σ ) ) , \kappa(\alpha) := \alpha,\qquad\kappa(\mathsf{m} \multimap\tau) := \kappa(\mathsf{m}) \multimap\kappa(\tau),\qquad(\kappa(\mathsf{m}))(\tau) := \sum_{\substack{\sigma\in I_{[S]}\\ \kappa(\sigma)=\tau}} \kappa(\mathsf{m}(\sigma)), κ ( α ) := α , κ ( m ⊸ τ ) := κ ( m ) ⊸ κ ( τ ) , ( κ ( m )) ( τ ) := σ ∈ I [ S ] κ ( σ ) = τ ∑ κ ( m ( σ )) , translating typings in I [ S ] I_{[S]} I [ S ] into typings in I S I_S I S , and likewise for the relevant systems. If S S S has positivity, this translation preserves positive typings.
Proof. Preservation of addition and multiplication are immediate. Surjectivity follows from κ ( [ c ] ) = c \kappa([c]) = c κ ([ c ]) = c for c ≠ 0 S c \ne0_S c = 0 S , and κ ( [ ] ) = 0 S \kappa([]) = 0_S κ ([ ]) = 0 S . Induction on types and on typing derivations then proves that collapse translates valid typings into valid typings. If S S S is positive, then κ ( a ) = 0 S \kappa(a) = 0_S κ ( a ) = 0 S iff a = [ ] a = [] a = [ ] . Collapse therefore preserves empty and nonempty multi-types, hence positive typings.
Example 34 (Boolean Grades). Since 2 ∗ = { 1 } 2^* = \{1\} 2 ∗ = { 1 } , [ 2 ] [2] [ 2 ] consists of finite multisets of 1 1 1 . The map a ↦ a ( 1 ) a \mapsto a(1) a ↦ a ( 1 ) identifies it with N \mathbb{N} N . Consequently, I [ 2 ] I_{[2]} I [ 2 ] is just the usual system I N I_{\mathbb{N}} I N , and likewise for the relevant systems. Collapse becomes the classical morphism turning non-idempotent into idempotent intersection typings.
Lifting Locally Finite Types
We now extend the construction to the locally finite setting from § 3 . Things get a bit more complicated: extending Definition 30 by taking grading multisets in M N l f ( S ∗ ) \mathcal{M}^{\mathrm{lf}}_{\mathbb{N}}(S^*) M N lf ( S ∗ ) is not enough, since these are N \mathbb{N} N -multisets and N \mathbb{N} N is equipped with the discrete topology, so that M N l f ( S ∗ ) = M N f ( S ∗ ) \mathcal{M}^{\mathrm{lf}}_{\mathbb{N}}(S^*) = \mathcal{M}^{\mathrm{f}}_{\mathbb{N}}(S^*) M N lf ( S ∗ ) = M N f ( S ∗ ) . We instead allow infinite multisets of grades whose family of elements is locally finite in S S S : outside every neighbourhood of 0 S 0_S 0 S , only finitely many elements may occur.
Let S S S admit locally finite sums and have no zero divisors. Its nonzero elements form a multiplicative monoid S ∗ : = ( S ∖ { 0 } , × , 1 ) S^* := (S \setminus\{0\}, \times, 1) S ∗ := ( S ∖ { 0 } , × , 1 ) .
Definition 35. A multiset of grades a : S ∗ → N a : S^* \to\mathbb{N} a : S ∗ → N has locally finite support towards 0 0 0 if, for all neighbourhood U U U of 0 S 0_S 0 S , the set supp ( a ) ∖ U \operatorname{supp}(a)\setminus U supp ( a ) ∖ U is finite. We denote the set of these multisets by [ [ S ] ] [[S]] [[ S ]] . (Equivalently, [ [ S ] ] [[S]] [[ S ]] consists of multisets [ a l ] l ∈ L [a_l]_{l\in L} [ a l ] l ∈ L whose family of elements ( a l ) l ∈ L (a_l)_{l\in L} ( a l ) l ∈ L is locally finite in S S S .) We equip [ [ S ] ] [[S]] [[ S ]] with:
V U ( a ) : = { b ∈ [ [ S ] ] ∣ ∀ c ∈ S ∗ ∖ U , b ( c ) = a ( c ) } , V_U(a) := \{b \in[[S]] \mid\forall c \in S^* \setminus U,\ b(c) = a(c)\}, V U ( a ) := { b ∈ [[ S ]] ∣ ∀ c ∈ S ∗ ∖ U , b ( c ) = a ( c )} ,
where U U U ranges over the neighbourhoods of 0 S 0_S 0 S ;
To see that the product is well-defined, write a = [ a k ] k ∈ K a = [a_k]_{k\in K} a = [ a k ] k ∈ K and b = [ b l ] l ∈ L b = [b_l]_{l\in L} b = [ b l ] l ∈ L . First, the families ( a k ) k (a_k)_k ( a k ) k and ( b l ) l (b_l)_l ( b l ) l are locally finite in S S S , so by Definition 19 the family ( a k × b l ) k , l (a_k \times b_l)_{k,l} ( a k × b l ) k , l is locally finite too. Since S S S has no zero divisors, its elements belong to S ∗ S^* S ∗ . Therefore, for each c ∈ S ∗ c \in S^* c ∈ S ∗ , Hausdorffness gives a neighbourhood U c U_c U c of 0 S 0_S 0 S not containing c c c . Hence { k , l ∣ a k × b l = c } ⊆ { k , l ∣ a k × b l ∉ U c } \{k,l \mid a_k \times b_l = c\} \subseteq\{k,l \mid a_k \times b_l \notin U_c\} { k , l ∣ a k × b l = c } ⊆ { k , l ∣ a k × b l ∈ / U c } , which is finite by local finiteness of ( a k × b l ) k , l (a_k \times b_l)_{k,l} ( a k × b l ) k , l . As a consequence the sum defining ( a ⊙ b ) ( c ) (a \mathbin{\odot} b)(c) ( a ⊙ b ) ( c ) is a finite sum.
Local finiteness of a a a in this Definition concerns its family of elements; in particular it is not the same thing as local finiteness of the multiset a a a as defined in Definition 22 (which just amounts to finite support, as we consider N \mathbb{N} N -multisets); neither does it require the coefficient family ( a ( c ) ) c ∈ S ∗ (a(c))_{c\in S^*} ( a ( c ) ) c ∈ S ∗ to be locally finite in N \mathbb{N} N .
Remark 36. For every set X X X , currying identifies M [ [ S ] ] l f ( X ) \mathcal{M}^{\mathrm{lf}}_{[\![S]\!]}(X) M [ [ S ] ] lf ( X ) with the set of all maps X × S ∗ → N X \times S^* \to\mathbb{N} X × S ∗ → N such that, for all neighbourhood U U U of 0 S 0_S 0 S ,
{ ( x , c ) ∈ X × ( S ∗ ∖ U ) ∣ m ( x , c ) ≠ 0 } is finite. \{(x,c) \in X \times(S^* \setminus U) \mid m(x,c) \ne0\} \text{ is finite.} {( x , c ) ∈ X × ( S ∗ ∖ U ) ∣ m ( x , c ) = 0 } is finite.
For m ∈ M [ [ S ] ] l f ( X ) m \in\mathcal{M}^{\mathrm{lf}}_{[\![S]\!]}(X) m ∈ M [ [ S ] ] lf ( X ) , we denote again the curried map by m ~ \widetilde{m} m .
Theorem 37. [ [ S ] ] [\![S]\!] [ [ S ] ] is a locally finite resource semiring. In addition, if G G G is a guarding set of S S S , then [ [ G ] ] : = { a ∈ [ [ S ] ] ∣ supp ( a ) ⊆ G } [\![G]\!] := \{a \in[\![S]\!] \mid\operatorname{supp}(a) \subseteq G\} [ [ G ] ] := { a ∈ [ [ S ] ] ∣ supp ( a ) ⊆ G } is a guarding set of [ [ S ] ] [\![S]\!] [ [ S ] ] .
Proof. We first check that Definition 35 defines a topological semiring (Definitions 1 and 18).
To see that the topology on [ [ S ] ] [\![S]\!] [ [ S ] ] is Hausdorff, take a ≠ b a \ne b a = b , then ∃ c ∈ S ∗ \exists c \in S^* ∃ c ∈ S ∗ , a ( c ) ≠ b ( c ) a(c) \ne b(c) a ( c ) = b ( c ) ; any neighbourhood U U U of 0 S 0_S 0 S not containing c c c gives disjoint neighbourhoods V U ( a ) V_U(a) V U ( a ) and V U ( b ) V_U(b) V U ( b ) .
Continuity of addition is immediate. For continuity of multiplication at ( a , b ) (a,b) ( a , b ) , we first fix a neighbourhood U U U of 0 S 0_S 0 S and we will find a neighbourhood U ′ U' U ′ of 0 S 0_S 0 S such that
V U ′ ( a ) ⊙ V U ′ ( b ) ⊆ V U ( a ⊙ b ) . V_{U'}(a) \odot V_{U'}(b) \subseteq V_U(a \odot b). V U ′ ( a ) ⊙ V U ′ ( b ) ⊆ V U ( a ⊙ b ) .
Choose a neighbourhood W W W of 0 S 0_S 0 S such that W × S W ⊆ U W \times_S W \subseteq U W × S W ⊆ U . The sets A : = supp ( a ) ∖ W A := \operatorname{supp}(a) \setminus W A := supp ( a ) ∖ W and B : = supp ( b ) ∖ W B := \operatorname{supp}(b) \setminus W B := supp ( b ) ∖ W are finite. By continuity of multiplication in S S S , choose a neighbourhood U ′ ⊆ W U' \subseteq W U ′ ⊆ W of 0 S 0_S 0 S such that
∀ a ∈ A , a × S U ′ ⊆ U , ∀ b ∈ B , U ′ × S b ⊆ U . \forall a \in A,\ a \times_S U' \subseteq U,\qquad\forall b \in B,\ U' \times_S b \subseteq U. ∀ a ∈ A , a × S U ′ ⊆ U , ∀ b ∈ B , U ′ × S b ⊆ U .
If a ∈ supp ( a ) a \in\operatorname{supp}(a) a ∈ supp ( a ) , b ∈ supp ( b ) b \in\operatorname{supp}(b) b ∈ supp ( b ) and a × S b ∉ U a \times_S b \notin U a × S b ∈ / U , then a , b ∉ U ′ a,b \notin U' a , b ∈ / U ′ . Indeed, if a ∈ U ′ a \in U' a ∈ U ′ , then either b ∈ W b \in W b ∈ W , giving a × S b ∈ W × S W ⊆ U a \times_S b \in W \times_S W \subseteq U a × S b ∈ W × S W ⊆ U , or b ∈ B b \in B b ∈ B , giving a × S b ∈ U ′ × S b ⊆ U a \times_S b \in U' \times_S b \subseteq U a × S b ∈ U ′ × S b ⊆ U . The argument for b ∈ U ′ b \in U' b ∈ U ′ is symmetric.
Now take a ′ ∈ V U ′ ( a ) a' \in V_{U'}(a) a ′ ∈ V U ′ ( a ) and b ′ ∈ V U ′ ( b ) b' \in V_{U'}(b) b ′ ∈ V U ′ ( b ) . For every c ∉ U c \notin U c ∈ / U ,
( a ′ ⊙ b ′ ) ( c ) = ∑ a ∈ supp ( a ) ∖ U ′ b ∈ supp ( b ) ∖ U ′ a × S b = c a ( a ) × N b ( b ) = ( a ⊙ b ) ( c ) . (a' \odot b')(c) =
\sum_{\substack{a \in\operatorname{supp}(a)\setminus U'\\ b \in\operatorname{supp}(b)\setminus U'\\ a \times_S b=c}}
a(a) \times_{\mathbb{N}} b(b) = (a \odot b)(c). ( a ′ ⊙ b ′ ) ( c ) = a ∈ supp ( a ) ∖ U ′ b ∈ supp ( b ) ∖ U ′ a × S b = c ∑ a ( a ) × N b ( b ) = ( a ⊙ b ) ( c ) .
This proves the required inclusion.
We now check that [ [ S ] ] [\![S]\!] [ [ S ] ] admits locally finite sums (Definition 19).
Let ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I be locally finite, let us prove that it has a sum. By Remark 36, for every neighbourhood U U U of 0 S 0_S 0 S , the set
E U : = { ( i , c ) ∈ I × ( S ∗ ∖ U ) ∣ a i ( c ) ≠ 0 } E_U := \{(i,c) \in I \times(S^* \setminus U) \mid a_i(c) \ne0\} E U := {( i , c ) ∈ I × ( S ∗ ∖ U ) ∣ a i ( c ) = 0 }
is finite. For fixed c ∈ S ∗ c \in S^* c ∈ S ∗ and any U U U not containing c c c , we obtain that finitely many a i ( c ) a_i(c) a i ( c ) are non-zero. Thus a ( c ) : = ∑ i ∈ I a i ( c ) a(c) := \sum_{i\in I} a_i(c) a ( c ) := ∑ i ∈ I a i ( c ) is a finite sum in N \mathbb{N} N . In addition, for all neighbourhood U U U of 0 S 0_S 0 S , the set supp ( a ) ∖ U \operatorname{supp}(a) \setminus U supp ( a ) ∖ U is included in the second projection of E U E_U E U , hence is finite, so that a ∈ [ [ S ] ] a \in[\![S]\!] a ∈ [ [ S ] ] . To show that it is the sum of the family ( a i ) i (a_i)_i ( a i ) i , observe that as soon as F ⊆ f I F \subseteq_f I F ⊆ f I contains the first projection of E U E_U E U , then ⨁ i ∈ F a i ∈ V U ( a ) \bigoplus_{i\in F} a_i \in V_U(a) ⨁ i ∈ F a i ∈ V U ( a ) .
Take a locally finite family ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I and a partition I = ⨆ j ∈ J I j I = \bigsqcup_{j\in J} I_j I = ⨆ j ∈ J I j . For all j ∈ J j \in J j ∈ J and c ∈ S ∗ c \in S^* c ∈ S ∗ , if ∑ i ∈ I j a i ( c ) ≠ 0 \sum_{i\in I_j} a_i(c) \ne0 ∑ i ∈ I j a i ( c ) = 0 , then a i ( c ) ≠ 0 a_i(c) \ne0 a i ( c ) = 0 for some i ∈ I j i \in I_j i ∈ I j . As a consequence, for every neighbourhood U U U of 0 S 0_S 0 S ,
{ j ∈ J ∣ ⨁ i ∈ I j a i ∉ V U ( [ [ ] ] ) } ⊆ { j ∈ J ∣ ∃ ( i , c ) ∈ E U , i ∈ I j } . \left\{j \in J \mathrel{\Big|} \bigoplus_{i\in I_j} a_i \notin V_U([\![\,]\!])\right\}
\subseteq
\{j \in J \mid\exists(i,c) \in E_U,\ i \in I_j\}. ⎩ ⎨ ⎧ j ∈ J i ∈ I j ⨁ a i ∈ / V U ([ [ ] ]) ⎭ ⎬ ⎫ ⊆ { j ∈ J ∣ ∃ ( i , c ) ∈ E U , i ∈ I j } .
The right-hand set is finite, since E U E_U E U is finite and each i i i belongs to exactly one I j I_j I j . Thus ( ⨁ i ∈ I j a i ) j ∈ J (\bigoplus_{i\in I_j} a_i)_{j\in J} ( ⨁ i ∈ I j a i ) j ∈ J is locally finite. Associativity and commutativity of the finite sums in N \mathbb{N} N , applied pointwise for every c ∈ S ∗ c \in S^* c ∈ S ∗ , give ⨁ i ∈ I a i = ⨁ j ∈ J ⨁ i ∈ I j a i \bigoplus_{i\in I} a_i = \bigoplus_{j\in J} \bigoplus_{i\in I_j} a_i ⨁ i ∈ I a i = ⨁ j ∈ J ⨁ i ∈ I j a i .
Let ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I and each ( b i j ) j ∈ J (b_{ij})_{j\in J} ( b ij ) j ∈ J be locally finite. Write a i = [ a i k ] k ∈ K i a_i=[a_{ik}]_{k\in K_i} a i = [ a ik ] k ∈ K i and b i j = [ b i j l ] l ∈ L i j b_{ij}=[b_{ijl}]_{l\in L_{ij}} b ij = [ b ij l ] l ∈ L ij . By Remark 36, ( a i k ) i , k (a_{ik})_{i,k} ( a ik ) i , k is locally finite in S S S , and so is ( b i j l ) j , l (b_{ijl})_{j,l} ( b ij l ) j , l for every i i i . Definition 19 (3) gives local finiteness of ( a i k × S b i j l ) i , j , k , l (a_{ik}\mathbin{\times_S}b_{ijl})_{i,j,k,l} ( a ik × S b ij l ) i , j , k , l . Since a i ⊙ b i j = [ a i k × S b i j l ] k , l a_i\mathbin{\odot}b_{ij}=[a_{ik}\mathbin{\times_S}b_{ijl}]_{k,l} a i ⊙ b ij = [ a ik × S b ij l ] k , l , Remark 36 gives local finiteness of ( a i ⊙ b i j ) i , j (a_i\mathbin{\odot}b_{ij})_{i,j} ( a i ⊙ b ij ) i , j .
Then we check algebraic axioms of a locally finite resource semiring (Definition 20 ).
For locally finite discreteness, suppose that ⨁ i a i = [ 1 S ] \bigoplus_i a_i=[1_S] ⨁ i a i = [ 1 S ] . For all c ≠ 1 S c\ne1_S c = 1 S , for all i i i , a i ( c ) = 0 a_i(c)=0 a i ( c ) = 0 by positivity of N \mathbb{N} N ; local finiteness of ( a i ) i (a_i)_i ( a i ) i and n n n -ary discreteness of N \mathbb{N} N gives exactly one a i ( 1 S ) a_i(1_S) a i ( 1 S ) equal to 1 1 1 , and all others equal to 0 0 0 . Hence exactly one a i a_i a i is [ 1 S ] [1_S] [ 1 S ] , and all others are empty.
To prove locally finite additive refinement, take locally finite families ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I , ( b j ) j ∈ J (b_j)_{j\in J} ( b j ) j ∈ J and labellings λ : I → X \lambda:I\to X λ : I → X , μ : J → X \mu:J\to X μ : J → X , such that
∀ x ∈ X , ⨁ i ∈ I λ ( i ) = x a i = ⨁ j ∈ J μ ( j ) = x b j . \forall x\in X,\qquad\bigoplus_{\substack{i\in I\\\lambda(i)=x}}a_i=\bigoplus_{\substack{j\in J\\\mu(j)=x}}b_j. ∀ x ∈ X , i ∈ I λ ( i ) = x ⨁ a i = j ∈ J μ ( j ) = x ⨁ b j .
For every x ∈ X x\in X x ∈ X and c ∈ S ∗ c\in S^* c ∈ S ∗ , this gives an equality in N \mathbb{N} N ,
∑ i ∈ I λ ( i ) = x a i ( c ) = ∑ j ∈ J μ ( j ) = x b j ( c ) , \sum_{\substack{i\in I\\\lambda(i)=x}}a_i(c)=\sum_{\substack{j\in J\\\mu(j)=x}}b_j(c), i ∈ I λ ( i ) = x ∑ a i ( c ) = j ∈ J μ ( j ) = x ∑ b j ( c ) ,
with only finitely many nonzero summands. Apply n n n -ary additive refinement in N \mathbb{N} N to each of these equalities, and put c i j ( c ) = 0 c_{ij}(c)=0 c ij ( c ) = 0 when λ ( i ) ≠ μ ( j ) \lambda(i)\ne\mu(j) λ ( i ) = μ ( j ) . We obtain maps c i j : S ∗ → N c_{ij}:S^*\to\mathbb{N} c ij : S ∗ → N such that
∀ i , c , a i ( c ) = ∑ j c i j ( c ) , ∀ j , c , b j ( c ) = ∑ i c i j ( c ) . (2) \forall i,c,\quad a_i(c)=\sum_j c_{ij}(c),\qquad\forall j,c,\quad b_j(c)=\sum_i c_{ij}(c). \tag*{(2)} ∀ i , c , a i ( c ) = j ∑ c ij ( c ) , ∀ j , c , b j ( c ) = i ∑ c ij ( c ) . (2)
We must check that ( c i j ) i , j (c_{ij})_{i,j} ( c ij ) i , j is locally finite. If c i j ( c ) ≠ 0 c_{ij}(c)\ne0 c ij ( c ) = 0 , then both a i ( c ) ≠ 0 a_i(c)\ne0 a i ( c ) = 0 and b j ( c ) ≠ 0 b_j(c)\ne0 b j ( c ) = 0 . Outside each neighbourhood U U U of 0 S 0_S 0 S , there are finitely many such pairs ( i , c ) (i,c) ( i , c ) and ( j , c ) (j,c) ( j , c ) , hence finitely many triples ( i , j , c ) (i,j,c) ( i , j , c ) . By Remark 36, the maps c i j c_{ij} c ij belong to [ [ S ] ] [[S]] [[ S ]] and form a locally finite family. The required identities follow by Eq. (2) .
For simultaneous locally finite mixed refinement, take locally finite families ( a k ) k ∈ K (a_k)_{k\in K} ( a k ) k ∈ K , ( b x k ) x ∈ X (b_{xk})_{x\in X} ( b x k ) x ∈ X for every k ∈ K k\in K k ∈ K , and ( c i ) i ∈ I (c_i)_{i\in I} ( c i ) i ∈ I , and a labelling λ : I → X \lambda:I\to X λ : I → X , such that
∀ x ∈ X , ⨁ k ∈ K a k ⊙ b x k = ⨁ i ∈ I λ ( i ) = x c i . (3) \forall x\in X,\qquad\bigoplus_{k\in K}a_k\mathbin{\odot}b_{xk}=\bigoplus_{\substack{i\in I\\\lambda(i)=x}}c_i. \tag*{(3)} ∀ x ∈ X , k ∈ K ⨁ a k ⊙ b x k = i ∈ I λ ( i ) = x ⨁ c i . (3)
We use the decomposition of natural coefficients into units to obtain a common decomposition of each a k a_k a k into singletons, independently of x x x . As in the proof of mixed refinement in N \mathbb{N} N , the decompositions of each b x k b_{xk} b x k are then obtained by n n n -ary additive refinement.
Decompose each natural coefficient a k ( a ) a_k(a) a k ( a ) into a sum of a k ( a ) a_k(a) a k ( a ) units. Explicitly, put
L k : = { ( a , r ) ∣ a ∈ S ∗ , r ∈ { 1 , … , a k ( a ) } } , a k , ( a , r ) : = a , a k l : = [ a k l ] . L_k:=\{(a,r)\mid a\in S^*,\ r\in\{1,\ldots,a_k(a)\}\},\qquad a_{k,(a,r)}:=a,\qquad a_{kl}:=[a_{kl}]. L k := {( a , r ) ∣ a ∈ S ∗ , r ∈ { 1 , … , a k ( a )}} , a k , ( a , r ) := a , a k l := [ a k l ] .
Then a k = ⨁ l ∈ L k a k l a_k=\bigoplus_{l\in L_k}a_{kl} a k = ⨁ l ∈ L k a k l . By Remark 36, the family ( a k l ) k , l (a_{kl})_{k,l} ( a k l ) k , l is locally finite in S S S , hence ( a k l ) k , l (a_{kl})_{k,l} ( a k l ) k , l is locally finite in [ [ S ] ] [[S]] [[ S ]] .
Now, for fixed x ∈ X x\in X x ∈ X and c ∈ S ∗ c\in S^* c ∈ S ∗ , define
I x c : = { i ∈ I ∣ λ ( i ) = x , c i ( c ) ≠ 0 } , I_{xc}:=\{i\in I\mid\lambda(i)=x,\ c_i(c)\ne0\}, I x c := { i ∈ I ∣ λ ( i ) = x , c i ( c ) = 0 } ,
J x c : = { ( k , l , b ) ∣ k ∈ K , l ∈ L k , b ∈ S ∗ , a k l × S b = c , b x k ( b ) ≠ 0 } . J_{xc}:=\{(k,l,b)\mid k\in K,\ l\in L_k,\ b\in S^*,\ a_{kl}\mathbin{\times_S}b=c,\ b_{xk}(b)\ne0\}. J x c := {( k , l , b ) ∣ k ∈ K , l ∈ L k , b ∈ S ∗ , a k l × S b = c , b x k ( b ) = 0 } .
These sets are finite. Indeed, local finiteness of ( c i ) i (c_i)_i ( c i ) i gives finiteness of I x c I_{xc} I x c . Definition 19(3) gives local finiteness of ( a k ⊙ b x k ) k , x (a_k \mathbin{\odot} b_{xk})_{k,x} ( a k ⊙ b x k ) k , x , hence there are finitely many k , x k,x k , x such that ( a k ⊙ b x k ) ( c ) ≠ 0 (a_k \mathbin{\odot} b_{xk})(c) \ne0 ( a k ⊙ b x k ) ( c ) = 0 ; each of these is a finite sum of summands a k ( a ) × b x k ( b ) a_k(a) \times b_{xk}(b) a k ( a ) × b x k ( b ) , for some a × S b = c a \times_S b = c a × S b = c ; each such a a a is equal to finitely many a k l a_{kl} a k l . This gives finiteness of J x c J_{xc} J x c .
Equation (3) , evaluated at c c c , becomes
∑ ( k , l , b ) ∈ J x c b x k ( b ) = ∑ i ∈ I x c c i ( c ) . \sum_{(k,l,b)\in J_{xc}} b_{xk}(b) = \sum_{i\in I_{xc}} c_i(c). ( k , l , b ) ∈ J x c ∑ b x k ( b ) = i ∈ I x c ∑ c i ( c ) .
Apply n n n -ary additive refinement in N \mathbb{N} N to this equality, for every x , c x,c x , c . This defines a coefficient b i k l ( b ) b_{ikl}(b) b ik l ( b ) whenever x = λ ( i ) x = \lambda(i) x = λ ( i ) and c = a k l × S b c = a_{kl} \times_S b c = a k l × S b ; put b i k l ( b ) : = 0 b_{ikl}(b) := 0 b ik l ( b ) := 0 otherwise. They satisfy
∀ x , k , l , b , b x k ( b ) = ∑ i ∈ I λ ( i ) = x b i k l ( b ) , ∀ i , c , c i ( c ) = ∑ k ∈ K , l ∈ L k , b ∈ S ∗ a k l × S b = c b i k l ( b ) . \forall x,k,l,b,\quad b_{xk}(b) = \sum_{\substack{i\in I\\\lambda(i)=x}} b_{ikl}(b),\qquad
\forall i,c,\quad c_i(c) = \sum_{\substack{k\in K,\ l\in L_k,\ b\in S^*\\a_{kl}\times_S b=c}} b_{ikl}(b). ∀ x , k , l , b , b x k ( b ) = i ∈ I λ ( i ) = x ∑ b ik l ( b ) , ∀ i , c , c i ( c ) = k ∈ K , l ∈ L k , b ∈ S ∗ a k l × S b = c ∑ b ik l ( b ) .
We must now prove that ( b i k l ) i ∈ I (b_{ikl})_{i\in I} ( b ik l ) i ∈ I is locally finite for every k , l k,l k , l . Fix k ∈ K k\in K k ∈ K , l ∈ L k l\in L_k l ∈ L k and a neighbourhood U U U of 0 S 0_S 0 S . By Remark 36, local finiteness of ( b x k ) x (b_{xk})_x ( b x k ) x gives finitely many pairs ( x , b ) (x,b) ( x , b ) with b ∉ U b\notin U b ∈ / U and b x k ( b ) ≠ 0 b_{xk}(b)\ne0 b x k ( b ) = 0 . For any b i k l ( b ) ≠ 0 b_{ikl}(b)\ne0 b ik l ( b ) = 0 , we must have b λ ( i ) k ( b ) ≠ 0 b_{\lambda(i)k}(b)\ne0 b λ ( i ) k ( b ) = 0 ; for each of the finitely many pairs ( x , b ) (x,b) ( x , b ) above, a nonzero b i k l ( b ) b_{ikl}(b) b ik l ( b ) with λ ( i ) = x \lambda(i)=x λ ( i ) = x requires, by construction, i ∈ I x , a k l × S b i\in I_{x,a_{kl}\times_S b} i ∈ I x , a k l × S b , a finite set. Consequently
F U : = { ( i , b ) ∈ I × ( S ∗ ∖ U ) ∣ b i k l ( b ) ≠ 0 } F_U := \{(i,b)\in I\times(S^*\setminus U)\mid b_{ikl}(b)\ne0\} F U := {( i , b ) ∈ I × ( S ∗ ∖ U ) ∣ b ik l ( b ) = 0 }
is finite. For each i i i , this implies that supp ( b i k l ) ∖ U \operatorname{supp}(b_{ikl})\setminus U supp ( b ik l ) ∖ U is finite. Since U U U was arbitrary, each b i k l b_{ikl} b ik l belongs to [ [ S ] ] [[S]] [[ S ]] . Moreover, { i ∈ I ∣ b i k l ∉ V U ( [ [ ] ] ) } \{i\in I\mid b_{ikl}\notin V_U([[\,]])\} { i ∈ I ∣ b ik l ∈ / V U ([[ ]])} is equal to the first projection of F U F_U F U , hence is finite. Thus ( b i k l ) i ∈ I (b_{ikl})_{i\in I} ( b ik l ) i ∈ I is locally finite.
In addition, we obtain:
∀ x , k , l , b x k = ⨁ i ∈ I λ ( i ) = x b i k l , ∀ i , c i = ⨁ k ∈ K l ∈ L k a k l ⊙ b i k l . \forall x,k,l,\quad b_{xk}=\bigoplus_{\substack{i\in I\\\lambda(i)=x}}b_{ikl},\qquad
\forall i,\quad c_i=\bigoplus_{\substack{k\in K\\l\in L_k}}a_{kl}\mathbin{\odot}b_{ikl}. ∀ x , k , l , b x k = i ∈ I λ ( i ) = x ⨁ b ik l , ∀ i , c i = k ∈ K l ∈ L k ⨁ a k l ⊙ b ik l .
Finally, let G G G be a guarding set of S S S , with associated continuous morphism γ : S → 2 \gamma:S\to\mathbf{2} γ : S → 2 . Define
[ [ γ ] ] ( a ) : = ⋁ a ∈ supp ( a ) γ ( a ) . [[\gamma]](a):=\bigvee_{a\in\operatorname{supp}(a)}\gamma(a). [[ γ ]] ( a ) := a ∈ supp ( a ) ⋁ γ ( a ) .
Only finitely many terms are nonzero, since G G G is a neighbourhood of 0 S 0_S 0 S . Positivity and absence of zero divisors in N \mathbb{N} N , together with the sum and product equations for γ \gamma γ , give [ [ γ ] ] ( a ⊕ b ) = [ [ γ ] ] ( a ) ∨ [ [ γ ] ] ( b ) [[\gamma]](a\mathbin{\oplus}b)=[[ \gamma]](a)\vee[[\gamma]](b) [[ γ ]] ( a ⊕ b ) = [[ γ ]] ( a ) ∨ [[ γ ]] ( b ) and [ [ γ ] ] ( a ⊙ b ) = [ [ γ ] ] ( a ) ∧ [ [ γ ] ] ( b ) [[\gamma]](a\mathbin{\odot}b)=[[ \gamma]](a)\wedge[[\gamma]](b) [[ γ ]] ( a ⊙ b ) = [[ γ ]] ( a ) ∧ [[ γ ]] ( b ) . Moreover [ [ γ ] ] ( [ ] ) = 0 [[\gamma]]([\,])=0 [[ γ ]] ([ ]) = 0 and [ [ γ ] ] ( [ 1 S ] ) = 1 [[\gamma]]([1_S])=1 [[ γ ]] ([ 1 S ]) = 1 . Thus [ [ γ ] ] [[\gamma]] [[ γ ]] is a unital semiring morphism with [ [ γ ] ] − 1 ( { 0 } ) = [ [ G ] ] [[\gamma]]^{-1}(\{0\})=[[G]] [[ γ ] ] − 1 ({ 0 }) = [[ G ]] . It is constant on every V G ( a ) V_G(a) V G ( a ) , hence continuous. Therefore [ [ G ] ] [[G]] [[ G ]] is a guarding set of [ [ S ] ] [[S]] [[ S ]] .
Consequently, subject reduction and expansion hold in I [ [ S ] ] l f \mathcal{I}^{\mathrm{lf}}_{[[S]]} I [[ S ]] lf and r [ [ S ] ] l f \mathfrak{r}^{\mathrm{lf}}_{[[S]]} r [[ S ]] lf , by Theorems 26 and 27 .
Remark 38. One could replace N \mathbb{N} N as a target of multisets by another semiring Q \mathbb{Q} Q , using its operations for multiplicities. The proof of Theorem 37 then requires appropriate refinement and discreteness properties of Q \mathbb{Q} Q . In particular for Q = 2 \mathbb{Q}=\mathbf{2} Q = 2 , the construction only produces a weak locally finite resource semiring.
Theorem 39 (Collapse). The collapse surjective semiring morphism defined and extended to (multi-)types as Theorem 33 translates typings in I [ [ S ] ] l f \mathcal{I}^{\mathrm{lf}}_{[[S]]} I [[ S ]] lf into typings in I S l f \mathcal{I}^{\mathrm{lf}}_S I S lf , and likewise for the relevant systems. If S S S has positivity, this translation preserves positive typings.
Proof. The family ( a l ) l (a_l)_l ( a l ) l is locally finite, so its sum exists and κ \kappa κ is well-defined. Preservation of addition and multiplication are immediate by the locally finite semiring laws of S \mathbf{S} S . As for preservation of locally finite sums, let ( a i ) i ∈ I (a_i)_{i\in I} ( a i ) i ∈ I be locally finite, with a i = [ a i l ] l ∈ L i a_i=[a_{il}]_{l\in L_i} a i = [ a i l ] l ∈ L i . By Remark 36, ( a i l ) i , l (a_{il})_{i,l} ( a i l ) i , l is locally finite. By Definition 19 (2), ( κ ( a i ) ) i ∈ I (\kappa(a_i))_{i\in I} ( κ ( a i ) ) i ∈ I is locally finite and
κ ( ⨁ i ∈ I a i ) = ∑ i , l a i l = ⨁ i ∈ I κ ( a i ) . \kappa\left(\bigoplus_{i\in I}a_i\right)=\sum_{i,l}a_{il}=\bigoplus_{i\in I}\kappa(a_i). κ ( i ∈ I ⨁ a i ) = i , l ∑ a i l = i ∈ I ⨁ κ ( a i ) .
Continuity of γ \gamma γ gives γ ( κ ( a ) ) = [ [ γ ] ] ( a ) \gamma(\kappa(a))=[[\gamma]](a) γ ( κ ( a )) = [[ γ ]] ( a ) , hence κ − 1 ( G ) = [ [ G ] ] \kappa^{-1}(G)=[[G]] κ − 1 ( G ) = [[ G ]] . As a consequence, an immediate induction using all these properties concludes that valid typings in I [ [ S ] ] l f \mathbb{I}^{\mathrm{lf}}_{[[\mathbf{S}]]} I [[ S ]] lf are translated to valid typings in I S l f \mathbb{I}^{\mathrm{lf}}_{\mathbf{S}} I S lf . Preservation of positive typings follows from the same argument as in Theorem 33 .
Remark 40. In particular, [ S ] [\mathbf{S}] [ S ] is a subsemiring of [ [ S ] ] [[\mathbf{S}]] [[ S ]] . If 0 S 0_{\mathbf{S}} 0 S is isolated in S \mathbf{S} S , the condition of Definition 35 applied to the neighbourhood { 0 S } \{0_{\mathbf{S}}\} { 0 S } forces every multiset of grades to have finite support, so [ S ] = [ [ S ] ] [\mathbf{S}]=[[\mathbf{S}]] [ S ] = [[ S ]] . Moreover, V { 0 S } ( a ) = { a } V_{\{0_{\mathbf{S}}\}}(a)=\{a\} V { 0 S } ( a ) = { a } for every a ∈ [ [ S ] ] a\in[[\mathbf{S}]] a ∈ [[ S ]] , so the topology defined on [ [ S ] ] [[\mathbf{S}]] [[ S ]] is discrete.
Example 41. Let us give some details in the case S = T \mathbf{S}=\mathbf{T} S = T :
The monoid T ∗ \mathbf{T}^{*} T ∗ is the usual ( N , + , 0 ) (\mathbb{N},+ ,0) ( N , + , 0 ) .
[ [ T ] ] [[\mathbf{T}]] [[ T ]] is just T ∗ → N \mathbf{T}^{*}\to\mathbb{N} T ∗ → N . Indeed, a neighbourhood basis of ∞ \infty ∞ in T \mathbf{T} T is given by U d : = { ∞ } ∪ { c ∈ T ∗ ∣ c > d } U_d:=\{\infty\}\cup\{c\in\mathbf{T}^{*}\mid c>d\} U d := { ∞ } ∪ { c ∈ T ∗ ∣ c > d } , for d ∈ N d\in\mathbb{N} d ∈ N . All these sets have finite complements.
( a ⊕ b ) ( c ) : = a ( c ) + b ( c ) , ( a ⊙ b ) ( c ) : = ∑ a + b = c a ( a ) b ( b ) . (a\oplus b)(c):=a(c)+b(c),\qquad(a\odot b)(c):=\sum_{a+b=c}a(a)b(b). ( a ⊕ b ) ( c ) := a ( c ) + b ( c ) , ( a ⊙ b ) ( c ) := a + b = c ∑ a ( a ) b ( b ) .
The zero and unit are [ ] [\,] [ ] and [ 0 ] [0] [ 0 ] , respectively.
d [ [ T ] ] ( a , b ) : = { 0 if a = b , 2 − min { c ∣ a ( c ) ≠ b ( c ) } otherwise. d_{[[\mathbf{T}]]}(a,b):=
\begin{cases}
0 & \text{if }a=b,\\
2^{-\min\{c\mid a(c)\ne b(c)\}} & \text{otherwise.}
\end{cases} d [[ T ]] ( a , b ) := { 0 2 − m i n { c ∣ a ( c ) = b ( c )} if a = b , otherwise.
Indeed, V U d ( a ) V_{U_d}(a) V U d ( a ) consists of the multisets agreeing with a a a at grades at most d d d .
∀ d ∈ N , { ( σ , c ) ∈ I [ [ T ] ] l f × T ∗ ∣ c ≤ d , m ~ ( σ , c ) ≠ 0 } is finite, \forall d\in\mathbb{N},\quad\left\{(\sigma,c)\in\mathbb{I}^{\mathrm{lf}}_{[[\mathbf{T}]]}\times\mathbf{T}^{*}\mid c\le d,\ \widetilde{m}(\sigma,c)\ne0\right\}\text{ is finite,} ∀ d ∈ N , { ( σ , c ) ∈ I [[ T ]] lf × T ∗ ∣ c ≤ d , m ( σ , c ) = 0 } is finite,
i.e., within any delay d d d , m m m contains only finitely many types.
Remark 42 (Finite and Locally Finite Mixed Refinement). A locally finite resource semiring need not be a resource semiring: the refining family in mixed refinement may have to be infinite, even when the hypothesis is a single binary equality. This happens in [ [ T ] ] [[\mathbf{T}]] [[ T ]] , as follows.
Put a p = 4 p a_p=4^p a p = 4 p , b p = 2 × 4 p b_p=2\times4^p b p = 2 × 4 p for p ∈ N p\in\mathbb{N} p ∈ N , and
a = [ a p ] p , b = [ b q ] q , c 1 = [ a p + b p ] p , c 2 = [ a p + b q ] p ≠ q . a=[a_p]_p,\qquad b=[b_q]_q,\qquad c_1=[a_p+b_p]_p,\qquad c_2=[a_p+b_q]_{p\ne q}. a = [ a p ] p , b = [ b q ] q , c 1 = [ a p + b p ] p , c 2 = [ a p + b q ] p = q .
These multisets belong to [ [ T ] ] [[\mathbf{T}]] [[ T ]] , and a ⊙ b = c 1 ⊕ c 2 a\odot b=c_1\oplus c_2 a ⊙ b = c 1 ⊕ c 2 . All grades a p + b q a_p+b_q a p + b q are distinct: for p ≠ q p\ne q p = q the base-4 expansion of a p + b q a_p+b_q a p + b q has digit 1 in position p p p and digit 2 in position q q q ; for p = q p=q p = q , it has digit 3 in position p p p . All other digits are zero. Thus a p + b q a_p+b_q a p + b q uniquely determines ( p , q ) (p,q) ( p , q ) . Now, suppose that mixed refinement gave a finite set L L L and multisets satisfying
a = ⨁ l ∈ L a l , ∀ l ∈ L , b = b 1 l ⊕ b 2 l , ∀ i ∈ { 1 , 2 } , c i = ⨁ l ∈ L a l ⊙ b i l . \mathbf{a} = \bigoplus_{l \in L} a_l,\qquad\forall l \in L,\ \mathbf{b} = b_{1l} \oplus b_{2l},\qquad\forall i \in\{1,2\},\ c_i = \bigoplus_{l \in L} a_l \odot b_{il}. a = l ∈ L ⨁ a l , ∀ l ∈ L , b = b 1 l ⊕ b 2 l , ∀ i ∈ { 1 , 2 } , c i = l ∈ L ⨁ a l ⊙ b i l .
Observe that for all i i i , l l l , p p p and q q q ,
( a l ⊙ b i l ) ( a p + b q ) = ∑ a , b a + b = a p + b q a l ( a ) b i l ( b ) = ∑ p ′ , q ′ a p ′ + b q ′ = a p + b q a l ( a p ′ ) b i l ( b q ′ ) = a l ( a p ) b i l ( b q ) (a_l \odot b_{il})(a_p+b_q)=\sum_{\substack{a,b\\a+b=a_p+b_q}}a_l(a)b_{il}(b)=\sum_{\substack{p',q'\\a_{p'}+b_{q'}=a_p+b_q}}a_l(a_{p'})b_{il}(b_{q'})=a_l(a_p)b_{il}(b_q) ( a l ⊙ b i l ) ( a p + b q ) = a , b a + b = a p + b q ∑ a l ( a ) b i l ( b ) = p ′ , q ′ a p ′ + b q ′ = a p + b q ∑ a l ( a p ′ ) b i l ( b q ′ ) = a l ( a p ) b i l ( b q )
because supp ( a l ) ⊆ supp ( a ) \operatorname{supp}(a_l) \subseteq\operatorname{supp}(a) supp ( a l ) ⊆ supp ( a ) and supp ( b i l ) ⊆ supp ( b ) \operatorname{supp}(b_{il}) \subseteq\operatorname{supp}(b) supp ( b i l ) ⊆ supp ( b ) , and because a p + b q a_p+b_q a p + b q uniquely determines ( p , q ) (p,q) ( p , q ) .
Since a ( a p ) = 1 a(a_p)=1 a ( a p ) = 1 , there is exactly one l ( p ) ∈ L l(p) \in L l ( p ) ∈ L such that a l ( p ) ( a p ) = 1 a_{l(p)}(a_p)=1 a l ( p ) ( a p ) = 1 , and a l ( a p ) = 0 a_l(a_p)=0 a l ( a p ) = 0 for any other l l l . Hence for all p p p and q q q ,
c 1 ( a p + b q ) = ∑ l ∈ L a l ( a p ) b 1 l ( b q ) = b 1 , l ( p ) ( b q ) . c_1(a_p+b_q)=\sum_{l\in L}a_l(a_p)b_{1l}(b_q)=b_{1,l(p)}(b_q). c 1 ( a p + b q ) = l ∈ L ∑ a l ( a p ) b 1 l ( b q ) = b 1 , l ( p ) ( b q ) .
Suppose there are p ≠ q p \ne q p = q such that l ( p ) = l ( q ) l(p)=l(q) l ( p ) = l ( q ) , then
1 = c 1 ( a p + b p ) = b 1 , l ( p ) ( b p ) = b 1 , l ( q ) ( b p ) = c 1 ( a q + b p ) = 0. 1=c_1(a_p+b_p)=b_{1,l(p)}(b_p)=b_{1,l(q)}(b_p)=c_1(a_q+b_p)=0. 1 = c 1 ( a p + b p ) = b 1 , l ( p ) ( b p ) = b 1 , l ( q ) ( b p ) = c 1 ( a q + b p ) = 0.
Thus p ↦ l ( p ) p \mapsto l(p) p ↦ l ( p ) is injective, which is impossible for finite L L L . (Instead, a locally finite refinement does exist: take L = N L=\mathbb{N} L = N , a p = [ a p ] a_p=[a_p] a p = [ a p ] , b 1 p = [ b p ] b_{1p}=[b_p] b 1 p = [ b p ] and b 2 p = [ b q ] q ≠ p b_{2p}=[b_q]_{q\ne p} b 2 p = [ b q ] q = p . The family ( a p ) p (a_p)_p ( a p ) p is locally finite, and the displayed identities hold.)
Consequently, subject reduction (and expansion) of the system I ⟦ T ⟧ l f I^{\mathrm{lf}}_{\llbracket T\rrbracket} I [ [ T ] ] lf does hold by Theorem 26 , whereas subject reduction of the finite system I ⟦ T ⟧ I_{\llbracket T\rrbracket} I [ [ T ] ] does not: there is derivation
h : [ [ α : a ] ] ⊸ α : [ 0 ] , g : [ [ α : b ] ] ⊸ α : a , f : [ [ ] ⊸ α : c 1 , [ α : [ 0 ] ] ⊸ α : c 2 ] , x : [ α : c 2 ] ⊢ ( λ y . h ( g y ) ) ( f x ) : α , h : [\![\alpha:a]\!]\multimap\alpha:[0],\quad g : [\![\alpha:b]\!]\multimap\alpha:a,\quad f :
\begin{bmatrix}
[]\multimap\alpha:c_1,\\
[\alpha:[0]]\multimap\alpha:c_2
\end{bmatrix},\quad x:[\alpha:c_2]
\vdash(\lambda y.h(gy))(fx):\alpha, h : [ [ α : a ] ] ⊸ α : [ 0 ] , g : [ [ α : b ] ] ⊸ α : a , f : [ [ ] ⊸ α : c 1 , [ α : [ 0 ]] ⊸ α : c 2 ] , x : [ α : c 2 ] ⊢ ( λ y . h ( g y )) ( f x ) : α ,
but no finite typing of h ( g ( f x ) ) h(g(fx)) h ( g ( f x )) with the same type and context: the typing of the redex crucially relies on the fact that the abstracted variable y y y has multi-types a ⊙ b a\odot b a ⊙ b and c 1 ⊕ c 2 c_1\oplus c_2 c 1 ⊕ c 2 .
Operational Characterisations
One main interest of usual intersection types is that they do not only guarantee, but also characterise some operational properties of λ \lambda λ -terms. Classically, typing in I 2 I_2 I 2 and I N I_{\mathbb{N}} I N characterises head normalisation [22 , 23 , 8 ] : we show that this can actually be extended to all systems defined above. We then recall two other characterisations from the literature, to illustrate how restricting the shape of the types allows to account for other notions of termination.
Head Normalisation
Write H N \mathcal{HN} H N for the terms having a head normal form λ x 1 … x n . y M 1 … M k \lambda x_1\ldots x_n.yM_1\ldots M_k λ x 1 … x n . y M 1 … M k .
Definition 43. A reducibility candidate is a set R ⊂ H N \mathcal{R}\subset\mathcal{HN} R ⊂ H N containing all terms x M 1 … M k xM_1\ldots M_k x M 1 … M k and closed under inverse head contraction: if P [ Q / x ] M ⃗ ∈ R P[Q/x]\vec{M}\in\mathcal{R} P [ Q / x ] M ∈ R then ( λ x . P ) Q M ⃗ ∈ R (\lambda x.P)Q\vec{M}\in\mathcal{R} ( λ x . P ) Q M ∈ R .
The set H N \mathcal{HN} H N itself is a candidate. Any nonempty intersection of candidates is a candidate. For any set V ⊆ R ⊆ Λ V\subseteq R\subseteq\Lambda V ⊆ R ⊆ Λ and candidate S S S ,
R → S : = { M ∣ ∀ N ∈ R , M N ∈ S } R\to S:=\{M\mid\forall N\in R,\ MN\in S\} R → S := { M ∣ ∀ N ∈ R , M N ∈ S }
is a candidate too (this holds in particular when R R R is a candidate).
Theorem 44 (Soundness and Completeness wrt. Head Normalisation). For any positive semiring S S S with no zero divisors, I S \mathsf{I}_{S} I S and r I S \mathsf{rI}_{S} rI S characterise head normalisation: M M M is typable iff M ∈ H N M \in\mathcal{HN} M ∈ H N . The same holds for I S l f \mathsf{I}^{\mathrm{lf}}_{S} I S lf and r I S l f \mathsf{rI}^{\mathrm{lf}}_{S} rI S lf if S S S admits locally finite sums and has a guarding set G G G .
Proof. Soundness. For the full systems, let G G G be the guarding set defined on S S S , and γ : S → 2 \gamma: S \to\mathbf{2} γ : S → 2 the associated morphism (as in Definition 23). For the finite systems, use the morphism γ : 0 ↦ 0 \gamma: \mathbf{0} \mapsto0 γ : 0 ↦ 0 , and a ↦ 1 a \mapsto1 a ↦ 1 for a ≠ 0 a \ne0 a = 0 ; positivity and absence of zero divisors make it a semiring morphism. Given an environment ρ \rho ρ mapping atoms to candidates, define the reducibility interpretation of a type or a multi-type by:
⟦ α ⟧ ρ : = ρ ( α ) , ⟦ m ⊸ σ ⟧ ρ : = ⟦ m ⟧ ρ → ⟦ σ ⟧ ρ , ⟦ m ⟧ ρ : = ⋂ γ ( m ( σ ) ) = 1 ⟦ σ ⟧ ρ . \llbracket\alpha\rrbracket_\rho:= \rho(\alpha), \qquad\llbracket m \multimap\sigma\rrbracket_\rho:= \llbracket m \rrbracket_\rho\to\llbracket\sigma\rrbracket_\rho, \qquad\llbracket m \rrbracket_\rho:= \bigcap_{\gamma(m(\sigma))=1} \llbracket\sigma\rrbracket_\rho. [ [ α ] ] ρ := ρ ( α ) , [ [ m ⊸ σ ] ] ρ := [ [ m ] ] ρ → [ [ σ ] ] ρ , [ [ m ] ] ρ := γ ( m ( σ )) = 1 ⋂ [ [ σ ] ] ρ .
For finite types this definition is well-founded by induction on their formation trees. For the full systems it is well-founded since we recurse only in inductive positions: the condition γ ( m ( σ ) ) = 1 \gamma(m(\sigma)) = 1 γ ( m ( σ )) = 1 exactly means that σ \sigma σ is not guarded by its coefficient in m m m . (An empty intersection is defined to be Λ \Lambda Λ .) The semiring equations, and for the full systems the continuity of γ \gamma γ (ensuring that it preserves locally finite sums), give:
\llbracket m+n \rrbracket_\rho= \llbracket m \rrbracket_\rho\cap\llbracket n \rrbracket_\rho, \qquad\left\llbracket\sum_{i\in I} a_i \times m_i \right\rrbracket_\rho= \bigcap_{\substack{i\in I\\\gamma(a_i)=1}} \llbracket m_i \rrbracket_\rho.
Using these identities, a straightforward induction on the derivation (in either system) allows to prove that for all derivation ▶ x 1 : m 1 , … , x n : m n ⊢ M : σ \blacktriangleright x_1 : m_1,\ldots,x_n : m_n \vdash M : \sigma ▶ x 1 : m 1 , … , x n : m n ⊢ M : σ , for all N i ∈ ⟦ m i ⟧ ρ N_i \in\llbracket m_i \rrbracket_\rho N i ∈ [ [ m i ] ] ρ , for 1 ≤ i ≤ n 1 \le i \le n 1 ≤ i ≤ n , one has M [ N ⃗ / x ⃗ ] ∈ ⟦ σ ⟧ ρ M[\vec{N}/\vec{x}] \in\llbracket\sigma\rrbracket_\rho M [ N / x ] ∈ [ [ σ ] ] ρ , and likewise for multi-types. Finally, take ρ ( α ) : = H N \rho(\alpha) := \mathcal{HN} ρ ( α ) := H N and N i : = x i N_i := x_i N i := x i to obtain M ∈ ⟦ σ ⟧ ρ ⊆ H N M \in\llbracket\sigma\rrbracket_\rho\subseteq\mathcal{HN} M ∈ [ [ σ ] ] ρ ⊆ H N for any typable M M M .
Completeness. Type a head normal form λ x ⃗ . y M 1 … M k \lambda\vec{x}.yM_1\ldots M_k λ x . y M 1 … M k by assigning y y y the type [ ] ⊸ … ⊸ [ ] ⊸ α [] \multimap\ldots\multimap[] \multimap\alpha [ ] ⊸ … ⊸ [ ] ⊸ α , with k k k empty domains, typing each argument with [ ] [] [ ] , then applying ( ⊸ e ) (\multimap e) ( ⊸ e ) and ( ⊸ i ) (\multimap i) ( ⊸ i ) . Conclude by subject expansion in the finite system (which holds without any assumption on S S S , as a consequence of Lemma 15). The resulting derivation is also valid in the full system. □
Positive Typing
Let us recall two further characterisations from the literature, which use restrictions to positive typings.
Definition 46 (Positive Typing). The polarity of a position in the syntax tree of a type is defined as follows:
the root of the type is positive,
polarity is reversed when entering the domain of an arrow ⊸ \multimap ⊸ ,
polarity is preserved when entering the codomain of an arrow, and when entering in an element of an S S S -multiset.
A typing derivation ▶ Γ ⊢ M : σ \blacktriangleright\ \Gamma\vdash M : \sigma ▶ Γ ⊢ M : σ is positive if [ ] [] [ ] does not occur in any Γ ( x ) \Gamma(x) Γ ( x ) in negative position, and in σ \sigma σ in positive position.
Write W N \mathcal{WN} WN for the set of all λ \lambda λ -terms having a β \beta β -normal form. The following Theorem extends the well-established characterisation of weak β \beta β -normalisation by positive typing in I 2 \mathbf{I}_2 I 2 [11 , 20 ] and in r I N \mathbf{rI}_{\mathbb{N}} rI N [8 ] .
Theorem 47 (Soundness and Completeness wrt. Weak β \beta β -Normalisation). For any positive semiring S \mathbf{S} S with no zero divisors, positive typing in I S \mathbf{I}_{\mathbf{S}} I S and r I S \mathbf{rI}_{\mathbf{S}} rI S characterise weak normalisation: M M M is typable iff M ∈ W N M \in\mathcal{WN} M ∈ WN .
Proof. As in Remark 45, we can use soundness of I 2 \mathbf{I}_2 I 2 and completeness of r I N \mathbf{rI}_{\mathbb{N}} rI N :
for soundness, instead of using γ \gamma γ , apply to all coefficients the semiring morphism χ : S → 2 \chi: \mathbf{S} \to\mathbf{2} χ : S → 2 defined by χ ( a ) = 0 \chi(a) = 0 χ ( a ) = 0 iff a = 0 a = 0 a = 0 . The resulting derivation is a positive derivation in I 2 \mathbf{I}_2 I 2 : since χ \chi χ preserves zero and nonzero coefficients (this is a consequence of positivity and absence of zero divisors), the translation preserves empty and nonempty multi-types;
for completeness, any M ∈ W N M \in\mathcal{WN} M ∈ WN has a positive derivation in r I N \mathbf{rI}_{\mathbb{N}} rI N . Apply to all its coefficients the semiring morphism N → S \mathbb{N} \to\mathbf{S} N → S , n ↦ 1 + ⋯ + 1 n \mapsto1 + \cdots+ 1 n ↦ 1 + ⋯ + 1 (n n n times). Positivity ensures that nonzero coefficients remain nonzero, so the resulting derivation in r I S \mathbf{rI}_{\mathbf{S}} rI S is positive.
The restriction to the finite systems is essential, since χ \chi χ need not preserve local finiteness of multisets or guardedness of types.
Write H N + \mathcal{HN}^{+} H N + for the set of all hereditary head normalising λ \lambda λ -terms, i.e. H N + \mathcal{HN}^{+} H N + is the coinductively defined set such that M ∈ H N + M \in\mathcal{HN}^{+} M ∈ H N + iff M ∈ H N M \in\mathcal{HN} M ∈ H N and, if M → β ∗ λ x 1 … x n . y M 1 … M k M \to_{\beta}^{*} \lambda x_1 \ldots x_n.yM_1 \ldots M_k M → β ∗ λ x 1 … x n . y M 1 … M k , then M i ∈ H N + M_i \in\mathcal{HN}^{+} M i ∈ H N + for all 1 ≤ i ≤ k 1 \leq i \leq k 1 ≤ i ≤ k . Equivalently, M ∈ H N + M \in\mathcal{HN}^{+} M ∈ H N + is its Böhm tree contains no undefined subterm ⊥ \bot ⊥ . The following characterisation was given in [10 ] .
Theorem 48 (Soundness and Completeness wrt. Hereditary Head Normalisation). Positive typing in I T l f \mathbf{I}_{\mathbf{T}}^{\mathrm{lf}} I T lf characterises H N + \mathcal{HN}^{+} H N + : M M M is typable by a positive derivation iff M ∈ H N + M \in\mathcal{HN}^{+} M ∈ H N + .
The lifted system r I ⟦ T ⟧ l f \mathbf{rI}_{\llbracket\mathbf{T}\rrbracket}^{\mathrm{lf}} rI [ [ T ] ] lf from Example 41 is exactly the “auxiliary system” used in [10 ] to prove Theorem 48: one first proves completeness of positive typings in r I ⟦ T ⟧ l f \mathbf{rI}_{\llbracket\mathbf{T}\rrbracket}^{\mathrm{lf}} rI [ [ T ] ] lf wrt. hereditary head normalisation, which immediately gives completeness of positive typings in I ⟦ T ⟧ l f \mathbf{I}_{\llbracket\mathbf{T}\rrbracket}^{\mathrm{lf}} I [ [ T ] ] lf by inclusion, and finally in I T l f \mathbf{I}_{\mathbf{T}}^{\mathrm{lf}} I T lf by collapse (Theorem 39).
Acknowledgements
Tito Nguyẽn pointed us at an error in a first version of this draft and drew our attention to parts of the literature around Definition 2, which sparked insightful discussions with Quentin Aristote and Vincent Moreau. He also suggested the counter-example λ \lambda λ -term from Remark 42, which has a semantic counterpart in [21 ] . Fruitful exchanges also took place with Gabriele Vanoni. The authors wish to thank them all.