Lambda-Calculus and Type Theory Part II

Lambda-Calculus and Type Theory Part II

Ugo Dal Lago

Scuola Estiva AILA, Gargnano, August 2018

Propositional Intuitionistic Logic: Natural Deduction

I Formulas are derived by the grammar

ϕ ::= ⊥

|

|

|

|

I Judgments have the form Γ ` ϕ, where Γ is a finite set of formulas. Given two such sets Γ and ∆, their union is indicated as Γ, ∆.

I The rules of propositional intuitionistic logic are as follows:

Γ, ϕ ` ϕ AX Γ, ϕ ` τ

Γ ` ϕ → τ I → Γ ` ϕ → τ Γ ` ϕ

Γ ` τ E →

Γ ` ϕ Γ ` τ

Γ ` ϕ ∧ τ I∧ Γ ` ϕ ∧ τ

Γ ` ϕ EL∧ Γ ` ϕ ∧ τ Γ ` τ ER∧ Γ ` ϕ

Γ ` ϕ ∨ τ IL∨ Γ ` τ

Γ ` ϕ ∨ τ IR∨ Γ ` ϕ Γ ` τ Γ, ϕ ∨ τ ` ρ

Γ ` ρ E∨

Γ ` ⊥ Γ ` ϕ E⊥

Propositional Intuitionistic Logic: Semantics

I Heyting Algebras

I Distributive lattices with top and bottom elements, in which relative pseudo-complement always exist.

I Meet and joins interpret conjunctions and disjunctions, respectively. Implication is given semantics by way of pseudo-complements.

I Γ |= ϕ indicates that every Heyting Algebra validating Γ also validates ϕ.

I Kripke Semantics

I Propositional variables are put in relation with the elements of a partial order or possible worlds.

I Conjuction and disjuction are interpreted in Tarski-style, while implication is given semantics by way of the underlying partial order

I Γ ϕ indicates that every Kripke model validating Γ also validates ϕ.

Theorem (Completeness)

Γ ` ϕ if and only if Γ |= ϕ if and only if Γ ϕ.

Simply-Typed λ-Calculus à la Curry

I An implicational propositional formula is called a simple type. The set of all simple types is denoted by Φ_→.

I An environment is a finite set Γ of pairs of the form {x₁: ϕ1, · · · , xn: ϕn}, where the x_i are distinct variables and ϕ_i are simple types. In this case, dom(Γ) is

{x₁, · · · , x_n}.

I A typing judgement is a triple Γ ` M : ϕ, consisting of an environment, a λ-term and a simple type.

I The rules are as follows:

Γ, x : ϕ ` x : ϕ V Γ, x : ϕ ` M : τ

Γ ` λxM : ϕ → τ λ Γ ` M : ϕ → τ Γ ` N : ϕ

Γ ` M N : τ @

I The obtained calculus is referred to as ST_→.

Subject Reduction

Lemma (Generation Lemma) Suppose that Γ ` M : ϕ. Then:

1. If M is a variable x, then Γ(x) = ϕ;

2. If M is an application N L, then there is τ such that Γ ` N : τ → ϕ and Γ ` L : τ ;

3. If M is an abstraction λxN and x /∈ dom(Γ), then ϕ = τ → ρ, where Γ, x : τ ` N : ρ.

Lemma (Substitution Lemma)

1. If Γ ` M : ϕ and Γ(x) = ∆(x) for every x ∈ FV (M ), then

∆ ` M : ϕ

2. If Γ, x : ϕ ` M : τ and Γ ` N : ϕ, then Γ ` M [x := N ] : τ . Theorem (Subject Reduction Theorem)

If Γ ` M : ϕ and Mβ N , then Γ ` N : ϕ.

Simply-Typed λ-Calculus à la Church

I Preterms of the simply-typed λ-calculus à la Church are defined as follows:

M ::= x

|

|

I The notions of substitution, α-conversion, term, and reduction can be generalised to terms à la Church.

I Typing rules are the obvious ones:

Γ, x : ϕ ` x : ϕ V Γ, x : ϕ ` M : τ

Γ ` λx : ϕM : ϕ → τ λ Γ ` M : ϕ → τ Γ ` N : ϕ

