Intersection Types and Domain Operators ?

(1)

Intersection Types and Domain Operators ?

Fabio Alessi

^a

, Mariangiola Dezani-Ciancaglini

^b

, Stefania Lusin

^c

aDipartimento di Matematica e Informatica, Universit`a di Udine, via delle Scienze 208, 33100 Udine, Italyalessi@dimi.uniud.it

bDipartimento di Informatica, Universit`a di Torino, Corso Svizzera 185, 10149 Torino, Italydezani@di.unito.it

cDipartimento di Informatica, Universit`a di Venezia, via Torino 153, 30170 Venezia, Italy slusin@dsi.unive.it

Abstract

We use intersection types as a tool for obtaining λ-models. Relying on the notion of easy intersection type theory we successfully build a λ-model in which the interpretation of an arbitrary simple easy term is any filter which can be described by a continuous predicate.

This allows us to prove two results. The first gives a proof of consistency of the λ-theory where the λ-term (λx.xx)(λx.xx) is forced to behave as the join operator. This result has interesting consequences on the algebraic structure of the lattice of λ-theories. The second result is that for any simple easy term there is a λ-model where the interpretation of the term is the minimal fixed point operator.

Key words: Lambda calculus, intersection types, models of lambda calculus, lambda theories, fixed point operators.

Introduction

Intersection types were introduced in the late 70’s by Dezani and Coppo [8, 10, 6], to overcome the limitations of Curry’s type discipline. They are a very expressive type language which allows to describe and capture various properties of λ-terms.

For instance, they have been used in Pottinger [19] to give the first type theoretic characterisation of strongly normalizable terms and in Coppo et al. [11] to cap- ture persistently normalising terms and normalising terms. See Dezani et al. [12], appearing also in this issue, for a more complete account of this line of research.

? Partially supported by EU within the FET - Global Computing initiative, project DART IST-2001-33477, and MURST Projects COMETA and McTati. The funding bodies are not responsible for any use that might be made of the results presented here.

(2)

Intersection types have a very significant realizability semantics with respect to applicative structures. This is a generalisation of Scott’s natural semantics [20] of simple types. According to this interpretation types denote subsets of the applicative structure, an arrow type A → B denotes the sets of points which map all points belonging to the interpretation of A to points belonging to the interpretation of B, and an intersection type A ∩ B denotes the intersections of the interpretation of A and the interpretation of B. Building on this, intersection types have been used in Barendregt et al. [6] to give a proof of the completeness of the natural semantics of Curry’s simple type assignment system in applicative structures, introduced in Scott [20].

Intersection types have also an alternative semantics based on duality which is re- lated to Abramsky’s Domain Theory in Logical Form [1]. Actually it amounts to the application of that paradigm to the special case of ω-algebraic lattice models of pure λ-calculus, see Coppo et al. [9]. Namely, types correspond to compact ele- ments: the type Ω denotes the least element, intersections denote joins of compact elements, and arrow types denote step functions of compact elements. A typing judgement can then be interpreted as saying that a given term belongs to a pointed compact open set in an ω-algebraic lattice model of λ-calculus. By duality, type theories give rise to filter λ-models. Intersection type assignment systems can then be viewed as finitary logical descriptions of the interpretation of λ-terms in such models, where the meaning of a λ-term is the set of types which are deducible for it.

This duality lies at the heart of the success of intersection types as a powerful tool for the analysis of λ-models, see Plotkin [18] and the references there. Section 2 of Dezani et al. [12] discusses intersection types (with partial intersection) as finitary descriptions of inverse limit λ-models.

The λ-models we build out of intersection types differ essentially in the preorder relations between types. In all these preorders, the equivalencies between atomic types and intersections of arrow types are crucial in order to determine the theory.

In the present paper the focus is on semantic proofs of consistencies of λ-theories.

Actually, the mainstream of consistency proofs is based on the use of syntactic tools (see Kuper [15] and the references there). Instead, very little literature can be found on the application of semantic tools, we can mention the papers Zylberajch [22], Baeten and Boerboom [5], Alessi et al. [3], Alessi and Lusin [4].

In [4] Alessi and Lusin deal with the issue of easiness proofs of λ-terms from the semantic point of view (we recall that a closed term e is easy if, for any other closed term t, the theory λβ + {t = e} is consistent). Going in the direction of Alessi et al. [3], they introduced the notion of simple easiness: this notion, which turns out to be stronger than easiness, can be handled in a natural way by semantic tools, and allows to prove consistency results via construction of suitable filter models: given a simple easy term e and an arbitrary closed term t, it is possible to build (in a canonical way) a non-trivial filter model which equates the interpretation of e and

(3)

t. [4] proves in such a way the easiness of several terms.

Besides, simple easiness is interesting in itself, since it has to do with minimal sets of axioms which are needed in order to assign certain types to the easy terms.

The theoretical contribution of the present paper is to show how the relation between simple easiness and axioms on types can be put to work in order to interpret easy terms by filters described by continuous predicates.

This produces two nice applications. Given an arbitrary simple easy term e we build a filter model F⁵ such that e is interpreted as the join operator: the interpretation [[e]]⁵of e in F⁵ is exactly the filter Θ such that for all filters Ξ, Υ

(Θ · Ξ) · Υ = Ξ t Υ.

This way we prove the consistency of the λ-theory which equates (λx.xx)(λx.xx) to the join operator. This consistency has been used in Lusin and Salibra [17] to show that there exists a sub-lattice of the lattice of λ-theories which satisfies many interesting algebraic properties.

The second result we give is the following. For an arbitrary simple easy term e there is a filter model F⁵ such that the interpretation [[e]]⁵ of e in F⁵ is the minimal fixed point operator

µ

(that is

µ

(f ) = ^F_nfⁿ(⊥), for all continuous endofunctions f over F⁵). This result is not trivial: easy terms can obviously be equated to an arbitrary fixed point combinator Y, i.e. it is possible to find λ-models M such that [[e]]^M = [[Y]]^M. This only implies that [[e]]^M represents a fixed point operator, but there is no guarantee as to the minimality.

The present paper is organised as follows. In Section 1 we present easy intersection type theories and type assignment systems for them. In Section 2 we introduce λ- models based on spaces of filters in easy intersection type theories. Section 3 gives the main theoretical contribution of the present paper: after introducing simple easy terms, we show that each simple easy term can be interpreted as an arbitrary filter which can be described by a continuous predicate. In Section 4 and Section 5 we derive from our result the two above mentioned applications. Finally, Section 6 discusses similarities and differences between the present paper and Dezani et al. [12].

The consistency of the λ-theory in which the λ-term (λx.xx)(λx.xx) behaves as the join operator was presented at WIT’02 [13].

1 Intersection Type Assignment Systems

Intersection types are syntactic objects built inductively by closing a given set CC

(4)

of type atoms (constants), which contains the universal type Ω, under the function type constructor → and the intersection type constructor ∩.

Definition 1 (Intersection type language) Let CC be a countable set of constants such that Ω ∈ CC. The intersection type language over CC, denoted by TT = TT(CC), is defined by the following abstract syntax:

T

T = CC | TT → TT | TT ∩ TT.

Notation Upper case Roman letters i.e. A, B, . . ., will denote arbitrary types. Greek letters φ, ψ, . . . will denote constants in CC. When writing intersection types we shall use the following conventions:

• the constructor ∩ takes precedence over the constructor →;

• the constructor → associates to the right;

• ^T_i∈IAi with I = {1, . . . , n} and n ≥ 1 is short for ((. . . (A1∩ A2) . . .) ∩ An);

• ^T_i∈IA_i with I = ∅ is Ω.

Much of the expressive power of intersection type disciplines comes from the fact that types can be endowed with a preorder relation ≤ which satisfies axioms and rules 5 of Figure 1, so inducing the structure of a meet semi-lattice with respect to ∩, the top element being Ω. We recall here the notion of easy intersection type theory as first introduced in Alessi and Lusin [4].

(refl ) A ≤ A (trans) A ≤ B B ≤ C

A ≤ C (mon) A ≤ A⁰ B ≤ B⁰

A ∩ B ≤ A⁰∩ B⁰ (idem) A ≤ A ∩ A

(incl_L) A ∩ B ≤ A (incl_R) A ∩ B ≤ B

(→ ∩) (A → B) ∩ (A → C) ≤ A → B ∩ C (η) A⁰ ≤ A B ≤ B⁰ A → B ≤ A⁰ → B⁰

(Ω) A ≤ Ω (Ω-η) Ω ≤ Ω → Ω

Fig. 1. The axioms and rules of 5

Definition 2 (Easy intersection type theories) Let TT = TT(CC) be an intersection type language. The easy intersection type theory (eitt for short) Σ(CC, 5) over TT is the set of all judgements A ≤ B derivable from 5, where 5 is a collection of axioms and rules such that (we write A ∼ B for A ≤ B & B ≤ A and 5⁻ for 5 \ 5):

(1) 5 contains the set 5 of axioms and rules shown in Figure 1;

(5)

(2) 5⁻contains axioms of the following two shapes only:

φ ≤ φ⁰,

φ ∼ ^T_h∈H(ϕ_h → F_h).

where φ, φ⁰, ϕ_h ∈ CC, F_h ∈ TT, and φ, φ⁰ 6≡ Ω;

(3) no rule is in 5⁻;

(4) for each φ 6≡ Ω there is exactly one axiom in 5⁻of the shape φ ∼ ^T_h∈H(ϕ_h → F_h);

(5) let 5⁻ contain φ ∼ ^T_h∈H(ϕ_h → F_h) and φ⁰ ∼ ^T_k∈K(ϕ⁰_k → F⁰_k), with φ, φ⁰ 6≡ Ω. Then 5⁻ contains also φ ≤ φ⁰ iff for each k ∈ K, there exists h_k ∈ H such that ϕ⁰_k ≤ ϕ_h_k and F_h_k ≤ F⁰_kare both in 5⁻.

Notice that:

(a) since Ω ∼ Ω → Ω ∈ Σ(CC, 5) by (Ω) and (Ω-η), it follows that all atoms in CC are equivalent to suitable (intersections of) arrow types;

(b) ∩ (modulo ∼) is associative and commutative;

(c) in the last clause of the above definition F_k⁰ and F_h_k must be constant types for each k ∈ K.

Notation When we consider an eitt Σ(CC, 5), we will write CC⁵ for CC, TT⁵for TT(CC) and Σ⁵ for Σ(CC, 5). Moreover A ≤5 B will be short for (A ≤ B) ∈ Σ⁵ and A∼₅B for A ≤₅ B ≤₅ A. We will consider syntactic equivalence “≡” of types up to associativity and commutativity of ∩.

One can easily show that all types (not only type constants) are equivalent to suitable intersections of arrow types. This is stated in the following lemma together with a simple inequality between intersections of arrows and arrows of intersections.

Lemma 3

(1) For all A ∈ TT⁵there are I, and B_i, C_i ∈ TT⁵ such that A∼5

\

i∈I

(B_i → C_i).

(2) For all J ⊆ I, and A_i, B_i ∈ TT⁵,

\

i∈I

(Ai → Bi) ≤5 (^\

i∈J

Ai) → (^\

i∈J

Bi).

A nice feature of eitts is the possibility of performing smooth induction proofs based on the number of arrows in types. In view of this aim next definition and lemma work.

(6)

Definition 4 The mapping # : TT⁵ → IN is defined inductively on types as follows:

#(A) = 0 if A ∈ CC⁵;

#(A → B) = #(A) + 1;

#(A ∩ B) = max{#(A), #(B)}.

Lemma 5 For all A ∈ TT⁵ with #(A) ≥ 1 there is B ∈ TT⁵ such that A∼5B, B ≡^T_i∈I(C_i → D_i), and #(B) = #(A).

PROOF. Let A ≡ (^T_j∈J(C_j⁰ → D⁰_j)) ∩ (^T_h∈Hφh), where C_j⁰, D⁰_j ∈ TT⁵, φh ∈ CC⁵. For each h ∈ H there are I^(h), ϕ^(h)_i ∈ CC⁵, F_i^(h) ∈ TT⁵, such that

φ_h∼5

\

i∈I^(h)

(ϕ^(h)_i → F_i^(h)).

We can choose

B ≡ (^\

j∈J

(C_j⁰ → D⁰_j)) ∩ (^\

h∈H

( ^\

i∈I^(h)

(ϕ^(h)_i → F_i^(h)))).

Another nice feature of eitts is that the order between intersections of arrows agrees with the order between joins of step functions. This property, which is fully ex- plained in Section 2 of [12], relies on the next theorem.

Theorem 6 For all I, and Ai, Bi, C, D ∈ TT⁵,

\

i∈I

(Ai → Bi) ≤5 C → D iff ^\

i∈J

Bi ≤5 D where J = {i ∈ I | C ≤5 Ai}.

PROOF. (⇐) easily follows from Lemma 3(2) and rule (η).

As to (⇒), recall that, by Definition 2, for each constant φ 6≡ Ω, there is exactly one axiom in 5⁻of the shape φ ∼ ^T_h∈H(ϕ_h → F_h). One can prove the statement by induction on the definition of ≤5; the only non-trivial case is when the inequality is derived using transitivity as the last step with the middle type being an intersection containing constants. In that case, condition (5) of Definition 2 is used.

Notice that in the statement of Theorem 6 the set J may be empty, and in this case we get Ω∼5D.

Before giving the crucial notion of intersection-type assignment system, we intro- duce bases and some related notations.

(7)

Definition 7 (Basis) A 5-basis is a (possibly infinite) set of statements of the shape x : A, where A ∈ TT⁵, with all variables distinct.

We will use the following notations:

• If Γ is a ∇-basis then x ∈ Γ is short for (x : A) ∈ Γ for some A.

• If Γ is a 5-basis and A ∈ TT⁵ then Γ, x : A is short for Γ ∪ {x : A} when x /∈ Γ.

Definition 8 (Type assignment system) The intersection type assignment system relative to the eitt Σ⁵, notation λ∩⁵, is a formal system for deriving judgements of the form Γ `⁵ t : A, where the subject t is an untyped λ-term, the predicate A is in TT⁵, and Γ is a 5-basis. Its axioms and rules are the following:

