src/HOL/Algebra/Lattice.thy
changeset 33657 a4179bf442d1
parent 32960 69916a850301
child 35847 19f1f7066917
equal deleted inserted replaced
33648:555e5358b8c9 33657:a4179bf442d1
    16   le :: "['a, 'a] => bool" (infixl "\<sqsubseteq>\<index>" 50)
    16   le :: "['a, 'a] => bool" (infixl "\<sqsubseteq>\<index>" 50)
    17 
    17 
    18 locale weak_partial_order = equivalence L for L (structure) +
    18 locale weak_partial_order = equivalence L for L (structure) +
    19   assumes le_refl [intro, simp]:
    19   assumes le_refl [intro, simp]:
    20       "x \<in> carrier L ==> x \<sqsubseteq> x"
    20       "x \<in> carrier L ==> x \<sqsubseteq> x"
    21     and weak_le_anti_sym [intro]:
    21     and weak_le_antisym [intro]:
    22       "[| x \<sqsubseteq> y; y \<sqsubseteq> x; x \<in> carrier L; y \<in> carrier L |] ==> x .= y"
    22       "[| x \<sqsubseteq> y; y \<sqsubseteq> x; x \<in> carrier L; y \<in> carrier L |] ==> x .= y"
    23     and le_trans [trans]:
    23     and le_trans [trans]:
    24       "[| x \<sqsubseteq> y; y \<sqsubseteq> z; x \<in> carrier L; y \<in> carrier L; z \<in> carrier L |] ==> x \<sqsubseteq> z"
    24       "[| x \<sqsubseteq> y; y \<sqsubseteq> z; x \<in> carrier L; y \<in> carrier L; z \<in> carrier L |] ==> x \<sqsubseteq> z"
    25     and le_cong:
    25     and le_cong:
    26       "\<lbrakk> x .= y; z .= w; x \<in> carrier L; y \<in> carrier L; z \<in> carrier L; w \<in> carrier L \<rbrakk> \<Longrightarrow> x \<sqsubseteq> z \<longleftrightarrow> y \<sqsubseteq> w"
    26       "\<lbrakk> x .= y; z .= w; x \<in> carrier L; y \<in> carrier L; z \<in> carrier L; w \<in> carrier L \<rbrakk> \<Longrightarrow> x \<sqsubseteq> z \<longleftrightarrow> y \<sqsubseteq> w"
   634 proof (rule finite_sup_insertI)
   634 proof (rule finite_sup_insertI)
   635   -- {* The textbook argument in Jacobson I, p 457 *}
   635   -- {* The textbook argument in Jacobson I, p 457 *}
   636   fix s
   636   fix s
   637   assume sup: "least L s (Upper L {x, y, z})"
   637   assume sup: "least L s (Upper L {x, y, z})"
   638   show "x \<squnion> (y \<squnion> z) .= s"
   638   show "x \<squnion> (y \<squnion> z) .= s"
   639   proof (rule weak_le_anti_sym)
   639   proof (rule weak_le_antisym)
   640     from sup L show "x \<squnion> (y \<squnion> z) \<sqsubseteq> s"
   640     from sup L show "x \<squnion> (y \<squnion> z) \<sqsubseteq> s"
   641       by (fastsimp intro!: join_le elim: least_Upper_above)
   641       by (fastsimp intro!: join_le elim: least_Upper_above)
   642   next
   642   next
   643     from sup L show "s \<sqsubseteq> x \<squnion> (y \<squnion> z)"
   643     from sup L show "s \<sqsubseteq> x \<squnion> (y \<squnion> z)"
   644     by (erule_tac least_le)
   644     by (erule_tac least_le)
   875 proof (rule finite_inf_insertI)
   875 proof (rule finite_inf_insertI)
   876   txt {* The textbook argument in Jacobson I, p 457 *}
   876   txt {* The textbook argument in Jacobson I, p 457 *}
   877   fix i
   877   fix i
   878   assume inf: "greatest L i (Lower L {x, y, z})"
   878   assume inf: "greatest L i (Lower L {x, y, z})"
   879   show "x \<sqinter> (y \<sqinter> z) .= i"
   879   show "x \<sqinter> (y \<sqinter> z) .= i"
   880   proof (rule weak_le_anti_sym)
   880   proof (rule weak_le_antisym)
   881     from inf L show "i \<sqsubseteq> x \<sqinter> (y \<sqinter> z)"
   881     from inf L show "i \<sqsubseteq> x \<sqinter> (y \<sqinter> z)"
   882       by (fastsimp intro!: meet_le elim: greatest_Lower_below)
   882       by (fastsimp intro!: meet_le elim: greatest_Lower_below)
   883   next
   883   next
   884     from inf L show "x \<sqinter> (y \<sqinter> z) \<sqsubseteq> i"
   884     from inf L show "x \<sqinter> (y \<sqinter> z) \<sqsubseteq> i"
   885     by (erule_tac greatest_le)
   885     by (erule_tac greatest_le)
  1087 
  1087 
  1088 locale partial_order = weak_partial_order +
  1088 locale partial_order = weak_partial_order +
  1089   assumes eq_is_equal: "op .= = op ="
  1089   assumes eq_is_equal: "op .= = op ="
  1090 begin
  1090 begin
  1091 
  1091 
  1092 declare weak_le_anti_sym [rule del]
  1092 declare weak_le_antisym [rule del]
  1093 
  1093 
  1094 lemma le_anti_sym [intro]:
  1094 lemma le_antisym [intro]:
  1095   "[| x \<sqsubseteq> y; y \<sqsubseteq> x; x \<in> carrier L; y \<in> carrier L |] ==> x = y"
  1095   "[| x \<sqsubseteq> y; y \<sqsubseteq> x; x \<in> carrier L; y \<in> carrier L |] ==> x = y"
  1096   using weak_le_anti_sym unfolding eq_is_equal .
  1096   using weak_le_antisym unfolding eq_is_equal .
  1097 
  1097 
  1098 lemma lless_eq:
  1098 lemma lless_eq:
  1099   "x \<sqsubset> y \<longleftrightarrow> x \<sqsubseteq> y & x \<noteq> y"
  1099   "x \<sqsubset> y \<longleftrightarrow> x \<sqsubseteq> y & x \<noteq> y"
  1100   unfolding lless_def by (simp add: eq_is_equal)
  1100   unfolding lless_def by (simp add: eq_is_equal)
  1101 
  1101