**Intersection Types and Domain Operators ?**

### Fabio Alessi

^{a}

### , Mariangiola Dezani-Ciancaglini

^{b}

### , Stefania Lusin

^{c}

a*Dipartimento di Matematica e Informatica, Universit`a di Udine, via delle Scienze 208,*
*33100 Udine, Italy*alessi@dimi.uniud.it

b*Dipartimento di Informatica, Universit`a di Torino, Corso Svizzera 185, 10149 Torino,*
*Italy*dezani@di.unito.it

c*Dipartimento 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.

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 applica- tive 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

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 be-
tween 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^{5} such that e is interpreted as the join operator: the interpretation
[[e]]^{5}of e in F^{5} 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^{5} such that the interpretation [[e]]^{5} of e in F^{5} *is the minimal*
fixed point operator

### µ

(that is### µ

(f ) =^{F}

_{n}f

^{n}(⊥), for all continuous endofunctions f over F

^{5}). 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 dis-
cusses 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 C*C

*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 C**C be a countable set of constants*such that Ω ∈ CC. The intersection type language over CC, denoted by T*T = TT(C*C), 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∈I}Ai with I = {1, . . . , n} and n ≥ 1 is short for ((. . . (A1∩ A2) . . .) ∩ An);

• ^{T}_{i∈I}A_{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^{0} B ≤ B^{0}

A ∩ B ≤ A^{0}∩ B^{0} (idem) A ≤ A ∩ A

(incl_{L}) A ∩ B ≤ A (incl_{R}) A ∩ B ≤ B

(→ ∩) (A → B) ∩ (A → C) ≤ A → B ∩ C (η) A^{0} ≤ A B ≤ B^{0}
A → B ≤ A^{0} → B^{0}

(Ω) A ≤ Ω (Ω-η) Ω ≤ Ω → Ω

Fig. 1. The axioms and rules of 5

* Definition 2 (Easy intersection type theories) Let T*T = TT(C

*C) be an intersection*

*type language. The easy intersection type theory (eitt for short) Σ(CC, 5) over T*T

*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;*

*(2) 5*^{−}*contains axioms of the following two shapes only:*

φ ≤ φ^{0},

φ ∼ ^{T}_{h∈H}(ϕ_{h} → F_{h}).

*where φ, φ*^{0}, ϕ_{h} ∈ C*C, F*_{h} ∈ T*T, and φ, φ*^{0} *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 φ*^{0} ∼ ^{T}_{k∈K}(ϕ^{0}_{k} → F^{0}_{k}*), with*
φ, φ^{0} *6≡ Ω. Then 5*^{−} *contains also φ ≤ φ*^{0} *iff for each k ∈ K, there exists*
h_{k} *∈ H such that ϕ*^{0}_{k} ≤ ϕ_{h}_{k} *and F*_{h}_{k} ≤ F^{0}_{k}*are 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}^{0} and F_{h}_{k} must be constant types for
each k ∈ K.

**Notation When we consider an eitt Σ(C**C, 5), we will write CC^{5} for CC, TT^{5}for TT(CC)
and Σ^{5} for Σ(CC, 5). Moreover A ≤5 B will be short for (A ≤ B) ∈ Σ^{5} and
A∼_{5}B for A ≤_{5} B ≤_{5} 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 suit- able intersections of arrow types. This is stated in the following lemma together with a simple inequality between intersections of arrows and arrows of intersec- tions.

**Lemma 3**

*(1) For all A ∈ T*T^{5}*there are I, and B*_{i}, C_{i} ∈ TT^{5} *such that*
A∼5

\

i∈I

(B_{i} → C_{i}).

*(2) For all J ⊆ I, and A*_{i}, B_{i} ∈ TT^{5}*,*

\

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.

* Definition 4 The mapping # : T*T

^{5}

*→ IN is defined inductively on types as follows:*

#(A) = 0 *if A ∈ C*C^{5};

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

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

* Lemma 5 For all A ∈ T*T

^{5}

*with #(A) ≥ 1 there is B ∈ T*T

^{5}

*such that A∼*5

*B,*B ≡

^{T}

_{i∈I}(C

_{i}→ D

_{i}

*), and #(B) = #(A).*

