Transcript ppt

A Short Introduction to Logic
Summer School on Proofs as Programs
2002 Eugene (Oregon)
Stefano Berardi Università di Torino
[email protected]
http://www.di.unito.it/~stefano
1
The text of this short course on Logic,
together with the text of the next short
course on Realizability, may be found in
the home page of the author
http://www.di.unito.it/~stefano
(look for the first line in the topic
TEACHING)
2
Plan of the course
• Lesson 1. Propositional Calculus. Syntax and Semantic.
Proofs (Natural Deduction style). Completeness Result.
• Lesson 2. Predicate Calculus. Syntax and Semantic.
Proofs (Natural Deduction style).
• Lesson 3. Gödel Completeness Theorem. Validity.
Completeness.
• Lesson 4. Strong Normalization. Intuitionistic Logic.
Strong Normalization. Structure of Normal proofs.
• Next Course: Realization Interpretation.
3
Reference Text
• Logic and Structure. Dirk van Dalen. 1994,
Springer-Verlag. Pages 215.
4
Using the Textbook
•
1.
2.
3.
•
•
•
What we skipped:
Model theory of Classical Logic (most of §3)
Second Order Logic (§ 4)
Model theory of Intuitionistic Logic (in §5)
Roughly speaking: Lessons 1,2,3,4 correspond to
sections
§1, §2,
§3 and 4,
§5 and 6
of Van Dalen’s textbook.
Roughly speaking (and on the long run): in these Course
Notes, one slide corresponds to one page of Van Dalen’s
book.
5
Lesson 1
Propositional Calculus
Syntax
Semantic
Proofs
Completeness
6
Plan of Lesson 1
• We will quickly go through Syntax and Semantic of
Propositional Calculus again.
• § 1.1 Syntax. The set of formulas of Propositional
Calculus.
• § 1.2 Semantic. Truth tables, valuations, and tautologies.
• We will really start the course from here:
• § 1.3 Proofs. We introduce Natural Deduction
formalization of Propositional Calculus.
• § 1.4 Completeness. We prove that logical rules prove
exactly all “true” propositions.
• Forthcoming Lesson:
First Order Logic
7
§ 1.1 Syntax
• The symbol of the language.
• Propositional symbols: p0, p1, p2, …
• Connectives:  (and),  (or),  (not), 
(implies),  (is equivalent to),  (false).
• Parenthesis: (, ).
8
§ 1.1 Syntax
•
1.
2.
3.
4.
The set PROP of propositions: the
smallest closed under application of
connectives:
PROP
pi PROP for all iN
PROP
 ()PROP
,PROP  (), (  ), (),
() PROP
9
§ 1.1 Syntax
•
•
•
•
•
•
Examples:
(p0)
((p0))
(p0  (p1  p2))
(p0 (p1 p2))
Correct expressions of Propositional Logic
are full of unnecessary parenthesis.
10
§ 1.1 Syntax
• Abbreviations. Let c=, , . We write
p0 c p1 c p2 c …
• in the place of
(p0 c (p1 c (p2 c …)))
• Thus, we write
p0  p1  p2, p0p1 p2, …
• in the place of
(p0  (p1  p2)), (p0 (p1 p2))
11
§ 1.1 Syntax
• We omit parenthesis whenever we may
restore them through operator precedence:
•  binds more strictly than , , and , 
bind more strictly than , .
• Thus, we write:
• p0
for ((p0)),
• p0  p1
for ((p0 )  p1)
• p0  p1 p2 for ((p0 p1)  p2), …
12
§ 1.1 Syntax
•
•
Outermost symbol. The outermost symbol
of
, pi , ,
(), (), (), ()
are, respectively:
, pi , ,
, , , 
13
§ 1.1 Syntax
•
1.
2.
3.
•
•
Immediate Subformulas :
Of  and pi
are
none
Of 
is

Of (), (  ), (), ()
are
, 
 is a subformula of  iff there is some chain =0, …,
n=, each formula being some immediate subformula
of the next formula.
Subformulas of =((p0 p1)  p2) are:
 itself, (p0 p1), p0, p1, p2.
14
§ 1.2 Semantic
•
•
•
•
•
Interpreting Propositional constant and connective.
Each proposition pi may be either T (true) or F (false).
 is always F (false).
, , , ,  are interpreted as unary or binary map
(or Truth Tables), computing the truth of a statement
, (), (), (), (),
given to the truth of immediate subformulas , .
15
§ 1.2 Semantic
•
Truth table of .
=T
=F
=F =T
16
§ 1.2 Semantic
•
Truth table of .
=T
=F
=T
= T
= F
= F
= F
= F
17
§ 1.2 Semantic
•
Disjunction is taken not exclusive: if
, then both ,  may be true.
=T
=F
=T
= T
= T
= F
= T
= F
18
§ 1.2 Semantic
•
Implication is “material”:  is true
also for unrelated statements , : it only
depends on the truth values of , .
=T
=F
=T
= T
= T
= F
= F
= T
19
§ 1.2 Semantic
•
Equivalence  is identity of truth
values.
=T
=F
=T
=T
=F
=F
=F
=T
20
§ 1.2 Semantic
• Inductive definition. Fix any set I, any map v:NI, any
bI, and for any unary (binary) connective c, some unary
(binary) map Tc on I.
• Then there is exactly one map h:PROPI, such that:
• f(pi)
= v(i)
I
for all iN,
• f() = b
I
• f()
= T(f())
I
• f( c )
= Tc(f(), f())
I
for all binary connectives c
21
§ 1.2 Semantic
•
•
1.
2.
•
A Valuation is any map v:N{T,F}, assigning truth
values to Propositional constants.
Interpreting Propositional formulas. Any valuation v
may be extended by an inductive definition to some
map h:PROP{T,F}, by:
mapping  into b=False,
using, as Tc, the truth table of connective c= , , ,
, .
For all  PROP, we denote h() by
[]v {T,F}
22
§ 1.2 Semantic
•
•
•
•
Let PROP.
Tautologies.  is a tautology iff for all
valuations v we have []v =T.
Contradictions.  is a contradiction iff for
all valuations v we have []v =F.
Tautology conveys our intuitive idea of
being “logically true”, or “true no matter
what the Propositional constants are”.
23
§ 1.2 Semantic
•
•
•
•
•
Some examples of tautologies
Double Negation Law:   .
Excluded Middle:   .
An easy exercise: check that    is a
tautology, i.e., that
[]v = True
for all valuations v:N{T,F}.
24
§ 1.3 Proofs
•
•
•
•
Formal Proofs. We introduce a notion of
formal proof of a formula : Natural
Deduction.
A formal proof of  is a tree
whose root is labeled ,
and whose children are proofs of the
assumptions 1, 2, 3, … of the rule r we
used to conclude .
25
§ 1.3 Proofs
•
•
•
•
Natural Deduction: Rules. For each logical
symbol c=, , , , and each formula  with
outermost connective c, we give:
A set of Introduction rules for c, describing
under which conditions  is true;
A set of Elimination rules for c, describing
what we may infer from the truth of .
Elimination rules for c are justified in term of
the Introduction rules for c we chose.
26
§ 1.3 Proofs
•
•
•
•
Natural
Deduction:
the
missing
connectives.
We treat
,
,
as abbreviating
(),
()(),
We do not add specific rules for the
connectives , .
27
§ 1.3 Proofs
•
•
•
•
Natural Deduction: notations for proofs.
Let  be any formula, and  be any unordered (finite or
infinite) list of formulas. We use the notation

…

abbreviated by |- , for:
“there is a proof of  whose assumptions are included
in ”.
28
§ 1.3 Proofs
•
•
•
Natural
Deduction:
crossing
assumptions.
we use the notation
, 
\
…

for: “we drop zero or more assumptions
equal to  from the proof of ”.
29
§ 1.3 Proofs
•
•
•
Natural Deduction: assumptions of a
proof
1
2
3
…
r -------------------------------
are inductively defined as:
all assumptions of proofs of 1, 2, 3, …,
minus all assumptions we “crossed”.
30
§ 1.3 Proofs
•
•
•
•
Identity Principle: The simplest proof is:

having 1 assumption, , and conclusion
the same .
We may express it by: |-, for all 
We call this proof “The Identity
Principle” (from  we derive ).
31
§ 1.3 Proofs
•
•
•
Rules for 
Introduction rules: none ( is always false).
Elimination rules: from the truth of  (a
contradiction) we derive everything:

---
•
If |- , then |-, for all 
32
§ 1.3 Proofs
•
•
Rules for 
Introduction rules:
 
-------
•
If |-  and |-  then |-   
33
§ 1.3 Proofs
•
•
Elimination rules:

-------

------
If |-   , then |-  and |- 
34
§ 1.3 Proofs
•
•
•
Rules for 
Introduction rules:

-------

------
If |-  or |- , then |-   
35
§ 1.3 Proofs
•
Elimination rules:


…
…



-------------------------------------
\
•
•
\
If |-    and ,|- and , |-, then |-
We may drop any number of assumptions equal to  (to
) from the first (from the second) proof of 
36
§ 1.3 Proofs
•
Rules for 
Introduction rule:

…

-------
\
•
•
If , |- , then |-
We may drop any number of assumptions equal to 
from the proof of .
37
§ 1.3 Proofs
•
•
Elimination rule:


---------------
If |- and |-, then  |- .
38
§ 1.3 Proofs
•
The only axiom not associated to a connective, nor
justified by some Introduction rule, is Double
Negation:

….