(Ax) (x : A) ∈ Γ

Γ `⁵ x : A (Ax-Ω) Γ `⁵ t : Ω (→ I) Γ, x : A `⁵ t : B

Γ `⁵ λx.t : A → B (→ E) Γ `⁵ t : A → B Γ `⁵ u : A Γ `⁵ tu : B

(∩I) Γ `⁵ t : A Γ `⁵ t : B

Γ `⁵ t : A ∩ B (≤5) Γ `⁵ t : A A ≤₅ B Γ `⁵ t : B

Example 9 Self-application can be easily typed in all λ∩⁵, as follows.

x : (A → B) ∩ A `⁵x : (A → B) ∩ A (≤5) x : (A → B) ∩ A `⁵ x : A → B

x : (A → B) ∩ A `⁵x : (A → B) ∩ A (≤5) x : (A → B) ∩ A `⁵x : A

(→ E) x : (A → B) ∩ A `⁵xx : B

(→ I)

`⁵ λx.xx : (A → B) ∩ A → B

Notice that due to the presence of axiom (Ax-Ω), one can type terms without as- suming types for their free variables.

As usual we consider λ-terms modulo α-conversion. Notice that intersection elim- ination rules

(∩E) Γ `⁵ t : A ∩ B Γ `⁵ t : A

