author wenzelm Thu, 28 Feb 2013 14:10:54 +0100 changeset 51308 51e158e988a5 parent 51307 943ad9c0d99d child 51309 473303ef6e34
eliminated legacy 'axioms';
 src/CTT/CTT.thy file | annotate | diff | comparison | revisions
```--- a/src/CTT/CTT.thy	Thu Feb 28 13:54:45 2013 +0100
+++ b/src/CTT/CTT.thy	Thu Feb 28 14:10:54 2013 +0100
@@ -93,175 +93,174 @@
"_PROD"   :: "[idt,t,t] => t"     ("(3\<Pi> _\<in>_./ _)"    10)
"_SUM"    :: "[idt,t,t] => t"     ("(3\<Sigma> _\<in>_./ _)" 10)

-axioms
-
(*Reduction: a weaker notion than equality;  a hack for simplification.
Reduce[a,b] means either that  a=b:A  for some A or else that "a" and "b"
are textually identical.*)

(*does not verify a:A!  Sound because only trans_red uses a Reduce premise
No new theorems can be proved about the standard judgements.*)
-  refl_red: "Reduce[a,a]"
-  red_if_equal: "a = b : A ==> Reduce[a,b]"
-  trans_red: "[| a = b : A;  Reduce[b,c] |] ==> a = c : A"
+axiomatization where
+  refl_red: "\<And>a. Reduce[a,a]" and
+  red_if_equal: "\<And>a b A. a = b : A ==> Reduce[a,b]" and
+  trans_red: "\<And>a b c A. [| a = b : A;  Reduce[b,c] |] ==> a = c : A" and

(*Reflexivity*)

-  refl_type: "A type ==> A = A"
-  refl_elem: "a : A ==> a = a : A"
+  refl_type: "\<And>A. A type ==> A = A" and
+  refl_elem: "\<And>a A. a : A ==> a = a : A" and

(*Symmetry*)

-  sym_type:  "A = B ==> B = A"
-  sym_elem:  "a = b : A ==> b = a : A"
+  sym_type:  "\<And>A B. A = B ==> B = A" and
+  sym_elem:  "\<And>a b A. a = b : A ==> b = a : A" and

(*Transitivity*)

-  trans_type:   "[| A = B;  B = C |] ==> A = C"
-  trans_elem:   "[| a = b : A;  b = c : A |] ==> a = c : A"
+  trans_type:   "\<And>A B C. [| A = B;  B = C |] ==> A = C" and
+  trans_elem:   "\<And>a b c A. [| a = b : A;  b = c : A |] ==> a = c : A" and

-  equal_types:  "[| a : A;  A = B |] ==> a : B"
-  equal_typesL: "[| a = b : A;  A = B |] ==> a = b : B"
+  equal_types:  "\<And>a A B. [| a : A;  A = B |] ==> a : B" and
+  equal_typesL: "\<And>a b A B. [| a = b : A;  A = B |] ==> a = b : B" and

(*Substitution*)

-  subst_type:   "[| a : A;  !!z. z:A ==> B(z) type |] ==> B(a) type"
-  subst_typeL:  "[| a = c : A;  !!z. z:A ==> B(z) = D(z) |] ==> B(a) = D(c)"
+  subst_type:   "\<And>a A B. [| a : A;  !!z. z:A ==> B(z) type |] ==> B(a) type" and
+  subst_typeL:  "\<And>a c A B D. [| a = c : A;  !!z. z:A ==> B(z) = D(z) |] ==> B(a) = D(c)" and

-  subst_elem:   "[| a : A;  !!z. z:A ==> b(z):B(z) |] ==> b(a):B(a)"
+  subst_elem:   "\<And>a b A B. [| a : A;  !!z. z:A ==> b(z):B(z) |] ==> b(a):B(a)" and
subst_elemL:
-    "[| a=c : A;  !!z. z:A ==> b(z)=d(z) : B(z) |] ==> b(a)=d(c) : B(a)"
+    "\<And>a b c d A B. [| a=c : A;  !!z. z:A ==> b(z)=d(z) : B(z) |] ==> b(a)=d(c) : B(a)" and

(*The type N -- natural numbers*)

-  NF: "N type"
-  NI0: "0 : N"
-  NI_succ: "a : N ==> succ(a) : N"
-  NI_succL:  "a = b : N ==> succ(a) = succ(b) : N"
+  NF: "N type" and
+  NI0: "0 : N" and
+  NI_succ: "\<And>a. a : N ==> succ(a) : N" and
+  NI_succL:  "\<And>a b. a = b : N ==> succ(a) = succ(b) : N" and

NE:
-   "[| p: N;  a: C(0);  !!u v. [| u: N; v: C(u) |] ==> b(u,v): C(succ(u)) |]
-   ==> rec(p, a, %u v. b(u,v)) : C(p)"
+   "\<And>p a b C. [| p: N;  a: C(0);  !!u v. [| u: N; v: C(u) |] ==> b(u,v): C(succ(u)) |]
+   ==> rec(p, a, %u v. b(u,v)) : C(p)" and

NEL:
-   "[| p = q : N;  a = c : C(0);
+   "\<And>p q a b c d C. [| p = q : N;  a = c : C(0);
!!u v. [| u: N; v: C(u) |] ==> b(u,v) = d(u,v): C(succ(u)) |]
-   ==> rec(p, a, %u v. b(u,v)) = rec(q,c,d) : C(p)"
+   ==> rec(p, a, %u v. b(u,v)) = rec(q,c,d) : C(p)" and

NC0:
-   "[| a: C(0);  !!u v. [| u: N; v: C(u) |] ==> b(u,v): C(succ(u)) |]
-   ==> rec(0, a, %u v. b(u,v)) = a : C(0)"
+   "\<And>a b C. [| a: C(0);  !!u v. [| u: N; v: C(u) |] ==> b(u,v): C(succ(u)) |]
+   ==> rec(0, a, %u v. b(u,v)) = a : C(0)" and

NC_succ:
-   "[| p: N;  a: C(0);
+   "\<And>p a b C. [| p: N;  a: C(0);
!!u v. [| u: N; v: C(u) |] ==> b(u,v): C(succ(u)) |] ==>
-   rec(succ(p), a, %u v. b(u,v)) = b(p, rec(p, a, %u v. b(u,v))) : C(succ(p))"
+   rec(succ(p), a, %u v. b(u,v)) = b(p, rec(p, a, %u v. b(u,v))) : C(succ(p))" and

(*The fourth Peano axiom.  See page 91 of Martin-Lof's book*)
zero_ne_succ:
-    "[| a: N;  0 = succ(a) : N |] ==> 0: F"
+    "\<And>a. [| a: N;  0 = succ(a) : N |] ==> 0: F" and

(*The Product of a family of types*)

-  ProdF:  "[| A type; !!x. x:A ==> B(x) type |] ==> PROD x:A. B(x) type"
+  ProdF:  "\<And>A B. [| A type; !!x. x:A ==> B(x) type |] ==> PROD x:A. B(x) type" and

ProdFL:
-   "[| A = C;  !!x. x:A ==> B(x) = D(x) |] ==>
-   PROD x:A. B(x) = PROD x:C. D(x)"
+   "\<And>A B C D. [| A = C;  !!x. x:A ==> B(x) = D(x) |] ==>
+   PROD x:A. B(x) = PROD x:C. D(x)" and

ProdI:
-   "[| A type;  !!x. x:A ==> b(x):B(x)|] ==> lam x. b(x) : PROD x:A. B(x)"
+   "\<And>b A B. [| A type;  !!x. x:A ==> b(x):B(x)|] ==> lam x. b(x) : PROD x:A. B(x)" and

ProdIL:
-   "[| A type;  !!x. x:A ==> b(x) = c(x) : B(x)|] ==>
-   lam x. b(x) = lam x. c(x) : PROD x:A. B(x)"
+   "\<And>b c A B. [| A type;  !!x. x:A ==> b(x) = c(x) : B(x)|] ==>
+   lam x. b(x) = lam x. c(x) : PROD x:A. B(x)" and

-  ProdE:  "[| p : PROD x:A. B(x);  a : A |] ==> p`a : B(a)"
-  ProdEL: "[| p=q: PROD x:A. B(x);  a=b : A |] ==> p`a = q`b : B(a)"
+  ProdE:  "\<And>p a A B. [| p : PROD x:A. B(x);  a : A |] ==> p`a : B(a)" and
+  ProdEL: "\<And>p q a b A B. [| p=q: PROD x:A. B(x);  a=b : A |] ==> p`a = q`b : B(a)" and