--
If , |- , then |-
We may drop any number of assumptions equal to 
from the proof of .
\
•
•
39
§ 1.3 Proofs
•
1.
2.
•
•
•
Lemma (Weakening and Substitution).
If |- and p, then p|-.
If |- and , |-, then |- .
Proof.
Any proof with all free assumptions in  has all
free assumption in p.
Replace, in the proof of  with free
assumptions all in ,, all free assumptions 
by a proof of  with all free assumptions in .
40
§ 1.4 Completeness
•
•
•
•
Definition (Validity). |- is valid iff for all
valuations v such that v(){True}, we have
v()=True (iff for no valuation v we have
v(){True}, v()=False).
Validity conveys the idea “|- is true no matter
what the Propositional constants are”.
Definition (Consistency).  is consistent iff (|) is false (if  does not prove ).
Definition (Completeness).  is complete iff for
all propositions , either |- or |- .
41
§ 1.4 Completeness
Correctness. If |- is true in Natural
Deduction, then |- is valid.
• Proof. Routine. By induction over the
proof of |-, considering:
1. one case for each introduction and
elimination rule,
2. one for the Identity rule,
3. one for Excluded middle.
•
42
§ 1.4 Completeness
•
Completeness Theorem. If |- is valid, then then |-
is derivable in Natural Deduction.
•
•
•
Proof.
We will pass through many Lemmas:
Lemma 1 (Consistency). If |- is not derivable, then
,  is consistent.
Lemma 2 (Consistent Extension). For all formulas ,
if  is consistent, then either ,  or ,  is
consistent.
•
43
§ 1.4 Completeness
•
•
•
Lemma 3 (Complete Consistent extension).
Any consistent set  may be extended to some
consistent complete set ’.
Lemma 4 (Valuation Lemma). For every
complete consistent consistent set  there is
some valuation v such that v()={True}.
Lemma 5 (2nd Valuation Lemma). For every
consistent set  there is some valuation v such
that v(){True}.
44
§ 1.4 Completeness
•
Lemma 1 (Consistency). If |- is not
derivable, then ,  is consistent.
•
Proof. We will prove the contrapositive: if
, |-, then |-. This statement
follows by Double Negation.
45
§ 1.4 Completeness
•
Lemma 2 (Consistent Extension). For for all
formulas , if  is consistent, then either , 
or ,  is consistent.
•
Proof. We will prove the contrapositive: if
,|- and ,|-, then |-.
1. From ,|- and -Intr. we deduce |-.
2. From |- (by 1 above), the hypothesis
,|-, and Substitution, we conclude |-.
46
§ 1.4 Completeness
•
Lemma 3 (Complete Consistent extension). Any
consistent set  may be extended to some consistent
complete set ’ (such that for all formulas , either
’|- or ’ |- ).
•
Proof. Fix any numbering of formulas 0, …, n, … .
Let 0, …, n, … be the sequence of sets of formulas
defined by:
0
=
n+1
= n, n,
if n, n is consistent
n+1
= n, n
if n, n is not consistent
•
•
•
47
§ 1.4 Completeness
•
•
•
Proof of Complete Consistent Extension .
(Consistency) By the Consistent Extension lemma, if
n is consistent then n+1 is. Since 0 =  is consistent,
then all n are consistent. Thus,  = nn is consistent
(a proof of  with assumptions in  would have all
assumptions in some n).
(Completeness) By construction,  includes, for all
formulas n, either n or n. By the Identity Principle,
in the first case |-n, in the second one |-n .
48
§ 1.4 Completeness
•
Lemma 4 (Valuation Lemma). For every complete
consistent set  there is some valuation v such that
v()={True}.
•
•
•
•
•
Proof. Define v()=T iff |-. We have to prove:
v()
=F
v(  ) = T  v()=T or v()=T
v(  ) = T  v()=T and v()=T
v(  )
= T  v()=F or v()=T
49
§ 1.4 Completeness
•
v() = F because |- is false, by
consistency of .
50
§ 1.4 Completeness
•
•
•
v(  ) = T  v()=T or v()=T
Left-to-Right. Assume for contradiction
v()=F and v()=F. By Completeness of
, |- and |- are true. By  -Elim.,
we have ,|- and ,|-. From |-
(by hyp.) and -Elimination we conclude
|-, against the consistency of .
Right-to-Left. If |- or |-, then |-
by -Introduction.
51
§ 1.4 Completeness
•
•
•
v(  ) = T  v()=T and v()=T
Left-to-Right: by  -Elimination.
Right-to-Left: by -Introduction.
52
§ 1.4 Completeness
•
•
•
1.
2.
v(  ) = T  v()=F or v()=T
Left-to-Right: If v()=F, we are done. If v()=T, then
|-, and by -E |-, v()=T.
Right-to-Left. Assume either v()=F or v()=T, in
order to prove v()=T.
Case v()=F. By completeness of , we have |-.
Then ,|- by -Elimination, and ,|- by Elimination. We conclude |- by -Introduction.
Case v()=T. If |-, then |- by some Introduction crossing no assumptions .
53
§ 1.4 Completeness
•
•
Lemma 5 (2nd Valuation Lemma). For
every consistent set  there is some
valuation v such that v(){True}.
Proof. Extend  to some complete
consistent set ’, and find some
valuation v such that v(’)={True}. From
’ we conclude v(){True}.
54
§ 1.4 Completeness
•
Proof of Completeness Theorem (end). If
|- is not derivable, then ,  is
consistent. Thus, for some v:N{T,F} we
have v(){T}, v()=T, therefore
v()=F. We conclude that |- is not valid.
55
Appendix to § 1
•
•
•
Some Tautologies (Exercises).
Hilbert-style formalization (the idea).
Sequent Calculus (the idea).
56
Appendix to § 1
•
•
Some examples of Tautologies.
All formulas which follow may be proved
to be tautology in two ways:
1. using the inductive definition of []v ;
2. using proofs in Natural Deduction,
together with the identifications of ,
 with (), ()().
57
Appendix to § 1
•
•
•
Associativity of  , :
      (  )  
      (  )  
•
•
•
Commutativity of  , :




58
Appendix to § 1
•
•
•
Distributivity of  , :
  (  )  (  )  (  )
  (  )  (  )  (  )
•
•
•
De Morgan’s Laws:
(  )
   
(  )
   
59
Appendix to § 1
•
•
•
•
•
•
•
Idempotency of  , :




Characterizing Implication
  
 ()
Characterizing Equivalence
(  )
 ()  ()
60
Appendix to § 1
•
•
•
•
•
•
•
•
Proof of: Excluded Middle is a tautology.
[]v = T([]v ,[]v) = T([]v,T([]v))
Case []v = True:
[  ]v
= T(True, T(True)) =
T(True, False)
= True.
Case []v = False:
[  ]v
= T(False, T(False)) =
T(False, True)
= True.
61
Appendix to § 1
•
1.
2.
3.
4.
5.
6.
7.
8.
9.
How to deduce Excluded Middle out of Double
Negation:
By the Id. Princ. (),  |- 
By -Introd. on 1
(),  |- 
By the Id. Princ. (),  |- ()
By -Elim. on 2, 3
(),  |- 
By -Introd. on 4
()
|- 
By -Introd. on 5
()
|- 
By the Id. Princ. ()
|- ()
By -Elim. on 6, 7
()
|- 
By Double Neg. on 8
|- 
62
Appendix to § 1
•
•
Modus Ponens: if  and  are
tautologies, then  is a tautology.
Proof. Let v:N{T,F}. By hyp., []v =
[]v = True. We have to prove []v =
True. If it were []v = False, then by []v =
True we would conclude []v = False.
This contradicts the hypothesis []v =
True.
63
Appendix to § 1
•
A first alternative formalization of proofs
of Propositional Calculus:
• Hilbert-style formalization.
• We fix a set X of axioms, and we
inductively define the set T of theorems:
1. All axioms  are theorems.
2. If ,  are theorems, then  is a
theorem.
64
Appendix to § 1
• Hilbert-Style Proofs may be seen by trees
1. whose root is the formula  being proved,
and
2. whose children are
• none if  is an axiom, and
• are the proofs of , , if  has been
proved by Modus Ponens.
65
Axioms







Hilbert-style proofs
Appendix to § 1
•
•
•
In order to give some Hilbert-style
formalization for Propositional logic, we have
to fix some set X of tautologies, able to derive
all tautologies through Modus Ponens.
Using Hilbert-style axiomatization we describe
the notion of truth for Propositional logic, but
we miss an intuitive understanding of the
notion of (formal) proof.
We prefer to introduce the notion of formal
proof through Natural Deduction.
67
Appendix to § 1
•
•
•
•
A second alternative formalization of proofs of
Propositional Calculus: Sequent Calculus.
We may in fact introduce proofs independently as rules
to derive a sequent |- rather than a formula.
The resulting notation for proofs is rather cumbersome
to use: we prefer Natural Deduction.
Sequent notation is instead convenient if we work in
Type Theory or in Automated Deduction: in this case
we have to precise the pair: assumptions  /thesis .
68
Lesson 2
Predicate Calculus.
Syntax
Semantic
Proofs
69
Plan of Lesson 2
• § 2.1 Syntax. The set of formulas of First Order
Logic.
• § 2.2 Semantic. Interpreting formulas of First
Order Logic.
• § 2.3 Proofs. We introduce Natural Deduction
formalization of First Order Logic.
• Previous Lesson:
Propositional Logic
• Forthcoming Lesson: Completeness Theorem
70
§ 2.1 Syntax: The symbol of
Predicate Calculus.
• Predicate Symbols: P, Q, R, …, of integer arity n0, n1, n2,
….
• They should include a name “=” for equality.
• Function Symbols: f, g, h, ……, of integer arity m0, m1,
m2, …
• Variables: x0, x1, x2, …
• Connectives:  (and),  (or),  (not),  (implies),  (is
equivalent to),  (false), and quantifiers:  (exists),  (for
all).
• Parenthesis: (, ).
71
§ 2.1 Syntax
•
The set TERM of (first order) terms: the
smallest set including variables, and closed
under application of functions symbols:
1. xiTERM
for all iN
2. t1, …, tmTERM,
f function name of arity m

f(t1,…, tm)TERM,
for all i, mN
72
§ 2.1 Syntax
•
•
•
•
•
•
Examples of (first order) terms
Any variable: x, y, z, …
If we have 0-ary (constant) function symbols a,
b, c, then a, b, c are also terms
To show it, just apply a, b, c to the empty
sequence of terms.
If f is unary, g is binary, then
f(f(c)), g(f(a),b), g(x,y)
are terms
73
§ 2.1 Syntax
•
•
The set ATOM of atomic formulas:
If t1, …, tnTERM,
P predicate name of arity n

P(t1,…, tn)ATOM,
for all nN
• Examples: if P is unary, Q is binary, then
c=f(x), P(f(f(c))), Q(z, g(f(a),b)), P(g(x,y))
• are atomic formulas
74
§ 2.1 Syntax
•
•
•
•
The set FORM of (first order) formulas: the
smallest including atomic formulas, and closed
under application of connectives:
ATOM
 FORM
FORM, x variable
 (), (x), (x)FORM
,PROP  (), (), (),
() PROP
75
§ 2.1 Syntax
•
•
•
•
•
•
Examples of formulas:
(P(f(f(c))))
((P(g(x,y)) ))
((xP(x))  (P(y)  P(z)))
(x(P(x)  (P(y)  P(z))))
Correct formulas require
parenthesis.
unnecessary
76
§ 2.1 Syntax
• Abbreviations. Let c=, , . We write
p0 c p1 c p2 c …
• in the place of
(p0 c (p1 c (p2 c …)))
• Besides, we write
xy, xyz …
• in the place of
(x(y)), (x(y(z)))
• We also use x,y for xy.
77
§ 2.1 Syntax
• We omit parenthesis whenever we may restore them
through operator precedence:
• , ,  bind more strictly than , , and ,  bind more
strictly than , .
• Thus, we write:
• P(a)
for
((P(a))),
• P(a)  Q(x,y)
for
((P(a))  Q(x,y))
• xP(x)  P(y)  P(z)
for
((xP(x))  (P(y)  P(z)))
• xP(x)P(y)P(z) for
(((xP(x))P(y)) P(z))
78
§ 2.1 Syntax
•
Outermost symbol. The outermost symbol
of
x, f(t1,…, tn), P(t1,…, tn), , , x, x,
(), (), (), ()
• are, respectively:
x, f, P, , , , 
, , , 
79
§ 2.1 Syntax
•
1.
2.
3.
•
•
Immediate Subformulas of:
 and P(t1,…, tn),
are
none
, x, x
is

(), (), (), ()
are
, 
 is a subformula of  iff there is some chain =0, …,
n=, each formula being some immediate subformula
of the next formula.
Subformulas of =xP(x)  P(y)  P(z) are:
 itself, xP(x), P(x), P(y)P(z), P(y), P(z)
