17453

1 
header {* Lambda Cube Examples *}


2 


3 
theory Example


4 
imports Cube


5 
begin


6 


7 
text {*


8 
Examples taken from:


9 


10 
H. Barendregt. Introduction to Generalised Type Systems.


11 
J. Functional Programming.


12 
*}


13 


14 
method_setup depth_solve = {*

30549

15 
Attrib.thms >> (fn thms => K (METHOD (fn facts =>

42814

16 
(DEPTH_SOLVE (HEADGOAL (ares_tac (facts @ thms)))))))


17 
*}

17453

18 


19 
method_setup depth_solve1 = {*

30549

20 
Attrib.thms >> (fn thms => K (METHOD (fn facts =>

42814

21 
(DEPTH_SOLVE_1 (HEADGOAL (ares_tac (facts @ thms)))))))


22 
*}

17453

23 


24 
method_setup strip_asms = {*

30549

25 
Attrib.thms >> (fn thms => K (METHOD (fn facts =>


26 
REPEAT (resolve_tac [@{thm strip_b}, @{thm strip_s}] 1 THEN


27 
DEPTH_SOLVE_1 (ares_tac (facts @ thms) 1)))))

42814

28 
*}

17453

29 


30 


31 
subsection {* Simple types *}


32 

45242

33 
schematic_lemma "A:* \<turnstile> A\<rightarrow>A : ?T"

17453

34 
by (depth_solve rules)


35 

45242

36 
schematic_lemma "A:* \<turnstile> \<Lambda> a:A. a : ?T"

17453

37 
by (depth_solve rules)


38 

45242

39 
schematic_lemma "A:* B:* b:B \<turnstile> \<Lambda> x:A. b : ?T"

17453

40 
by (depth_solve rules)


41 

45242

42 
schematic_lemma "A:* b:A \<turnstile> (\<Lambda> a:A. a)^b: ?T"

17453

43 
by (depth_solve rules)


44 

45242

45 
schematic_lemma "A:* B:* c:A b:B \<turnstile> (\<Lambda> x:A. b)^ c: ?T"

17453

46 
by (depth_solve rules)


47 

45242

48 
schematic_lemma "A:* B:* \<turnstile> \<Lambda> a:A. \<Lambda> b:B. a : ?T"

17453

49 
by (depth_solve rules)


50 


51 


52 
subsection {* Secondorder types *}


53 

45242

54 
schematic_lemma (in L2) "\<turnstile> \<Lambda> A:*. \<Lambda> a:A. a : ?T"

17453

55 
by (depth_solve rules)


56 

45242

57 
schematic_lemma (in L2) "A:* \<turnstile> (\<Lambda> B:*.\<Lambda> b:B. b)^A : ?T"

17453

58 
by (depth_solve rules)


59 

45242

60 
schematic_lemma (in L2) "A:* b:A \<turnstile> (\<Lambda> B:*.\<Lambda> b:B. b) ^ A ^ b: ?T"

17453

61 
by (depth_solve rules)


62 

45242

63 
schematic_lemma (in L2) "\<turnstile> \<Lambda> B:*.\<Lambda> a:(\<Pi> A:*.A).a ^ ((\<Pi> A:*.A)\<rightarrow>B) ^ a: ?T"

17453

64 
by (depth_solve rules)


65 


66 


67 
subsection {* Weakly higherorder propositional logic *}


68 

45242

69 
schematic_lemma (in Lomega) "\<turnstile> \<Lambda> A:*.A\<rightarrow>A : ?T"

17453

70 
by (depth_solve rules)


71 

45242

72 
schematic_lemma (in Lomega) "B:* \<turnstile> (\<Lambda> A:*.A\<rightarrow>A) ^ B : ?T"

17453

73 
by (depth_solve rules)


74 

45242

75 
schematic_lemma (in Lomega) "B:* b:B \<turnstile> (\<Lambda> y:B. b): ?T"

17453

76 
by (depth_solve rules)


77 

45242

78 
schematic_lemma (in Lomega) "A:* F:*\<rightarrow>* \<turnstile> F^(F^A): ?T"

17453

79 
by (depth_solve rules)


80 

45242

81 
schematic_lemma (in Lomega) "A:* \<turnstile> \<Lambda> F:*\<rightarrow>*.F^(F^A): ?T"

17453

82 
by (depth_solve rules)


83 


84 


85 
subsection {* LP *}


86 

45242

87 
schematic_lemma (in LP) "A:* \<turnstile> A \<rightarrow> * : ?T"

17453

88 
by (depth_solve rules)


89 

45242

