diff -r cf7f3465eaf1 -r 240563fbf41d src/ZF/Ordinal.thy --- a/src/ZF/Ordinal.thy Thu Jul 23 14:20:51 2015 +0200 +++ b/src/ZF/Ordinal.thy Thu Jul 23 14:25:05 2015 +0200 @@ -3,7 +3,7 @@ Copyright 1994 University of Cambridge *) -section{*Transitive Sets and Ordinals*} +section\Transitive Sets and Ordinals\ theory Ordinal imports WF Bool equalities begin @@ -38,9 +38,9 @@ le (infixl "\" 50) -subsection{*Rules for Transset*} +subsection\Rules for Transset\ -subsubsection{*Three Neat Characterisations of Transset*} +subsubsection\Three Neat Characterisations of Transset\ lemma Transset_iff_Pow: "Transset(A) <-> A<=Pow(A)" by (unfold Transset_def, blast) @@ -53,7 +53,7 @@ lemma Transset_iff_Union_subset: "Transset(A) <-> \(A) \ A" by (unfold Transset_def, blast) -subsubsection{*Consequences of Downwards Closure*} +subsubsection\Consequences of Downwards Closure\ lemma Transset_doubleton_D: "[| Transset(C); {a,b}: C |] ==> a\C & b\C" @@ -73,7 +73,7 @@ "[| Transset(C); A*B \ C; a \ A |] ==> B \ C" by (blast dest: Transset_Pair_D) -subsubsection{*Closure Properties*} +subsubsection\Closure Properties\ lemma Transset_0: "Transset(0)" by (unfold Transset_def, blast) @@ -112,7 +112,7 @@ by (rule Transset_Inter_family, auto) -subsection{*Lemmas for Ordinals*} +subsection\Lemmas for Ordinals\ lemma OrdI: "[| Transset(i); !!x. x\i ==> Transset(x) |] ==> Ord(i)" @@ -149,7 +149,7 @@ by (blast dest: OrdmemD) -subsection{*The Construction of Ordinals: 0, succ, Union*} +subsection\The Construction of Ordinals: 0, succ, Union\ lemma Ord_0 [iff,TC]: "Ord(0)" by (blast intro: OrdI Transset_0) @@ -172,7 +172,7 @@ apply (blast intro!: Transset_Int) done -text{*There is no set of all ordinals, for then it would contain itself*} +text\There is no set of all ordinals, for then it would contain itself\ lemma ON_class: "~ (\i. i\X <-> Ord(i))" proof (rule notI) assume X: "\i. i \ X \ Ord(i)" @@ -187,7 +187,7 @@ thus "False" by (rule mem_irrefl) qed -subsection{*< is 'less Than' for Ordinals*} +subsection\< is 'less Than' for Ordinals\ lemma ltI: "[| i\j; Ord(j) |] ==> i j"} abbreviates @{term"iRecall that @{term"i \ j"} abbreviates @{term"i lemma le_iff: "i \ j <-> iNatural Deduction Rules for Memrel\ (*The lemmas MemrelI/E give better speed than [iff] here*) lemma Memrel_iff [simp]: " \ Memrel(A) <-> a\b & a\A & b\A" @@ -307,12 +307,12 @@ apply (rule foundation [THEN disjE, THEN allI], erule disjI1, blast) done -text{*The premise @{term "Ord(i)"} does not suffice.*} +text\The premise @{term "Ord(i)"} does not suffice.\ lemma trans_Memrel: "Ord(i) ==> trans(Memrel(i))" by (unfold Ord_def Transset_def trans_def, blast) -text{*However, the following premise is strong enough.*} +text\However, the following premise is strong enough.\ lemma Transset_trans_Memrel: "\j\i. Transset(j) ==> trans(Memrel(i))" by (unfold Transset_def trans_def, blast) @@ -323,7 +323,7 @@ by (unfold Transset_def, blast) -subsection{*Transfinite Induction*} +subsection\Transfinite Induction\ (*Epsilon induction over a transitive set*) lemma Transset_induct: @@ -348,17 +348,17 @@ done -section{*Fundamental properties of the epsilon ordering (< on ordinals)*} +section\Fundamental properties of the epsilon ordering (< on ordinals)\ -subsubsection{*Proving That < is a Linear Ordering on the Ordinals*} +subsubsection\Proving That < is a Linear Ordering on the Ordinals\ lemma Ord_linear: "Ord(i) \ Ord(j) \ i\j | i=j | j\i" proof (induct i arbitrary: j rule: trans_induct) case (step i) note step_i = step - show ?case using `Ord(j)` + show ?case using \Ord(j)\ proof (induct j rule: trans_induct) case (step j) thus ?case using step_i @@ -366,7 +366,7 @@ qed qed -text{*The trichotomy law for ordinals*} +text\The trichotomy law for ordinals\ lemma Ord_linear_lt: assumes o: "Ord(i)" "Ord(j)" obtains (lt) "i j \ i" by (rule_tac i = i and j = j in Ord_linear2, auto) -subsubsection{*Some Rewrite Rules for <, le*} +subsubsection\Some Rewrite Rules for <, le\ lemma Ord_mem_iff_lt: "Ord(j) ==> i\j <-> iResults about Less-Than or Equals\ (** For ordinals, @{term"j\i"} implies @{term"j \ i"} (less-than or equals) **) @@ -446,7 +446,7 @@ lemma all_lt_imp_le: "[| Ord(i); Ord(j); !!x. x x j \ i" by (blast intro: not_lt_imp_le dest: lt_irrefl) -subsubsection{*Transitivity Laws*} +subsubsection\Transitivity Laws\ lemma lt_trans1: "[| i \ j; j iUnion and Intersection\ lemma Un_upper1_le: "[| Ord(i); Ord(j) |] ==> i \ i \ j" by (rule Un_upper1 [THEN subset_imp_le], auto) @@ -560,7 +560,7 @@ by (blast intro: Ord_trans) -subsection{*Results about Limits*} +subsection\Results about Limits\ lemma Ord_Union [intro,simp,TC]: "[| !!i. i\A ==> Ord(i) |] ==> Ord(\(A))" apply (rule Ord_is_Transset [THEN Transset_Union_family, THEN OrdI]) @@ -633,7 +633,7 @@ by (blast intro: Ord_trans) -subsection{*Limit Ordinals -- General Properties*} +subsection\Limit Ordinals -- General Properties\ lemma Limit_Union_eq: "Limit(i) ==> \(i) = i" apply (unfold Limit_def) @@ -701,7 +701,7 @@ by (blast elim!: leE) -subsubsection{*Traditional 3-Way Case Analysis on Ordinals*} +subsubsection\Traditional 3-Way Case Analysis on Ordinals\ lemma Ord_cases_disj: "Ord(i) ==> i=0 | (\j. Ord(j) & i=succ(j)) | Limit(i)" by (blast intro!: non_succ_LimitI Ord_0_lt) @@ -723,8 +723,8 @@ lemmas trans_induct3 = trans_induct3_raw [rule_format, case_names 0 succ limit, consumes 1] -text{*A set of ordinals is either empty, contains its own union, or its -union is a limit ordinal.*} +text\A set of ordinals is either empty, contains its own union, or its +union is a limit ordinal.\ lemma Union_le: "[| !!x. x\I ==> x\j; Ord(j) |] ==> \(I) \ j" by (auto simp add: le_subset_iff Union_least) @@ -757,7 +757,7 @@ assume "Limit(\I)" thus ?thesis by auto qed -text{*If the union of a set of ordinals is a successor, then it is an element of that set.*} +text\If the union of a set of ordinals is a successor, then it is an element of that set.\ lemma Ord_Union_eq_succD: "[|\x\X. Ord(x); \X = succ(j)|] ==> succ(j) \ X" by (drule Ord_set_cases, auto)