80
§ 2.1 Syntax
•
•
•
•
•
•
•
•
•
Free variables. We define free variables by induction
over the definition of a term or a formula.
FV(x)
=x
FV(f(t1,…, tm)) = FV(t1)  …  FV(tm)
FV(P(t1,…, tm)) = FV(t1)  …  FV(tm)
FV()
= FV()
FV(x)=FV(x)
= FV()-{x}
FV( c )
= FV()  FV()
We call closed a term (formula) e if FV(e)=.
We call closed a set of closed terms (formulas).
81
§ 2.1 Syntax
•
•
•
•
•
•
•
Substitution. We define substitution e[x:=t] of
a variable x by a term t by induction over e
(term or formula).
Terms:
y[x:=t]
=t
if y=x
y[x:=t]
=y
if yx
f(t1,…, tm)[x:=t]
= f(t1[x:=t],…, tm[x:=t])
Atomic Formulas:
P(t1,…, tm)[x:=t])
= P(t1[x:=t],…, tm[x:=t])
82
§ 2.1 Syntax
•
•
•
•
•
Substitution (Formulas). Let Q=,  be
any quantifier, c=, , ,  be any
binary connective.
()[x:=t]
= ([x:=t])
( c )[x:=t]
= [x:=t] c [x:=t]
(Qy)[x:=t]
= Qy
if y=x
(Qy)[x:=t]
= Qy([x:=t]) if yx
83
§ 2.1 Syntax
•
•
•
Binder. A binder for x in  is any
subformula x or x of .
Free and Bound occurrences. An
occurrence of x in  is bound iff x is
inside some binder of x in , free in the
opposite case.
A substitution e[x:=t] is sound iff no free
occurrence of variable in t becomes
bound after substitution.
84
§ 2.1 Syntax
•
•
•
Renaming. ’ is a renaming of  iff ’ is obtained out
of  by replacing some subformula Qx by Qy[x:=y],
with yFV(), and [x:=y] sound substitution.
Convertibility. We that two formulas are convertible iff
there is a chain of renaming transforming one into the
other.
We identify formulas up to convertibility. Intuitively, if
, ’ are convertible, then they express the same
meaning using different names for bound variables.
85
§ 2.1 Syntax
•
•
•
•
•
Substitution may always be considered sound.
Lemma (Substitution). For all substitutions [x:=t]
there is some suitable ’ convertible to  such that
’[x:=t] is sound.
We omit the proof (it is conceptually simple, but rather
cumbersome).
Thus, any substitution [x:=t] becomes sound after
some renaming.
As a consequence, the result of a substitution is
determined only up to renaming.
86
§ 2.2 Semantic
• Structure M
for a first order language:
• A universe M of M, not empty.
• For each Predicate Symbols: P, Q, R, …, of integer arity
n, n’, n”, …, some predicates
PMMn,
QM Mn’, RM Mn”,
• interpreting P, Q, R, … .
• For each Function Symbols: f, g, h, ……, of integer
arity m, m’, m”, … some functions
fM MnM,
gM Mn’M, hM Mn”M,
• interpreting f, g, h, … .
87
§ 2.2 Semantic
• Equality. Interpretation =M of the equality
name should be the equality predicate.
• This condition may be weakened to: =M is
some equivalence relation compatible with
all predicate and functions of M.
• In this case, we obtain a structure by taking
the quotient M/=M.
• Constants, i.e., names c of functions of arity
0, are interpreted by cMM.
88
§ 2.2 Semantic
• Interpreting terms. Let M be any model. Every
map v:{0,1,2,…}M may be extended to some
map
[.]v, M :TERMSM
• If M is fixed, we abbreviate [.]v, M by [.]v.
• We define [.]v,M by induction over the definition
of a term.
• [xi]v
= v(i)
M
• [f(t1,…, tm)] v, M = fM([t1]v,…, [tn]v)
M
89
§ 2.2 Semantic
•
Interpreting atomic formulas. Let M be any
model. Every map v:{0,1,2,…}M from
indexes of variables to M may be extended to
some map [.]v,M: ATOMS  {True, False}.
1. First, we extend v to a map [.]v, M on all terms
2. Then we define
[P(t1,…,tm)]v,M=True if
([t1]v,M,…,[tn]v,M)PM
[P(t1,…, tm)]v, M = False if
([t1]v, M ,…, [tn]v, M )PM
90
§ 2.2 Semantic
•
•
Case definition. If v:{0,1,2,…}M, and
mM, by
v[xi:=m]
we denote the map :{variables}M
defined by cases:
1. v[xi:=m](j)
2. v[xi:=m](j)
=m
= v(j)
if i=j
if ij
91
§ 2.2 Semantic
• Let M be any model. We extended every map
v:{variables}M to some map
[.]v, M : ATOMS  {True, False},
• We will now extend [.]v, M to some map
[.]v, M : FORMULAS  {True,False},
• by induction over the definition of a formula.
• We distinguish several cases, according if the
outermost connective of  is
, , , , , , 
92
§ 2.2 Semantic
• Let Tc be the truth table of c=,,,,.
• []v,M
= T([]v,M )
for c=,,,:
• [ c ] v,M
= Tc([]vM,[]v,M),
•
[x]v
•
[x]v
•
[x]v
•
[x]v
= True, iff []v[x:=m],M = True
for some mM
= False, otherwise.
= True, iff []v[x:=m],M = True
for all mM
= False, otherwise.
93
§ 2.2 Semantic
•
We extend [.]v,M to sets  of formulas, by
[]v,M = {[]v,M | }
•
We also write M|=v, or “ is true in M
under substitution v”, for []v,M = True.
94
§ 2.2 Semantic
•
•
•
Substitution Theorem.
Substitution on  is interpreted by substitution on the
valuation map v.
Let m=[t]v,M:
[[x:=t]]v,M = []v[x:=m],M ,
•
If xFV(), then [x:=t]= and therefore
[]v[x:=m],M = []v,M.
•
Proof. See Van Dalen’s book.
95
§ 2.2 Semantic
•
•
•
•
•
Lemma (Quotient Lemma).
Take any structureM in which =M is some
equivalence relation compatible with all
predicate and functions of M.
Consider the quotient structure M/=M. This
structure satisfies the same formulas as M:
M |=v  (M /=M ) |=v
Proof. By induction over , using compatibility
of =M with all predicate and function names.
Thus: in order to define a structure with an
equality relation =M, it is enough to define
some equivalence relation =M compatible with
all predicate and functions of M.
96
§ 2.3 Proofs
• From the Propositional case, we keep
1. Double Negation Rule.
2. Introduction and Elimination rules for each
logical symbol c = , , , .
3. Abbreviations for connectives , .
• The rules we have to add are:
1. Introduction and Elimination for , , and
2. Rules for atomic formulas, including Equality.
97
§ 2.3 Proofs
•
•
Rules for : Introduction rule.

…
[x:=t]
--------x
•
If |-[x:=t] for some t, then |- x
98
§ 2.3 Proofs
•
Rules for : Elimination rule.

 ,
…
…
x

---------------
Provided xFV(,).
•
If |-x, ,|-, and xFV(,), then |-
•
\
99
§ 2.3 Proofs
•
•
•
Rules for : Introduction rule.

…

-----x
Provided xFV()
If |- and xFV(), then |-x
100
§ 2.3 Proofs
•
Rules for : Elimination rule.

