Lambda-Calculus and Type Theory Part III

Lambda-Calculus and Type Theory Part III

Ugo Dal Lago

Scuola Estiva AILA, Gargnano, August 2018

Section 1

Classical Logic and the λµ-Calculus

Propositional Classical Logic

I If we restrict our attention to the fragment with implication and ⊥, we get the system CPL_→,⊥, which is defined as follows:

Γ, ϕ ` ϕ AX Γ, ϕ → ⊥ ` ⊥

Γ ` ϕ E¬

Γ, ϕ ` τ

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

Γ ` τ E →

I Rule E¬ subsumes E⊥. Moreover, the following two rules are equivalent to it:

Γ ` ⊥ Γ ` ϕ

Γ, ϕ → τ ` ϕ Γ ` ϕ

Theorem

Propositional classical logic is sound and complete for classical validity.

The λµ-Calculus

I Terms of the Church-style λµ-calculus are the following ones:

M ::= x

|

|

|

([a]M )

|

I a ranges over a set Ξ of addresses;

I ϕ ranges over CPL_→,⊥formulas.

I The notions of α-conversion and substitution can be generalized from the λ-calculus to the λµ-calculus, keeping in mind that:

I µa : ¬ϕM acts as a binder for a in M .

I Only variables can be substiuted for terms, while addresses are subsituted for more complicated objects, to be defined later.

The λµ-Calculus

I Environments now assigns types to variables and negated types to addresses.

I Typing rules are as follows:

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

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

Γ ` M N : τ @

Γ, a : ¬ϕ ` M : ⊥

Γ ` µa : ¬ϕM : ϕ µ Γ, a : ¬ϕ ` M : ϕ Γ, a : ¬ϕ ` [a]M : ⊥ [·]

The λµ-Calculus: Reduction

I λµ-contexts are defined as follows:

C ::= [·]

|

|

I Given a λµ-context C and a λµ-term M , the term C[M ] is defined as follows:

[·][M ] = M ; (CN )[M ] = (C[M ])N ; ([a]C)[M ] = [a](C[M ]).

I The concept of free variable set is generalized to contexts as follows:

FV ([·]) = ∅;

FV (CM ) = FV (C) ∪ FV (M );

FV ([a]C) = {a} ∪ FV (C)

The λµ-Calculus: Reduction

I For a λµ-context C, an address a, and a λµ-term M , we define the susbstitution M [a := C] as follows:

x[a := C] = x

(λy : ϕM )[a := C] = λy : ϕ(M [a := C]) (M N )[a := C] = (M [a := C])(N [a := C]) (µb : ¬ϕM )[a := C] = µb : ¬ϕ(M [a := C])

([a]M )[a := C] = C[M [a := C]]

([b]M )[a := C] = [b](M [a := C])

where where y, b /∈ FV (C) and a 6= b.

I The relation →_µ denotes the least compatible relation containing all the following pairs:

(λx : ϕM )N →µM [x := N ];

µa : ¬ϕ[a]M →µM if a /∈ FV (M );

[b](µa : ¬ϕM ) →µM [a := ([b][·])];

(µa : ¬(ϕ → τ )M )N →µµb : ¬τ (M [a := ([b]([·]N ))]) if a 6= b /∈ FV (M N )

The λµ-Calculus: Confluence and Normalisation

Theorem (Subject Reduction Theorem) If Γ ` M : ϕ and M →<sup>∗</sup><sub>µ</sub>N , then Γ ` N : ϕ.

Theorem (Strong Normalization)

The relation →_µ on λµ-terms is strongly normalizing.

Theorem (Confluence)

The relation →_µ on λµ-terms is weakly Church-Rosser, thus Church-Rosser.

Section 2

Gödel’s T and Arithmetic

Gödel’s T: Statics

I It can be seen as an extension of the simply-typed λ-calculus natural numbers and a form of primitive recursion are directly available, rather than encoded.

I Types are extended as follows:

ϕ ::= · · ·

|

|

I Terms are extended as follows:

M :: · · ·

|

|

|

|

where the new constants can be typed by the following rules:

Γ ` R : int → ϕ → (int → ϕ → ϕ) → ϕ R

Γ ` X : int → int X Γ ` Z : int Z

Γ ` ∗ : unit ∗

Gödel’s T: Dynamics

I Two new reduction rules are necessary:

R Z M N →β M ;

R (XL) M N →β N L(R L M N ) Theorem (Strong Normalization)

The relationβ on terms of Gödel’s T is strongly normalizing.

I A function f : N^k→ N is definable in T if there is a term M_f with ∅ ` M_f : int^k→ int such that

M_fn₁· · · n_kβ f (n₁, . . . , n_k) where n is the encoding of n via Z and X.

Theorem

The class of total functions on N which are λ-definable in T coincides with those which are provably total in Peano’s arithmetic.

Section 3

Second-Order Logic and Polymorphism

Second-Order Propositional Logic

I Formulas are the expressions derived from the following grammar:

ϕ ::= ⊥

|

|

|

|

|

|

I Usual concepts, like those of α-conversion, free variables, and the like are generalized easily to this new setting.

I Classically, the following two logical equivalences hold:

∃pϕ ⇐⇒ ϕ[p := ¬⊥] ∨ ϕ[p := ⊥]

∀pϕ ⇐⇒ ϕ[p := ¬⊥] ∧ ϕ[p := ⊥]

where ¬ϕ := ϕ → ⊥.

I Intuitionistically, the same does not hold.

Second-Order Propositional Logic

I Getting a natural deduction system for second-order propositional logic boils down to extending natural deduction for propositional logic with the following four rules:

Γ ` ϕ[p := τ ]

Γ ` ∃pϕ I∃ Γ ` ∃pϕ Γ, ϕ ` τ p /∈ FV (Γ, τ )

Γ ` τ E∃

Γ ` ϕ p /∈ FV (Γ)

Γ ` ∀pϕ I∀ Γ ` ∀pϕ

Γ ` ϕ[p := τ ] E∀

I Both Heyting and Kripke Semantics can be generalized to second-order quantifiers.

Theorem (Completeness)

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

The Polymorphic λ-Calculus

I Types are taken as second-order propositional formulas including only the operators → and ∀.

I Terms are generated by the following grammar:

M ::= x

|

|

|

|

I Typing rules are the following ones:

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

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

Γ ` M N : τ @

Γ ` M : ϕ p /∈ FV (Γ)

Γ ` ΛpM : ∀pϕ Λ Γ ` M : ∀pϕ

Γ ` (M τ ) : ϕ[p := τ ] @Λ

The Polymorphic λ-Calculus: Reduction

I The relation →_Λ denotes the least compatible relation such that

(λx : ϕM )N →ΛM [x := N ];

(ΛpM )ϕ →ΛM [p := ϕ].

Theorem (Subject Reduction Theorem) If Γ ` M : ϕ and M →<sup>∗</sup><sub>Λ</sub>N , then Γ ` N : ϕ.

Theorem (Strong Normalization)

The relation →_Λ on λµ-terms is strongly normalizing.

Theorem (Confluence)

The relation →_Λ on λµ-terms is weakly Church-Rosser, thus Church Rosser.