ProdC:
-   "[| a : A;  !!x. x:A ==> b(x) : B(x)|] ==>
-   (lam x. b(x)) ` a = b(a) : B(a)"
+   "\<And>a b A B. [| a : A;  !!x. x:A ==> b(x) : B(x)|] ==>
+   (lam x. b(x)) ` a = b(a) : B(a)" and

ProdC2:
-   "p : PROD x:A. B(x) ==> (lam x. p`x) = p : PROD x:A. B(x)"
+   "\<And>p A B. p : PROD x:A. B(x) ==> (lam x. p`x) = p : PROD x:A. B(x)" and

(*The Sum of a family of types*)

-  SumF:  "[| A type;  !!x. x:A ==> B(x) type |] ==> SUM x:A. B(x) type"
+  SumF:  "\<And>A B. [| A type;  !!x. x:A ==> B(x) type |] ==> SUM x:A. B(x) type" and
SumFL:
-    "[| A = C;  !!x. x:A ==> B(x) = D(x) |] ==> SUM x:A. B(x) = SUM x:C. D(x)"
+    "\<And>A B C D. [| A = C;  !!x. x:A ==> B(x) = D(x) |] ==> SUM x:A. B(x) = SUM x:C. D(x)" and

-  SumI:  "[| a : A;  b : B(a) |] ==> <a,b> : SUM x:A. B(x)"
-  SumIL: "[| a=c:A;  b=d:B(a) |] ==> <a,b> = <c,d> : SUM x:A. B(x)"
+  SumI:  "\<And>a b A B. [| a : A;  b : B(a) |] ==> <a,b> : SUM x:A. B(x)" and
+  SumIL: "\<And>a b c d A B. [| a=c:A;  b=d:B(a) |] ==> <a,b> = <c,d> : SUM x:A. B(x)" and