…
x
--------[x:=t]
•
If |- x, then |- [x:=t] for all t
101
§ 2.3 Proofs
•
Rules for atomic formulas. Any set of rules of the
shape:
1 … n
-----------
for 1
… n,  atomic. For instance: reflexivity,
symmetry, transitivity of equality, compatibility of
equality with functions and predicates.
102
§ 2.3 Proofs
----t=t
t=u
----u=t
t=u u=v
-----------t=v
t1=u1
…
tn=un
-------------------------f(t1,…,tn)=f(u1,…,un)
103
§ 2.3 Proofs
t1=u1
…
tn=un
P(t1,…,tn)
----------------------------------------P(u1,…,un)
By induction on , we deduce:
t1=u1
…
tn=un
[x1:=t1,…, x1:=tn]
---------------------------------------------------[x1:=u1,…, x1:=un]
104
§ 2.3 Proofs
• Mathematical Theories T are identified with sets
of axioms T.
•  is a theorem of T iff T|-.
• An example: First Order Arithmetic PA has
language L={0, succ, <}.
• PA is introduced adding axioms characterizing
successor, plus, for every formula , the
• Induction Axiom for  :
x.([x:=0]x([x:=x+1]))
105
§ 2.3 Proofs
• An exercise for the next Lesson: derive, for z not
free nor bound in ,
z(x[x:=z])
“there is some z such that:
if (x) is true for some x, then (z)”
• Hint: prove first x|-Thesis and x|-Thesis.
Then conclude |-Thesis out of |- xx and
-Elimination.
106
Appendix to § 2
• Proof of Th=z(x[x:=z]).
• As suggested, we are going to prove both
x|-Th and x|-Th, then conclude Th
out of |- xx and -Elimination.
• By renaming z with x, we may replace Th
by Th’ = x(x) in the proof:
• Th and Th’ are convertible, hence they may
be identified.
107
Appendix to § 2
•
1.
2.
3.
4.
5.
6.
x|-Th’.
|-
|-x
|-x(x)
xFV(Th’)
x|-x
x|-x(x)
by Id. Princ..
by 1 and -I
by 2 and -I
x is bound in Th’.
by Id. Princ.
by 3, 4, 5 and -E
108
Appendix to § 2
•
1.
2.
3.
4.
5.
6.
Proof of x|-Th’.
x |- x
x |- x
x, x|-
x, x|-
x |-x
x |- x(x)
by id. princ.
by id. princ.
by 1,2, and-E
by 3 and -E
by 4 and -I
by 5 and -I
109
Lesson 3
Validity Theorem
Gödel Completeness Theorem
110
Plan of Lesson 3
•
•
•
•
§ 3.1 Validity Theorem. All derivable sequents
are “logically true”.
§ 3.2 Completeness Theorem. All “logically
true” sequents are derivable.
Previous Lesson:
Forthcoming Lesson:
First Order Logic
Normalization.
111
§ 3.1 Validity Theorem
•
•
•
•
•
Validity. A sequent |- is valid iff for all models M
and valuations v, if []v,M {True} then []v,M
=True.
We also write  |= for “|- is valid”.
 is valid iff |- is valid (i.e., iff for all models M,
[]v,M =True).
“|- valid” expresses our intuitive idea of “logical
truth”:
“|- is true no matter what are the meaning of
predicate and function symbols in it”
112
§ 3.1 Validity Theorem
•
•
•
Derivability perfectly correspond to
validity (to our intuitive notion of truth)
Validity Theorem. If |- is provable, then
|- is valid.
Completeness Theorem (Gödel). Also the
converse holds: if |- is valid, then it is
provable.
113
§ 3.1 Proof of Validity Theorem
•
•
•
•
•
Proof of Validity Theorem.
By induction on the proof of |-: we have to prove,
for all logical rules, that Validity is preserved:
“if all premises are Valid then also the conclusion is”
The only non-trivial steps concern Introduction and
Elimination rules for ,.
Let us pick up -Introduction, -Elimination as sample
cases.
114
§ 3.1 Proof of Validity Theorem
•
•
•
•
•
•
•
Proof of Validity Theorem:
-Introduction preserves validity.
The inductive hypothesis is:
|-[x:=t] is valid.
The thesis is:
|-x is valid.
We assume []v,M {True} in order to
prove [x]v,M =True.
115
§ 3.1 -Introduction
preserves Validity
1. Assume []v,M {True}.
2. From |-[x:=t] valid and 1 we obtain:
[[x:=t]]v,M =True.
3. Set m=[t]v,M M.
4. By Substitution Theorem and 3:
[[x:=t]]v,M = []v[x:=m],M.
5. By 2, 4, we deduce []v[x:=m],M =True.
6. By 5, we deduce [x]v,M = True.
116
§ 3.1 -Elimination
preserves Validity
•
•
•
•
•
•
•
Proof of Validity Theorem:
-Elimination preserves validity.
The inductive hypothesis is:
|-x and ,|- are valid, and xFV(,)
The thesis is:
|- is valid.
We assume []v,M {True}, in order to prove
[]v,M =True.
117
§ 3.1 -Elimination
preserves Validity
1.
2.
1.
2.
3.
4.
5.
Assume []v,M {True}.
By 1 and |-x valid, we deduce [x]v,M = True,
that is:
[]v[x:=m ],M = True, for some mM
By xFV(), Sub.Thm: []v[x:=m],M = []v,M
By 1, 3 we deduce []v[x:=m],M {True}
By ,|- valid, and 2, 4, we deduce []v[x:=m],M =
True.
By xFV(), Sub.Thm: []v[x:=m],M = []v,M.
By 5, 6, we conclude []v,M =True.
118
§ 3.2 Completeness
•
1.
2.
3.
•
Completeness Theorem (Gödel).
(Weak closed form) If  is closed consistent, then there
is some model M such that []v,M {True} (for any
valuation v).
(Weak form) If  is consistent, then there is some
model M and some valuation v such that []v,M
{True}.
(Strong form) If |- is valid, then |- is provable.
Proof. We will first prove weak closed form, then weak
and strong form out of it.
119
§ 3.2 Proof of Completeness
(weak closed form)
•
Henkin Axioms. Fix, for each closed
formulas x of a language L, some
constant cx of L. Then we call Henkin
axiom for x the statement:
x[x:=cx]
“there is some some z=cx such that, if (x)
for some x, then (z)”
120
§ 3.2 Proof of Completeness
(weak closed form)
•
•
•
At the end of the previous section, we proved
|-z(x[x:=z])
“there is some z such that:
if (x) is true for some x, then (z)”
Intuitively, this means that all Henkin axioms
are logically correct (there exists some
interpretation z for cx).
Henkin Theories. A closed set H of formulas in
a language L is an Henkin Theory iff H proves
all Henkin axioms of language L.
121
§ 3.2 Proof of Completeness
(weak closed form)
•
Lemma (Henkin Lemma). Let H be an Henkin
Theory of language L.
• All closed sets H’H of formulas of L are
Henkin Theories.
• Derivability from H commutes with the
interpretation of ,  on the set TERM0 of
closed term, and for closed x, x.
1. H|- x  H|- [x:=t],
for some tTERM0
2. H|- x  H|- [x:=t],
for all tTERM0
122
§ 3.2 Proof of Henkin Lemma
•
If H proves all Henkin axioms of L, then the
same is true for all H’H in L.
1. . If H|-x, then by Henkin axiom for x
and -Elim. we get H|-[x:=cx], with cx
closed term.
. If H|-[x:=t] for some closed t, we obtain
H|-x by -Introd..
2. . Assume H|-x.
• Then H|-[x:=t] for all closed t by -Elim..
123
§ 3.2 Proof of Henkin Lemma
2.
•
•
•
•
•
•
. Assume H|-[x:=t] for all closed t.
By Identity princ., H,|-
By -Introduction, H,|-x.
By Henkin axiom for x (a closed formula)
and -Elim., we get H,|-[x:=cx]
From the hyp. H|-[x:=cx] and -Elim. we
conclude
H,|-.
From H,|- we deduce H|- by D. Neg..
from H|-, and xFV(H)= (H is closed) we
conclude H|-x by -Introd..
124
•
•
§ 3.2 Henkin Extension
Lemma
Conservative Extensions. If T’T are two sets
of formulas, in the languages L’L, we say that
T’ is a conservative extension of T if T’ proves
no new theorem in the language L of T:
If  is a formula of L, and T’|-, then T|-
Lemma (Henkin Extension Lemma). For all
sets  of closed formulas of L, there is some
Henkin theory H, of language L’L, which
is a conservative extension of .
125
§ 3.2 Proof of Henkin
Extension Lemma
•
•
•
•
Fix any language L, any closed formula
x of L, any closed , any cxL. Let
’ = {Henkin axiom for x}
’ is  + the Henkin axiom for .
Claim (one-step Henkin extension):
’ is a closed conservative extension of ,
of language L’=L{cx}.
126
§ 3.2 Proof of the Claim
1.
2.
3.
4.
5.
6.
Assume , x[x:=cx]|- and cx not in , in
order to prove |- .
cx is not in , nor in , because ,  are in the original
language L.
Replace cx in the proof of the sequent above by any
variable zFV(,,).
Since cx is not in ,,, we obtain a proof of:
, x[x:=z]|-
By -Elim., , z(x[x:=z])|-.
By |-z(x[x:=z]) (end of the previous lesson) we
conclude |-.
127
•
•
•
•
§ 3.2 Proof of Henkin
Extension Lemma
Fix any enumeration of closed formulas of the shape
x in L. Starting from 0=, we define
n+1 = n{xnn[x:=c]}
By the Claim, each n+1 is a closed conservative
extension of n, and therefore of .
Thus, 1=nNn is a closed conservative extension of
: if we have a proof of  in L in , then we have a
proof of  in some n, and by conservativity of n w.r.t.
, also in .
1 includes all Henkin axiom for the language of the
original .
128
§ 3.2 Proof of Henkin
Extension Lemma
•
•
•
•
•
Define 0 = , n+1 = (n)1.
Then H = nNn is a closed conservative extension of
, including all n+1, and therefore all Henkin axiom
for all closed x in the language of all n .
Thus, H includes all Henkin axioms for all closed x
in the language of H itself.
We conclude that H is an Henkin Theory, and a
closed conservative extension of .
H is consistent if  is: by conservativity, any proof of 
in H is a proof of  in .
129
§ 3.2 Proof of Completeness
(weak closed form)
• Using Henkin Extension Lemma, we may
define, for all closed consistent  of
language L, some closed consistent Henkin
H, of language L’L.
• By adapting the Complete Set Lemma of
Propositional logic to the set of closed first
order formulas, we may define some closed
complete ’H .
130
§ 3.2 Proof of Completeness
(weak closed form)
• ’  (closed, complete) is an Henkin theory by Henkin
Lemma.
• ’ defines a model M of , whose universe are the
closed terms of the language L’ of ’ (modulo provable
equality in ’).
• We interpret each n-ary function name f by the map over
closed terms of L’
fM : (t1,…,tn) | f(t1,…,tn),
• and each m-ary predicate name P by
PM = {(t1,…,tn) closed in L’| ’|-P(t1,…,tn)}
131
•
•
•
§ 3.2 Proof of Completeness
(weak closed form)
By construction, “=” is interpreted in M by
provable equality in ’.
Provable equality is closed under equality rules,
therefore is an equivalence relation on M,
compatible with all functions and predicates of
L’.
We will now prove that []v,M 
[’]v,M
= {True}, or that M is a model of .
132
§ 3.2 Valuation Thm
• Theorem (Valuation Thm).
1. For all closed v:
’|-v()  []v,M =True
• In particular we have Weak Closed
Completeness:
[]v,M 
[’]v,M ={True}
2. For all closed substitutions v, w: VAR 
{closed terms}:
[]v,M = [v()]w,M
133
§ 3.2 Valuation Thm (1)
•
•
•
•
•
Proof of (1). By induction on .
For  atomic, we have ’|-v()  []v,M =True by
definition of the structure M.
If the outermost symbol of  is , , , , we have to
prove that ’|-v() commutes with the meaning of all
Propositional connectives.
This follows by Completeness of ’ and the result on
Complete sets in Propositional Logic.
We have still to prove that ’|-v() commutes with the
meaning of , .
134
§ 3.2 Valuation Thm (1)
• By ’ Henkin Theory we have:
1. ’|- x ’|-[x:=t], for some tTERM0
2. ’ |-x  ’|- [x:=t], for all tTERM0
• We will prove that ’|-v() commutes with the meaning
of quantifier ,  using point 1, 2 above, inductive
hypothesis on [x:=t], and the trivial syntactical
identities:
a. v(x)
= x v[x:=x](),
b. v[x:=x][x:=t]()
= v[x:=t]()
• for all substitutions v, all terms t.
135
’|- v(x)  M
1.
2.
3.
5.
6.
7.
’|- v(x)
’|- xv[x:=x]()
for some closed term t:
’|-v[x:=x][x:=t]()
for some closed term t:
’|- v[x:=t]()
for some closed term t:
M |=v[x:=t] 
M |=v x
|=v x 
 (Identity a)
 (’ Henkin)
 (Identity b)
 (Ind.Hyp.)
 (def. of
|=)
136
’|- v(x)  M |=v x 
1.
2.
3.
5.
6.
7.
’|- v(x)
’|- xv[x:=x]()
for all closed term t:
’|-v[x:=x][x:=t]()
for all closed term t:
’|- v[x:=t]()
for all closed term t:
M |=v[x:=t] 
M |=v x
 (Identity a)
 (’ Henkin)
 (Identity b)
 (Ind.Hyp.)
 (def. of
|=)
137
§ 3.2 Valuation Thm (2)
•
•
•
•
•
•
Proof of (2): []v,M= [v()]w,M.
v is a closed substitution, hence v() is a closed
term. Thus, w(v()))=v(). From this fact and 1
we deduce, for all closed substitutions
v,w:VAR{closed terms}:
[]v,M = True

(point 1)
’|-v()

(w(v()))=v())
’|-w(v())

(point 1)
[v()]w,M = True
138
§ 3.2 Proof of Completeness
Theorem (weak form)
•
•
•
•
Assume  is consistent, with possibly free variables.
We have to define some model M and some valuation
v such that []v,M {True}.
Let c1,…, cn, …be fresh constants. Set s(xi)=ci for all
iN.
Then s()|- is not provable, otherwise, by replacing
back each ci with xi (and possibly renaming some bound
variable) also |- would be provable.
139
§ 3.2 Proof of Completeness
Theorem (weak form)
•
•
•
•
By the Weak form of Completeness, there is some
model in which [s()]v,M  {True} for any valuation
v.
By Valuation Thm., point 2, or all closed substitutions
s, v we have:
[s()]v,M = True  [s()]s,M = True
we conclude
[]s,M
 {True}