Γ `⁵ t : A ∩ B Γ `⁵ t : B are derivable¹ in any λ∩⁵.

Moreover, the following rules are admissible:

1 Recall that a rule is derivable in a system if, for each instance of the rule, there is a deduction in the system of its conclusion from its premises. A rule is admissible in a system if, for each instance of the rule, if its premises are derivable in the system then so is its conclusion.

(8)

(≤∇L) Γ, x : A ` t : B A⁰ ≤∇ A Γ, x : A⁰ ` t : B (W) Γ ` t : B x 6∈ Γ

Γ, x : A ` t : B (S) Γ, x : A ` t : B x 6∈ F V (t) Γ ` t : B

We end this section with a standard Generation Theorem.

Theorem 10 (Generation Theorem)

(1) Assume A6∼₅Ω. Then Γ `⁵ x : A iff (x : B) ∈ Γ and B ≤5 A for some B ∈ TT⁵.

(2) Γ `⁵ tu : A iff Γ `⁵ t : B → A, and Γ `⁵ u : B for some B ∈ TT⁵.

(3) Γ `⁵ λx.t : A iff Γ, x : B_i `⁵ t : C_i and^T_i∈I(B_i → C_i) ≤5 A, for some I and B_i, C_i ∈ TT⁵.

(4) Γ `⁵ λx.t : B → C iff Γ, x : B `⁵ t : C.

PROOF. The proof of each (⇐) is easy. So we only treat (⇒).

(1) Easy by induction on derivations, since only the axioms (Ax), (Ax-Ω), and the rules (∩I), (≤5) can be applied. Notice that the condition A6∼₅Ω implies that Γ `⁵ x : A cannot be obtained just using axiom (Ax-Ω).

(2) If A∼5Ω we can choose B∼₅Ω. Otherwise, the proof is by induction on derivations. The only interesting case is when A ≡ A₁ ∩ A₂ and the last applied rule is (∩I):

(∩I) Γ `⁵ tu : A₁ Γ `⁵ tu : A₂ Γ `⁵ tu : A₁∩ A₂ .

The condition A6∼₅Ω implies that we cannot have A₁∼5A₂∼5Ω. We give the proof for A16∼₅Ω and A₂6∼₅Ω, the other cases can be treated similarly. By induction there are B₁, B₂such that

Γ `⁵ t : B₁ → A₁, Γ `⁵ u : B₁, Γ `⁵ t : B₂ → A₂, Γ `⁵ u : B₂.

Then Γ `⁵ t : (B₁ → A₁) ∩ (B₂ → A₂) and by Lemma 3(2) and rule (η) (B₁ → A₁) ∩ (B₂ → A₂) ≤₅ B₁∩ B₂ → A₁∩ A₂ ≤ B₁ ∩ B₂ → A.

We are done, since Γ `⁵ u : B1∩ B2 by rule (∩I) .

