src/HOL/Orderings.thy
changeset 21404 eb85850d3eb7
parent 21383 17e6275e13f5
child 21412 a259061ad0b0
equal deleted inserted replaced
21403:dd58f13a8eb4 21404:eb85850d3eb7
    17   fixes less_eq :: "'a \<Rightarrow> 'a \<Rightarrow> bool"
    17   fixes less_eq :: "'a \<Rightarrow> 'a \<Rightarrow> bool"
    18     and less :: "'a \<Rightarrow> 'a \<Rightarrow> bool"
    18     and less :: "'a \<Rightarrow> 'a \<Rightarrow> bool"
    19 begin
    19 begin
    20 
    20 
    21 notation
    21 notation
    22   less_eq  ("op \<^loc><=")
    22   less_eq  ("op \<^loc><=") and
    23   less_eq  ("(_/ \<^loc><= _)" [51, 51] 50)
    23   less_eq  ("(_/ \<^loc><= _)" [51, 51] 50) and
    24   less  ("op \<^loc><")
    24   less  ("op \<^loc><") and
    25   less  ("(_/ \<^loc>< _)"  [51, 51] 50)
    25   less  ("(_/ \<^loc>< _)"  [51, 51] 50)
    26 
    26 
    27 notation (xsymbols)
    27 notation (xsymbols)
    28   less_eq  ("op \<^loc>\<le>")
    28   less_eq  ("op \<^loc>\<le>") and
    29   less_eq  ("(_/ \<^loc>\<le> _)"  [51, 51] 50)
    29   less_eq  ("(_/ \<^loc>\<le> _)"  [51, 51] 50)
    30 
    30 
    31 notation (HTML output)
    31 notation (HTML output)
    32   less_eq  ("op \<^loc>\<le>")
    32   less_eq  ("op \<^loc>\<le>") and
    33   less_eq  ("(_/ \<^loc>\<le> _)"  [51, 51] 50)
    33   less_eq  ("(_/ \<^loc>\<le> _)"  [51, 51] 50)
    34 
    34 
    35 abbreviation (input)
    35 abbreviation (input)
    36   greater  (infix "\<^loc>>" 50)
    36   greater  (infix "\<^loc>>" 50) where
    37   "x \<^loc>> y \<equiv> y \<^loc>< x"
    37   "x \<^loc>> y \<equiv> y \<^loc>< x"
    38   greater_eq  (infix "\<^loc>>=" 50)
    38 
       
    39 abbreviation (input)
       
    40   greater_eq  (infix "\<^loc>>=" 50) where
    39   "x \<^loc>>= y \<equiv> y \<^loc><= x"
    41   "x \<^loc>>= y \<equiv> y \<^loc><= x"
    40 
    42 
    41 notation (xsymbols)
    43 notation (xsymbols)
    42   greater_eq  (infix "\<^loc>\<ge>" 50)
    44   greater_eq  (infix "\<^loc>\<ge>" 50)
    43 
    45 
    44 end
    46 end
    45 
    47 
    46 notation
    48 notation
    47   less_eq  ("op <=")
    49   less_eq  ("op <=") and
    48   less_eq  ("(_/ <= _)" [51, 51] 50)
    50   less_eq  ("(_/ <= _)" [51, 51] 50) and
    49   less  ("op <")
    51   less  ("op <") and
    50   less  ("(_/ < _)"  [51, 51] 50)
    52   less  ("(_/ < _)"  [51, 51] 50)
    51   
    53   
    52 notation (xsymbols)
    54 notation (xsymbols)
    53   less_eq  ("op \<le>")
    55   less_eq  ("op \<le>") and
    54   less_eq  ("(_/ \<le> _)"  [51, 51] 50)
    56   less_eq  ("(_/ \<le> _)"  [51, 51] 50)
    55 
    57 
    56 notation (HTML output)
    58 notation (HTML output)
    57   less_eq  ("op \<le>")
    59   less_eq  ("op \<le>") and
    58   less_eq  ("(_/ \<le> _)"  [51, 51] 50)
    60   less_eq  ("(_/ \<le> _)"  [51, 51] 50)
    59 
    61 
    60 abbreviation (input)
    62 abbreviation (input)
    61   greater  (infix ">" 50)
    63   greater  (infix ">" 50) where
    62   "x > y \<equiv> y < x"
    64   "x > y \<equiv> y < x"
    63   greater_eq  (infix ">=" 50)
    65 
       
    66 abbreviation (input)
       
    67   greater_eq  (infix ">=" 50) where
    64   "x >= y \<equiv> y <= x"
    68   "x >= y \<equiv> y <= x"
    65   
    69   
    66 notation (xsymbols)
    70 notation (xsymbols)
    67   greater_eq  (infix "\<ge>" 50)
    71   greater_eq  (infix "\<ge>" 50)
    68 
    72 
    76   and trans: "x \<sqsubseteq> y \<Longrightarrow> y \<sqsubseteq> z \<Longrightarrow> x \<sqsubseteq> z"
    80   and trans: "x \<sqsubseteq> y \<Longrightarrow> y \<sqsubseteq> z \<Longrightarrow> x \<sqsubseteq> z"
    77   and less_le: "x \<sqsubset> y \<longleftrightarrow> x \<sqsubseteq> y \<and> x \<noteq> y"
    81   and less_le: "x \<sqsubset> y \<longleftrightarrow> x \<sqsubseteq> y \<and> x \<noteq> y"
    78 begin
    82 begin
    79 
    83 
    80 abbreviation (input)
    84 abbreviation (input)
    81   greater_eq (infixl "\<sqsupseteq>" 50)
    85   greater_eq  (infixl "\<sqsupseteq>" 50) where
    82   "x \<sqsupseteq> y \<equiv> y \<sqsubseteq> x"
    86   "x \<sqsupseteq> y \<equiv> y \<sqsubseteq> x"
    83 
    87 
    84 abbreviation (input)
    88 abbreviation (input)
    85   greater (infixl "\<sqsupset>" 50)
    89   greater (infixl "\<sqsupset>" 50) where
    86   "x \<sqsupset> y \<equiv> y \<sqsubset> x"
    90   "x \<sqsupset> y \<equiv> y \<sqsubset> x"
    87 
    91 
    88 text {* Reflexivity. *}
    92 text {* Reflexivity. *}
    89 
    93 
    90 lemma eq_refl: "x = y \<Longrightarrow> x \<sqsubseteq> y"
    94 lemma eq_refl: "x = y \<Longrightarrow> x \<sqsubseteq> y"
   200 
   204 
   201 subsection {* Linear (total) orders *}
   205 subsection {* Linear (total) orders *}
   202 
   206 
   203 locale linorder = partial_order +
   207 locale linorder = partial_order +
   204   assumes linear: "x \<sqsubseteq> y \<or> y \<sqsubseteq> x"
   208   assumes linear: "x \<sqsubseteq> y \<or> y \<sqsubseteq> x"
   205 
       
   206 context linorder
       
   207 begin
   209 begin
   208 
   210 
   209 lemma trichotomy: "x \<sqsubset> y \<or> x = y \<or> y \<sqsubset> x"
   211 lemma trichotomy: "x \<sqsubset> y \<or> x = y \<or> y \<sqsubset> x"
   210   unfolding less_le using less_le linear by blast 
   212   unfolding less_le using less_le linear by blast 
   211 
   213 
   257   unfolding not_le .
   259   unfolding not_le .
   258 
   260 
   259 (* min/max *)
   261 (* min/max *)
   260 
   262 
   261 definition
   263 definition
   262   min :: "'a \<Rightarrow> 'a \<Rightarrow> 'a"
   264   min :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" where
   263   "min a b = (if a \<sqsubseteq> b then a else b)"
   265   "min a b = (if a \<sqsubseteq> b then a else b)"
   264   max :: "'a \<Rightarrow> 'a \<Rightarrow> 'a"
   266 
       
   267 definition
       
   268   max :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" where
   265   "max a b = (if a \<sqsubseteq> b then b else a)"
   269   "max a b = (if a \<sqsubseteq> b then b else a)"
   266 
   270 
   267 lemma min_le_iff_disj:
   271 lemma min_le_iff_disj:
   268   "min x y \<sqsubseteq> z \<longleftrightarrow> x \<sqsubseteq> z \<or> y \<sqsubseteq> z"
   272   "min x y \<sqsubseteq> z \<longleftrightarrow> x \<sqsubseteq> z \<or> y \<sqsubseteq> z"
   269   unfolding min_def using linear by (auto intro: trans)
   273   unfolding min_def using linear by (auto intro: trans)