equal
deleted
inserted
replaced
43 "\<lbrakk>refl(A,r); r \<subseteq> A*A\<rbrakk> \<Longrightarrow> r \<subseteq> converse(r) O r" |
43 "\<lbrakk>refl(A,r); r \<subseteq> A*A\<rbrakk> \<Longrightarrow> r \<subseteq> converse(r) O r" |
44 by (unfold refl_def, blast) |
44 by (unfold refl_def, blast) |
45 |
45 |
46 lemma equiv_comp_eq: |
46 lemma equiv_comp_eq: |
47 "equiv(A,r) \<Longrightarrow> converse(r) O r = r" |
47 "equiv(A,r) \<Longrightarrow> converse(r) O r = r" |
48 apply (unfold equiv_def) |
48 unfolding equiv_def |
49 apply (blast del: subsetI intro!: sym_trans_comp_subset refl_comp_subset) |
49 apply (blast del: subsetI intro!: sym_trans_comp_subset refl_comp_subset) |
50 done |
50 done |
51 |
51 |
52 (*second half*) |
52 (*second half*) |
53 lemma comp_equivI: |
53 lemma comp_equivI: |
64 "\<lbrakk>sym(r); trans(r); \<langle>a,b\<rangle>: r\<rbrakk> \<Longrightarrow> r``{a} \<subseteq> r``{b}" |
64 "\<lbrakk>sym(r); trans(r); \<langle>a,b\<rangle>: r\<rbrakk> \<Longrightarrow> r``{a} \<subseteq> r``{b}" |
65 by (unfold trans_def sym_def, blast) |
65 by (unfold trans_def sym_def, blast) |
66 |
66 |
67 lemma equiv_class_eq: |
67 lemma equiv_class_eq: |
68 "\<lbrakk>equiv(A,r); \<langle>a,b\<rangle>: r\<rbrakk> \<Longrightarrow> r``{a} = r``{b}" |
68 "\<lbrakk>equiv(A,r); \<langle>a,b\<rangle>: r\<rbrakk> \<Longrightarrow> r``{a} = r``{b}" |
69 apply (unfold equiv_def) |
69 unfolding equiv_def |
70 apply (safe del: subsetI intro!: equalityI equiv_class_subset) |
70 apply (safe del: subsetI intro!: equalityI equiv_class_subset) |
71 apply (unfold sym_def, blast) |
71 apply (unfold sym_def, blast) |
72 done |
72 done |
73 |
73 |
74 lemma equiv_class_self: |
74 lemma equiv_class_self: |
102 (*** Quotients ***) |
102 (*** Quotients ***) |
103 |
103 |
104 (** Introduction/elimination rules -- needed? **) |
104 (** Introduction/elimination rules -- needed? **) |
105 |
105 |
106 lemma quotientI [TC]: "x \<in> A \<Longrightarrow> r``{x}: A//r" |
106 lemma quotientI [TC]: "x \<in> A \<Longrightarrow> r``{x}: A//r" |
107 apply (unfold quotient_def) |
107 unfolding quotient_def |
108 apply (erule RepFunI) |
108 apply (erule RepFunI) |
109 done |
109 done |
110 |
110 |
111 lemma quotientE: |
111 lemma quotientE: |
112 "\<lbrakk>X \<in> A//r; \<And>x. \<lbrakk>X = r``{x}; x \<in> A\<rbrakk> \<Longrightarrow> P\<rbrakk> \<Longrightarrow> P" |
112 "\<lbrakk>X \<in> A//r; \<And>x. \<lbrakk>X = r``{x}; x \<in> A\<rbrakk> \<Longrightarrow> P\<rbrakk> \<Longrightarrow> P" |
116 "equiv(A,r) \<Longrightarrow> \<Union>(A//r) = A" |
116 "equiv(A,r) \<Longrightarrow> \<Union>(A//r) = A" |
117 by (unfold equiv_def refl_def quotient_def, blast) |
117 by (unfold equiv_def refl_def quotient_def, blast) |
118 |
118 |
119 lemma quotient_disj: |
119 lemma quotient_disj: |
120 "\<lbrakk>equiv(A,r); X \<in> A//r; Y \<in> A//r\<rbrakk> \<Longrightarrow> X=Y | (X \<inter> Y \<subseteq> 0)" |
120 "\<lbrakk>equiv(A,r); X \<in> A//r; Y \<in> A//r\<rbrakk> \<Longrightarrow> X=Y | (X \<inter> Y \<subseteq> 0)" |
121 apply (unfold quotient_def) |
121 unfolding quotient_def |
122 apply (safe intro!: equiv_class_eq, assumption) |
122 apply (safe intro!: equiv_class_eq, assumption) |
123 apply (unfold equiv_def trans_def sym_def, blast) |
123 apply (unfold equiv_def trans_def sym_def, blast) |
124 done |
124 done |
125 |
125 |
126 subsection\<open>Defining Unary Operations upon Equivalence Classes\<close> |
126 subsection\<open>Defining Unary Operations upon Equivalence Classes\<close> |