1 theory Tutorial3 |
|
2 imports Lambda |
|
3 begin |
|
4 |
|
5 section {* Formalising Barendregt's Proof of the Substitution Lemma *} |
|
6 |
|
7 text {* |
|
8 The substitution lemma is another theorem where the variable |
|
9 convention plays a crucial role. |
|
10 |
|
11 Barendregt's proof of this lemma needs in the variable case a |
|
12 case distinction. One way to do this in Isar is to use blocks. |
|
13 A block consist of some assumptions and reasoning steps |
|
14 enclosed in curly braces, like |
|
15 |
|
16 { \<dots> |
|
17 have "statement" |
|
18 have "last_statement_in_the_block" |
|
19 } |
|
20 |
|
21 Such a block may contain local assumptions like |
|
22 |
|
23 { assume "A" |
|
24 assume "B" |
|
25 \<dots> |
|
26 have "C" by \<dots> |
|
27 } |
|
28 |
|
29 Where "C" is the last have-statement in this block. The behaviour |
|
30 of such a block to the 'outside' is the implication |
|
31 |
|
32 A \<Longrightarrow> B \<Longrightarrow> C |
|
33 |
|
34 Now if we want to prove a property "smth" using the case-distinctions |
|
35 P1, P2 and P3 then we can use the following reasoning: |
|
36 |
|
37 { assume "P1" |
|
38 \<dots> |
|
39 have "smth" |
|
40 } |
|
41 moreover |
|
42 { assume "P2" |
|
43 \<dots> |
|
44 have "smth" |
|
45 } |
|
46 moreover |
|
47 { assume "P3" |
|
48 \<dots> |
|
49 have "smth" |
|
50 } |
|
51 ultimately have "smth" by blast |
|
52 |
|
53 The blocks establish the implications |
|
54 |
|
55 P1 \<Longrightarrow> smth |
|
56 P2 \<Longrightarrow> smth |
|
57 P3 \<Longrightarrow> smth |
|
58 |
|
59 If we know that P1, P2 and P3 cover all the cases, that is P1 \<or> P2 \<or> P3 |
|
60 holds, then we have 'ultimately' established the property "smth" |
|
61 |
|
62 *} |
|
63 |
|
64 subsection {* Two preliminary facts *} |
|
65 |
|
66 lemma forget: |
|
67 shows "atom x \<sharp> t \<Longrightarrow> t[x ::= s] = t" |
|
68 by (nominal_induct t avoiding: x s rule: lam.strong_induct) |
|
69 (auto simp add: lam.fresh fresh_at_base) |
|
70 |
|
71 lemma fresh_fact: |
|
72 assumes a: "atom z \<sharp> s" |
|
73 and b: "z = y \<or> atom z \<sharp> t" |
|
74 shows "atom z \<sharp> t[y ::= s]" |
|
75 using a b |
|
76 by (nominal_induct t avoiding: z y s rule: lam.strong_induct) |
|
77 (auto simp add: lam.fresh fresh_at_base) |
|
78 |
|
79 |
|
80 |
|
81 section {* EXERCISE 10 *} |
|
82 |
|
83 text {* |
|
84 Fill in the cases 1.2 and 1.3 and the equational reasoning |
|
85 in the lambda-case. |
|
86 *} |
|
87 |
|
88 lemma |
|
89 assumes a: "x \<noteq> y" |
|
90 and b: "atom x \<sharp> L" |
|
91 shows "M[x::=N][y::=L] = M[y::=L][x::=N[y::=L]]" |
|
92 using a b |
|
93 proof (nominal_induct M avoiding: x y N L rule: lam.strong_induct) |
|
94 case (Var z) |
|
95 have a1: "x \<noteq> y" by fact |
|
96 have a2: "atom x \<sharp> L" by fact |
|
97 show "Var z[x::=N][y::=L] = Var z[y::=L][x::=N[y::=L]]" (is "?LHS = ?RHS") |
|
98 proof - |
|
99 { -- {* Case 1.1 *} |
|
100 assume c1: "z = x" |
|
101 have "(1)": "?LHS = N[y::=L]" using c1 by simp |
|
102 have "(2)": "?RHS = N[y::=L]" using c1 a1 by simp |
|
103 have "?LHS = ?RHS" using "(1)" "(2)" by simp |
|
104 } |
|
105 moreover |
|
106 { -- {* Case 1.2 *} |
|
107 assume c2: "z = y" "z \<noteq> x" |
|
108 |
|
109 have "?LHS = ?RHS" sorry |
|
110 } |
|
111 moreover |
|
112 { -- {* Case 1.3 *} |
|
113 assume c3: "z \<noteq> x" "z \<noteq> y" |
|
114 |
|
115 have "?LHS = ?RHS" sorry |
|
116 } |
|
117 ultimately show "?LHS = ?RHS" by blast |
|
118 qed |
|
119 next |
|
120 case (Lam z M1) -- {* case 2: lambdas *} |
|
121 have ih: "\<lbrakk>x \<noteq> y; atom x \<sharp> L\<rbrakk> \<Longrightarrow> M1[x ::= N][y ::= L] = M1[y ::= L][x ::= N[y ::= L]]" by fact |
|
122 have a1: "x \<noteq> y" by fact |
|
123 have a2: "atom x \<sharp> L" by fact |
|
124 have fs: "atom z \<sharp> x" "atom z \<sharp> y" "atom z \<sharp> N" "atom z \<sharp> L" by fact+ -- {* !! *} |
|
125 then have b: "atom z \<sharp> N[y::=L]" by (simp add: fresh_fact) |
|
126 show "(Lam [z].M1)[x ::= N][y ::= L] = (Lam [z].M1)[y ::= L][x ::= N[y ::= L]]" (is "?LHS=?RHS") |
|
127 proof - |
|
128 have "?LHS = \<dots>" sorry |
|
129 |
|
130 also have "\<dots> = ?RHS" sorry |
|
131 finally show "?LHS = ?RHS" by simp |
|
132 qed |
|
133 next |
|
134 case (App M1 M2) -- {* case 3: applications *} |
|
135 then show "(App M1 M2)[x::=N][y::=L] = (App M1 M2)[y::=L][x::=N[y::=L]]" by simp |
|
136 qed |
|
137 |
|
138 text {* |
|
139 Again the strong induction principle enables Isabelle to find |
|
140 the proof of the substitution lemma completely automatically. |
|
141 *} |
|
142 |
|
143 lemma substitution_lemma_version: |
|
144 assumes asm: "x \<noteq> y" "atom x \<sharp> L" |
|
145 shows "M[x::=N][y::=L] = M[y::=L][x::=N[y::=L]]" |
|
146 using asm |
|
147 by (nominal_induct M avoiding: x y N L rule: lam.strong_induct) |
|
148 (auto simp add: fresh_fact forget) |
|
149 |
|
150 subsection {* MINI EXERCISE *} |
|
151 |
|
152 text {* |
|
153 Compare and contrast Barendregt's reasoning and the |
|
154 formalised proofs. |
|
155 *} |
|
156 |
|
157 end |
|