**PROOF. Let A ≡ (**^{T}_{j∈J}(C_{j}^{0} → D^{0}_{j})) ∩ (^{T}_{h∈H}φh), where C_{j}^{0}, D^{0}_{j} ∈ TT^{5}, φh ∈ CC^{5}.
For each h ∈ H there are I^{(h)}, ϕ^{(h)}_{i} ∈ CC^{5}, F_{i}^{(h)} ∈ TT^{5}, such that

φ_{h}∼5

\

i∈I^{(h)}

(ϕ^{(h)}_{i} → F_{i}^{(h)}).

We can choose

B ≡ (^{\}

j∈J

(C_{j}^{0} → D^{0}_{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 A*i, Bi, C, D ∈ TT

^{5}

*,*

\

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.

**Definition 7 (Basis)** *A 5-basis is a (possibly infinite) set of statements of the*
*shape x : A, where A ∈ T*T^{5}*, 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^{5} then Γ, x : A is short for Γ ∪ {x : A} when x /∈ Γ.

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

(Ax) (x : A) ∈ Γ

Γ `^{5} x : A *(Ax-Ω) Γ `*^{5} t : Ω
(→ I) Γ, x : A `^{5} t : B

Γ `^{5} λx.t : A → B (→ E) Γ `^{5} t : A → B Γ `^{5} u : A
Γ `^{5} tu : B

(∩I) Γ `^{5} t : A Γ `^{5} t : B

Γ `^{5} t : A ∩ B (≤5) Γ `^{5} t : A A ≤_{5} B
Γ `^{5} t : B

**Example 9 Self-application can be easily typed in all λ∩**^{5}*, as follows.*

x : (A → B) ∩ A `^{5}x : (A → B) ∩ A
(≤5)
x : (A → B) ∩ A `^{5} x : A → B

x : (A → B) ∩ A `^{5}x : (A → B) ∩ A
(≤5)
x : (A → B) ∩ A `^{5}x : A

(→ E)
x : (A → B) ∩ A `^{5}xx : B

(→ I)

`^{5} λ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) Γ `^{5} t : A ∩ B
Γ `^{5} t : A

Γ `^{5} t : A ∩ B
Γ `^{5} t : B
are derivable^{1} in any λ∩^{5}.

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.

(≤∇L) Γ, x : A ` t : B A^{0} ≤∇ A
Γ, x : A^{0} ` 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∼*_{5}*Ω. Then Γ `*^{5} *x : A iff (x : B) ∈ Γ and B ≤*5 *A for some*
B ∈ TT^{5}*.*

*(2) Γ `*^{5} *tu : A iff Γ `*^{5} *t : B → A, and Γ `*^{5} *u : B for some B ∈ T*T^{5}*.*

*(3) Γ `*^{5} *λx.t : A iff Γ, x : B*_{i} `^{5} t : C_{i} *and*^{T}_{i∈I}(B_{i} → C_{i}) ≤5 *A, for some I*
*and B*_{i}, C_{i} ∈ TT^{5}*.*

*(4) Γ `*^{5} *λx.t : B → C iff Γ, x : B `*^{5} *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∼_{5}Ω implies that
Γ `^{5} x : A cannot be obtained just using axiom (Ax-Ω).

*(2) If A∼*5Ω we can choose B∼_{5}Ω. Otherwise, the proof is by induction on deriva-
tions. The only interesting case is when A ≡ A_{1} ∩ A_{2} and the last applied rule is
(∩I):

(∩I) Γ `^{5} tu : A_{1} Γ `^{5} tu : A_{2}
Γ `^{5} tu : A_{1}∩ A_{2} .

The condition A6∼_{5}Ω implies that we cannot have A_{1}∼5A_{2}∼5Ω. We give the
proof for A16∼_{5}Ω and A_{2}6∼_{5}Ω, the other cases can be treated similarly. By induc-
tion there are B_{1}, B_{2}such that

Γ `^{5} t : B_{1} → A_{1}, Γ `^{5} u : B_{1},
Γ `^{5} t : B_{2} → A_{2}, Γ `^{5} u : B_{2}.

Then Γ `^{5} t : (B_{1} → A_{1}) ∩ (B_{2} → A_{2}*) and by Lemma 3(2) and rule (η)*
(B_{1} → A_{1}) ∩ (B_{2} → A_{2}) ≤_{5} B_{1}∩ B_{2} → A_{1}∩ A_{2} ≤ B_{1} ∩ B_{2} → A.

We are done, since Γ `^{5} u : B1∩ B2 by rule (∩I) .

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

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

(∩I) Γ `^{5} λx.t : A1 Γ `^{5} λx.t : A2

Γ `^{5} λx.t : A_{1}∩ A_{2} .
By induction there are I, B_{i}, C_{i}, J, D_{j}, G_{j} such that

∀i ∈ I. Γ, x : B_{i} `^{5} t : C_{i}, ∀j ∈ J. Γ, x : D_{j} `^{5} t : G_{j},

T

i∈I(B_{i} → C_{i}) ≤5 A_{1} & ^{T}_{j∈J}(D_{j} → G_{j}) ≤5 A_{2}.
So we are done since (^{T}_{i∈I}(B_{i} → C_{i})) ∩ (^{T}_{j∈J}(D_{j} → G_{j})) ≤_{5} 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∈J}C_{i} ≤5

C where J = {i ∈ I | B ≤5 B_{i}}. From Γ, x : B_{i} `^{5} t : C_{i} we can derive
Γ, x : B `^{5} t : C_{i} by rule (≤∇ L), so by (∩I) we have Γ, x : B `^{5} t : ^{T}_{i∈J}C_{i}.
Finally applying rule (≤5) we can conclude Γ, x : B `^{5} 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 T*T^{5}*) is a set Ξ ⊆ T*T^{5} *such that:*

*• Ω ∈ Ξ;*

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

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

*(2) F*^{5}*denotes the set of 5-filters over T*T^{5}*;*

*(3) if Ξ ⊆ T*T^{5}*, ↑*^{5} *Ξ denotes the 5-filter generated by Ξ;*

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

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

on TT^{5} by ∼5. That means that compact elements are the filters of the form ↑^{5} A
for some type A, the top element is TT^{5}, and the bottom element is ↑^{5} Ω. 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 Υ = ↑^{5} (Ξ ∪ Υ)
Ξ 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^{5} → F^{5}] and vice versa.

**Definition 12 (Application)**

*(1) Application · : F*^{5}× F^{5} 7→ F^{5}*is defined as*

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

*(2) The continuous maps F*^{5} : F^{5} 7→ [F^{5} → F^{5}*] and G*^{5} : [F^{5} → F^{5}] 7→ F^{5}
*are defined as:*

F^{5}(Ξ) = λλΥ ∈ F^{5}.Ξ · Υ;

G^{5}(f ) =↑^{5} {A → B | B ∈ f (↑^{5} 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 Σ**^{5}*be an eitt, Ξ ∈ F*^{5} *and C ∈ T*T^{5}*. Then*
B ∈ Ξ· ↑^{5} C *iff* C → B ∈ Ξ.

**PROOF.**

B ∈ Ξ· ↑^{5} C ⇔ ∃C^{0}.C ≤5 C^{0} & C^{0} → B ∈ Ξ by definition of application

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

As expected, F^{5}and G^{5}are inverse to each other.

**Lemma 14**

F^{5} ◦ G^{5} *= id*_{[F}^{5}_{→F}^{5}_{]};
G^{5} ◦ F^{5} *= id*_{F}^{5}.

**PROOF. It suffices to consider compact elements.**

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

by definition of F^{5} and Lemma 13

= {B | A → B ∈↑^{5} {A^{0} → B^{0} | B^{0} ∈ f (↑^{5} A^{0})}}

by definition of G^{5}

= {B | ∃I, A_{i}, B_{i}.(∀i ∈ I.B_{i} ∈ f (↑^{5} 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 (↑^{5} A_{i}))

&^{T}_{i∈J}B_{i} ≤_{5} B}

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

= {B | B ∈ f (↑^{5} A)}

by the monotonicity of f

= f (↑^{5} A).

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

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

= ↑^{5} A *by Lemma 3(1).*

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

Env_{F}^{5}7→F^{5}of λ-terms:

[[x]]^{5}_{ρ} = ρ(x);

[[tu]]^{5}_{ρ} = F^{5}([[t]]^{5}_{ρ})([[u]]^{5}_{ρ});

[[λx.t]]^{5}_{ρ} = G^{5}(λλΞ ∈ F^{5}.[[t]]^{5}_{ρ[Ξ/x]}).

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

[[t]]^{5}_{ρ} = {A ∈ TT^{5} | ∃Γ ρ. Γ `^{5} 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*^{5}, ·, [[ ]]^{5}*i is called the filter model over Σ*^{5}*.*

**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 Σ^{5} and a type E ∈ TT^{5}, we can extend in a
conservative way Σ^{5} to an eitt Σ^{5}^{0}, so that [[e]]^{5}^{0} = (↑^{5}^{0} E) t [[e]]^{5}. 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 conser-
vative extension of the original one.

**Definition 17 (EITT maps)**

*(1) Let Σ*^{5} *and Σ*^{5}^{0} *two eitts. We say that Σ*^{5}^{0} *is a conservative extension of Σ*^{5}
*(notation Σ*^{5} v Σ^{5}^{0}*) iff C*C^{5} ⊆ CC^{5}^{0} *and for all A, B ∈ T*T^{5}*,*

A ≤5 *B iff A ≤*5^{0} B.

*(2) A pointed eitt is a pair (Σ*^{5}*, E) with E ∈ T*T^{5}*.*

*(3) An EITT map is a map M : PEITT 7→ EITT, such that for all (Σ*^{5}, E)
Σ^{5} v M(Σ^{5}, 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 M*e*such that for all pointed eitt (Σ*^{5}*, E),*

`^{5}^{0} *e : B iff ∃C ∈ T*T^{5}.C ∩ E ≤5^{0} B & `^{5} e : C,
*where Σ*^{5}^{0} = M_{e}(Σ^{5}*, E).*

Define I ≡ λx.x, W2 ≡ λx.xx, W_{3} ≡ λx.xxx, and R_{n} inductively as R0 =
W_{2}W_{2}, R_{n+1} = R_{n}R_{n}. Examples of simple easy terms are W_{2}W_{2} (see next
section), W_{3}W_{3}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]]

^{5}

^{0}= (↑

^{5}

^{0}E) t [[e]]

^{5}.

**PROOF. (⊇) Taking C = Ω in Definition 18, we have `**^{5}^{0} e : E. Therefore,
(↑^{5}^{0} E) ⊆ [[e]]^{5}^{0}. Since [[e]]^{5} ⊆ [[e]]^{5}^{0}, we get [[e]]^{5}^{0} ⊇ (↑^{5}^{0} E) t [[e]]^{5}.

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

*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(Σ*^{5}*, E) is short for P(Σ*^{5}*, E) = tt):*

*(1) Σ*^{5} v Σ^{5}^{0} & P(Σ^{5}, E) ⇒ P(Σ^{5}^{0}, E)
*(2) P(Σ*^{5}^{∞}, E) ⇒ ∃n.P(Σ^{5}^{n}, E)

*where Σ*^{5}^{∞} = Σ(^{S}_{n}CC^{5}^{n},^{S}_{n}5_{n}*).*

*The 5-filter induced by P over Σ*^{5}*is the filter defined by:*

Ξ^{5}_{P} =↑^{5} {A ∈ TT^{5} | P(Σ^{5}, A)}.

*Note that if we endow PEITT with the Scott topology induced by the ordering*
(Σ^{5}, E) v (Σ^{5}^{0}, E^{0}) iff Σ^{5} v Σ^{5}^{0} and E∼5E^{0}, 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_{0} : D_{0} →
[D_{0} → D_{0}] defined by:

i_{0}(⊥) = ⊥ ⇒ ⊥
i_{0}(>) = ⊥ ⇒ >

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 inter-
pretation of all unsolvable terms is bottom. Moreover this model is isomorphic to
the filter model hF^{5}^{0}, ·, [[ ]]^{5}^{0}i induced by the eitt Σ^{5}^{0} defined by:

CC^{5}^{0} = {Ω, ω};

5_{0} =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**^{5}^{0}, ·, [[ ]]^{5}^{0}*i the interpretation of all unsolv-*
*able terms is ↑*^{5}^{0} *Ω.*

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

*be a continuous predicate and Ξ*^{5}_{P} *be the 5-filter induced by P over Σ*^{5}*. Then there*
*is a filter model F*^{5} *such that*

[[e]]^{5} = Ξ^{5}_{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 Σ^{5}^{0}, . . . , Σ^{5}^{r}, . . .. For each r we
will consider a fixed enumeration hT_{s}^{(r)}i_{s∈}IN of the set {A ∈ TT^{5}^{r} | P(Σ^{5}^{r}, A)}.

We can construct the model as follows.

**step 0: take the eitt Σ**^{5}^{0} defined as above.

**step (n + 1): if n = hr, si we define Σ**^{5}^{n+1} = M_{e}(Σ^{5}^{n}, T_{s}^{(r)}) (notice that Σ^{5}^{n} v
Σ^{5}^{n+1}).

**final step: take Σ**^{5}^{∞} = Σ(^{S}_{n}CC^{5}^{n},^{S}_{n}5_{n}).

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

Now we prove that [[e]]^{5}^{∞} =↑^{5}^{∞} {T_{s}^{(r)} | r, s ∈ IN} by showing that [[e]]^{5}^{n} =↑^{5}^{n}
{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]]^{5}^{0} =↑^{5}^{0} Ω by Proposition 21.

Suppose the thesis is true for n = hr_{n}, s_{n}i and let B ∈ [[e]]^{5}^{n+1}. Then `^{5}^{n+1} e : B.

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

k ≤5n C for some r_{1}, . . . , r_{k}, s_{1}, . . . , s_{k}with hr_{i}, s_{i}i < n (1 ≤ i ≤
k). We derive T_{s}^{(r}^{1}^{)}

1 ∩ . . . ∩ T_{s}^{(r}^{k}^{)}

k ∩ T_{s}^{(r}^{n}^{)}

n ≤_{5}_{n+1} B, i.e. B ∈↑^{5}^{n+1} {T_{s}^{(r)} | hr, si <

n + 1} .

Finally we show that

A ∈ TT^{5}^{∞} & P(Σ^{5}^{∞}, A) ⇔ ∃r, s. A ≡ T_{s}^{(r)}.
*(⇐) is immediate by Definition 20(1).*

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

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

**4** **Consistency of λ-theories**

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

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

W4xx = x; W4xy = W4yx; W4x(W4yz) = W4(W4xy)z
*where W*2 *≡ λx.xx and W*4 ≡ W2W2*.*

It is clear that the previous equations hold if the interpretation of W_{4} 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^{5}is represented
by the filter:

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

In fact, by easy calculation we have:

(Θ · Ξ) · Υ = Ξ t Υ

for all filters Ξ, Υ in F^{5}. Therefore, the required predicate is
P(Σ^{5}, 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_{2} and W_{4}.

**Lemma 24**

*(1) `*^{5} W_{2} *: A → B iff A ≤*5 *A → B;*

*(2) `*^{5} W_{4} *: B iff A ≤*_{5} *A → B for some A ∈ T*T^{5} *such that `*^{5} W_{2} *: A.*

*(3) If `*^{5} W_{4} *: B then there exists A ∈ T*T^{5} *such that #(A) = 0, A ≤*5 A → B
*and `*^{5} W_{2} *: A.*

* PROOF. (1) By a straightforward computation, A ≤*5 A → B implies `

^{5}W

_{2}: A → B. Conversely, suppose `

^{5}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 `*

^{5}

*xx : B. By Theorem 10(2) there exists a type C ∈ T*T

^{5}such that x : A `

^{5}x : C → B and x : A `

^{5}x : C. Notice that B6∼

_{5}Ω implies C → B6∼

_{5}Ω, 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∼*

_{5}Ω 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.

*(2) The case B∼*5Ω is trivial. Otherwise, if `^{5} W_{4} *: B, by Theorem 10(2) it*
follows that there exists A ∈ TT^{5} such that `^{5} W_{2} : A and `^{5} W_{2} : A → B. We
*conclude by Point (1).*

*(3) Let `*^{5} W_{4} *: B. Then, by Point (2), the set*

Π = {A ∈ TT^{5} | `^{5} W_{2} : 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^{0} such that A^{0}∼5A, A^{0} ≡ ^{T}_{i∈I}(Ci → Di) and #(A^{0}) = #(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 `^{5} W_{2} : A, by (≤5)
it follows `^{5} W2 : Ci → Di for all i ∈ J and `^{5} W2 : ^{T}_{i∈J}Ci. 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∈J}D_{i}, and also C ≤5 C → B, where C ≡ ^{T}_{i∈J}C_{i}. We have
obtained:

`^{5} W_{2} : C;

C ≤5 C → B;

#(C) < #(A^{0}) = #(A).

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

The crucial step for proving simple easiness of W_{4} is to find its EITT map.

**Definition 25 Let (Σ**^{5}*, E) a pointed eitt and χ /*∈ CC^{5}*. We define*
MW4(Σ^{5}, E) = Σ^{5}^{0},

*where:*

• CC^{5}^{0} = CC^{5}*∪ {χ} ;*

• 5^{0} *= 5 ∪ {χ ∼ χ → E}.*

First we notice that M_{W}_{4} is an EITT map. In fact M_{W}_{4}(Σ^{5}, E) is an easy inter-
section type theory by Definition 25. Moreover, it is straightforward to show by
induction on derivations that Σ^{5} v M_{W}_{4}(Σ^{5}, E).

Now we prove that MW4 is an EITT map for W4.
**Lemma 26 Let Σ**^{5}^{0} = M_{W}_{4}(Σ^{5}*, E). Then*

`^{5}^{0} W_{4} *: B iff ∃C ∈ T*T^{5}.C ∩ E ≤5^{0} B & `^{5} W_{4} : C.

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

(⇒) Let `^{5}^{0} W_{4} : B. First we show that there is a type D ∈ TT^{5}^{0} such that
(a) D ≡^{T}_{i∈I}(ϕ_{i} → F_{i}) ∩ χ;

(b) ∀i ∈ I.ϕ_{i} ∈ CC^{5} & F_{i} ∈ TT^{5};
(c) D ≤5^{0} D → B;

(d) `^{5}^{0} W_{2} : D.

*By Lemma 24(3) `*^{5}^{0} W_{4} : B implies that there exists A ∈ TT^{5}^{0} such that the
following three properties hold:

(i) #(A) = 0;

(ii) A ≤5^{0} A → B;

(iii) `^{5}^{0} W_{2} : A.

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

Moreover, (ii) holds for A^{0}*since by Lemma 3(2) and rules (mon), (η):*

A ∩ χ ≤5^{0} (A → B) ∩ (χ → E) ≤5^{0} A ∩ χ → B ∩ E ≤5^{0} A ∩ χ → B.

It must be A^{0} ∼5^{0} (^{T}_{k∈K}φ_{k}) ∩ χ, with φ_{k} ∈ CC^{5}, φ_{k}6∼_{5}0Ω for all k ∈ K, since
the unique possible shape for A^{0} 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^{0}.

Considering (a), (d), rule (≤5^{0}*) and Lemma 24(1), we have that for all i ∈ I,*
ϕ_{i} ≤5^{0} ϕ_{i} → F_{i}. Since Σ^{5} v Σ^{5}^{0} and for each i ∈ I, ϕ_{i}, F_{i} ∈ TT^{5}, it follows that
ϕ_{i} ≤5 ϕ_{i} → F_{i}*, for all i ∈ I. By applying Lemma 24(1) and rule (∩I), we get*

`^{5} W_{2} :^{T}_{i∈I}(ϕ_{i} → F_{i}*). This implies by Lemma 3(2) and rule (≤*_{5})

`^{5} W_{2} : (^{\}

i∈I^{0}

ϕ_{i}) → (^{\}

i∈I^{0}

F_{i}) for all I^{0} ⊆ I. (1)

Because of (c), (^{T}_{i∈J}Fi) ∩ E ≤5^{0} B where J = {i ∈ I | D ≤5^{0} ϕi)}. Because
of (d) and rule (≤5^{0}), it follows `^{5}^{0} W_{2} :^{T}_{i∈J}ϕ_{i}. Let ϕ_{i} ≡^{T}_{h∈H}(i)(ζ_{h}^{(i)} → G^{(i)}_{h} ).

Then by rule (≤5^{0}), we have `^{5}^{0} W_{2} : ζ_{h}^{(i)} → G^{(i)}_{h} for each i ∈ J and h ∈ H^{(i)}. By

*Lemma 24(1) it follows, for each i ∈ J and h ∈ H*^{(i)}, ζ_{h}^{(i)} ≤5^{0} ζ_{h}^{(i)} → G^{(i)}_{h} . Using
again Σ^{5} v Σ^{5}^{0}, we have, for each i ∈ J and h ∈ H^{(i)}, ζ_{h}^{(i)} ≤5 ζ_{h}^{(i)} → G^{(i)}_{h} ,
*hence, by Lemma 24(1), `*^{5} W_{2} : ζ_{h}^{(i)} → G^{(i)}_{h} , for each i ∈ J and h ∈ H^{(i)}.
Therefore, by rule (∩I), we have `^{5} W_{2} :^{T}_{i∈J}(^{T}_{h∈H}(i)(ζ_{h}^{(i)} → G^{(i)}_{h} )), that is

`^{5} W_{2} : ^{\}

i∈J

ϕ_{i}. (2)

Applying rule (→ E) to (1) with I^{0} = J and (2), we obtain `^{5} W4 :^{T}_{i∈J}Fi. Since
we have proven (^{T}_{i∈J}F_{i}) ∩ E ≤5^{0} B, we are done, by choosing C ≡^{T}_{i∈J}F_{i}.
(⇐) By Theorem 19 we have that `^{5}^{0} W_{4} : E. Since by hypothesis `^{5} W_{4} : C
and moreover Σ^{5} v Σ^{5}^{0}, we obtain `^{5}^{0} W4 : C. By applying rule (≤5^{0}) we have

`^{5}^{0} W_{4} : B.

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

**Theorem 27 W**_{4} *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^{5}
such that [[e]]^{5} represents the minimal fixed point operator

### µ

.Actually, since [[e]]^{5} ∈ F^{5}, while

### µ

∈ [[F^{5}→ F

^{5}] → F

^{5}], the identification between [[e]]

^{5}and

### µ

is possible via the “canonical embedding” of [[F^{5}→ F

^{5}] → F

^{5}] in F

^{5}.

Lemma 14 implies that every “higher order” space can be embedded in a canon-
ical way in F^{5}, by defining standard appropriate mappings via F^{5} and G^{5}. For
instance, in order to embed the space of

### µ

, namely [[F^{5}→ F

^{5}] → F

^{5}], in F

^{5}, we consider the pair of mappings H

^{5}: F

^{5}→ [[F

^{5}→ F

^{5}] → F

^{5}] and K

^{5}: [[F

^{5}→ F

^{5}] → F

^{5}] → F

^{5}defined as follows:

H^{5}(Ξ) = F^{5}(Ξ) ◦ G^{5},

K^{5}(H) = G^{5}◦ λλΞ.(H ◦ F^{5})(Ξ).

It is easy to check that

H^{5}◦ K^{5} *= id*_{[[F}^{5}_{→F}^{5}_{]→F}^{5}_{]→[[F}^{5}_{→F}^{5}_{]→F}^{5}_{]}. (3)

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

So the problem of finding a filter model F^{5}, such that [[e]]^{5} represents

### µ

, can be solved if we find F^{5}such that [[e]]

^{5}= K

^{5}(

### µ

).* Remark 30 We point out that, given a simple easy term e, the existence of a model*
F

^{5}

*where [[e]]*

^{5}

*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]]

^{5}

*represents*

### µ

*in each filter model F*

^{5}

*. In fact, if*

*there were such a ˜Y, then it would be possible to find a filter model F*

^{5}

^{0}

*such*

*that [[ ˜*Y]]

^{5}

^{0}= [[e]]

^{5}

^{0}

*, following the technique of Alessi and Lusin [4]. Therefore we*

*would obtain H*

^{5}

^{0}([[e]]

^{5}

^{0}) =

### µ

*. 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]]*^{5} = G^{5}*(λλX.X) for all Σ*^{5}*.*