SumE:
-    "[| p: SUM x:A. B(x);  !!x y. [| x:A; y:B(x) |] ==> c(x,y): C(<x,y>) |]
-    ==> split(p, %x y. c(x,y)) : C(p)"
+    "\<And>p c A B C. [| p: SUM x:A. B(x);  !!x y. [| x:A; y:B(x) |] ==> c(x,y): C(<x,y>) |]
+    ==> split(p, %x y. c(x,y)) : C(p)" and

SumEL:
-    "[| p=q : SUM x:A. B(x);
+    "\<And>p q c d A B C. [| p=q : SUM x:A. B(x);
!!x y. [| x:A; y:B(x) |] ==> c(x,y)=d(x,y): C(<x,y>)|]
-    ==> split(p, %x y. c(x,y)) = split(q, % x y. d(x,y)) : C(p)"
+    ==> split(p, %x y. c(x,y)) = split(q, % x y. d(x,y)) : C(p)" and

SumC:
-    "[| a: A;  b: B(a);  !!x y. [| x:A; y:B(x) |] ==> c(x,y): C(<x,y>) |]
-    ==> split(<a,b>, %x y. c(x,y)) = c(a,b) : C(<a,b>)"
+    "\<And>a b c A B C. [| a: A;  b: B(a);  !!x y. [| x:A; y:B(x) |] ==> c(x,y): C(<x,y>) |]
+    ==> split(<a,b>, %x y. c(x,y)) = c(a,b) : C(<a,b>)" and

-  fst_def:   "fst(a) == split(a, %x y. x)"
-  snd_def:   "snd(a) == split(a, %x y. y)"
+  fst_def:   "\<And>a. fst(a) == split(a, %x y. x)" and
+  snd_def:   "\<And>a. snd(a) == split(a, %x y. y)" and

(*The sum of two types*)

-  PlusF:   "[| A type;  B type |] ==> A+B type"
-  PlusFL:  "[| A = C;  B = D |] ==> A+B = C+D"
+  PlusF:   "\<And>A B. [| A type;  B type |] ==> A+B type" and
+  PlusFL:  "\<And>A B C D. [| A = C;  B = D |] ==> A+B = C+D" and

-  PlusI_inl:   "[| a : A;  B type |] ==> inl(a) : A+B"
-  PlusI_inlL: "[| a = c : A;  B type |] ==> inl(a) = inl(c) : A+B"
+  PlusI_inl:   "\<And>a A B. [| a : A;  B type |] ==> inl(a) : A+B" and
+  PlusI_inlL: "\<And>a c A B. [| a = c : A;  B type |] ==> inl(a) = inl(c) : A+B" and

-  PlusI_inr:   "[| A type;  b : B |] ==> inr(b) : A+B"
-  PlusI_inrL: "[| A type;  b = d : B |] ==> inr(b) = inr(d) : A+B"
+  PlusI_inr:   "\<And>b A B. [| A type;  b : B |] ==> inr(b) : A+B" and
+  PlusI_inrL: "\<And>b d A B. [| A type;  b = d : B |] ==> inr(b) = inr(d) : A+B" and