(3) The proof is very similar to the proof of Point (2). It is again by induction on

(9)

derivations and again the only interesting case is when the last applied rule is (∩I):

(∩I) Γ `⁵ λx.t : A1 Γ `⁵ λx.t : A2

Γ `⁵ λx.t : A₁∩ A₂ . By induction there are I, B_i, C_i, J, D_j, G_j such that

∀i ∈ I. Γ, x : B_i `⁵ t : C_i, ∀j ∈ J. Γ, x : D_j `⁵ t : G_j,

T

i∈I(B_i → C_i) ≤5 A₁ & ^T_j∈J(D_j → G_j) ≤5 A₂. So we are done since (^T_i∈I(B_i → C_i)) ∩ (^T_j∈J(D_j → G_j)) ≤₅ A.

(4) The case C∼5Ω is trivial. Otherwise let I, B_i, C_i as in Point (3), where A ≡ B → C. Then^T_i∈I(B_i → C_i) ≤5 B → C implies by Theorem 6 that^T_i∈JC_i ≤5

C where J = {i ∈ I | B ≤5 B_i}. From Γ, x : B_i `⁵ t : C_i we can derive Γ, x : B `⁵ t : C_i by rule (≤∇ L), so by (∩I) we have Γ, x : B `⁵ t : ^T_i∈JC_i. Finally applying rule (≤5) we can conclude Γ, x : B `⁵ t : C.

Note that in Point (1) of the previous theorem, we have to suppose that A 6∼^∇ Ω, since we can derive `^∇x : Ω using axiom (Ax-Ω).

2 Filter Models

In this section we discuss how to build λ-models out of type theories. We start with the definition of filter for eitt’s. Then we show how to turn the space of filters into an applicative structure. We define continuous maps from the space of filters to the space of its continuous functions. Since the composition of these maps is the identity we get λ-models (filter models).

Definition 11 (Filters)

(1) A 5-filter (or a filter over TT⁵) is a set Ξ ⊆ TT⁵ such that:

• Ω ∈ Ξ;

• if A ≤5 B and A ∈ Ξ, then B ∈ Ξ;

• if A, B ∈ Ξ, then A ∩ B ∈ Ξ;

(2) F⁵denotes the set of 5-filters over TT⁵;

(3) if Ξ ⊆ TT⁵, ↑⁵ Ξ denotes the 5-filter generated by Ξ;

(4) a 5-filter is principal if it is of the shape ↑⁵ {A}, for some type A. We shall denote ↑⁵ {A} simply by ↑⁵ A.

It is well known that F⁵is an ω-algebraic lattice, whose poset of compact (or finite) elements is isomorphic to the reversed poset obtained by quotienting the preorder

(10)

on TT⁵ by ∼5. That means that compact elements are the filters of the form ↑⁵ A for some type A, the top element is TT⁵, and the bottom element is ↑⁵ Ω. Moreover the join of two filters is the filter induced by their union and the meet of two filters is their intersection, i.e.:

Ξ t Υ = ↑⁵ (Ξ ∪ Υ) Ξ u Υ = Ξ ∩ Υ.

The key property of F^∇ is to be a reflexive object in the category of ω-algebraic complete lattices and Scott-continuous functions. This become clear by endowing the space of filters with a notion of application which induces continuous maps from F^∇to its function space [F⁵ → F⁵] and vice versa.

Definition 12 (Application)

(1) Application · : F⁵× F⁵ 7→ F⁵is defined as

Ξ · Υ = {B | ∃A ∈ Υ.A → B ∈ Ξ}.

(2) The continuous maps F⁵ : F⁵ 7→ [F⁵ → F⁵] and G⁵ : [F⁵ → F⁵] 7→ F⁵ are defined as:

F⁵(Ξ) = λλΥ ∈ F⁵.Ξ · Υ;

G⁵(f ) =↑⁵ {A → B | B ∈ f (↑⁵ A)}.

Notice that previous definition is sound, since it is easy to verify that Ξ · Υ is a 5-filter.

We start with a useful lemma on application.

Lemma 13 Let Σ⁵be an eitt, Ξ ∈ F⁵ and C ∈ TT⁵. Then B ∈ Ξ· ↑⁵ C iff C → B ∈ Ξ.

PROOF.

B ∈ Ξ· ↑⁵ C ⇔ ∃C⁰.C ≤5 C⁰ & C⁰ → B ∈ Ξ by definition of application

⇔ C → B ∈ Ξ by rule (η).

As expected, F⁵and G⁵are inverse to each other.

(11)

Lemma 14

F⁵ ◦ G⁵ = id_[F⁵_→F⁵_]; G⁵ ◦ F⁵ = id_F⁵.

PROOF. It suffices to consider compact elements.

(F⁵◦ G⁵)(f )(↑⁵ A) = {B | A → B ∈ G⁵(f )}

by definition of F⁵ and Lemma 13

= {B | A → B ∈↑⁵ {A⁰ → B⁰ | B⁰ ∈ f (↑⁵ A⁰)}}

by definition of G⁵

= {B | ∃I, A_i, B_i.(∀i ∈ I.B_i ∈ f (↑⁵ A_i))

&^T_i∈I(A_i → B_i) ≤5 A → B}

by definition of filter

= {B | ∃I, A_i, B_i.(∀i ∈ I.B_i ∈ f (↑⁵ A_i))

&^T_i∈JB_i ≤₅ B}

where J = {i ∈ I | A ≤5 A_i} by Theorem 6

= {B | B ∈ f (↑⁵ A)}

by the monotonicity of f

= f (↑⁵ A).

(G⁵◦ F⁵)(↑⁵ A) = ↑⁵ {B → C | C ∈↑⁵ A· ↑⁵ B} by definition of F⁵ and G⁵

= ↑⁵ {B → C | B → C ∈↑⁵ A} by Lemma 13

= ↑⁵ A by Lemma 3(1).

Lemma 14 implies that F⁵ induces an extensional λ-model. Let Env_F⁵ be the set of all mappings from the set of term variables to F⁵ and ρ range over Env_F⁵. Via the maps F⁵ and G⁵ we get the standard semantic interpretation [[ ]]⁵ : Λ ×