This concludes the proof of Weak Completeness
Theorem.
140
§ 3.2 Proof of Completeness
Theorem (strong form)
•
•
•
•
We will prove the contrapositive of Completeness: if
|- is not provable, then there is some model M and
some valuation v such that []v,M {True} but []v,M
= False.
If |- is not provable, by the Consistency Lemma
, is consistent.
We apply the weak form of the Theorem to ,, and
we find some model M and some valuation v such
that []v,M {True}, []v,M = True, that is,
[]v,M = False.
This concludes the proof of Strong Completeness
Theorem.
141
Lesson 4
Intuitionistic Logic
Strong Normalization
Normal Forms
142
Plan of Lesson 4
•
•
•
•
•
§ 4.1 Intuitionistic Logic. The interest of proofs
without Excluded Middle.
§ 4.2 Strong Normalization Results. All proofs may be
reduced to some canonical form.
§ 4.3 Structure of normal form. Using normalization,
we may interpret intuitionistic proofs as programs.
Previous Lesson:
Forthcoming Lesson:
Completeness Theorem
none.
143
§ 4.1 Intuitionistic Logic
• The Introduction rules for a connective c
may be seen as a definition of c.
• Elimination rules for c may be seen as
consequences of the definition of c.
• Double negation is the only rule not
justified by definition of some connective.
• Double negation is a Belief about Truth.
144
§ 4.1 Intuitionistic Logic
• We believe that in Nature all statements are
either true or false.
• Double negation is then justified by the
consideration that all statements which are
not false are true.
• Double Negation looks like some external
axiom,
breaking
the
Introduction/
Elimination symmetry of logical rules.
145
§ 4.1 Heyting Realization
Interpretation
• In a Natural Deduction Style of proofs, we obtain
Intuitionistic Logic by removing Double Negation Rule.
• In Intuitionistic Logic, some mathematical results are not
provable.
• In
Intuitionistic
Logic,
Introduction/Elimination
symmetry provides a simple interpretation of any proof of
 by some program of specification  (a program which
effectively does what  says).
• This interpretation was first proposed by Heyting, and
depends on the outermost connective of .
146
§ 4.1 Heyting Interpretation
of Atomic Formulas.
• A proof of an atomic formulas (x) should
provide, for all values of x, a proof of 
without logical connectives, by Post rules
only.
• In particular, no proof of  should exists
(unless we get it by Post Rules only).
147
§ 4.1 Heyting Interpretation
of Propositional Connectives.
• A proof for 1(x)2(x) should provide a pair of
a proof 1(x) and a proof of 2(x).
• A proof of 1(x)2(x) should provide a program
returning, for all x, either a proof of 1(x) or a
proof of 2(x) (thus, deciding, for each x,
whether 1(x) is true or 2(x) is true).
• A proof of (x)(x) should provide a program
returning, for all x, and all proofs of (x), some
proof of (x).
148
§ 4.1 Heyting Interpretation
of Quantifiers.
• A proof of x(x,x) should provide, for all
values of x and x, some proofs of (x,x).
• A proof of x(x,x) should provide, for all
values of x, both some value for x and some
proofs of (x,x).
149
§ 4.1 Heyting Interpretation
of Quantifiers.
• There is no Heyting interpretation for Excluded Middle,
by:
• Gödel Undecidability Theorem. There are some
arithmetical formulas (x), such that no computable
function (no computer program) is able is to decide
whether (x) is true or (x) is true.
• For such a (x), Heyting interpretation of (x)(x) is
false.
• Double Negation proves Excluded Middle, hence it has
no Heyting Interpretation as well.
150
§ 4.1 Heyting Interpretation
of Quantifiers.
• Heyting interpretation is bridge between
(intuitionistic) proofs and programming: .
• Out of, say, an intuitionistic proof of
x.f(x,x)=0 Heyting interpretation provides,
for all values of x, some x0 and some proof
of f(x0,x)=0.
• We will introduce a method, Normalization
providing an Heyting interpretation for
Intuitionistic Proofs in Natural Deduction.
151
§ 4.2 Normalization
• For all connectives c, every c-Elimination is
justified by the corresponding cIntroduction in the following sense:
• If we have some c-I followed by some c-E,
we may derive the conclusion of c-E just
by combining in some suitable way the
premises of c-I.
• We call any c-I followed by a c-E a c-Cut.
152
§ 4.2 Normalization
• Any c-Cut is, conceptually, a redundant step in
the proof, and it may be removed (often, at the
price of expanding the proof size considerably).
• For any c-Cut we define an operation removing it
we call a c-reduction.
• Removing a c-Cut may generated new Cuts.
• Yet, we will prove that if we repeatedly remove
cuts in any order, eventually we get a (unique)
proof without cuts.
153
§ 4.2 Normalization
• We call Normal any proof without Cuts, and
Normalization the process removing all cuts (in
any order).
• After Normalization, Intuitionistic Proofs satisfy
Heyting Interpretation.
• Thus, normalizing an intuitionistic proof of  is a
way of interpreting the truth of  as a program of
specification .
• We will now define some c-reduction for all c.
154
§ 4.2 Reduction Rule for 
D1 D2
1
2
--------12
--------i
Di
i
155
§ 4.2 Reduction Rule for 
D
i
\1
2
\
-------E1
E2
12


-------------------------------
D
i
Ei

156
§ 4.2 Reduction Rule for 
\
D

-------E


------------------
E

D

157
§ 4.2 Reduction Rule for 
D

-----x
--------[x:=t]
D[x:=t]
[x:=t]
158
§ 4.2 Reduction Rule for 
D
[x:=t]

-------E
x

-----------------
D
[x:=t]
E[x:=t]

159
§ 4.2 Subject Reduction
• If D is a proof of  with assumptions  we
write |- D:.
• We write D1E if we may obtain E out of
D by replacing some subtree of D with its
reduced version.
• A proof D have finitely many subtrees,
hence we have D1E for finitely many E.
• We write DE for “there is some chain D
1 D’ 1 D” 1 … 1 E” from D to E.
160
§ 4.2 Subject Reduction
• Subject Reduction Theorem. Reducing a
proof p we obtain a proof p’ having equal
hypothesis and conclusion:
|- D:,
DE

|-E:
161
§ 4.2 Strong Normalization
(definition)
• Reduction Tree. We call reduction tree the
tree of all reduction path from D.
• Strong Normalization. D strongly
normalizes iff its reduction tree is finite.
162
§ 4.2 Strong Normalization
Lemma
•
1.
2.
•
1.
2.
Strong Normalization Lemma.
D strongly normalize iff all D1E strongly
normalize.
If D ends by an introduction, it strongly normalizes
iff all its premises strongly normalize.
Proof.
Since D1E for finitely many E’s, the reduction tree
of D is finite iff the reduction tree of all D1E is
finite.
No reduction is defined over an Introduction.
163
§ 4.2 Strong Normalization
Theorem
• We state (not yet prove) the normalization
result we are looking for:
• Strong Normalization Theorem (or
Hauptsatz). All intuitionistic proofs
strongly normalizes.
164
§ 4.2 Computability
• In the strong normalization proof, we will actually
prove a notion of “computability” for a proof D,
implying Strong Normalization.
• Definition of Computable proof: by induction over the
proof D.
• D does not end with an Introduction. D is computable
iff all D1E are computable.
• D ends with an ,,-Introduction. D is computable iff
all its premises are.
• D ends with an , -Introduction:
next two pages
165
§ 4.2 Computability for -I
• The proof
D

-----x
• is computable iff for all tTERM,
D[x:=t]
[x:=t]
• is computable
166
§ 4.2 Computability for -I
• The proof

D

------
• is computable iff for all computable E,
• is computable.
E

D

167
§ 4.2 Computability Lemma
• Lemma (Computability Lemma).
1. Identity principle (a one-formula proof) is
a computable proof.
2. If D is computable, then D is strongly
normalizable.
3. If D is computable and D1E, then E is
computable.
168
§ 4.2 Computability, Point 1
1. Identity principle has no reduction. Thus,
trivially, all its reduction are computable.
Thus, Identity Principle is computable.
169
§ 4.2 Computability, Point 2
2.
•
•
Assume D is computable, in order to prove D strongly
normalizable. We argue by induction over the
definition of computable.
D does not end by an Introduction. Then all D1E
are computable, and by ind. hyp. strongly
normalizable. Thus, D itself is strongly normalizable.
D ends with an ,,-Introduction. Then all premises
of D are computable, and by ind. hyp. strongly
normalizable. Thus, D itself is strongly normalizable.
170
§ 4.2 Computability, Point 2,
-I case
•
The proof
•

-----x
is computable iff for all tTERM,
D
D[x:=t]
[x:=t]
•
are computable. By ind. Hyp., all such proofs strongly
normalizes.
171
§ 4.2 Computability, Point 2,
-I case
•
•
•
Take t=x: then
D

is strongly normalizable. Thus, also
D

-----x
is strongly normalizable.
172
§ 4.2 Comp., Point 2, -I case
• The proof

D

------
• is computable iff for all computable E,
E

D
• is computable. By ind. hyp., all such proofs strongly
normalize.

173
§ 4.2 Comp., Point 2, -I case
• Take E=the Identity Principle: then

D
• strongly normalizes. Thus,also

D

------
• strongly normalizes.
174
§ 4.2 Computability, Point 3
3.
•
•
Assume D is computable, in order to prove that all
D1E are computable. We argue by induction over
the definition of computable.
D does not end by an Introduction. All D1E are
computable by def. of computable.
D ends with an ,,-Introduction. If D is
computable, then all its premises are. By ind. hyp., all
one-step reductions of all premises of D are
computable. If D1E, this reduction takes place in
some premise of D. Thus, E is computable because E
ends with some ,,-Introd., and all its premises are
computable.
175
§ 4.2 Computability, Point 3,
-I case
•
The proof
•

-----x
is computable iff for all tTERM,
D
D[x:=t]
[x:=t]
•
are computable. By ind. hyp., if D[x:=t] 1 E[x:=t],
then E is computable.
176
§ 4.2 Computability, Point 3,
-I case
•
Take any reduction D1 E. Then D[x:=t] 1 E[x:=t],
hence
E[x:=t]
[x:=t]
•
•
is computable. Thus, also
E

-----x
is computable.
177
§ 4.2 Comp., Point 3, -I case

• The proof
D

------
• is computable iff for all computable E,
E

D

• is computable. By ind. hyp., if we replace D by any
D1 E, we get a computable proof.
178
• Take any reduction D1 E. Then for all computable D,
D

E
• is computable. Thus, also
• is computable.

E

------

179
§ 4.2 Computable
by Substitution and Replacing
• Definition. Assume |-D:, =1,…,n, and
FV(,){x1,….,xm}. D is computable by
substitution and replacing iff for all substitutions
s(.)=(.)[x1:=t1,….,xm:=tm], for all computable
proofs p|-D1:s(i), …, p|-Dn:s(n), the proof
• is computable
D1
Dn
s(1) … s(n)
s(D)
s()
180
§ 4.2 Strong Normalization
• Theorem (Strong Normalization)
• All intuitionistic proofs D are Computable
by Substitution and Replacing.
• As a Corollary, they are all Strongly
Normalizing.
181
§ 4.2 Strong Normalization
• Proof.
• By induction over D.
• We assume that all premises of D are
computable by substitution and replacing,
we take any composition and substitution
of D, and we check it is computable.
• We distinguish two cases, according if the
last rule in D is not an introduction, or it is
an Introduction.
182
§ 4.2 Strong Norm., Case 1
• Case 1: D not ending with some Introduction.
• we have to prove that all D1E are computable
by substitution and composition.
• If the c-reduction is applied to some premise of
D, the thesis follows by the inductive hypothesis
on the premises of D and the Computability
Lemma.
• If the c-reduction is applied to the conclusion
itself of D, the thesis is an immediate
consequence of the definition of computable for
c-Introduction, for each connective c.
183
§ 4.2 Strong Norm., Case 1
• An example. Assume that D is computable by
substitution and reduction, and that some -E:
D1
Dn
s(1) … s(n)
s(D)
s()
----x
--------[x:=t]
184
§ 4.2 Strong Norm., Case 1
•
reduces to
D1
Dn
s(1) … s(n)
s(D)
s()[x:=t]
• This latter proof is computable by:
1. ind. hyp. over the premise D of the rule -E;
2. definition of computability by substitution and
composition for such a D.
185
§ 4.2 Strong Norm., Case 2
• Case 2: D ending with an ,,-Introduction
• Any composition and substitution of the proof is
computable iff all its premises are.
• This latter fact follows immediately by inductive
hypothesis.
• Case 2: D ending with ,-Introduction. We
have to prove that these two rules preserve
computability by composition and substitution.
186
§ 4.2 Strong Norm., Case 2:
-I Preserves computability
Let x=x1,…,xm. Assume xFV(1, …, n),
and
D1
…
Dn
1[x:=t, x:=t] … n[x:=t, x:=t]
D [x:=t, x:=t]
[x:=t, x:=t]
• is computable for all sub. [x:=t, x:=t] on D.
187
§ 4.2 Strong Norm., Case 2,
-I Preserves computability
• x is the bound variable of -I.
• By possibly renaming x, we may assume
xFV(t):
[x:=t, x:=t] = ([x:=t])[x:=t]
• for all formulas .
• By xFV(1, …, n) we also obtain:
(i[x:=t])[x:=t] = i[x:=t]
188
§ 4.2 Strong Norm., Case 2
-I Preserves computability
• Thus, we may simplify the hyp. to:
D1
…
Dn
1[x:=t] … n[x:=t]
(D[x:=t])[x:=t]
([x:=t])[x:=t]
• is computable for all terms t, and all computable:
D1
Dn
1[x:=t], …, n[x:=t]
189
§ 4.2 Strong Norm., Case 2
-I Preserves computability
• By definition of computability for -I, we
conclude that
D1
Dn
1[x:=t]… n[x:=t]
D[x:=t]
[x:=t]
---------------x ([x:=t])
• is computable
190
§ 4.2 Strong Norm., Case 2
-I Preserves computability
Assume
D1
Dn

