src/HOL/Orderings.thy
changeset 22068 00bed5ac9884
parent 21818 4d2ad5445c81
child 22206 8cc04341de38
equal deleted inserted replaced
22067:39d5d42116c4 22068:00bed5ac9884
   120 end
   120 end
   121 
   121 
   122 
   122 
   123 subsection {* Partial orderings *}
   123 subsection {* Partial orderings *}
   124 
   124 
   125 locale partial_order = preorder + 
   125 locale order = preorder + 
   126   assumes antisym: "x \<sqsubseteq> y \<Longrightarrow> y \<sqsubseteq> x \<Longrightarrow> x = y"
   126   assumes antisym: "x \<sqsubseteq> y \<Longrightarrow> y \<sqsubseteq> x \<Longrightarrow> x = y"
   127 
   127 
   128 context partial_order
   128 context order
   129 begin
   129 begin
   130 
   130 
   131 text {* Asymmetry. *}
   131 text {* Asymmetry. *}
   132 
   132 
   133 lemma less_not_sym: "x \<sqsubset> y \<Longrightarrow> \<not> (y \<sqsubset> x)"
   133 lemma less_not_sym: "x \<sqsubset> y \<Longrightarrow> \<not> (y \<sqsubset> x)"
   179   order_trans: "x <= y ==> y <= z ==> x <= z"
   179   order_trans: "x <= y ==> y <= z ==> x <= z"
   180   order_antisym: "x <= y ==> y <= x ==> x = y"
   180   order_antisym: "x <= y ==> y <= x ==> x = y"
   181   order_less_le: "(x < y) = (x <= y & x ~= y)"
   181   order_less_le: "(x < y) = (x <= y & x ~= y)"
   182 
   182 
   183 interpretation order:
   183 interpretation order:
   184   partial_order ["op \<le> \<Colon> 'a\<Colon>order \<Rightarrow> 'a \<Rightarrow> bool" "op < \<Colon> 'a\<Colon>order \<Rightarrow> 'a \<Rightarrow> bool"]
   184   order ["op \<le> \<Colon> 'a\<Colon>order \<Rightarrow> 'a \<Rightarrow> bool" "op < \<Colon> 'a\<Colon>order \<Rightarrow> 'a \<Rightarrow> bool"]
   185 apply unfold_locales
   185 apply unfold_locales
   186 apply (rule order_refl)
   186 apply (rule order_refl)
   187 apply (erule (1) order_trans)
   187 apply (erule (1) order_trans)
   188 apply (rule order_less_le)
   188 apply (rule order_less_le)
   189 apply (erule (1) order_antisym)
   189 apply (erule (1) order_antisym)
   190 done
   190 done
   191 
   191 
   192 
   192 
   193 subsection {* Linear (total) orders *}
   193 subsection {* Linear (total) orders *}
   194 
   194 
   195 locale linorder = partial_order +
   195 locale linorder = order +
   196   assumes linear: "x \<sqsubseteq> y \<or> y \<sqsubseteq> x"
   196   assumes linear: "x \<sqsubseteq> y \<or> y \<sqsubseteq> x"
   197 begin
   197 begin
   198 
   198 
   199 lemma less_linear: "x \<sqsubset> y \<or> x = y \<or> y \<sqsubset> x"
   199 lemma less_linear: "x \<sqsubset> y \<or> x = y \<or> y \<sqsubset> x"
   200   unfolding less_le using less_le linear by blast 
   200   unfolding less_le using less_le linear by blast