src/HOL/WF_Rel.ML
changeset 5144 7ac22e5a05d7
parent 5143 b94cd208f073
child 6803 8273e5a17a43
equal deleted inserted replaced
5143:b94cd208f073 5144:7ac22e5a05d7
   105 by (Blast_tac 1);
   105 by (Blast_tac 1);
   106 qed "trans_finite_psubset";
   106 qed "trans_finite_psubset";
   107 
   107 
   108 (*---------------------------------------------------------------------------
   108 (*---------------------------------------------------------------------------
   109  * Wellfoundedness of finite acyclic relations
   109  * Wellfoundedness of finite acyclic relations
   110  * Cannot go into WF because it needs Finite
   110  * Cannot go into WF because it needs Finite.
   111  *---------------------------------------------------------------------------*)
   111  *---------------------------------------------------------------------------*)
   112 
   112 
   113 Goal "finite r ==> acyclic r --> wf r";
   113 Goal "finite r ==> acyclic r --> wf r";
   114 by (etac finite_induct 1);
   114 by (etac finite_induct 1);
   115  by (Blast_tac 1);
   115  by (Blast_tac 1);
   127 qed "wf_iff_acyclic_if_finite";
   127 qed "wf_iff_acyclic_if_finite";
   128 
   128 
   129 
   129 
   130 (*---------------------------------------------------------------------------
   130 (*---------------------------------------------------------------------------
   131  * A relation is wellfounded iff it has no infinite descending chain
   131  * A relation is wellfounded iff it has no infinite descending chain
       
   132  * Cannot go into WF because it needs type nat.
   132  *---------------------------------------------------------------------------*)
   133  *---------------------------------------------------------------------------*)
   133 
   134 
   134 Goalw [wf_eq_minimal RS eq_reflection]
   135 Goalw [wf_eq_minimal RS eq_reflection]
   135   "wf r = (~(? f. !i. (f(Suc i),f i) : r))";
   136   "wf r = (~(? f. !i. (f(Suc i),f i) : r))";
   136 by (rtac iffI 1);
   137 by (rtac iffI 1);