1[x:=t] ,…, n[x:=t] [x:=t]
D [x:=t]
[x:=t]
• is computable for all computable E.
191
§ 4.2 Strong Norm., Case 2
-I Preserves computability
Then
D1
Dn
1[x:=t], …, n[x:=t] [x:=t]
D [x:=t]
[x:=t]
--------------------[x:=t][x:=t]
\
• is computable by def. of computability for -I.
192
§ 4.2 Strong Normalization
(end of the proof)
• We checked that all proofs are computable by
substitution and replacing.
• If we replace each assumption i with the
Identity Principle for i, and each variable x by
itself, we re-obtain the original proof.
• We conclude they all proofs are computable,
and therefore all have a finite reduction tree.
• This ends the proof of Strong Normalization
Theorem.
193
§ 4.3 Normal Forms
• We will now study normal intuitionistic proofs.
• Then we will check that then intuitionistic
proofs satisfy Heyting Interpretation of logical
connectives.
• We introduce some terminology first.
• Main premise. The main premise of a logical
rule is the leftmost one.
• Main Branches. A branch in a proof tree is a
Main branch iff it includes, with each
conclusion of an Elimination, the Main premise
of such Elimination.
194
§ 4.3 Structure of
Normal Forms
• Lemma (Main Branch).
1. All Elimination rules have a non-atomic main
premise, and discharge no assumptions on the
branch main premise.
2. All main branches either include some cut, or,
from top to bottom, include first only
elimination rules, then only atomic rules,
eventually only introduction rules.
3. All Main Branches ending with an Elimination
rule include either some cut, or some free
assumption, or end with an introduction.
195
§ 4.3 Proof of
Main Branch Lemma
1. By inspecting all Elimination rules.
2. Assume there are no cuts, in order to prove that after
atomic rules there are only atomic rules or
Introductions, and after Introductions only
Introductions.
• Below atomic rules there are only atomic rules or
Introductions. The conclusion of an atomic rule can
only be atomic. Thus, it is either the conclusion, the
premise of another atomic rule, or of some
Introduction. It cannot be the main premise of an
Elimination rule, because such main premise is not
atomic.
196
§ 4.3 Proof of
Main Branch Lemma
•
•
Below Introductions there are only
Introductions. The conclusion of an
Introduction is not atomic, thus it cannot
be the premise of an atomic rule.
It can only be the conclusion of the proof,
or the premise of another Introduction. If
it were the main premise of an
Elimination we would have a cut.
197
§ 4.3 Proof of
Main Branch Lemma
3. If a main branch include no cuts, then all
Introductions are at the end of the branch.
If the last rule is not an Introduction, then
there are no Introductions at all, only
Eliminations and atomic rules. In this
case no formula is discharged when we
are going up the main branch. Thus, the
uppermost formula of the branch is a free
assumption.
198
§ 4.3 Strong Normalization
• Corollary (Cut-Free Proofs). In every cutfree and assumption-free proof, all Main
Branches end up either with some
introduction or with some atomic rule.
• All cut-free and assumption-free proof end
up with some introduction or with some
atomic rule.
199
§ 4.3 Strong Normalization
• Let  have outermost symbol some
predicate P, or some logical connective c.
• Corollary (Cut-free theorems). All normal
proofs of  end with, respectively, with
some atomic rule, or with some cIntroduction.
200
§ 4.3 Strong Normalization
• Corollary (Heyting interpretation for
Normal Proofs).
• If  has outermost symbol some predicate
P, then all normal proofs of  consists
only of atomic rules.
• There is no normal proof of  (unless
there is some proof of  using only
atomic rules).
201
§ 4.3 Strong Normalization
• Corollary
(Conservativity
over
atomic
formulas).
• Thus, logical rules deduce no new result about
atomic formulas:
• First Order Intuitionistic Logic is a conservative
extension of the system of atomic rules.
• This is a constructive result: we have some
method (to normalize) turning any proof of any
atomic P(t1,…,tn) in first order logic in some
proof of the P(t1,…,tn) using atomic rules.
202
§ 4.3 Strong Normalization
• Corollary (Heyting interpretation).
• Every normal proof of |-12 include, as
last step, some proof of some |-i.
• Every normal proof of |-12 include, as
last step, some proof of |-1 and some
proof of |-2.
• Every normal proof of |-12 include, as
last step, some proof of 1|-2.
203
§ 4.3 Strong Normalization
• Corollary (Heyting interpretation)
• Every normal proof of |-x include, as
last step, some proof of .
• Every normal proof of |-x include, as
last step, some proof of some [x:=t].
204
§ 4.3 Strong Normalization
• By combining the result about normal form
with the fact that every proof may be
normalized, we obtain:
• |- 12  |- i for some i{1,2}
• |- x  |- [x:=t] for some tTERM
205
§ 4.3 Strong Normalization
Result about ,  hold only for
Intuitionistic Logic.
• In Classical Logic:
1. we have |- even if nor |-, neither |;
2. we have |-x even if |-[x:=t] for no
tTERM.
•
206
Realizability: Extracting
Programs from proofs
Summer School on Proofs as Programs
2002 Eugene (Oregon)
Stefano Berardi Università di Torino
[email protected]
http://www.di.unito.it/~stefano
207
The text of this short course on
Realizability, together with the text of the
previous short course on Logic, may be
found in the home page of the author:
http://www.di.unito.it/~stefano
(look for the first line in the topic:
TEACHING)
208
Plan of the course
• Lesson 5. Realization Interpretation. A
Model of Realizers. Harrop Formulas.
• Lesson 6. The problem of Redundant code.
209
Reference Text
• L. Boerio “Optimizing Programs Extracted
from Proofs”. Ph. D. Thesis, C. S. Dept.
Turin University, 1997.
• Available in the web page of the course:
http://www.di.unito.it/~stefano
• (look for the first line in the topic:
TEACHING)
210
Lesson 5
Realization Interpretation
A Model of Realizers
Harrop Formulas
211
Plan of Lesson 5
• § 5.1 Realization
• § 5.2 A Model of Realizers
• § 5.2 Harrop Formulas.
212
§ 5.1 Realization Interpretation
• In the previous course, we showed how, in
Intuitionistic Logic, any proof D of  may be
interpreted with some effective operation r
associated to .
• Now, we will call such an r a Realizer of .
• In the simplest case, r is the proof D itself,
executed through normalization.
• Yet, in order to effectively use Heyting
Interpretation, is is convenient to think of r as a
separate object.
• We will now reformulate Heyting interpretation
213
in term of Realizers.
§ 5.1 Realization Interpretation
• We will abbreviate the statement “r is a realizer
of ” by “r: ”.
• Language will be: multi-sorted language for
Integers and Lists of integers, with induction over
Integers and over Lists.
• x denotes any sequences of variables, each
labeled with its type, which is Integer or List.
• Quantifiers are: yT.(x,y), yT.(x,y), with
T=Integers, Lists.
214
§ 5.1 Realization Interpretation
• All what we will say applies not just to
T=Integers, List
• but also to
T=any Bohm-Berarducci Data Types
(of cardinality > 1)
• Look at Boerio Ph.d in the course Web page
if you want to learn more.
215
§ 5.1 A simply typed -calculus
• We choose as r some simply typed lambda term,
with Data Types
Unit={unit}, Bool={True,False}, N={0,1,2,3,..},
List={nil, cons(n,nil), cons(n,cons(m,nil)), …}
• as base types, with product types, and including
if, and primitive recursion recN, recL over
integers and lists.
• (We could take any simply typed lambda term +
Bohm-Berarducci Data Types).
• We distinguish, in the definition of r:, one case
for each possible outermost symbol of .
216
§ 5.1 Dummy constants.
•
•
1.
2.
3.
4.
5.
6.
For each simple type T, we we will need some
dummy element dummyT:T (just dT for short),
to be used as default value for such type.
We define dT:T by induction over T.
dummyUnit
= unit
dummyBool
= False
dummyN
=0
dummyList
= nil
dummyTU
= x. dummyU
dummyTU
= <dummyT, dummyU>
217
§ 5.1 Realization Interpretation
of Atomic Formulas.
• r:P(t1,…,tm)  r=unit, and some proof of 
without logical connectives exists.
• We chose r=unit because a proof of an
atomic formula correspond to an empty
operation, therefore to a dummy value.
• The type Unit={unit} is the type of empty
operations.
218
§ 5.1 Realization Interpretation
of Propositional Connectives.
• r(x):1(x)2(x)  r(x)=<r1(x),r2(x)> and
r1(x):1(x), r2(x):2(x)
• r(x):1(x)2(x)  r(x)=<i(x),r1(x),r2(x)> with
i(x)Bool
i(x)=True  r1:1(x)
i(x)=False  r2:2(x)
(if i(x)=True, the canonical choice for r2 is a
dummy constant, and conversely)
• r(x):1(x)2(x)  for all s:1(x), r(x)(s):2(x) 219
§ 5.1 Realization Interpretation
of Quantifiers.
• r(x):yT.(x,y)  for all yT,
r(x,y):(x,y)
• r(x):yT.(x,y)  for some y(x)T
r(x)=<y(x),s(x)>,
with s(x):(x,y(x))
220
§ 5.1 Realization Interpretation
• According to our definition, a realizer
r:yT.(f(x,y)=0) is some pair r(x)=<y(x),unit>,
of a function y=y(x):T, solving the equation
f(x,y)=0 (w.r.t. the parameters in x), and some
(dummy) realizer unit of f(x,y)=0.
• yT.(f(x,y)=0) says “there is a solution to
f(x,y)=0, parametric in x”, while r finds it.
• r:yT.(f(x,y)=0) may be seen as a program
whose specification is yT.(f(x,y)=0).
• Realization interpretation turns any intuitionistic
proof of solvability of some equation, into a
program which effectively solves such equation. 221
§ 5.1 Realization Interpretation
of Formulas.
• Let  be any closed formula. The previous
clauses implicitly defined some simple type ||
for all r:. Definition is by induction over .
• |P(t1,…,tm)|
= Unit
• |12|
= |1|  |2|
• |12|
= Bool  |1|  |2|
• |12|
= |1|  |2|
• |xT.|
= T  ||
• |xT.|
= T  ||
222
§ 5.1 Realization Interpretation
of Formulas.
• If x=x1,…,xn is a vector of variables of types
T1,…, Tn, then |(x)| = T1…Tn|| is the type
of all r:(x).
• Let ={1,…,n} and x=x1,…,xk. We may turn
every proof p:(x), with free assumptions in ,
into some realizer r=|p| of (x), depending on
free variables in x, and on the realizer variables
1:|1(x)|, …, k:|k(x)|.
• Definition is by induction on p, with one clause
for each possible rule at the conclusion of p.
223
§ 5.1 Assigning Realizers
•
Atomic rules. If p end by some Atomic rule,
then r(x)=unit.
…
…
unit: P1(t1) … unit: Pm(tm)
---------------------------unit: P(t)
•
If |- unit: P1(t1), …, |- unit: Pm(t1), then |unit: P(t)
224
§ 5.1 Assigning Realizers
•
•
Rules for 
Introduction rules:
s1:  s2: 
------------------<s1,s2>:   
•
If |- s1:  and |- s2:  then |- <s1,s2>:  

