src/HOL/Library/Order_Relation.thy
changeset 30198 922f944f03b2
parent 29859 33bff35f1335
child 30661 54858c8ad226
equal deleted inserted replaced
30193:391e10b42889 30198:922f944f03b2
     8 imports Main
     8 imports Main
     9 begin
     9 begin
    10 
    10 
    11 subsection{* Orders on a set *}
    11 subsection{* Orders on a set *}
    12 
    12 
    13 definition "preorder_on A r \<equiv> refl A r \<and> trans r"
    13 definition "preorder_on A r \<equiv> refl_on A r \<and> trans r"
    14 
    14 
    15 definition "partial_order_on A r \<equiv> preorder_on A r \<and> antisym r"
    15 definition "partial_order_on A r \<equiv> preorder_on A r \<and> antisym r"
    16 
    16 
    17 definition "linear_order_on A r \<equiv> partial_order_on A r \<and> total_on A r"
    17 definition "linear_order_on A r \<equiv> partial_order_on A r \<and> total_on A r"
    18 
    18 
    55 by(simp add: order_on_defs trans_diff_Id)
    55 by(simp add: order_on_defs trans_diff_Id)
    56 
    56 
    57 
    57 
    58 subsection{* Orders on the field *}
    58 subsection{* Orders on the field *}
    59 
    59 
    60 abbreviation "Refl r \<equiv> refl (Field r) r"
    60 abbreviation "Refl r \<equiv> refl_on (Field r) r"
    61 
    61 
    62 abbreviation "Preorder r \<equiv> preorder_on (Field r) r"
    62 abbreviation "Preorder r \<equiv> preorder_on (Field r) r"
    63 
    63 
    64 abbreviation "Partial_order r \<equiv> partial_order_on (Field r) r"
    64 abbreviation "Partial_order r \<equiv> partial_order_on (Field r) r"
    65 
    65 
    71 
    71 
    72 
    72 
    73 lemma subset_Image_Image_iff:
    73 lemma subset_Image_Image_iff:
    74   "\<lbrakk> Preorder r; A \<subseteq> Field r; B \<subseteq> Field r\<rbrakk> \<Longrightarrow>
    74   "\<lbrakk> Preorder r; A \<subseteq> Field r; B \<subseteq> Field r\<rbrakk> \<Longrightarrow>
    75    r `` A \<subseteq> r `` B \<longleftrightarrow> (\<forall>a\<in>A.\<exists>b\<in>B. (b,a):r)"
    75    r `` A \<subseteq> r `` B \<longleftrightarrow> (\<forall>a\<in>A.\<exists>b\<in>B. (b,a):r)"
    76 apply(auto simp add: subset_eq preorder_on_def refl_def Image_def)
    76 apply(auto simp add: subset_eq preorder_on_def refl_on_def Image_def)
    77 apply metis
    77 apply metis
    78 by(metis trans_def)
    78 by(metis trans_def)
    79 
    79 
    80 lemma subset_Image1_Image1_iff:
    80 lemma subset_Image1_Image1_iff:
    81   "\<lbrakk> Preorder r; a : Field r; b : Field r\<rbrakk> \<Longrightarrow> r `` {a} \<subseteq> r `` {b} \<longleftrightarrow> (b,a):r"
    81   "\<lbrakk> Preorder r; a : Field r; b : Field r\<rbrakk> \<Longrightarrow> r `` {a} \<subseteq> r `` {b} \<longleftrightarrow> (b,a):r"
    82 by(simp add:subset_Image_Image_iff)
    82 by(simp add:subset_Image_Image_iff)
    83 
    83 
    84 lemma Refl_antisym_eq_Image1_Image1_iff:
    84 lemma Refl_antisym_eq_Image1_Image1_iff:
    85   "\<lbrakk>Refl r; antisym r; a:Field r; b:Field r\<rbrakk> \<Longrightarrow> r `` {a} = r `` {b} \<longleftrightarrow> a=b"
    85   "\<lbrakk>Refl r; antisym r; a:Field r; b:Field r\<rbrakk> \<Longrightarrow> r `` {a} = r `` {b} \<longleftrightarrow> a=b"
    86 by(simp add: expand_set_eq antisym_def refl_def) metis
    86 by(simp add: expand_set_eq antisym_def refl_on_def) metis
    87 
    87 
    88 lemma Partial_order_eq_Image1_Image1_iff:
    88 lemma Partial_order_eq_Image1_Image1_iff:
    89   "\<lbrakk>Partial_order r; a:Field r; b:Field r\<rbrakk> \<Longrightarrow> r `` {a} = r `` {b} \<longleftrightarrow> a=b"
    89   "\<lbrakk>Partial_order r; a:Field r; b:Field r\<rbrakk> \<Longrightarrow> r `` {a} = r `` {b} \<longleftrightarrow> a=b"
    90 by(auto simp:order_on_defs Refl_antisym_eq_Image1_Image1_iff)
    90 by(auto simp:order_on_defs Refl_antisym_eq_Image1_Image1_iff)
    91 
    91