src/ZF/ex/Brouwer.ML

expanded tabs

(*  Title:      ZF/ex/Brouwer.ML
    ID:         $ $
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
    Copyright   1994  University of Cambridge

Infinite branching datatype definitions
  (1) the Brouwer ordinals
  (2) the Martin-Löf wellordering type
*)

open Brouwer;

(** The Brouwer ordinals **)

goal Brouwer.thy "brouwer = {0} + brouwer + (nat -> brouwer)";
let open brouwer;  val rew = rewrite_rule con_defs in  
by (fast_tac (sum_cs addSIs (equalityI :: map rew intrs)
                     addEs [rew elim]) 1)
end;
qed "brouwer_unfold";

(*A nicer induction rule than the standard one*)
val major::prems = goal Brouwer.thy
    "[| b: brouwer;                                     \
\       P(Zero);                                        \
\       !!b. [| b: brouwer;  P(b) |] ==> P(Suc(b));     \
\       !!h. [| h: nat -> brouwer;  ALL i:nat. P(h`i)   \
\            |] ==> P(Lim(h))                           \
\    |] ==> P(b)";
by (rtac (major RS brouwer.induct) 1);
by (REPEAT_SOME (ares_tac prems));
by (fast_tac (ZF_cs addEs [fun_weaken_type]) 1);
by (fast_tac (ZF_cs addDs [apply_type]) 1);
qed "brouwer_induct2";


(** The Martin-Löf wellordering type **)

goal Brouwer.thy "Well(A,B) = (SUM x:A. B(x) -> Well(A,B))";
let open Well;  val rew = rewrite_rule con_defs in  
by (fast_tac (sum_cs addSIs (equalityI :: map rew intrs)
                     addEs [rew elim]) 1)
end;
qed "Well_unfold";

(*A nicer induction rule than the standard one*)
val major::prems = goal Brouwer.thy
    "[| w: Well(A,B);                                                   \
\       !!a f. [| a: A;  f: B(a) -> Well(A,B);  ALL y: B(a). P(f`y)     \
\            |] ==> P(Sup(a,f))                                         \
\    |] ==> P(w)";
by (rtac (major RS Well.induct) 1);
by (REPEAT_SOME (ares_tac prems));
by (fast_tac (ZF_cs addEs [fun_weaken_type]) 1);
by (fast_tac (ZF_cs addDs [apply_type]) 1);
qed "Well_induct2";


(*In fact it's isomorphic to nat, but we need a recursion operator for
  Well to prove this.*)
goal Brouwer.thy "Well(bool, %x.x) = 1 + (1 -> Well(bool, %x.x))";
by (resolve_tac [Well_unfold RS trans] 1);
by (simp_tac (ZF_ss addsimps [Sigma_bool, Pi_empty1, succ_def]) 1);
qed "Well_bool_unfold";