225
§ 5.1 Assigning Realizers
•
•
Elimination rules:
s:   
---------1(s): 
s:   
---------2(s): 
If |- s:   , then |- 1(s):  and |2(s): 
226
§ 5.1 Assigning Realizers
•
•
•
•
Rules for . Let T=True, F=False, and _, _’, be
dummy elements of ||, ||.
Introduction rules:
r: 
s: 
--------------------------------------<T,r,_’>:   
<F,_,s>:   
If |- r: 
If |- s: 
then |- <T,r,_’>:   
then |- <F,_,s>:   
227
§ 5.1 Assigning Realizers
Elimination rules for . Let
u = if (i=True) then s(a) else t(b)
Then
:
:
…
…
<i,a,b>:    s(): 
t(): 
---------------------------------------------u: 
•
\
•
\
If |- r:  and , :|- and , :|-, then
228
|- u: 
§ 5.1 Assigning Realizers
•
Rules for . Introduction rule:
:
…
s(): 
------------------- .s():
\
•
If , : |- s(): , then |- .s(): 
229
§ 5.1 Assigning Realizers
•
•
Elimination rule:
r:
s:
------------------------r(s):
If |-r: and |-s:, then  |-r(s):.
230
§ 5.1 Assigning Realizers
•
Rules for : Introduction rule.

…
r: [x:=t]
------------------<t,r>: xT.
•
If |- r:[x:=t] for some t, then |- <t,r>: x
T.
231
§ 5.1 Assigning Realizers
•
Rules for : Elimination rule.

 , :
…
…
<i,a>: xT.
t(x,): 
----------------------------------t(i,a): 
\
•
•
Provided xFV(,).
If |-<i,a>:xT., ,:|-t(x,):,
xFV(,), then |- t(i,a):
and
232
§ 5.1 Assigning Realizers
•
•
•
Rules for : Introduction rule.

…
r:
----------------x.r:xT.
Provided xFV()
If |- r: and xFV(), then |- x.r:xT.
233
§ 5.1 Assigning Realizers
•
Rules for : Elimination rule.

…
f:xT.
--------------f(t):[x:=t]
•
If |- f:xT., then |-f(t):[x:=t] for all t
234
§ 5.1 Assigning Realizers
• Induction Axiom for the type N=Integers :
Rec: xN.([x:=0]xN.([x:=x+1]))
• Rec has type: N||(N||||)||
• Let n:N, r:||, s:N||||.
• We inductive define Rec(n,r,s):|| by:
1. Rec(0,r,s)
=r
2. Rec(n+1,r,s) = s(n,Rec(n,r,s))
235
§ 5.1 Assigning Realizers
•
Induction Axiom for the type L=Lists:
RecL: lL.([l:=nil]
lL, xN.([l:=cons(x,l)])
)
• We abbreviate AB…C by A,B,…C.
• RecL has type: L,||,(L,N,||||)||
• Let n:N, r:||, s:L,N,||||.
• We inductive define RecL(n,r,s):|| by:
1. RecL(nil,r,s)
=r
2. RecL(cons(n,l),r,s) = s(l,n,Rec(l,r,s))
236
§ 5.2 A Model for Realizers
•
•
1.
2.
3.
4.
5.
6.
In order to study the behavior of Realizers we
first define a model for them.
For each simple type T there is some settheoretical interpretation [T]Set:
[Unit] = {unit}
[Bool] = {True,False}
[N]
= {0,1,2,3,…}
[L]
= {nil, cons(n,nil), …}
[TU] = [T][U] (Cartesian Product)
[TU] = {set theoretical functions :[T][U]}237
§ 5.2 Harrop Types
•
•
•
•
•
The set-theoretical interpretation of types may
be extended to an interpretation of terms.
We write t=Setu iff t, u has the same
interpretation in the Set-Theoretical Model
(under all valuations).
Denote the cardinality of [T] by C([T]).
For all types T: C([T])1 (because dummyT:T)
We say that H is an Harrop type (simply is
Harrop, for short) iff C([T])=1 (iff t=Setu for all
t,u:H).
238
§ 5.2 Characterizing Harrop
Types
•
1.
2.
3.
•
1.
2.
Lemma (Harrop Lemma).
Unit is Harrop. Bool, N, L are not Harrop.
HH’ is Harrop  H, H’
are Harrop.
TH is Harrop  H
is Harrop
Proof.
C({unit})=1,C({True,False}),C({0,1,2,..})>1,...
C([HH’]) = C([H])C([H’]) = 1 iff C([H]) =
C([H’]) =1.
3. C([TH]) = C([H])C([T])=1 iff C([H]) = 1
(because C([T])1 ).
239
§ 5.3 The Harrop(.) map
•
•
•
•
•
•
•
A term u is Harrop iff its type is.
We may decide if u is Harrop.
If u:U is Harrop, then [U] is a singleton and
u=SetdummyU.
Denote with Harrop(t) the term obtained out of
t by replacing any maximal Harrop subterm
u:U of t with dummyU.
Theorem. t=SetHarrop(t).
Proof. We defined Harrop(t) by replacing some
subterms of t with some equal terms.
The map Harrop(.) is some simplification240
procedure over Realizers. What does it do?
§ 5.3 The Harrop(.) map
•
•
•
•
If  is any first order formula, we say that  is
Harrop iff || is Harrop.
If  is an Harrop formula, then all r: are
replaced with dummy|| by the map Harrop(.).
Therefore, all Realizers r: correspond to
some dummy operation.
Thus, we are interested in characterizing the set
of Harrop formulas , in order to learn which
realizers are (necessarily) dummy.
241
§ 5.3 Harrop formulas
•
•
•
•
•
•
If =P(t), then ||=Unit is Harrop.
If =12, then ||=|1||2| is Harrop iff
|1|,|2| are.
If =2, then ||=|||2| is Harrop iff |2|
is Harrop.
If =xT.2, then ||=T|2| is Harrop iff
|2| is Harrop.
If =12, then ||=(|1||2|)(|2||1|) is
Harrop iff |1|, |2| are Harrop.
If =12, xT.2, then  is not Harrop,
because ||=Bool|1||2|, T|2| have
242
cardinality > 1 (because T has cardinality > 1).
§ 5.3 Characterizing
Harrop Formulas
•
•
•
•
Theorem (Harrop formulas). The set of
Harrop formula is the smallest set including:
all atomic formulas, and with 1, 2, also
12, xT.2, 12, and 2 (with any
 formula).
We may decide if a formula  is Harrop.
All proofs of Harrop formula  may be
neglected if we are looking for the program
hidden in a proof: they generate a dummy
realizer.
243
§ 5.3 Some Harrop Formulas
•
•
•
•
Negations. All  are Harrop, because
=(), and  is Harrop. Thus, any
statement defined through a negation may
be neglected.
Examples are:
“x is not a square”,
“x is a prime element = no y, z are a
factorization of x”.
244
§ 5.3 Some Harrop Formulas
•
Universal properties. All quantification
x1,…,xn f(x1,…,xn) = g(x1,…,xn)
• are Harrop.
• This set includes:
1. Associativity, Commutativity, all equational
identities.
2. “l is sorted = every element in l but the last is 
of the next one”
3. “l, m are permutations = for all x, the number
of times x is in l and m is the same”.
245
§ 5.3 Some Harrop Formulas
•
Note. Being Harrop depends on the exact
formal definition we choose.
• For instance: if we formally define
“l, m are permutations”
• by
“there is some permutation sending l into m”
• then the statement we obtain is not Harrop
(because of the existential quantifier in it).
246
§ 5.3 Logical Parts
•
•
•
•
Summing up: subproofs whose conclusion is
an Harrop formulas correspond to purely
logical parts of the proof.
A proof of an Harrop formula defines no action.
Yet, it may be used in order to prove that the
action defined by the proof is correct.
For instance, if we look for a solution of (x23x+2)=0, and we found some a such that
(a2+2=3a), then using the Harrop statement
x,yN.(x2-3x+2)=0  (x2+2=3x),
we may prove that a solves the original
247
equation (x2-3x+2)=0.
Appendix to § 5: an example
•
•
•
•
•
We extract a toy sorting algorithm out of a
proof that all lists may be sorted.
Assume Perm(l,m), Sorted(m) are fresh
predicate letter, whose meaning is: l, m are
permutations, and m is sorted.
Assume we already proved that ordering on N
is total: x,yN.(xy  yx).
We are going to prove:
 = lT.mT. (Perm(l,m)  Sorted(m))