(12)

Env_F⁵7→F⁵of λ-terms:

[[x]]⁵_ρ = ρ(x);

[[tu]]⁵_ρ = F⁵([[t]]⁵_ρ)([[u]]⁵_ρ);

[[λx.t]]⁵_ρ = G⁵(λλΞ ∈ F⁵.[[t]]⁵_ρ[Ξ/x]).

Actually, by using the Generation Theorem 10, it is easy to prove by induction on λ-terms that:

[[t]]⁵_ρ = {A ∈ TT⁵ | ∃Γ ρ. Γ `⁵ t : A},

where the notation Γ ρ means that for (x : B) ∈ Γ one has that B ∈ ρ(x).

Remark 15 Note that any intersection type theory satisfying Theorem 6 produces a reflexive object in the category of ω-algebraic lattices, and Lemma 3(1) ensures that the retraction pair (G, F) consists of isomorphisms.

We conclude this section with the formal definition of filter models.

Definition 16 (Filter models)

The extensional λ-model hF⁵, ·, [[ ]]⁵i is called the filter model over Σ⁵.

3 Simple Easy Terms and Continuous Predicates

In this section we give the main notion of the paper, namely simple easiness. A term e is simple easy if, given an eitt Σ⁵ and a type E ∈ TT⁵, we can extend in a conservative way Σ⁵ to an eitt Σ⁵⁰, so that [[e]]⁵⁰ = (↑⁵⁰ E) t [[e]]⁵. This allows to build with a uniform technique, the filter models in which the interpretation of e is a filter of types induced by a continuous predicate (see Definition 20).

First we introduce EITT maps: an EITT map applied to an easy intersection type theory and to a type builds a new easy intersection type theory which is a conservative extension of the original one.

Definition 17 (EITT maps)

(1) Let Σ⁵ and Σ⁵⁰ two eitts. We say that Σ⁵⁰ is a conservative extension of Σ⁵ (notation Σ⁵ v Σ⁵⁰) iff CC⁵ ⊆ CC⁵⁰ and for all A, B ∈ TT⁵,

A ≤5 B iff A ≤5⁰ B.

(2) A pointed eitt is a pair (Σ⁵, E) with E ∈ TT⁵.

(13)

(3) An EITT map is a map M : PEITT 7→ EITT, such that for all (Σ⁵, E) Σ⁵ v M(Σ⁵, E),

where EITT and PEITT denote respectively the class of eitts and pointed eitts.

We now give the central notion of simple easy term.

Definition 18 (Simple easy terms) An unsolvable term e is simple easy if there exists an EITT map Mesuch that for all pointed eitt (Σ⁵, E),

`⁵⁰ e : B iff ∃C ∈ TT⁵.C ∩ E ≤5⁰ B & `⁵ e : C, where Σ⁵⁰ = M_e(Σ⁵, E).

Define I ≡ λx.x, W2 ≡ λx.xx, W₃ ≡ λx.xxx, and R_n inductively as R0 = W₂W₂, R_n+1 = R_nR_n. Examples of simple easy terms are W₂W₂ (see next section), W₃W₃I, and R_n for all n [4]. See Lusin [16] for further examples of simple easy terms.

The first key property of simple easy terms is the following.

Theorem 19 With the same notation of previous definition, we have [[e]]⁵⁰ = (↑⁵⁰ E) t [[e]]⁵.

PROOF. (⊇) Taking C = Ω in Definition 18, we have `⁵⁰ e : E. Therefore, (↑⁵⁰ E) ⊆ [[e]]⁵⁰. Since [[e]]⁵ ⊆ [[e]]⁵⁰, we get [[e]]⁵⁰ ⊇ (↑⁵⁰ E) t [[e]]⁵.

(⊆) If B ∈ [[e]]⁵⁰, then `⁵⁰ e : B, hence, by Definition 18, there exists C ∈ TT⁵ such that C ∈ [[e]]⁵and C ∩E ≤5⁰ B. We are done, since C ∩E ∈ (↑⁵⁰ E)t[[e]]⁵⁰.

Finally, we define filters by continuous predicates.

Definition 20 (Continuous predicates) Let P : PEITT 7→ {tt, ff} a predicate. We say that P is continuous iff (as usual P(Σ⁵, E) is short for P(Σ⁵, E) = tt):

(1) Σ⁵ v Σ⁵⁰ & P(Σ⁵, E) ⇒ P(Σ⁵⁰, E) (2) P(Σ⁵^∞, E) ⇒ ∃n.P(Σ⁵ⁿ, E)

where Σ⁵^∞ = Σ(^S_nCC⁵ⁿ,^S_n5_n).

The 5-filter induced by P over Σ⁵is the filter defined by:

Ξ⁵_P =↑⁵ {A ∈ TT⁵ | P(Σ⁵, A)}.

(14)

Note that if we endow PEITT with the Scott topology induced by the ordering (Σ⁵, E) v (Σ⁵⁰, E⁰) iff Σ⁵ v Σ⁵⁰ and E∼5E⁰, then continuous predicates are in one-to-one correspondence with Scott open sets in PEITT.

For the proof of the Main Theorem it is useful to recall some properties of Scott’s λ-model D∞ [20]. We are interested in the inverse limit λ-model D∞, obtained starting from the two point lattice D0 = {⊥, >} and the embedding i₀ : D₀ → [D₀ → D₀] defined by:

i₀(⊥) = ⊥ ⇒ ⊥ i₀(>) = ⊥ ⇒ >

where a ⇒ b is the step function defined by

λd. if a v d then b else ⊥.

It is well-known (and first shown in Wadsworth [21]) that in this model the interpretation of all unsolvable terms is bottom. Moreover this model is isomorphic to the filter model hF⁵⁰, ·, [[ ]]⁵⁰i induced by the eitt Σ⁵⁰ defined by:

CC⁵⁰ = {Ω, ω};

5₀ =5 ∪ {ω ∼ Ω → ω}.

This isomorphism (stated with a proof sketch in Coppo et al. [9] and fully proved in Alessi [2]) is a particular case of the duality discussed in Section 2 of [12].

Therefore we get:

Proposition 21 In the filter model hF⁵⁰, ·, [[ ]]⁵⁰i the interpretation of all unsolv- able terms is ↑⁵⁰ Ω.

Theorem 22 (Main Theorem) Let e be a simple easy term, P : PEITT → {tt, ff}

be a continuous predicate and Ξ⁵_P be the 5-filter induced by P over Σ⁵. Then there is a filter model F⁵ such that

[[e]]⁵ = Ξ⁵_P.

PROOF. Let h·, ·i denote any fixed bijection between IN × IN and IN such that hr, si ≥ r.

We will choose a denumerable sequence of eitts Σ⁵⁰, . . . , Σ⁵^r, . . .. For each r we will consider a fixed enumeration hT_s^(r)i_s∈IN of the set {A ∈ TT⁵^r | P(Σ⁵^r, A)}.

We can construct the model as follows.

step 0: take the eitt Σ⁵⁰ defined as above.

(15)

step (n + 1): if n = hr, si we define Σ⁵ⁿ⁺¹ = M_e(Σ⁵ⁿ, T_s^(r)) (notice that Σ⁵ⁿ v Σ⁵ⁿ⁺¹).

final step: take Σ⁵^∞ = Σ(^S_nCC⁵ⁿ,^S_n5_n).

First we prove that the model F⁵^∞ is non-trivial by showing that [[I]]⁵^∞ 6= [[K]]⁵^∞, where I ≡ λx.x, K ≡ λxy.x. Let D ≡ (ω → ω) → (ω → ω). Since `⁵^∞ I : D, we have that D ∈ [[I]]⁵^∞. On the other hand, if it were D ∈ [[K]]⁵^∞, then there would exist n such that D ∈ [[K]]⁵ⁿ. This would imply (by applying several times the Generation Theorem) ω → ω ≤5n ω. Since we have Σ⁵ⁿ v Σ⁵ⁿ⁺¹ for all n, we should have ω → ω ≤5₀ ω. Since ω ∼5₀ Ω → ω, we should conclude by Theorem 6, Ω ≤50 ω, which is a contradiction. Therefore, we cannot have D ∈ [[K]]⁵^∞ and the model F⁵^∞ is non-trivial.

Now we prove that [[e]]⁵^∞ =↑⁵^∞ {T_s^(r) | r, s ∈ IN} by showing that [[e]]⁵ⁿ =↑⁵ⁿ {T_s^(r) | hr, si < n} for all n. The inclusion (⊇) is immediate by construction. We prove (⊆) by induction on n. If n = 0, then [[e]]⁵⁰ =↑⁵⁰ Ω by Proposition 21.

Suppose the thesis is true for n = hr_n, s_ni and let B ∈ [[e]]⁵ⁿ⁺¹. Then `⁵ⁿ⁺¹ e : B.

This is possible only if there exists C ∈ TT⁵ⁿ such that C ∩ T_s^(r_nⁿ⁾ ≤5n+1 B and moreover `⁵ⁿ e : C. By induction we have C ∈↑⁵ⁿ {T_s^(r) | hr, si < n}, hence T_s^(r₁¹⁾∩ . . . ∩ T_s^(r^k⁾

k ≤5n C for some r₁, . . . , r_k, s₁, . . . , s_kwith hr_i, s_ii < n (1 ≤ i ≤ k). We derive T_s^(r¹⁾

1 ∩ . . . ∩ T_s^(r^k⁾

k ∩ T_s^(rⁿ⁾

n ≤₅_n+1 B, i.e. B ∈↑⁵ⁿ⁺¹ {T_s^(r) | hr, si <

n + 1} .

Finally we show that

A ∈ TT⁵^∞ & P(Σ⁵^∞, A) ⇔ ∃r, s. A ≡ T_s^(r). (⇐) is immediate by Definition 20(1).

We prove (⇒). If A ∈ TT⁵^∞ and P(Σ⁵^∞, A), then by definition of Σ⁵^∞and the con- tinuity of P, it follows that there is r such that A ∈ TT⁵^r and P(Σ⁵^r, A). Therefore by definition of T_s^(r), there is s such that A ≡ T_s^(r).

So we can conclude [[e]]⁵^∞ =↑⁵^∞ {A ∈ TT⁵^∞ | P(Σ⁵^∞, A)}, i.e. [[e]]⁵^∞ = Ξ⁵_P^∞.

4 Consistency of λ-theories

We introduce now a λ-theory whose consistency has been first proved using a suitable filter model in Dezani and Lusin [13]. We obtain the same model here as a consequence of Theorem 22.

(16)

Definition 23 (Theory J ) The λ-theory J is axiomatized by

W4xx = x; W4xy = W4yx; W4x(W4yz) = W4(W4xy)z where W2 ≡ λx.xx and W4 ≡ W2W2.

It is clear that the previous equations hold if the interpretation of W₄ is the join operator on filters. In order to use Theorem 22 we need:

• the join operator on filters to be a filter generated by a continuous predicate;

• W4to be simple easy.

For the first condition it is easy to check that the join relative to F⁵is represented by the filter:

Θ =↑⁵ {A → B → A ∩ B | A, B ∈ TT⁵}.

In fact, by easy calculation we have:

(Θ · Ξ) · Υ = Ξ t Υ

for all filters Ξ, Υ in F⁵. Therefore, the required predicate is P(Σ⁵, C) ⇔ C ≡ A → B → A ∩ B.

It is trivial that the predicate above is continuous.

To show that W4 is simple easy we give a lemma which characterises the types derivable for W₂ and W₄.

Lemma 24

(1) `⁵ W₂ : A → B iff A ≤5 A → B;

(2) `⁵ W₄ : B iff A ≤₅ A → B for some A ∈ TT⁵ such that `⁵ W₂ : A.

(3) If `⁵ W₄ : B then there exists A ∈ TT⁵ such that #(A) = 0, A ≤5 A → B and `⁵ W₂ : A.

PROOF. (1) By a straightforward computation, A ≤5 A → B implies `⁵ W₂ : A → B. Conversely, suppose `⁵ W2 : A → B. If B∼5Ω, then by axioms (Ω), (Ω-η), and rules (η), (trans), we have A ≤5 A → B. Otherwise, by Theorem 10(4) it follows x : A `⁵ xx : B. By Theorem 10(2) there exists a type C ∈ TT⁵ such that x : A `⁵ x : C → B and x : A `⁵ x : C. Notice that B6∼₅Ω implies C → B6∼₅Ω, since from C → B∼5Ω we get C → B∼5Ω → Ω by axiom (Ω-η) and rule (trans) and this implies B∼5Ω by Theorem 6. So by Theorem 10(1), we get A ≤5 C → B. We have A ≤5 C either by Theorem 10(1) if C6∼₅Ω or by axiom (Ω) and rule (trans) if C∼5Ω. From A ≤5 C → B and A ≤5 C by rule (η) it follows A ≤5 A → B.

(17)

(2) The case B∼5Ω is trivial. Otherwise, if `⁵ W₄ : B, by Theorem 10(2) it follows that there exists A ∈ TT⁵ such that `⁵ W₂ : A and `⁵ W₂ : A → B. We conclude by Point (1).

(3) Let `⁵ W₄ : B. Then, by Point (2), the set

Π = {A ∈ TT⁵ | `⁵ W₂ : A and A ≤5 A → B}

is non-empty. Let A ∈ Π be such that #(A) is minimal. We are done if we prove

#(A) = 0. By contradiction, if it is not the case, by applying Lemma 5, we obtain a type A⁰ such that A⁰∼5A, A⁰ ≡ ^T_i∈I(Ci → Di) and #(A⁰) = #(A). From A ≤5 A → B we have ^T_i∈I(C_i → D_i) ≤5 A → B, hence, by Theorem 6,

T

i∈JD_i ≤5 B where J = {i ∈ I | A ≤5 C_i}. Since `⁵ W₂ : A, by (≤5) it follows `⁵ W2 : Ci → Di for all i ∈ J and `⁵ W2 : ^T_i∈JCi. By Point (1) it follows ∀i ∈ J.C_i ≤5 C_i → D_i. By axiom (→ ∩) and rule (η) we get C ≤5 C → ^T_i∈JD_i, and also C ≤5 C → B, where C ≡ ^T_i∈JC_i. We have obtained:

`⁵ W₂ : C;

C ≤5 C → B;

#(C) < #(A⁰) = #(A).

This is a contradiction, since C ∈ Π contradicts the minimality of #(A).

The crucial step for proving simple easiness of W₄ is to find its EITT map.

Definition 25 Let (Σ⁵, E) a pointed eitt and χ /∈ CC⁵. We define MW4(Σ⁵, E) = Σ⁵⁰,

where:

• CC⁵⁰ = CC⁵∪ {χ} ;

• 5⁰ = 5 ∪ {χ ∼ χ → E}.

First we notice that M_W₄ is an EITT map. In fact M_W₄(Σ⁵, E) is an easy intersection type theory by Definition 25. Moreover, it is straightforward to show by induction on derivations that Σ⁵ v M_W₄(Σ⁵, E).

Now we prove that MW4 is an EITT map for W4. Lemma 26 Let Σ⁵⁰ = M_W₄(Σ⁵, E). Then

`⁵⁰ W₄ : B iff ∃C ∈ TT⁵.C ∩ E ≤5⁰ B & `⁵ W₄ : C.

(18)

PROOF. Throughout the proof we use the Generation Theorem and Theorem 6 without explicitly mentioning them each time.

(⇒) Let `⁵⁰ W₄ : B. First we show that there is a type D ∈ TT⁵⁰ such that (a) D ≡^T_i∈I(ϕ_i → F_i) ∩ χ;

(b) ∀i ∈ I.ϕ_i ∈ CC⁵ & F_i ∈ TT⁵; (c) D ≤5⁰ D → B;

(d) `⁵⁰ W₂ : D.

By Lemma 24(3) `⁵⁰ W₄ : B implies that there exists A ∈ TT⁵⁰ such that the following three properties hold:

(i) #(A) = 0;

(ii) A ≤5⁰ A → B;

(iii) `⁵⁰ W₂ : A.

If we consider A⁰ ≡ A ∩ χ, it is easy to check that A⁰ satisfies (i) and (iii) above.

Moreover, (ii) holds for A⁰since by Lemma 3(2) and rules (mon), (η):

A ∩ χ ≤5⁰ (A → B) ∩ (χ → E) ≤5⁰ A ∩ χ → B ∩ E ≤5⁰ A ∩ χ → B.

It must be A⁰ ∼5⁰ (^T_k∈Kφ_k) ∩ χ, with φ_k ∈ CC⁵, φ_k6∼₅0Ω for all k ∈ K, since the unique possible shape for A⁰ is an intersection of constants containing χ. Next, since for each k ∈ K, we have, from the axioms of 5, φ_k ∼5 T

l∈L^(k)(ϕ^(k)_l → F_l^(k)), we can define D ≡^T_k∈K(^T_l∈L(k)(ϕ^(k)_l → F_l^(k)))∩χ. Then, by reindexing the types and using a unique intersection, we get the syntactic shape for D required by conditions (a) and (b). Moreover, conditions (c) and (d) hold since by construction D ∼5 A⁰.

Considering (a), (d), rule (≤5⁰) and Lemma 24(1), we have that for all i ∈ I, ϕ_i ≤5⁰ ϕ_i → F_i. Since Σ⁵ v Σ⁵⁰ and for each i ∈ I, ϕ_i, F_i ∈ TT⁵, it follows that ϕ_i ≤5 ϕ_i → F_i, for all i ∈ I. By applying Lemma 24(1) and rule (∩I), we get

`⁵ W₂ :^T_i∈I(ϕ_i → F_i). This implies by Lemma 3(2) and rule (≤₅)

`⁵ W₂ : (^\

i∈I⁰

ϕ_i) → (^\

i∈I⁰

F_i) for all I⁰ ⊆ I. (1)

Because of (c), (^T_i∈JFi) ∩ E ≤5⁰ B where J = {i ∈ I | D ≤5⁰ ϕi)}. Because of (d) and rule (≤5⁰), it follows `⁵⁰ W₂ :^T_i∈Jϕ_i. Let ϕ_i ≡^T_h∈H(i)(ζ_h⁽ⁱ⁾ → G⁽ⁱ⁾_h ).

Then by rule (≤5⁰), we have `⁵⁰ W₂ : ζ_h⁽ⁱ⁾ → G⁽ⁱ⁾_h for each i ∈ J and h ∈ H⁽ⁱ⁾. By

(19)

Lemma 24(1) it follows, for each i ∈ J and h ∈ H⁽ⁱ⁾, ζ_h⁽ⁱ⁾ ≤5⁰ ζ_h⁽ⁱ⁾ → G⁽ⁱ⁾_h . Using again Σ⁵ v Σ⁵⁰, we have, for each i ∈ J and h ∈ H⁽ⁱ⁾, ζ_h⁽ⁱ⁾ ≤5 ζ_h⁽ⁱ⁾ → G⁽ⁱ⁾_h , hence, by Lemma 24(1), `⁵ W₂ : ζ_h⁽ⁱ⁾ → G⁽ⁱ⁾_h , for each i ∈ J and h ∈ H⁽ⁱ⁾. Therefore, by rule (∩I), we have `⁵ W₂ :^T_i∈J(^T_h∈H(i)(ζ_h⁽ⁱ⁾ → G⁽ⁱ⁾_h )), that is

`⁵ W₂ : ^\

i∈J

ϕ_i. (2)

Applying rule (→ E) to (1) with I⁰ = J and (2), we obtain `⁵ W4 :^T_i∈JFi. Since we have proven (^T_i∈JF_i) ∩ E ≤5⁰ B, we are done, by choosing C ≡^T_i∈JF_i. (⇐) By Theorem 19 we have that `⁵⁰ W₄ : E. Since by hypothesis `⁵ W₄ : C and moreover Σ⁵ v Σ⁵⁰, we obtain `⁵⁰ W4 : C. By applying rule (≤5⁰) we have

`⁵⁰ W₄ : B.

The previous lemma yields the second crucial step in the construction of the model.

Theorem 27 W₄ is simple easy.

We can conclude:

Theorem 28 (Consistency of J ) The λ-theory J is consistent.

Remark 29 The set of all λ-theories is naturally equipped with a structure of com- plete lattice (see Barendregt [7], Chapter 4), with meet u defined as set theoretic intersection. The join t of two λ-theories T and S is the least equivalence relation including T ∪ S. Lusin and Salibra [17] consider the set [J ) of all λ-theories extending J : this is a sublattice of the lattice of λ-theories. They prove that this sublattice has many interesting algebraic properties, due to the validity of the equa- tions defining J (see Definition 23). In particular [J ) satisfies a restricted form of distributivity, called meet semidistributivity, i.e. for all λ-theories T , S, G ∈ [J ), if T u S = T u G, then T u S = T u (S t G).

5 Minimal Fixed Point Operators

In this section we prove that for all simple easy terms e there are filter models F⁵ such that [[e]]⁵ represents the minimal fixed point operator

µ

.

Actually, since [[e]]⁵ ∈ F⁵, while

µ

∈ [[F⁵ → F⁵] → F⁵], the identification between [[e]]⁵and

µ

is possible via the “canonical embedding” of [[F⁵ → F⁵] → F⁵] in F⁵.

(20)

Lemma 14 implies that every “higher order” space can be embedded in a canonical way in F⁵, by defining standard appropriate mappings via F⁵ and G⁵. For instance, in order to embed the space of

µ

, namely [[F⁵ → F⁵] → F⁵], in F⁵, we consider the pair of mappings H⁵ : F⁵ → [[F⁵ → F⁵] → F⁵] and K⁵ : [[F⁵ → F⁵] → F⁵] → F⁵defined as follows:

H⁵(Ξ) = F⁵(Ξ) ◦ G⁵,

K⁵(H) = G⁵◦ λλΞ.(H ◦ F⁵)(Ξ).

It is easy to check that

H⁵◦ K⁵ = id_[[F⁵_→F⁵_]→F⁵_]→[[F⁵_→F⁵_]→F⁵_]. (3)

We say that a filter Ξ represents an operator H ∈ [[F⁵ → F⁵] → F⁵] if H⁵(Ξ) = H. The equality (3) guarantees that each H is represented by K⁵(H).

So the problem of finding a filter model F⁵, such that [[e]]⁵ represents

µ

, can be solved if we find F⁵such that [[e]]⁵ = K⁵(

µ

).

Remark 30 We point out that, given a simple easy term e, the existence of a model F⁵where [[e]]⁵represents

µ

is not trivial at all. A simple easy term e, being easy, can obviously be equated to an arbitrary fixed point combinator Y. This could be useful in view of identifying [[e]] with

µ

, provided that there exists a fixed point combinator ˜Y such that [[ ˜Y]]⁵ represents

µ

in each filter model F⁵. In fact, if there were such a ˜Y, then it would be possible to find a filter model F⁵⁰ such that [[ ˜Y]]⁵⁰ = [[e]]⁵⁰, following the technique of Alessi and Lusin [4]. Therefore we would obtain H⁵⁰([[e]]⁵⁰) =

µ

. Unfortunately, such a ˜Y does not exist. In fact, con- sider the filter model F^{P ark} isomorphic to the Park λ-model D^{P ark} of λ-calculus (see Honsell and Ronchi [14]). As proven in [14], for all closed λ-terms t, [[t]]^{P ark} is above a certain compact element c different from the bottom element. In partic- ular, for all fixed point combinators Y, [[YI]]^{P ark}is above c, where I is the identity combinator. Since

µ

(λλX.X) is obviously the bottom element, we have that it is not possible that H^{P ark}([[Y]]^{P ark}) represents

µ

, since

H^{P ark}([[Y]]^{P ark})(λλX.X) = (F^{P ark}([[Y]]^{P ark}) ◦ G^{P ark})(λλX.X)

= F^{P ark}([[Y]]^{P ark})(G^{P ark}(λλX.X))

= [[Y]]^{P ark}· [[I]]^{P ark}

= [[YI]]^{P ark} w c

where we have used the fact that [[I]]⁵ = G⁵(λλX.X) for all Σ⁵.