PlusE:
-    "[| p: A+B;  !!x. x:A ==> c(x): C(inl(x));
+    "\<And>p c d A B C. [| p: A+B;  !!x. x:A ==> c(x): C(inl(x));
!!y. y:B ==> d(y): C(inr(y)) |]
-    ==> when(p, %x. c(x), %y. d(y)) : C(p)"
+    ==> when(p, %x. c(x), %y. d(y)) : C(p)" and

PlusEL:
-    "[| p = q : A+B;  !!x. x: A ==> c(x) = e(x) : C(inl(x));
+    "\<And>p q c d e f A B C. [| p = q : A+B;  !!x. x: A ==> c(x) = e(x) : C(inl(x));
!!y. y: B ==> d(y) = f(y) : C(inr(y)) |]
-    ==> when(p, %x. c(x), %y. d(y)) = when(q, %x. e(x), %y. f(y)) : C(p)"
+    ==> when(p, %x. c(x), %y. d(y)) = when(q, %x. e(x), %y. f(y)) : C(p)" and

PlusC_inl:
-    "[| a: A;  !!x. x:A ==> c(x): C(inl(x));
+    "\<And>a c d A C. [| a: A;  !!x. x:A ==> c(x): C(inl(x));
!!y. y:B ==> d(y): C(inr(y)) |]
-    ==> when(inl(a), %x. c(x), %y. d(y)) = c(a) : C(inl(a))"
+    ==> when(inl(a), %x. c(x), %y. d(y)) = c(a) : C(inl(a))" and

PlusC_inr:
-    "[| b: B;  !!x. x:A ==> c(x): C(inl(x));
+    "\<And>b c d A B C. [| b: B;  !!x. x:A ==> c(x): C(inl(x));
!!y. y:B ==> d(y): C(inr(y)) |]
-    ==> when(inr(b), %x. c(x), %y. d(y)) = d(b) : C(inr(b))"
+    ==> when(inr(b), %x. c(x), %y. d(y)) = d(b) : C(inr(b))" and

(*The type Eq*)

-  EqF:    "[| A type;  a : A;  b : A |] ==> Eq(A,a,b) type"
-  EqFL: "[| A=B;  a=c: A;  b=d : A |] ==> Eq(A,a,b) = Eq(B,c,d)"
-  EqI: "a = b : A ==> eq : Eq(A,a,b)"
-  EqE: "p : Eq(A,a,b) ==> a = b : A"
+  EqF:    "\<And>a b A. [| A type;  a : A;  b : A |] ==> Eq(A,a,b) type" and
+  EqFL: "\<And>a b c d A B. [| A=B;  a=c: A;  b=d : A |] ==> Eq(A,a,b) = Eq(B,c,d)" and
+  EqI: "\<And>a b A. a = b : A ==> eq : Eq(A,a,b)" and
+  EqE: "\<And>p a b A. p : Eq(A,a,b) ==> a = b : A" and

(*By equality of types, can prove C(p) from C(eq), an elimination rule*)
-  EqC: "p : Eq(A,a,b) ==> p = eq : Eq(A,a,b)"
+  EqC: "\<And>p a b A. p : Eq(A,a,b) ==> p = eq : Eq(A,a,b)" and

(*The type F*)

-  FF: "F type"
-  FE: "[| p: F;  C type |] ==> contr(p) : C"
-  FEL:  "[| p = q : F;  C type |] ==> contr(p) = contr(q) : C"
+  FF: "F type" and
+  FE: "\<And>p C. [| p: F;  C type |] ==> contr(p) : C" and
+  FEL:  "\<And>p q C. [| p = q : F;  C type |] ==> contr(p) = contr(q) : C" and

(*The type T
Martin-Lof's book (page 68) discusses elimination and computation.
@@ -269,11 +268,11 @@
but with an extra premise C(x) type x:T.
Also computation can be derived from elimination. *)

-  TF: "T type"
-  TI: "tt : T"
-  TE: "[| p : T;  c : C(tt) |] ==> c : C(p)"
-  TEL: "[| p = q : T;  c = d : C(tt) |] ==> c = d : C(p)"
-  TC: "p : T ==> p = tt : T"
+  TF: "T type" and
+  TI: "tt : T" and
+  TE: "\<And>p c C. [| p : T;  c : C(tt) |] ==> c : C(p)" and
+  TEL: "\<And>p q c d C. [| p = q : T;  c = d : C(tt) |] ==> c = d : C(p)" and
+  TC: "\<And>p. p : T ==> p = tt : T"

subsection "Tactics and derived rules for Constructive Type Theory"```