Debian Codegraph @

examples/tait/diplomarbeit_schlenker/proofAxiomsGlobal_SHORT.scm

raw
1 ; ***********************************************************
2 ; ; Adapt path if necessary:
3 ; (define path "~/minlog/examples/tait/diplomarbeit_schlenker/")
4
5 ; ; Defines the function "pload" to load files
6 ; ; from the path defined above
7 ; (define pload (lambda (x) (load (string-append path x))))
8
9 ; ; Used Modules:
10 ; (pload "./initiate.scm")
11 ; (pload "./defsLamCalc.scm")
12 ; (pload "./defsSubst.scm")
13 ; (pload "./subst_Joachimski_SHORT.scm")
14 ; (pload "./omega.scm")
15 ; (pload "./defsNT.scm")
16 ; (pload "./defsAxiomsSpecial.scm")
17 ; (pload "./trivial.scm")
18 ; (pload "./auxGlobal_SHORT.scm")
19 ; (pload "./defsPred.scm")
20 ; (pload "./proofAxiomsGlobal.scm")
21 ;
22 ; NOTICE: Uncomment modules only when file is run on its own
23 ; ***********************************************************
24
25 ; =======================================
26 ; Section: Global Proofs for the Axioms
27 ; =======================================
28 ; contains global lemmas and definitions for
29 ; the proofs of the axioms
30
31 ; Subsection: "Miscellaneous"
32 ; ==========================
33
34 ; Definition: "Typs"
35 ; ------------------
36 (add-program-constant "Typs"
37 (py "list type => list term => list type") 1)
38
39 (add-computation-rule (pt "Typs rhos (Nil term)")
40 (pt "(Nil type)"))
41 (add-computation-rule (pt "Typs rhos (r::rs)")
42 (pt "(Typ rhos r)::(Typs rhos rs)"))
43
44 ; Lemma: "CorTypJ"
45 ; ---------------
46 (set-goal
47 (pf "all rhos, r.Cor rhos r -> TypJ rhos r (Typ rhos r)"))
48
49 (assume "rhos" "r" 1)
50 (ng)
51 (use 1)
52 (save "CorTypJ")
53
54 ; Lemma: "TypJFoldHead"
55 ; ---------------------
56 (add-global-assumption "TypJFoldHead"
57 (pf "all rhos,rho,r,s,rs.
58 TypJ rhos (FoldApp r rs) rho ->
59 TypJ rhos s (Typ rhos r) ->
60 TypJ rhos (FoldApp s rs) rho"))
61
62 ; Lemma: "TypJFoldHeadCor"
63 ; ------------------------
64 (add-global-assumption "TypJFoldHeadCor"
65 (pf "all rhos,rho,sig,r,s,rs.
66 TypJ rhos (FoldApp (Abs rho r s) rs) sig ->
67 Cor rhos (Abs rho r s)"))
68
69
70 ; Subsection: "SR"
71 ; ================
72 ; "SR" stands for "Subject Reduction";
73 ; needed for Ax8, BNTypJ and Ax1
74
75 ; Subsubsection: Auxiliaries for "SR"
76 ; :::::::::::::::::::::::::::::::::::
77 ; ...
78 ; Subsubsection: Proof of "SR"
79 ; ::::::::::::::::::::::::::::
80
81 ; Lemma: "SR"
82 ; -----------
83 (add-global-assumption "SR"
84 (pf "all rhos,rho,sig,r,s.
85 TypJ rhos ((Abs sig r) s) rho ->
86 TypJ rhos (Sub r (Wrap 0 (s:))) rho"))
87
88
89 ; Subsection: "ExpTypJ"
90 ; =====================
91
92 ; Subsubsection: Auxiliaries for "ExpTypJ"
93 ; ::::::::::::::::::::::::::::::::::::::::
94
95 ; Definition: "OR"
96 ; ----------------
97 (add-program-constant "OR"
98 (py "boole => boole => boole") 1)
99
100 (add-computation-rule (pt "OR F F ")
101 (pt "F"))
102 (add-computation-rule (pt "OR T F ")
103 (pt "T"))
104 (add-computation-rule (pt "OR F T ")
105 (pt "T"))
106 (add-computation-rule (pt "OR T T ")
107 (pt "T"))
108
109 ; Definition: "Occurs"
110 ; --------------------
111 (add-program-constant "Occurs"
112 (py "nat => term => boole") 1)
113
114 (add-computation-rule (pt "Occurs 0 (Var 0) ")
115 (pt "T"))
116 (add-computation-rule (pt "Occurs 0 (Var (Succ n)) ")
117 (pt "F"))
118 (add-computation-rule (pt "Occurs (Succ n) (Var 0) ")
119 (pt "F"))
120 (add-computation-rule (pt "Occurs n (r s) ")
121 (pt "OR (Occurs n r) (Occurs n s)"))
122 (add-computation-rule (pt "Occurs n (Abs rho s) ")
123 (pt "Occurs (Succ n) s"))
124
125 ; Definition: "Occurss"
126 ; ---------------------
127 (add-program-constant "Occurss"
128 (py "nat => list term => boole") 1)
129
130 (add-computation-rule (pt "Occurss n (Nil term)")
131 (pt "F"))
132 (add-computation-rule (pt "Occurss n (r::rs)")
133 (pt "OR (Occurs n r) (Occurss n rs)"))
134
135 ; Subsubsection: Proof of "ExpTypJ"
136 ; :::::::::::::::::::::::::::::::::
137 ; contains "ExpTypJLeft" "ExpTypJRight" and
138 ; "ExpTypJ"
139
140 ; Lemma: "ExpTypJLeft"
141 ; --------------------
142 (add-global-assumption "ExpTypJLeft"
143 (pf "all rhos,rho,r,s.
144 Exp rhos rho r s ->
145 TypJ rhos r rho"))
146
147 ; Lemma: "ExpTypJRight"
148 ; --------------------
149 (add-global-assumption "ExpTypJRight"
150 (pf "all rhos,rho,r,s.
151 Exp rhos rho r s ->
152 TypJ rhos s rho"))
153
154 ; Lemma: "ExpTypJ"
155 ; ----------------
156 (add-global-assumption "ExpTypJ"
157 (pf "all rhos,rho,r,s.
158 Exp rhos rho r s ->
159 TypJ rhos r rho & TypJ rhos s rho"))
160
161
162 ; Subsection: "BNTypJ"
163 ; ====================
164
165 ; Subsubsection: Auxiliaries for "BNTypJ"
166 ; :::::::::::::::::::::::::::::::::::::::
167
168 ; Subsubsection: Proof of "BNTypJ"
169 ; ::::::::::::::::::::::::::::::::
170
171 ; Lemma: "BNTypJ"
172 ; ---------------
173 (add-global-assumption "BNTypJ"
174 (pf "all r,s.
175 BN r s ->
176 all rhos,rho.TypJ rhos r rho ->
177 TypJ rhos s rho"))
178
179
180 ; Subsection: "NTypJ"
181 ; ===================
182 ; not used explicitly, but for "N" to be
183 ; a proper definition the formula
184 ; "TypJ rhos r rho -> N rhos rho r s -> TypJ rhos s rho"
185 ; is implicitly required.
186 ;
187 ; Our Definition of "N" has the property
188 ; that the type judgements follow directly from "N".
189 ; Hence N rhos rho r s means exactly that
190 ; "s" is the long Normalform of "r"
191 ; in the given context with the given type
192
193 ; Lemma: "NIndTypJ"
194 ; -----------------
195 (add-global-assumption "NIndTypJ"
196 (pf "all rhos,rho,r,s.
197 TypJ rhos r rho ->
198 NInd rhos rho r s ->
199 TypJ rhos s rho"))