90 
schematic_lemma (in LP) "A:* P:A\<rightarrow>* a:A \<turnstile> P^a: ?T"

17453

91 
by (depth_solve rules)


92 

45242

93 
schematic_lemma (in LP) "A:* P:A\<rightarrow>A\<rightarrow>* a:A \<turnstile> \<Pi> a:A. P^a^a: ?T"

17453

94 
by (depth_solve rules)


95 

45242

96 
schematic_lemma (in LP) "A:* P:A\<rightarrow>* Q:A\<rightarrow>* \<turnstile> \<Pi> a:A. P^a \<rightarrow> Q^a: ?T"

17453

97 
by (depth_solve rules)


98 

45242

99 
schematic_lemma (in LP) "A:* P:A\<rightarrow>* \<turnstile> \<Pi> a:A. P^a \<rightarrow> P^a: ?T"

17453

100 
by (depth_solve rules)


101 

45242

102 
schematic_lemma (in LP) "A:* P:A\<rightarrow>* \<turnstile> \<Lambda> a:A. \<Lambda> x:P^a. x: ?T"

17453

103 
by (depth_solve rules)


104 

45242

105 
schematic_lemma (in LP) "A:* P:A\<rightarrow>* Q:* \<turnstile> (\<Pi> a:A. P^a\<rightarrow>Q) \<rightarrow> (\<Pi> a:A. P^a) \<rightarrow> Q : ?T"

17453

106 
by (depth_solve rules)


107 

45242

108 
schematic_lemma (in LP) "A:* P:A\<rightarrow>* Q:* a0:A \<turnstile>


109 
\<Lambda> x:\<Pi> a:A. P^a\<rightarrow>Q. \<Lambda> y:\<Pi> a:A. P^a. x^a0^(y^a0): ?T"

17453

110 
by (depth_solve rules)


111 


112 


113 
subsection {* Omegaorder types *}


114 

45242

115 
schematic_lemma (in L2) "A:* B:* \<turnstile> \<Pi> C:*.(A\<rightarrow>B\<rightarrow>C)\<rightarrow>C : ?T"

17453

116 
by (depth_solve rules)


117 

45242

118 
schematic_lemma (in Lomega2) "\<turnstile> \<Lambda> A:*.\<Lambda> B:*.\<Pi> C:*.(A\<rightarrow>B\<rightarrow>C)\<rightarrow>C : ?T"

17453

119 
by (depth_solve rules)


120 

45242

121 
schematic_lemma (in Lomega2) "\<turnstile> \<Lambda> A:*.\<Lambda> B:*.\<Lambda> x:A. \<Lambda> y:B. x : ?T"

17453

122 
by (depth_solve rules)


123 

45242

124 
schematic_lemma (in Lomega2) "A:* B:* \<turnstile> ?p : (A\<rightarrow>B) \<rightarrow> ((B\<rightarrow>\<Pi> P:*.P)\<rightarrow>(A\<rightarrow>\<Pi> P:*.P))"

17453

125 
apply (strip_asms rules)


126 
apply (rule lam_ss)


127 
apply (depth_solve1 rules)


128 
prefer 2


129 
apply (depth_solve1 rules)


130 
apply (rule lam_ss)


131 
apply (depth_solve1 rules)


132 
prefer 2


133 
apply (depth_solve1 rules)


134 
apply (rule lam_ss)


135 
apply assumption


136 
prefer 2


137 
apply (depth_solve1 rules)


138 
apply (erule pi_elim)


139 
apply assumption


140 
apply (erule pi_elim)


141 
apply assumption


142 
apply assumption


143 
done


144 


145 


146 
subsection {* Secondorder Predicate Logic *}


147 

45242

148 
schematic_lemma (in LP2) "A:* P:A\<rightarrow>* \<turnstile> \<Lambda> a:A. P^a\<rightarrow>(\<Pi> A:*.A) : ?T"

17453

149 
by (depth_solve rules)


150 

45242

151 
schematic_lemma (in LP2) "A:* P:A\<rightarrow>A\<rightarrow>* \<turnstile>


152 
(\<Pi> a:A. \<Pi> b:A. P^a^b\<rightarrow>P^b^a\<rightarrow>\<Pi> P:*.P) \<rightarrow> \<Pi> a:A. P^a^a\<rightarrow>\<Pi> P:*.P : ?T"

17453

153 
by (depth_solve rules)


154 

45242

155 
schematic_lemma (in LP2) "A:* P:A\<rightarrow>A\<rightarrow>* \<turnstile>