A realizer r: has type ||=LLH, for some
H Harrop (Perm(l,m), Sorted(m) are Harrop,
248
hence their conjunction is).
Appendix to § 5: an example
•
Any r: takes some list l, and returns some pair
r(l)=<m,_>, with:
1. m = sorted version of l;
2. “_” = some realizer of type H, corresponding to
some proof of (Perm(l,m)  Sorted(m)).
• If we apply the simplification Harrop(r), then
“_” is replaced by dummyH (some dummy
constant).
• Replacing “_” by dummyH is computationally
correct: any proof of (Perm(l,m)  Sorted(m))
states something about l, m, but it performs no
249
action on l, m.
Appendix to § 5: an example
•
•
•
•
•
We argue by induction over lists.
Base case: nil. We have to prove
mT.S(nil,m). We just set m=nil. We have to
prove Perm(nil,nil) and Sorted(nil).
Inductive case: x*l for some xN. By ind.
hyp., Perm(l,m) and Sort(m) for some mList.
We will prove a Lemma: for all m, if
Sorted(m), then all x*m have some sorted
version p (that is: Perm(x*m,p) and Sorted(p)).
Out of the Lemma, we conclude Perm(x*l,
x*m), and by transitivity of Perm, Perm(x*l,p),
250
Q.E.D..
Appendix to § 5: an example
•
•
•
•
The Lemma is proved by induction over
m.
Base case of the Lemma: m=nil.
We choose p=x*nil. We have to prove
Perm(x*nil, x*nil), Sorted(x*nil).
Inductive case of the Lemma. Let m=y*q
for some q. We distinguish two subcases:
xy and yx.
251
Appendix to § 5: an example
•
•
Subcase xy. By second ind. hyp. we have
Perm(y*q,r) and Sorted(r) for some r. We
choose p=x*r. We have to prove that if
Perm(y*q, r) and Sorted(r) and xy, then
Perm(x*y*q, x*r) and Sorted(x*r).
Subcase xy. We just reverse the roles of x, y.
By second ind. hyp. we have Sort(x*q,r) for
some r. We choose p=y*r. We have the same
proof obligation (with x, y exchanged), plus
Perm(x*y*q, y*x*q).
252
Appendix to § 5: an example
•
•
•
•
Proof obligations. we list here the subproofs
we did not fill in (and we will actually skip).
Sorted(nil) and Sorted(x*nil): by def. of Sorted.
Perm(nil,nil),
Perm(x*y*q,
y*x*q),
if
Perm(l,m), then Perm(x*l,x*m), and if
Perm(l,m) and Perm(m,p), then Perm(l,p): all
come by def. of Perm.
If Perm(y*q, r) and Sorted(r) and xy, then
Sorted(x*r): this is intuitive, yet it is a little
tricky to prove formally.
253
Appendix to § 5: an example
•
•
•
All such proofs obligation are only
included to show that sorting is done
correctly: they do not influence the Sorting
Algorithm in the proof.
We do not include here.
Formal proofs may be found in the Web
site of Coq group.
254
Appendix to § 5: an example
•
•
•
•
•
We may already precise the algorithm we get,
without knowing the proofs of Harrop
statements (they will eventually be removed).
We only have to carefully apply the inductive
definition of realizer, and to replace by a
dummy constant all Harrop subterms.
We write the program in the next page, using
green color for all Harrop part (a color difficult
to see, to stress that they are totally irrelevant).
Let “less” be a realizers of x,yN.(xyyx).
“less” has type N,NBoolUnitUnit, and
255
less(x,y)=<True,_,_>  xy.
Appendix to § 5: an example
•
•
•
sort(l)=recL(l,<nil,_,_>, x:N,m:L.ins(m,x,_))
: LUnitUnit
The map ins:LUnit(NLUnitUnit) takes
some sorted list m, and returns some map
ins(m), inserting any integer x in m, and
preserving the ordering of m:
ins(m) = _:Unit. recL(m,
x:N. <x*nil,_,_>
y:N, f:NLH, x:N.
if(1(less(x,y)),x*f(y),y*f(x))
):NLUnitUnit
256
Lesson 6
Program Extraction from proofs
Useless Code Analysis
257
Plan of Lesson 6
• § 6.1 Useless Code. In Program Extraction.
• § 6.2 Useless Code Analysis.
• Previous Lesson: Realization Interpretation.
• Next Lesson: none.
258
§ 6.1 Useless Code
• Useless Code. Large program are often cluttered
with useless code.
• If a program is large, most of it comes from
previous programs, or was designed some time
ago, and it originally performed slightly different
tasks.
• Thus, there are old tasks of no more interest,
producing results of no use.
• Such useless tasks require memory space and
time to initialize and update parameters of no
more use.
259
§ 6.1 Useless Code
• Useless code may slow down a computation
considerably.
• Removing it is one of the problem we have to
face in programming.
• To detect and remove useless parts is
conceptually simple
• Yet, it is really time consuming.
• Thus, useless code removal is often automatized.
260
§ 6.1 Useless Code and
Program Extraction
• Extracting program from proofs produces a
large amount of useless code.
• In the previous lesson we introduced a simple
example: Harrop subterms of any Realizer.
• Harrop subterms correspond to purely logical
parts of the proof: to the parts of a proof defining
no action, but showing the correctness of some
action performed by the proof.
261
§ 6.1 Useless Code and
Program Extraction
• Logical part of a proof are of interest only if we
want to produce a proof.
• They are of no more interest when our task is to
write a program.
• Thus, Logical parts (subproofs with an Harrop
conclusion) are a typical example of useless
code: they were of some use in the proof, they are
of no further use now in the Realizer.
• There are many more examples of useless code in
program extracted from proofs.
262
§ 6.1 Useless Code and
Program Extraction
• We look now through some examples of
useless code in Realizers which is included
in no Harrop subterm.
• Such examples are written in an extension of
the language for Realizers from the
previous lesson: simply typed lambda
calculus + all Bohm-Berarducci Data Types.
• For a formal description of this language we
refer to Boerio Ph.d..
263
§ 6.1 Useless Code and
Program Extraction
• Some hint about the language for Data Types.
Each data type D has finitely many constructors
c1, …, cn. Each ci has type T1, …, TkiD, with Ti
either previously defined type, or D itself.
• Constructors true:D, false:D: then D is Bool.
• Constructors in1:A1D, …, inn:AnD: then D is
A1+…+An.
• Constructor <_>:A1,…,AnD: D is A1… An.
• Constructors zero:D, s:DD: then D={integers}.
• Constructors nil:D, cons:A,DD: then D is {lists
264
on A}
§ 6.1 Useless Code and
Program Extraction
• Some hint about the language for Data Types. If
D has constructors c1:T1[D], …, cn:Tn[D], then
we denote D by:
X.(T1[X], …, Tn[X])
(the smallest X closed under c1, …, cn)
• For each data type D we add a primitive recursor
recD. Some examples are:
• D=Bool. Then recD=if.
• D=A1+…+An. Then recD=case.
• D={integers}, {lists}. Then recD was defined in
265
the previous lesson.
§ 6.1 Example 0
• A particular case of Useless Code: Dead code. A
subterm t is dead code if, whatever the input
values are, there is an evaluation strategy not
evaluating t.
• A trivial example: 3 is dead code (never used) in
(x.5)(3).
• Usually, it is not so easy to detect dead code! It is
even a non-recursive problem.
• Indeed, to decide whether b is dead code in
if(h(x)=0,a,b) we have to decide whether h(x)=0
for all x, or not, and this is a non-recursive266
problem.
§ 6.1 Example 1
• Let p a program of input x, of type A or B or C.
• Let q be a program feeding such an x, but with
possible types only A, B. Compose p with q.
• Consider any “case analysis” in p over the type of
the input x. There are three clauses, according if
the type of x is A or B or C.
• The “C” clause is now dead code: it is never used
• Such situation may happen if we extract a
program from a proof having a Lemma slightly
more general than required: we prove ,
then we apply it to  (instead of ).
267
§ 6.1 Example 1
•
1.
2.
3.
•
Let for instance p:A+B+CE defined by:
p = x:A+B+C. case(x,a(x),b(x),c(x))
q = j°f, with f:DA+B
j: A+BA+B+C canonical injection.
Then c(x) is never used, because x is
obtained from f, hence is not in C.
268
§ 6.1 Example 2
• The most general case of Useless code is a
code never affecting the final result, even if
it may be used for some inputs.
• Let h(n,a,b) = <an,bn>:AB be recursively
defined by:
• <a0, b0>
= <a, b>
: AB
• <ai+1,bi+1>
= <f(ai), g(bi)> : AB
• Define k(n) = (left component of h(n)) :A.
269
§ 6.1 Example 2
• Look to the computation of k(n):
<a,b>, <f(a),g(b)>, <f(f(a)),g((b))>, ..., <fn(a),gn(b)>
• Eventually we trash gn(a) and we return an=fn(a).
• g, b are dead code in k (they are never used,
under a suitable evaluation strategy).
• The pairing operation <_,_> is useless code in k:
it is indeed used, however, it never affects the
final result an=fn(a).
• Again, this situation may arise in a Realizer if we
proved a Lemma having a goal slightly more
270
general than required.
§ 6.1 Example 3
• Let length(L) be a function taking a list L,
then returning the length n of it.
• Look at the computation of length(L).
• L = cons(x1,cons(x2,...cons(xn)...)), but the
actual values of x1, x2,... xn do not matter.
• Eventually, we trash all xi’s, and we return
the number of cons’s.
271
§ 6.1 Example 3
• All elements of L are now useless code in f.
• We compute the elements of L, using an
unpredictable amount of time; yet, we do not
use them in order to compute length(L).
• This situation may arise in a Realizer when:
• we first prove the existence of L, then, in the
rest of the proof, we only use the number of
elements of L.
272
§ 6.2 Useless code Analysis
•
•
•
•
•
In order to perform Useless code Analysis, we
extend the language with subtyping.
We add a dummy type Unit  A for typing dead
code, the constant unit:Unit, the typing rule: if
a:A, then a: Unit.
Data types are covariant: if A’A, B’B, then
A’B’  AB.
Arrow is contravariant: if A  A’ , B’  B, then
A’B’  AB.
We allow now null constructor c:Unit in a Data
Type D. Such constructors build no term: they
273
intend to represent redundant code in D.
§ 6.2 Useless code Analysis
•
•
•
•
For each type A, we may define some trivial
term dummyA:A by induction on A.
The type Unit represents the set of all terms,
with trivial equality: all terms of type Unit are
intended to be equal.
If we quotient Unit up to its equality notion, we
get only one equivalent class: Unit is a
cardinality 1 type.
As we did in the previous lesson, we define
Harrop types as types of cardinality 1 in the settheoretical model. Unit is an Harrop type.
274
§ 6.2 Useless code Analysis
• Definition. A subtype is strictly positive iff it
occurs in the left-hand side of no arrow type,
including arrows in constructor types.
• Lemma 1. A is Harrop iff it is an Harrop type
w.r.t Unit (iff any strictly positive atomic type in
A is Unit).
• Corollary 1. For any term t having an Harrop A,
t=dummyA in the set-theoretical model.
• Corollary 2. Let t : A, and Hp(t) be obtained by
replacing all subterms v having an Harrop B by
dummyB. Then t and Hp(t) are observationally
275
equal of type A.
§ 6.2 Useless code Analysis
• Remark. Corollary 2 says that each subterm of
Harrop type is useless, because it may be
replaced by a dummy constant without altering
the value of the term.
• Hence Hp(t) removes useless code in t.
• We will introduce now a redundant code analysis
much more general than in the previous lesson:
before applying Hp, we will retype any term in
order to maximize subterms with an Harrop type.
276
§ 6.2 Main Results
• Theorem 1. Assume |-t:A.
• Retype with Unit some parts of t in such a
way to preserve the condition |-t:A.
• Then replace all subterms v of t now having
an Harrop type B by the constant dummyB.
• The term u we obtain in this way is equal to
t in the set-theoretical model.
277
§ 6.2 Main Results
•
Theorem 1 outlines method for removing
useless code.
• We have only to select some retyping of t
which:
1. is correct, and
2. does not change the final typing |-t:A of t.
• Let u be the resulting term. Then every subterm
in t which got a type U is useless, and it may be
removed by forming Hp(u).
278
§ 6.2 Main Results
•
Main Theorem. Let t be any term of simply
typed lambda calculus with Bohm-Berarducci
Data Types.
• Order terms we get by a retyping of t according
to the set of Harrop subterms they have.
1. This order has a maximum, a term u having a
maximum of Harrop subterms. Denote u by
Fl(t).
2. Fl(t) may be computed in linear time over the
type-decorated version of t.
279
§ 6.2 Using Fl(t)
• Fact. Fix any term t from the Examples 1-3.
Then all dead code we found belongs to
some Harrop subterms of Fl(t).
• Thus, all dead code in Examples 1-3 may be
removed by first computing Fl(t), then
Hp(Fl(t)).
• By construction, context and type of t and
Hp(Fl(t)) are the same, and t=SetHp(Fl(t)).
280
§ 6.2 The “Iso” map
• Some further optimization may be obtained
by applying a new map, Iso (not to be
included here) to the term Hp(Fl(t))
• Iso(.) removes some useless code which is
not dead.
• Example are: Iso(.) turns <a,u>,<u,a>, p1(a)
(if a:AU), p2(a) (if a:UA) into a.
• Iso(.) is but a minor detail.
281
§ 6.2 About Efficiency
1. Fl(p) is computed using saturation over a
subset of the adjacency graph of typing
assignment. Thus, Fl is an higher-order
version of Flow algorithm for compilers.
2. The type-decorated version p’ of p is, in
theory, exponential in p. Thus, in theory, Fl,
which is linear in the size of p’, is
exponential.
3. In programming practice, however, p’ is
feasible to compute. So Fl is feasible, too.
4. In 2000, N. Kobayashi found a way to get
282
rid of exponential time.
§ 6.2 Up-to-date: Year 2000
• N. Kobayashi (C.S., Tokyo Univ.). For languages
with let-polymorphism, Fl(t) may be found in
time (n log*(n)) over the size of the untyped
program t.
• We explain what is log*(n) in the next slide.
• Kobayashi idea is merging the algorithm
inferring the type with the algorithm inferring
useless code out of typing.
• In this way, we do not have to apply type
inference to subterms with an Harrop type,
because they are redundant code and they will be
283
removed.
§ 6.2 log*(n)
•
1.
2.
3.
4.
5.
•
•
Log*(n) is the inverse of exp*(n) = expn(1) …
(the
2
super-exponential, or a tower of n digits: 22
log*(2)
= log*(2) = 1
log*(4)
= log*(22) = 2
2
log*(16)
= log*(22 ) = 3
22
2
log*(65536) = log*(2 ) = 4
For n  265536, we have log*(n)  5.
265536 is a number of 19,729 digits!
O(n*log*(n)) is, in practice, O(n*5) = O(n).
284
§ 6.2 References
• “Type-bases useless code elimination for
functional programs (Position Paper)”, by
S. Berardi, M. Coppo, F. Damiani and P.
Giannini, to appear on proceeding of SAIG
conference on functional programming.
• “Automatic Useless code detection and
elimination
for
HOT
functional
programs”, by F. Damiani, P. Giannini,
J.F.P. 10 (6): 509-559, 2000.
285