Γ ` M N : τ @

I The Subject Reduction Theorem can be easily reproved.

Curry vs. Church

Proposition

In the Simply-Typed λ-calculus à la Church, if Γ ` M : ϕ and Γ ` M : τ , then ϕ = τ .

I The erasing map | · | from terms à la Church to terms à la Curry is defined by induction on the structure of terms, as follows:

|x| := x |λx : ϕM | := λx|M | |M N | := |M ||N |

I Typability and reduction judgments in the two styles can be translated into each other relatively easily.

Weak Normalisation

Theorem

Every term typable in ST_→ has a normal form.

I The proof is based on the following key ideas:

I One can assign to each typable term M , a pair natural numbers m_M := (δ_M, n_M) in such a way that if M is not a normal form, then there is N with M →_βN and

mM > mN in the lexicographic order.

I Then, one proves the statement for every typable term M by lexicographic induction on mM.

I This is not a proof of strong normalisation.

Strong Normalisation

Theorem

Every term typable in ST_→ is strongly normalising.

I A Proof Based on Reducibility.

I For every type ϕ, a set of terms Redϕ, the reducible terms;

I A proof that any term of type ϕ is in Redϕ;

I A proof that any term in Redϕ is strongly normalizing.

I A Proof through λI

I η-reduction is the smaller compatible relation →_η including pairs of the form λx(M x) →_η M (where x /∈ FV (M ). →_βη is the union of →_β and →_η.

I In the λI-calculus, one can form an abstraction λxM only if x ∈ FV (M ).

I In the λI-calculus, WNβ= SNβ.

The Church-Rosser Property

I Let → be a binary relation on a set X.

I → has the Church-Rosser property (CR) iff for all

a, b, c ∈ X such that a →⁺b and a →⁺c there is d such that b →⁺d and c →⁺d.

I → has the Weak Church-Rosser property (WCR) iff for all a, b, c ∈ X such that a → b and a → c there is d such that b →⁺d and c →⁺d.

I → is strongly normalizing (SN) iff there is no infinite sequence a1→ a2→ · · · .

Proposition (Newman’s Lemma)

Let → be a binary relation satisfying SN. If → satisfies WCR, then → satisfies CR.

Theorem

Church-style ST_→ is WCR, thus CR.

Expressivity

I The normal form of a term of length n can in the worst case have size

2

2^{. .}

.2)

Θ(n) times

which is higher (as a function on n) than any elementary function.

Theorem (Statman)

The problem of deciding whether any two given Church-style terms M and N of the same type are beta-equal is of

nonelementary complexity.

Expressivity

I Let int = (p → p) → (p → p), where p is an arbitrary type variable. A function f : N^k→ N is ST→-definable if there is a term M_f with ∅ ` M_f : int^k→ int such that

Mfn1· · · n_kβ f (n1, . . . , nk)

I The class of extended polynomials is the smallest class of functions over N which is closed under compositions and contains the constant functions, projections, addition, multiplication, and the conditional function

cond (n, m, p) =

 m if n = 0;

p otherwise.

Theorem (Schwichtenberg)

The ST_→-definable functions are exactly the extended polynomials.

The Curry-Howard Correspondence

I If Γ = {x₁ : ϕ₁, · · · , x_n: ϕ_n}, then rg(Γ) is the set of implicational propositional formulas {ϕ₁, . . . , ϕn}.

Proposition (Curry-Howard Isomorphism) 1. If Γ ` M : ϕ in ST<sub>→</sub>, then rg(Γ) ` ϕ in IPL_→.

2. If Γ ` ϕ in IPL_→, then there are ∆, M with rg (∆) = Γ and

∆ ` M : ϕ.

Corollary

IPL→ is consistent.

The Curry-Howard Correspondence

I The one we presented is not an isomorphism between proofs of IPL_→ and terms of ST_→.

I Getting an exact isomorphism requires altering the way we presented natural deduction:

[ϕ]ⁱ ....

ϕ → τ (i)τ

ϕ → τ ϕ τ

I What corresponds to β-reduction is the following rule:

....

ϕ [ϕ]ⁱ

....

ϕ → τ (i)τ τ

⇒ ....

ϕ..

τ..

Hilbert-Style Proofs

I Logical axioms are defined as all those instances of the following t two schemes:

ϕ → τ → ϕ; (A1 )

(ϕ → τ → ρ) → (ϕ → τ ) → ϕ → ρ; (A2 )

I The Hilbert-Style rules for propositional intuitionistic logic are as follows:

Γ, ϕ `_H ϕ

ϕ is a logical axiom Γ `_H ϕ

Γ `<sub>H</sub> ϕ → τ Γ `_H ϕ Γ `_H τ

Theorem (Deduction Theorem) If Γ, ϕ `<sub>H</sub> τ , then Γ `_H ϕ → τ . Theorem

Γ `<sub>H</sub> ϕ iff Γ ` ϕ

Combinatory Logic

I Terms of combinatory logic are defined as follows:

M ::= x

|

|

|

I The relation →_w is the least compatible relation on combinatory logic terms such that

KM N →w M ; SM N L →w M L(N L).

As usual,w is the reflexive and transitive closure of →_w.

I The notions of normal forms, weak normalization and strong normalization are defined as usual.

Typed Combinatory Logic

I Typing Rules for Combinatory Logic Terms are defined as follows:

Γ, x : ϕ ` x : ϕ V

Γ ` S : (ϕ → τ → ρ) → (ϕ → τ ) → ϕ → ρ S

Γ ` K : ϕ → τ → ϕ K Γ ` M : ϕ → τ Γ ` N : ϕ Γ ` M N : τ @

Theorem (Subject Reduction)

If Γ ` M : ϕ and Mw N , then Γ ` N : ϕ.

Theorem (Strong Normalization)

Γ ` M : ϕ, then M is strongly normalizing.