equal
deleted
inserted
replaced
7 theory Orders imports Main begin |
7 theory Orders imports Main begin |
8 |
8 |
9 subsection \<open>Ordered structures\<close> |
9 subsection \<open>Ordered structures\<close> |
10 |
10 |
11 text \<open> |
11 text \<open> |
12 We define several classes of ordered structures over some type @{typ |
12 We define several classes of ordered structures over some type \<^typ>\<open>'a\<close> with relation \<open>\<sqsubseteq> :: 'a \<Rightarrow> 'a \<Rightarrow> bool\<close>. For a |
13 'a} with relation \<open>\<sqsubseteq> :: 'a \<Rightarrow> 'a \<Rightarrow> bool\<close>. For a |
|
14 \emph{quasi-order} that relation is required to be reflexive and |
13 \emph{quasi-order} that relation is required to be reflexive and |
15 transitive, for a \emph{partial order} it also has to be |
14 transitive, for a \emph{partial order} it also has to be |
16 anti-symmetric, while for a \emph{linear order} all elements are |
15 anti-symmetric, while for a \emph{linear order} all elements are |
17 required to be related (in either direction). |
16 required to be related (in either direction). |
18 \<close> |
17 \<close> |
63 |
62 |
64 lemma dual_leq [iff?]: "(dual x \<sqsubseteq> dual y) = (y \<sqsubseteq> x)" |
63 lemma dual_leq [iff?]: "(dual x \<sqsubseteq> dual y) = (y \<sqsubseteq> x)" |
65 by (simp add: leq_dual_def) |
64 by (simp add: leq_dual_def) |
66 |
65 |
67 text \<open> |
66 text \<open> |
68 \medskip Functions @{term dual} and @{term undual} are inverse to |
67 \medskip Functions \<^term>\<open>dual\<close> and \<^term>\<open>undual\<close> are inverse to |
69 each other; this entails the following fundamental properties. |
68 each other; this entails the following fundamental properties. |
70 \<close> |
69 \<close> |
71 |
70 |
72 lemma dual_undual [simp]: "dual (undual x') = x'" |
71 lemma dual_undual [simp]: "dual (undual x') = x'" |
73 by (cases x') simp |
72 by (cases x') simp |
77 |
76 |
78 lemma dual_undual_id [simp]: "dual o undual = id" |
77 lemma dual_undual_id [simp]: "dual o undual = id" |
79 by (rule ext) simp |
78 by (rule ext) simp |
80 |
79 |
81 text \<open> |
80 text \<open> |
82 \medskip Since @{term dual} (and @{term undual}) are both injective |
81 \medskip Since \<^term>\<open>dual\<close> (and \<^term>\<open>undual\<close>) are both injective |
83 and surjective, the basic logical connectives (equality, |
82 and surjective, the basic logical connectives (equality, |
84 quantification etc.) are transferred as follows. |
83 quantification etc.) are transferred as follows. |
85 \<close> |
84 \<close> |
86 |
85 |
87 lemma undual_equality [iff?]: "(undual x' = undual y') = (x' = y')" |
86 lemma undual_equality [iff?]: "(undual x' = undual y') = (x' = y')" |