156 
?p: (\<Pi> a:A. \<Pi> b:A. P^a^b\<rightarrow>P^b^a\<rightarrow>\<Pi> P:*.P) \<rightarrow> \<Pi> a:A. P^a^a\<rightarrow>\<Pi> P:*.P"

17453

157 
 {* Antisymmetry implies irreflexivity: *}


158 
apply (strip_asms rules)


159 
apply (rule lam_ss)


160 
apply (depth_solve1 rules)


161 
prefer 2


162 
apply (depth_solve1 rules)


163 
apply (rule lam_ss)


164 
apply assumption


165 
prefer 2


166 
apply (depth_solve1 rules)


167 
apply (rule lam_ss)


168 
apply (depth_solve1 rules)


169 
prefer 2


170 
apply (depth_solve1 rules)


171 
apply (erule pi_elim, assumption, assumption?)+


172 
done


173 


174 


175 
subsection {* LPomega *}


176 

45242

177 
schematic_lemma (in LPomega) "A:* \<turnstile> \<Lambda> P:A\<rightarrow>A\<rightarrow>*.\<Lambda> a:A. P^a^a : ?T"

17453

178 
by (depth_solve rules)


179 

45242

180 
schematic_lemma (in LPomega) "\<turnstile> \<Lambda> A:*.\<Lambda> P:A\<rightarrow>A\<rightarrow>*.\<Lambda> a:A. P^a^a : ?T"

17453

181 
by (depth_solve rules)


182 


183 


184 
subsection {* Constructions *}


185 

45242

186 
schematic_lemma (in CC) "\<turnstile> \<Lambda> A:*.\<Lambda> P:A\<rightarrow>*.\<Lambda> a:A. P^a\<rightarrow>\<Pi> P:*.P: ?T"

17453

187 
by (depth_solve rules)


188 

45242

189 
schematic_lemma (in CC) "\<turnstile> \<Lambda> A:*.\<Lambda> P:A\<rightarrow>*.\<Pi> a:A. P^a: ?T"

17453

190 
by (depth_solve rules)


191 

45242

192 
schematic_lemma (in CC) "A:* P:A\<rightarrow>* a:A \<turnstile> ?p : (\<Pi> a:A. P^a)\<rightarrow>P^a"

17453

193 
apply (strip_asms rules)


194 
apply (rule lam_ss)


195 
apply (depth_solve1 rules)


196 
prefer 2


197 
apply (depth_solve1 rules)


198 
apply (erule pi_elim, assumption, assumption)


199 
done


200 


201 


202 
subsection {* Some random examples *}


203 

45242

204 
schematic_lemma (in LP2) "A:* c:A f:A\<rightarrow>A \<turnstile>


205 
\<Lambda> a:A. \<Pi> P:A\<rightarrow>*.P^c \<rightarrow> (\<Pi> x:A. P^x\<rightarrow>P^(f^x)) \<rightarrow> P^a : ?T"

17453

206 
by (depth_solve rules)


207 

45242

208 
schematic_lemma (in CC) "\<Lambda> A:*.\<Lambda> c:A. \<Lambda> f:A\<rightarrow>A.


209 
\<Lambda> a:A. \<Pi> P:A\<rightarrow>*.P^c \<rightarrow> (\<Pi> x:A. P^x\<rightarrow>P^(f^x)) \<rightarrow> P^a : ?T"

17453

210 
by (depth_solve rules)


211 

36319

212 
schematic_lemma (in LP2)

45242

213 
"A:* a:A b:A \<turnstile> ?p: (\<Pi> P:A\<rightarrow>*.P^a\<rightarrow>P^b) \<rightarrow> (\<Pi> P:A\<rightarrow>*.P^b\<rightarrow>P^a)"

17453

214 
 {* Symmetry of Leibnitz equality *}


215 
apply (strip_asms rules)


216 
apply (rule lam_ss)


217 
apply (depth_solve1 rules)


218 
prefer 2


219 
apply (depth_solve1 rules)

45242

220 
apply (erule_tac a = "\<Lambda> x:A. \<Pi> Q:A\<rightarrow>*.Q^x\<rightarrow>Q^a" in pi_elim)

17453

221 
apply (depth_solve1 rules)


222 
apply (unfold beta)


223 
apply (erule imp_elim)


224 
apply (rule lam_bs)


225 
apply (depth_solve1 rules)


226 
prefer 2


227 
apply (depth_solve1 rules)


228 
apply (rule lam_ss)


229 
apply (depth_solve1 rules)


230 
prefer 2


231 
apply (depth_solve1 rules)


232 
apply assumption


233 
apply assumption


234 
done


235 


236 
end
